Skip to content
Eng. Juan Camilo Gómez Cadavid MSc edited this page Mar 7, 2019 · 142 revisions

A Non-Preemptive RTOS for low-range MCUs

Download

Latest release 4.6.6(j) GNU Lesser General Public License (LGPL)

Supported Plataforms : Potentially, anyone. But to clear up doubts, it has been implemented successfully in ARM(ATMEL, STM32, Kinetis and NXP), AVR, PIC, ColdFire, MSP430, 8051, MIPS, HCS12 and x86

What is QuarkTS?

Is a simple non-Preemtive Real-Time OS with a quasi-static scheduler for embedded multi-tasking applications. QuarkTS uses a cooperative Round-Robin scheme with a linked chain approach, and a queue to provide true FIFO priority-scheduling. QuarkTS is suitable for small-footprint embedded systems because it consumes little memory of the system.

The most significant feature of the QuarkTS tasks is that they are NOT preemptable. Once a task starts its execution, it 'owns' the CPU in Base Level (non-Interrupt) until it returns. In other words, except when the CPU is servicing an event in interrupt-level, the CPU will be executing the task until returns, then, the control back to the task-scheduler. This has however, significant benefits: you don't need to worry about concurrency inside the callback method, since only one callback method runs at a time and could not be interrupted. All resources are yours for that period of time, no one can switch the value of variables (except interrupt functions of course...). It is a stable and predictable environment and it helps a lot with writing stable code.

Note 1: QuarkTS has no direct hardware dependencies, so it is portable to many platforms.

Note 2: QuarkTS is a Quasi-static scheduler , consequently, it don't use the dynamic memory allocation and the assignment of tasks must be done before program execution begins, however, most of the scheduling parameters regarding task execution, can be changed at run-time.

Timing approach

QuarkTS uses a Time-Triggered Architecture (TTA), in which the tasks are triggered by comparing the corresponding task-time with a monotonic real-time clock. To meet the real-time requirements, the clock must be fed with a constant tick generated with a periodic background timer. Following the previous specification, is required to configure a hardware timer, such it generates an interrupt at the desired frequency (at least F ≥ 100Hz). After the Interrupt Service Routine (ISR) has been implemented using the platform dependent code, the qSchedulerSysTick API must be called inside. It is recommended that the reserved ISR should only be used by QuarkTS. Additional code instructions could add latency in timed tasks.

Tasks

A task in QuarkTS, is a node concept that links together:

  • Program code performing specific task activities (callback function)
  • Execution interval (Time)
  • Number of execution (iterations)
  • Event-based data

Tasks perform certain functions, which could require periodic or one-time execution, update of specific variables, or waiting for specific events. Tasks also could be controlling specific hardware, or triggered by hardware interrupts.

For execution purposes, the tasks are linked into execution chains, which are processed by the scheduler in priority order.

Each task performs its function via a callback function. All Tasks are responsible for supporting cooperative multitasking by being “good neighbors”, i.e., running their callback methods quickly in a non-blocking way, and releasing control back to scheduler as soon as possible (returning).

Every task node, must be defined using the qTask_t data-type

qTask_t UserTask;
void UserTask_Callback(qEvent_t eventdata){
    /*
    TODO : Task code
    */
}

The task callback is defined as a function that returns void and takes a qEvent_t data structure as its only parameter (This input argument can be used to get event information).

Note: All the QuarkTS tasks must ensure their completion to return the CPU control back to the scheduler, otherwise, the scheduler will hold the execution-state for that task, preventing the activation of other tasks.

Task states and scheduling rules

Task states are classified into the four below:

  • qWaiting : The task cannot run because the conditions for running are not in place. In other words, the task is waiting for the conditions for its execution to be met.
  • qReady : The task has completed preparations for running, but cannot run because a task with higher precedence is running.
  • qRunning : The task is currently being executed.
  • qSuspended : The task doesn‘t take part on what is goining on. Normally this state is taken after the qRunning state or when the task dont reach the qReady state.

Except for the Idle task, a task exists in one of this states. As the real-time embedded system runs, each task moves from one state to another, according to the logic of a simple finite state machine (FSM). Figure illustrates the typical FSM followed by QuarkTS for task execution states, with brief descriptions of state transitions.

Task management

QuarkTS assumes that none of the task does a block anywhere during the qRunning state. Based in the Round-robin fashion, each ready task runs in turn only from the linked list or the priority-queue, here, the priority parameter set its position in the list statically and in the queue in a dinamic way.

