The Taos operating system uses objects from the ground up to enable processors based on different architectures to work together on the same problem
Dick Pountain
Nowadays several computers can generate realistic ray-traced images, and some of them can even do it fast. A rendering demonstration I recently witnessed was impressive for one special reason: The PC doing the rendering was executing the same ray-tracing program in parallel on an Intel 486, four Inmos T800 transputers, and four Mips R3000s. What made this feat possible was Taos (pronounced "dowse," as in the Chinese philosophy Taoism), a radically different, object-oriented parallel operating system.
Roots of Taos
Most operating systems are created either by large computer companies or by university researchers, but Taos is different--it's the product of a devoted g
roup of enthusiasts with an idea that was well ahead of its time. The principal architect of Taos is Chris Hinsley, formerly a professional games programmer with hit titles for the Atari ST and the Commodore Amiga to his credit. Although writing solely in assembly language, Hinsley devised his own object-oriented development style based on macros, which sparked the original idea for Taos. Fired by the launch of Inmos's transputer architecture, Hinsley wanted to create a real-time operating system that could harness the parallel-processing power he believed would be needed for future multimedia systems.
When I first wrote about Taos in the International edition of the March 1991 BYTE, it seemed outrageously removed from the mainstream. Today, many of the concepts it is built on are showing up in the commercial operating-system world. Everyone wants a microkernel now, but Taos is already a nanokernel system, with its tiny 12-KB kernel running on each processor in a parallel network. Taligent promises obj
ects from the ground up with dynamic binding; Taos has had them from the start.
One difference is Taos doesn't really aspire to mainstream desktop status; instead, it is a fast and skinny system for embedded applications. Tao Systems is promoting it into the multimedia and games console markets.
The Virtual Processor
By far, the most radical aspect of Taos is its hardware independence. Taos programs are all written in the machine code of a VP (virtual processor), which is called VPcode. The Taos kernel translates VPcode into the native machine code of each real processor immediately before running it--there is little or no run-time penalty, unlike earlier interpreted systems (e.g., the UCSD p-system), which were slow. Taos's fine-grained object orientation and dynamic binding makes this translation strategy feasible: VPcode modules are always small (typically a few hundred bytes), so they can be translated on the fly as they load from disk into memory. Huge monolithic applications like Excel
or WordPerfect wouldn't lend themselves to this approach. But Tao Systems' translator supremo Andy Henson stressed to me that a fast modern CPU can actually translate VPcode faster than a hard drive can transfer data.
The imaginary VP is a 32-bit little-endian RISC machine with 16 registers. It supports data types from 8-bit bytes up to 64-bit double integers and 32- or 64-bit IEEE floating-point numbers. Hence, the VP is a reasonably good match to most real RISC chips like the Alpha, Mips, ARM, and PowerPC, if somewhat short of registers by today's standards. It supports around 60 simple RISC-like arithmetic, logical, and branching instructions, as well as a few special pseudoinstructions. These latter include TAO, which calls Taos kernel routines, and LIT, which marks literal data that needs to be translated (e.g., from little-endian to big-endian).
The Taos assembler, VPASM, outputs VPcode that you can run directly or you can convert to native code by manually invoking the appropriate transla
tor. The listing "VPcode at Work" shows a sample of VPASM source code. Currently, Tao Systems has translators for the Intel 286, 386, and 486, the Inmos T800 and T9000 transputers, the Mips R3000, and the ARM 601. The PowerPC and the DEC Alpha are next in the pipeline; it takes around six worker-months to produce a new translator.
The Taos Object Model
Taos is a message-passing operating system whose software model is based on objects, processes, and messages. An object is a bundle of data and code that consumes memory, while a process executes an object and consumes processor time. The Taos hardware model involves multiple processors each with a local memory, connected by a network of communications links. Every processor in this network runs a copy of the Taos kernel and the translator from VPcode to its own native code. Whenever Taos creates a new object, it allocates the object to a processor and then starts a process to execute the object.
All Taos objects are constructed from variable-s
ize blocks of contiguous memory called nodes. Each node contains two link fields so that the kernel can manage them in doubly linked lists. Nodes can contain data or code, and they have a type field that identifies the type of object they hold. Taos itself doesn't type-check the application of operations to data, although you can implement such type-checking at a higher level within an OOP (object-oriented programming) language.
While stored on disk or in transit over a communications link, nodes exist as unbound templates, but once nodes are loaded into memory, they are converted to "process-ready" form, and it's at this time that any translation of VPcode to native code takes place. The Taos kernel on a particular processor inserts a process-ready node onto a list of other process-ready objects, from where it can be processed according to the type of object it holds.
Tools, Control Objects, and Classes
Taos's predefined system object types are tools, control objects, bit maps, graphical obj
ects, and class objects, but programmers are free to define new types. A tool is a node containing executable code that can act on the data contained in an object, to perform calculations or send and receive messages. A control object is the Taos equivalent of a program, consisting of one or more component tools that are executed in sequence. Control objects are the smallest unit of parallel distribution and execution under Taos. They are not, however, the smallest unit of memory management, because the kernel can retrieve individual tools from disk and make them process-ready. The kernel that creates a new control object distributes its template (using a special load-balancing algorithm) onto some processor, which starts a process to execute the object. When the last component of the control object is finished, the control object closes, and its process terminates. Every component has at least two tools associated with it: one that executes the component and one that cleans up after it dies.
A control
object's template contains only the text names of its component tools, not their actual code. When the kernel creates a new control object, it first checks whether any of these specified components are already in memory, and if so, it just points to them--otherwise, it fetches them from disk and makes them process-ready (first translating them, if necessary). Binding under Taos is thus fully dynamic so that no module gets loaded until it is needed and only one copy is ever present in memory. The Taos processes that execute control objects are lightweight, equivalent to "threads" in operating systems like OS/2, and more than one process can share the same tool's code in multithreaded fashion.
Class objects provide the highest level of organization under Taos. A class encapsulates a group of message-passing objects that can run in parallel, hiding them behind an OOP method interface. Users of classes like Window or PolygonWorld make method calls to the class object (e.g., to open a new window) and are s
hielded from the complexity of the underlying parallelism that's generated by the execution of the objects hidden within the class.
The Kernel and Memory Management
The simplest version of the Taos kernel is just 12 KB in size and is responsible for multitasking (via a time-sliced process scheduler), memory management, and the mail and naming systems. Tao Systems is working on a Posix-compliant version of the kernel that implements virtual memory and memory protection on microprocessors that have suitable MMU (memory management unit) hardware, but the 12-KB version does not offer these features.
All executable code in Taos is contained in tools, apart from the small bootstrap loader on each processor that must be in native code. Even the kernel itself is built from tools and is largely written in VPcode. Device drivers are just like any other process, running outside and in parallel with the kernel. Link drivers running outside the kernel handle all I/O messages, although the kernel handles s
ome local I/O support mechanisms such as data caching.
A process called the Migrator, which runs outside the kernel, is responsible for relocating tool objects in memory and for incremental garbage collection. The lifetime of a Taos tool in memory is determined by its status, according to four different degrees of volatility:
1. Virtual tools are loaded, translated, and bound only when another tool calls them. The translated code remains in memory until the tool's reference count (which the kernel keeps) falls to zero, after which the kernel can flush the code whenever it needs memory. The kernel may relocate a virtual tool at any time.
2. Nonvirtual tools get loaded and bound at the same time as the tool that references them, and they remain in memory, exempt from relocation, for at least the lifetime of their caller.
3. Semivirtual tools are loaded and bound only when called, like virtual tools, but they then remain in memory like nonvirtual tools.
4. Nonvirtual tools can be flagged
as embed, which causes the translator to embed them as in-line code in their caller's code. This is a speed optimization that is extensively used in the kernel code.
Message Passing
Because Taos does not support shared memory, the only way for objects existing in the address spaces of different processors to interact is by exchanging messages. The lightweight asynchronous mail system works through just two kernel operations, SENDMAIL and READMAIL, and it's nonblocking so that the sender continues executing without waiting for a reply.
All Taos messages are sent to mailboxes belonging to processes, which act as queues for incoming messages. When a control object is created and executed, it automatically receives a default mailbox, whose mail address is simply the ID of the child process that executes the object. The new control object can then send mail to any other object whose mailbox address it knows--every object knows the address of its own children, parents, and named resources like dis
k drives and CRT displays. Messages may contain a whole list of successive destination addresses for forwarding, along with the address of their sender in case a reply is requested.
Taos messages are assigned distinct types. The kernel reserves 16 types, which include arrays, streams, and executable code; error and debugging data; and screen refresh, mouse, and keyboard events. A further 16 types are free for programmers' use. The kernel on each processor handles all incoming mail for its local objects, all outgoing mail, and mail to be forwarded to another processor. The typing system enables the kernel to trap system messages (e.g., executable code) and also allows user-defined objects to prioritize the way they read their waiting mail. Objects can employ the READMAIL kernel call to read messages from their mailbox, adding a list of the desired message types as a parameter. The result of such a call might be a message of the required type, or the news that there are no such messages--if the mailbox c
ontains no messages at all then READMAIL suspends the calling process until some mail arrives so that you can use mail messages to awaken sleeping objects.
Taos's link drivers hide the details of the physical transport mechanism that implements the communications links from user programs (although real-time performance issues may sometimes intrude). In the rendering demonstration I mentioned earlier in this article, the transputers were connected via their serial links, while the Mips R3000 chips were connected together through FIFO (first-in/first-out) chips, and all of them talked to the 486 host CPU via the PC's VL-Bus.
Execution in Parallel
Taos is a fully distributed operating system that doesn't attempt to exert central control over the execution of parallel applications. Obviously, in practice, you must pick out one processor from which to boot the system, but once all the kernels are booted Taos programs tend to spread out over the network of processors in an almost organic manner, co
ntrolled by a distributed load-balancing algorithm. If you examine the "control object management" subsection in the text box "Taos Kernel Calls" on page 56, you'll see the kind of services that are available for spawning remote processes. These kernel calls use the mail system to transfer executable VPcode from one processor to another.
Information about the system's performance and current loading is stored in the link drivers that control each communications channel. At boot-up, each link driver benchmarks the processors to which it's attached (by timing the VPcode translator). This number is then divided by the number of processes currently running to give a measure of available power for each processor. The automatic load-balancing algorithm uses these power figures in the allocation of new processes. When a tool object arrives at a processor, the local kernel inspects all the links leading outward and asks "is there one of my nearest neighbors who's got more spare power than I have?"--if so, the
object is passed on; if not, it executes here.
Applications that dynamically spawn many parallel processes spread out like water running down a mountain, the flow seeking out the lowest points, or gullies, in processor-loading space.
Each link driver also maintains a table of encoded information about the network topology, used by the kernel to route messages. These tables are dynamically updated at run time so that if a new processor is added to the system, news of its existence spreads outward like a wave. The nature of the routing algorithm reduces the probability of deadlock due to circular message paths, and it can usually find multiple paths between two processors (if they exist), which provides a degree of fault tolerance if a link fails.
A programmer can always override the automatic load balancing and allocate objects to specified processors, by using the OPENDEVICE or OPENGLOBAL calls, while OPENREMOTE invokes a partially automatic mechanism where you explicitly send many object
s to a particular processor but let Taos distribute them automatically from there. For example, you could specify that a 1000-process ray-tracing calculation should be run by sending groups of 100 objects to 10 different processors, with Taos completing the distribution.
The Parallel PC
Although Taos can support its own file and display systems, the current release version is PC-hosted, using the MS-DOS file system and an SVGA graphics adapter for display. I received Taos on six 1.44-MB floppy disks, although more than three of these were filled with bit maps and MPEG animations. I was able to run Taos happily on my 486DX2\66 Elonex PC as a single-processor operating system, coexisting on the same hard disk with Windows (though hardly surprising, it would not run under Windows).
Taos comes with a very simple GUI whose look and feel is loosely modeled on Motif. Control objects that you store in the Taos/Control directory automatically appear on a pop-up menu from where you can execute them wit
h a mouse click. To supplement this GUI, you can open a shell window and use a command-line interface, with a syntax that resembles DOS. But unlike DOS, Taos command lines represent genuine pipelines in which each successive command launches a separate process whose output is fed to the next.
The most immediately striking attribute of Taos is its blazing graphics speed; you can grab a window in which an image is being ray-traced and whirl it vigorously around the screen while tracing continues unhindered. The GUI, which is packaged as a Taos class object, works with a device-independent virtual screen with only two hardware-dependent primitives to put and get bit maps to the real screen. Apart from SVGA adapters, Tao Systems currently implements the GUI for several of Inmos's graphical TRAMs (transputer modules). Processes running on remote processors can open screen windows by sending messages to the processor running the GUI, rather like a lightweight version of the X Window System.
In additio
n, Taos encapsulates the MS-DOS filing system within its own object model so that DOS hard drives are mapped into Taos servers; therefore, you can send messages about the objects the servers hold. For example, a control object called Trace.Ctl, which is referenced in Taos by the message \@PCI\Control\Trace, is simply the DOS file C:\Taos\Control\Trace.Ctl; @PCI is a Taos server object that aliases my C:\Taos directory.
Taos Directions
At present, Taos is deficient in the sort of development tools that Unix or DOS programmers expect to find--the small Taos team has devoted most of its time over the last two years to getting the kernel and VPcode translation system robust and to building a variety of graphical tools for manipulating and displaying ray-traced images and MPEG animations, all written directly in VPASM assembly language. There's a BASIC compiler that uses a QuickBasic-like dialect but as yet no C compiler; however, there is a library called the Taos HLL Toolset, accessible from VP assembl
y language or BASIC, which provides the functionality of the ANSI C library including malloc, sprintf, fscanf, and others. Work is under way on an in-house C++ implementation.
The much hyped "multimedia revolution," which puts a new premium on inexpensive but high-performance graphics, may prove to be a window of opportunity for Taos. SGS-Thomson/Inmos has made a technology sharing agreement with Tao Systems to use Taos on its next-generation processors (code-named Chameleon) in the games, visualization, and multimedia markets.
Tao Systems is negotiating with a large Japanese communications corporation, which is evaluating Taos as an operating system for the TV set-top boxes that will control the new domestic multimedia services. These units will have to decrypt, decompress, decode, and otherwise mangle real-time data streams for "video-on-demand," videophone communications, and other services yet to be invented. This will require large amounts of processing power but must be delivered at domest
ic electrical-appliance prices. A small, hardware-independent parallel operating system begins to look very attractive; you can shop around for this week's best processor deals and issue inexpensive upgrade cards to provide more processing power.
Company Information
Tao Systems
P.O. Box 2320
London NW11 6PW
U.K.
+44 81 905 5708
Illustration: Listing: VPcode at Work
A sample tool written in VP assembly language. This tool changes the backdrop picture shown on the Taos GUI desktop to another bit-map file that you select from a browse window.
include "tao.inc"
node bproc,CONTROLTP,0,TEMPLATE
control 0,1024,DATATP,0,0,0,0
component plmthd2-bproc
compend
tstring plmthd2,"DESK/BACKDROP"
nodeend bproc
node tl_b,TOOLTP,VP,TEMPLATE
tool "DESK/BACKDROP"
;inputs
;r6=control object pointer
allocstruct 80,r7
loop
;request filename from user
cpy r7,r0
lea bpath,r1
qcall GUI/GI_BROWSE
breakif r8=0
;GUI will be parent
inquire "BACKDROP",0
breakif r8=0
;send name to backdrop
cpy r7,r1
qcall LIB/PA_SEND
endloop
freestruct 80
ret
string bpath,"BITMAPS/*.TBM"
toolend tl_b
nodeend tl_b
end
Illustration: The Taos operating system runs on a virtual processor. Hardware-specific kernels translate Taos VPcode into native code. The virtual processors communicate using an object-based message-passing system.
Illustration: Bearing a passing resemblance to Motif, the Taos GUI is actually a class object that requires just two hardware-specific primitives to work with any display type.
Dick Pountain is a BYTE contributing editor based in London. You can reach him
on the Internet or BIX at
dickp@bix.com
.
Parallel Course
