Reliable task scheduling with Arduino / AVR

** EDIT 27/04/2016: This article is now for background information only. I have now created a ‘user-friendly’ library compatible with the Arduino IDE **

There comes a point, when writing embedded software, where you need to time the execution of tasks more precisely than just having a list of functions in a loop. In order to make a system as predictable, and therefore reliable, as possible it is desirable to use a time-triggered scheduler. If you are unfamiliar with this concept, I recommend you have a scan of Dr Michael J Pont’s Patterns for Time Triggered Embedded Systems, and watch some of his lectures.

The idea is to use a small-scale operating system that runs on a microcontroller, using timer interrupts to execute tasks with microsecond precision. This isn’t a new idea; the aerospace industry have been using this approach for years to stop their aircrafts from making ‘premature landings’, but it’s rare to find it implementated on hobby-centric platforms such as Arduino. So I thought I’d have a go at writing my own.

There’s a long way to go before this is a fully-fledged Arduino library. It is written in C at the moment for simplicity / reduced overheads. This is fine for my needs, but I appreciate that some people aren’t used to using I may write a C++ library if there’s enough interest though. This was written in Eclipse using Jan Baeyens’ Arduino Eclipse Extensions. I’m using the timer function of the ATMEGA to generate timer interrupts (“ticks”). For an excellent tutorial on how to use the timer, see here.

How it works:

• The program sits in an empty loop when idle.
• “Ticks” are generated by the timer driven interrupt.
• Tasks have a period and an offset:
  • Period – How often the task is executed
  • Offset – The first tick in which the task is executed
• The period and offset of the tasks are adjusted manually to spread the tasks out, ensuring that tasks don’t collide.
• The ISR iterates through each task in the schedule and executes any task that is ready to run.
• Doing this ensures that tasks are executed with precise timing (as precise as the ATMEGA timer allows).

In main.h (along with the rest of the standard Arduino stuff):

Tasks are written as volatile void x_update(void) functions, with prototypes referenced in main.h:

/*
* Task includes
* These header files contain the function prototypes for your tasks
* */
#include "Tasks/ExampleTask1.h"
#include "Tasks/ExampleTask2.h"
#include "Tasks/ExampleTask3.h"

Defining the task structure:

/*
* Function pointer for task array
* This links the Task list with the functions from the includes
* */

typedef volatile void (*task_function_t)(void);

/* Task properties */
typedef struct
{
task_function_t task_function;	/* function pointer */
uint32_t task_period;	/* period in ticks */
uint32_t task_delay;	/* initial offset in ticks */
} task_t;

main.cpp:

/*
* Simple Time Triggered Co-operative Scheduler for Arduino / AVR
* by Chris Barlow
* chrisbarlow.wordpress.com
* chris.barlow2@gmail.com
*
* This is a WORK IN PROGRESS, stripped down implementation of a scheduler.
* More functionality will be added in due course.
*/
#include "main.h"

/*
* Define how often the ticks occur, and the number of tasks in the schedule
*/
#define TICK_PERIOD (2000) 	/* Tick period in microseconds */
#define NUM_TASKS 	(3)		/* Total number of tasks */

/*
* The task array.
* This dictates the tasks to be run from the scheduler
* The order of these tasks sets their priority, should more than one task run in one tick
* */
task_t Tasks[NUM_TASKS] =
{
{
exampleTask1_update,
10,
0
},

{
exampleTask2_update,
2,
1
},

{
exampleTask3_update,
10,
2
}

};

/*
* The familiar Arduino setup() function: runs once when you press reset.
* x_Init() functions contain initialisation code for the related tasks.
*/
void setup()
{
exampleTask1_Init();
exampleTask2_Init();
exampleTask3_Init();

tick_Start();
}

/*
* Start the timer interrupts
*/
void tick_Start()
{
/* initialize Timer1 */
cli(); 			/* disable global interrupts */
TCCR1A = 0; 		/* set entire TCCR1A register to 0 */
TCCR1B = 0; 		/* same for TCCR1B */

/* set compare match register to desired timer count: */
OCR1A = (16 * TICK_PERIOD); /* TICK_PERIOD is in microseconds */

/* turn on CTC mode: */
TCCR1B |= (1 << WGM12);

/* enable timer compare interrupt: */
TIMSK1 |= (1 << OCIE1A);
TCCR1B |= (1 << CS10);

/* enable global interrupts (start the timer)*/
sei();
}

/*
* The ISR runs periodically every TICK_PERIOD
*/
ISR(TIMER1_COMPA_vect)
{
uint16_t i;

for(i = 0; i < NUM_TASKS; i++)					/* For every task in schedule */
{
if(Tasks[i].task_delay > 0)				/* Decrement task_delay */
{
Tasks[i].task_delay--;
}

if(Tasks[i].task_delay == 0)				/* Task is ready when task_delay = 0 */
{
(*Tasks[i].task_function)();			/* Call task function */
Tasks[i].task_delay = Tasks[i].task_period;	/* Reload task_delay */
}

}
}

/* The loop function does nothing as all tasks are time triggered */
void loop()
{
/*
* Do nothing (actually, do EVERYTHING)
*/
}

That’s all there is to it. Some things to bear in mind, though:

• At the moment, the micro will freeze if the tasks overrun a tick. Some trial and error is required to find a suitable tick period to avoid this.
• while loops should be avoided where possible. If they are used, a timeout mechanism is required to prevent the program getting stuck.
• Avoid long for loops: use counters and if(x == y) statements in tasks if you have lots of repeating code.
• Some things will take longer than 1 tick to execute, for example, writing to an LCD screen. This can be overcome by buffering characters and writing fewer characters at once. I plan on covering this in a future post.

I’ve successfully used this method in a system with 6 tasks, which were performing different communications-based actions. 2 ms ticks. 5 tasks had a period of 20 ms (10 ticks), and 1 task (an LCD screen update task) had a period of 4 ms (2 ticks), executing in between the other tasks. Obviously, increasing the period means you can fit more tasks in, and the ticks can be shorter if the tasks are less time-intensive.

Future improvements:

• Put the processor to sleep and move the dispatch functionality to the main loop – putting the processor to sleep will save power, and ensure the processor is in a known state. The ISR will wake the processor up, running the dispatcher once before the processor goes back to sleep.
• Allow tasks to last longer than 1 tick.
• Introduce more functionality, such as the ability to add and remove tasks during runtime.
• Explore using different interrupts to drive the tick – for future expansion to multiprocessor systems.