Pete Vidler

Software development and technology in general

Simple Co-Operative Scheduling

RTOS Alternatives

This is the second post in the RTOS Alternatives series.

Last time, I looked at some of the simplest alternatives to using a Real-Time Operating System. The problem is, as soon as you need both accurate timing and prioritised tasks, you are out of luck – a foreground/background system would need a separate interrupt source per task priority, which can bring its own problems to the table:

Graph of predictability and functionality against number of interrupt sources

In order to meet our requirements and avoid these issues, we really need a scheduler… luckily, they aren’t too hard to write. The simplest of all schedulers is the Time-Triggered Co-operative (TTC) scheduler, in which tasks are released by a single timer interrupt (hitting the green ‘sweet spot’ on the above graph). This differs from foreground/background scheduling in that tasks are actually executed from the main function and not from the interrupt handler itself.

Time-Triggered Systems

Before delving into the scheduler implementation, it’s probably worth taking a short detour through time-triggered systems. If you’re not familiar with them, they are a subset of the more widely used event-driven programming technique. The difference is that the only ‘events’ we are allowed to use are those whose timing is known in advance. This typically means just having one timer interrupt as the event source — which, as some will already have guessed — often leads to a technique known as polling.

Polling has a poor reputation in most software development circles, and for good reason. As soon as you start polling on more than a few frequent (but aperiodic) events, the time taken to continually check for the event can be costly in terms of processor utilisation. Then there’s the problem of long tasks, which — in a co-operatively scheduled system — can delay polling activities and potentially cause events to be missed.

Despite these issues, the idea of knowing exactly what your system is doing at any given instant is very compelling. So, in this article we will look at building a co-operative scheduler and in future articles we will look at ways of coping with the shortcomings of this approach. Perhaps in time I might even get as far as writing about pre-emptive schedulers!

The Anatomy of a Task

For systems written in C, a task is usually represented as a function. The average RTOS will not allow the task function to return, instead forcing us to wrap the code in an infinite loop. Having the task perform operations periodically – as in a time-triggered system – is done by calling blocking functions provided by the RTOS, similar to the following:

Typical RTOS Task Usage
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Called in the main function:
Create_Task(RTOS_Task, // Task function.
            512,       // Bytes of stack to allocate.
            NULL);     // No parameters to pass.

// Never called directly, runs only through context switching.
void RTOS_Task(void *parameters)
{
    // Tasks may never return!
    while (1) {
        Do_Something();
        Delay(5);
    }
}

Notice how similar this is to the super loop example from last time? It suffers from many of the same problems too, but we won’t get into that now. Instead, let’s look at a roughly equivalent task for a Time-Triggered, Co-operative (TTC) scheduler:

Typical TTC Scheduled Task Usage
1
2
3
4
5
6
7
8
9
10
// Called in the main function:
Create_Task(Scheduled_Task, // Task function.
            5,              // Task period, in ticks.
            0);             // Delay before first run, in ticks.

// Called directly and periodically by the scheduler.
void Scheduled_Task(void)
{
    Do_Something();
}

Notice that the function is allowed to return, and that we specify a period and delay for the task. The scheduler will be responsible for calling the task function at the appropriate times – we do not control this inside the task itself. Note also that the task function is called directly without context switching, and so does not require a stack of its own.

The scheduler implementation will need a data structure to store this information; to keep things simple, we can use the following:

Data Structure for Task Information
1
2
3
4
5
typedef struct {
    void   (*task)(void); // Pointer to the task function.
    uint32_t period;      // Period to execute with.
    uint32_t delay;       // Delay before first call.
} task_type;

The above structure is effectively minimal for a time-triggered scheduler, containing just the function pointer and timing data needed to call the task at the appropriate times. Note that the implementation is easiest if the period and delay are in units of ‘ticks’, which correspond to a (single) periodically repeating timer interrupt.

Implementing a Simple Scheduler

