[blog] A Time-Triggered Cooperative Scheduler Pattern

On a bare-metal system, if we have multiple periodic tasks to run we can choose to dedicate one hardware Timer to each. We may not have enough timers though. Another approach is to share a single Timer between multiple tasks by the means of a Scheduler [1].

Instead of triggering a specific task on a specific time interval, this timer will be responsible for generating a system tick. The scheduler keeps track of these ticks for each task, dispatching a task when it is due.

/*
@file sch.h
@brief Scheduler interface
*/
#ifndef SCH_H_
#define SCH_H_
#include <stdint-gcc.h>
#define NTASK 4 /*max number of tasks*/
/*task data structure */
typedef struct  
{
	void		(*pTask)(void); /*task signature is void Task(void)*/
	uint32_t	delay; /*initial delay*/
	uint32_t	period; /*period*/
	uint8_t		run;	 /*run flag*/
} Task_t;

/*
\brief Execute a pending task, if any
*/
void SCH_Dispatch(void);

/*
\brief Update each task deadline at each time tick.
*/
void SCH_Update(void);

/*
\brief  Add a task to the task pool. 
\param task    Function pointer to the task.
\param delay   Initial delay (tick numbers)
\param period  Task period (tick numbers)
*/
char SCH_Add(void (*task)(void), const uint32_t delay, const uint32_t period);

/*
\brief   Delete a task from the task pool.
\param task_index  Index of the task on the task array
*/
char SCH_Del(const int task_index);

/*
\brief Initialize the System Tick. Is hardware-dependent.
*/
void SCH_TickInit(void);
#endif /* SCH_H_ */

Below, the scheduler implementation. Note that while there is no task to run the CPU goes to sleep.

/*
@file sch.c
@brief Scheduler implementation
*/
#include "sch.h"
#include <atmel_start.h>
/*pool of tasks*/
static Task_t TaskPool[NTASK] = {0};

/*forward declarations*/
static void SCH_LowPowerOn(void);
static void SCH_LowPowerOff(void);	

void SCH_Dispatch(void)
{
	int index;
	for (index = 0; index < NTASK; index++)
	{
		if (TaskPool[index].run > 0) /*task is pending to run*/
		{
			SCH_LowPowerOff(); /*wake-up CPU*/
			TaskPool[index].pTask(); /*run it*/
			TaskPool[index].run -= 1;
			if (TaskPool[index].period == 0) /*if one-shot*/
			{
				SCH_Del(index);
			}
		}
	}
	SCH_LowPowerOn(); /*enable low-power*/
}

void SCH_Update(void)
{
	int index;
	for (index = 0; index < NTASK; index++)
	{
		/*there is a task?*/
		if (TaskPool[index].pTask)
		{
			if (TaskPool[index].delay == 0) /*ready to run?*/
			{
				TaskPool[index].run += 1;
				if (TaskPool[index].period)
				{
					/*schedule to run again*/
					TaskPool[index].delay = TaskPool[index].period;
				}
			}
			else /*decrement delay*/
			{
				TaskPool[index].delay -= 1;
			}
		}
	}
}

char SCH_Add(void (*task)(void), const uint32_t delay, const uint32_t period)
{
	int index=0;
	/*find a slot*/
	while ((TaskPool[index].pTask != 0) && (index < NTASK))
	{
		index++;
	}
	if (index == NTASK) /*array is full*/
	{
		return -1;
	}
	TaskPool[index].pTask = task;
	TaskPool[index].delay = delay;
	TaskPool[index].period = period;
	return index;
}

char SCH_Del(const int task_index)
{
	if (TaskPool[task_index].pTask == 0) return -1; //no task
	TaskPool[task_index].pTask = 0;
	TaskPool[task_index].delay = 0;
	TaskPool[task_index].period = 0;
	TaskPool[task_index].run	= 0;
	return task_index;
}

/*
 Hardware-dependent code. 
 Written for an Atmel Atmega328p MCU.
****/

/* 
 Generate a 4ms system tick for a 16MHz clock
*/
void SCH_TickInit(void)
{
	TCCR0A |= (1 << WGM01); 
	OCR0A = 0xF9;  
	TIMSK0 |= (1 << OCIE0A);
	TCCR0B |= (1 << CS02);
}

/*
 Put CPU on IDLE 
*/
static void SCH_LowPowerOn(void)
{
	cli();
	set_sleep_mode(SLEEP_MODE_IDLE);
	sleep_enable();
	sei();
	sleep_cpu();
}

/*
 Wake up CPU
*/
static void SCH_LowPowerOff(void)
{
	sleep_disable();
}

A simple main program using this scheduler:

#include <atmel_start.h>
#include <assert.h>
#include "sch.h"
#include "usart.h"
/*
 Tasks
*/
void Task1(void)
{
	usart_send_string("Task1\n\r");
}

void Task2(void)
{
	usart_send_string("Task2\n\r");
}

void Task3(void)
{
	usart_send_string("Task3\n\r");
}

void Task4(void)
{
	usart_send_string("Task4\n\r");
}

/*
 ISR for system tick
*/
ISR(TIMER0_COMPA_vect)
{
	SCH_Update();
}

int main(void)
{
	usart_init();
    /*add tasks*/
	assert(SCH_Add(Task1, 0, 1250) != -1); /*schedule to run every 5s*/
	assert(SCH_Add(Task2, 0, 1750) != -1); /*every 7s*/
	assert(SCH_Add(Task3, 0, 2750) != -1); /*every 11s */
	assert(SCH_Add(Task4, 2000, 0) != -1); /*one-shot, 8 sec delay */
	usart_send_string("Sys started\n\r");
   /*start system tick */
	SCH_TickInit();
   /*enable interupts*/
	sei(); 
	while (1)
	{
		SCH_Dispatch();
	}
}

Below, the tasks running. Time-stamps are printed by the terminal to validate tasks periodicity.