next up previous contents index
Next: Summary Up: The GNAT Project Previous: The Compiler   Contents   Index

Subsections


The Run Time System

In order to make GNAT portable, the Ada Run-Time System (RTS) is written in Ada. The compiler communicates with the RTS through procedure and function calls, without direct reference to RTS data structures aside from the parameters of the RTS subprograms. The RTS data structures may be kept in a separate address space, protected from access by the application. The direction of call is always from application code to the RTS [GB94a, Section 2]. The exceptions to this rule are:

Thus, the opportunities for optimization involve alternate source-code transformations, and alternate algorithms and data structures in the runtime library routines [DIB94, Section 4.2.1].

Figure 1.4: The GNAT Run Time Library.
\begin{figure}\centerline{\psfig{figure=figures/01-GNAT/04-rts.eps,width=6 cm }}\end{figure}

Figure [*] presents Run-Time hierarchy. The Run-Time library is made up of three levels: GNARL, GNULL and Pthreads1.6. An Ada program requests the services of the Run Time through the GNARL subprograms calls. This level uses the services provided by the GNULL level. This intermediate level is an interface between the upper level and the POSIX standard library. POSIX Pthreads provides support to languages for concurrent programming.


GNARL

GNARL is the GNU Ada Run-time Library. High level language constructs are translated by the expander into calls to this library. Packages that constitute the run-time are treated as any other unit of the context of the compilation, and analyzed when necessary. This obviates the need to place run-time information in the compiler itself, and allows a knowledgeable user to modify the run-time if he/she so chooses. The design of GNARL is based on the CARTS (Common Ada Run-Time System) specification [SGC94, Section 3.6]. The original design objectives of GNARL, in order of priority, were [GB94a, Section 1]:

  1. Semantic correctness. GNARL must support the full core tasking semantics, and as much of the Real-Time Systems and Systems Programming annexes as permitted by other constraints.

  2. Timeliness. Development should be incremental, so that working partial implementations can be delivered early. The RTS and compiler development should proceed in parallel. This means the RTS responsibilities should be clearly separated from those of the compiler. Ada features that early versions of the compiler are not likely to be able to translate should be avoided. Ideally, it should be possible to compile and test it using an existing Ada 83 compiler. It should use the existing PART RTS code for leverage, to speed development.

  3. Modularity. GNARL should be partitioned to hide information that the compiler does not need to know, including information about tasking features that are not used by a particular compilation. The GNAT strategy for implementing tasking is based on tree-to-tree translation, converting tasking constructs in the intermediate syntax tree representation into equivalent Ada language constructs, with interspersed RTS service calls. Thus, the GNAT interface should be expressible in terms of ordinary Ada packages whenever possible.

  4. Portability. GNARL should be written in Ada, with target-specific code clearly isolated in the GNULL level and kept as small as possible. It should be possible to produce configurations that run both over commercial off-the-shelf operating systems and on bare machines with minimal modifications. Initially, it should be supported on several commonly used operating systems.

  5. Research and technology transfer. GNARL should serve as a test-bed for implementation ideas, providing experience that will be useful in designing other implementations. Lessons learned should be reported promptly, and code made publicly available. Among other experimental goals, GNARL should provide a basis for measuring the overhead imposed by implementing Ada over Pthreads.

  6. Efficiency. GNARL should be as efficient as possible, consistent with the other objectives. The design should allow for future optimizations, including inline expansion and optimization of RTS calls. This means using ordinary procedure calls in the interface, as opposed to traps or calls via procedure pointers''.

GNARL is designed to facilitate the in-line optimization of Ada tasking constructs. The use of task constructs results in the implicit with of one or more of the packages that make up the GNARL by the GNAT compiler. Other than this implicit import, GNARL packages are indistinguishable from other application packages. There are no special restrictions on GNARL code. In particular, GNARL subprograms can be named in Inline pragmas, resulting in the replacement of implicit calls to these subprograms with the subprogram body. This should result in somewhat faster code due to the elimination of the subprogram call. However, once the code has been inserted inline, it can be further optimized by the compiler using information about the local environment including current register contents. This process is further augmented by the inline nature of the GNARL interface. Tasking is implemented with calls to the GNARL interleaved with user code. The only exception to this is task startup, where GNARL executes the task body code from a new thread of control via call-back. This inline nature of the GNARL interface is intended to allow local optimizations across the boundaries between the application and the GNARL, in particular when the GNARL calls are expanded inline. This kind of optimization is much less applicable with an interface involving call-backs to user code within the RTS. Each call-back point can call one of an arbitrary number of user code sequences, so they cannot be inlined, and it is less likely that local optimizations (i.e. register allocation) will be applicable to all of them [GMB94, Section 3].

Implementing GNARL semantics is relatively complex, and will probably be of interest only to users requiring unusual tasking semantics, or to take advantage of unusual hardware architecture (i.e. multiprocessing or distributed environments).


GNULL

GNULL exists only for portability; it provides a standard interface to services that are typically provided by an operating system or real-time kernel, isolating dependences on a particular host from the rest of GNARL [DIB94, Section 4.2.1].

