MPTHD: The Context Switching Layer

Essential to any multitasker is the ability to switch the processor's context from one process to another. Traditional multitaskers do this by having interrupt handlers save the state of processor by pushing it on the stack when they are invoked. This is an efficient but complex and machine dependent approach. The MPTHD layer achieves the same effect in a portable way that is easy to understand.

The MPTHD layer introduces the notion of an thread, and independent thread of execution. Like a normal process, a thread has its own stack on which it executes. With its own stack, the state of the thread can be saved, and then the thread later resumed (see illustration of internal MPTHD datatype).

To perform this context switch, the thread must call the mpthd$\_switch$() function. Now the mpthd$\_switch$() function is not your ordinary function. The mpthd$\_switch$() function is special. Like an ordinary function, the mpthd$\_switch$() can return to you. Or it can return to anyone else you specify! Indeed, the mpthd$\_switch$() function can return to any active call of mpthd$\_switch$(). You specify as an argument the thread you want it to return to, and returns from that thread's call of mpthd$\_switch$(). In fact it tells that thread (via its returned argument) the thread that switched to them. (See illustration).

Figure: MPTHD: Context Switching Illustration
\begin{figure}
\begin{verbatim}
Thread A Control Flow Thread B
-------...
...t :
: V :
Output: ''Hello, there!''
------\end{verbatim}
\end{figure}

The mpthd$\_switch$() also works fine in a multiprocessor environment. If another processor is executing a thread when you switch to it, it will wait until the other processor switches out of the thread before you switch in. And if you switch to an invalid thread or one with a corrupted stack, mpthd$\_switch$() returns to you telling you that it came from you (not some other thread), which you may interpret as an error.

The mpthd$\_switch$() interface is also portable. In many cases it can be directly implemented with ``C'''s standard setjmp() and longjmp() functions. In other languages, the function is quickly coded in assembly and ``linked in.'' Most every stack based-machines can support it (see internal representation).

Figure: MPTHD: Thread Datatype Internals
\begin{figure}\par
\begin{verbatim}
Semaphore (to control multiprocessor...
...
jmp_buf (for saving the thread's execution state)\end{verbatim}
\end{figure}

With a few additional support functions, threads can be easily created and destroyed (see MAN page for exact details).

Notice that the initialization function requires several (three) arguments: the memory buffer used to store the thread, the size of the buffer, and the function to execute. All this is awkward to specify when we set up a thread, so suppose we store a default size in some global variable. But, remember, we're in a concurrent environment: different tasks may change the default value, and different tasks may want different defaults. Therefore, the thread maintains a heap, private to that task. Instead, we can set up a global constant, an offset into the current thread's heap, containing our default buffer size. That way, each task has its own defaults, but refer to them with the same variable name. MPTHD automatically copies the parent's heap when initializing a new thread, so defaults are inherited. This simple feature can also be used for passing arguments from the parent to the child thread.

So far so good. Now suppose we also don't want to specify a the buffer storing a thread – suppose, instead, MPTHD called malloc to dynamically allocate storage for us. Ahh, but storage is a resource. Not all languages have this resource (limiting portability). More importantly, dynamic memory allocation sometimes takes time – it must be interruptable. A high-level scheduler may switch into another thread which allocates memory while our thread is doing the same! Because memory allocation is a resource, this feature will have to wait for higher levels.

In short, the MPTHD cluster, with the mpthd$\_switch$() function, is a simple and portable way to do context switching. The package provides examples of how it can be used, such as a tank game in which entrants submit ``C'' programs to control their tanks. Each ``program'' runs as an independent thread, with a ``referee'' thread scheduling the battle!