Christian, a freelance programmer who specializes in small-system development, can be contacted at Friesenbergstrasse 38, CH-8055 Zurich, Switzerland.
Recently, I was systems programmer of a group that developed an 80186-based embedded system designed to monitor and control moisture. The software which controlled the analyzer and a variety of peripherals included the following functionality: a force-compensation cell, an infrared heater, several temperature sensors, a customized keyboard and LCD display, a speaker, several serial channels, and a printer. One of the problems I faced was how to keep track of time--triggering rescheduling of compute-bound tasks, detecting time-out on I/O devices, making LCD display elements blink, implementing autorepeat keys, polling the temperature sensors with a chosen frequency, playing a few simple tunes with the speaker, and the like.
Following the design maxim that "data flow across module boundaries must be accompanied by control flow," I implemented in Borland C++ a "timed callback" scheme, whereby functions are queued to be invoked after a given number of system-clock ticks. The implementation uses a bounded priority queue and is quite efficient. The timed callback transmits the information that a certain number of clock ticks has passed by invoking a client-specified function from within the clock module. From within the callback, therefore, the client can switch a semaphore write to several message queues, output a byte to a hardware port, and so on. I added the ability to transmit context information from the client to its callback function. By using the return value of the callback to specify, that it should be called again after so many clock ticks, I also implemented autorepeat keys, blinking display elements, polling sensors, and sounds. Listing One (page 120) is TMDCBK.HPP, the timed-callback interface, and Listing Two (page 120) is TMDCBK.CPP, the actual implementation.
Ignoring the problems of concurrency for the moment, I proposed the scheme in Figure 1. You call timedCallback as in Example 1, then queue the callback. For example, if you have detected a keypress and want to generate a first duplicate after Delta clock ticks: AutoRepeat.queue(Delta);.
Example 1: Calling timedCallback.
timedCallback AutoRepeat (RepeatFun);
assuming that you have defined the function:
long RepeatFun (timedCallback* Self)
{
// Eg. generate duplicate keypress..
return NewDelta;
}
Figure 1: Class timedCallback.
class timedCallback
{
public:
typedef long (*timeCallbackFun) (timedCallback* Self);
timedCallback(timedCallbackFun SomeFun);
void queue(long Delta);
//-- Queues a timed callback for Delta ticks.
void cancel ();
// -- Cancels a queued callback
static void tick ();
// -- To be called for each clock tick
private:
...
};
If your RepeatFun gets invoked, it can generate the first duplicate keypress and requeue itself. That's an easy way to have the repeat frequency increase--up to a certain limit, say--if the user keeps the key pressed for a long time. If you detect a key release, however, you just cancel the callback: AutoRepeat.cancel();.
The pointer passed to the callback function is meant to allow the client to transmit context information to its callback by embedding the timedCallback object in another class and using a cast within the callback to access it; see Example 2. In this example, I used inheritance, not embedding, to relate class context to a timed callback.
Example 2: Embedding the timedCallback object in another class and using a cast within the callback to access it.
class context : timedCallback
{
// Whatever RepeatFun needs to know!
};
long RepeatFun (timedCallback* Self)
{
context *ContextPtr = (context *)Self;
...// Use ContextPtr ->* to access data
return NewDelta;
}
Top of the Heap
The scheme described here can be efficiently implemented using a heap. A heap is a fully balanced binary tree mapped neatly into a linear array (hence the fixed upper boundary on queued callbacks) and maintained in such a way as to keep the heap property invariant at all times.
The callback to be invoked first is placed on top of the heap using as the key value the required delivery time expressed as the number of clock ticks since startup. If the tick counter overflows, it's possible to use a signed long tick counter instead of an unsigned one. Then you replace the restriction on the total number of clock ticks with a restriction on the number of ticks to wait before delivery of a callback on the Delta parameter of member queue(). Requiring 0 less than equal Delta less than 231, we can handle the wraparound problem by defining Key1 less than equal Key2 && 0 less than equal Key2-Key1 and base the heap on that ordering; see Listing Two.
An Example
The example program in Listing Three, page 124, plays a simple tune in lieu of a more complete example from our embedded system (which would require inordinate amounts of detail and, above all, a multitasking system). Other examples that could make use of timed callbacks to solve time-related problems might include the following:
- Whenever the scheduler wants to run a task for which time slicing has been enabled, it queues a timed callback. However, the scheduler need never cancel that callback. Instead, if the callback is invoked by the clock module, it checks whether the task for which it has been queued is still active and forces rescheduling if necessary.
- To implement time-out control for I/O devices, you can add a timed-callback member to each I/O control block. Again, whenever a task gets blocked waiting for some I/O to complete, queue that callback. If the callback is invoked, it uses its argument pointer to access the I/O stream control block of which it is a part and unblocks the task with an appropriate status indication.
- You can use a timed callback to implement a simple automaton for sounds. If the automaton is idle and gets invoked--because we queued it from without--it starts playing a tune as indicated to it by, say, a list of triples. Each list entry specifies pitch, duration, and mode. The callback keeps working on that list, modifying its internal state as needed and requeuing itself until it reaches the end of the list, at which point it becomes idle again. Listing Three is a much-simplified version of this idea.
- To delay tasks for a given number of clock ticks, you can design a class of timers like that in Figure 2. These objects can be made more useful than a mere task delay: They can be made drift-free sources of periodic time events, requiring fewer system resources than additional tasks. (Remember, this is for a small system.) Additionally, multiple tasks can wait for the same timer to expire.
Figure 2: Class timer.
class timer : timedCallback
{
public:
typedef enum {
stopped, started, expired
} timerState;
timer();
void start(long Delta);
// -- Timer will time out after Delta clock ticks
timerState wait ();
// -- Blocks task until the timer expires or stops
void stop ();
// -- Stop timer and reactivate blocked tasks
void setPeriod();
// -- Makes the timer into a driftfree periodic
// source of events
timerState state();
private:
...
};
This example shows that callbacks offer time-related services at a level below that of tasks. If your system is rich in MIPS and bytes and your multitasking system already offers time services, you may want to use tasks instead of callbacks.
What About Concurrency?
An easy way to implement concurrency--and one that will get by during the development process--is to disable interrupts when accessing the shared data structure used to support timed callbacks--essentially, the priority queue. We can simply use the clock interrupt to drive tick(). But the more you use this facility, the more you'll find that either interrupt latency caused by these interrupt-disable periods is unacceptable or you need more processing within timed callbacks, except when servicing the clock interrupt.
In this case, you can offload callback invocation and heap maintenance from the clock-interrupt handler to a high-priority task. The clock interrupt can still be used to drive member tick(), but we would move the body of the current implementation of tick() to that task and reduce tick() to something like Example 3.
Example 3: Moving and reducing tick().
void timedCallback::tick()
{
tickCount += 1;
if (0 <= tickCount - nextOut)
wakeUp.up();
}
This implementation of timedCallback uses nextOut to remember when the next callback is to be invoked. The high-priority task simply sits in a loop: It first blocks on a semaphore wakeUp until it is time for it to invoke some callbacks. The task must be careful, however, not to get confused if it cannot finish dishing out callbacks before the next clock interrupt arrives.
Conclusion
I occasionally envy programmers who develop for targets larger than that described here. The sometimes unnecessary complexity dictated by such systems, however, can eliminate much of the joy experienced when working on small embedded systems--those that still force you into "running light without overbyte."
_TIMED CALLBACKS IN C++_ by Christain Stapfer[LISTING ONE]
<a name="0230_000e">
//===== tmdcbk.hpp -- timedCallback: Interface ======
#ifndef tmdcbk_hpp
#define tmdcbk_hpp
// -- Maximum number of simultaneously queued callbacks:
#define MaxTimedCallbacks 16 // Any number > 0 will do
class timedCallback
{
public:
typedef
long (*timedCallbackFun)(timedCallback *Entry);
// Type of function to be called after a given number of tick()
// invocations.
// Return value = Number of ticks to wait till next call (0 if
// the callback must not be requeued).
timedCallback( );
// Constructs a callback using a default 'do-nothing' function.
// This allows you to create arrays of timedCallback objects and
// define the callback function later by use of member setFun().
timedCallback(timedCallbackFun SomeFun);
// Constructs a real-time clock callback to be used for later calls
// to queue() and cancel().
void queue(long Delta);
// Queues the callback to be called after the specified number of
// invocations of member tick(). Delta == 0 cancels the callback.
// Raises : NoRoom Callback queue cannot hold another entry.
// (Not implemented)
// Note : It is ok to requeue an already queued callback.
void cancel( );
// Cancels 'this' callback - if it is queued.
// Note : It is ok to cancel a callback that is not queued.
int isQueued( )
// Returns 1 if 'this' callback is queued, 0 otherwise.
{ return index != 0; }
static void tick( );
// Advances the time by one tick. Queued callbacks may time out and
// are invoked from within member tick().
void setFun(timedCallbackFun SomeFun);
// Redefines the callback function to be used for 'this' callback.
~timedCallback( )
// Cancels the callback before it goes out of scope.. .
{ cancel(); }
private:
timedCallbackFun fun; // Address of the function to be called back.
long clock;// System clock count to wait for
unsigned index;// Aux. handshake index into the heap
// Priority heap of queued callbacks is contained in:
static timedCallback *heap[MaxTimedCallbacks + 1];
static unsigned inUse;
// Number of invocations of member tick():
static long tickCount;
void upHeap( );
// Repositions 'this' heap entry if count member has been decreased
void downHeap( );
// Repositions 'this' heap entry if count member has been increased
static long defaultFun(timedCallback* );
// Default callback function used by the constructor timedCallback().
// Prevent copying of timedCallback objects:
// (You may want to modify this.. )
timedCallback(const timedCallback& );
timedCallback& operator = (const timedCallback& );
};// class timedCallback
#endif // ndef tmdcbk_hpp
// tmdcbk.hpp
<a name="0230_000f">
<a name="0230_0010">[LISTING TWO]<a name="0230_0010">
//===== timedCallback: Implementation. timedCallback::queue() silently drops
//===== queueing requests that cannot be satisfied if the heap is already full.
#include "tmdCbk.hpp" // timedCallback interface
//#include "exc.hpp" // Exception handling (not used)
// static timedCallback data members
long timedCallback::tickCount = 0;
timedCallback *timedCallback::heap[MaxTimedCallbacks + 1];
unsigned timedCallback::inUse = 0;
// timedCallback::*() members
long timedCallback::defaultFun(timedCallback* )
// Callback used as a default for the constructor.
{
return 0;// Don't requeue
}// defaultFun()
timedCallback::timedCallback( )
{
clock = index = 0;
fun = timedCallback::defaultFun;
}// timedCallback()
timedCallback::timedCallback(timedCallbackFun SomeFun)
{
clock = index = 0;
fun = SomeFun;
}// timedCallback()
void timedCallback::setFun(timedCallbackFun SomeFun)
{
fun = SomeFun;
}// setFun()
void timedCallback::queue(long Delta)
{
long OldClock = clock;
if (Delta == 0) {
cancel();
}
else {
clock = tickCount + Delta;
if (0 < index) {
// Still queued ..
if (0 <= clock - OldClock) {
downHeap();
}
else {
upHeap();
}
}
else if (inUse < MaxTimedCallbacks) {
// Not currently queued (and there is room!)
index = inUse += 1;
heap[inUse] = this;
upHeap();
}
else {
// NoRoom.raise(); Exception handling not available!
// You may want to exit() to DOS or something.
}
}
}// queue()
void timedCallback::cancel( )
{
unsigned Index;
Index = index;
if (0 < Index) {
index = 0;
inUse -= 1;
if (Index <= inUse) {
heap[Index] = heap[inUse + 1];
heap[Index]->downHeap();
}
// else cancelling the last entry is trivial ..
}
}// cancel()
void timedCallback::tick( )
{
timedCallback **First = heap + 1;
long NewTicks;
// Advance tick count
tickCount += 1;
// Deliver timed-out callbacks
while (0 < inUse && (*First)->clock == tickCount) {
// Expired - deliver!
NewTicks = (*(*First)->fun)(*First);
if (NewTicks != 0) {
// Callback wants to be requeued
(*First)->clock = tickCount + NewTicks;
}
else {
// Callback doesn't want to be requeued
heap[inUse]->index = 1;
(*First)->index = 0;
*First = heap[inUse];
inUse -= 1;
}
if (0 < inUse) {
(*First)->downHeap();
}
}// while
}// tick()
// PRIORITY-QUEUE (HEAP) MANAGEMENT
void timedCallback::upHeap( )
{
unsigned K = index;
// Use alias as a sentinel entry to ensure we'll dropout of this loop:
heap[0] = this;
// Move 'this' up until the heap condition is satisfied again:
while (0 < heap[K >> 1]->clock - clock) {
heap[K] = heap[K >> 1];
heap[K]->index = K;
K >>= 1;
}
// Actually insert 'this' at its new position
heap[K] = this;
index = K;
}// upHeap()
void timedCallback::downHeap( )
{
unsigned J,
K = index,
Kmax = inUse >> 1;
// Scan down the heap to locate the new position for 'this':
while (K <= Kmax) {
J = K << 1;
if (J < inUse) {
if (heap[J | 1]->clock - heap[J]->clock < 0) {
J |= 1;
}
}
if (0 <= heap[J]->clock - clock)
break;
heap[K] = heap[J];
heap[K]->index = K;
K = J;
}
// Actually insert 'this' at its new position
heap[K] = this;
index = K;
}// downHeap()
// tmdcbk.cpp
<a name="0230_0011">
<a name="0230_0012">[LISTING THREE]<a name="0230_0012">
//===== play.cpp -- Example usage of timedCallback objects: Play a tune.
//===== Compiled for MS-DOS with Borland C++.
#include "tmdcbk.hpp" // Defines timed callbacks
#include <dos.h> // We need sound()
#include <time.h> // .. and clock()
// -- A sound is defined by the struct:
typedef struct {
unsigned freq;
unsigned delta;
} aSound; // More elaborate sounds include fading, up/down sweeps, etc.
// To create a tune we must hand it a list of sounds:
aSound List[] = { {1000,4},{0,1},{500,3},{0,1},{600,3},{0,1},
{700,1},{0,3},{700,1},{0,3},{700,4},{0,0} };
// A tune is defined as:
class tune : timedCallback {
static long PlayFun(timedCallback* Self);
aSound *toPlay;
unsigned nextSound;
public:
tune(aSound* Tune): timedCallback(tune::PlayFun)
{ toPlay = Tune; };
void play( )
{ nextSound = 0; queue(1); };
void stop( )
{ cancel(); };
private:
tune();// Only allow tune(aSound*) to be used!
};
long tune::PlayFun(timedCallback* Self)
//-- Timed callback: Walks down the list of sounds, sets the speaker
// and requeues itself accordingly until it reaches delta == 0.
{
tune *This = (tune *)Self;
aSound ThisSound = This->toPlay[This->nextSound];
if (ThisSound.freq == 0) {
nosound(); // sound(0) will not do!
}
else {
sound(ThisSound.freq);
}
if (ThisSound.delta != 0) {
This->nextSound += 1;
}
return ThisSound.delta;
}// PlayFun()
void DriveTick(unsigned Delta)
//-- Aux. function used to avoid fooling around with the clock interrupt.
{
static clock_t LastClock = 0;
for ( ; 0 < Delta ; Delta -= 1) {
while (LastClock == clock())
;// Wait till next clock tick
LastClock = clock();
timedCallback::tick();
}
}// DriveTick()
void main ( )
// Plays a single tune and quits.
{
tune Tune(List);
Tune.play(); // If we had multi-tasking we'd simply do this ..
DriveTick(50); // .. without having to drive the callbacks ourselves!
}// main()
Copyright © 1992, Dr. Dobb's Journal