The GNULL interface is an abstraction of a subset of the POSIX interfaces, including Pthreads. Therefore, it is trivially implementable over an operating system that supports the POSIX standards. In order to permit a simpler and more efficient implementation over other operating systems, or a bare machine, many features of Pthreads have been left out or restricted. The deleted features are ones that the Ada RTS does not need, or cannot use. For example, the POSIX semantics of thread cancellation do not fit the Ada semantics of abortion, so the Pthread cancellation services are not included in GNULL. The features retained include thread creation and operations on mutexes, condition variables, and signals. In cases where the Ada RTS does not need the full strength or generality of the Pthread interface, the semantics are relaxed. For example, GNULL mutexes have only one form of priority inheritance (the priority ceiling emulation locking protocol) and are required to be unlocked in FIFO order. Condition variables are only allowed to be used by one task at a time. Further simplifications are contemplated, including the hiding of condition variables behind a suspend/resume interface [GB94a, Section 4.2.1].


POSIX

The POSIX Portable Operating System Interface provides an application program interface to services supporting the creation and executio<n of multiple threads of control sharing the address space and file descriptors of a single POSIX process. POSIX has its roots in an effort to promote application program portability by establishing a non-proprietary standard interface to the many variants of the UNIX operating system [GB92, Section 2].

The IEEE identifies POSIX standards by designations of the form 1003.x. For instance, 1003.1 designates the C language application program interface for core operating systems services (i.e. file and process creation, input/output and inter-process communication). It is the base POSIX standard, and has been approved by the ISO as ISO/IEC 9945-1: 1990. Two other POSIX standards on which this project depends are 1003.4 and 1003.4a. The 1003.4 interface (Realtime Extension) is an extension to 1003.1 that provides services commonly needed in real-time applications. Examples of these services include binary semaphores, process memory locking and timers. The 1003.4a interface (Threads Extension, or Pthreads for short) is an extension to 1003.4 that supports multiple threads of control within a single POSIX process. Examples of services provided by 1003.4a include thread creation, mutual exclusion, and thread suspension. Both 1003.4 and 1003.4a are expressed as C language interfaces [GB92, Section 2]. There is also a standard Ada binding for 1003.1, namely 1003.5. This interface is defined as a set of packages, which provide access to the facilities of POSIX.1 via Ada data types, subprograms and generics [GB92, Section 3].

GNARL uses the POSIX services to build services with correct Ada semantics. The scheduling of the threads is directly under the control of the Pthreads scheduler, as is the state of each thread. Runtime stack allocation is also under the control of the Pthread implementation. Pthread priorities are fully dynamic, allowing the Ada RTS to make this priority adjustment in the code implementing the accept statement. Other Ada features, including the distinction between task creation and activation and the rules for task termination, are very different from their Pthread counterparts, and must be implemented almost entirely by the Ada RTS [GB92, Section 4.1]. Pthreads can be supported by the OS kernel or by a separate library. If Pthreads is supported by the OS kernel. System calls need only block the calling task, rather than the whole process. If global thread scheduling is provided, there may be better response to asynchronous events [GB92, Section 2].


Low-Level Locks

The GNAT run-time uses Lock/Unlock operations in order to maintain data consistency under concurrent read/update operations by multiple threads of control. It does quite a few more Lock/Unlock operations than is typical of older Ada run-time systems. The difference is that this run-time was designed to be multi-threaded, whereas most earlier Ada runtime systems were designed as a monolithic monitor. That is, the older style of Ada runtime system only allowed one task to be executing in the RTS at a time (we call this single-lock mode), but with the GNAT run-time several tasks may be executing in the RTS concurrently. Rather than just one lock that protects the entire RTS, there are individual locks for several RTS global data structures, and a lock for each task control block (we call this multiple-lock mode). Multiple-lock mode allows more concurrency between tasks. According to conventional wisdom, more concurrency is generally better. It permits more parallel execution if there are multiple processors, and even if there is only one processor it may permit quicker response to high-priority real-time events [DIB94, Section 4.2.1].

Mutual exclusion is provided through POSIX mutexes. When a thread wants exclusive access to some shared resource, it locks the associated mutex, via pthread_mutex_lock(); if some other thread has already locked that mutex, the requesting thread is suspended until the thread holding the mutex unlocks it, via pthread_mutex_unlock(). Any number of tasks can be suspended on the same mutex; one of them is granted the mutex and permitted to continue execution when the holder unlocks the mutex. Mutexes are similar to binary semaphores; the principal difference is that the thread which holds the mutex must be the one to unlock it. This makes mutexes difficult to use for general communication between threads; an arbitrary thread cannot signal to other threads that something has occurred by unlocking a locked mutex. For this kind of synchronization, condition variables are used [GB92, Section 5.1].

A thread waits for a condition to become true by calling pthread_cond_wait() on a condition variable. Another thread can signal that the condition has become true by signaling the condition variable, via pthread_cond_signal() (this is not to be confused with operations on POSIX signals). A mutex is associated with the condition variable by the pthread_cond_wait() call. This mutex must be locked before the call; it is unlocked (atomically) by the call and locked again before the call returns. This is to protect the condition for which the thread is waiting. A pthread_cond_signal() call is guaranteed to wake up at least one waiting thread, but it turns out to be more efficient (particularly on multiprocessors) to allow more than one waiting thread to return. Since the first thread to reacquire the associated mutex might make the condition false again, each thread needs to check that the condition is true when pthread_cond_wait() returns. This is usually done in a while loop [GB92, Section 5.1].



Footnotes

... Pthreads1.6
Pthreads - POSIX Threads.

next up previous contents index
Next: Summary Up: The GNAT Project Previous: The Compiler   Contents   Index
(c) Javier Miranda. Canary Islands (Spain), 2002. Version 1.0