Cooperative Multitasking in C++

Embedded systems programming presents some interesting challenges. A typical application might involve juggling a variety of sampling, processing, control, and communication functions simultaneously on a very small system. Such applications are inherently parallel and are best implemented by many small tasks working together. I've recently switched from developing these applications in a cooperative multitasking Forth environment to object-oriented programming in C++. Unfortunately, operating system support is required for normal preemptive multitasking, context switches can be slow, and resource sharing can be complex. Not wanting that kind of overhead in an embedded application, my solution was to create cooperative multitasking objects for C++.

Cooperative vs. Preemptive Multitasking

In preemptive multitasking, an interrupt timer periodically executes an executive program. The executive determines if the current task has been running too long, and if so forces a context switch to the next scheduled task. If the task still has time, it updates a counter and returns from interrupt. Because an interrupt can occur and force a context switch at any point in the program, the system must save and restore the processor's entire state. Resource sharing between tasks requires routines to lock and unlock common data structures. Further, operating system calls must be reentrant (which MS-DOS is not).

Cooperative multitasking, on the other hand, has no executive overhead and does not rely on interrupts. Instead, when a task is ready to give up control the task calls a routine (pause), which switches context to the next task. Because the point of the switch is always the same (the pause routine), only the stack pointer and a few registers are saved and restored. This makes the context switch simple and potentially very fast. Cooperative multitasking greatly simplifies resource sharing since other tasks can't "sneak in" during updating of common structures. System calls can be performed in any operating system because a context switch cannot occur unexpectedly during the call.

The Code

The cooperative multitasker I'm presenting here is implemented using a C++ task object which is part of a multiple channel communication program currently under development at our company. The task object and associated header file are in Listings One and Two. I've also included a demo program in Listing Three to show the multitasker in use. The demo program requires the simple text window object and header file which make up Listings Four and Five. The interface into the multitasker consists of the routines InitTasking, fork, and pause. InitTasking sets up the multitasking system and must be called before any other calls are made. fork spawns new tasks and pause performs the context switch to the next task. The task object itself has an Activate method to change what a task object is executing and a Show method to display the current instance variables for debugging purposes. Although I wrote the code in Borland's Turbo C++, it should be fairly portable to other environments, with the following caveats:

Listing One

_COOPERATIVE MULTITASKING IN C++_
by Marc Tarpenning


// File: TASK.H
// Task object header -- Each task object contains its own stack, links to next
// and previous task objects in the round robin, the saved stack pointer, and
// debug information.

class Task {
    int *area;      // base stack location
    int id;         // task id number for debuging purposes
    Task *next;     // next task in chain
    Task *prev;     // prev task in chain
    int *saved;     // saved stack location during pause
    int *top;       // top stack location

public:
    void Activate(void (*)() );     // starting function
    int GetId()                     // return id number
        { return id; }
    Task *GetNext()                 // return next pointer
        { return next; }
    int *GetSP()                    // return saved sp
        { return saved; }
    void SetNext(Task *t)           // sets next pointer
        { next = t; }
    void SetPrev(Task *t)           // sets prev pointer
        { prev = t; }
    void Show();                    // display data for debugging
    void Switch();                  // context switch to next task
    Task(int);                      // constructor
    ~Task();                        // destructor
};

Task *fork(void (*)() );            // forks tasks
Task *InitTasking();                // Initializes all task stuff
void pause();                       // switches to next task

extern int totalTasks;              // debug counter of total tasks

Listing Two

// File: TASK.CPP
// Cooperative Multi-tasking in C++ --
// Marc Tarpenning, P.O. 254801, Sacramento, CA  95865
// Cis: 71435,1753    uucp: [email protected]

#include <conio.h>
#include <stdlib.h>
#include "task.h"

// Protypes
void terminate();               // terminate task on completion

// Defines
#define STACKSIZE   0x200       // Stack size of each task

// Global variables
Task *CurrentTask = 0;          // current task executing
Task *SystemTask;               // main task using system stack
int totalTasks = 0;             // debug counter of tasks

// Task.Activate - sets up the task object's stack so the when the task is
// switched to, the passed function is performed.
void Task::Activate(void (*f)() )
{
    saved = top;                    // reset stack
    *(--saved) = (int) &terminate;  // kill task function on exit
    *(--saved) = (int) f;           // place function for return address
    *(--saved) = _BP;               // save all registers for switch
    *(--saved) = _SI;               // save SI
    *(--saved) = _DI;               // save DI
}