Task precedence is used as the task scheduling rule, and precedence among tasks is determined as follows based on the priority of each task. If there are multiple tasks that can be run, the one with the highest precedence goes to qRunning state and the others go to qReady state. In determining precedence among tasks, of those tasks having different priority levels, that with the highest priority has the highest precedence. Among tasks having the same priority, the one that entered to the scheduling scheme first has the highest precedence.

Event data

When the level of interaction increases in a multitasking environment, knowing the event that triggered the task execution becomes relevant. QuarkTS provides a simple approach for this, a data structure as input argument in the callback with all the regarding information of the task execution.

The data structure is defined as:

   typedef struct{
        qTrigger_t Trigger;
        void *TaskData;
        void *EventData;
        qBool_t FirstCall, FirstIteration, LastIteration;
    }qEvent_t;

Every field of the structure are described as follows

  • Trigger: The flag that indicates the event source that triggers the task execution. This flag can only have eight(8) possible values:
    1. byTimeElapsed : When the time specified for the task elapsed.
    2. byQueueExtraction: When the scheduler performs extraction of task-associated data at the beginning of the priority-queue.
    3. byAsyncEvent: When the execution chain does, according to a requirement of asynchronous event prompted by qTaskSendEvent
    4. byRBufferPop: When there is elements available in the linked ring-buffer, the scheduler makes a data extraction (auto-pop) from the head. A pointer to the extracted (popped) data will be available in the _EventData_field.
    5. byRBufferFull: When the linked ring-buffer is full. A pointer to the RingBuffer will be available in the EventData field.
    6. byRBufferCount: When the element-count of the linked ring-buffer reaches the specified value. A pointer to the RingBuffer will be available in the EventData field.
    7. byRBufferEmpty: When the linked ring-buffer is empty. A pointer to the RingBuffer will be available in the EventData field.
    8. byNoReadyTasks: Only when the Idle Task is triggered.
  • TaskData: The storage pointer. Tasks can store a pointer to specific variable, structure or array, which represents specific user data for a particular task. This may be needed if you plan to use the same callback method for multiple tasks.
  • EventData: Associated data of the event. Specific data will reside here according to the event source. This field will only have a NULL value when the trigger is byTimeElapsed or byPriority.
  • FirstCall :This flag indicates that a task is running for the first time. This flag can be used for data initialization purposes.
  • FirstIteration :Indicates whether current pass is the first iteration of the task. This flag will be only set when time-elapsed events occours and the Iteration counter has been parametrized. Asyncronous events never change the task iteration counter, consequently doesn't have effect in this flag .
  • LastIteration :Indicates whether current pass is the last iteration of the task. This flag will be only set when time-elapsed events occours and the Iteration counter has been parametrized. Asyncronous events never change the task iteration counter, consequently doesn't have effect in this flag

Activation Events

Time elapsed

Running tasks at pre-determined rates is desirable in many situations, like sensory data acquisition, low-level servoing, control loops, action planning and system monitoring. With QuarkTS, you can schedule tasks at an interval your design demands (at least, if the time specification is lower than the scheduler tick). When an application consists of several periodic tasks with individual timing constraints, a few points must be taken:

  • When the time interval of a task has elapsed, the scheduler triggers an event that generates its execution (byTimeElapsed) (see Figure 1).
  • If a task has a finite number iterations, the scheduler will disable the task when the number of iterations reaches the programed value.
  • Tasks always have an inherent time-lag that can be noticed even more, when the programmed time-interval is too low. In a real-time context, it is important to reduce this time-lag or jitter, to an acceptable level for the application. QuarkTS can generally meet a time deadline if you use lightweight code in the callbacks and there is a reduced pool of pending tasks, so it can be considered a soft real-time scheduler, however it cannot meet a deadline deterministically like a hard real-time OS. Single timed task Figure 1 – Single timed task scheduling
  • The most significant delay times are produced inside the callbacks. As mentioned before, use short efficient callback methods written for cooperative scheduling.
  • If two tasks have the same time-interval, the scheduler executes first the task with the highest priority value (see Figure 2).

Figure 2 – QuarkTS Non-Preemptive Priority Scheduling Example with three (3) tasks attached Figure 2 – QuarkTS Non-Preemptive Priority Scheduling Example with three (3) tasks attached

The following example, illustrates the lifetime of a task scheduled to run 4 iterations, every 2 seconds.

    // ...
    qSchedulerAddxTask(ExampleTask, ExampleTask_Callback, MEDIUM_Priority, 2.0, 4, qEnabled, NULL);
    // ...

Timed task example Figure 3 – Timed task life time illustration

Asynchronous

