From BYTE Magazine, January 1991. Copyright 1991 by McGraw-Hill, Inc. cunningham-lee.com CONTENTS
BeOS Diary
cover F E A T U R E

     

THE
OBJECT-ORIENTED
AMIGA EXEC


A close look at the object-oriented core of the Amiga operating system

Tim Holloway

Object-oriented is the computer buzzword for the early 1990s. It's the latest Holy Grail, which will let programmers leap tall buildings in a single bound, cure world hunger, and produce 100,000 lines of fully debugged code a day.

    Well, maybe not. After all, AT&T invented one of the premier object-oriented programming languages, C++, and was unable to get release 2.0 out within a year of its predicted release date. Nevertheless, there is no question that OOP is a Good Thing, and producers of operating systems have been furiously recoding their products as object-oriented systems, generally using C++.

    Yet there is one object-oriented operating system that has been in widespread use since 1985. It runs Commodore's Amiga, although, ironically, it was not written in an OOP language.


Amiga Exec--An "OOPS" Design

The Amiga's operating system is sometimes incorrectly referred to as AmigaDOS. Actually, the Amiga operating system has three major components: Exec, the multitasking kernel AmigaDOS proper, which provides the high-level file systems and Command Line Interface; and Intuition, the basis for the graphical user interface (GUI). I'll be discussing only the Amiga Exec. Of the three, it is the most object-oriented and the nost comparable to the C++programming language.

    That may seem surprising. Aren't GUI's what made OOP so famous? Well, yes, but there's more to OOP than simply dealing with data objects that correspond to graphical images. More on this later.

    Although many Amiga features have a potentially unlimited number of elements, the absolute minimum RAM that the Amiga system software requires is a fraction of what many comparable systems require; even counting the ROM part ofthe operating system, the memory consumed is only about 512Kbytes (although newer Amigas can support larger ROMs).

    So what's missing from the Amiga operating system that makes it so small? How does the Amiga manage to provide multitasking and windowing services in less than one-half tc one-fourth the memory that Apple and IBM computers need? The answer lies in minimal redandancy.

    If you examine the internal structure of many popular operating systems, you'll discover that it's "OS versus them." That is, you have this somewhat monolithic block of stuff that is the core operating system, some additional voodoo acting as device drivers and the like, and applications code--and only an uneasy truce ever lets them meet. Even though the operating system may itself be composed of many components, its appearance to the applications programmer is still essentially as a rather mysterious edifice, beyond which only selected portions of applications software may go.

    The Amiga operating system is different. Relatively few parts of it are totally opaque; in fact, with later revisions of the operating system, the trend has been to further open its internals for applications use. This is even more surprising considering that, unlike the Macintosh, the Amiga runs its applications in the nonprivileged state.


No Magic

Most present-day operating systems operate as if the operating system code is "magic"; that is, it spends most of its time running in privileged states, inhibiting interrupts, executing arcane instructions that are incomprehensible to mere mortal applications programmers, and otherwise doing things that are completely outside the scope of applications programming. That isn't really true.

    Very little operating-system code is truly magic; most of it deals with managing tables, lists, queues, and other such mundane tasks. However, since these are operating-system tables lists, queues, and so forth, they are generally managed with special routines that run in privileged, noninterruptible, memory-managed, or otherwise arcane environments.

    What tends to be overlooked is that it is often possible to take all the "magical" parts of code and separate them from the "nonmagical" parts, resulting in a set of controlling routines to switch modes, and a lot of data-handling routines that look suspiciously similar.

    This situation means that, first, there exists the possibility that general-purpose versions of some of these routines can be created to replace all these similar-but-not-identical functions; and second, since these routines are no longer magic, they can be accessible to application programs as well, reducing their overall size and complexity, to say nothing of the time saved by using pre-debugged code.

    Using general-purpose code for critical operating-system functions might seem like heresy to some--after all, aren't "general-purpose" and "efficient" mutually exclusive? The answer appears to be no, or more accurately, "If it's general-purpose and it's not efficient, perhaps it's not general-purpose enough." What usually wastes time in general-purpose code is all the testing and branching that it has to do to handle the variations of data structures it processes.

    Where does OOP come into all this? The answer lies in the principle of inheritance. By arranging the system data structures much as we did for system code in traditional systems and by placing related data items in a common sequence, we gain two advantages: a reduction in the amount of special-case processing that was so offensive, and the creation of a hierarchy of data object classes. As a side effect, the system becomes easier to understand--there are fewer unique functions.


