AVR Scheduler

First steps in Multi Tasking

AVR Scheduler

What is a Scheduler?

Implementation

The Code, Explained

Closing Thoughts


Back to Main

My final year project will be an implementation of a Real Time Operating System (RTOS) for the AVR microcontrollers. Although many have said it isn't wise to write yet another OS (apparently, there are enough of these around), I decided it is the best way to learn, since the source of other OSes weren't as easy to understand as I had expected.To start off, I began with the Scheduler.

What is a Scheduler?

A scheduler is a piece of code that calls functions (usually refered to as "Tasks") at periodic intervals of time. Schedulers form one of the basic components of an RTOS. A scheduler can be as simple as an array of function pointers, with the array index being incremented every few milliseconds to a more advanced version using data structures like Task Control Blocks. There are many algorithms that decide when a task is supposed to run. One such algorithm is the Round Robbin Scheduler Algorithm, which gives each task equal amount of time to execute. Round Robbin algorithms are easy to implement and donot implement priorites, so there is no starvation. All tasks get ample time to execute.

For example, let the maximum time for each task to execute be 100ms. The Round Robbin scheduler thus calls each task in intervals of 100ms. This is assuming that each task complies with the timing and completes within 100ms.

The following scheduler is based on an Atmel Application Journal, which unfortunately, seems to be missing some pages.

Implementation

Code Listing: scheduler.c

/**
AVR Round Robbin Scheduler
Hardware: ATMega8 running at 8MHz
*/

#include<avr/interrupt.h>
#include<inttypes.h>

#define MAX_TASKS (10)

// task states
#define RUNNABLE (0x00)
#define RUNNING  (0x01)
#define STOPPED  (0x02)
#define ERROR    (0x03)


// a task "type"
// pointer to a void function with no arguments
typedef void (*task_t)(void);

// basic task control block (TCB)
typedef struct __tcb_t
{
    uint8_t id; // task ID
    task_t task; // pointer to the task
    // delay before execution
    uint16_t delay, period;
    uint8_t status; // status of task
} tcb_t;


// scheduler functions
void initScheduler(void);
void addTask(uint8_t, task_t, uint16_t);
void deleteTask(uint8_t);
uint8_t getTaskStatus(uint8_t);
void dispatchTasks(void);

// prototypes of tasks
void Task1(void);
void Task2(void);

// the task list
tcb_t task_list[MAX_TASKS];

// keeps track of number of timer interrupts
uint16_t count = 0;

// scheduler function definitions

// initialises the task list
void initScheduler(void)
{
    for(uint8_t i=0; i<MAX_TASKS; i++)
    {
        task_list[i].id = 0;
        task_list[i].task = (task_t)0x00;
        task_list[i].delay = 0;
        task_list[i].period = 0;
        task_list[i].status = STOPPED;
    }
}

// adds a new task to the task list
// scans through the list and
// places the new task data where
// it finds free space
void addTask(uint8_t id, task_t task,
             uint16_t period)
{
    uint8_t idx = 0, done = 0x00;   
    while( idx < MAX_TASKS )
    {
        if( task_list[idx].status == STOPPED )
        {
            task_list[idx].id = id;
            task_list[idx].task = task;
            task_list[idx].delay = period;
            task_list[idx].period = period;
            task_list[idx].status = RUNNABLE;           
            done = 0x01;
        }
        if( done ) break;
        idx++;
    }

}

// remove task from task list
// note STOPPED is equivalent
// to removing a task
void deleteTask(uint8_t id)
{   
    for(uint8_t i=0;i<MAX_TASKS;i++)
    {
        if( task_list[i].id == id )
        {
            task_list[i].status = STOPPED;
            break;
        }
    }
}

// gets the task status
// returns ERROR if id is invalid
uint8_t getTaskStatus(uint8_t id)
{
    for(uint8_t i=0;i<MAX_TASKS;i++)
    {
        if( task_list[i].id == id )
            return task_list[i].status;
    }
    return ERROR;
}

// dispatches tasks when they are ready to run
void dispatchTasks(void)
{
    for(uint8_t i=0;i<MAX_TASKS;i++)
    {
        // check for a valid task ready to run
        if( !task_list[i].delay &&
             task_list[i].status == RUNNABLE )
        {
            // task is now running
            task_list[i].status = RUNNING;           
            // call the task
            (*task_list[i].task)();

            // reset the delay
            task_list[i].delay =
                task_list[i].period;
            // task is runnable again
            task_list[i].status = RUNNABLE;
        }
    }   
}   

