%
% x-kernel v3.3
%
% Copyright (c) 1996,1993,1991,1990  Arizona Board of Regents
%

\section{Thread Library}\label{thread_lib}

The {\xk} uses a ``thread-per-message'' model of computation, and
provides primitives for synchronizing threads.  The following
operations affect thread scheduling.  Of these, only {\var semWait} can
cause the {\xk} to run a different thread than the current one.

Note that this section does not define any operations for creating or
destroying threads.  This is because {\xk} threads are created and
destroyed implicitly.  Threads are created by the device driver (in
the case of incoming messages), by the system call interface (in the
case of outgoing messages), and by the event library (in the case of
an event firing).  Threads are destroyed when they return from the
outer-most procedure.

\subsection{Type Definitions}\label{thread_type_defs}

The only thread-related type of which protocol programmers need be
aware is the type {\var Semaphore}.  However, this type is defined by
the underlying platform and is opaque to the protocol programmer.

\subsection{Synchronization Operations}\label{sync_ops}

\subsubsection{semInit}\label{semInit}
\index{semInit}

Initializes semaphore {\var sem} with a count of {\var count}.
Semaphores in the kernel are normally allocated statically (i.e.,
{\var Semaphore x;}) and must be initialized ({\var semInit(\&x, 1);})
before they are used.
\medskip

{\var void semInit(Semaphore *sem, int count)}

\subsubsection{semWait}\label{semWait}
\index{semWait}

Increments the use count for the semaphore.  The current thread will
either acquire the semaphore {\var sem} or give up control until a
{\var semSignal} is done by another thread and the scheduler runs.
\medskip

{\var void semWait(Semaphore *sem)}

\subsubsection{semSignal}\label{semSignal}
\index{semSignal}

The current thread decrements the use count for semaphore {\var sem}.
The current thread continues executing.  Note that if multiple threads
are blocked on the semaphore, there is no policy about which thread
will be awakened by the {\var semSignal}.
\medskip

{\var void semSignal(Semaphore *sem)}

\subsection{Delay}\label{Delay}
\index{Delay}

Delays the current thread for at least {\var msec} milliseconds.  This
is not a thread primitive, but a library routine built on top of 
{\var semWait}/{\var semSignal}.  Note that the argument is in milliseconds,
while the time argument to {\var evSchedule}
(Section~\ref{evSchedule}) is in microseconds.
\medskip

{\var void Delay(int msec)}

\subsection{Usage Rules}\label{thread_usage}

\subsubsection{Scheduling and Preemption}\label{sched_preempt}

The currently executing thread gives up control by either terminating
or executing a {\var semWait} operation.  In other words, the {\xk}
does not preempt threads; threads voluntarily give up control of the
processor.  However, because each protocol is assumed to be an
independent component, protocols are written to assume that control
may be given up when a higher or lower level protocol is invoked.
Therefore, all protocol-to-protocol operations are considered to have
the potential to cause a thread switch, and all data structures must
be ``secured'' before calling such operations.

\subsubsection{Blocking}\label{blocking}
\index{Blocking}

Although the {\xk} advocates a ``thread-per-message'' model and it
provides primitives for blocking threads, as a general rule, threads
should not block except when waiting for a reply in an RPC-like
protocol.  In most other cases, should a thread not be able to
proceed, it should put the message in a protocol-dependent queue and
return.  Later, another thread can pick up the message from the queue
and continue processing it.

For example, when an incoming thread/message arrives in IP and
discovers that it is just one fragment of a larger datagram, rather
than blocking the thread and waiting for the other fragments to
arrive, the thread should insert the fragment into a reassembly buffer
and return.  The thread that delivers the last fragment will then
reassemble the fragments into a single datagram and continue.

\subsubsection{External Threads}\label{ext_threads}
\label{ext-threads}

Where the {\xk} is embedded in another operating system, there may be
asynchronous threads representing device drivers or user requests that
want to enter the {\xk}.  These threads must, in general, acquire the
{\xk} master lock (i.e., enter the {\xk} monitor) with 
{\var xk\_master\_lock} before performing any {\xk} operations, including
other thread synchronization operations.  (This isn't necessary for
normal {\xk} threads because threads started by {\var evSchedule}
acquire the master lock automatically when they start running.)
Unless a call is explicitly documented otherwise, threads may not make
{\xk} system or library calls without holding the master lock.

A thread acquires and releases the master {\xk} lock with the
following operations.
\medskip

{\var void xk\_master\_lock(void)}
\medskip

{\var void xk\_master\_unlock(void)}
\medskip

\noindent
Note that normal protocols should not use these operations.  The only
place that they are meaningful is in anchor protocols, such as device
drivers, and application-level interfaces, that have to transition
between the {\xk} and the host OS.  Also note that this interface is
not part of the official {\xk} interface; it is internal to the
current implementation of the {\xk}.

\subsubsection{Thread Turnaround}\label{thread_turnaround}

Protocols should refrain from taking threads which are shepherding
outgoing messages down the protocol stack and turning them around to
accompany messages traveling up the protocol stack.  Since protocols
are allowed to reverse thread direction from incoming to outgoing,
allowing turnaround from outgoing to incoming could lead to a thread
caught in a recursive loop.  If an outgoing thread needs to send a
message back up, it should start a new thread to do this.  The push
routine of the ethernet protocol ({\var /usr/xkernel/protocols/eth})
has an example of how this is done.

\subsubsection{Multiprocessor Support}\label{multiproc_support}
\index{Multiprocessor Support}

Version 3.3 of the {\xk} is MP-safe, although probably not
MP-performant.  This is because all threads executing in the {\xk}
must first acquire a master lock; i.e., the {\xk} is currently
implemented as a single monitor.  Research projects at the Swedish
Institute of Computer Science and The University of Massachusetts have
been investigating the addition of finer-grain locks.