A dive into TRIPOS¶

The “TRIvial Portable Operating System” is an O/S from the 70’s from Cambridhe University. It ran (and runs) on a variety of older computers, mostly 16-bit. I’ve been going through the “Cintpos” version of the code, which is freely available from Martin Richards’ webpage.

The Cintpos version is based on the Cintcode bytecode interpreter, normally written in C. As such, it’s really an emulated environment with C code acting as the “hardware” (using POSIX threads for parallelism w.r.t. I/O and clock/timer). So there are really two sides to this: 1) the BCPL code which implements the core O/S design with tasks, queues, drivers, and coroutines, and 2) an emulated environment to make it all work on top of Linux, MacOS, Windows, etc.

Being written in BCPL, this O/S is very portable and – even more importantly perhaps – also very readable. It’s a really nice design, well worth diving into.

Some context¶

TRIPOS is many things, but first: some of its limitations. There is NO …

… memory protection, everything is running in a single address space
… memory management, other than a very basic free space allocator
… automatic task cleanup: no closing files, no releasing memory
… real-time guarantee, but each task does have its own priority
… explicit support for mutexes, semaphores, or condition variables
… stack expansion, each task and coroutine has its pre-allocated fixed stack

Then again, many of the above points don’t really matter all that much. This is not for managing access to highly competing resources. It’s just a system to run well-behaved programs, while supporting a few activities “in the background” as well.

On the plus side …¶

Here are some of the more interesting aspects of the system, which seem to work well:

concurrency is managed via packets exchanged between tasks and drivers
the “work queues” tend to behave as an implicit form of semaphores
there is no need to copy much data, everything can be shared via pointers
packets are usually returned to their sender, there is no need to alloc/free
very clear roles: tasks are coded in BCPL, device drivers are coded in C
the BCPL compiler is self-hosting, the generated code can be loaded as needed
BCPL’s “global vectors” make it easy to reason about dependencies and linkage
as a result, it’s easy to make changes to the BCPL part of the O/S itself
there is no lengthy startup, a reboot after crash/watchdog reset is instant

Having said that, crashes are definitely possible (and almost inevitable during development). There’s “enough rope to hang yourself”, as they say …

High-level design¶

The BCPL side of TRIPOS makes for quite an elegant design:

parallelism is simulated via tasks, which may be switched pre-emptively
a task can send any number of packets to other tasks and devices
sending does not lose control if the destination task has lower priority
hardware devices are exposed and interfaced to via drivers (coded in C)
sending packets to a driver also never blocks, it just starts or stops h/w
TRIPOS can also make use of coroutines for more fine-grained concurrency

This design allows for both asynchronous and synchronous message passing: a task can send a packet and immediately wait for a reply on its wait queue, or it can just send packets at will (keeping good track of their lifetimes), and deal with replies whenever they arrive later.

Task creation and activation are distinct. Creating a task does not set it up for work, nor does it even create a stack for it. This happens when sending the first packet to such a “dead” task. A newly created “service” task will then be handed that packet, at which point it initialises itself and then returns the startup packet. From then on it can wait for incoming packets, deal with them, and eventually send them back with reply information. When finished, the task exits and returns to its dead state, at which point its stack will be released.

Device activity is different. First off: a “device” is hardware and a “driver” is its controlling software. And although TRIPOS documentation refers to sending packets to devices, I will rephrase this as sending packets to drivers, as this seems like a more accurate description.

Device drivers are not tasks. They do not run, suspend, wait, or block. Drivers cannot create packets, they can only accept, save, re-route, and return packets. Devices respond to requests, by making hardware peripherals (or emulated peripherals) start or stop doing something. Often, a request packet will cause the driver to activate some hardware, and then return to the caller. If the calling task wants to wait for a reply, it can wait for incoming packets.

If there is nothing else to do, all the main tasks will end up waiting. At this point, a special idle task will be resumed. This is a zero-priority task doing nothing but sleep. It never blocks.

At some point, a hardware interrupt will take the system out of its lethargic state, and run some code in its associated driver. These interrupts may come at the most inconvenient times, such as while manipulating a task or packet queue. It would be a bad idea to shuffle tasks at this point. Instead, the interrupt routine sets a flag in its associated device data structure.

There is a special interrupt enable/disable call which specifies whether pending interrupts may be processed. All the O/S code which manipulates critical data structures brackets those critical sections with matching disable and re-enable calls. If now is not the time, the interrupt will remain pending until the enable call is made.

Once acceptable, a pending interrupt is then transformed into a call to the generic interrupt dispatcher, which is written in BCPL. This is where the driver can be interrogated again, and where completion of a request can be dealt with by returning the original packet with a reply.

In a way, packets act as message tokens: you set them up and then pass them around using some agreed-upon protocols between originator and destination(s). All the synchronisation takes place via packets, actively being processed or held in a task or device work queue.

Timer delays¶

There is a clock device and associated driver, which accepts packets with a millisecond delay in them. It will save these packets in an internal queue, ordered on expiration time. When the time has been reached, the timer interrupt will cause all expired timers to be returned to their respective sender(s). To delay a task for N milliseconds, you simply call delay(N). Under the hood, it 1) sets up a new packet, 2) sends it to the clock device, and 3) waits for the reply.

Multiple events¶

The above works for “single-minded” activities, such as reading from a device or writing to it. Tasks will block, waiting for the packet to be sent back to their work queue with a reply.

But what about reading with a timeout limit, or reading from any of multiple sources?

Well, this too is straightforward: set up a number of packets and send them off to each of the destination devices (or tasks). Then wait for packets to come in again. Managing packets will be a bit more involved, since there will now be several of them “in flight” at the same time. But since packets are owned by the sending task, it is also free to add any additional information at the end. Such extra information will simply not be used by the destinations.

Coroutines¶

One solution TRIPOS offers for dealing with multiple outstanding packets is to adopt another mechanism: coroutines. These can be viewed as “functions which carry their own stack state around”. Because of this, coroutines (“coro’s“) can suspend (yield) and wake up (resume), very much like full-fledged tasks, the difference is that these are very lightweight, in that no “contexts” need to be saved, restored, let alone switched pre-emptively. Coro overhead is more like a standard function call + return than the context switching needed with tasks.

In modern terms, this is essentially the “async / await” mechanism which is being adopted in numerous programming languages. The coroutine approach is like setting up “mini tasks” which will (cooperatively) block while waiting for replies. Each mini-task will only block on one request, but there can be any number of them in progress. When a reply comes back, the “real” (waiting) task simply needs to figure out which associated coro to resume.

There’s a lot more to TRIPOS, but for now the above will have to do as first introduction …