Bill is a software engineer at Lynx Real-Time Systems and vice chair of the POSIX.4 committee. He can be reached at 16780 Lark Ave., Los Gatos, CA 95030, or via e-mail at bog@ lynx.com.
The federal government's recent push for computing standards is producing some major headaches for developers of systems and applications. Three principal requirements of the U.S. federal market are: Support for the Ada programming language; support for real-time performance; and support for Unix. In the past, government contracts have not frequently needed all three of these standards requirements fulfilled in the same contract.
However, the recent contract for supplying the on-board systems for NASA's Space Station Freedom called for the IEEE POSIX 1003.4 standard real-time extension and specified that the operating system also run Ada programs efficiently. If this indicates a trend, it means that software vendors will find an increasing need to supply Ada, Unix, and real-time all at the same time.
This spells headaches for developers. Why? Because of two well-known inequalities. The first is "Unix!= Real-Time Performance." The second, and less well-known, is "Unix!= Ada".
Although it is a fine general-purpose time-sharing system, Unix was never designed for real-time performance, and suffers from serious limitations in this area. Unix can cause large delays to high-priority tasks that need to respond to events external to the computer. This added delay is highly variable and unpredictable, and varies from vendor to vendor, from process to process, and even from one process invocation to the next.
Because Unix is designed to support a number of different users at the same time, it tries to be fair to all of them. Process priorities in Unix drift in an effort to equitably timeshare the processor(s), and to improve the performance of I/O-bound processes. By contrast, process priorities in many real-time applications must be immutable, and the highest priority processes must always be the ones running on a given processor.
Unix does not allow direct control of critical shared resources. In comparison, the real-ti e programmer (or user) needs to have substantial control over the system, including absolute control over priorities and which task can run on a processor at a given time. Most important, the system must be able to respond to critical external events quickly and in a predictable amount of time.
It is less widely known that typical Unix systems are capable of supporting only a crippled Ada implementation. While Ada was designed to deal with both real-time constraints and concurrency, Unix was not. Standard versions of Unix lack certain features necessary for optimum Ada processing: a non-time-sharing scheduler, asynchronous I/O, reliable event notification, and fast mechanisms for interprocess communication.
Although there are Ada implementations that run on standard Unix, these are crippled, clumsy, and inefficient.
For example, an area in which these implementations fall short is tasking. Many versions of Ada implement tasking on top of the Unix process model. In the actual application code, "tasks" are implemented by a user-level scheduler switching between different program counters and instruction pointers. Although this has the advantage that switching tasks happens without going into the kernel for a context switch, when one thread enters the kernel and blocks -- for instance, when reading from a disk file -- all the tasks in the Ada application are blocked. This is because the underlying Unix process that runs the user-level scheduler is blocked waiting for the I/O. Standard Unix has no concept of tasks, so on these systems, tasks will always be second-class citizens.
Other implementation use a one-to-one mapping between Ada tasks and Unix processes. The problem here is that Ada task priorities can't be respected because the underlying Unix priorities used to implement them will drift, according to the fairness calculation invoked every few system ticks by the Unix scheduler.
Ada programs also require efficient methods for intertask synchronization. Ideally, the operating system should provide semaphores that can effect a lock in three or four instructions, without having to enter the kernel. In contrast, the locking methods used in standard Unix (such as System V semaphores, or using the fcntl( ) function) require kernel entry with each operation. It seems that many of the incompatibilities between Unix and Ada stem from the fundamental difference between their respective processing models.
Ada supports the concept of multiple threads of control in a particular program, generally known as "Ada tasking." The two terms, "task" and "thread," are often used interchangeably, although not always correctly.
A straightforward way of implementing Ada tasks is to create one operating system thread to run each task. However, greater efficiencies in task switching can be achieved if multiple Ada tasks are supported by each thread, because in such a case, we can schedule tasks without involving the kernel. In subsequent discussion, I'll assume that Ada tasks are mapped one-to-one onto operating system threads.
Each thread can be thought of as a unique set of machine registers -- a different stack pointer, a different program counter. Threads within an Ada program run concurrently. While one thread may be at a particular assignment statement, another may be off updating the display, while a third is waiting for a disk write to complete. These threads operate as separate subprocesses within the application.
It is useful to think of multiple-threaded applications (Ada) as a natural extension of single-threaded applications (Unix). However, there is one significant difference. In a multithreaded system, there is no asynchrony visible to the programmer. In single-threaded Unix, there is still the need to do multiple things in parallel. This need has historically been supported using multiple Unix processes and a couple of well-worn hacks. The most well-known is Unix signals. Another is the use of the O_NONBLOCK flag on files to avoid indefinite waits for I/O. These workarounds are discussed in the next section.
A standard Unix process is a single "flow of control" -- a single line that goes through the code as time progresses. This is the line you're thinking of when you debug your single-threaded programs: "Okay, we're here at the assignment statement, now we drop through into this case statement...." The line is characterized by the contents of the machine registers at any point in time -- especially the program counter.
One thing happens, followed by another. Other things, by and large, do not happen in parallel with this single flow of control. Over the years, ad hoc mechanisms for handling concurrency have evolved on Unix: the use of signals, Sun-style asynchronous I/O, and nonblocking I/O. But none of these quite handle the job.
Suppose an application wants to do something -- write a data log to a disk file, for instance. In parallel, it wants to do something else -- say, continue gathering data into a second log buffer. One way it can do that under standard Unix is by creating a new process (via the fork() system call) to perform the asynchronous operation. Separate processes do not share any memory by default, but let's assume that we arrange things so that the old and the new process share a few pages of virtual memory used to store the pages of the data log to be written to disk.
A double-buffering scheme can be used to allow the original process to continue gathering data in one buffer while another is asynchronously being flushed to disk. The new process goes off with the data and writes to the file; the original process continues on gathering data. However, the original process needs to know when the asynchronous activity has completed, so that the buffer written to the log can be reused for more data gathering.
How does the second process communicate its completion to the original process? Historically, a signal sent via kill() is used. When a signal is received by a process, it is interrupted as if by a hardware device interrupt, and vectors to a signal handler routine that is analogous to an interrupt handling routine. In that routine, the used buffer can be made available for reuse.
The problem with this mechanism is that it is asynchronous -- the signal can occur at any time. At any point in the application's execution, it must presume that it can (and will) be "preempted" by the arrival of the signal. Say the application is enqueueing more buffers to the list of free log buffers when the signal arrives. It must assure that when the signal handling routine comes along and tries to enqueue its own buffer, it doesn't muck up the queue structure.
As if this weren't enough of a headache, the standard methods for dealing with such concurrency cannot be used with signal handlers. The signal handler is not a separate thread of execution. Rather, it is just a change in the direction of the running process. Therefore, it cannot block on a semaphore waiting for the free queue to become accessible. It has to do something with the used buffer immediately, because once the signal handler stops, it is done, forever.
Normally, the signal handler's action is to enqueue the buffer if possible, but otherwise to leave it in a well-known place and set some flag indicating that the buffer needs to be taken care of. Then, the initial process needs to check whether a signal has occurred, if so enqueue the buffer, and so on.
As you can tell, dealing with asynchrony in an application is a major headache. In contrast, multithreaded applications can avoid all asynchrony. These applications are comprised of multiple threads, executing code synchronously, without the possibility of being interrupted amidst what they are doing. When one thread must synchronize with another, it does so synchronously, by waiting for the other thread to arrive at an agreed-upon rendezvous point. Because the applications do not have to deal with numerous "what-if?" cases, they tend to be more robust, legible, and maintainable. They are probably also more efficient, because they needn't do a lot of paranoid checking to see if something has happened behind their back.
In the example above, one thread would be writing buffers out to disk, while another puts data into the buffers. The threads would wait politely for each other, using some kind of synchronization mechanism.
Increasingly, Unix vendors are extending the standard Unix processing model with facilities for multiple threads within a single Unix process. Multithreaded Unix processes allow asynchronous programming to be turned into synchronous programming, as well as offering natural support for Ada tasking.
Threads and Ada tasks are very similar, but not equivalent concepts. The difference between the two can be seen largely in the methods used for synchronizing threads versus tasks.
Why synchronize? Threads must synchronize what they're doing because they are all sharing the same process. That means the same address space, the same file descriptors, and the same data structures. There has to be a way to assure that shared resources don't get messed up by threads modifying them all at once. It's like too many chefs ruining the broth -- it's okay if each chef locks the others out of the kitchen while he's stirring his particular pot.
There are many different mechanisms for synchronizing thread execution -- binary semaphores, counting semaphores, mutexes, condition variables, readers/writer locks, and monitors, just for starters. Rather than try and attack all of these, we'll just discuss one of the most popular synchronization mechanisms: the combination of mutexes and condition variables.
A mutex is simple -- it enforces mutual exclusion. Threads perform two calls on a mutex to use it -- mutex_enter and mutex_exit. Once a thread has successfully called mutex_enter, other threads that call mutex_enter will be stopped until the first thread calls mutex_exit. Thus, a mutex can be used to guard a resource (such as an error log) that must be written by only one thread at a time.
Mutexes are also used to guard more complicated resources than files -- resources that may be ready for a particular operation or not. For a thread to safely examine the state of such a resource, it must lock the mutex. But, say the thread gets into the mutex and finds the resource isn't ready for its use? It has to wait for a particular condition to be satisfied.
For example, in the case of the data-logging example, the thread putting data in the buffers would wait for conditions like "the second buffer is available," while the thread writing data to disk would wait for a condition like "the first buffer is ready to be written to disk." You see the reason for the name "condition variable." A condition variable can be waited for with cond_wait, and signalled with cond_signal.
cond_wait automatically exits the mutex and enqueues the thread on the condition variable, to await another thread's call to cond_signal. Then, the mutex is reentered, and the thread continues. Mutexes and condition variables are an extremely common way of synchronizing thread execution.
Interestingly, Unix systems based on Berkeley or AT&T Unix have a close analogue to condition variables inside the kernel, in the sleep( )/wakeup( ) calls. However, a parallel to the mutex primitives is lacking in these systems.
Ada task synchronization is accomplished with the Ada rendezvous. This is a higher-level synchronization mechanism than condition variables and mutexes. By that I mean that condition variables and mutexes can be used to efficiently implement Ada rendezvous, but can also be used to synchronize threads in other ways that might be difficult to emulate using Ada rendezvous.
In the Ada rendezvous, one task, the caller, calls another task, the acceptor. Independently, the acceptor announces its willingness to accept callers. If either of these happens before the other, the task is blocked. When both these events occur, the acceptor is awakened and handles the caller's call. While the acceptor is handling the caller's call, the caller is blocked. When the acceptor is done, it ends the rendezvous, and the caller continues on its way. Ada allows acceptors to accept any of a set of callers.
An Ada rendezvous looks something like a procedure call from the caller's point of view -- it calls something (in the data logging example, it might be a buffer-management facility) and it blocks until the thing returns. From the callee's point of view, it's like waiting for some event to occur, handling the event, and then waiting for the next event. The reason Ada uses this mechanism is that it accurately models what is usually desired when two threads wish to synchronize.
The Ada-style rendezvous is useful for many applications that use threads, even if those applications are written in C.
Earlier sections have discussed many shortcomings in standard versions of Unix. These shortcomings are not necessarily inherent to the architecture of Unix. In many cases, they can be viewed as specific holes in current implementations.
For example, there is no requirement that a Unix system implement a time-sharing scheduler in order to be called "Unix." There now exist real-time Unixes that do not allow process priorities to drift. Likewise, some versions of Unix can support most of Ada's real-time requirements. Still, most current versions of Unix are based on the AT&T (System V) or UC Berkeley (BSD) implementations, neither of which directly support real-time requirements.
The first steps toward Unix-based support for Ada tasking (among other things) have been taken by a number of people, and are now being standardized by the IEEE POSIX 1003.4a committee. Thread support can be found in systems such as LynxOS, CMU's Mach, and numerous Unix ports performed by vendors of multiprocessor Unixes, such as Encore and Sequent. The proposed POSIX.4a functions allow a POSIX process to create an additional thread in a given process, allow that thread to exit, allow other threads to synchronize their execution with that thread.
In addition, the standard specifies that blocking system calls will block only the thread which made the call. This, together with POSIX 1003.4 support for real-time functionality, provides all the necessary pieces for real-time Unix-based support of Ada.
To receive standards group mailings, including current drafts of POSIX 1003. 4a, request subscription and meeting information from:
Secretary, IEEE Standards Board IEEE Inc. P.O. Box 1331 445 Hoes Lane Piscataway, NJ 08855-1336
Copyright © 1991, Dr. Dobb's Journal