%****************************************************************************/
%* mptsk.tex -- EDUCATIONAL ARTICLE DESCRIBING THE MAILBOX MULTITASKER 	    */
%* Created:  see below		Release:  see below	Version:  see below */
%****************************************************************************
%(c) Copyright 1987, 1988 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:
% 
%
% 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\\
Portable Multitasking Environment\\
in ``C''}

\author{
Copyright \copyright 1988\thanks{
This is a beta release of an article intended for the July '88 issue
of BYTE Magazine.  Do not copy nor distribute.  Your thoughts and
suggestions appreciated.  (By the way, that thing up above is supposed 
to be a juggler!)}
 Michael Benjamin Parker, MIT '89 \\
|\\
East Campus - Mun. 303\\
3 Ames Street\\
Cambridge, MA\\
617-225-6303
}

\date{Created: 3/24/88 \\ Release: 0.7 \\ Version: 4/1/88}

\begin{document}
\maketitle
\begin{verbatim}

                                -O  
                             O      O
                               O-     
                           O    _    |  
                           |   / \   O
                              <^_^>     
                           X   \_/   X
                            \   U   /
                             \-----/    
                                U
                                U
                                ^
                              /   \
                            _/ the \_
                             mailbox
                           multitasker

\end{verbatim}

\newpage
\tableofcontents

\section{Goals of this Article}

{\bf Multitasking}, the ability to execute more than one task at once, is
becoming increasingly important in the small-system world.

A form of {\bf time sharing}, multitasking was originally invented in
the days of punched cards, when a computer was so expensive that it
was important to share it efficiently between many users.
Multitasking as a pursuit of resource efficiency has actually led to
new uses for computers (as E-mail), new approaches to them (as
interactive programming), and new ideas of their operation
(distributed processing).

Today, personal computers dominate the landscape.  They allow millions
of people to have their own computer at their fingertips.
Unfortunately, many of the great mainframe concepts for resource
management have been lost in this popularization of computers.  But,
as personal computers become more powerful and their users want to do
more with them, the concepts are being rediscovered.

The most notable rediscovery on today's PC scene is multitasking.  The
Terminate-but-Stay-Resident (TSR) utilities found on the IBM PC and
the Desk Accessories found on the Macintosh point to the need for
multitasking.  However, these are ``hacked'' solutions; the personal
computer industry, in its youth, lacks understanding of multitasking
issues.

