It's not just for defense contracts any more. Ada has developed into a useful programming language for plenty of different embedded projects. This expert shows how new Ada standards improve Ada's real-time capability to meet those tight deadlines.
Ada's status as a well-established programming language has sometimes led to the perception that it's outdated or even obsolete. It's worth noting, however, that in the same year Ada debuted, Microsoft introduced a new product called Windows. Today, few would call Windows outdated or obsolete because, like Ada, constant innovation improves, enhances, and maintains Windows' competitive capabilities. For Ada, this constant innovation is most obvious in the real-time arena, where Ada 2005, like Ada 95 before it, raises the bar for real-time programming languages by providing facilities that are either new to the industry or are only partially available in other programming languages.
This article takes you on a tour of the new features in Ada 2005 for real-time applications, showing why it's arguably the new standard for real-time programming languages. The language design was completed in 2005 (hence the colloquial name) and the final administrative details for the ISO standardization will be finished this year. Comprehensive implementations are available now.
New in Ada 2005
Ten years ago Ada 95 provided a concurrent programming environment for real-time systems using fixed-priority, preemptive scheduling. Building on that foundation, Ada 2005 includes new dispatching policies, such as non-preemptive, round-robin, and earliest-deadline-first dispatching. With the exception of non-preemptive dispatching, these policies can even be combined for systems with both hard real-time and background tasks.
Another new facility called timing events is a lightweight mechanism for reacting to the arrival of a point in time, much as interrupts allow handlers to react to external events. A similar capability is also provided for monitoring and responding to individual task execution times (CPU time). Monitoring and reacting to the execution time of groups of tasks is supported, too. This “group budget” mechanism is especially useful for implementing servers for sporadic tasks.
In addition, the Ravenscar Profile is now standardized in Ada, after having previously been implemented in slightly different ways by different Ada vendors. (The Ravenscar Profile is a tasking subset for real-time and high-integrity applications–I discuss it in more detail later in this article.) Although particularly appropriate for real-time systems, the profile represents a new opportunity for applying concurrency to high-integrity applications that could not otherwise allow tasking. The small footprint and high efficiency also make the profile attractive for embedded systems.
I'll describe these new features in detail, but first it helps to understand Ada's concurrency model and how it relates to the Real-Time Annex.
The Ada concurrency model
Ada is organized into one core and several annexes. The core is required of all Ada implementations and contains the definitions of all language constructs. The annexes define additional facilities but never new syntax. The additional facilities they provide are typically in the form of packages (modules) that define abstract data types and pragmas (compiler directives) that specify required behavior. Both packages and pragmas are defined in the core.
The core includes the definition of concurrency in the form of tasks representing threads of control, and protected objects that provide mutual exclusion and condition synchronization in a high-level, yet efficient, manner. Consider the typical producer/consumer programming example shown in Listing 1. Tasks represent the producer and consumer threads, with a protected object representing the shared buffer. In this example we use a reusable generic unit defining a bounded buffer type. Generic units are essentially templates for program units, with various aspects factored out of the code. (Indeed, in C++ generic units are called templates and serve much the same purpose.)
Our generic unit is shown in Listing 2. The package template is named Concurrent_Bounded_Buffers and has one generic parameter named Element (see Line 2, Listing 2) representing the type of values held within a buffer object. Given this template, the main program Demo_Buffers can instantiate the generic into a usable concrete unit (Line 1, Listing 1), in this case a package named Characters because we instantiate the generic to obtain buffers of Character values. The package exports a protected type, such that many protected objects of that type can be easily declared. In particular, the protected type Bounded_Buffer is used to declare the object Holding in the main program (Line 3, Listing 1). When a Bounded_Buffer object is declared we must also specify the capacity of the buffer. Thus the buffer Holding can contain at most 10 characters at once.
The producer body is declared on Line 9 and the consumer body on Line 16 of Listing 1. These task bodies define the behavior of the two threads of control. The producer simply inserts 26 characters into the buffer by calling the Put operation on object Holding (Line 12, Listing 1). Because at most 10 characters can be in the buffer at once, the producer might temporarily block at some point, depending on how the tasks are scheduled. The consumer task loops indefinitely, reading characters from the buffer via procedure Get (Line 20, Listing 1) and printing them until it reads the character Z . If the Holding buffer is empty before the last character is consumed, the consumer will temporarily block. Eventually the tasks terminate and the program as a whole terminates.
An important point about protected objects is that they're not threads of control. Rather, they're passive, data-oriented objects in the same way that semaphores are data instead of threads. As a result, no expensive task switching is involved when invoking one of their operations. In contrast, tasks in the now-outdated Ada 83 model could only communicate directly, via the rendezvous mechanism, thereby causing a number of task switches on each invocation. In particular, the shared buffer had to be another task in Ada 83 because no synchronization mechanism existed other than the rendezvous mechanism defined in the language. In Ada 95, protected objects provide operations that are executed by callers without this task switching overhead.
The body of the generic package in Listing 3 contains the body of the protected type Bounded_Buffer. As mentioned, each protected operation is executed by a caller with mutually exclusive access so no other task can be executing a modifying call on the same object at the same time. Thus, no race conditions are possible on the shared data inside the protected object. Note the logical expressions on Lines 5 and 12 of Listing 3, referring to encapsulated objects Count and Size. These “barriers” express condition synchronization by enabling or disabling the execution of the associated routine until the proper conditions are met. In this example a call to Put is allowed to execute only when the buffer is not full. Execution of Get is similarly enabled only when the buffer is not empty.
Ada 95 real-time foundation
Although the core tasking model in Ada 95 has great expressive power and is difficult to use incorrectly, it's not enough for real-time programming. For example, the core doesn't define a notion of priority, nor of priority-based queuing or scheduling. That's where Ada's Real-Time Systems Annex comes into play.
The Real-Time Systems Annex defines additional semantics and facilities, integrated priority-based interrupt handling, and run-time library behavior that support deterministic tasking via fixed-priority, preemptive scheduling. Priority inheritance and the immediate ceiling priority protocol (ICPP) are included to limit blocking. (ICPP is known as Priority Protect Protocol in POSIX and Priority Ceiling Emulation in Real-Time Java.) Together with a high-resolution monotonic clock providing both relative and absolute time delays, these facilities support off-line schedulability analyses (such as response-time analysis) so that total schedulability can be determined before the program is ever executed.1, 2
For example, we can assign priorities to the tasks by applying pragma Priority, defined by the Annex for this very purpose, as illustrated in Listing 4. The priority values shown are purely for the sake of illustration. Actual task priorities would be determined by whatever method best suited the characteristics of the task set. For example, Deadline Monotonic would be best if the deadlines aren't equal to the periods.1, 2 The protected object would also apply pragma Priority. Priorities for protected objects would be assigned in accordance with the ceiling priority protocol.
Having assigned individual priorities, we can apply additional pragmas to configure the behavior of the run-time library. These pragmas are also defined by the Annex:
pragma Task_Dispatching_Policy (FIFO_Within_Priorities);pragma Locking_Policy (Ceiling_Locking);pragma Queuing_Policy (Priority_Queuing);
These pragmas and arguments specify that the run-time system should preemptively assign tasks to the processor strictly in terms of their priorities (Line 1: pragma Task_Dispatching_Policy. . . ), that priority inheritance and the immediate ceiling priority protocol should be used (Line 2: pragma Locking_Policy . . . ), and that all run-time tasking queues are to be ordered by priority and that otherwise non-deterministic behavior is to be decided by priorities (Line 3: pragma Queuing_Policy . . . ).In addition, low-level tasking control and synchronization are available in Ada 95 to meet extreme performance requirements. These capabilities include an abstraction similar to a binary semaphore and, optionally, the ability to asynchronously suspend and resume tasks for the sake of building application-defined schedulers (for example).The language also defines a standardized mechanism for restricting the run-time library and language constructs for the sake of both greater efficiency and easier certification. The mechanism for specifying these restrictions is the pragma Restrictions, defined in the core. For example, we can promise by the following that no use of the task abort capability appears in our application:
pragma Restrictions (No_Abort_Statements);
As a result it would be possible to execute our application with a run-time library that did not include support for aborting tasks. Such a run-time library would be smaller and would exhibit considerably better performance. The Real-Time Systems Annex defines a number of restrictions (including the no task-abort one I just mentioned) that can be used with pragma Restrictions to facilitate the construction of highly efficient tasking run-time systems. Other annexes, notably the Safety and Security Annex, also define restrictions.2005 real-time enhancements
Ada 2005 is a fairly modest revision to Ada 95–with some notable exceptions. Multiple inheritance is now supported à la Java interfaces but the concept of interfaces has been extended to also include concurrency. Thus, an interface type can specify that the abstract operations it defines must be implemented in a thread-safe manner. The most dramatic additions, however, are in the Real-Time Systems Annex. Here, a number of significant capabilities have been added that go beyond any other mainstream language or library facility, including the POSIX real-time facilities.New dispatching policies
The Ada 95 Real-Time Systems Annex defines a complete facility for fixed-priority, preemptive scheduling appropriate for systems with hard deadlines (those that must not be missed). This dispatching scheme is arguably best for systems requiring complete predictability, especially during transient overloads, but other dispatching schemes also have advantages. Ada 2005 extends the standard dispatching schemes to include support for non-preemptive, round-robin, and earliest deadline first (EDF) dispatching. Any one of these additional dispatching policies may be specified to the pragma Task_Dispatching_Policy using the following policy names:
With non-preemptive dispatching, tasks run until voluntarily blocked, for example on a delay statement or a protected entry call. Tasks are assigned priorities–to enable selection of the task to dispatch to the processor when a choice must be made–but are never preempted by higher-priority tasks. This dispatching scheme is not unusual in high-integrity applications because the effect of asynchronous events doesn't need to be analyzed. However, systems using this scheme are naturally less reactive to events than with preemptive dispatching.In the round-robin scheme, tasks again have a priority assigned, for the same reason. The principle characteristic of this scheme is that each task is allocated an execution time quantum when placed on the ready queue. As each task executes, this budgeted quantum is decreased by the execution time used. The task retains whatever remains of the time allotted while blocked (for example, on an entry call). When the quantum is exhausted the task is de-scheduled and placed on the tail of the ready queue. The budgeted quantum is reallocated to the task when it is next dispatched. Round-robin dispatching is common in non”real-time environments and some soft real-time systems because it provides a measure of fairness. The code in Appendix A (online at file name Rogers_appendices.doc) contains the standard interface for manipulating the budgeted time quanta.The third new dispatching policy, earliest deadline first (EDF) , is a dynamic priority scheme in that task priorities are computed at run-time and therefore can change (unlike conventional fixed-priority schemes). Specifically, when dispatching occurs the task with the nearest deadline is assigned the highest priority and is given the processor. These deadlines are in terms of absolute time, computed for each ready task as the current time plus the deadline time relative to the task release. Developers specify this relative deadline using another pragma-defined by the Annex. For example, the task Worker in Listing 5 specifies a relative deadline of 20 milliseconds, using a function defined by the package Ada.Real_Time that returns a value of type Time_Span. Relative deadline assignments can also be procedurally manipulated by the application during execution, although typically these deadlines do not change. The interface for doing so is defined by package Ada.Dispatching.EDF shown in Appendix B (at www.embedded.com/code). If no deadline is specified, the deadline is the value of the constant Default_Deadline defined in that package, effectively the farthest point in the future that is possible to express.
pragma Priority_Specific_ Dispatching (FIFO_Within_ Priorities, 9, 20);pragma Priority_Specific_ Dispatching (Round_Robin_ Within_Priorities, 1, 8);
As shown, the arguments to the pragma are the dispatching policy followed by the low- and high-priority values of the band intended to use that policy. Hence, any task with a priority in the range 9 through 20 (inclusive) will be dispatched by the fixed-priority, preemptive scheme and those tasks with priorities in the range 1 through 8 will use round-robin. This mix is illustrated by Figure 1. EDF dispatching could also be applied with another instance of the pragma. Note that any tasks with priorities not covered by an instance of pragma Priority_Specific_Dispatching are dispatched using FIFO_Within_Priorities.
Ada has never had a lightweight facility for reacting to the arrival of a point in time. A task executing after a delay statement achieves that effect, but a full thread of control may not be required and is not lightweight compared with, say, interrupts. For that reason, Ada 2005 introduces the notion of “timing events,” which are conceptually interrupts generated by the arrival of points in time.3 Developers can define procedure “handlers” to be executed in response to these events. These procedures can do anything required. For example they can set the next time for the same event such that a continuous periodic invocation occurs. As another example, they can implement the functionality of a traditional “watchdog timer,” in which an interrupt is generated if a sequence of code is not completed in a certain amount of time. Timing events are represented by objects of type Timing_Event defined by a package specified in the Real-Time Systems Annex (see Appendix C at www.embedded.com/code). For any such event, the user associates a time and a reference to the procedure to be invoked at that time. This association is made via the procedural interface provided by the package. Note that setting a timing event's time and handler cancels any previous settings for that event.The time associated with an event can either be an absolute point in time or a time relative to the current execution. Both kinds are of types declared in package Ada.Real_Time: an absolute time is expressed in terms of type Time and the relative time is expressed in terms of type Time_Span. The procedure “handler” that responds to the event must be a protected procedure, in other words, part of a protected object. Any such protected procedure must have one parameter, of type Timing_Event. Having defined these basic semantics we can now illustrate the watchdog idiom using timing events. We assume a task is executing a sequence of critical statements that must complete. We know the amount of time required for successful completion of this sequence so a problem has occurred if more than that amount of time passes. In response we can take some corrective action. The code fragment in Listing 6 illustrates the idea.
Monitoring the execution time (the CPU time) of tasks is generally useful. An application can quickly detect timing overruns when, for example, high-integrity tasks exceed their computed worst-case execution times. Such a facility can be used to implement flexible scheduling schemes and fault tolerance mechanisms and, in combination with other facilities, implement sporadic servers.The monitoring facility is provided by package Ada.Execution_Time (see Appendix D at www.embedded.com/code). The idea is that each task has a dedicated CPU time accumulator that is incremented as the task executes. To that end, the package defines a type CPU_Time with at least one-millisecond granularity and a range of at least 50 years. Each task-specific clock is automatically started after the task is created and accumulates both the task's direct execution time and any time indirectly spent in the run-time library and underlying operating system (if an operating system is present). Additionally, time spent by the run-time library or operating system on behalf of no specific task may actually be accrued to some individual task or tasks. Whether this occurs is implementation-defined, as is to what tasks it accrues if it does occur.The package defines a function Clock that returns a value of type CPU_Time for a specified task. Arithmetic functions for manipulating CPU_Time values are also provided, as well as a means of composing values, all in terms of wall-clock time values. We will provide an example after the additional execution time facilities are described in the next sections. For now, see Appendix D at www.embedded.com/code for the basic monitoring interface.Execution time events
In addition to monitoring the execution time of individual tasks, an application may define and respond to events based on cumulative execution time. Execution time events are very similar in concept and interface to those of timing events described earlier, except that these events use execution time rather than wall-clock time.Events are represented by objects of type Timer defined by package Ada.Execution_Time.Timers (see Appendix E at www.embedded.com/code). Timer objects monitor a given task's execution time and can be associated with a protected procedure to be invoked when the given task's execution time reaches a specified amount.
In Listing 7, a task monitors itself and cuts its own priority by half after every two seconds of execution time. A timer is associated with a task when the timer is declared by passing a reference to a value of type Task_Id. That type is language-defined by package Ada.Task_Identification which provides a means of identifying tasks independent of the specific task types involved. (That package, among others, is not shown for brevity.) Therefore, we declare the execution timer on Line 5, Listing 7, passing a reference to the Task_Id object declared on Line 3, Listing 7. That Task_Id object designates the Worker task on Line 1 via the standard attribute Identity.
Applications may declare as many timers as required and these can monitor different tasks at different times by changing the value of the Task_Id object they designate. In Line 3, Listing 7, the value of the Task_Id object is not a constant and could refer to some other task by simply assigning a new reference.
Continuing the example, on Line 7, Listing 7, we declare the protected procedure invoked by the timer event. The priority of the enclosing protected object is set using the constant Min_Handler_Ceiling defined by the Ada.Execution_Time.Timers package. This value is defined by the implementation to allow for the use of the Ceiling_Locking protocol but, unlike the other timing events package, this one might not be invoked by an interrupt handler.
On Line 16, Listing 7, the handler determines the current priority of the task designated by Id, halves it, and then brackets the result to the greater of that value and the lowest priority value possible. The handler then sets the priority of the task to that value on Line 17, Listing 7.The body of the task is declared on Line 21, Listing 7. Note that subprograms Set_Priority and Get_Priority are provided by the language-defined package Ada.Dynamic_Priorities. Both routines work with the current task by default.
The task first sets its own initial priority on Line 26, Listing 7 and then loops indefinitely. It sets the execution timer event on Line 29, Listing 7, in the outer loop so that after every two seconds of execution time the event will trigger the Expired procedure. The task then enters the inner loop that executes as long as the priority is unchanged. Eventually the Expired procedure will change the priority and the inner loop will exit, the new priority will be captured, and the timer will be reset for another two seconds of CPU time. The two-second value is created by function Time_Of, defined in package Ada.Execution_Time. The function takes two parameters: the first specifies the number of seconds required, and the second specifies the fraction of a second required. This second parameter defaults to zero for convenience.Although this example is somewhat artificial it will provide a taste of what the facility can do. You can imagine, for example, a reusable component that monitors a series of tasks, leveling the load among them by controlling their relative priorities.
The execution time facilities have, so far, been focused on individual tasks. In contrast, the package Ada.Execution_Time.Group_Budgets handles allocating and monitoring a budgeted execution time for a group of tasks as a whole. A protected procedure handler can respond to the exhaustion of this group budget, as with the other events we have seen. Package Ada.Execution_Time.Group_Budgets defines the facility, as shown in Appendix F at www.embedded.com/code. This package is especially intended for writing “servers” that integrate sporadic tasks (aperiodic tasks with known properties) into a set of schedulable periodic tasks.2 For example a “deferred server” can be implemented fairly easily.
The package defines type Group_Budget to represent groups of tasks. A number of operations on objects of the type are provided in support of group membership, time budget control, and setting the event response procedure.Although the implementation of a deferrable server is relatively straightforward using Group_Budget facilities (and some of the other abstractions defined by the Real-Time Systems Annex), it is nevertheless beyond the scope of this article. The original document that suggested the Group_Budget facility provides a sample implementation.4 This implementation is very slightly out of date but it fully illustrates the approach.
The Ravenscar Profile
The Ravenscar Profile is an analyzab