// Task.Show - Debug information is displayed
void Task::Show()
{
    cprintf("Task: %4i  area: %04X\n\r",id,area);
    cprintf(" top: %04X saved: %04X\n\r",top,saved);
    cprintf("prev: %04X  next: %04X",prev,next);
}

// Task.Switch - switch context to next task object in the round robin.
// It saves the current stack pointer, gets the stack pointer of the
// next task (after making it current), and returns.
void Task::Switch()
{
    _SI = _DI;                          // force compiler to save SI and DI
    saved = (int *) _SP;                // store stack pointer
    CurrentTask = next;                 // set current task to next task
    _SP = (int) CurrentTask->saved;     // restore new task's stack pointer
}

// Task.Task - Initializes the new task object.  Threads the object into
// the linked round robin of other tasks.  If size is 0, then does not
// allocate any stack space and uses the system stack instead (system).
Task::Task(int size)
{
    static int newid = 0;       // unique identifier for each task
    id = newid++;               // set ID and inc
    totalTasks++;               // inc debug counter of total tasks
    if (size) {                 // Want to create operator task?
        if ((area = (int *) malloc(size * 2)) == 0)     // No, so allocate
        {
            cprintf("Not enough memory to create task %i\n", id);
            exit(1);
        }
        top = area + size;              // set absolute top of stack
        saved = top;                    // default saved stack to top

        next = CurrentTask->GetNext();  // link task in chain
        prev = CurrentTask;
        prev->SetNext(this);            // set current task to point to me
        next->SetPrev(this);            // set next task to point to me
    } else {                    // operator task, so don't allocate stack
        top = (int *) _SP;              // instead, co-opt system stack
        saved = top;
        next = this;                    // since first task, make point
        prev = this;                    // to myself
    }
}

// Task destructor - return all allocate memory to the system.
Task::~Task()
{
    totalTasks--;           // dec debug counter of total tasks
    prev->SetNext(next);    // unthread this task from the round robin.
    next->SetPrev(prev);

    CurrentTask = next;     // Set new current task
    if (area)               // don't free if no stack allocated (system)
        free(area);         // free object's stack
}

// fork -  creates a new task to execute the passed function.  When
// the function has completed, the task is automatically destroyed.
// fork returns a pointer to the new task object or NULL if out of memory.
Task *fork(void (*f)() )
{
    Task *newtask;              // pointer to new task object
    // In small memory models, malloc uses the stack pointer to
    // determine if there is any free memory on the heap.
    // To allow forking from sub-tasks, we "borrow" the system stack
    // for the malloc operation.
    int temp = _SP;             // save current stack pointer
    _SP = (int) SystemTask->GetSP() - 20;   // borrow system stack
    // create new task object
    if ( (newtask = (Task *) new Task (STACKSIZE)) )
        newtask->Activate(f);   // Setup new stack to execute function
    _SP = temp;                 // restore original stack
    return newtask;             // return a pointer to the new object
}

// InitTasking - Initializes anything required before multitasking can
// begin.  This function must be called before any other tasks are
// forked.  It creates the "system" task by coopting the system
// stack into a task object (task # 0).  It also sets CurrentTask
// to point to the new operator task.
Task *InitTasking()
{
    CurrentTask = (Task *) new Task(0);     // create system task
    SystemTask = CurrentTask;   // set system task pointer
    return SystemTask;          // return with pointer to system task
}

// pause - non-object interface to switch context.
void pause()
{
    CurrentTask->Switch();          // context switch out of current task
}

// terminate - kills the current task when the fork is over.  This is not
// a method, but its address is setup on the initial stack so if the
// task's function ever returns, terminate will be the next execution addr.
void terminate()
{
    _DI = _SI;                          // force compiler to save DI and SI
    delete CurrentTask;                 // kill the current task
    _SP = (int) CurrentTask->GetSP();   // set to next task's stack and
                                        // return into the new task
}

Listing Three

// File: DEMO.CPP
// Demo program for cooperative multitasking objects
// Marc Tarpenning, P.O. 254801, Sacramento, CA  95865
// Cis: 71435,1753    uucp: [email protected]

// General includes for prototype headers
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <conio.h>
#include <string.h>
#include <bios.h>
#include <ctype.h>
#include <dos.h>