Applications existing in heavy environments, like handling multiple peripherals and I/Os, must implement some event model. Events are characterized by changes in the environment at an undetermined time. In embedded systems, "interrupts" is the best method to catch this kind of events. However, sometimes the event-handling requires heavy processing that can overload the ISR and consequently, the system can lose future events. For this kind of applications, we can assign tasks to handle events that need high processing, taking the notification from the interrupt-level and making the actions in the base-level. QuarkTS, can trigger asynchronous events generated by the following mechanisms:

  • Simple send
  • Dequeue (Queue extraction)
  • Linked Ring-Buffers

Simple send

This event can be triggered calling the qTaskSendEvent. This method marks the task as ready for execution, therefore, the planner launch the task immediately according to the execution chain. Note: Sending simple events using qTaskSendEvent is interrupt-safe, however, this only catch one event per task because qTaskSendEvent overwrites the trigger and the event asociated data. So, if your applications notifies multiple events to the same task in the interrupt level, try usign the priority-queue with qTaskQueueEvent.

Dequeue (Queue extraction)

QuarkTs integrates an FIFO priority queue to handle multiple events in a cooperative multitasking environment. This kind of queue, is somewhat similar to a standard queue, with an important distinction: each task is added to the queue with the corresponding priority level, and will be later removed from the queue with the highest priority task first. That is, the tasks are (conceptually) stored in the queue in priority order instead of in insertion order. If two tasks have the same priority, they are served in the FIFO form according to their order in the queue.

FIFO Priority Queue behaivor

QuarkTS always checks the queue state. If the queue has elements (a data associated with a task), the scheduler algorithm will extract the data and the corresponding task will be launched with the Trigger flag set in byQueueExtraction.

The following image, shows a cooperative environment of 5 tasks. Initially, the scheduler activates TASK-E, then, this task enqueues data to Task_A and Task_B respectively using the qTaskQueueEvent function. In the next scheduler cycle, the scheduler realizes that the priority-queue is not empty, generating an activation over the task located at the begining of the queue. In this case, TASK-A will be launched and its respective data will be extracted from the queue. However, TASK-A also enqueues data to Task_C and Task_D. As mentioned previously, this is a priority-queue, so the scheduler makes a new reordering. In this context, the next queue extraction will be for Task_D, Task_C, and Task_B sequentially.

Any queue extraction involves an activation to the asociated task and the extracted data will be passed as argument to the callback function inside the qEvent_t structure.

Note: If your application notifies interrupt-based events using the priority-queue, you must setup the scheduler using qSchedulerSetInterruptsED

Linked Ring-buffers

A ring buffer is a software-based circular FIFO queue that uses a single fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.

In general, this kind of queue is used to serialize data between tasks, allowing some elasticity in time. In many cases, the queue is used as a data buffer in interrupt service routines. This buffer will collect the data so at some later time, another task can fetch the data for further processing. This use case is the single "task to task" buffering case. There is also another applications for ring buffers as serialize many data streams into one receiving streams (Multiple tasks to a single task) or vice versa (single task to multiple tasks)

In QuarkTS, ring buffers come with additional features if they are linked to tasks; in this mode, the Scheduler passes specific Ring-buffer events to it. This events are usually responses to the ring-buffer, for example:

  • Auto-Pop (Data extraction if available)
  • Buffer full
  • Element count
  • Buffer empty

Core extensions

Quark Finite State Machines (qSM)

The state machine is one of the fundamental programming patterns. Designers use this aproach frequently for solving complex engineering problems. State machines break down the design into a series of finite steps called "states". Each state performs some narrowly defined actions. Events, on the other hand, are the stimuli wich cause the state to move, or produce a transition between states.

The best FSM running strategy is delegating it to a task. For this, the qSchedulerAddSMTask API should be used. Here, the task doesnt have a specific callback, instead, the task will evaluate the active state of FSM, and later, all the other possible states in response to events that mark their own transition.

In QuarkTS, states must be defined as functions taking a pointer to the FSM, and returning the fininsh status of the state.

qSM_Status_t Example_State(qSMData_t m){
    /*
    TODO: State code
    */
    return qSM_EXIT_SUCCESS;
}

The finish status of the State can be qSM_EXIT_SUCCESS(-32768), qSM_EXIT_FAILURE(-32767) or any other integer value between -32766 and 32767). The finish status can be handled with additional sub-states stablished in the qSchedulerAddSMTask arguments. A state can jump to another by changing the NextState field of the FSM pointer. Also, aditional information can be retreived checking the other fields of the FSM pointer, as the associated data and previous state. The substates workflow follows the behavior showed in the graph below:

FSM substatates

STimers

