{This material originally appeared in the July, 1994 issue of Byte magazine, a McGraw-Hill publication} The Taos operating system uses objects from the ground up to enable processors based on different architectures to work together on the same problem Nowadays many computers can generate pretty ray-traced images, and some of them can even do it fast. What impressed me about the demonstration I was witnessing was that it was running on a no-name 486 PC clone with some co-processor boards in it, not a Silicon Graphics workstation. On the other hand parallel-processing accelerator boards for PCs are not exactly new - no, what made the event REALLY special was that the PC contained an Intel 486 CPU, four Inmos T800 transputers and four MIPS R3000s, and it was running the same binary ray-tracing program in parallel on all of them at once. What made this feat possible was Taos, a radically different, object-oriented parallel operating system. Most operating systems are created either by large hardware manufacturers or by university researchers, but Taos came from neither - it's the product of a devoted group of enthusiasts with an idea that was well ahead of its time. The principal architect of Taos is Chris Hinsley who was a professional games programmer, with hit titles for the Atari ST and the Commodore Amiga to his credit. Although writing solely in assembler, Hinsley devised his own object-oriented development style based on macros, which sparked the original idea for Taos. (Incidentally you pronounce its name 'dowse' like the Chinese religion rather than the New Mexico town). Fired by the launch of Inmos's Transputer, 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 Byte International some four years ago it seemed outrageously far removed from the mainstream, but the rest of the commercial operating system world is catching up. Everyone wants a micro-kernel now, but Taos is already a nano-kernel system, with its tiny 12 Kbyte kernel running on each processor in a parallel network. Taligent promises objects-from-the-ground-up with dynamic binding; Taos has had them from the start. However Taos doesn't really aspire to mainstream desktop status, but is rather a fast-and-skinny system for embedded applications and Tao Systems is now promoting it into the multimedia and games console markets. VPCODE By far the most radical aspect of Taos is it's hardware independence. Taos programs are all written in the machine code of a virtual processor (VP), 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 runtime penalty, unlike earlier interpreted systems like the UCSD p-system which were very slow. Taos's fine-grained object orientation and dynamic binding makes this translation strategy feasible since VPcode modules are always small (typical a few hundred bytes) and so 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, though Tao Systems' translator supremo Andy Henson did stress to me that a fast modern CPU can actually translate VPcode faster than the hard disk can transfer data. The imaginary VP processor 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 floats. Hence the VP machine 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 and a few special pseudo-instructions, like TAO which calls Taos kernel routines, and LIT which marks literal data that needs to be translated (eg. from little to big-endian). The Taos assembler VPASM outputs VPcode, which you can run directly or you can invoke the appropriate translator manually to convert it to native code (Text box 1 shows a sample of VPASM source code). Currently Tao Systems has translators for the Intel 286, 386 and 486, the Inmos T8 and T9000 transputers, MIPS R3000 and ARM 601. PowerPC and DEC Alpha are next in the pipeline; it takes around 6 man-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 communication 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 variably-sized blocks of contiguous memory called 'nodes' which contain 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, though you can implement such type-checking at a higher level within an Object-Oriented programming language. While stored on disk, or in transit over a communications link, nodes exist as unbound 'templates' but once 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 pre-defined system object types are Tools, Control Objects, Bitmaps, Graphical Objects and Class Objects but programmers are free to define new types. A Tool is a node containing executable code that can act upon 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 which are executed in sequence. Control objects are the smallest unit of parallel distribution and execution under Taos, but not the smallest unit of memory management since individual tools can be retrieved from disk and made process-ready. The kernel which 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 it and one to clean 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 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's needed and only one copy is ever present in memory. The Taos processes which 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 multi-threaded fashion. Class objects provide the highest level of organization under Taos. A class encapsulates a group of message-passing objects which 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, for example to open a new window, and are shielded 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 Kbytes in size and is responsible for multi-tasking (via a time-sliced process scheduler), memory-management, and the mail and naming systems. Tao Systems is currently working on a POSIX compliant version of the kernel which implements virtual memory and memory protection on microprocessors that have suitable MMU hardware, but the 12 Kbyte version does not offer these features. All executable code in Taos is contained in tools, apart from the small bootstrap loader on each processor which must be in native code). Even the kernel itself is built from tools and is largely written in VPcode. Device drivers are simply processes like any other, running outside and in parallel with the kernel. All message I/O is handled by link drivers running outside the kernel, though the kernel handles some local I/O support mechanisms such as data cacheing. The lifetime of a Taos tool in memory is determined by its status, according to four different degrees of volatility: 1) VIRTUAL tools are only loaded, translated and bound when called by another tool, the translated code remaining in memory until the tool's reference count (kept by the kernel) falls to zero, after which it may be flushed whenever the kernel needs memory. The kernel may relocate a virtual tool at any time; 2) NON-VIRTUAL 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) SEMI-VIRTUAL tools are only loaded and bound when called, like virtual tools, but they then remain in memory like non-virtual tools; 4) Non-virtual tools can also be flagged as EMBED, which causes the translator to embed them as inline code in their caller's code. This is a speed optimization which is extensively used in the kernel code. A process called the Migrator, running outside the kernel, is responsible for actually relocating objects in memory and for incremental garbage collection. MESSAGES Since 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 non-blocking 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 which executes the object. The new control object can then send mail to any other object whose mailbox address it knows, which will always include its own parents and children, and named resources like disk drives and VDU 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 typed, with 16 reserved types used by the kernel that include arrays, streams and executable code; error and debugging data; 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 (eg. 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 contains 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 communication links from user programs (though real-time performance issues may sometimes intrude). In the PC demonstration I mentioned at the start of this article the transputers were connected via their serial links, while the MIPS R3000 chips were connected together though FIFO chips, and all of them talked to the 486 host CPU via the PC's VL local-bus. PARALLEL PROCESSING Taos is a fully distributed operating system which 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, controlled by a distributed load-balancing algorithm. Text Box 2 lists some of the Taos kernel calls, and if you examine the subsection on 'control object management' 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 communication channel. At boot-time each link driver benchmarks the processors to which it's attached (by timing the VPcode translator) and this number is 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 outwards and asks "is there one of my nearest neighbours 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 'gullies' or lowest points 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 runtime so that if a new processor is added to the system, news of its existence spreads outwards 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 a number of objects 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. TAOS ON A PC Though Taos can support its own file and display systems, the current release version is PC-hosted, using the MS-DOS file system and a SuperVGA graphics adaptor for display. I received Taos on six 1.44 Mbyte floppies, though more than three of these were filled with bitmaps and MPEG animations. I was able to run Taos quite happily on my 486DX2/66 Elonex PC as a single processor operating system, coexisting on the same hard disk with Windows (though hardly surprisingly it would not run under Windows). Taos comes with a very simple GUI whose look-and-feel is loosely modelled on Motif (fig.2). Control objects which you store in the taos/control directory automatically appear on a pop-up menu from where you can execute them with 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. However 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 to a device-independent virtual screen with only two hardware-dependent primitives to put and get bitmaps to the real screen. Apart from SVGA adaptors 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. Taos also encapsulates the MS-DOS filing system within its own object model, so that DOS disk drives are mapped into Taos servers which you can send messages about the objects they hold. For example a control object called TRACE.CTL which is referenced in Taos by the message \@PC1\CONTROL\TRACE is just the DOS file C:\TAOS\CONTROL\TRACE.CTL; @PC1 is a Taos server object that aliases my C:\TAOS directory. THE FUTURE OF TAOS At present Taos is very deficient in the sort of development tools that programmers under UNIX or DOS 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 assembler. There's a Basic compiler which uses a QBasic-like dialect but as yet no C compiler - there is however a library called the Taos HLL Toolset, accessible from VP assembler or Basic, which provides the functionality of the ANSI C library including malloc, sprintf, fscanf and all the rest. Work is underway on a in-house C++ implementation. The much hyped 'multimedia revolution' which puts a new premium on cheap 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, visualisation and multimedia markets. Tao Systems is presently 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 domestic 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 cheap upgrade cards to provide more processing power. Dick Pountain - 08/03/94 15:04 -------------------------------------------------------------------- CONTACT: Tao Systems PO Box 2320, London NW11 6PW, England ------------------------------------------------------------------- TEXT BOX 1. An example tool written in VP assembly language. This tool changes the backdrop picture shown on the Taos GUI desktop to another bitmap file selected by the user from a browser 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 enquire '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 ------------------------------------------------------------------- TEXT BOX 2. TAOS KERNEL CALLS This selection from among the 64 Taos kernel calls gives some impression of the kind of services that the kernel provides. Mailbox Management SENDMAIL Send a mail message COPYMAIL Copy a mail message then send the copy READMAIL Read a mail message from a mailbox READTYPE Read a mail message from a mailbox; wait until specified type arrives Control Object Management STARTCONTROL Start a control object locally OPENCONTROL Create a control object and start locally OPENCHILD Create, distribute and start a control object in the network OPENARRAY Create, distribute and open a number of different control objects OPENFARM Create, distribute and open multiple instances of a control object OPENDEVICE Create and transport a control object to a specified processor and start it OPENGLOBAL Create, distribute and open multiple instances of a control object. Guarantee one control object on every processor OPENREMOTE Create and transport a control object to a specified processor for distribution from that processor, then start it OPENPIPE Create, distribute and open a pipeline of control objects Tool Object Management VCALL Virtual Call tool object OPENTOOL Request tool object load CLOSETOOL Close tool object FLUSHNAMES Flush named tools from local tool list FLUSHTOOLS Flush un-referenced tools from local tool list UNCLOSETOOL Increments a tool object's reference count General Object Management VADDR Obtain address of embedded object OBJPROC Process an object using the existing thread LISTPROC Process a linked list of objects using the existing thread LISTTEST Search list for types of node Processor Type Identification & Mailbox ID FINDTYPE Enquire processor id of a processor node of specified processor type and with a minimum memory requirement GETMYID Enquire mailbox id of own control object GETPARENT Enquire mailbox id of parent control object GETSERVER Enquire server mailbox id for an object NETINFO Enquire processor and network information |
 |
Home > Byte Articles >
Parallel Course (July 1994) |