#include "task.h"
#include "twindow.h"

// Prototypes for simple demo functions
void endlessCount();
void fiveseconds();
void funwindow();
void msdelay(int);
int  newgetch();
void periodic();
void quicky();
void status();
void wallclock();

main()
{
    /* Init multi-tasker.  Creates system parent task */
    InitTasking();                  // init task, coopt system stack

    /* ---- Init screen ----- */
    textattr(WHITE);                // set "normal" white on black
    clrscr();                       // clear screen
    _setcursortype(_NOCURSOR);      // kill cursor

    /* ----- start up some tasks ----- */
    fork(&endlessCount);            // spawn endless counter task
    fork(&wallclock);               // spawn clock task
    fork(&periodic);                // spawn periodic launcher task
    fork(&funwindow);               // spawn strange window
    fork(&status);                  // spawn total number of tasks

    /* ----- create main window for user commands ---- */
    TextWindow myWindow(1,20,80,25,(LIGHTGRAY<<4)+BLUE);
    gotoxy(20,1);
    cputs("*** Cooperative Multitasking Demo ***\r\n");
    cputs("    Each one of the windows is a seperate task object ");
    cputs("executing a C++\r\n");
    cputs("    function.  All are running 'concurrently' using the ");
    cputs("pause() context\r\n");
    cputs("    switch routine.");
    gotoxy(2,6);
    cputs("Commands: [M]ake new task, [Q]uit");

    /* ----- wait for input & process key strokes ------ */
    for (;;)
        switch ( toupper( newgetch() ) ) {
            case 'Q':               // quit - clean up screen and leave
                window(1,1,80,24);
                textattr(WHITE);
                clrscr();
                _setcursortype(_NORMALCURSOR);
                return(0);
            case 'M':               // make - fork a new quick task
                fork(&quicky);
                break;
            default:                // illegal character
                sound(500);
                msdelay(160);
                nosound();
                break;
        }
}

// endlessCount - opens a window and counts up forever.
void endlessCount()
{
    TextWindow myWindow( 40,7,64,8,(CYAN<<4)+RED );
    cprintf(" This task never ends!");
    long count = 0;
    for(;;) {                               // just keep counting, but
        myWindow.Activate();                // don't forget to pause
        gotoxy(1,2);
        cprintf(" Current count: %li",count++);
        pause();                            // let other tasks run
    }
}

// fiveseconds - opens a window, counts for 5 seconds, and returns
void fiveseconds()
{
    TextWindow myWindow( 5,5,35,7,(GREEN<<4)+RED );     // make text window
    cprintf("    This is a temporary task");
    gotoxy(2,3);
    cprintf("which only lasts five seconds");

    time_t t;                               // get current time
    t = time(NULL);

    int i = 10000;                          // count down from 10000
    while (difftime(time(NULL),t) < 5) {    // keep counting down until
        myWindow.Activate();                // difftime is five seconds
        gotoxy(13,2);                       // or more.
        cprintf("%5i",i--);
        pause();                            // let other tasks run
    }
}

// funwindow - displays moving character in window
void funwindow()
{
    TextWindow myWindow(65,10,78,10, (BROWN<<4) + YELLOW);

    for(int i=0;;i = ++i % 20) {    // forever move i from 0 to 19
        myWindow.Activate();
        gotoxy( abs( ((i/10) * -20) + i) + 1 ,1);   // calc cursor
        cputs(" * ");               // so range is 1..10 then 10..1
        msdelay(100);               // delay ~ 100 ms
    }
}

// msdelay - delays the number of milliseconds with ~ 55ms resolution
void msdelay(int delay)
{
    long ticksplus = biostime(0,0L) + delay / 55;
    while (biostime(0,0L) < ticksplus)      // wait until time has passed
        pause();                            // let other tasks run
}

// newgetch - does same as getch, except calls pause while waiting
// for a keyboard hit.
int newgetch()
{
    while (!kbhit())
        pause();
    return getch();
}

// periodic - occasionally launchs another task
void periodic()
{
    TextWindow myWindow(1,10,41,11,(LIGHTGRAY<<4) + MAGENTA);
    cputs(" Every ten seconds launch temporary task");
    for (;;) {
        for (int i=0; i < 10; i++) {    // loop ten times before forking
            myWindow.Activate();
            gotoxy(20,2);
            cprintf("%i",i);        // display current count
            msdelay(1000);          // delay ~ one second
        }
        fork(&fiveseconds);         // spawn new task which dies in 5 sec
    }
}

