Programming real-time with Ada 2005It'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:
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 Task_Dispatching_Policy (FIFO_Within_Priorities); pragma Locking_Policy (Ceiling_Locking); pragma Queuing_Policy (Priority_Queuing);
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
pragma Restrictions (No_Abort_Statements);
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:
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.
pragma Priority_Specific_ Dispatching (FIFO_Within_ Priorities, 9, 20); pragma Priority_Specific_ Dispatching (Round_Robin_ Within_Priorities, 1, 8);
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 analyzable subset of Ada tasking that's suitable for hard real-time and high-integrity applications.5 Arguably the most important new addition to the Real-Time Systems Annex, it isn't really new. The original was introduced in 1998 and is included in an ISO Technical Report dated 2000.6 Changes to Ada and experience applying the model have lead to refinements culminating in its standardization within the language itself.
The tasking model defined by Ravenscar is intended for one processor using fixed-priority, preemptive dispatching. There will be a fixed number of tasks and they never terminate. There are two kinds of tasks: time-triggered (periodic) and event-triggered (sporadic). Either kind of task will have at most one invocation point: periodic tasks will be released by a delay statement; sporadic tasks will be released by a protected entry triggered by either an interrupt or another task. Tasks do not communicate directly (via rendezvous) and do not interact with the control flow of other tasks. Any communication is indirect using shared variables encapsulated within protected objects.For example, a periodic task could be structured as depicted in Listing 8. Package Config simply contains the necessary configuration parameters for the tasks in the system. The procedure Do_Work called on Line 15, Listing 8, is just a place-holder for the computation performed by the task. Note the single release point for this periodic task on Line 14, Listing 8. The first time this delay statement is executed the task will delay until the initial release point--the Epoch--assigned on Line 12, but from then onward the task will delay until the next computed release point based on the period.
The interrupt handling procedure is declared on Line 5 of Listing 9. It is declared in the private part because no software should ever call it; only hardware interrupts invoke it. The procedure linkage to the UART interrupt occurs on Line 6, Listing 9. The incoming message data are represented by the encapsulated objects declared on Lines 7 and 8, Listing 9. The barrier that controls the entry is declared on Line 9, Listing 9 and is initially False so that the first call will block until a message is received. The entry called by the task is declared in Line 2 of Listing 9; note the parameter, a reference to a Message object. This parameter will provide the received message to the sporadic task calling the entry.
The body of the protected object implements the handler body and entry body and appears in Listing 10. The interrupt handler stores the incoming data and then sets Message_Ready to True on Line 9, Listing 10. That is what the caller task has been awaiting so the body of the entry can then execute (Lines 14 to 17, Listing 10). The entry body copies the internally buffered message into the calling task's object using the formal access parameter Msg declared on Line 12, Listing 10. The body then sets Message_Ready back to False for the next call.
The event-driven task iteratively calls the entry on Line 10 of Listing 11, blocking each time until a message is received. That call is the single trigger for the event-driven task. The task processes the message according to application requirements on Line 11, Listing 11, and then repeats indefinitely. (The procedure Respond is just a place-holder representing the actual work.)
- Task types & objects (in library level units)
- Protected types & objects (in library level units)
- Pragmas Atomic and Volatile
- Absolute delays
- Ceiling_Locking and FIFO_
- Task identifiers and attributes ('Caller' and 'Identity')
- Synchronous task control package
- Task type & protected type discriminants
- Package Ada.Real_Time
- Statically bound interrupt handlers
A profile defines a mode of operation, in this case equivalent to having written a series of pragmas:
pragma Profile (Ravenscar);
pragma Task_Dispatching_Policy (FIFO_Within_Priorities); pragma Locking_Policy (Ceiling_Locking); pragma Detect_Blocking; pragma Restrictions (...);
The set of arguments to pragma Restrictions enforces the tasking subset and is quite extensive. That is one reason for defining the pragma Profile instead of applying these pragmas. Another reason is that other profiles can be envisioned, such as a Ravenscar with non-preemptive dispatching.
Tasks are only intended to suspend at one point in their code, either on an entry or on a delay statement. Other blocking is not allowed. To enforce this restriction, pragma Detect_Blocking requires blocking operations to result in an exception. They are not required to be detected otherwise.
With this model and language subset, the intended application domains are well supported. The schedulability of real-time systems can be analyzed using any of a number of methods. For high-integrity applications, the static analyses normally performed on sequential code can be applied to tasks individually because in this model each task acts like an independent program. There is no intertask control flow and communication is indirect, as in a program accepting external inputs and producing outputs. You should understand that the Ravenscar Profile is silent on the subject of other language constructs. A subset of other parts of the language is certainly expected in high-integrity applications. For embedded systems, the run-time library is very much reduced in size so the footprint is small. In one implementation of Ravenscar (for Ada 95), the run-time library was reduced in size from approximately 500K down to around 3.5K.7 The resulting efficiency is great because the expensive constructs, such as task abort and asynchronous select statements, are not present in the run-time library. An implementation of a run-time library for comparable tasking subset measured overheads of approximately 3%.8
More to see
We have not fully explored the new Real-Time Systems Annex. For example, in addition to the dynamic priority mechanism for tasks that Ada 95 already provided, Ada 2005 adds dynamic priorities for protected objects. That capability makes protected objects easier to use when an application is based on operating "modes," such as in-flight, cruise, and landing modes for an aircraft. In different modes, distinct subsets of tasks will be operating, such that differing ceiling priorities will be required for the protected objects. A worst-case priority assignment causes schedulability difficulties so this is a useful addition to the language. Other additions, elsewhere in other Annexes, are also applicable to use with the Real-Time Systems Annex. For these, and details of the mechanisms described in this paper, a good resource is the Rationale for Ada 2005, which is available online.9
No other programming language or language-library combination provides this set of integrated capabilities for real-time systems. The POSIX real-time profiles provide some of these capabilities, but certainly not all of them, and leaves many important semantic points treated as implementation defined, thus sacrificing portability. The Real-Time Java community is discussing a Ravenscar Profile for that language but it does not yet exist.10 Only Ada has a mature, concrete Ravenscar implementation available in a language designed for real-time systems. In my opinion, these combined facilities make Ada 2005 once again the leading technology for real-time systems programming.
Patrick Rogers is a senior member of the technical staff with Ada Core Technologies. A computing professional since 1975 he has extensive experience in real-time applications in Ada and C/C++ in embedded environments. He holds BS and MS degrees in computer science from the University of Houston and a PhD in computer science from the University of York in the Real-Time Systems Research Group. You can reach him at email@example.com.
1. Briand, Loc and Daniel Roy. Meeting Deadlines in Hard Real-Time Systems: The Rate Monotonic Approach. IEEE Computer Society Press, 1999.
2. Burns, Alan and Andy Wellings. Real-Time Systems and Programming Languages, 3rd. ed: Addison-Wesley, 2001.
3. Barnes, John. Programming in Ada 2005. Addison-Wesley, 2006, pp. 713-716.
4. Burns, Alan. "Group execution-time budgets (AI95-00354)" www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-00354.TXT?rev=1.13
5. Burns, Alan, Brian Dobbing, and Tullio Vardanega. "Guide for the use of the Ada Ravenscar Profile in high integrity systems," Technical Report YCS-2003-348, Department of Computer Science, University of York, York, England, January, 2003. click here for article
6. ISO. "Guide for the use of the Ada programming language in high integrity systems," ISO/IEC TR 15942:2000, High Integrity Rapporteur Group, July 2000.
7. Dobbing, Brian. "The Ravenscar Tasking Profile—Experience Report," Ada Letters, vol. 19, no. 2, pp. 28-32, 1999.
8. Shen, Hongfeng, Arnaud Charlet, and Theodore P. Baker. "A 'Bare Machine' Implementation of Ada Multi-tasking beneath the Linux Kernel" in <9\i>Reliable Software Technologies--Ada-Europe'99, vol. 1622, Lecture Notes in Computer Science, M. G. Harbour and J. A. d. l. Puente, Eds., Santander, Spain: Springer-Verlag, 1999, pp. 287-297.
10. Kwon, Jagun, Andy Wellings, and Steve King. "Ravenscar-Java: a High-integrity Profile for Real-time Java," Concurrency and Computation: Practice and Experience, vol. 17, no. 5"6, pp. 681-713, 2005.