Time is obviously going to be the most important factor in a time-triggered system. To build the scheduler, we will need – as a minimum – the ability to configure a hardware timer such that it generates an interrupt at the desired frequency. This is platform dependent and I will not go into detail here – see the datasheet or user manuals for your architecture for more information.

In the terminology introduced last time, all tasks in our co-operative scheduler are going to be ‘background’ tasks. In other words, the interrupt handler is not responsible for actually running tasks; instead it will just keep track of time for us:

Trivial Timer Interrupt Routine for a TTC Scheduler
1
2
3
4
5
6
7
// Count the number of ticks yet to be processed.
volatile uint32_t elapsed_ticks = 0;

void Timer_ISR(void)
{
    ++elapsed_ticks;
}

It’s that simple – all the real work will be done outside of the ISR, in a dispatcher that can be called over and over again from the main function. All we really need to do is wait until the elapsed_ticks variable is greater than zero, then decrement the delay of every task and execute any that reach zero. The task’s delay variable can then be reloaded with the period.

Note that the elapsed_ticks variable must be made volatile, as it is accessed both inside and outside of an ISR. This is not to ensure atomic access – which is good, because it doesn’t – but instead prevents some potentially harmful compiler optimisations (however unlikely). We must take further steps to ensure atomic access, and in this case I have opted for a heavy handed application of disabled interrupts:

Task Dispatcher for a TTC Scheduler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
task_type tasks[NUM_TASKS];

void Dispatch_Tasks(void)
{
    Disable_Interrupts();
    while (elapsed_ticks > 0) { // TRUE only if the ISR ran.
        for (uint32_t i = 0; i < NUM_TASKS; i++) {
            if (--tasks[i].delay == 0) {
                tasks[i].delay = tasks[i].period;

                Enable_Interrupts();
                tasks[i].task(); // Execute the task!
                Disable_Interrupts();
            }
        }
        --elapsed_ticks;
    }
    Enable_Interrupts();
}

Reading the above code, you might notice that the first call to the dispatcher will (probably) jump past the outer loop and exit almost immediately. This is not a disaster – if the function is called repeatedly as intended then it will still operate correctly – but it is not ideal.

Initialisation and Usage

We can improve efficiency by making use of the microcontroller’s idle mode:

Task Creation for a TTC Scheduler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main(void)
{
    Initialise_Timer( /* ... */ );

    // Note the tasks from the last post.
    Create_Task(Task_1, 10, 0);
    Create_Task(Task_2, 10, 5);

    Start_Timer();

    while (1) {
        // Sleep until the next interrupt.
        Enter_Idle_Mode();
        Dispatch_Tasks();
    }
}

Line 13 effectively puts the microcontroller to sleep until the next interrupt occurs; once again, this function is highly architecture-dependent and you will have to write it yourself. The trouble with using idle mode is what happens when an interrupt occurs immediately before this line is reached – the elapsed_ticks variable will still be incremented, but the dispatcher will not run until the following tick (i.e. one tick will be ‘missed’).

We can assume that the timer interrupt will not fire between lines 9 and 13 above, but there is still the possibility of this happening between the end of Dispatch_Tasks and entering idle mode. Actually, there is another problem with this code – the dispatcher decrements the delay before testing it and we are setting the initial delay to zero, so how do we avoid underflow (or subtraction overflow if you prefer)?

Creating a TTC Task
1
2
3
4
5
6
7
8
9
10
11
12
void Create_Task(void (*function_pointer)(void),
                 uint32_t period,
                 uint32_t delay) {
    static uint32_t index = 0;
    assert(index < NUM_TASKS);

    tasks[index].task = function_pointer;
    tasks[index].period = period;
    // Avoid underflow in the dispatcher.
    tasks[index].delay = delay + 1;
    ++index;
}

That’s it for the implementation… let’s take a look at how it works with the two-task example from last time:

Timing of the scheduler example

So, we now have access to priorities – based on the order of the task array – as well as a simple way of getting accurate timing. Next time, we’ll look at some of the problems inherent in both co-operative and time-triggered schedulers and some ways of working around them.

Comments