Lab Guide: Time-Triggered Scheduling

In this class we are interested in executing code asynchronously and at pre-determined rates.  Students can accomplish this without resorting to a complicated, full-blown scheduler or a real-time operating system by using a technique called time-triggered scheduling (TTS).  The implementation described below was inspired by an algorithm given in Michael J. Pont’s book Patterns for Time-Triggered Embedded Systems, which is available as a free download.

Here’s the paragraph where I try to justify using TTS.  Asynchronous execution is desirable when tasks on external modules take a long time to run.  For example, a stepper motor control program performs a single step of the motor every 10 or so ms.  The Arduino Stepper library is synchronous so it ties up the processor until all the requested steps are finished, even though it spends less than 0.1% of that time executing useful instructions.  If TTS is used to schedule a step every 10 ms, other tasks can run while the motor module is waiting to do the next step.  Running tasks at pre-determined rates is also desirable in some situations, like when reading sensors.  For example, when querying an ultrasonic range sensor the program needs to wait an extra 50 to 100 ms after the reading is returned to allow echoes to settle.  A reading can’t be implicitly triggered by the end of the previous reading, the program needs to know something about elapsed time in order to initiate range measurements. With TTS you can schedule tasks at any interval your design demands.

The scheduler has a three-function interface that allows the designer to define several tasks (in the form of callback functions) and to indicate approximately when they should run.  Tasks are scheduled according to a delay and a period, the former determining how long after system startup the task runs for the first time and the latter determining at what rate thereafter the task repeats.  For example, a task with a delay of 500 ms and a period of 10 ms will run for the first time at t=500, then again at t=510, 520, 530, etc. Tasks can be run at different rates according to their domains: for example one task steps a stepper motor every 10 ms, another task steps its motor every 12 ms, another task takes a sonar reading every 100 ms, and another task sends a status update over the radio every 1000 ms.

N.b. these aren’t real tasks as provided by a real-time operating system.  They don’t have separate stack spaces, they are not pre-emptible (except by interrupts), and run-times are neither guaranteed nor enforced.  You can think of it like a periodic co-operative multitasking system with no operating system to provide oversight and error handling.  As such, tasks should not have internal delays; rather task functions should return as soon as possible to give other tasks the chance to run. Friendly delays inside a task can be accomplished by counting how many times the task has run.  For example, to implement a variable delay of N milliseconds between stepper motor steps, have the stepper motor task run every 1 millisecond and execute the step code after the task runs N times. That way you can effectively inject an N ms delay into the stepper code and allow other tasks to run while the stepper is waiting.

What the TTS loses in design robustness and flexibility compared to an RTOS it gains in simplicity.  This is the header for the scheduler:

/*
 * scheduler.h
 *
 *  Created on: 17-Feb-2011
 *      Author: nrqm
 */
 
#ifndef SCHEDULER_H_
#define SCHEDULER_H_
 
#include <avr/io.h>
 
///Up to this many tasks can be run, in addition to the idle task
#define MAXTASKS	8
 
///A task callback function
typedef void (*task_cb)();
 
/**
 * Initialise the scheduler.  This should be called once in the setup routine.
 */
void Scheduler_Init();
 
/**
 * Start a task.
 * The function "task" will be called roughly every "period" milliseconds starting after "delay" milliseconds.
 * The scheduler does not guarantee that the task will run as soon as it can.  Tasks are executed until completion.
 * If a task misses its scheduled execution time then it simply executes as soon as possible.  Don't pass stupid
 * values (e.g. negatives) to the parameters.
 *
 * \param id The tasks ID number.  This must be between 0 and MAXTASKS (it is used as an array index).
 * \param delay The task will start after this many milliseconds.
 * \param period The task will repeat every "period" milliseconds.
 * \param task The callback function that the scheduler is to call.
 */
void Scheduler_StartTask(int16_t delay, int16_t period, task_cb task);
 
/**
 * Go through the task list and run any tasks that need to be run.  The main function should simply be this
 * function called as often as possible, plus any low-priority code that you want to run sporadically.
 */