An Inside View

Exec, as mentioned earlier, is the nucleus (or kernel) of the Amiga operating system, and it is realized in just such a manner. Exec consists of a collection of increasingly complex object classes, as can be seen in figure 1. When a new Exec object class is defined based on a simpler class, it contains all the data objects of the simpler class and also is (usually) valid for not only operations defined for that class, but for all operations pertaining to the simpler class, as well. This is known as function inheritance.


Inheritance Figure 1: The nucleus of the Amiga's operating system consists of a collection of increasingly complex object classes.

    Exec's heavy reliance on inheritance is what makes it so compact. It does not contain separate sets of routines to manipulate tasks, I/O devices, intertask messages, and so on; instead, it contains basic routines to handle collections of objects--be they task objects, device objects, or whatever--and adds functions only where additional support is required. In contrast, many operating systems contain a collection of task routines (including those required to manage the task table) and a collection of device routines (including those required to manage the device table), and so forth.

    There are many ways to represent collections of data internally, each with its own advantages and disadvantages. Exec is based on the doubly linked list. The list elements are allocated dynamically from anywhere in RAM that's convenient (see the section on memory management); therefore, there are no tables to fill up. On the other hand, access speed is highly dependent on the number of nodes in the list, but there are ways to reduce that problem, as I'll explain later.

    The Amiga operating system distinguishes itself in that the operating system itself provides support for doubly linked lists. Exec supports two levels of lists: lists and MinLists. (The Lattice C++ implementation adds two more that are similar to the standard Exec lists, but without automatic initialization.) These are used to define items that the Amiga system software initializes.

    The MinList is the anchor to a doubly linked list of MinNodes. MinNodes contain next and previous MinNode pointers. The MinList structure contains a pair of dummy MinNodes to simplify processing by reducing special-case logic required to process items at the ends of the list. An empty MinList always consists of two MinNodes--the dummy nodes at the front and the end of the MinList--both of which are contained within the MinList data structure itself. The dummy front node's next-node pointer points to the actual first node of the list. Its previous-node pointer is always NULL.

    A similar situation exists in regard to the dummy end node. Since the dummy front node's previous-node pointer is always NULL and the dummy end node's next-node pointer is also always NULL, it was possible to save a small amount of memory by making them overlap by sharing the same NULL pointer. Dummy MinNodes do add one complication: The last actual item of the list is not the one with the NULL next-node pointer: That honor belongs to the dummy node.

    A complete set of functions exists to support insertion and deletion of MinNodes at either end--or points in between--of a MinList. By using the proper functions, therefore, a MinList can be used as a first-in/first-out (FIFO) (also known as a queue) or as a last-in/first-out (LIFO) (also known as a stack), as well as a general-purpose list.

    Once again, note that there is nothing magical about MinLists, MinNodes, or any of the functions that act on them. Although they are extensively used by the Amiga operating system, they can be used just as freely in any application program.


Friends and Members

A note about C++ friend and member functions. When a class is defined in C++, its internal components are (unless otherwise specified) protected from casual access. This is a strong selling point; it makes it harder for an object's innards to be corrupted and easier to locate the responsible function. To make practical use of (and to alter) the information within a class object, therefore, some sort of access mechanism is required. C++ provides two: a friend function, which is like a traditional C function, except that by having been declared a friend of one or more classes, it is allowed to directly access the data stored within that class or classes, and a member function which is actually owned by a specific class and therefore has an "invisible" extra parameter passed to it: "this," which is a pointer to the class object being acted on.

    Exec was designed to be used by non-OOP languages; thus the Exec functions are, in effect, friend functions. The #include files made up by MTS Associates to support C++ on the Amiga generally define them as such. However, to better support Exec in its capacity as an object-oriented system, a number of member functions were also defined. For example, virtually every object in the Amiga is in some sort of list, so most objects have a member function named next(). No matter what it is, no matter how it's linked, and no matter what the name or relative location of the object's next-item pointer, you are thus always guaranteed that you can get a pointer to the next one in the list by using the next ( ) function.


