2010-01-29

Function Pointers and Cooperative Multitasking

In the Good Old Days of Mac OS 9 and Windows 3.1, there existed a notion of multitasking known as cooperative multitasking. This is when the OS schedules tasks to run, and gives the tasks complete control of the CPU for as long as they want it. Tasks would voluntarily relinquish control after not too long, so that other tasks could run.

Of course, a greedy task could just take over the system and not let anything else run, but such a task would lead to an unpleasant user experience, and so such software was unpopular. In other words, it was in the software's best interest to be cooperative.

Not could greedy tasks take over the system, but buggy ones could, as well! This would lead to system hangs, and user unhappiness. Real computer operating systems, like Unix, BSD, and Linux, shunned cooperative multitasking and instead used the superior idea of preemptive multitasking, in which the OS forcibly takes control away from a process when that process's time is up... no more hangs! All modern desktop OSes, including those from Microsoft and Apple, have left cooperative multitasking behind.

So why even talk about it at all? Well, it's a good way to bring up another idea in C: function pointers.

In an earlier article, I talked about pointers in C, which are variables that hold the memory address of other variables. Here's the fun bit: they can hold the memory address of functions, too! And then you can call functions indirectly via the pointer to the function!

What's we're going is use this to set up a little cooperative multitasking system.

But first let's get through some of the funky C syntax. We'll need to declare a variable that's of type "pointer to a function". We'll even be specific, and declare it to be a pointer to a function with a certain return type and a certain parameter list. E.g. "Declare a variable named 'functionpointer' that is a pointer to a function that returns an int and takes a const char* as a parameter:

// This is a function pointer

int (*functionpointer)(const char *s);

At this point, we've declared a variable named "functionpointer", but it doesn't actually point at anything.

Now for comparison, here is a function prototype for a function that returns an int*:

int *functionprototype(const char *s);  // function prototype!!
int (*functionpointer)(const char *s);  // function pointer

Note the subtle difference: the parentheses. This lets the compiler know that the * is associated with the functionpointer, and not the int before it.

So let's blow out this example into something big, and actually have the functionpointer point to a function, and then let's call it. The reason I made it return int and take the const char* parameter was so that it would match another standard function in [stdio.h](http://en.wikipedia.org/wiki/Stdio.h), namely puts()—this function prints a string on the console. We'll get the address of puts(), store it in functionpointer, and then call it.

To get the address of a function, you refer to it by name without parentheses. That is, puts("Hello!") calls the function normally, but puts is a pointer to the function. (You can preface it with ampersand if you want ("&puts"), but that's not idiomatic.) So we can store a pointer to puts() in functionpointer just with the simple assignment:

// functionpointer now points to puts

functionpointer = puts;

Now how do we call the function pointed to by the pointer? That is, how do we call puts() via functionpointer? Easy! We just add parenthesis and arguments and call it like a normal function:

// just like puts("Hello, world!")

functionpointer("Hello, world!");

And here's a full-blown example of the above stuff:

#include <stdio.h>

int main(void)
{
    // declare a variable named "functionpointer" that is a pointer to a
    // function that returns and int and takes one parameter: a const
    // char *:

    int (*functionpointer)(const char *s);

    // initialize functionpointer to point to the built-in puts()
    // function:

    functionpointer = puts;

    // now call the function via the pointer:

    functionpointer("This is just like calling puts()!");

    return 0;
}

Of course, all this so far have been for illustrative purposes and is marginally useful at best.

Something in C that's actually common is to use function pointers in the library functions [qsort()](http://en.wikipedia.org/wiki/Qsort) and [bsearch()](http://en.wikipedia.org/wiki/Bsearch). These functions accept as a parameter a pointer to a comparison function, which compares two values and returns the result. The qsort() function uses the results of the comparison function to help sort an array. The advantage of this approach is that qsort()'s behavior can be modified by passing it pointers to different comparison functions, and a generalized qsort() routine that can sort arbitrary types of data can be shipped for everyone to use.

For instance, here is a program that sorts arrays. One array is sorted forward, and one is sorted backward. The only difference in the qsort() call is the comparison function used:

#include <stdio.h>

#include <stdlib.h>

int sort_ascending(const void *a, const void *b)
{
    return *(int*)a > *(int*)b;
}

int sort_descending(const void *a, const void *b)
{
    return *(int*)a < *(int*)b;
}

int main(void)
{
    int array1[5] = { 9, 2, 6, 1, 7 };
    int array2[5] = { 9, 2, 6, 1, 7 };

    // give qsort() a pointer to the "sort_ascending"
    // comparison function:

    qsort(array1, 5, sizeof(int), sort_ascending);

    // give qsort() a pointer to the "sort_descending"
    // comparison function:

    qsort(array2, 5, sizeof(int), sort_descending);

    return 0;
}

Anyway, where were we? Oh yeah—let's see if we can use this to set up a simple cooperative multitasking system. The basic idea here is that we're going to have a bunch of "tasks", and each task will have an associated function that does all the work of that task. Each function will be called in turn, and each function is expected to return before too much time has elapsed (so it doesn't hog the system).

We'll have a structure called tasklist that knows how many active tasks there are, and knows which functions are associated with those tasks. How many tasks is easy: it's an int. But we have to have a list of functions for each task... a list of pointers to functions... an array of pointers functions... an array of pointers to functions that return void and have no parameters. Man, how do you declare that?

Again the syntax is funky, but it is what it is. Here's an example declaration of an array of pointers to functions, with 10 elements:

void (*task_function[10])(void);

There we've declared an array of pointers to functions, and that array is named "task_function". Here's an assignment to the third array element (index 2) and a subsequent call to it:

task_function[2] = foo;  // assign to point to function foo
task_function[2]();      // call it (call foo(), that is)

For this final example, we'll make up three tasks: one for Manatees, one for Goats, and one for Bats. Each task's function does a short thing and then returns control so it can go on to the next function. In main() the task list is initialized with three tasks, and the task function pointers are stored in the task function pointer array.

The main loop then runs through the task list and dispatches each one in order, and then starts over again, round-robin style. In this example, it does it forever, but that's just my arbitrary decision.

#include <stdio.h>

#define MAX_TASKS 10

struct tasklist {
    int task_count;
    void (*task_function[MAX_TASKS])(void);
};

void manatee_float_and_graze(void)
{
    printf("  The manatee is floating and grazing.\n");
}

void goat_stand_on_item(void)
{
    printf("  The goat is standing on an item.\n");
}

void bat_eat_insects(void)
{
    printf("  The bat is eating insects.\n");
}

int main(void)
{
    int i;
    struct tasklist tl;

    tl.task_count = 3;
    tl.task_function[0] = manatee_float_and_graze;
    tl.task_function[1] = goat_stand_on_item;
    tl.task_function[2] = bat_eat_insects;

    while (1) {
        printf ("Dispatching:\n");
        for (i = 0; i < tl.task_count; i++) {
            tl.task_function[i]();   // execute the task's function
        }
    }

    return 0;
}

And this gives the following output:

Dispatching:
  The manatee is floating and grazing.
  The goat is standing on an item.
  The bat is eating insects.
Dispatching:
  The manatee is floating and grazing.
  The goat is standing on an item.
  The bat is eating insects.
Dispatching:
  The manatee is floating and grazing.
  .
  .
  .

...Forever.

Ways to improve this might be to pass a pointer to a data chunk to each task so it could maintain some state between calls. Or you could choose a different scheduling algorithm that would call tasks in an order other than round-robin. Or you could allow the system to dynamically create and destroy tasks as needed.

For fun sometime in the future I might write a piece on scheduling and priorities and so on.

Historic Comments

Comments