// generates a "tick"
// each tick 100ms apart
ISR(TIMER0_OVF_vect)
{
    count ++;
    if( count == 392 )
    {
        count = 0;
        // cycle through available tasks
        for(uint8_t i=0;i<MAX_TASKS;i++)
        {               
            if( task_list[i].status == RUNNABLE )
                task_list[i].delay--;
        }
    }
}

// Task definitions

void Task1(void)
{
    static uint8_t status = 0x01;
    if( status )
        PORTD |= _BV(PD0);
    else
        PORTD &= ~_BV(PD0);
    status = !status;
}


void Task2(void)
{
    static uint8_t status = 0x01;
    if( status )
        PORTD |= _BV(PD1);
    else
        PORTD &= ~_BV(PD1);
    status = !status;
}

int main(void)
{
    // use 1/8 of system clock frequency
    TCCR0 = 0x02;
    // inital timer value = 0
    TCNT0 = 0;   
    // enable Timer0 Overflow interrupt
    TIMSK = _BV(TOIE0);
    // set PORTD bit0 and bit1 as outputs
    DDRD = _BV(PD0)|_BV(PD1); 

    // set up the task list
    initScheduler();

    // add tasks, id is arbitrary
    // task1 runs every 1 second
    addTask(1, Task1, 10);

    // task2 runs every 4 seconds
    addTask(2, Task2, 40);   

    // enable all interrupts
    sei();   
    for(;;)
        dispatchTasks();
    return 0; // will never reach here
}

The Code, Explained

A Task Control Block is how a RTOS "sees" a task. It is a manifestation of a task in an RTOS. A Task can be defined as a small independant piece of code that accomplishes something. Tasks are represented as functions, in this case, as a void function taking no arguments.

A simple TCB is used here, consisting of 5 fields: the task id, task address, time after which the task should run (delay and period) and the task's current status. A TCB array task_list stores information about each task that is defined. 

A task is STOPPED if it is no longer going to run. This qualifies its removal from the task list. The addTask function goes through the list and replaces the first occurance of a STOPPED task with a new task. A task is RUNNABLE if it is ready to run, but is waiting for its time slot. A task is RUNNING if it is currently executing. 

Adding a task means task_list is scanned and the new task is added where a STOPPED task is present, overwriting the old task. The task is now set to RUNNABLE. Deleting a task simply marks the task's status as STOPPED. It will no longer be executed, and if a new task is added, may be overwritten. getTaskStatus gets the status of a task with a given id. 

dispatchTasks loops through the entire task list, and checks if a valid task is ready to run. A valid ready-to-run task is defined as a task whose delay has become 0 and is currently RUNNABLE.  If so, the task's status is changed to RUNNING, and the corresponding function is called. After the function returns, the task's delay is reset (using the period attribute) and is marked as RUNNABLE.

The Timer0 Overflow Interrupt is used to provide a tick. Everytime a tick occurs, the delay attribute of each task is decremented. Simply put, ticks measure the time in a convinient way. All OS time is subsequently measured in ticks. In this case, a tick is generated every 100ms. The Timer0 Overflow Interrupt occurs every 255us, since the input frequency to the time is F_CPU/8, which is 1MHz since F_CPU is 8MHz. The counter value increases every 1us, and overflows at a count of 255. When this happens, count is incremented. Since an increment in count  represents an interval of 255us, there must be 392 such increments for 100ms to elapse. (392 * 255us = 100ms, approx.)

Task1 and Task2 toggle the states of PortD bit0 and bit1. Task1 is set to run every 10 ticks, which is 10*100ms = 1s. Task2 is set to run every 40 ticks. An LED is connected to each of PortD bit0 and bit1.

Once the required registers are set, and interrupts enabled, dispatchTasks will take care of everything, in conjunction with the Timer Overflow Interrupt.

Closing Thoughts

While this is a fairly complex implementation, it does have a few drawbacks. Firstly, a task id is arbitrary, and no check is made to see if there are two tasks with the same id. Hence getTaskStatus will return the first task that matches the task id. Secondly, each task is expected to finish its work within a tick interval, that is, within 100ms. If a task takes more than that, the timing of the entire system is affected. There are no problems with a task finishing within the tick interval. Finally, disabling interrupts means the entire system is brought to a halt. Without the timer interrupt, no task gets to run.