uint32_t Scheduler_Dispatch();
 
#endif /* SCHEDULER_H_ */

The init function is called once at system startup, tasks are defined once during the program setup using Scheduler_StartTask, and the dispatch function is called as often as possible in the main loop.  The tasks are prioritized according to when the start task function was called for that task: if two tasks are scheduled to run at the same time, the task that was started first is given priority.  The scheduler is implemented for Arduino as follows:

/*
 * scheduler.cpp
 *
 *  Created on: 17-Feb-2011
 *      Author: nrqm
 *      Based on code by Jacob Schwartz
 */
#include "scheduler.h"
 
#include "arduino/Arduino.h"
#include <avr/interrupt.h>
 
typedef struct
{
	int32_t period;
	int32_t remaining_time;
	uint8_t is_running;
	task_cb callback;
} task_t;
 
task_t tasks[MAXTASKS];
 
uint32_t last_runtime;
 
void Scheduler_Init()
{
	last_runtime = millis();
}
 
void Scheduler_StartTask(int16_t delay, int16_t period, task_cb task)
{
	static uint8_t id = 0;
	if (id < MAXTASKS)
	{
		tasks[id].remaining_time = delay;
		tasks[id].period = period;
		tasks[id].is_running = 1;
		tasks[id].callback = task;
		id++;
	}
}
 
uint32_t Scheduler_Dispatch()
{
	uint8_t i;
 
	uint32_t now = millis();
	uint32_t elapsed = now - last_runtime;
	last_runtime = now;
	task_cb t = NULL;
	uint32_t idle_time = 0xFFFFFFFF;
 
	// update each task's remaining time, and identify the first ready task (if there is one).
	for (i = 0; i < MAXTASKS; i++)
	{
		if (tasks[i].is_running)
		{
			// update the task's remaining time
			tasks[i].remaining_time -= elapsed;
			if (tasks[i].remaining_time <= 0)
			{
				if (t == NULL)
				{
					// if this task is ready to run, and we haven't already selected a task to run,
					// select this one.
					t = tasks[i].callback;
					tasks[i].remaining_time += tasks[i].period;
				}
				idle_time = 0;
			}
			else
			{
				idle_time = min((uint32_t)tasks[i].remaining_time, idle_time);
			}
		}
	}
	if (t != NULL)
	{
		// If a task was selected to run, call its function.
		t();
	}
	return idle_time;
}

This code is mostly sugar. It’s super-easy to implement time-triggered scheduling just by counting milliseconds in the main loop of your program and calling your functions after the appropriate number of milliseconds have elapsed since the last call.  On the other hand it’s useful to structure the scheduler in a centralized way, because that omniscient view allows the application to identify when it doesn’t have a task to run.  The dispatcher function above returns how much time the CPU is expected to spend waiting for the next task to run, which gives the application the opportunity to fill that idle time by running sporadic or low-latency timing-invariant tasks, e.g. processing UART.  In an energy-efficient system the CPU could be put to sleep during this time.  Here’s an example program that illustrates using the TTS module with an idle task that just delays:

/*
 * main.cpp
 *
 *  Created on: 18-Feb-2011
 *      Author: nrqm
 *
 * Example program for time-triggered scheduling on Arduino.
 *
 * This program pulses one pin every 500 ms and another pin every 300 ms
 *
 * There are two important parts in this file:
 * 		- at the end of the setup function I call Scheduler_Init and Scheduler_StartTask.  The latter is called once for
 * 		  each task to be started (note that technically they're not really tasks because they share the stack and don't
 * 		  have separate contexts, but I call them tasks anyway because whatever).
 * 		- in the loop function, I call the scheduler dispatch function, which checks to see if a task needs to run.  If
 * 		  there is a task to run, then it its callback function defined in the StartTask function is called.  Otherwise,
 * 		  the dispatch function returns the amount of time (in ms) before the next task will need to run.  The idle task
 * 		  can then do something useful during that idle period (in this case, it just hangs).
 *
 * To use the scheduler, you just need to define some task functions and call Scheduler_StartTask in the setup routine
 * for each of them.  Keep the loop function below the same.  The scheduler will call the tasks you've created, in
 * accordance with the creation parameters.
 *
 * See scheduler.h for more documentation on the scheduler functions.  It's worth your time to look over scheduler.cpp
 * too, it's not difficult to understand what's going on here.
 */
 