// quicky - opens window, hangs around for a few seconds, and leaves
void quicky()
{
    static int xpos = 0;                // x position of new task window
    static int ypos = 0;                // base y of new task window
    TextWindow myWindow( xpos+1,ypos+12,xpos+16,ypos+12,(GREEN<<4)+BROWN);
    xpos = (xpos+3) % 64;               // inc x position of "step" windows
    ypos = ++ypos % 7;                  // inc y but keep within 7 lines

    for (int i=0; i < 10; i++) {        // count down for ten seconds
        myWindow.Activate();
        cprintf(" Dead in ten: %i",i);
        msdelay(1000);                  // delay ~ one second
    }
}

// status - displays the number of tasks running
void status()
{
    TextWindow myWindow(1,1,18,1, (CYAN<<4) + MAGENTA);
    for (;;) {
        myWindow.Activate();
        cprintf(" Total tasks: %2i", totalTasks );      // display total
        msdelay(200);               // delay ~ 200 ms
    }
}

// wallclock - continuously displays the current time
void wallclock()
{
    TextWindow myWindow( 55,1,80,1, (LIGHTGRAY << 4) + BLUE);
    time_t t;                       // will hold the current time
    char buf[40];                   // temp buffer so can kill the \n
    for (;;) {                      // always keep updating the time
        myWindow.Activate();

        t = time(NULL);             // get the current time string address
        strcpy(buf,ctime(&t));      // copy the string into temp
        buf[24]='\0';               // kill the \n so window won't scroll
        cprintf(" %s",buf);         // display it

        msdelay(1000);              // wait for ~ one second
    }
}

Listing Four

// File: TWINDOW.H -- Demo text window objects -- These window objects create
// a primitive text window for demo program.
// Assume Borland C++ libarary functions

class TextWindow {
    int attrib;             // text mode attribute
    int left,top;           // starting x and y position
    int right,bottom;       // ending x and y position

public:
    void Activate();                    // make active
    TextWindow(int,int,int,int,int);    // constructor
    ~TextWindow();                      // destructor
};

Listing Five

// File: TWINDOW.CPP -- Demo text window objects
// Marc Tarpenning, P.O. 254801, Sacramento, CA  95865
// Cis: 71435,1753    uucp: [email protected]

#include "twindow.h"
#include <stdio.h>
#include <conio.h>

// Window activation - makes this window the active window.
void TextWindow::Activate()
{
    window(left,top,right,bottom);      // Use C++ library
    textattr(attrib);                   // to make window active
}

// Window constructor - store coordinates and clear window
TextWindow::TextWindow(int l,int t,int r,int b,int a)
{
    left = l;           // set up all instance variables
    top = t;
    right = r;
    bottom = b;
    attrib = a;
    Activate();         // activate window
    clrscr();           // clear window
}

// Window destructor - clears window with black background
TextWindow::~TextWindow()
{
    Activate();
    textattr( (BLACK << 4) + WHITE);
    clrscr();
}

The demo program uses several screen functions unique to Borland's standard library, and the task objects get direct access to the CPU registers via Borland's "pseudovariables." You can easily replace Borland's pseudovariable references with standard assembly code if required. Any type of processor could be used, but the saving of registers would of course have to be changed. Though these objects are designed for the small memory model, only a slight modification is required for larger models.

How to Context Switch

The C calling convention, also used in C++, performs a procedure call by pushing all of the passed parameters onto the stack, followed by the return address. When the procedure call finishes, it returns to the pushed address, leaving the calling code to remove the passed parameters from the stack. The registers BP, SI, and DI and the stack pointer (SP) maintain the entire state of a Turbo C++ program upon entering a function. Therefore, to save the state of a task we need only push these three registers and store the stack pointer. The next task starts by getting the saved stack pointer from the next task object, popping the registers, and returning to the address where the new task left off. The new task now executes and the caller straightens out the stack. An example execution flow for a two task system can be seen in Figure 1. Note that in Task 1 the pause within the while loop executes twice. Each execution takes the program flow to a different place within Task 2, depending on where Task 2 gave up control the previous time.

Figure 1.

Task Objects