There are several situations were the application don't need such hard real-time precision for timing actions and we just need that a section of code will execute when "at least" some amount of time has elapsed. For this purposes, STIMERS (Software-Timers) is the right extension to use. The QuarkTS STimers implementation dont access resources from the interrupt context, does not consume any significant processing time unless a timer has actually expired, does not add any processing overhead to the sys-tick interrupt, and does not walk any other data structures. The timer service just take the value of the existing QuarkTS clock source for reference (tsys), allowing timer functionality to be added to an application with minimal impact.

STimers Features:

  • STimers uses the same QuarkTS clock source, so the time resolution depends of the base-time established in the scheduler when using qSchedulerSetup
  • Provides a non-blocking equivalent to delay function.
  • Each STimer encapsulate its own expiration (timeout) time.
  • Provides elapsed time and remaining time APIs.
void Example_Task(qEvent_t e){
    static qSTimer_t timeout;
    if(e->FirstCall){
         qSTimerSet(&timeout, 3.5); /*Arming the stimer for  3.5 seg*/
    }
    if(qSTimerExpired(&timeout)){ /*non-blocking delay, true when timeout expires*/
        /*
        TODO: Code when STimer expires
        */    
    }
    else return; /*Yield*/
}

CoRoutines

A task coded as a Co-routine, is just a task that allows multiple entry points for suspending and resuming execution at certain locations, this feature can bring benefits by improving the task cooperative scheme and providing a linear code execution for event-driven systems without complex state machines or full multi-threading.

You only need to surround the coroutine body with qCoroutineBegin and qCoroutineEnd, then, you can do qCoroutineYield inside the coroutine segment, consequently, the next call control will resume just after the qCoroutineYield statement.

void CoroutineTask_Callback(qEvent_t e){
    qCoroutineBegin{                  
        /*
        TODO: Coroutine code
        */
    }qCoroutineEnd;
}

qCoroutines

The QuarkTS implementation uses the Duff's device approach, and is heavily inspired from the Simon Tatham's Coroutines in C and Adam Dunkels Protothreads. This implementation does, however, impose slightly restrictions that are listed below:

Limitations and Restrictions:

  • The stack of a co-routine is not maintained when a co-routine yields. This means variables allocated on the stack will loose their values. To overcome this, a variable that must maintain its value across a blocking call must be declared as static.
  • Another consequence of sharing a stack, is that calls to API functions that could cause the co-routine to block, can only be made from the co-routine function itself - not from within a function called by the co-routine.
  • Never put qCoroutineYield within an explicit 'switch'.
void Sender_Task(qEvent_t e){
    static STimer_t timeout;
    qCoroutineBegin{                  
        Send_Packet();
        /* Wait until an ackowledgement has been received, or until the timer expires. 
           If the timer expires, we should send the packet again. */
        qSTimerSet(&timeout, TIMEOUT_TIME);
        qCoroutineWaitUntil( PacketACK_Received() || qSTimerExpired(&timeout));
    }qCoroutineEnd;
}

void Receiver_Task(qEvent_t e){
    qCoroutineBegin{                  
        /* Wait until a packet has been received, and send an acknowledgment. */
        qCoroutineWaitUntil(Packet_Received());
        Send_Acknowledgement();  
    }qCoroutineEnd;
}

Memory Management

There is an implementation of a fixed-size memory allocator with different heaps.

  • The allocating policy is First-Fit.
  • Memory is always allocated from a pre-defined memory heap.
  • Each memory heap has its own defined minimum allocatable size. In practice, this is the size of a memory block.
  • The allocated memory must always be returned to the heap from which was allocated.

Contents:

General info:



APIS

Scheduler Handling

Scheduling scheme

Task Asyncronous events

Task handling

Ring-Buffers

STimers - Software-based timers

Finite State machines (FSM)

Co-routines

Memory management

Utility

Extras and I/O

Byte-Sized Buffers

Bit/Byte/Word Manipulation Macros

  • qBitsSet(Register, Bits)
  • qBitsClear(Register, Bits)
  • qBitSet(Register, Bit)
  • qBitClear(Register, Bit)
  • qBitRead(Register,Bit)
  • qBitToggle(Register,Bit)
  • qBitWrite(Register, Bit, Value)
  • qBitMakeByte(b7,b6,b5,b4,b3,b2,b1,b0) or qByteMakeFromBits(b7,b6,b5,b4,b3,b2,b1,b0)
  • qByteHighNibble(Register)
  • qByteLowNibble(Register)
  • qByteMergeNibbles(H,L)
  • qWordHighByte(Register)
  • qWordLowByte(Register)
  • qWordMergeBytes(H,L)
  • qDWordHighWord(Register)
  • qDWordLowWord(Register)
  • qDWordMergeWords(H,L)
Clone this wiki locally
You can’t perform that action at this time.