Ron Kreymborg
TaskR is a simple event based task dispatcher for embedded systems. It provides for queuing ready tasks on a first come first served basis. Event based means a new task is started or restarted by an event, where an event occurrence is usually implemented via a processor interrupt. A task is defined as a function that executes in a finite time, where finite simply means it must eventually exit.Tasks may be queued individually at any time on the ready queue. Tasks are removed from this queue and run one after the other until the queue is empty.
The function to add tasks to the queue (QueTask) is typically called from an interrupt routine with the task name as the parameter, but may be called from anywhere. The function to run all tasks currently in the queue (Despatch) is usually called from the main program in a loop entered at the conclusion of system initialisation.
Note that task scheduling does not imply a pre-emptive system, but a system for managing multiple tasks in a controlled way. A task function cannot return anything and cannot take parameters. It may call other functions of course as part of its execution sequence. The intent is that a task addresses a particular state change or computation as the result of an event and when completed will have moved the system to a new state.
As all tasks must share the processor, the execution time of the longest task must be less then the maximum response time required of the system. Thus if one task must be run every 5 mSecs, it cannot coexist with some huge task that takes 25 mSecs to complete. Break the long task into sections where this situation occurs. This is relatively simple because the task can record its current state locally then re-schedule itself just prior to exiting.
When an interrupt occurs, the relevant interrupt executes, calls the queue-task function to add its associated task to the tail of the ready queue, and then exits. The next cycle through the main program loop that calls the despatch function will now find a new task on the queue. This task is taken off the head of the queue, made the current task, and started running. The task runs until it decides to conclude. Other interrupts may occur while the task is running, but their only effect when they call QueTask is to put other tasks on the ready queue. A task cannot be put on the queue if it is there already. As noted earlier, a task can put itself back on the ready queue before exiting and if there are no other tasks, it will re-run immediately.
Where the response to an interrupt must occur pronto (for example where a character arrives at the serial interface) then the necessary code to save the character would naturally be included within the interrupt routine. (In this case the queued task (if any) would perhaps check for an end-of-message character or similar). But in general, tasks are run via the ready queue, and responses that embody significant processing are always run as queued tasks. The main plus of this system is that a running task has complete ownership of the cpu, and need not worry about contention issues with other tasks such as occur in pre-emptive systems.
In a task based paradigm, interrupt events are the only instigators of processing, and the cpu time involved in most tasks is typically from a few dozen to a few hundred microseconds. Even when a task does require considerable processing that could take many milliseconds to complete, as long as this does not mean other tasks could be compromised, the system will execute as expected. Many embedded systems fit this model perfectly. The TaskR2 module described elsewhere adds a delay queue which allows events to run at specific times or after specific delays.
Because the QueTask (and sometimes Despatch) function is called from interrupt routines, it must be considered a critical region. Here a critical region means that no more than one process may be executing the code at any one time. In fast microprocessors like the Atmel AVR's and where the code to be protected executes in a dozen or so microseconds, it is convenient to provide a critical region by ensuring global interrupts are off while the code is executing. Because both functions may be called with interrupts either on or off, the interrupt flag state must be preserved during processing and restored on exit. The two critical region headers provide this facility for each function.
Two defines are provided to enable specific functionality. These control whether the processor's sleep capability is used, and whether a record of the maximum queue depth is maintained.
The AVR processors can considerably reduce their current requirements by powering down various internal systems. They do this by executing the sleep instruction in various modes. The processor will remain powered down (and effectively halted) until the next interrupt occurs. Have a look at the Using the Sleep Instruction article for more details. TaskR will execute the sleep instruction once the ready queue is empty if USE_SLEEP_MODE is defined. Otherwise the Despatch function will simply return. For the Mega103 the the default sleep mode is Idle, and the initialisation routine sets this mode with the code:
cbi(MCUCR, SM0); // setup for Idle mode sleep cbi(MCUCR, SM1); sbi(MCUCR, SE);
This sets the two MCUCR bits to 00. If you are using the Power Down mode, change these instructions to:
sbi(MCUCR, SM0); // setup for Power Down mode sleep sbi(MCUCR, SM1); sbi(MCUCR, SE);
If you define RECORD_MAX_STACK_DEPTH then TaskR will update the maximum queue length reached each time QueTask is called. Your program can then access this number at any time via the GetMaxStackSize function. This is useful during program development where it can be displayed via leds or monitored in some way and allows you to subsequently set the MAX_TASKS value with some confidence. I would recommend setting this one or two values larger than you ever see during debugging, just to be sure.
Note that here the queue is implemented as two arrays to minimise the associated code size. If your application has the luxury of code space to spare, you might like to change the declaration throughout the module to a more conventional structure:
struct {
void (*Task[MAX_TASKS+1])(void); // pointer to task
BYTE Next[MAX_TASKS+1]; // list linker
} Queue;
The following list the taskr.h and taskr.c files respectively. They are listed here for completeness but may not always be at the latest revision. You can download the TaskR set of files to get the latest revision.
// taskr.h
//
// Header for tasks only version.
#ifndef _TASKR_H
#define _TASKR_H
#include <interrupt.h>
//-----------------------------------------------------------------------
#define MAX_TASKS 20 // set for your application
//-----------------------------------------------------------------------
#define BYTE unsigned char
#define UNSIGNED unsigned int
#define SLEEP asm("sleep"::);
// Public task management functions.
//
extern void InitTaskR(void);
extern UNSIGNED QueTask(void (*func)(void));
extern void Despatch(void);
extern BYTE GetMaxStackSize(void);
#endif // _TASKR_H
/******************************************************************************
MODULE: TaskR.c
FUNCTION: A module to provide facilities for queuing ready tasks on
a queue along with functions to run tasks from the queue
on a first in first out basis.
AUTHOR: Ron Kreymborg
Jennaron Research
December 2000
REVISIONS:
******************************************************************************/
#include <signal.h>
#include "Taskr.h"
#include "critical1.h"
#include "critical2.h"
#define USE_SLEEP_MODE // undefine to always return from Despatch()
#define RECORD_MAX_STACK_DEPTH // usually defined while testing
static void RunTask(void);
static UNSIGNED GetNewTask(void (*func)(void));
static void (*Task[MAX_TASKS+1])(void); // pointer to task
static BYTE Next[MAX_TASKS+1]; // linked list
static BYTE RunningTask; // current task
static BYTE TaskHead, TailTask; // head and tail of task queue
static BYTE NewTask; // new task queue pointer
static BYTE MaxStackSize = 0; // biggest stack size
//-----------------------------------------------------------------------------
// Initialise. Must be called before first use. Sometimes the real-time
// clock can be initialised here too.
//
void InitTaskR(void)
{
#ifdef USE_SLEEP_MODE
cbi(MCUCR, SM0); // setup for Idle mode sleep
cbi(MCUCR, SM1);
sbi(MCUCR, SE);
#endif
}
//-----------------------------------------------------------------------------
// Put a task on the tail of the ready list. Call with a pointer to the task
// as argument. Returns TRUE if the task could not be queued.
//
UNSIGNED QueTask(void (*pntr)(void))
{
UNSIGNED retval = 1;
ENTER_CRITICAL_REGION1; // must be indivisible
// Get a task pointer if one is available
//
if (GetNewTask(pntr))
{
// Is there a tail task?
//
if (TailTask != 0)
Next[TailTask] = NewTask; // link tail to new
else
TaskHead = NewTask; // else new is head
TailTask = NewTask; // tail always new
Next[NewTask] = 0; // flag tail link
Task[NewTask] = pntr; // insert task pointer
NewTask = 0;
retval = 0; // return Ok
}
EXIT_CRITICAL_REGION1;
return retval;
}
//-----------------------------------------------------------------------------
// Run all tasks in the ready queue. When the queue empties, go to sleep.
//
void Despatch(void)
{
ENTER_CRITICAL_REGION2; // must be indivisible
while (TaskHead)
{
RunningTask = TaskHead;
TaskHead = Next[RunningTask]; // head is now next
// If there are no more tasks then clear the tail
//
if (TaskHead == 0)
TailTask = 0;
// Run this task. Note this function does not return
// until the task completes.
//
RunTask();
}
EXIT_CRITICAL_REGION2;
#ifdef USE_SLEEP_MODE
// The queue is empty, so sleep until an interrupt occurs.
//
SLEEP;
#endif
}
#ifdef RECORD_MAX_STACK_DEPTH
//----------------------------------------------------------
// Return the maximum stack entries to date.
//
BYTE GetMaxStackSize(void)
{
return MaxStackSize;
}
#endif
//-----------------------------------------------------------------------------
// PRIVATE FUNCTIONS.
//-----------------------------------------------------------------------------
//
//-----------------------------------------------------------------------------
// Run the task in the ready queue at . When it returns, clear
// the link entry. If it has re-scheduled itself, put it on the queue
// again, otherwise clear the queue entry.
//
static void RunTask(void)
{
EXIT_CRITICAL_REGION2;
(*Task[RunningTask])(); // run the task
ENTER_CRITICAL_REGION2; // must be indivisible
Next[RunningTask] = 0;
// Otherwise ensure task is idle
//
Task[RunningTask] = 0;
RunningTask = 0;
}
//-----------------------------------------------------------------------------
// Find the first free entry in the data structure. Returns FALSE if a free
// spot could not be found, or this task is already on the queue.
//
static UNSIGNED GetNewTask(void (*ptr)(void))
{
NewTask = 1;
while (NewTask <= MAX_TASKS)
{
if (Task[NewTask] == 0)
return 1; // free spot found
if (Task[NewTask] == ptr)
return 0; // here already, ignore
NewTask++;
#ifdef RECORD_MAX_STACK_DEPTH
// Optional: keep a record of max stack depth
//
if (NewTask > MaxStackSize)
MaxStackSize = NewTask;
#endif
}
return 0; // no room
}