Project page

Download

CVS repository

This is another free and small realtime kernel for microcontrollers focused on minimal RAM usage. The “ft” prefix means femto, the next order after nano and pico :)

Primarily this kernel is intended for MSP430 family of microcontrollers. Porting to another architectures is quite simple but on some architectures performance may degrade.

The source code is written in pure C. The preference is given to GCC as free software should be compiled with a free compiler. Assembly language is used only where it is unavoidable.

Two approaches are used to achieve the main design goal: avoiding dynamic memory management and splitting all structures into two parts.

Dynamic memory management adds overhead to all memory blocks and requires some additional code. Without dynamic memory management it is impossible to dynamically create tasks and synchronization objects (more precisely, protected shared objects, PSO). But for tiny systems it is not a key feature. So, all tasks and PSOs are defined at compile time.

Splitting structures that describe tasks and PSO means that they have constant (ROMable) and variable parts. The first one contains static properties, such as priority, address of entry point, address of stack, etc. The variable part is placed in RAM and contains only those properties that require changes at run time.

It is necessary to note that such division requires frequent access to the flash/ROM and on some architectures it may lead to performance degradation. For example in AVR family the access to the flash memory is very painful.

The simplicity of kernel as a design philosophy obliges to implement only minimal set of functions and only those which are absolutely necessary. There's only one global critical section which disables context switching. There are no functions to suspend and resume tasks (their appearance in user code tells that something wrong in software design). Only one type of PSO, namely queue, is used for communications between tasks.

