% This is a TEX LaTeX) document
%

\documentstyle[a4]{article}

\pagestyle{plain}
\pagenumbering{arabic}

\begin{document}

\parindent=22pt
\addtolength{\parskip}{0.2cm}
\sloppy

\bigskip

\centerline{\bf \Large The TRIPOS Operating System}
\medskip

\centerline{M. Richards, October 1988}
\bigskip




\section{Introduction to Tripos}

Tripos is an operating system designed at the University Computer
Laboratory in Cambridge as part of a research project on portable
operating systems.  It was first implemented in 1978 on three
mini-computers: the Computer Automation LSI/4, the PDP 11 and the Data
General Nova.  Since then it has been transferred to several other
machines including the IBM Series/1, the Motorola 68000, the Intel
8086 and the National Semiconductor 16032.

Tripos was originally designed as a single user system that supports
real time multi-tasking facilities, with the overriding constraint
that it should be easy to transfer from one machine to another.  In
order to achieve this level of portability most of the software was
written in the portable systems programming language BCPL.  Even
though most of the system is implemented in BCPL, it was decided that
the entire kernel and all device driver routines should be coded in
assembly language.  This means that when transferring Tripos to a new
machine about 1500 line of assembly code have to be rewritten.  This
does not interfer significantly with the portability of the system and
it has the advantage that the kernel can be compact and efficient.

The hardware facilities for memory mapping and memory protection are
very system dependent and often costly, and so most Tripos systems run
all the code in privileged mode and in the same address space.  This
greatly increases the internal efficiency of the system, but has the
effect programming errors in application programs can crash the
system.  Some versions of Tripos provide limited protection features
that alleviate this problem to some extent.

\section{An example console session}

The main features of Tripos are demonstrated in this section by means
of an annotated console session on BBC model B Microcomputer with two
floppy disc drives attached to a 16032 second processor with 256K
bytes of store.

After switching on the machine and placing the Tripos Load disc in
drive 0 the command \verb|*TRIPOS| will load the resident part of
Tripos into the 16032 and transfer control to it.  The following
message will then appear on the screen:
\begin{verbatim}
Load the Tripos System Disc into drive 0 then press RETURN
\end{verbatim}
\noindent
When these instructions have been carried out the Tripos system will
start to initialise itself, and the following message will appear:
\begin{verbatim}
TRIPOS starting on df0:
***Validating disc "TRIPOS-SYSTEM-0" on df0:
Time?: 
\end{verbatim}
\noindent
The user should respond with the current time of day, for example
\begin{verbatim}
Time?: 10:43
\end{verbatim}
\noindent
The system will reply with the prompt string from the command language
interpreter (CLI) task:
\begin{verbatim}
1>
\end{verbatim}
\noindent
indicating that the system is waiting for commands from the user.
Although the system is now ready to obey commands, the user is not
permitted to do anything that will write to disc until the filing
system validation process is complete.  This state is reached after a
period of about 30 seconds and is indicated by the message:
\begin{verbatim}
***"TRIPOS-SYSTEM-0" validated (21% utilisation)
\end{verbatim}

A small BCPL program is now typed in by the user, as follows:
\begin{verbatim}
1> input to bcpl.t
GET "libhdr"

