The imperative synchronous languages Esterel and Reactive C (RC) were developed to address concurrent programming difficulties associated with the reactive systems commonly encountered in real-time and embedded programming[1, 2]. These languages have been called synchronous/reactive languages. This paper considers the applicability of such languages to the closely related problem of general system software development, and then describes an alternative software architecture intended specifically for system software development.
System software consists of components such as operating system kernels; file, database, and network systems; device drivers; and server architectures for I/O, transaction processing, and multimedia. These components react to external service requests generated by applications, other components, and hardware. Each component is generally capable of servicing multiple concurrent requests, some of which may be of long-duration, and some of which may have real-time constraints. Thus, operating system software constitutes a significant concurrent programming problem, and it is widely agreed that development of such software remains difficult[3].
There are many ways to view concurrency. The remainder of this section describes concurrent programming considerations germane to the design and programming of concurrent system software, that is, concurrency from the viewpoint of the systems programmer.
We can identify three orthogonal attributes that affect the systems programmer:
Cooperative concurrency either increases a single request's performance or simplifies multiple event coordination pertaining to a single request. Performance is increased by techniques such as issuing multiple overlapped I/O operations on behalf of a single service request. Coordination provided by cooperative concurrency simplifies activities such as request cancellation and error handling. Cooperative concurrency usually occurs internal to a system component and typically reduces the latency of a single request.
Cooperative concurrency typically reduces the latency of a single request.
Competitive concurrency maintains the timesharing illusion. This permits a given service request to be considered `invisible' to other unrelated service requests currently active within the same system component. Competitive concurrency occurs when a system component can execute two or more concurrent and unrelated service requests generated external to the component. Competitive concurrency mechanisms typically increase overall throughput of the component.
The amount of context copied during a context switch dominates performance. Modern hardware register sets are divided into non-privileged and privileged registers. Non-privileged registers are accessible to applications while privileged registers are protected from normal application access. A heavyweight context switch completely switches both privileged and non-privileged registers. This may require updating memory structures associated with both the privileged registers and with the software process model implemented by the system. A heavyweight context switch typically crosses protection boundaries.
Switching only the non-privileged registers provides lightweight context switching. Typically, one of these registers is the application stack pointer, so there is usually a stack associated with each thread defined by a set of non-privileged registers. A lightweight context switch is often an order of magnitude faster than a heavyweight context switch.
High-performance systems occasionally are designed which switch only a subset of the non-privileged registers. This approach is used in some transaction systems, such as IBM's TPF, and is often used within the interrupt handling component of operating systems[4]. Context switching a subset of the non-privileged registers will be called featherweight in the remainder of this paper. In the extreme, featherweight context switching involves switching only a single register, which usually is the base register of a data context describing a transaction or service request.
In this paper we are concerned with concurrency explicitly controlled by a single component to at least some extent. We call this internal concurrency. All other concurrency is external.
More specifically, from the viewpoint of a systems programmer, all concurrent activities occur in response to some request. Given two concurrent activities, the activities represent internal concurrency if:
All other cases represent external concurrency.
An example that satisfies the first condition above but not the second would be conventional re-entrant code with no shared data structures. One or more external components could initiate distinct activities within the component that were completely unrelated.
Due to differing internal concurrency requirements, different components often implement different internal concurrency mechanisms. Both competitive and cooperative concurrency may be supported internal to the component.
A system component itself typically executes in a concurrent environment in which it competes with other components for external resources. A common example of such external concurrency is competition between components for the CPU. Another example of important external concurrency is the mechanism by which the component can initiate and manage multiple asynchronous external requests, for instance, multiple asynchronous I/O operations.
The degree that concurrent contexts internal to a system component are simultaneously exposed to the systems programmer differs, often reflecting the required degree of cooperation between requests. At one end of the spectrum are classical threading models which typically do not expose to a given thread the internal state of other threads, that is, a thread's stack contents are private. At the other extreme, as exemplified by some windowing systems, multimedia servers, and simulation-action games, all concurrent context may be equally visible and expressly managed by the programmer.
In thread-based approaches, context tends to be encapsulated in a single data structure, such as a stack, which is explicitly scheduled by a lower-level scheduler. The implementation of this scheduler is often not visible to the programmer. In these systems, thread scheduling provides for concurrent behavior of processes, threads, transactions, requests, etc.. The programmer gets concurrency `for free' because implementation of the underlying threading system is not the programmer's responsibility.
At the other extreme, where expressly managed concurrent behavior is inherent in the program implementation, the programmer has complete responsibility for locating and scheduling activities. The programmer is in control and effectively defines custom context and concurrency mechanisms. Context may be distributed throughout program data structures. Locating relevant context upon the occurrence of each significant event may require considerable run-time logic. Such expressly managed approaches tend to be used when concurrent activities are highly interrelated and it is advantageous for the programmer to have a `gods eye' view of the entire concurrent state. Sometimes, as with the X-windows system, the code that expressly manages activities is placed into a standard run-time system. In general, modern windowing systems have used approaches based on explicit application event dispatch work-loops and call-backs rather than thread-based concurrency. This concurrency style, convenient in highly interactive cooperative environments, is sometimes called faux concurrency[5].
Concurrent service requests for file, network, database, and transaction systems often have a high degree of independence. Unlike message and window servers, two arbitrary service requests to this type of server are usually competitive. Optimally, the degree of internal concurrency within such a component is determined dynamically by the rate at which the external environment generates service requests. Lightweight or featherweight competitive internal concurrency mechanisms are thus very important for these servers.
The systems programmer is responsible for considering all of these issues. The internal concurrency mechanisms in many system components are only used by the systems programmer, and never directly by external code. The systems programmer is therefore free to implement custom concurrency mechanisms as well as program using those mechanisms.
Thus, when implementing a system component, one often programs with at least three different viewpoints in mind: the perspective of the individual service request, the perspective of the custom internal concurrent programming mechanism through which all individual service requests are controlled within the component, and the external concurrent environment that must be used but over which one may have no direct control. Optimally, the operating system kernel implementation itself supports these viewpoints, thus facilitating component implementation. The kernel is often considered simply another component that has primary responsibility for CPU allocation and interrupt dispatching.
Software architecture has been defined as `The structure of the components of a program/system, their interrelationships, and principles and guidelines governing their design and evolution over time.'[6] A software architecture is distinguished by `a shared repertoire of methods, techniques, patterns and idioms for structuring complex software systems.'
Software architectures provide an abstract conceptual approach to complex systems more specific than the models often inherent in a general purpose language but more general than a single design. A software architecture provides an identifiable approach or framework, often implicitly framed by the adopted tools, languages, and development environments.
Good system software invariably adopts a well defined software architecture. The architectures used for system software are usually based on some form of explicitly coded critical sections[3]. However, explicit critical sections introduce nondeterminism and are a root cause of many concurrent programming difficulties[7]. Because synchronous languages do not contain explicit critical sections, software architectures based on such languages may have advantages over traditional architectures.