The fork routine in Listing Two creates a new task object and initializes the object to execute a passed function. Each object contains its own stack area, the saved stack pointer, an ID number for debugging, and links to other task objects. The number of task objects is limited only by available memory. The task object constructor method links the new object into a circular list of other task objects (Figure 2). The size of the private stack area is passed to the constructor. The default stack size in this program is somewhat large due to library functions such as printf, which use considerable stack space. A stack size of zero causes the constructor to assign the system stack to the new stack object. Only one task object can own the system stack. The program creates this task during the InitTasking function called at the beginning of the program.

Figure 2.

In small memory models malloc (which allocates the stack area) uses the current stack pointer to determine if any heap space is available. In order for child processes to spawn additional tasks, fork "borrows" the system stack before the new operation. Any tasks can then spawn additional tasks as needed by using fork. The Activate method initializes the task's stack to restore dummy values to SI, DI, BP, and initializes the return address to execute the function passed to fork. Activate also places the address of the routine terminate on the stack. If the passed function ever finishes and returns, execution passes to terminate, which deletes the task object and performs a context switch to the next task. Each task object has a forward and backward pointer, so the task destructor method can easily take the task object out of the linked list.

Switching

The currently running task executes pause when the task is ready to give up control. This routine sends a Switch message to the currently running task object. Switch pushes the three registers, saves the stack pointer, and moves to the next task in the linked list. The Switch method uses a slight trick to save the registers. For any object method, the compiler automatically generates a BP PUSH at the start of the routine and the complimentary BP POP before the return instruction.

The compiler normally uses SI and DI for register variables and generates PUSHs only if register variables are used in the method. By assigning SI to DI at the beginning of the routine, we force the compiler to save SI and DI by generating SI PUSH, DI PUSH, and the corresponding POPs at the end of the routine. After the PUSHs, all the required registers are on the stack, so the stack pointer is stored in the object. The function retrieves the stack pointer of the next task in the chain and, as the routine exits, pops the new task's registers from the stack and returns to the new task's previous execution address. The assembly code generated by Switch is in Figure 3. This technique of forcing the compiler to save important registers also works in many other compilers. Although the routine could be optimized in assembly, it was easier to keep the code high level and not resort to any direct assembly language programming.

  Task: :Switch()
                    push bp        ;save stack frame
                    mov bp, sp
                    push si        ;save register SI
                    push di        ;save register DI
                    mov si, di     ;dummy instruction
  ...
  _SI = _DI;                       //dummy instruction to force SI, DI save
  saved = (int*)_SP;               //store stack pointer
  CurrentTask = next;              //set task to next task
  _SP = (int) CurrentTask->saved;  //use new task's stack pointer   ...
                  pop di           ;restore DI from new task
                  pop si           ;restore SI from new task
                  pop bp           ;restore stack frame from new task
                  ret              ;return to new task's execution address

Figure 3.

The Demo Program

The demo program creates six tasks that each run in their own text window (the program is compatible with any standard IBM display). The program creates five of the tasks by executing fork; the sixth is the "main" task, which uses the system stack. Additional temporary tasks can be created by pressing the M key when the demo is running. Even on an 8088, the program can run a large number of tasks before slowing down appreciably. The important thing to remember when programming with cooperative multitasking is to place a pause whenever a function is likely to use up a great deal of time. For example, the keyboard input routine has been coded to constantly cycle through pause while waiting for a keystroke, and delays are achieved by watching the BIOS timer and executing pause until the correct number of ticks has passed. In embedded applications, I/O routines execute pause between samples or while waiting for data availability. Communications routines execute pause until the interrupt code has constructed an incoming buffer or completed an outgoing transmission.

Conclusion

Cooperative multitasking provides some of the benefits of more powerful multitasking operating systems without many of the complexities. For embedded applications, where resources are often scarce, cooperative multitasking's lack of an executive and the associated overhead is ideal. In small environments even the dynamic memory allocation can be eliminated to produce tight and fast code. Further, until a multitasking operating system comes into widespread use, cooperative multitasking allows those of us addicted to multiple task programs to write effective applications while we wait eagerly for the demise of MS-DOS.

Marc is a software engineer with Digital Alchemy Incorporated, a software consulting firm. He specializes in real-time applications and can be reached at P.O. Box 254801, Sacramento, CA 95865 or by e-mail at [email protected]. US.

Source code for this article is available here.