Home
Latest release 4.7.4 GNU Lesser General Public License (LGPL)
QuarkTS its 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.
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.
This basic capabilities and their small memory footprint, make it suitable for small embedded µController systems.
QuarkTS has no direct hardware dependencies, so it is portable to many platforms. The following cores has been powered with QuarkTS successfully:
- ARM cores(ATMEL, STM32, Kinetis, Nordic and NXP)
- AVR
- ColdFire
- PIC (16F, 18F, )
- MSP430
- 8051
- HCS12
- x86
As a quasi-static scheduler is implemented here, dynamic memory allocation is not required 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. In this context, the kernel allow for unlimited tasks and kernel objects (STimers, FSMs, RBuffers, etc). The kernels' memory footprint can be scaled down to contain only the features required for your application, typically 2.5 KBytes of code space and less than 1 KByte of data space.
OS Memory Footprint (Measured in a 32bit MCU with a 4-byte memory alignment)
| Functionality | Size(bytes) |
|---|---|
| Kernel, scheduler and task management | 2637 |
| A task node | 56 |
| Finite State-Machines(FSM) handling and related APIs | 314 |
| A FSM object (qSM_t) | 37 |
| STimers handling and related APIs | 258 |
| A STimer object (qSTimer_t) | 9 |
| RBuffers handling and related APIS | 544 |
| A RBuffer object (qRBuffer_t) | 20 |
| Memory management | 407 |
| A memory pool (qMemoryPool_t) | 5 |
| The AT Command Parser | 1724 |
| An AT-Parser instance (qATParser_t) | 60 |
| An AT command object (qATCommand_t) | 20 |
| Utilities(some I/O APIs, Tracing, I/O EdgeCheck, the responses handle, and some C-std ports) | 2980 |
The kernel implements a Time-Triggered Architecture (TTA), in which the tasks are triggered by comparing the corresponding task-time with a reference clock. The reference clock must be real-time and follow a monotonic behavior. Usually all embedded systems can provide this kind of reference with a constant tick generated by a periodic background hardware-timer, typically, at 1Khz (1mS tick).
The kernel allows you to select the reference clock source among this two scenarios:
- When tick already provided: The reference is supplied by the HAL of the device. Is the simplest scenario and it occurs when the framework or SDK of the embedded system includes a HAL-API that obtains the time elapsed since the system starts, usually in milliseconds, taking a variable 32-bit counter.
- When the tick is not provided: The user should use bare-metal code to configure the device and feed the reference clock manually. Here, a hardware timer should raise an interrupt periodically. After the Interrupt Service Routine (ISR) has been implemented using the platform dependent code, the \lstinline{qSchedulerSysTick} API must be called inside. It is recommended that the reserved ISR should only be used by QuarkTS.
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: 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 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.
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 dynamic 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.
When the level of interaction increases in a multitasking environment, knowing the event that triggered the task execution becomes relevant. The OS 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:
- byTimeElapsed : When the time specified for the task elapsed.
- byQueueExtraction: When the scheduler performs extraction of task-associated data at the beginning of the priority-queue.
- byAsyncEvent: When the execution chain does, according to a requirement of asynchronous event prompted by qTaskSendEvent
- 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.
- byRBufferFull: When the linked ring-buffer is full. A pointer to the RingBuffer will be available in the EventData field.
- 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.
- byRBufferEmpty: When the linked ring-buffer is empty. A pointer to the RingBuffer will be available in the EventData field.
- 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 occurs and the Iteration counter has been parametrized. Asynchronous 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 occurs and the Iteration counter has been parametrized. Asynchronous events never change the task iteration counter, consequently doesn't have effect in this flag
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 programmed 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.
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 1 – Single timed task scheduling
The following example, illustrates the lifetime of a task scheduled to run 4 iterations, every 2 seconds.
// ...
qSchedulerAdd_Task(ExampleTask, ExampleTask_Callback, MEDIUM_Priority, 2.0, 4, qEnabled, NULL);
// ...
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
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.
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.
The OS dispatcher 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 beginning 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 associated 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
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
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 qSchedulerAdd_StateMachineTask API should be used. Here, the task doesn't 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 finish 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 established in the qSchedulerAddSMTask arguments. A state can jump to another by changing the NextState field of the FSM pointer. Also, additional information can be retrieved 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:
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 don't 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 uses the same kernel 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*/
}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;
}
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 acknowledgement 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;
}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.