LET start() BE
$( LET f(n) = n=0 -> 1, n*f(n-1)
   FOR i = 1 TO 5 DO
       writef("f(%n) = %i3*n", i, f(i))
$)
/*
1>
\end{verbatim}
\noindent
The characters \verb|/*| terminate the input and do not form part of
the file \verb|bcpl.t|.  By convention BCPL programs are held in a
file directory called \verb|bcpl|.  The file title \verb|bcpl.t|
refers to the file \verb|t| in the directory \verb|bcpl|.  As can be
seen this example program will tabulate the factorial function from 1
to~5.  It can be compiled using the \verb|bcpl| command as follows:
\begin{verbatim}
1> bcpl bcpl.t to t
BCPL started
Tree size 2385
NS 16032 CG(June 1983)
Program size = 79 words
1>
\end{verbatim}
All but the first and last lines are generated by the compiler.  It
takes about 11 seconds, most of the time being taken reading the
compiler into memory and processing the rather large header file
(\verb|libhdr|) of standard declarations.  The compiled form (or
object module) of the program is now in the file called \verb|t| and
it can be executed by typing the command \verb|t| as follows:
\begin{verbatim}
1> t
f(1) =   1
f(2) =   2
f(3) =   6
f(4) =  24
f(5) = 120
1> 
\end{verbatim}
Notice that no link-editing step is required.  This is because the CLI
dynamically loads the specified object module and executes it as a
coroutine of the CLI task.  It is thus run in the environment of the
CLI which includes all the standard BCPL library procedures (such as
\verb|writef|) as well as all the Tripos kernel primitives.  The linkage to
these procedures is via the BCPL global vector which is the standard
mechanism for combining separately compiled BCPL modules.  Tripos
commands can be separated by semicolons and so it would be legal to
type the following command line:
\begin{verbatim}
1> t;t;t;t;t;t;t;t;t;t
\end{verbatim}
\noindent
This would output the following five lines ten times in rapid succession.
\begin{verbatim}
f(1) =   1
f(2) =   2
f(3) =   6
f(4) =  24
f(5) = 120
\end{verbatim}
There are no noticeable delays in this output largely as a result of
the way the filing system handles small files.

\section{The filing system}

     The filing system provides for the creation of an arbitrary tree
structure of directories.  Each leaf node of the tree is a data file
which can be regarded as a (possibly huge) vector of bytes on the
disc.  A data file may be accessed sequentially or by random access,
sequential access being just a special case of random access.
Directories and data files can, of course, be created, modified and
deleted dynamically.

     The disc is formatted with equal sized blocks (or sectors) that
are typically quite small.  For most Tripos systems the chosen size is
256 words.  All directories are one block long and contain the name of
the directory, its creation date, protection data, and a hash table of
about 200 words giving the start addresses on disc of chains of file
header blocks.  A file header block represents either a directory or
the first block of a data file, in either case it contains a file name
and the creation date, and, if it is the start of a data file, it
contains the first few hundred characters of the file together with
disc addresses locating the rest of the file.  In practice, many files
are small enough to fit entirely in the header block.

     The operation of opening a file such as \verb|t| in directory
\verb|bcpl| is carried out in a number of steps as follows.

\begin{enumerate}
\item The directory block for \verb|bcpl| is brought into main memory.

\item A hash value depending on the file name \verb|t| is 
computed, and used with the directory hash table to find the disc
address of the start of the chain of header blocks for files with the
same hash value.

\item If the chain is empty, then the file is not in the 
directory and the open operation fails.  Otherwise the specified
header block is brought into memory and its file name compared with
\verb|t|.  If it matches then the required header block has been found, and
if it does not match the address of the next header block is extracted
and step (3) repeated.
\end{enumerate}

     In practice very few directories contain hash chains of length greater 
than one, and so file opening tends to be efficient, particularly since 
there is a cache store of recently read disc blocks, which usually already 
contains the relevent directory.  For the command sequence:
\begin{verbatim}
1> t;t;t;t;t;t;t;t;t;t
\end{verbatim}
\noindent
after executing \verb|t| for the first time both the current directory
and the header block for \verb|t| will be in the cache, and since, in
this case, the entire body of \verb|t| is in its header no further
disc transfers will be made during the remaining nine repetitions of
the command.  This partly accounts for the apparent high efficiency of
the CLI.

     Directories may be examined by means of the \verb|ex| command, as
in:
\begin{verbatim}
1> ex
Directory :demo
   bcpl                   dir        17-Oct-84 09:12:36
   t                      1  Block   25-Nov-84 10:56:32
1>
\end{verbatim}
File titles can be quite long (up to 30 characters).  This is regarded
a valuable feature of a general purpose filing system and one that is
not often found in operating systems for small machines.  One can use
the \verb|ex| command to examine other directories, for example:
\begin{verbatim}
1> ex bcpl
Directory bcpl
   t                      1  Block   25-Nov-84 10:59:13
   bounce                 1  Block   24-Nov-84 15:31:49
   send                   1  Block   24-Nov-84 15:33:09
1>
\end{verbatim}

\section{Tasks}

     The filing system is implemented by means of a Tripos task called
the file handler.  This runs independently of the other tasks in the
system but is able to communicate with them by means of the Tripos
message passing primitives.  There are four tasks in a standard Tripos
system and the status of each can be displayed on the screen by means
of the \verb|status| command, as in:
\begin{verbatim}
1> status
Task 1: running
Task 2: waiting
Task 3: waiting
Task 4: waiting
1>
\end{verbatim}
Task 1 is the CLI task and so it is, of course, `running' at the time
when the status command is executing.  Task 2 is a debugging task that
is waiting for a line of input from the keyboard.  Task 3 is called
the console handler and its job is to coordinate all input from the
keyboard and output to the screen.  It implements simple line editing
features and provides facilities for connecting the keyboard to any
specified task.  Finally, task 4 is the file handler.

     Each task has a task control block (TCB) which contains all the
information that the system requires relating to the task.  In
particular, the first five words of a TCB are as follows:
\smallskip
\halign{\indent\indent\indent#\hfil 
        &\quad\vtop{\parindent=0pt\hsize=300pt\strut#\strut}\cr

          Word 1:&a link word used to chain all TCBs in decreasing priority 
                     order.\cr

          Word 2:&a small positive integer used to identify the task.\cr

          Word 3:&a positive integer giving the scheduling priority of the 
                     task.\cr

          Word 4:&a (possibly empty) list (called the work queue) of 
                     messages 
                     received but not yet processed by the task.\cr

          Word 5:&the status of the task encoded as a four bit integer.\cr
}
\smallskip
     When a task is active it has two important areas of workspace:
the global vector and the runtime stack.  These are allocated by the
system automatically when the task starts up.

     It is possible to create tasks dynamically and the \verb|run|
command is an example of a program that uses this facility.  It
creates a new CLI task and causes the rest of the command line to
appear as the currently selected input of the newly created CLI.  This
new CLI task has its own TCB, global vector and stack, and behaves
exactly like the original CLI, except that it obeys the command line
that was given to it by the \verb|run| command.  When the CLI
completes the execution of the command line it commits suicide and
ceases to exist.  Thus the command:
\begin{verbatim}
1> run t
\end{verbatim}
\noindent
causes the following output:
\begin{verbatim}
1> f(1) =   1
f(2) =   2
f(3) =   6
f(4) =  24
f(5) = 120
\end{verbatim}
\noindent
The prompt \verb|1>| appears first since the foreground CLI completes
the execution of the run command before the newly created CLI has had
time to load and enter the command \verb|t|.  We can demonstrate more
clearly that the foreground and background CLIs are active
simultaneously by typing the following two commands in rapid
succession:
\begin{verbatim}
1> run t;t
1> status
f(1) =   1
f(2) =   2
f(3) =   6
f(4) =  24
f(5) = 120
Task 1: running
Task 2: waiting
Task 3: waiting
Task 4: waiting
Task 5: interrupted
f(1) =   1
1> f(2) =   2
f(3) =   6
f(4) =  24
f(5) = 120
\end{verbatim}
As can be seen, the lines of output from the two CLI tasks are merged
on the screen on a first come first served basis.  At first sight this
may seem rather silly, but in practice it is not an inconvenience and
works well.  From the output above we see that task 5 (the background
CLI) did exist at the time that the \verb|status| command was running.
However, if we type \verb|status| again:
\begin{verbatim}
1> status
Task 1: running
Task 2: waiting
Task 3: waiting
Task 4: waiting
1>
\end{verbatim}
\noindent
We see that it has gone away.

     The \verb|run| command is simple to use and has many
applications.  For instance the command:
\begin{verbatim}
1> run spool res; bcpl bcpl.t to t
1>
\end{verbatim}
\noindent
will create a task to do a background compilation of the program
\verb|bcpl.t|.  The \verb|spool| command will redirect the standard
output from the CLI to a file (in this case called \verb|res|) which
can be inspected at a later time.  Typing this file will yield the
expected output:
\begin{verbatim}
1> type res
BCPL started
Tree size 2385
NS 16032 CG(June 1983)
Program size = 79 words
1>
\end{verbatim}
Of course, before typing the file \verb|res| one could have executed other 
commands, even while the background compilation was in progress.

\section{Inter-task communication}

     As has been seen, the Tripos system consists of a number of
interacting tasks.  They communicate with each other by means of a
message passing facility provided by the kernel primitives \verb|qpkt|
and \verb|taskwait|.  A simple but somewhat artificial example of
their use is given in the following demonstration program.
\begin{verbatim}
1> type bcpl.bounce
GET "libhdr"

LET start() BE
    qpkt(taskwait()) REPEAT
1>
\end{verbatim}
When run as a task, this program first calls \verb|taskwait| which
causes it to wait until some other task sends it a message.  A message
consists of a vector (usually called a packet) whose first two
elements are used for system purposes.  The first is used to link
packets together into chains, and the second is used to hold a task
(or sometimes a device) number.  The result of \verb|taskwait| is a
pointer to the packet that caused the task to resume execution, and
the task number that it contains identifies the task that sent the
packet.  This packet is in exactly the the state required by
\verb|qpkt| whose effect, in this case, is to return the packet to the
sender unchanged.  These two calls are embedded in a repeat loop and
so the program will continue to bounce packets back to any task that
sends them indefinitely.

     Assuming that \verb|bcpl.bounce| has been compiled into the file
\verb|bounce|, a bounce task can be created by means of the following
command.
\begin{verbatim}
1> run bounce
1>
\end{verbatim}
This creates task 5 which has the property described above.  Its
existence can be verified by means of the \verb|status| command.
\begin{verbatim}
1> status
Task 1: running
Task 2: waiting
Task 3: waiting
Task 4: waiting
Task 5: waiting
1>
\end{verbatim}
It is, of course, waiting in \verb|taskwait| for some task to send it
a packet.  The bounce task can be exercised by executing the command
\verb|send| whose definition follows.
\begin{verbatim}
1> type bcpl.send
GET "libhdr"

LET start() BE
$( LET v = VEC 2
   v!0, v!1, v!2 := -1, 5, 30000

   writes("starting*n")

   $( LET n = v!2
      IF n=0 BREAK
      v!2 := n-1
      qpkt(v)
      v := taskwait()
   $) REPEAT

   writes("done*n")
$)
1>
\end{verbatim}
This program first declares a vector of three elements and initialises
them, respectively, to -1 (the not-in-use marker), 5 (the desination
task number) and 30000 (a count value).  Assuming that the \verb|send|
command has been compiled, it can be executed as follows:
\begin{verbatim}
1> send
starting
\end{verbatim}
As can be seen from the program, it first writes the message
\verb|starting|.  It then inspects the count field in its packet and
terminates with the message ``\verb|done|'' if has reached zero.
Initially the count (30000) is non zero and so it is decremented and
the packet dispatched to the bounce task by means of \verb|qpkt|.
This task then suspends itself in \verb|taskwait| waiting for the
packet to return from the bounce task.  At this moment the Tripos
scheduler will find that the bounce task has a packet and so can
resume execution causing the packet to be returned immediately to the
send task.  The send task then resumes execution and inspects the
count field again.  It is clear that the packet is sent to the bounce
task 30000 times making a total of 60000 task changes before the count
reaches zero, and the following appears on the screen:
\begin{verbatim}
done
1>
\end{verbatim}
This takes about 15 seconds on a 16032 running with a 12MHz clock and this 
demonstrates that the system can perform about 4000 task changes per second.  
This level of efficiency in the qpkt-taskwait mechanism is important since 
so much of the Tripos system depends on it.

     Before leaving the bounce demonstration we can show that a few variants 
of it work.  In particular, the following:
\begin{verbatim}
1> run send
1> starting
done
\end{verbatim}
\noindent
shows that the \verb|send| command can be executed by a background CLI
in this case task 6.  The packet is therefore bouncing between tasks 5
and~6.  The following example is a little more involved.  Here
``\verb|run send|'' is typed twice and ``\verb|run status|'' once.
\begin{verbatim}
1> run send
1> starting
run send
1> starting
run status
1> Task 1: waiting
Task 2: waiting
Task 3: waiting
Task 4: waiting
Task 5: interrupted with packet(s)
Task 6: waiting
Task 7: interrupted
Task 8: running
done
done
\end{verbatim}
\noindent
However, with a little thought, one can understand why the output is
as it is.  The output does, of course take almost exactly 30 second to
complete and, after it has finished, only five tasks remain.

\section{Debugging}

     As was mentioned earlier, task 2 is a debugging task.  It can be
used to examine and modify other tasks while they are in execution.
To demostrate some of its features, it will be used to examine to
state of the bounce and send tasks while they are running.  The bounce
demonstration is first started by the following:
\begin{verbatim}
1> run send
1> starting
\end{verbatim}
\noindent
and then the following is typed (quickly)
\begin{verbatim}
@s02 s6 h
*
\end{verbatim}
This will connect the keyboard to the debugging task (\verb|@s02|), it
then causes debug to select task 6 (\verb|s6|) and finally causes that
task to be held (\verb|h|).  The asterisk (\verb|*|) is the prompt
character from the debug task.  A task that is `held' will not run
even when it has received packets to work on.  We can show that it is
in this state by selecting task 1 and executing the status command.
\begin{verbatim}
* @s01
1> status
Task 1: running
Task 2: waiting
Task 3: waiting
Task 4: waiting
Task 5: waiting
Task 6: waiting held with packet(s)
1>
\end{verbatim}
Returning to the debug task, we can examine the state of the send
task's stack.
\begin{verbatim}
1> @s02 eb

Active Coroutine START
 taskwai  7945:     10      9   -3337   -4176
 start    7938:   7939      0       5   22656
Stack base  7931 end  8931 hwm  7975

Called from

Root stack
 callco   9476:      0   1000    7851   -1364
 start    9406:   8101   9408    -741       0
Stack base  9399 end  9599 hwm  9517

End of backtrace
*
\end{verbatim}
This shows the root stack used by the CLI and a coroutine stack that
the CLI created in which to execute the \verb|send| command.  The
outermost call in this stack is for the procedure \verb|start|
declared in the send program.  The first local variable of start is
\verb|v| and its value can be seen to be 7939.  This is the address of
the packet used in the bounce demonstration.  This packet is, in fact,
allocated space immediately adjacent to \verb|v| and appears in the
output.  Its link word is zero indicating that it is at the end of a
work queue, the task number in the packet is 5, and the count field is
22656 which shows that the packet still has a long way to travel.  The
count could be changed to some other value, 10 say, as follows:
\begin{verbatim}
* 10pa7941
*
\end{verbatim}
\noindent
which puts (\verb|p|) the specified value (\verb|10|) in the memory
location with the specified absolute address (\verb|a7941|).  The
packet can be inspected again:
\begin{verbatim}
* a7939t3
A 7939/      0      5     10
*
\end{verbatim}
\noindent
to show that the modification has been made.  Before releasing task 6, it is 
instructive to inspect part of its task control block.
\begin{verbatim}
* wt10
W  0/     1543      6    999   7939      7
W  5/        0    200   2021   9047   9399
*
\end{verbatim}
This shows that we are indeed dealing with task 6, that its priority
999, that the first packet on its work queue is at address 7939 and
that its status is 7 (meaning that that it is waiting, held, and with
packet(s)).  The debug command \verb|c| will release the task and since the
packet has only a few bounces to complete its journey the message
``\verb|done|'' will appear immediately.
\begin{verbatim}
* c
* done
\end{verbatim}
In detail, pressing the return key after the \verb|c| command causes
the keyboard device to send a packet to the console handler task which
realises that it now has a complete line of input for task 2.  This it
sends to task 2 before suspending itself in \verb|taskwait| awaiting
more work.  On receiving the completed line, task 2 obeys the
debugging command it contains (releasing task 6) and then sends the
debug prompt string ``\verb|*|~'' to the console handler for
transmission to the vdu screen, and finally it sends a request to the
console handler for another line of input.  At this point task 2
suspends itself waiting for a reply, and the scheduler searches for
the next highest priority task to run.  Task 6 thus gains control and
bouncing continues until task 6 outputs ``\verb|done|''.


\section{Tripos Kernel Procedures}

This section contains a brief description of each of the procedures
belonging to the Tripos Kernel.

\subsection{CHANGEPRI}

\noindent{\it Form:~~}\verb|res := changepri(taskid, pri)|

\noindent{\it Purpose:~~}  To change the priority of a task.

\noindent{\it Specification}

     \verb|changepri| changes the priority of the task specified by
\verb|taskid| to the value of \verb|pri|.  \verb|Pri| must be a 
positive integer different from the priority of any other currently
existing task.  If \verb|changepri| is successful it returns a non
zero result.  If it fails it return zero, and \verb|result2| will
contain 101 (if the \verb|taskid| is invalid) or 102 (if \verb|pri| is
invalid).

\noindent{\it Example:~~}\verb|UNLESS changepri(displaytask, newpri)=0 DO ...|

\subsection{CREATEDEV}

\noindent{\it Form:~~}\verb|devid := createdev(dcb)|

\noindent{\it Purpose:~~}  To link a new device driver into the system.

\noindent{\it Specification}

     \verb|Dcb| is the device control block for the device.
\verb|Createdev| allocates a small negative number to identify the
device, and calls the device initialization routine that is given in
the DCB.  If creation is successful, the result is the new device id.
If creation fails, the result is zero and the reason why is in
\verb|result2|.

\noindent{\it Example:~~}\verb|printerdevid := createdev(printerdcb)|


\subsection{CREATETASK}

\noindent{\it Form:~~}\verb|taskid := createtask(seglist, stsize, pri)|

\noindent{\it Purpose:~~}  To create a new task.

\noindent{\it Specification}

     A task control block is allocated and initialised, using the next
available task identifer.  The segment list, stack size and priority
fields of the newly creates TCB are given the values \verb|seglist|,
\verb|stsize| and \verb|pri|, respectively.  The newly created task is
in `dead' state with no packets on its work queue.  If creation is
successful, then the result is the new task identifier (a small
positive integer).  If creation fails, the result is zero and the
reason why is in \verb|result2|.

\noindent{\it Example:~~}\verb|countingtask := createtask(countingsegl, 200, 1)|

\subsection{DELETEDEV}

\noindent{\it Form:~~}\verb|dcb := deletedev(devid)|

\noindent{\it Purpose:~~}  To delete a device from the system.

\noindent{\it Specification}

     \verb|Devid| must be the id of a device that currently exists.
\verb|Deletedev| will attempt to delete the device and, if successful,
it will yield the DCB of the device.  If unsuccessful, the resultis
zero and the reason why in given in \verb|result2|.  A device may only
be deleted if its work queue is empty.

\noindent{\it Example:~~}\verb|deletedev(lpdev)|

\subsection{DELETETASK}

\noindent{\it Form:~~}\verb|res := deletetask(taskid)|

\noindent{\it Purpose:~~}  To delete a task.

\noindent{\it Specification}

     \verb|Taskid| is an integer specifying the task task to be
deleted.  If deletion is successful, the result is non zero.  If
deletion is unsuccessful the result is zero and the reason why is in
\verb|result2|.  A task with a non empty work queue may not be deleted.

\noindent{\it Example:~~}\verb|IF deletetask(countingtask)=0 DD ...|



\subsection{DQPKT}

\noindent{\it Form:~~}\verb|res := dqpkt(id, pkt)|

\noindent{\it Purpose:~~} To attempt to recover a packet previously sent to a
task or device.

\noindent{\it Specification}

     \verb|Dqpkt| first searches down the work queue of the task or
device specified by \verb|id| for the packet \verb|pkt|, and if it
fails to find it there it searches down the work queue of the current
task.  If the packet is found, it is de-queued and the result is the
id of the device or task on whose queue it occurred.  If the packet is
not found, the result is zero and the reason why is given in
\verb|result2|.

\noindent{\it Example:~~}\verb|dqpkt(clkpkt)|



\subsection{FREEVEC}

\noindent{\it Form:~~}\verb|freevec(v)|

\noindent{\it Purpose:~~}  To return a vector to free store.

\noindent{\it Specification}

     The vector \verb|v| (which must be a vector allocated by
\verb|getvec|) is returned to free store.

\noindent{\it Example:~~}\verb|freevec(workvec)|

\subsection{GETVEC}

\noindent{\it Form:~~}\verb|v := getvec(upb)|

\noindent{\it Purpose:~~}  To allocate a vector of specified size.

\noindent{\it Specification}

     The result of \verb|getvec| is a vector allocated from free store
whose lower and upper bounds are 0 and \verb|upb|.  If \verb|getvec|
fails, the result is zero, and \verb|result2| contains the reason why
(103 = insufficient store).

\noindent{\it Example:~~}\verb|workspace := getvec(workspacesize)|


\subsection{GLOBIN}

\noindent{\it Form:~~}\verb|res := globin(segs)|

\noindent{\it Purpose:~~} To initialize the globals defined in a segment of
code.

\noindent{\it Specification}

     \verb|Segs| is a (possible empty) list of modules of code linked
through their zeroth elements.  Just such a list is the result of
\verb|loadseg|.  The global variables defines in each module in the
list are initialized.  If \verb|globin| is successful it returns
\verb|TRUE|, otherwise it returns \verb|FALSE| and the reason for
failure in \verb|result2| (111 = global vector too small).

\noindent{\it Example:~~}\verb|UNLESS globin(libseg) DO ...|


\subsection{HOLD}

\noindent{\it Form:~~}\verb|res := hold(taskid)|

\noindent{\it Purpose:~~}  To hold a specified task.

\noindent{\it Specification}

     \verb|Hold| attempts to sets the hold bit in the task control
block of the task whose id is \verb|taskid|.  If it is successful, the
result is non zero.  If it fails, the result is zero and the reason
why is in \verb|result2| (101 = invalid id, 110 = task already held).

\noindent{\it Example:~~}\verb|hold(sorttask)|


\subsection{QPKT}

\noindent{\it Form:~~}\verb|res := qpkt(pkt)|

\noindent{\it Purpose:~~}  To send a packet to a task or a device.

\noindent{\it Specification}

     \verb|Pkt| is the packet to be sent. It is a vector of at least
two elements, the first (\verb|pkt!0|) is used by the system for
chaining packets together and must be set to \verb|notinuse| (= -1),
and the second (\verb|pkt!1|) is the id of the task or device to which
the packet is to be sent.  \verb|qpkt| will put the packet on the end
of the work queue of the specified task or device, or in the
appropriate place in the queue if the packet is addressed to the
clock.  If \verb|qpkt| is sucessful, the result is non zero.  If
\verb|qpkt| fails, the result is zero and the reason why is in
\verb|result2| (101 = invalid id).  If the packet is addressed to a
higher priority task, the current task will be suspended until all
higher priority work has completed.

\noindent{\it Example:~~}\verb|IF qpkt(message)=0 DO ...|


\subsection{RELEASE}

\noindent{\it Form:~~}\verb|res := release(taskid)|

\noindent{\it Purpose:~~}  To release a previously held task.

\noindent{\it Specification}

     \verb|Release| will release the task whose id is \verb|taskid|.
If \verb|release| is successful, the result is non-zero.  If
\verb|release| fails the result is zero and the reason why is given in
\verb|result2|.

\noindent{\it Example:~~}\verb|IF release(worktask)=0 DO ...|


\subsection{SETFLAGS}

\noindent{\it Form:~~}\verb|res := setflag(taskid, flags)|

\noindent{\it Purpose:~~}  To set the flags in a task.

\noindent{\it Specification}

     The bit pattern \verb|flags| is ORed into the flags field of the
task whose id is \verb|taskid|.  If \verb|setflags| is successful, the
result is non-zero.  If it fails, the result is zero and the reason
why is given in \verb|result2|.

\noindent{\it Example:~~}\verb|IF setflags(worktask, flag.b+flag.d) = 0 DO ...|


\subsection{START}

\noindent{\it Form:~~}\verb|LET start(pkt) = ...|

\noindent{\it Purpose:~~} \verb|Start| is the main procedure of a task or a
command.

\noindent{\it Specification}

     When a newly created task receives its first packet, the system
will allocate space for its global vector and stack.  The elements of
the global vector will be initialised with the entry points to the
procedures defined in all the modules of code (in the segment list)
that belong to the task.  The system then calls \verb|start(taskwait())|,
and thus enters the procedure \verb|start| giving it as argument the packet
that activated the task.  It is thus necessary for \verb|start| to be
defined in one of the task's modules.

     \verb|Start| is also called by the Command Language Interpreter in
order to enter a command that has just been loaded into memory.  In
this context, the argument passed is zero.

\noindent{\it Example:~~}\verb|LET start() BE abort(999)|


\subsection{TASKWAIT}

\noindent{\it Form:~~}\verb|pkt := taskwait()|

\noindent{\it Purpose:~~} To suspend the current task until the next packet
arrives.

\noindent{\it Specification}

     If there are any packets on the work queue of the current task,
the first packet is de-queued and returned as the result.  If, on the
other hand, the work queue is empty, the current task is suspended (in
wait state) until the next packet arrives, this is then de-queued and
returned as the result.

\noindent{\it Example:~~}\verb|workpkt := taskwait()|


\subsection{TESTFLAGS}

\noindent{\it Form:~~}\verb|res := testflags(flags)|

\noindent{\it Purpose:~~}  To test and clear flags of the current task.

\noindent{\it Specification}

     Every task has a task control block and one of its fields is a
word of flag bits that can be set by \verb|setflags| and tested by
\verb|testflags|.  \verb|Testflags| inspects the flags of the current
task specified by the bit pattern \verb|flags|.  The result is TRUE if
any of the specified flags are set and FALSE otherwise.
\verb|Result2| is set to the bit pattern representing which of the
selected flags were set, and before returning \verb|testflags| resets
these flags.

\noindent{\it Example:~~}\verb|...  REPEATUNTIL testflags(flag.b)|


\smallskip

\section{The Tripos Kernel Data Structure}

In this section the main components of the Tripos Kernel Data
Structure are briefly described.

\section{The Root Node}

     This is a vector held in main memory from which all parts of the
system can be reached.  Its fields are as follows:

\begin{tabular}{lp{8.5cm}}
     Tasktab   & points to a vector of TCBs.\\
     Devtab    & points to a vector of DCBs.\\
     Tcblist   & points to the highest priority TCB.\\
     Crntsk    & points to the currently running TCB.\\
     Blklist   & points to the first block of store.\\
     Debtask   & points to the TCB of the debug task.\\
     Days      & is the number of days since 1 January 1978.\\
     Mins      & is the number of minutes since midnight.\\
     Ticks     & is the number of clock ticks since the start of the
current minute.\\
     Clkwq     & is the list of packets on the clock work queue.\\
     Memsize   & is the size of memory in Kwords.\\
     Info      & points to the infomation block.\\
     Restart   & is the restart address in the Kernel.\\
     Devunset  & is a bit pattern used by device drivers.\\
     (Devmvp)  & is the address of the movpkt subroutine.\\
     (Devret1) & is the address for a simple return from an interrupt.\\
     (Devret2) & is the address for a complicated return from an interrupt.\\
     (Htcb)    & pointer used by interrupt routines.\\
\end{tabular}

\section{The Task Table}

\begin{tabular}{lp{8.5cm}}
     \verb|Tasktab!0|&is the upper bound of the table.\\
     \verb|Tasktab!n|&is either zero or a pointer to the TCB (task
     control block) of task \verb|n|.\\
\end{tabular}

\section{The Device Table}

\begin{tabular}{lp{8.5cm}}
     \verb|Devtab!0|&is the upper bound of the table.\\
     \verb|Devtab!n|&is either zero or a pointer to the DCB (device
     control block) of device \verb|n|.\\
\end{tabular}
     
\section{Task Control Blocks}

\begin{tabular}{lp{8.5cm}}
     Link&points to the next TCB in the TCB list.\\
     Id&is the task identifier (\verb|Tasktab!id| points to this TCB).\\
     Pri&is the task priority.\\
     Wkq&is the list of packets sent to this task but not yet processed. \\
     State&is the status of the task (a four bit integer).\\
     Flags&is a field of bits used by \verb|setflags| and \verb|testflags|.\\
     Stsize&is the root stack size for this task.\\
     Segl&points to the segment list vector.\\
     Gbase&is zero or points to the global vector for this task.\\
     Sbase&is zero or points to the root stack for this task.\\
     Sp&points to the machine dependent register dump area for this task.\\
\end{tabular}

\section{Segment List Vector}

\begin{tabular}{lp{8.5cm}}
     \verb|Segl!0|&holds the upper bound of the segment list vector.\\
     \verb|Segl!n|&is a (possibly empty) list of sections of program 
              belonging to the task.\\
\end{tabular}

\section{Sections of Program}

     If \verb|L| points to a section of program then:

\begin{tabular}{lp{8.5cm}}
     \verb|L!0|&is zero or points to another section of program.\\
     \verb|L!1|&is the size (\verb|SIZE|) of this section of
     program.\\
     \verb|L!(SIZE-1)|&is the highest numbered global used
     by the code in this section of program.\\
     \verb|L!(SIZE-2)|&is
     zero or the entry address of a global procedure defined in this
     section of program.\\
      \verb|L!(SIZE-3)|&is the global number for
     the procedure in \verb|L!(SIZE-2)|\\
     \verb|.....|&entry address/global
     number pairs follow until a zero is \\
     \verb|.....|&encountered.\\
\end{tabular}

\section{Packets}

     The field of a packet are as follows:

\begin{tabular}{lp{8.5cm}}
     Link&is zero or points to another packet.\\
     Id&is the id of a task, a device, or the clock.\\
     Type&is the first of a variable number of words used to pass 
                 information from the sender to the receiver of the packet.\\
     Res1&is normally used for the first result.\\
     Res2&is normally used for the second result.\\
     Arg1&is normally used for the first argument.\\
     Arg2&(etc).\\
\end{tabular}

\section{Task States}

     The status of a task is held in the State field of the TCB.  It is a 
four bit integer (IWHP).

\begin{tabular}{llp{8.5cm}}
     State&{\tt 11XX}&the task is dead (with no stack or global vector).\\
     State&{\tt 01XX}&the task is in WAIT state waiting for a packet to be 
                      sent to it.  In this state the BCPL runtime stack 
                      pointer P is preserved in the TCB.\\
     State&{\tt 10XX}&the task is in interrupted state with all the 
                      processor registers preserved in the TCB.\\
     State&{\tt XXX1}&the TCB has at least on packet on its work queue.\\
     State&{\tt XX1X}&the task is in HOLD state (preventing execution).\\
     State&{\tt 000X}&the task is in RUN state (and may even be executing).\\
\end{tabular}

\end{document}