Lists: MinLists and Then Some

A list is an extended MinList, made up of nodes. The nodes are MinNodes plus a 1-byte type field, a 1-byte priority, and a pointer to the node's name, which is a C-format string. Figure 2 shows the structure of a node. A node incorporates the structure of a MinNode, and thus automatically inherits the properties of a MinList to form a list.

    Subsequently, a list can use all the MinList functions. A list can be maintained as a FIFO or LIFO, just like a MinList. However, a list can also be maintained in priority sequence courtesy of the list friend function Enqueue( ). If the nodes in the list are given names, it is also possible to search the list for the first/next node of that name. This can be very useful, as it's how Exec locates a number of public objects.


Signals

Signals are represented by a 32-bit word containing a pattern of signal flags. There are 16 that are allocatable to the user and 16 reserved by the operating system. When a task signals another task and the other task is in a signal wait state, the receiving task's incoming signal information has the incoming signal bits logically ORed in. This is then ANDed with the recipient task's pattern of signals that it is waiting on. A nonzero result causes the task to become dispatchable.

    This is an extremely efficient way to activate a sleeping task and it can be done at any system level, including in interrupt routines, which are denied many of the more sophisticated system services.


Messages

Figure 3 shows how a message is constructed from a node. Messages are extremely important in the operation of the Amiga. They are used to pass information from task to task, as the basis for I/O requests, and as the medium of transfer for Intuition's mouse and window events. Unlike a signal, which can merely give an "I'm here!" indication, a message can have complex information piggybacked on it.


Figure 2: Nodes can be located by name and arranged in priority order. Nodes are anchored by lists. Since a node incorporates a MinNode, it inherits all the list properties and functions.
Fig. 3
Figure 3: The Amiga operating system uses "messages" to pass information from task to task, as the basis for 1/0 requests, and as the medium of transfer for Intuition 's mouse and window events. A message incorporates a node and therefore inherits all its properties and functions.
Fig. 4
Figure 4: A message is transmitted to a message port, which contains a list of incoming messages to be serviced, in priority order. Like messages, message ports incorporate a node and therefore inherit all the properties and functions of a node.

    A message is an extended node and is usually transmitted to a message port (MsgPort), another type of node that contains a list of incoming messages to be serviced, in priority order (see figure 4). MsgPorts can be private and anonymous, or they can be added to the system message port list. Frequently, they occur in pairs (one of each), since after a message is serviced, it is common to forward it to a reply MsgPort, where it is generally recycled or discarded--although it is possible to bounce a message through a whole series of ports. There are several different ways to implement a MsgPort, but the most common way is supported by a special C++ class named the StdPort--or standard message port--which can be created and initialized by coding

StdPort *listener = new StdPort ( "I hear you" ) ;

    The StdPort constructor takes care of all the details of standard MsgPort initialization. Memory is allocated and initialized, and a signal is acquired on which the listening task can wait. Using the AddPort function, the MsgPort can be put on the system's public MsgPort list, where it can be found by any task that wishes to send it a message. Because Exec was designed in an object-oriented manner, the new operating-system functions are quite simple. A C++ reconstruction shows the following:


void AddPort ( MsgPort *mport )
{ Forbid( ) ; // disable task-switching
Enqueue ( AbsExecBase->PortList, mport ) ;
Enable( ) ; // re-enable task-switching
}


Here's a reconstruction of another system function:

MsgPort *
FindPort ( const char *portname )
{ return ( MsgPort *)
    AbsExecBase->PortList.find ( portname ) ;
}

    FindPort illustrates another important design feature. If you searched a system list every time you wanted to access an element in that list, system performance would suffer. Instead, the convention is to search and return the object's address. Thereafter, the object's address can be used directly (the Amiga does not use Macintosh-style handles, which cause objects to shift about in memory). The downside of that is that you must never move or remove an object that other tasks may be using. Libraries and devices ensure this by maintaining a user count. For simple message ports, the application should either enforce a log-in/log-out facility or else require that all messages be sent on a one-shot basis (i.e., FindPort / PutMsg).

    Each task is limited to a maximum of 32 distinct signals but can have an unlimited number of MsgPorts. The same signal can be used by more than one MsgPort, which is what keeps Intuition tasks from being limited to a finite number of open windows.