Only recently have software and computer manufacturers started to
create multitasking environments for their users (as Apple's
Multifinder or, more notably, Microsoft's OS/2).  But unfortunately
for the user and software developer, these environments are still
highly machine and operating system dependent.\footnote{Though the
popular UNIX environment is fairly portable between workstation and
mainframe machines, it only provides multiprocessing, not multitasking
(or multiple threads within a process) which share memory}.

This article aims to help you explore and appreciate multitasking; it
also aims show you how to use multitasking to enhance your programs,
and to know its limitations.  Multitasking has much to offer to the
efficency, functionality, and modularity of your programs, but it is a
tradeoff of power for complexity.

This article is in two main sections.  The first section, {\em The
Dimensions of Concurrent Processing}, addresses the issue of
multitasking understanding; it is a brief tutorial of the concepts and
issues involved in multitasking, or more generally, concurrent
processing.  The second section, {\em The Mailbox Multitasker},
addresses the issue of multitasking portability; it presents a
general-purpose multitasker, written in `C', which is portable to most
stack-based machines and even many stack-based languages.  By
including this multitasker in your programs, you will not only give
them the efficiency, power, and conceptual simplicity of a
multitasking environment, but will be able to easily port them to new
environments.

\section{The Dimensions of Concurrent Processing}

\subsection{Why Process Concurrently?}

Multitasking is actually a form of {\bf Concurrent Processing}.
Normally when we write programs, we specify the exact order of
everything the computer does.  Often, however, the order is not
important and, indeed, irrelevant.  This especially true between
separate modules which do isolated tasks.  Concurrent Processing, then,
allows the computer to chose this order for us;  it relieves us of
having to specify this order and allows the computer to optimize
its processing according to the particular enviornment.

\begin{description}

	\item[Computer Chooses the Order...]  Concurrent processing
allows us to share and efficiently manage resources ({\bf multiplexing
a resource}).  For example, if a task wants to print a file and
another file is printing, the print manager insures they don't print
at the same time (controlled sharing); since the first task must wait,
the scheduler reuses the task's processor to run another task
(efficiency).

	\item[...So We Don't Have To.]  Another under-appreciated
benefit of concurrent processing is the power and conceptual
simplicity it brings to our programs.  We can think and reason about
parts of a program as separate tasks, modules of data AND control.
Within a task module, instructions happen sequentially, are strongly
synchronized and strongly determined.  Outside a task, instructions
happen in parallel, are loosely synchronized and loosely determined.
The strong control and data modularization concurrent processing
encourages allows complex programs to be broken down into models which
more resemble their real-world counter-parts.

	For example, a full-screen on-line text editor really has two tasks:
to modify the internal data structures according to the keyboard
input, and to display the internal data structures via the screen
output.  The first task essentially waits for the keyboard, and the
second waits for the screen.  With this shared-memory multitasking
model, the user never has to wait for the display.  More importantly,
the model is easily extended.  For example, adding more display tasks
can allow the same data to be displayed in different windows (or even
on different screens) without worry of updating each of these each
time a character is pressed.  Likewise, with some additional
synchronization, adding more keyboard tasks can allow the same data to
be edited simultaneously by several people (a multi-user
editor!).\footnote{Also, any program involving multiple machines must
enivitably deal with concurrent processing (tasks, the machines
operate independently) -- another reason to understand the concepts.}
\end{description}

In summary, concurrent processing is a powerful programming concept.
It not only allows us to use computers more efficiently, but lets them
become more representative models of our concurrent world.

\subsection{Tasks, Processors, and Context Switching}

In the heart of concurrent processing lie tasks, processors, and
context switching.  Any machine has a certain number of hardware {\bf
processors}, each of which is always processing instructions ({\bf
multiprocessing}).  However, with software, we can construct any
number of {\bf tasks}, or virtual processors ({\bf multitasking}).
Usually the higher the number of processors and tasks, the simpler
they tend to become, the distinguishing factor of {\bf fine- and
course-grain concurrent processing}.  As there are a limited number
of processors but possibly an unlimited number of tasks, a {\bf
scheduler} must switch a processor from one task to another, known as
{\bf context switching}.

\begin{figure}
\caption{Elements of Concurrent Processing}
\begin{verbatim}
                                     -T
                            CONCURRENT PROCESSING
                 -T               involves              -T  
                                                     
                  T-            T-      T-            T- 

           T    _        /      MULTITASKING    T       _     |
           |   / \     T             |           \     / \    T
              <^_^>                  V                <^_^>     
           S   \_/   S       CONTEXT SWITCHING     S   \_/   S
            \   P   /                ^                  P   /
             \-----/                 |               \-----/    
                P             MULTIPROCESSING           P
                P                                       P
                ^                                       ^
              /   \                                   /   \
            _/     \_                               _/     \_

\end{verbatim}
\end{figure}

\subsection{Internal \& External Synchronization}

If concurrent processes are going to constructively interact, they
must be able to synchronize with each other.  Process synchronization
takes place on two levels: internally (between processors) using {\bf
semaphores} and externally (between a processor and external
hardware) using {\bf interrupts} or {\bf polling}.

A semaphore is a processor synchronization device used for limiting
the number of processors which access certain data simultaneously.
Normally only one processor is allowed to access the data at any given
time.  The semaphore is implemented as a mutually agreed upon bit in
the computer's memory.  When a processor wants to {\bf claim} or {\bf
wait for} the semaphore, it both tests and sets the bit in one {\bf
atomic} operation, usually implemented as a single machine instruction
so that it can't be interrupted\footnote{Though Dijkstra's algorithm
and Dekker's version of it can enable semaphores to be implemented
purely in software.  Other solutions exist as well}.  If (and only if
the bit) was already set, then the processor waits until it is
cleared.  (The bit signifies that the data the semaphore represents is
in use.)  Out of courtesy, a processor must likewise clear the bit
when it is through, to {\bf release} the semaphore and {\bf signal}
any waiting processors.

Semaphores provide the necessary processor synchronization but are
fairly primitive.  With them, higher-level control structures be
built.  The {\bf monitor}, for example, monitors data by limiting its
access to a set of procedures, only one of which can run at any given
time.


Interrupts and polling, on the other hand, allow a processor to
synchronize itself with its external hardware devices.  To synchronize,
a processor may poll its devices, waiting for them to reach a certain
state (as ``ready to receive data'').  The advantage of polling is
that the
processor may wait for any set of conditions of its choosing.  The
disadvantage, of course, is the processor may waste a lot of time
polling, and must remember to poll amid is regular processing.  For
this reason, most processors have built into them circuitry for
automatically polling a set of hardware interrupts between each of
their instructions.  When an interrupt is signaled, the current
process is {\em interrupted} and an {\bf interrupt handler} routine
is run to handle the interrupt.  Complications set in when the 
interrupt handler itself is interrupted, and most processors allow
interrupts to be disabled or prioritized.

\begin{figure}
\caption{Internal and External Processor Syncronization Devices}
\begin{verbatim}

                            EXTERNAL  HARDWARE
        /=============------------------------------============\
        U COMPUTER       i                      i               U
        U                n                      n               U
        U                t                      t               U
        U                e                      e               U
        U                r                      r               U
        U                r                      r               U
        U                u                      u               U
        U                p                      p               U
        U                t                      t               U
        U                s                      s               U
        U                |                      |               U
        U                V                      V               U
        U         /---------\                /---------\        U
        U         |PROCESSOR| <-semaphores-> |PROCESSOR|        U
        U         \---------/                \---------/        U
        U                                                       U
        \=======================================================/
\end{verbatim}
\end{figure}

As semaphores are systematically claimed and released, so are
interrupts disabled and enabled.  When accessing data, a process must
disable all interrupts which may also modify the data.  For this
reason, you'll typically, you'll typically hear the buzz words:
{\bf non-pre-emptive} code (not interruptable while executing) and
{\bf non-re-entrant} functions (not recallable while evaluating).

\subsection{Protocols of Communication}

With synchronization, communication is possible.  Communication is a
big, big issue in computer science.  Over the past decade or so, with
the growth of operating system technology, the focus has been on
communications within the computer.  Now, with great interest in
network technology, that interest has broadened to communication
between computers.  To introduce the subject, I will focus on the
communication types within a computer.  To communicate, it is critical to agree on a
protocol.  Here are several to choose:

\begin{description}

	\item[Shared Memory] is the most general form of interprocess
communication.  Two processes share an address space, a common
``blackboard'' to communicate.  There is ``in-transit'' state for
information and communication is simple and instantaneous.  However
this flexibility is shared memory's pitfall.  With so few constraints
on the shared access to data, it is easy to err and corrupt it.  What's more,
information may flow anywhere and {\bf protection} is difficult to
enforce.  Finally, it is not easy to extend the shared memory
abstraction to situations where the information communicated is
larger than memory, or, worse, between machines.

	\item[Message Passing] provides a little more control.  Processes
communicate by passing messages to one another.  The messages are
just records of bytes, and within a single machine, communication can
can be nearly as fast as shared memory because the message data need
not be copied.  But, because communication is divided into logical
units, the message passing abstraction can extend to communication
between machines with no modification to its interface.  Several
flavors of message passing are available.  In the most general form,
messages can be sent and received from any number of independent {\bf
mailboxes}, separate from the processes.  In distributed systems, due
to communication costs, {\bf ports} are often implemented instead.
Unlike a mailbox, a port is associated with a specific process.  Any
process can send messages to a process' ports, but only that process
can receive from it.

	\item[Remote Procedure Calls] are a form of message passing
particularly suited for distributed systems.  A seemingly normal
procedure call is actually invoked on another machine.  RPC's are a
form of {\bf synchronous} message passing, as the caller is suspended
while his function evaluates.  Nevertheless, because of the familiar
``procedure'' packaging, RPC's are becoming increasingly popular and
allow distributed programs to be quickly built.

	\item[Pipes] provide a still more restrictive interface.
Popularized by the UNIX operating system, pipes provide a one- or
two-way {\bf byte stream} between two processes.  Unlike message
systems, pipes are point-to-point established connections.  Connection
setup and the copying of data through the pipe add to the pipe
protocol's cost.  What's more, data must be formatted into a stream of
bytes on the transmitting end, and then reformatted into usable data
on the receiving end.  Yet these very restrictions have encouraged a
uniform interchangeable interface for programs, a prized aspect of the
UNIX operating system.

\end{description}


\subsection{Resource Management}

It is not enough to just to exchange resources and information.  A
concurrent environment must manage its resources.  As true with most
management science, there are few agreed-upon best methods.  However,
all processes must agree upon {\em a} method for managing resources.
{\bf Deadlock} is a typical problem in resource management, when,
simultaneously, a set of processes each try claim resources that
another one of them owns.  Another more subtle problem is {\bf
Livelock};  here deadlock is broken, but when the processes retries
the situation occurs again and again.  Another similar and subtle
situation is process {\bf starvation}; for example when the readers of
a file come and go so frequently that a writer process can never
write.  Here are some typical resources, and how they may be managed:

\begin{description}

	\item[Processor] management is the most fundamental part of a
multitasking environment.  Processors must be dynamically allocated to
different tasks.  Usually this is done by a separate task called a
{\bf scheduler}.  The simplest scheme is {\bf round-robbin}
scheduling, circling through each task, executing it for only a unit
of time (a {\bf time quanta}) or until it reliquishes control.
Usually, however, this scheme is not adequate.  Suppose a task is
simply idle waiting for a keystroke?  Or suppose a task is
time-critical, and must receive a character from a serial port.  Real
schedulers must suspend when they are awaiting resources \& messages and
must prioritize tasks according to their timeliness.  Also, they must take into
consideration how long the task has had to execute, and how frequently
it has executed, to see each task gets its fair share.  In addition, a
scheduler may consider the task's history (big task, small task; CPU
bound, I/O bound).  And as the scheduler grows more complex, the
designer must even consider how much time {\em the scheduler} making a
decision.  In short, good scheduler design is complex;  it requires
understanding, experience, and a touch of black magic.

	\item[Random Access Memory] is a resource and is usually intimately
tied with multitasking environment.  Often, especially in stack-based
languages, this resource is taken for granted; the program
dynamically allocates stack and heap memory as needed.  However, a
multitasker cannot make such assumptions; dynamic memory allocation
takes time and resources too costly for its time-critical primitive
functions.  Most often, a multitasker's memory management is tightly
designed around the hardware's capabilities.  For example, many
workstation and larger environments have {\bf virtual memory},
allowing each process a contiguous address space which is much larger
than physical memory, by swapping in memory from secondary storage as
it is accessed.  

	\item[Secondary Storage Devices] are next in line in a multitasker's
complex management scheme.  As well as its use for virtual memory
{\bf page swapping}, hard disks and tapes often contain an intricate
file system which the operating system must manage.  To support 
complex, multi-user database applications, operating systems often provide
{\bf locking} on the file level, or even on records within the file.
And in optimized systems, the pending disk accesses of multiple tasks
may be organized according to the head position of the disk.


	\item[Network Devices] are now playing an increasing role in operating
systems,  to the point to where nearly half the operating system may
be dedicated to network communications! (as is the case with some of
the networked versions of UNIX).  Often a single network connection
is {\bf multiplexed} between several processes, and the operating
system will emulate its interprocess communication protocol (as
pipes) over the network between processes on different machines.

	\item[User Devices] are beginning to be multiplexed as well.  On
graphics terminals, often a window is dedicated to each
process.  Standards, as Microsoft's Presentation Manager, are
emerging which allow a consistent multitasking interface to text and
graphics functions.  Some standards, as the Sun NeWS system and the
MIT X Window system, allow text and graphics to be displayed on
remote machines.

\end{description}

In short, resource management plays a very large part in a
multitasking system, and the technology is still under development.


\section{The Mailbox Multitasker}

The Mailbox Multitasker is {\em portable} multitasking environment
written in ``C''.  The package, which may be uploaded from BIX,
serves both as an educational illustration of how a multitasker can
be can be built, and as a productivity tool which you may incorporate in
your own programs and modify to suit your needs.  With the Mailbox
Multitasker you may write multitasking programs which are {\bf
portable} to many different machines and operating systems.  What is
more, should the machine have {\em multiple processors}, your program can
take advantage of them and may run significantly faster.

\subsection{Mailbox vs. The Typical Multitasker}

Mailbox is a multitasking environment written to encourage
exploration and applications in concurrent processing.
Unfortunately, multitasking is usually not available to the personal
computer user, as most personal computer operating systems only
represent a subset of many mainframe functions.  It must be made
clear, however, that Mailbox is multitasking environment, {\em not
an operating system}.  It does not provide file-, memory-, and other
resource management functions required of a complete operating
system.  However, it does provide a multitasking {\em environment}
{\em within a program} that you write with it.  And because the code
for Mailbox is easily ported and its interface is the same on all
machines, your own multitasking code can also be portable.

Traditionally, multitasking, when available, has been a function of
the operating system and usually machine specific.  The Macintosh
Multifinder provides limited multitasking support, but its programs
which use it will be limited to the Macintosh.  Microsoft's OS/2,
when it is released, promises an impressive library of multitasking
functions, but OS/2 is highly IBM AT specific.  Though UNIX does
provide portable multi{\em processing}, the operating system is still
usually found only on workstations and mainframes, and its common BSD
distribution processes are big and ``expensive'' and cannot share
memory.

\subsection{Mailbox's Layers of Portability}

The Mailbox package is built on three {\em layers of portability}.
Each layer adds a certain degree of functionality and machine
independence.  The lowest and most device-dependent layer, MPTHD,
implements the basic context switching required for any multitasking
package; it provides threads of execution.  The middle layer, MPTSK,
implements scheduling and interprocess communication, non-preemptive
multitasking based on MPTHD's; it provides independent, communicating
tasks.\footnote{All global names in the Mailbox package are prefexed
with the authors initials (MP) to prevent naming conflicts with other
global names your enviornment may have.}  The top layer, MPRES,
implements basic resource management for all standard resources and
those you may add, preemptive multitasking based on MPTSK's.

\begin{figure}
\caption{Mailbox's Portability/Functionality Layers}

\begin{description}

	\item[MPRES]	{\em Resource Management}\
		Pre-emptive concurrent processing; regulated access
to the basic resources, with provisions for sophisticated user
resources, resource mangers, and optimizations.

	\item[MPTSK]	{\em Task Organization}\
		Prioritized multiprocessor scheduling and ``mailbox''
message-passing, with provisions for user schedulers and
communication protocols.

	\item[MPTHD]	{\em Context Switching}\
		Independent threads of execution and simple
multiprocessor context switching.
\end{description}
\end{figure}

Since each layer depends only on the layer below it, you may
incorporate only the layers necessary to suit your needs.  The
remainder of this section discusses each of them in detail.

\subsection{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 {\em any} active call of $mpthd\_switch()$.  You specify as an
argument the thread you want it to return to, and returns from {\em
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).


\begin{figure}
\caption{MPTHD: Context Switching Illustration}
\begin{verbatim}

        Thread A                  Control Flow          Thread B
        --------                                        --------
           :                    V                          :
           :                    |                          :
        printf("Hello, ");      |                       printf("Welcome!");
                                |               
        mpthd_switch(A);        \------->-------\       mpthd_switch(X);
                                                |  
        printf("Goodbye!");                     |       printf("there!");
          :                                     |          :
          :                                     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 {\em 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).

\begin{figure}
\caption{MPTHD:  Thread Datatype Internals}

\begin{verbatim}

    Semaphore (to control multiprocessor access to the thread)
     \
      \                    Byte Flag (for detecting stack overflow and
       \                    \         thread corruption)
        \                    \
         \                    \                     Stack (for local variables
          \                    \                           & function calls)
           \                    \                                     \
MPTHDID  /--\--------------------\-------------------------/ /---------\-----\
-------  |   V   |             |  V  |       ||        /          \     V    |
thread-->| mpsem | "C" jmp_buf |  0  | heap- || heap   \==>    <==/    stack |
pointer  |       |  ^          |     | size  ||   ^    /          \          |
         \---------/-----------------------------/---------/ /---------------/
                  /                             /
                 /                             heap (for storing inherited
                /                                    defaults & passing args)
               /
              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 {\em offset} into the {\em current thread's}
heap, containing our default buffer size.  That way, each task has
its own defaults, but refer to them with the {\em 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 {\em
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!

\subsection{MPTSK:  The Task Organization Layer}

It is nice to be able to switch contexts whenever we choose, but we
may desire more.  Suppose, for instance, we get to a point in our
program where we must wait for, say, keyboard input.  Which thread do
we switch to?  Or suppose we want to send a message to another
thread, say, telling the thread it's printout has finished?  How do
we pass the thread the message?  What if the thread is busy?

The MPTSK cluster answers these questions by providing a
general-purpose, integrated scheduler and message passing system
based on mailboxes (from which the package gets its name).
Essentially, MPTSK organizes threads into a powerful (multi)task
force!

The MPTSK cluster introduces three new datatypes: tasks (MPTSK),
messages (MPMSG), and mailboxes  (MPBOX).

Tasks essentially enhanced threads.  They are automatically scheduled
and need not be explicitly switched between.  They can also send and
receive messages...

Messages can be any recordtype for maximum flexibility.  The
structure need only begin with an MPMSG field (for internal message
management purposes).  Indeed, even tasks and mailboxes are treated
as messages...

Mailboxes are the thing which ties tasks and messages together, and
makes Mailbox Multitasking work.  A hybrid of the queue data
structure, a mailbox {\em either} contains a list of messages {\em
or} a list of tasks (waiting for messages).  (See figure)

\begin{figure}
\caption{MPTSK:  Mailbox ``Message Bank'' Illustration}
\begin{verbatim}

                        Messages        Mailbox         Tasks
                        --------        -------         -----
                                           _
            A Mailbox|                    / \
with Messages Waiting|  M----M----M------< 3 >
            for Tasks|                    \_/
                                           _
            A Mailbox|                    / \
   with Tasks Waiting|                   <-2 >--------T----T
         for Messages|                    \_/


\end{verbatim}

{\em A mailbox is a task/message bank account.  A message is queued
until a task receives it.  A task is queued until a message reaches
it.}
\end{figure}

Tasks may either send or receive messages on a mailbox.  If a task
sends a message and there are no tasks waiting for it, then the tasks
adds the message to the end of waiting messages; if there are tasks
waiting, then the task gives the message to the first task in line.
On the other hand, if a task attempts to receive a message from a
mailbox, and there are no messages waiting, then the task adds itself
to the end of waiting tasks;  if there are messages waiting, then
the task takes the message and proceeds.



Think of a mailbox like a bank account and messages like money.  Like
a bank account, a mailbox has either a credit or deficit of
messages.  And like a bank account, messages can be deposited or
withdrawn.  This is a mailbox.

Of course, when people (tasks) come to the bank, they must wait in
line.  Likewise a mailbox services its tasks and messages in a
first-come, first-serve order.  This is a mailbox.

Though a simple concept, the MPBOX's mailbox turns out to be a
remarkably versatile structure.  It is used not only for inter-task
communication, but also for scheduling, resource-management, even
message-passing super-duper semaphores.  For instance, suppose we
view three messages waiting on the $printers$ mailbox as representing
the computer's three printers.  When a task wants a printer, it
simply receives from the $printers$ mailbox.  The message it gets
tells it which printer it got.  And if there are no printers
available, the task is queued waiting for the printer in logical
first-come, first-serve order; when a printer is available, the task
will automatically be restarted.  And since this FIFO ordering is
holds for messages as well, the least-recently-used printer will
always be chosen, insuring the three printers are evenly used.

If a processor is also thought of as a resource (which it is), the
mailbox abstraction makes a good scheduler.  We imagine a $schedule$
mailbox, with tasks waiting to ``receive'' a processor to run
them.\footnote{Of course, a processor need not be represented by a
real message.  But, for the moment, suppose it were, and when no
tasks were needed to be run, the processor waited on the schedule
mailbox like a message.  The processor would have to disable
interrupts during this period, as it would not be running any task,
under which it could save its state if it were interrupted.  If it
were the only processor, then no tasks would ever appear for it to
run.  Therefore, it is far better to quickly find {\em any} task to
run, even if it is an {\bf idle task}, which enables interrupts and
yields itself to higher priority tasks.}  Again, due to the FIFO
ordering, tasks are automatically processed in a round-robin fashion.
For more advanced, {\bf prioritized} scheduling, we assign a priority
to a task by assigning a mailbox on which to schedule it whenever it
can be run.  We list these schedule mailboxes in order of priority.
Whenever we need to run a task, we search this (short) list
sequentially until the first (highest priority) task is found
(see figure).

\begin{figure}
\caption{MPTSK:  A Mailbox Scheduler Example}
\begin{verbatim}

                                Priority
        Priority Level          Schedule        Tasks Waiting to be Run
        --------------          --------        -----------------------
                                   |
                                   V
                                  / \
        "I/O Tasks"              <-1 >----------T
                                  \_/
                                   |
                                  / \
        "User Tasks"             <-4 >----------T----T----T----T
                                  \_/
                                   |
                                  / \
        "Background Tasks"       <-1 >----------T
                                  \_/
                                   |
                                  / \
        "Idle Tasks"             <-3 >----------T----T----T
                                  \_/
                                   *

\end{verbatim}

{\em To find a new task to run, a processor simply searches down the schedule
list until it finds a task.}

\end{figure}

A key advantage to mailbox multitasking is speed.  Many multitasking
systems have a single kernel task which schedules all processes and
manages all resources.  Therefore, to switch between tasks, and even
to send a message, requires at least two context switches (into and
out of the kernel).  Mailbox requires no or at most one context
switch to send a message, and only one to switch between tasks.  This
is because it does these kernel functions simply and within the
current task.  It achieves efficiency at the cost of some inter-task
protection (which is acceptable since all the memory is shared
anyway).

Also, usually only one processor is allowed to execute inside the
kernel at once.  Thus the kernel scheduler itself becomes the
bottleneck as more processors are added, and for this reason it is
unusual to find a shared-memory machine with more than half-a-dozen
processors.  Likewise, a mailbox can only be opened by one processor.
But Mailbox Multitasking distributes message passing and scheduling
between multiple mailboxes; and a processor can only open one mailbox
at a time, and only momentarily.  Though its scheduling algorithm is
simple, it is {\em fast} and potentially {\em independent} of the
number of processors.  For this reason, Mailbox should be able to
take great advantage of multiprocessing machines.

\begin{figure}
\caption{MPTSK: Message, Task, and Mailbox Datatype Internals}
\begin{verbatim}

          Message Header (for message management)
           \ 
MPMSGID  /--\------------------------------------/ /---\
-------  |   V   |                                     |
message->| mpmsg | - YOUR RECORD STRUCTURE HERE -      |
pointer  |       |  ^                                  |
         \---------/----------------------------/ /----/
                  /
                 Any Record Structure of Any Size (the message)

------------------------------------------------------------------------------

      Message Header (for message management)
       \        
        \               Schedule Mailbox (on which to wait for a processor)
         \               \
          \               \              Mailbox on which the Task Waits
           \               \              \ (or nil iff running)
MPTSKID  /--\---------------\--------------\-----------------\
-------  |   V   |       |   V   |       |  V         |      |
task---->| mpmsg | mpthd | sched | mpbox | waitingfor | owns |
pointer  |       |  ^    |       |   ^   |            |  ^   |
         \---------/----------------/-------------------/----/
                  /                /            Resource Sources
                 /                /              which the Task Owns    
                /                /
               /                Private Mailbox (for "personal" messages)
              /
             Thread (for storing the task's state and heap)

( The last three fields are maintained but not used by Mailbox.  Rather,
  they are there to suggest possible usages for the system.)

------------------------------------------------------------------------------

        Message Header (for message management)
         \      
          \               Message Count (if negative, waiting task count)
           \               \ 
MPBOXID  /--\---------------\------------\
-------  |   V   |       |   V    |      |
mailbox->| mpmsg | mpsem | msgcnt | msgs |
pointer  |       |  ^    |        |  ^   |
         \---------/----------------/----/
                  /                / 
                 /                A Circular Queue of Messages
                /
               Semaphore (to control multiprocessor access to the mailbox)
\end{verbatim}
\end{figure}


An apparent disadvantage of Mailbox Multitasking is that it does not
come with functions to allow one task to force another to stop or
suspend, a feature common in other multitaskers.  But this is  because
Mailbox has been designed to also work in multiprocessor
environments, where the scheduler cannot automatically assume the other
tasks are suspended while it executes a task.  Though I do not have
a multiprocessor machine at my disposal, I designed Mailbox to take
advantage of multiprocessing environments should they become
available, and to better understand issues involved in real
concurrent environments.

Actually, Mailbox is easily extended to support sophisticated task
control operations due to another feature, its uniformity.
Everything, even scheduling, works by sending and receiving messages.
More sophisticated operations follow logically and do not need to be
tailored.  For example, to {\bf yield} the current task so other
tasks can run (useful when polling some condition), the task merely
attempts to ``receive'' a processor ``resource'' from its schedule
mailbox.  It is also possible for a task to specify which tasks
(which schedule list) it wants to yield to.  Thus, when optimizing
performance, a task can implement its own scheduler and ``break'' the
strict priority scheduling.  Or, for modular programming, a task can
duplicate it:  a task can multitask itself!

Even the send and receive ``primitives'' are special instances of a
general $mptsk\_xfer()$ function, with flexibility akin to the
$mpthd\_switch()$.  Because all task switching and message passing is
through a single function interface, any sort of message monitoring,
performance monitoring, or task control is possible, simply by
patching the desired code into this function.  As we will see more of
in the next subsection, instead of being big and complicated with every
possible feature, Mailbox is simple, so the programmer can quickly
tailor her own.

In short, the MPTSK implements prioritized multiprocessor scheduling
and simple ``mailbox'' message-passing, based on threads.  It
introduces the message, task, and mailbox datatypes and a simple set of
operations, with which many sophisticated scheduling, communication,
and monitoring environments can be easily built.

\subsection{MPRES:  The Resource Management Layer}

Still, the MPTSK layer only takes into account task's interaction
with themselves, not with the outside world.  The system will have no
problems until two (or more) tasks want to use the same resource at
the same time.  A final layer, MPRES, is need to share resources.

The MPRES layer is best viewed as an open-ended extension of the
MPTSK environment.  Unfortunately, only basic resource management
(regulated access) can be defined in a portable fashion (short of
writing an entire operating system).  Though all machines have
processors and memory, they vary widely in their devices.  Support
for a default set of resource types is provided.  For other, more
esoteric devices, the layer shows how the user can build resource
managers tailored to his environment.

\subsubsection{Contention Management}

MPRES introduces the resource and source datatypes.  The resource is
merely a mailbox datatype, used for storing the available sources of the
resource as messages.  The source datatype is a message with two extra
fields.  The first specifies the task which owns the source (or NIL if
none) and the second is a double-pointer structure (same as the
$mpmsg$ header) which keeps all the sources of a resource in a ring.
Operations are provided to take ($mpres\_take()$) and give or release
($mpres\_recv()$) a source of a resource; they are implemented directly
with $mptsk\_send()$ and $mptsk\_recv()$.  Additional operations are
provided to initialize a resource of a particular type, and to
deinitialize it (see MAN page for exact details).


\begin{figure}
\caption{MPRES: Resource Datatype Internals}

\begin{verbatim}

       Message Header (for message management)
        \       
         \               Ring of all the Sources of a Resource 
          \               \ (optional - for locating resources)
           \               \ 
MPSORID  /--\---------------\---------------------------------------\ \------\
-------  |   V   |       |   V   |                                           |
resource>| mpmsg | mptsk | mpres | - RESOURCE ID and CHARACTERISTICS -       |
pointer  |       |  ^    |       |    ^                                      |
         \---------/----------------/-------------------------------\ \------/
                  /                / 
                 /                Details Particular to this Resource Source
                /
               Task (if any) which Owns the Resource

\end{verbatim}

\end{figure}

The two fields allow all sources (and users) of a resource to be
located.  Though this feature is not taken advantage of, it could be
useful for reclaiming resources from crashed or discourteous tasks.
By incorporating the knowledge gained from the waitingfor and owns
field of tasks, its also possible to detect deadlock (a cycle of
tasks waiting endlessly for each other) before it occurs; when a task
is about to be suspended waitingfor a resource, it first checks if
any other tasks which have the resource are directly or indirectly
already waitingfor it.  Because this check potentially involves a
great deal of searching for every access to a resource, it is not
implemented, but could be, if deadlock is a serious problem.
(Nevertheless, users of Mailbox should beware of the base case of
deadlock, where a task requests a resource that it already has.)

The MPRES layer defines a few general resources.  The most universal
resource is $mpres\_memory$.  With memory contention management, we
can finally write a one-argument $mpthd\_init()$:

\begin{verbatim}

MPTHDID mpthd_create(MPTHDFN mpthdfn)
{
        int     mydeftasksize=  mpthd_mydef(mpdef_tasksize,int);
        MPTHDID mpthd;

        mpres_take(mpres_memory);               /* CLAIM MEMORY RESOURCE */
        mpthd=  (MPTHDID)malloc(mydeftasksize);
        mpres_give(mpres_memory);               /* RELEASE MEMORY RESOURCE */

        if (mpthd)      mpthd_init(mpthd,mydeftasksize,mpthdfn);
        return(mpthd);
}
\end{verbatim}

Notice how the resource must be claimed and released around the
standard $malloc$ memory allocation call.  This insures no other task
can allocate memory at the same time.  Likewise protection must be
taken around the $free$ memory deallocation call and other memory
management calls.  In general, {\em every ``C'' function which
accesses resources must be executed within an appropriate resource
lock.} This is true for any concurrent system.  To make the job
easier, the MPRES package defines a macro which takes as arguments a
resource and a block of code; it claims the resource, executes the
code, then (remembers to) free the resource before exiting.  MPRES
also duplicates many of the common ``C'' function calls with this
extra locking added (eg, $mpres\_malloc()$).  Operations such as
$malloc()$, which are completed in a single transaction, are well
suited for this; in contrast, operations as $printf$ usually require
several calls (``or the'' ``Hello'' ``output may not stick''
``Goodbye'' ``together''), and are best locked explicitly by the
caller.  Explicit locking is also necessary when calling (library)
functions which use resources and are unaware they are executing in a
concurrent environment.

One way to simplify the complexities of having to lock and unlock
resources is to assume a uniprocessor environment (often the case)
and have tasks only yield control explicitly, when they are not
holding resources.  This may be an acceptable compromise in many
circumstances, and Mailbox allows for this style of programming.

MPRES also provides three levels of I/O {\bf locking granularity}.
On the high stream level are the standard streams: $mpres\_stdin$,
$mpres\_stdout$, and $mpres\_stderr$.  On the middle component level
are standard operating system components: $mpres\_filesystem$,
$mpres\_network$, $mpres\_terminalin$ and $mpres\_terminalout$.  And on
the low device level are standard devices: $mpres\_harddisk$,
$mpres\_floppydisk$, $mpres\_modem$, $mpres\_printer$, $mpres\_parallel$,
and $mpres\_serial$.  Locking at a lower granularity level allows for
higher degree of concurrency at a cost of complexity and portability.
These locking levels are likely to be incomplete and to overlap; more
than anything else, they are merely suggested names for resources and
their locks.  It is up to the programmer to tailor the locking
appropriate to his environment and task.

\subsubsection{Pre-emptive Multitasking}

One optimization the programmer may want to do is tap into the power
of the hardware and operating system interrupts.  The MPTHD and MPTSK
layers have been carefully designed so their functions can also be
called from interrupt handlers with no modifications.  For example,
by adding this Turbo "C" code, the package becomes a {\em
pre-emptive} multitasker:

\begin{verbatim}

void interrupt  (* mpsig_oldclocktick)();       /* SAVE OLD CLOCK TICK INT */

void interrupt  mpsig_clocktick()
        {
                mpsig_oldclocktick();
                mptsk_yield();
        }

#define MPSIG_CLOCKTICK         (0x08)          /* INTERRUPT 0x08 ON IBM PC */

void    mpres_setup()
{
        ....
        mpsig_oldclocktick=     getvect(MPSIG_CLOCKTICK);
                                setvect(MPSIG_CLOCKTICK,mpsig_clocktick);
        ....
}

\end{verbatim}

Now 18.2 times a second (the frequency of the IBM PC clock), the current
task is yielded if other tasks are waiting to run.  A similar effect
can be achieved in UNIX using the alarm signal.


\subsubsection{Other Interrupt-Based Optimizations}

In general, Mailbox can be tailored to take advantage of most any
interrupt-driven resource.  For example, personal computers waste
most of their processing power waiting for keystrokes.  Suppose we
wanted to suspend tasks waiting for keyboard I/O, without modifying
standard functions, like $scanf()$, which may access the keyboard.
On the IBM PC, the keyboard is typically read through a ROM BIOS
software interrupts.  Also, the keyboard generates a hardware
interrupt each time a key is pressed.  By intercepting requests to
read the keyboard, and signaling when a key is available (see
figure), it is possible to put this idle time to more productive uses
-- like saving your work!

\begin{figure}
\caption{MPRES: Intercepting Interrupts ({\em Advanced
Optimizations})}
\begin{verbatim}

        IBM PC INTERRUPT                IBM PC ROM BIOS
          VECTOR TABLE
                                        
        Int #   Hndlr Addr              BIOS Routines
        -----   /-------\               /-------------------------\
Hard-     :     |       |               |                         |
ware    0x08:   |   ----+-------------->| Clock Tick              |
ints    0x09:   |   ----+--\  /-------->| Key Stroke              |
-------   :     |       |  |  |         |                         |
Soft-   0x14:   |   ----+--|--|-------->| Read/Write Serial Ports |
ware    0x15:   |   ----+--|--|-------->| Read/Write Cassette     |
ints    0x16:   |   ----+--|--|---\  /->| Read Keyboard           |
        0x17:   |   ----+--|--|---|--|->| Write Printer           |
         :      |       |  |  |   |  |  |
                \-------/  |  |   |  |  \-------------------------/
                           |  |   |  \------------------------\
                    /------/  |   \-----------\               |
                    V         |               V               |
Patch   /------------------\  |         /-------------------\ |
Routines| call bios routine---/     /----receive key ready  | |
        |                  |        |   | message (if any)  | |
        | send message to ----\     |   |                   | |
        | key_ready mailbox|  |     |   | call bios routine---/
        \------------------/  |     |   \-------------------/
                              |     |
                              \  _  /
                                / \  
key_ready mailbox:             <k_r>
                                \_/
\end{verbatim}

{\em To prevent tasks from wasting processor time waiting for
keystrokes, we can intercept the IBM PC's BIOS interrupt routines, to
check and signal when a keystroke is available.  Because Mailbox's send
and receive primitives are callable for interrupts, many such schedule
optimizations are possible without rewriting the scheduler. }

\end{figure}

A similar trick can be done in UNIX with the $signal(3C)$ and
$fcntl(2)$.  The calling task must explicitly wait for a mailbox,
associated with a particular stream, if an I/O operation on the
stream $EWOULDBLOCK$; in turn, a signal handler for $SIGIO$ would
restart the task by sending it a message that the stream was ready.

Likewise optimizations could be made for the other computer
resources.

In short, resource management is a difficult issue.  Since computer
devices differ and most languages several have wired-in I/O calls,
{\em portable} resource management is nearly impossible, short of
writing another operating system.  Mailbox provides portable
processor (pre-emptive multitasking), memory (dynamic allocation)
resource management, and contention management for many standard
resources.  Beyond this, the programmer is encouraged to tailor
Mailbox to her particular resource needs.


\section{Thinking Concurrently}

We have covered a lot of ground.  We have laid out the dimensions of
concurrent processing, and we have seen how an actual {\em portable}
multitasker is built, and the many issues involved.  Now the challenge is
{\em thinking concurrently}!  (see figure for a few rules of thumb)

\begin{figure}
\caption{Thinking Concurrently -- A Few Rules of Thumb}

\begin{verbatim}

                Rules of Thumb for Concurrent Processing
                ========================================

        1.      Divide Problems into Modular Tasks,
                units of highly-coupled data and control.

        2.      Know The Order In Which Things Must Happen,
                and in which they could be allowed to happen.

        3. ==>  Know Which Objects Are Shared,
                and which objects are local.

        4.      Synchronize Access To All Shared Objects.

        5.      Know The Unit of Transaction, what operations
                should be atomic, when they should commit.

        Modular and object-oriented programming styles are
        also helpful for reasoning about concurrent systems.

\end{verbatim}

\end{figure}


Concurrency buys us modularization, the ability to divide our
programs into their logical ``tasks'' -- in the full sense of the
word.  It also buys us performance.  But the price is high.  We must
face complex issues of managing resources and insuring data
integrity.  A big problem with concurrent systems, especially
distributed systems, is ``getting them right.''  The concurrency
issues introduced in this article are just the tip of the iceberg of
big current fields of research.  For example, Transaction Management.

\begin{figure}
\caption{Table of Commercial Multitaskers}
\begin{verbatim}
                Commercial PC and Workstation Multitaskers
                ==========================================

Multitasker     Type    Price   Machs   Op.Sys. Langs.  AB CDE FGH IJKL MNOP
-----------     ----    -----   -----   -----   ------  -- --- --- ---- ----
DesqView 2.0    AppInt  $330/   PC,AT   MS-DOS  "C",    #- ### ##- #-## --#-
Quarterdeck Sys.         n/a    PS/2            others

Mailbox 1.0     PgmEnv  $35/    IBM,DEC MS-DOS, "C",    #- #+- ### +##+ ####
M.B.Parker              free    Apple,  UNIX    others
                                 ( user portable )
Multifinder     AppInt  $15/    Mac     Mac     n/a     #- #-- ?-- ?--? ----
Apple Computer          n/a     

OS/2 (beta rel) OpSys   $3000/  IBM AT, self,   "C",    ## ### ##- #### -#-#
Microsoft Corp.         n/a     PS/2    MS-DOS  others

Tele (Kernel)   PgmEnv, $50/    PC's    MS-DOS, "C"     #- ### +#- ##-# ++++
M&T Books, CA   OpSys   free            self

TimeSlicer 5.0  PgmEnv  $300/   PC,AT   MS-DOS  "C"     #- #+- -#- ##-# -#-+
Lifeboat                $1000

XENIX 2.00      OpSys   $?/     IBM AT  self,   "C",    #- ##+ ### #### -+-# 
IBM Corp.               $?              MS-DOS  others

UNIX BSD 4.3    OpSys   $10000/ wkstns, self    "C",    -# ##+ ### #### -#-# 
Berkeley UC             free    mnframs         others

Windows 2.0     AppInt  $600/   PC,AT,  MS-DOS, "C",    #- ### #-- ??-# -#-+
Microsoft Corp.         n/a     PS/2    OS/2    others

LEGEND                                                  # = Has This Feature
------                                                  + = Poss to Implement
                                                        -  = No Support For
Type:   Programming Environment, Operating System, or Application Integrator
Price:  Developer's Kit with Runtime // Source Code

A: "Light-Weight" Threads (with shared memory)
B: "Heavy-Weight" Processes (with protected memory)

C: Low-Level Resource Management (eg, contention management)
D: Medium-Level Resource Management (eg, I/O waiting, deadlock handling)
E: High-Level Resource Management (eg, high-level, optimized interfaces)

F: Intertask Communication              M: User Context Switching
G: Pre-emptive Multitasking             N: User Interrupt Handling
H: Multiprocessor Support               O: User Task Schedulers
                                        P: User Resource Management
I: Task Delay/Alarm Timers
J: Task Priority Levels
K: Task Hierarchies/Inheritance
L: Task Suspension/Termination (Forced)
\end{verbatim}
\end{figure}


No language extension can provide a complete solution.  As alluded to
in the discussion on resources, new operating systems need to be
written to take real advantage of concurrency (Microsoft's OS/2 is
just the beginning).  Nevertheless, Mailbox will allow you to explore,
so you can learn and appreciate all the goods and evils concurrent
processing has to offer you.


\begin{quote}
{\em 
Michael Benjamin Parker is a Junior at MIT majoring in Computer Science.
The Mailbox Multitasker presented here is part of his larger research
project, SHARE, a shared-information distributed operating system for
personal computers.  He can reached from his California home address:
721 E. Walnut Ave, Orange, CA 92667-6833 (714) 639-9497.
}
\end{quote}

\end{document}
