%****************************************************************************/
%* mpthd.tex -- EDUCATIONAL ARTICLE DESCRIBING THE THREAD CLUSTER  	    */
%* Created:  see below		Release:  see below	Version:  see below */
%****************************************************************************
%(c) Copyright 1987 by Michael Benjamin Parker           (USA SS# 557-49-4130)
%
%All Rights Reserved unless specified in the following include files: */
%#include "mptsk.cpy" /*
%
%DO NOT REMOVE OR ALTER THIS NOTICE AND ITS PROVISIONS.
%****************************************************************************/
%****************************************************************************/
% OVERVIEW:
% This article talks about the concept of context switching, and its
% example implementation by the MPTHD CLUSTER.
%
% It is formatted using the public domain LaTeX, an enhancement of
% Donald Knuth's TeX text formatting system.   Both are in the public domain.
%****************************************************************************/
%****************************************************************************/
\documentstyle{article}
\pagestyle{headings}

\title{
Build A\\
{\em Portable} Multitasking Environment
\\ in ``C''\\
---------------------------------
{\em \#1 -- Switching Contexts}}

\author{
Copyright \copyright 1987\thanks{
This is a beta release of an article intended for Byte Magazine.  Do
not copy nor distribute.  This version of the article is intended for
the review and comment of the MIT community prior to the release in
Byte Magazine or other periodical.  Your thoughts and suggestions
appreciated.
}\\
Michael Benjamin Parker, MIT '89 \\
|\\
East Campus - Mun. 303\\
3 Ames Street\\
Cambridge, MA\\
617-225-6303
}

\date{Created: 11/20/87 \\ Release: 0.7 \\ Version: 12/10/87}

\begin{document}
\maketitle

\begin{quote}

This is the first in a series of three construction articles in which
you build a {\em portable} multitasking environment for programming.
The purpose of the series is two-fold:

\begin{enumerate}

	\item {\bf To Explain} the programming concepts and constructs
which come into play when building, programming, and operating within
a multitasking environment.

	\item {\bf To Construct} a general-purpose multitasking environment
for programming which is {\em portable} to most stack-based languages
and to most most mini, micro, and mainframe computers (so your
multitasking programs will be portable).

\end{enumerate}

The ``task'' is divided up into three construction articles, each of which
builds upon the code and concepts of the previous one but is complete in
itself (it does not depend on the successive articles).  The three articles
are:

\begin{description}

	\item[\#1]	{\em Switching Contexts}
	\item[\#2]	{\em Organizing a Task Force}
	\item[\#3]	{\em Managing Resources}

\end{description}

This article is the first in the series.  It {\bf explains} the
concept of context switching and {\bf constructs} a general-purpose
and {\em portable} context switch...

\end{quote}

\tableofcontents

Have you ever played one of those neat, new, sophisticated video games
and wondered how it works?  How it was written?  How the game flies
alien spaceships across the screen, fires tracking missiles whenever
you hit the phaser button, and blows away the universe when missile
and enemy collide?  It's a screen full of many independent activities
going on at once, yet synchronizing at just the right moment to give
the video game its magic!

Video games are complex systems.  They involve many asynchronous
entities (the missiles, the alien ships, even your own ship) which
must synchronize on both internal events (collisions) and external ones
(button presses).  They can be challenging to play, and even more
challenging to write, unless you possess the right abstractions...

Programs like video games with many independent entities do not
readily decompose into operations and sub-operations, into a single
hierarchal task.  A {\bf sequential} nor a {\bf functional flow}
doesn't seem to fit.  As in life, things are naturally going on in
{\bf parallel}, and even if you have only one person (or processor) to
do them, you find there are other things you can do while waiting for
something else.  Often, whether building operating systems or modeling
space wars, the problem decomposes into many, independent tasks, each
living asynchronously in its own {\bf context}...

{\bf IN THIS ARTICLE} we will explore these contexts in which a {\bf thread}
of program control executes.  Fundamental to the idea of {\bf
multitasking} is the ability to begin, restart \& suspend, and finally
end threads of execution.  The context switch we explore here packs
such {\em flow control} into a single construct, and offers it to the
programmer in a familiar form: the function call.  Currently running
on both Berkeley 4.3 UNIX and MS-DOS, its ``C'' implementation is
highly portable, and its clean functionality reduces the need for
grungy machine-dependent code on higher levels.  Subsequent articles
will build upon this flexibility and power to construct a multitasking
and potentially {\bf multiprocessing} environment within ``C''; based
on the context switch, the environment would be portable to both UNIX
and MS-DOS, and provide both {\bf interprocess communication} and {\bf
resource management} --in other words, lots of power for programs.
Sounds like fun?  Then let's get started!

\section{What's a Context Switch?}

In the traditional {\bf Van Noyman computer architecture}, there is some
subset of information which defines exactly what state a processor is in.
This {\bf state}, in combination with other inputs from memory or I/O devices,
defines exactly the sequence of future states.  For the most part, the
state of memory and I/O devices is assumed to be {\bf static} (unchanging)
unless the processor explicitly changes them (if they are changed by some
other entity as an I/O device,  the processor is usually
notified by an {\bf interrupt} for efficiency -- more on this later).  On the other hand,
the processor state changes continually and ``consciously'' with every
operation.

We call this special state the {\bf context} of a processor.  By saving
and restoring (changing) the context of the processor, we can allow one
processor to do the work of many, making it possible to manage the
computer's processors more efficiently.  We can also construct the useful
programming abstraction of independent {\bf threads of execution}.  A
processor can execute one thread for a while, then go off to execute
other threads.  Later, it or another processor can continue executing the
first thread where it left off.

Regardless of the number of processors, fundamental to this activity
is the processor's ability to save and restore (exchanging) thread contexts.  We
need to provide a provide a programming abstraction to encapsulate this
process.  Within the power of common high-level functional languages,
there two approaches we could build:

\subsection{The No-Return / Multiple-Return Approach}

In this approach, we create two special functions for context switching.
One function has the special property that it never returns, but restores
a prior context.  As a compliment, the other function has the special
property that it can return multiple times by first saving the current
context (see figure below) (C already provides a primitive form of these functions with
the $longjmp$ and $setjmp$ commands respectively, which are
tailored to the compiler just to save the current ``C'' state.)  These
functions provide a great flexibility at the cost of complexity.
The notion of a function that never returns or a function which returns
multiple times is a little strange and unconventional.  And it is easy to
``screw up'' by doing such things as $longjmp$ing into an unsaved or expired
context, or mixing up the different returns from $setjmp$.  Some
higher-level approach may be more appropriate...

\begin{figure}
\caption{Control Flow of the Two Approaches to Context Switching}
\begin{verbatim}

     No-Return / Multiple-Return                Switch Function

            A                B       *          A                  B
                                     *
   1                 x               *   1                  x
   |                 |               *   |                  |    
   |                 |               *   |                  |    
   \--> nreturn(B)   \--> mreturn()  *   \--> switch(B)     \--> switch(...)  
                     /---            *   /---               /---  
                     | /-            *   |                  |
                     | |             *   |                  |
                     V V             *   V                  V
                     x 1             *   y                  1
                                     *

\end{verbatim}
\end{figure}

\subsection{The Switch Function Approach}

So the other approach is to provide a switch function.  When called, the
switch function would switch into another context.  Later, another
context may switch back to the first, and the function would return (one
call, one return).  For symmetry, the function could take as an argument
the context to be switched to and return the context it switched from.
Unlike no-return/multiple-return, the switch approach is quite analogous
to the familiar function call.  Indeed, it is quite easy to implement the
traditional function: just ``call'' the function by switching to it, and
the function, having received the previous context from its own switch
instruction, would switch back upon ``return.''

But don't try this for recursive calls!  The analogy breaks down here.
The important difference is the ``caller'' and the ``callee'' are really
the same.  Both maintain their own state and their own stack.  Both called
the switch function.  The only difference is the ``caller'' hasn't
returned yet, while the ``callee'' has just returned.  But unlike in a
function, this ``callee'' does not have to return to its ``caller''.
Indeed, it can switch to any other context it like, which, in turn, my
switch back to the ``caller'' -- or the ``caller'' 's switch may never
return.

Another important point is that we can treat a context --the state of
execution of some thread, including its local variables (stack)-- as an
object.  One thread could potentially freeze another thread, examine its
context, perhaps modify some of its variables, and then start it running
again.  To be able to treat the control flow of a program like its data is
a very powerful capability.

In short, the switch function approach, as particular {\em application of}
the multiple-return/no-return approach, is not as flexible, but provides
the functionality we need for multitasking in an abstraction we can deal
with.

\section{Building a Context Switch in ``C''}

In implementing the context switch (see code in mp*.h and mp*.c files), we
use the powerful programming methodology of ``clustering'' similar
code and data into one modular unit with defined
interfaces.\footnote{Based on MIT Professor Barbra Liskov's CLU
programming language.  See B. Liskov et al, \underline{CLU Reference
Manual}, Springer-Verlag, New York, 1981.} In this case, we create a
thread cluster for initializing, manipulating, and deinitializing threads
of execution.  The {\bf interface} for the thread cluster is in the file
{\em mpthd.h}; you should include {\em mpthd.h} in your programs when you
wish to have multiple threads of execution.  The {\bf implementation and representation} for the threads is in the file
{\em mpthd.c}; your programs should not know about this file, and not make
any assumptions about how threads are work beyond their interface.  These
good programming disciplines help build clean, well-defined interfaces
between program modules -- a big help when your testing, debugging, or
modifying your code.

More generally, most {\em *.h} files are cluster interfaces (except
the sections marked {\em INTERNAL USE ONLY}), and their respective
{\em *.c} file (if it exists) the cluster implementation.  Within the
clusters, all datatypes are in upper case (eg, $MPTHD$) and, if
associated with a cluster, are referenced externally by name (pointer)
and internally by value (contents); on the other hand, all procedures
are in lower case, and prefixed with the major datatype they operate
on (eg, $mpthd\_switch$).  To help prevent naming conflicts, all
global names are prefixed with the initials of their creator.  In this
case, every name begins with {\em mp} for Mike Parker.  There are
quite a number of other programming disciplines adhered to within the
code not relevant to context switching but worth looking at.

Though your programs may not know how threads are implemented, I expect a
few humans are curious.  So if you haven't already, take a moment now and
read the overview and functional specification of the thread cluster in
{\em mpthd.h}, and briefly scan its implementation in {\em mpthd.c}.  Also
glance at the two major clusters it depends on, {\em mpsig.h} and {\em
mpsem.h}.  Here's a map to help guide your way (see figure).

\begin{figure}
\caption{Modular Dependency Diagram from mpthd Thread Cluster}
\begin{verbatim}
                        /------------------------\
                        |         mpthd.*        |
                        |                        |
                        | <THreaDs & PRoCessors> |
                        |           for          |
                        |    context-context     |
                        |       switching        |
                        \------------------------/
                       /                          \
                      /                            \
                     /                              \
                    \/                              \/
/------------------------\                      /------------------------\
|        mpsig.*         |                      |        mpsem.*         |
|                        |                      |                        |
|       <SIGnals>        |/_____________________|     <SEMaphores>       |
|          for           |\                     |          for           |
|   hardware-processor   |                      |  processor-processor   |
|    synchronization     |                      |    synchronization     |
\------------------------/                      \------------------------/
\end{verbatim}
\end{figure}


{\center * * *}

Since we can often understand what a program does (or can do) by understanding
how it represents its data, I will cover the data structure of the thread
cluster first.  However, I will also cover its code structure, defining
the functions available to access this data and how they work.

\subsection{The Thread Cluster - Data Structure}

The basic thread cluster data structure is MPTHD, which holds the context
of the thread.  Look at the MPTHD's structure declaration now at the
bottom of {\em mpthd.h}. You will notice MPTHD contains several fields.
Most important are the $state$ field, which stores the current processor
state when the thread is not executing, and the $heap/stack$ ``field''
(it's really after the structure), which holds the thread's stack (local
variables and function calls) and possibly a heap of variables the thread
allocates dynamically\footnote{Routines to manage this heap are beyond the
scope of this article}.  For beginning the thread, $mpsigstate$ holds the
signal blocked/unblocked state when the thread was initialized so that it
may be restored when the thread is first started.  For executing the
thread, $mpthdfn$ holds the thread function to be executed repeatedly.
For switching between threads, $oldmpthd$ holds the thread executed prior
to this one.  Finally, for safety, $stackoverflow$ detects (becomes
non-zero) when the context has become invalid due to stack overflow (when
the stack has grown over the heap and probably overwritten the thread
fields).

It is assumed that the macro $mpthd_me()$ is defined to be a dedicated
register of a processor so the processor can tell which thread it's
running (In single-processor machines, this can be a global variable.).


\subsection{The Thread Cluster - Code Structure}

In this subsection, I will cover the functions needed to fully implement
context switching.

\subsubsection{Achieving Atomicity with Signals and Semaphores}

Perhaps most fundamental to multitasking, even more than the context
switch, is the need for {\bf autonomous actions}.  It is not surprising
that they are among the first topics covered in texts on concurrent
operating systems and multitasking.\footnote{such as in Lubomir Bic,
\underline{The Logical Design of Operating Systems}, ...} An atonomous
action is an operation which must be completed in one indivisible step.
The action cannot be interrupted or partially completed.  Some things in
life require atomicity.  When changing clothes, you don't want to be
caught with your pants down, and the same is true for computers!

There are two basic approaches which we can take to achieve atomicity.
One approach is to wait until you can {\em guarantee} you can do what
you've got to do in ``one action''.  To avoid the wait, a more
sophisticated approach is to go ahead and do what you've got to do
atomicly, and if you're interrupted, to undo what you've done.
However, this approach is more complicated, requiring that you
remember everything you've done so far.  More importantly, all we've
really done is break up one big ``atomic'' action into smaller
actions, which, if you think about it, must also be atomic.  In other
words, we're going in circles.  Thus at some point, we will have to
have an action which must wait until it can guarantee to
complete.  To insure we are not interrupted, we need to {\bf
synchronize} ourselves with all parts of our environment which may
interrupt us, namely other processors and independent hardware the
computer may have.  We need the synchronicity of {\bf signals} and
{\bf semaphores}...

\begin{description}

\item[A Signal], or, in lower-level constructs, an {\bf interrupt}, is a
common means used to synchronize a processor with external (and
asynchronous) hardware (such as I/O drivers).  A processor supporting
interrupts automatically checks for any pending interrupt signals between
each instruction.  If an interrupt is pending, the processor suspends what
it is doing and calls an {\bf interrupt handler} routine, such as a procedure
to read in the character when one has arrived at the keyboard.  When the
handler returns, the processor (usually) continues as if nothing had
happened.

Interrupts help the programmer by automatically {\bf polling} {\em in
hardware} if specific events have occurred, allowing more timely (faster)
interaction with the outside world.  However, their handlers must make
some change to the computer's environment to have an effect.  At certain
points, though, we don't want them to make any changes; for example, we
may not want to be interrupted while servicing an interrupt, nor would we
like to be interrupted when working on data an interrupt may modify.  In
other words, when working with a piece of data, we need to {\bf mask} or
{\bf block} all interrupts which may directly or indirectly modify that
data.  If we are only going to be working with the data a short time,
perhaps the safest and easiest strategy is just to block all interrupts.
This is what the {\em mpsig.h} code does by modifying the $IF flag$
(MS-DOS version) or calling the $setsigmask$ (UNIX version).  For
convenience (and to emphasize the temporary nature of signal blocking), I
have included a $mpsig\_critsect$ macro to disable interrupts around a
specified block of code.

\item[A Semaphore] As signals synchronize the processor with other
hardware, semaphores synchronize it with other processors.  A semaphore is
like a gate which will only let a certain number of people (processors)
through, usually just one.  We can limit the simultaneous access of
certain data or the simultaneous evaluation of certain code by
associating a semaphore with it and requiring each process claim the
semaphore before it proceeds, and release it when it's through.

Though a simple idea, implementing semaphores is somewhat tricky.  At some
point we must have some {\em indivisible} operation which either exchanges
data between a processor's local (register) memory and global shared
memory, or something which essentially increments or decrements the global
memory location.  Though the former is most efficient, the latter happens
to be available in ``C'' and takes no low-level assembly programming.  The
{\em mpsem.h} code attempts to accomplish this in ``C'' via the $++var$
pre-increment operator on a $volatile$ integer.  On most machines, this
should compile to a single machine instruction.  (The problem of this
scheme is that it requires to be efficient a back-off strategy (a delay)
when several processes are grabbing for the same semaphore (NOT IN CURRENT
IMPLEMENTATION)).  For convenience (and to emphasize the temporary nature
of signal blocking), I have included a $mpsig\_critsect$ macro to claim a
semaphore and (then) disable interrupts around a specified block of code.

\end{description}

These synchronization tools, signals and semaphores, are necessary to
build an efficient and correct multiprocessing scheduler.  However, they
are intended {\em only} for these low-level system utilities.  For
simplicity, instead of signals, higher-level {\em task} I/O should more
straight-forward constructs as {\em streams}.  And for efficiency, instead
of semaphores, higher-level {\em task} synchronization should use more
controllable constructs as {\em conditional waits}.  (More on a
nifty abstraction to implement these ideas in a subsequent article.)

\subsubsection{Switching Between Contexts:  $mpthd\_switch$}

Now that we've defined what a thread context is and how we can synchronize
its environment, we need a way to switch between contexts.  Fortunately,
``C'' provides a way to save and replace the current context using the
$setjmp$ and $longjmp$ commands.  By using the two in conjunction (see
{\em mpthd.c}), we can switch between threads quickly and portably.
However, a context switch must be one of those autonomous operations: we
cannot be interrupted right after we have saved the old context yet have
not yet jumped into the new.  Therefore, I protect the operation in a
$mpsem\_critsect$ (see code) to insure that interrupts are disabled and
the processor has control of a new context {\em before} releasing its old
one.  You will notice the call checks if new context to be switched to is
valid (detecting stack overflow) and if it is already the current context
(detouring self {\bf deadlock}).  But perhaps least conspicuous is
$mpthd\_switch$ return of the id of the previous thread; it {\em must} be
returned from a switch if it is ever to be obtained reliably, so it is
copied into $oldmpthd$ so the receiving thread can read it before it
restores its interrupt status.

Thus the $mpthd\_switch$ isolates and encapsulates the complications
of context switching into one safe and convenient procedure call.

\subsection{Creating and Destroying Contexts: $mpthd\_init$ and $mpthd\_dinit$}

All may sound fine and dandy, until we write a program and want to switch
to another thread.  What thread?  How do threads get started?  How do
threads get stopped?  We need a means of getting threads going.

Lubomir Bic\footnote{L. Bic et al, \underline{The Logical Design of
Operating Systems}, p. 21.} describes one functionally nice way to
initiate {\em parallel processes} using a $cobegin S_{0} | S_{1} |
... | S_{n} coend$ construct which executes $n$ segments $S_{i}$ of
sequential code in parallel.  However, this approach may require a
major modification in the syntax of ``C'' or a complex function call
with a variable number of arguments.  More importantly, the forced
nesting of the construct lacks the expressive power of other approaches...

A more general (but more complex) approach would be to use $fork$, $join$,
and $quit$ primitives.  In this interface, an execution flow may be
$fork$ed at a point in the code, or two or more flows later $join$ed;
superfluous flows can also be $quit$ (terminated).  UNIX provides a
variant on this interface with its $fork$, $wait$, and $exit$ primitives.
The UNIX $fork$ can appear anywhere in a block of code, and after the
$fork$, both processes have access to all local variables currently
defined.  This is done by making an almost exact copy of the process
dataspace (both stack and heap) into an identical but separate address
space.  This technique does an excellent job at protecting processes
from each other, but it makes shared memory extremely difficult, is slow,
and requires a lot of special hardware ({\bf virtual memory} support) not
usually found on personal computers.

For these reasons, I provide the primitive $mpthd\_init$ which simply
creates a thread data object (see {\em mpthd.c}) which the caller can
manipulate as data.  The $mpthd\_init$ function nor its corresponding
$mpthd\_dinit$ function neither start nor stop the thread.  But the caller
can, by explicitly switching to the new thread when appropriate.  In this
way the $mpthd\_switch$ routine, which suspends and resumes threads, is
also be used to start and stop them (indeed, there is no difference).

Now we've got threads going, but how {\em do we tell them what to do?
And how do we pass them arguments?} The UNIX $fork$ provides a
beautiful way to specify the starting point of for a newly $fork$ed
process (the point of fork), and allows the forking user to pass
arguments to the new process via local variables.  However, as
mentioned previously, that beauty has a high price: essentially all
data needs to be compiled with the help of extensive hardware support.
Even if we could afford the processing cost, there is no easy way to
emulate this on a personal computer as simply copied pointers will
point to their old dataspace.  So, keeping consistent
with ``C'', $mpthd\_init$ instead identifies the new code to be executed with
function pointer.  When the thread is invoked, it calls the function,
and as ``C'' is {\bf statically scoped} we need not worry about
duplicating local variables (a function cannot directly access
variables in higher scopes).  {\em But what do we do when the function
returns?} We simply require the function to return a new thread id
which we switch to when the function returns; and if the switch
returns, we just call the function again.  (Thus, in this special
thread function ($THDFN$), the return argument is quasi-equivalent to
its return address -- but, unlike normal function calls, this one
doesn't have to return.

{\em And what about arguments?}  We give each thread a little heap which lives
in the space leftover by its stack.  In this local heap, a creating
thread can store arguments for the new thread, and after a thread has
executed, it can leave arguments in its heap for other threads to read.
Admittedly, this technique is a bit awkward, but it is {\em a lot} more
efficient than copying the entire data space.

In the implementation of $mpthd\_init$, there are a few interesting things
to note.  Notice the caller must also specify the size of buffer
it intends to store the thread context in.  The first use of this
information is to figure out where to start the new stack, since on most
machines, the stack grows downward and must be started from the {\em top} of
the buffer.  But another use of this number is to see if the context will be
large enough for any thread to run;  as most personal computer operating
system calls use the caller's stack to do their work, a reasonable size
stack will be needed for even the simplest "Hello, World!" function.

And in the implementation of $mpthd\_dinit$, also notice that function
waits until the processor can temporarily claim the thread.  In other
words, it waits to be sure processor is executing the thread:  you don't
destroy the house while you (or someone else) is in it.

Finally, a last note about the interface of all the initialization and
deinitialization functions.  Notice they all take/return a pointer to a
buffer in which to store the structure, rather than dynamically allocate
the structure with, say, a $malloc$ command.  The reason is three fold:
decreased operating system/``C'' environment dependence; the caller may
want to do his own (perhaps static) allocation for speed, or want to
store the structure in his own field; and finally, dynamic memory
allocation is a {\em shared} resource, and we haven't gotten to the
proper management of shared resources yet (see upcoming articles).

\section{Putting the Context Switch to Good Use}

We've covered most of the important points in the design and
implementation of the thread cluster and associates.  However, nothing
compares to a few good examples of its use.

The context switcher presented here is robust.  It can be used in
explicit software calls and in hardware interrupt calls.  Thus, it is
applicable to both {\bf interprocess communication} and {\bf resource
management}...

\subsection{Software-Driven Switching $\Longleftarrow$ Interprocess Communication}

As an example, I constructed a simple ``C'' program which puts the
thread cluster to good use.  It creates three threads, all of which
evaluate the same thread function, but distinguish themselves by variables
stored on their local heap by their creator.  The three threads switch
between each other in a circular fashion, each printing out its name on
the screen when it is invoked.  Finally, one by one, the counter in each
of the threads expires, and the threads ``return'' back to the thread
which first ``called'' them until the main thread is reached and the
program terminates.  This program provides a simple example of threads in
action, and is a good thing to run to insure your installation of the
thread cluster is running properly.

As a more sophisticated example (and a suitable challenge for the video
game goer), the thread cluster could be used to set up a simple robot
video game.  In this game, each player can program his or her own robot as
an independent program (the only difference it's ``main'' procedure would
actually be a THDFN).  Each robot would call upon a set of shared library
functions ($bot_move$, $bot_seek$, $bot_shoot$, etc) to hunt down and try
to destroy other robots -- but meanwhile, the other robots will be trying
to do the same.

The trick is when a robot calls a library function,
before returning the function will call a simple {\bf scheduler} to switch
to another robot in a (transparent) round-robin fashion.  After each trip
around this {\bf circular queue} of robots, the scheduler would
temporarily switch to the real main thread of the robot game.  The real
main thread would look over the damage had been done: arbitrating
collisions, disposing of any
dead robots and expired missiles, moving the survivors along to where they
wanted to go, and redisplaying the battlefield.  If there are any robots
left, the main task could then switch back to the scheduler to begin
another round.

With multiple threads and context switching, the implementation of such a
game not be that difficult, as we could treat robots, missiles and
everything that moves on its own as an independent thread.  Thus robots
could shoot guided missiles with smart tracking programs.  And these
missiles themselves could shoot off more, smaller proj*.  Or, if you
really want to get sophisticated, ally 'bots could send homing birds
carrying messages of enemy movements!  It's exciting how a good
programming concept like context context switching can really spice up a
game.


\subsection{Hardware-Driven Switching $\Longleftarrow$ Resource Management}

You will notice that both examples given were self-contained.  Neither
interacted with the outside world, other than to display their status on
the screen.  However our context switch can be used for more than a
expressive programming abstraction for individuality and interprocess
communication.  Its real benefits come from increasing the efficiency of
programs, so they do not waste time waiting for I/O operations to complete
--which most programs spend most their time waiting for.  For example, the
context switch can be used to transfer data files between systems in the
background, only switching to the file transfer program when a character
has been received from the communications port.  Or they can be used for
more sophisticated optimizations: for example, when waiting for the user
to type a character, recomputing the values of a spreadsheet or saving the
files of a word processor.

These applications of {\bf background, interrupt-driven I/O} and, in
general, good {\bf resource management}.  Though they are beyond the scope
of this article, future articles built upon this context switch will cover
them and show you the magic you never thought your computer could do!


\section{Conclusions}

I have tried to take some of the mystery out of the magic.  I have led you
on an in depth exploration of one of the most fundamental aspects of
multiprocessing and multitasking, the context switching.  In our journey,
we have explored multiple contexts or threads of execution and programming
constructs for encapsulating the switching between these contexts.  In
implementing the switch, we have touched upon even the even more
fundamental notion of atomicity and found methods of synchronization, the
signal and the semaphore, we could use to achieve it.  And we have
returned from our journey with more than just memories but something
useful:  a thread cluster which we can incorporate in our own ``C''
programs.  So perhaps the next video game you play will not be
such a mystery after all...  {\em You} will have made up the magic!

{\bf Mike Parker}
\end{document}