If you examine the
internal structure of many popular
operating systems, you'11 discover
that it's "0S versus them."


IORequests

IORequests are extended messages that include I/O control and transfer information sent to devices. A basic set of commands (read, write, control, and so on) is common to all IORequests; for a given device, additional extensions can be added as needed. A number of special-purpose device IORequest classes have been derived; any device implementer is at liberty to derive his or her own extensions as needed. It's fairly common to end up with something like the following:

MyDeviceRequest is based on:
 StdIORequest is based on:
 IORequest is based on:
 Message is based on:
   Node is based on:
     MinNode

With each level of inheritance, you gain additional properties and functions. The only new code required is that which supports your own unique class of object.


Libraries

Another important type of node is the library. It consists of a base structure, preceded by function vectors and followed by optional private storage. There is a set of basic functions (e.g., open, close, and expunge) common to all libraries. Beyond that, the designer is free to add functionality at will.

    Unlike most operating systems, the Amiga operating system does not use software interrupts or illegal instruction traps to provide operating-system services. Instead, there is a master library, named exec.library, located in the ROM kernel. All the fundamental system functions--the list primitives, memory management, functions to load and open libraries (the libraries' own internal initialization and open routines are called from this)--are defined here. The only immutable part of the operating system is absolute memory location 4, which points to the Exec library structure (ExecBase). The data portion of ExecBase contains the fundamental Exec structures, including the list definitions for the system message ports, libraries, devices, and tasks.

    It's interesting to compare Exec libraries with the dynamic link libraries used by OS/2 and Microsoft Windows. DLLs support sets of functions, but they provide additional services as well. The Intel 286 and subsequent chips support the concepts of different levels (rings) of security. If you don't hold the requisite minimum security level, a request will fail. DLL function dispatching can cause security-level switching. The Motorola 68000-series equivalent of this is the Module Call facility. It, however, requires at least a 68020 microprocessor unit and preferably a paged memory management unit. AmigaDOS runs on all 68000s, so the only security levels inherently available are due to the fact that AmigaDOS programs run by the default user state, whereas the operating system runs in supervisor state, as required.

    There are pros and cons to both approaches. Since Exec libraries are essentially simple vector tables, the overhead of calling library functions is barely higher than when the function is resident in the calling program (much less than a software interrupt), instead of being shared system code. On the other hand, a carefully designed DLL, while incurring a small speed penalty, is more immune to damage from programs that have run amok.

    Note that DLLs are extensions to the Microsoft operating systems; the basic system functions are still software-interrupt driven. Hence, there has to be logic for both kinds of library interfaces. Amiga libraries, however, not only provide a single interface, but they are immune to the problem inherent to all software interrupts--there's only a finite number of them, which never seems to be enough for practical purposes. Libraries, on the other hand, are not only "infinitely" expandable, but it is a straightforward task to create new ones that are indistinguishable from the built-in ones--or even to completely override a built-in one by inserting a new library of the same name at a higher priority on the system library list.

The Amiga operating system
is unusual in that it doesn't partition
memory for applications.

    The library concept is itself extended; it forms the basis for an I/O device by adding a few standard functions. Most devices work via extended messages, called IORequests. There are also extensions to these extensions (such as the StdIORequest), as well as customized extensions for specific devices. Devices typically also possess one or more tasks so that I/O can be done asynchronously, although this is not mandatory.

    There is another, less-understood extension to the library, called the resource. A resource essentially acts as a coordinator for shared resources (generally hardware), such as the different drives on a disk controller, or the serial and parallel I/O ports (whicb are implemented on the same chips).


Tasks

The task structure is yet another node. This one contains all the definitions required to make Exec a fully functional, preemptive, priority-driven, multitasking operating system. A task is roughly equivalent to an OS/2 thread. An extended task, known as a process, provides additional information to permit use of the AmigaDOS functions defined in the library named dos.library--chiefly such things as Unix-like I/O services, program loading capabilities, and the like.

    Exec's task scheduler is not as elaborate as OS/2's, which is rumored to have been lifted bodily from IBM's VM/370 mainframe operating system. The OS/2 dispatcher dynamically adjusts task priorities based on certain algorithms that are in the "magic" part of the operating system. While this is impressive, it's doubtful that a single-user operating system needs it. No matter; you're stuck with it. About the best you can do is turn it off, but it still eats up real memory.

    Exec gives good performance with a simple time-slice dispatching algorithm. More complex custom algorithms can be attached in a straightforward manner, if required. This can be done safely (and in a release-independent manner) on the Amiga, because both the dispatcher functions and task lists are accessible via well-defined interfaces.

    Nothing in the basic design of Exec actually requires only a single CPU to be present in the system. Exec could be implemented in a multiprocessor system if access to system lists were properly serialized. Amiga 2500 systems contain a 68000 and a 68020 (or 68030). At present, one or the other is put to sleep at boot time, but there are possibilities here.


Semaphores

Originally, serialization in Exec was done either by the Forbid( ) function, which prevents other tasks from being dispatched, or Disable(),which switches off interrupts. However, this serializes the entire system. For serializing access to a specific resource, semaphores are better.

    There are two kinds of semaphores in Exec. A SignalSemaphore is based on a MinNode. It provides high-performance serialization but has restrictions on use. A semaphore is based on the message system and can be used in more general situations. Either type of semaphore is preferable to the cruder Forbid()/Permit() or Disable()/Enable() functions, both of which reduce the amount of multitasking that can be done while serialized on the resource.


Interrupts

An interrupt is a data structure that points to interrupt-handling code, plus any working storage it might require. To allow for more than one task to handle an interrupt event, interrupts are nodes. The exact handling of interrupts varies, depending on the type of interrupt.


Memory Management

The Amiga operating system is unusual in that it doesn't partition memory for applications, or even the operating system itself. Instead, it maintains a free memory list where each chunk of free memory has certain attributes, and requests are matched against them. Thus, no application runs out of memory until the system itself runs out of memory, and there is no requirement to juggle segments or, as with the Macintosh, compact memory.

    A set of low-level functions can be used to acquire and free memory, but Exec also provides a set of functions to manage memory within pools acquired by the application. This has several advantages: less overall memory fragmentation, lower overhead (since the entire pool can be released as a unit, instead of piecemeal), and the ability to preallocate enough memory for applications that have a lot of dynamic memory usage.

    There is no system-memory-in-use list. If an application fails and doesn't have a cleanup routine, or if the programmer neglects to free all acquired memory, it's lost until the system is rebooted.

    Exec memory management supports both bank-switched memory and virtual memory. Memory allocated with the MEMF_PUBLIC attribute is guaranteed to always be visible to all tasks, interrupt routines, and the system supervisor. Memory on the application's stack or allocated without this flag has no such guarantee. With a minimum of 8.5 megabytes of RAM, neither virtual memory nor switched memory cards are in widespread use, so it's likely that many applications will fail should this situation change.

    All the other components of the Amiga's operating system--AmigaDOS, Intuition, the WorkBench, the system's unique built-in animation routines, and so on--all ultimately depend on the services of Exec. Exec is compact, efficient, flexible. reliable, and expandable. And no other system I've ever worked with has been so easy to work with. I like that.


BIBLIOGRAPHY

Commodore staff. "Amiga ROM Kernel Reference Manual: Exec." Reading, MA:Addison-Wesley, 1986.
Sassenrath, Carl. "Guru's Guide to the Commodore Amiga: Meditation #1--Interrupts." Ukiah, CA: Sassenrath Research, 1988.


Tim Holloway is president of MTS Associates, a system software development firm in Jacksonville, Florida. He can be reached on BlX as "tholloway."

From BYTE Magazine, January 1991
Copyright 1991 by McGraw-Hill, Inc.