However, sticking to minimalistic design leads to inflexibility. Therefore in addition to minimalistic design a list-based design has been implemented. The user can choose either. The differences and features will be explained later. Generally, list-based design increases the size of variable part of task structure (on MSP430 it becomes 12 bytes) but allows several waiting tasks on each side of PSO, the priority inversion problem is handled (the user's choice) and other types of PSO may be implemented.

A task is a function like this:

void task()
{
    for(;;)
    {
        /* do something */
    }
}

The function should never return.

Tasks are defined in the following steps:

The order of first two steps does not matters. TCBs may be defined before task functions and the order of definitions also does not matters.

Task control blocks are defined with the TCB macro. This macro accepts two parameters: the name of task and the size of stack. Note that the name of task is not a name of task function, a different one should be choosen. The size of stack is the number of values of void* data type (for proper alignment). For example, define four task control blocks:

TCB( task_1, 48 );
TCB( task_2, 64 );
TCB( task_3, 32 );
TCB( task_4, 80 );

Now suppose we defined functions task_1_func, task_2_func, task_3_func and task_4_func. It's time to perform the third step. Tasks are grouped together with the TASK_GROUP macro. It accepts one parameter, the name of the group. The macro actually defines an array of structures and items should be initialized with the TASK macro. This macro accepts three parameters: priority, the name of task and the name of task function. In the following example we define two levels of priority:

TASK_GROUP( idle_priority_tasks ) {
    TASK( 0, task_1, task_1_func ),
    TASK( 0, task_2, task_2_func )
};
TASK_GROUP( normal_priority_tasks ) {
    TASK( 1, task_3, task_3_func ),
    TASK( 1, task_4, task_4_func )
};

The order of groups does not matter but it is less error-prone when they are defined sequentially starting with lowest priority which should be 0. Priority value should be increased sequentially without gaps.

Each level of priority requires additional entry in the internal table task_lists. The entry is a pointer to the running or ready task of the corresponding priority.

The last step is performed with the help of three macros: TASKS_BEGIN, TASKS_ITEM and TASKS_END. Look at the example:

TASKS_BEGIN
    TASKS_ITEM( idle_priority_tasks ),
    TASKS_ITEM( normal_priority_tasks )
TASKS_END;

Groups of tasks should be defined exactly sequentially starting from the lowest priority.

That's all. The scheduler is ready to run.

A task may be in the one of the following states: idle, ready and running. The state of a task is defined explicitly: running task is pointed to by the current_task, idle tasks are referenced by PSO, linked into the delayed list or just abandoned if delayed infinitely.

The scheduler is started by the rtos_main function. This function performs initialization of stacks, task control blocks and internal variables, such as current_task pointer. The first task that is gained control is the task with highest priority.

Tasks of the same priority are switched by the round-robin policy with one exception: when a task is resumed by the event related with PSO it is gained control out of the order.

When all tasks of high priority become idle the scheduler proceeds with tasks of lower priority and so on. There's a special lowest priority task in most operating systems which never becomes idle but there's no such task in this kernel. The presence of such task simplifies the design but it requires a relatively large amount of RAM for its context. In this kernel when all tasks are idle current_task is NULL so it should be checked in the hardware-specific functions or macros save_context and restore_context. When there's no task to run MCU may be put into the sleep state or enter infinite loop.

The scheduler requires that a function tick_handler should be invoked from some timer interrupt service routine. All timings are measured in the number of ticks, not in real units. The calculations between seconds and number of ticks are leaved to the user.

Tasks that are delayed for the specified amount of time are linked into singly-linked list (field next_delayed_task in TCB). Tick handler walks through this list and decrements remaining tick count (field wait_countdown in TCB). When it becomes zero the task is removed from the list. In list-based design it is also moved to the end of ready list of corresponding priority.

Preemptive task switching is performed with the help of switch_context function. It must be called within some timer interrupt service routine. Here is an example of ISR function body:

save_context();
switch_context();
restore_context();

The function should be “naked”. If a C compiler is used, it should not contain generated prologue and epilogue. Using GCC it is possible to achieve this with naked attribute (however, this works not for all architectures but workarounds are possible, see test framework for example).

Usually, switch_context is called from the same routine after tick_handler. But in this case the following should be considered: if the tick handler changes state of some task to “ready” and there were no ready task, it assigns a value to current_task and returns TRUE. This means that context should be restored immediately and switch_context should not be called. An example:

save_context();
if( !tick_handler() )
    switch_context();
restore_context();

Queue is a ring buffer. Definition is simple. For example, define queue for two items each of 4 bytes:

QUEUE( sample_queue, 2, 4 );

The product of item size and queue capacity should fit into unsigned char data type.

In the minimalistic implementation only one task may be waiting at one side of queue. In the list-based implementation the number of waiting tasks is unlimited.

The user should provide femtoRTOSconfig.h file. It should contain the following essential definitions:

The user should select port type with the following macros:

If the runtime or debugging environment allows output of debug/trace messages it is possible to provide custom definitions of TRACE, TRACE_SWITCH_CONTEXT and ASSERT. Look into include/ports/femtoRTOStest.h for examples.

FIXME: describe

int tick_handler()
void switch_context()
void enter_critical_section()
void leave_critical_section()
void yield()
void sleep( tick_t timeout )

void rtos_main()

int queue_push( const struct queue* queue, void* buffer, tick_t timeout )
enum pso_result queue_push_from_isr( const struct queue* queue, void* buffer )
int queue_pop( const struct queue* queue, void* buffer, tick_t timeout )
enum pso_result queue_pop_from_isr( const struct queue* queue, void* buffer )

The following functions should be implemented or defined as macros: FIXME: describe

void enable_interrupts()
void disable_interrupts()
void enter_critical_section()
void yield()
void restore_context()
void save_context() (not used in kernel code)
void* init_stack( char* stack, int stack_size, void (*task_function)() )

Actually, save_context and restore_context should replace prologue and epilogue of interrupt service routine. restore_context should end up with “return from ISR” instruction and interrupts should be enabled after it.

save_context pseudocode:

    if( current_task )
    {
        /* save context */
        push reg1;
        push reg2;
        /* ... */
        push regN;
        current_context->saved_top_of_stack = regSP;
    }
    else
    {
        /* rewind stack: remove return address and flags */
        pop temp
        pop temp
    }

restore_context pseudocode:

    if( current_task )
    {
        /* restore context */
        regSP = current_context->saved_top_of_stack;
        pop regN;
        /* ... */
        pop reg2;
        pop reg1;
    }
    else
    {
        enable_interrupts();
        for(;;);
        /* or halt CPU/enter sleep state */
    }

yield function:

    disable_interrupts();
    save_context();
    switch_context();
    restore_context();

Copyright (c) 2006, Alexander Yaworsky

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.