git.pond.sub.org Git - empserver/blob - src/lib/lwp/misc/lwp.tex

   1 \documentstyle[tgrind, a4]{article}
   2 \title{The {\sc Rex} lightweight process library}
   3 \author{Stephen Crane\\ (jsc@doc.ic.ac.uk)\thanks{Thanks to Mark Little
   4 (m.c.little@ncl.ac.uk) for the Linux port}}
   5 \begin{document}
   6 \maketitle
   7 This document describes the interface to and the behaviour underlying
   8 my threads library for Rex.\footnote{Available as lwp.tar.gz by anonymous
   9 ftp from gummo.doc.ic.ac.uk:/rex.  Rex (Esprit project 2080) was
  10 axed by Men in Suits.}  It has been tested on Sun-3, Sun-4,
  11 Mips, 386-BSD and Linux systems.  Counting semi-colons, it is
  12 260 lines long, including support for the different architectures (this
  13 figure includes variable- but not function-declarations).
  14
  15 A word from our sponsor:
  16 \begin{quote}
  17 This library is free software; you can redistribute it and/or
  18 modify it under the terms of the GNU Library General Public
  19 License as published by the Free Software Foundation; either
  20 version 2 of the License, or (at your option) any later version.
  21
  22 This library is distributed in the hope that it will be useful,
  23 but {\sc WITHOUT ANY WARRANTY}; without even the implied warranty of
  24 {\sc MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE}.  See the GNU
  25 Library General Public License for more details.
  26
  27 You should have received a copy of the GNU Library General Public
  28 License along with this library; if not, write to the Free
  29 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  30 \end{quote}
  31
  32 (Note that while this library is protected by the GNU copyleft, it is not
  33 supported by the Free Software Foundation.)
  34
  35 \section{Threads}
  36 Threads are prioritised and
  37 non-preemptive.  Operations supported on threads are:
  38 \begin{tgrind}
  39 \L{\LB{}\Tab{8}{\K{struct} pcb *initlp (\K{int} priority)}}
  40 \L{\LB{}\Tab{8}{\K{struct} pcb *creatp (priority, entry, size, argc, argv, envp)}}
  41 \L{\LB{}\Tab{8}{\K{void} readyp (\K{struct} pcb *p)}}
  42 \L{\LB{}\Tab{8}{\K{void} yieldp (\K{void})}}
  43 \L{\LB{}\Tab{8}{\K{void} *getenvp (\K{struct} pcb *p)}}
  44 \L{\LB{}\Tab{8}{\K{void} setenvp (\K{struct} pcb *p, \K{void} *)}}
  45 \L{\LB{}\Tab{8}{\K{void} suicidep (\K{void})}}
  46 \L{\LB{}\Tab{8}{\K{void} destroyp (\K{struct} pcb *p)}}
  47 \end{tgrind}
  48 \begin{description}
  49 \item[initlp] initialises the threads runtime, creating a thread with
  50 specified priority for the invoker.
  51 \item[creatp] creates a new thread with specified {\em priority}, {\em
  52 entry} point, with a stack of {\em size}, {\em argc} arguments in {\em
  53 argv} and a user-defined environment pointer.
  54 \item[getenvp] returns the environment pointer associated with the given
  55 thread.  If the thread is null, the current thread is assumed.
  56 \item[setenvp] reassigns the environment pointer associated with the
  57 given thread.
  58 \item[readyp] makes the specified thread ready to run, or the current
  59 thread if null.
  60 \item[yieldp] makes the current thread ready to run.  If no thread of
  61 higher priority is runnable, the current thread will run.
  62 \item[suicidep] marks the invoking thread as dead.  It will never be
  63 rescheduled.
  64 \item[destroyp] marks the specified thread as dead.  It will be removed
  65 at the next reschedule.  If it is currently running, it will be
  66 unaffected until the next reschedule.
  67 \end{description}
  68
  69 \section{Semaphores}
  70 For synchronisation, counting semaphores are provided.  Available
  71 operations are:
  72 \begin{tgrind}
  73 \L{\LB{}\Tab{8}{\K{struct} sem *creats (\K{int} count)}}
  74 \L{\LB{}\Tab{8}{\K{void} signals (\K{struct} sem *s)}}
  75 \L{\LB{}\Tab{8}{\K{void} waits (\K{struct} sem *s)}}
  76 \end{tgrind}
  77 \begin{description}
  78 \item[creats] allocates a new semaphore from the heap and initialises its
  79 count.
  80 \item[signals] increments the semaphore's count, makes a waiting process
  81 ready if there is one.  If the readied process's priority is greater than
  82 that of the signaller, a reschedule is done.
  83 \item[waits] decrements the semaphore's count.  If it becomes negative,
  84 the current process is suspended and a reschedule is done.
  85 \end{description}
  86
  87 \section{Signals}
  88 The library is concerned with two types of signal, {\sc sigio} and {\sc
  89 sigalrm}.  These signals are normally blocked until the null process is
  90 scheduled.  It uses {\tt sigpause()} to reenable them and wait for one
  91 to arrive.  While awaiting a signal, the null process `runs' at maximum
  92 priority.  Thus users will not be able to cause a reschedule from
  93 their handlers.  When {\tt sigpause()} returns, the signal will have
  94 been handled and the null process drops back down to the lowest priority
  95 and yields to any thread which has been made ready to run from the
  96 user-level handler.
  97
  98 These semantics make the library rather unresponsive to signals in the
  99 presence of busy processes.  If a more responsive system is required,
 100 the constant {\sc LCOUNT} may be changed.  This value determines the
 101 number of times the {\tt reschedp ()} function must be called before
 102 signals are re-enabled.  If given a value of {\tt 1}, it will affect
 103 context-switching time by about 50\%.  Its default value is {\tt -1}.
 104
 105 \subsection{Input and output}
 106 Input and output present a problem to threads, because they require
 107 calls to the underlying {\sc Unix} system, which will block not only
 108 the invoking thread, but also all others in the process.  Thus, in
 109 general, a thread must wait until the descriptor on which I/O is to
 110 be done becomes ready for the operation.  This is done by trapping
 111 {\sc sigio}.  Two routines are provided:
 112 \begin{tgrind}
 113 \L{\LB{}\Tab{8}{\K{int} sigioset (\K{int} fd, \K{void} (*han) (\K{void}
 114 *, \K{int}), \K{void} *ctx)}}
 115 \L{\LB{}\Tab{8}{\K{int} sigioclr (\K{int} fd)}}
 116 \end{tgrind}
 117 The general model adopted for processing {\sc sigio} is to install a
 118 {\em handler} routine for the I/O descriptor using {\em sigioset} and
 119 remove it using {\em sigioclr}.  The user is responsible for setting up
 120 the device correctly to generate {\sc sigio}.  When {\sc sigio} arrives
 121 for the descriptor, the handler will be called with a context pointer
 122 as its argument.  (In C++, this context is the instance pointer of the
 123 invoking thread.)
 124
 125 \subsection{The timer}
 126 A single routine is provided to block the invoking thread for the
 127 specified time:
 128 \begin{tgrind}
 129 \L{\LB{}\Tab{8}{\K{void} delayp (\K{int} n)}}
 130 \end{tgrind}
 131 This routine blocks the invoker for {\em at least\/} the time specified.
 132 If this is zero, a reschedule is done.  Delays are implemented as a
 133 delta queue, using {\sc sigalrm}.  $n$ specifies a microsecond delay
 134 which is of limited utility in practice.
 135
 136 \section{Performance}
 137 \begin{figure}[htb]
 138 \begin{center}
 139 \begin{tabular}{||l|c|c|c||} \hline
 140 Arch    & ctxsw & creat & comment \\ \hline
 141 sun3    & 308   & 778   & 3/240 \\ \hline
 142 386bsd  & 186   & 464   & 486/33 \\ \hline
 143 sun4    & 96    & 436   & IPX \\ \hline
 144 sun4    & 59    & 212   & Sparc-10 \\ \hline
 145 linux   & 56    & 382   & 486-DX2/50 \\ \hline
 146 mips    & 17    & 85    & Decstation \\ \hline
 147 \end{tabular}
 148 \caption{Performance with architecture (times in microseconds).}
 149 \end{center}
 150 \end{figure}
 151 \begin{description}
 152 \item[sun3] has very lightweight process initialisation, compared with
 153 context switching.
 154 \item[sun4] has a high context switch time as a result of {\tt setjmp ()} and
 155 {\tt longjmp ()} implementations.  Process initialisation is also relatively
 156 heavyweight: it requires two calls to {\tt setjmp ()} and one to {\tt longjmp
 157 ()}.
 158 \item[mips] provides its own context switching in assembly language.
 159 \end{description}
 160
 161 \section{Porting to another architecture}
 162 Although the threads library is quite portable, a few guidelines should
 163 be observed when moving to a new architecture.
 164
 165 \begin{itemize}
 166 \item Create two new files for your architecture/kernel (e.g. {\tt sun4.c}
 167 and {\tt sun4.h}).
 168 The `.c' file should contain any routines which your version of {\sc Unix} is
 169 missing and a thread initialisation routine:
 170 \begin{tgrind}
 171 \L{\LB{}\Tab{8}{\K{void} initp (\K{struct} pcb *, \K{void} *)}}
 172 \end{tgrind}
 173 The `.h' file contains any machine-specific definitions.
 174 \item If {\tt setjmp ()} and {\tt longjmp ()} don't work on your machine
 175 (for example the {\sc Ultrix} {\tt longjmp ()} implementation checks that
 176 the frame being jumped to is an ancestor of the current one), you will
 177 have to write {\tt savep ()} and {\tt restorep ()} and put the following
 178 define into your machine-specific header file:
 179 \begin{tgrind}
 180 \L{\LB{}\Tab{8}{\K{\#define} OWN\_CONTEXT\_SWITCH}}
 181 \end{tgrind}
 182 \item Compile and run the three test programs: {\tt producer.c}, {\tt
 183 timer.c} and {\tt bm.c}.
 184 \item Add the name of the architecture to `config'.
 185 \item Send {\tt new-arch.[ch]}, any context diffs for the rest of the
 186 library and the output of {\tt bm.c} to {\tt jsc@doc.ic.ac.uk}.  Also
 187 please let me know where you got the library from.
 188 \end{itemize}
 189 \end{document}