#include "arduino/Arduino.h"
#include "scheduler.h"
 
uint8_t pulse1_pin = 3;
uint8_t pulse2_pin = 4;
uint8_t idle_pin = 7;
 
// task function for PulsePin task
void pulse_pin1_task()
{
	digitalWrite(pulse1_pin, HIGH);
 
	digitalWrite(pulse1_pin, LOW);
}
 
// task function for PulsePin task
void pulse_pin2_task()
{
	digitalWrite(pulse2_pin, HIGH);
 
	digitalWrite(pulse2_pin, LOW);
}
 
// idle task
void idle(uint32_t idle_period)
{
	// this function can perform some low-priority task while the scheduler has nothing to run.
	// It should return before the idle period (measured in ms) has expired.  For example, it
	// could sleep or respond to I/O.
 
	// example idle function that just pulses a pin.
	digitalWrite(idle_pin, HIGH);
	delay(idle_period);
	digitalWrite(idle_pin, LOW);
}
 
void setup()
{
	pinMode(pulse1_pin, OUTPUT);
	pinMode(pulse2_pin, OUTPUT);
	pinMode(idle_pin, OUTPUT);
 
	Scheduler_Init();
 
	// Start task arguments are:
	//		start offset in ms, period in ms, function callback
 
	Scheduler_StartTask(0, 500, pulse_pin1_task);
	Scheduler_StartTask(0, 300, pulse_pin2_task);
}
 
void loop()
{
	uint32_t idle_period = Scheduler_Dispatch();
	if (idle_period)
	{
		idle(idle_period);
	}
}
 
int main()
{
	init();
	setup();
 
	for (;;)
	{
		loop();
	}
	for (;;);
	return 0;
}

The program pulses different pins to indicate when specific tasks are running.  You could also have tasks to step a stepper motor, obtain a sonar reading, check the radio for new packets, and send regular status updates to a base station. The example code above pulses pins to indicate when a task is running. You can use a logic analyzer to find out exactly when the tasks are running. Here is a swimlane diagram illustrating the task runtimes, including the idle task (the tasks were given internal 30 ms delays to make their runtimes clearly visible):

Time-triggered scheduler runtimes measured by logic analyzer.

Time-triggered scheduler runtimes measured by logic analyzer (click to expand).

Note that when the two tasks are scheduled at the same time, the first task is given priority.

3 thoughts on “Lab Guide: Time-Triggered Scheduling

  1. bill

    This is C style Function Callback.
    When your code becomes more that this toy, you will want to use several callers and want to use it as a library, you would want to use CLASSES. That is called Member Callback and it is an entirely different proposition.

    Reply
    1. Neil MacMillan Post author

      Thanks for your comment. With all due respect, this technique is quite sufficient for coordinating several control loops that are written in C and are run on a low-resource microcontroller (the file extensions are .cpp for compatibility with Arduino, but our code is written in C). Some of the students in our lab this year even used the timing mechanisms found in projects like AeroQuad and ArduPilot, which mechanisms are even simpler than time-triggered scheduling, and found them to be adequate. I have added some comments to the introduction to clarify.

      Reply
  2. Pingback: Project 1: Phase 1 | CSC 460 – Roomba Project

Leave a Reply

Your email address will not be published. Required fields are marked *

ERROR: si-captcha.php plugin: GD image support not detected in PHP!

Contact your web host and ask them to enable GD image support for PHP.

ERROR: si-captcha.php plugin: imagepng function not detected in PHP!

Contact your web host and ask them to enable imagepng for PHP.