Portable, reliable, and efficient concurrency: Ravenscar Ada tasking and the FACE safety profiles

3Airborne systems that need a small footprint or must comply with an industry assurance standard such as DO-178B [1] or DO-178C [2] are sensitive to size and complexity costs in the run-time support libraries. To answer these needs, the Future Airborne Capability Environment (FACE™) Technical Standard [4] has designated the Ravenscar subset of the Ada programming language’s tasking features as one of the acceptable concurrency approaches for a software component that must satisfy safety and/or security assurance requirements.

The approach is a government-industry software standard and business strategy to acquire affordable software systems, rapidly integrate portable capabilities across global defense programs, and attract innovation and deploy it quickly and affordably. It promotes component portability and reuse through standard well-defined interfaces in the context of a common Reference Architecture. The Reference Architecture includes an Operating System Segment (OSS) that supplies the run-time services that an application may require. The generality of the OSS support for a FACE component depends on the component’s profile, which is a subset of the complete FACE capabilities based on requirements for performance, safety, and/or security. The FACE Technical Standard defines several profiles:

General-purpose (assurance as required, determinism not guaranteed, time partitioning optional, space partitioning required)

Security (safety/security assurance, determinism, and time/space partitioning)

Safety (safety assurance, determinism, and time/space partitioning) – both Base and Extended

Corresponding to these profiles are language subsets (“Capability Sets”) for C, C++, Ada, and Java. A Capability Set defines which features are allowed and which are prohibited: allowance ensures sufficient expressiveness, prohibition helps to simplify analysis/certification against the relevant assurance requirements. A run-time support library has to implement the allowed features and may provide more, but (for the Safety Capability Sets) in a way that ensures determinism and facilitates assurance analysis.

The FACE Technical Standard defines several Capability Sets for Ada:

  • Ada 95 Safety – Ada 95 Safety Base and Security and Ada 95 Safety Extended
  • Ada 95 General-Purpose
  • Ada 2012 General-Purpose

Concurrency is supported in these profiles in two ways: By a threading API from the Operating System environment (POSIX or ARINC 653), or by language constructs (tasking).

Using the concurrency features defined in the language has the advantage of source code portability, since every Ada implementation needs to support the Ada tasking model. The high-level nature of Ada tasking also tends to promote reliability, since the programmer can express typical communication paradigms directly rather than through lower-level constructs such as semaphores or condition variables.

The allowed tasking features differ between the General-Purpose and the Safety Capability Sets. For the General-Purpose set, nearly the full Ada tasking facility is permitted. However, where safety or security assurance is required, the complexity of the run-time support would be problematic, and the full model also introduces application nondeterminism due to implementation dependencies.

A deterministic subset of tasking features is needed. This subset needs to be expressive enough to program real-world applications and also simple enough to implement efficiently. It should facilitate static analysis to verify critical properties including schedulability for hard real-time systems (making sure that all deadlines are met), and supports certification against assurance standards. The Ravenscar tasking subset was designed specifically to meet these goals and is allowed by the FACE Safety Capability Sets; it is a subset of the Ada 95 tasking features and is part of the Ada 2005 language standard.

Ada tasking and the Ravenscar restrictions

A concurrent Ada program consists of a set of tasks (threads of control) that communicate with each other either directly, through an intertask communication facility known as a rendezvous, or indirectly through shared data. For the latter purpose the language provides a high-level mechanism known as protected objects for state/condition-based mutual exclusion while avoiding race conditions and deadlock. Other forms of safe data sharing are also defined by the language, for example relying on hardware-enforced atomicity of access.

The Ada tasking model includes features for terminating a task (e.g., the abort statement), time-related support such as relative and absolute delays and a package with operations on a real-time clock, and an event- or timeout-based asynchrony mechanism. To prevent data corruption, certain code sections are defined as abort-deferred and need to execute to completion before being subject to asynchronous termination.

Tasks and protected objects may be defined either globally or within local scopes; the semantics prevents dangling references (for example a subprogram is not allowed to return until all its local tasks have terminated).

Tasks may execute either with actual parallelism on multiple processors/cores or else multiplexed under the control of a dispatcher on a single processor/core. A task may be assigned a priority, either statically or dynamically, and – based on the task dispatching policy – priorities are taken into account at various points during program execution when multiple tasks are eligible to execute.

Figure 1 shows a simple example of an Ada tasking program with two tasks (a Reader and a Writer) communicating with mutual exclusion through a protected data object (Resource).

21
Figure 1: Example of an Ada tasking program with Reader and Writer communicating through a Resource.

The full tasking model is highly expressive but requires a complex run-time implementation. In the interest of supporting efficient, high-integrity concurrent applications in Ada, particularly those with hard real-time requirements, workshops held in Ravenscar U.K. in 1997 and 1999 specified a set of restrictions that would allow a tasking program to be statically analyzable with respect to both its functional and temporal properties. This subset became known as the Ravenscar Profile; to avoid confusion with the FACE concept of “profile,” it is referred to here as the Ravenscar subset.

A program obeying the Ravenscar subset restrictions has several properties: It comprises a fixed number of nonterminating tasks, all defined globally; each task has a single triggering event, either time-based or event-based (signaled from another task or the environment), with a potentially unbounded number of occurrences of the triggering event; and the only task interaction is via shared/protected data objects.

The restrictions are defined through standard Ada language features, in particular a sequence of pragmas that the implementation enforces. Two such pragmas dictate the task dispatching and object locking policies:

  • pragma Task_Dispatching_Policy (FIFO_Within_Priorities)
  • pragma Locking_Policy (Ceiling_Locking)

These policies facilitate schedulability analysis methods such as Rate Monotonic Analysis [5] and can help minimize priority inversion, prevent mutual exclusion-based deadlock, and guarantee that tasks always meet their deadlines (see sidebar for further explanation).

The other Ravenscar restrictions are limitations on specific language features. These include prohibition against relative delay statements (since they are not needed and cannot be used reliably to achieve periodicity), abort statements, locally defined tasks or protected objects, task rendezvous, dynamic priorities, task allocation, and asynchronous transfer of control. Other restrictions that simplify the implementation or facilitate schedulability analysis include a limit of at most one queue (entry) per protected object, with at most one caller pending at any given time, and the prohibition against task termination. A complete definition of the Ravenscar subset appears in the Ada 2012 standard [6].

Although restrictive, the Ravenscar subset is also general enough to express a range of useful tasking idioms, for example cyclic (periodic) tasks; event-driven (aperiodic or sporadic) tasks, interrupt handlers, and shared resources (simple protected objects).

Figure 2 illustrates the Ravenscar subset in a variation of the Reader/Writer example from Figure 1, with cyclic (periodic) tasks that avoid drift.

22
Figure 2: Ravenscar subset in a variation of the example from Figure 1.

Implementing the Ravenscar tasking subset in a FACE context

In addition to allowing the Ravenscar subset, the Ada 95 Safety Capability Sets either permit or prohibit a variety of sequential language features. For example, the Safety Base Capability Set allows interrupt support, predefined exceptions with a single default handler, and some of the packages from the Ada predefined environment, while prohibiting dynamic allocation. The Ada 95 Safety Extended Capability Set allows exception handling in general and permits dynamic allocation at startup while prohibiting deallocation.

The challenge for an implementation of a run-time support library for either of the Safety Capability Sets is that of supplying the allowed functionality in a way that facilitates analysis for the relevant assurance requirements. An example of an implementation that meets this challenge is AdaCore’s Ravenscar-Cert library, which supports all the features permitted in the Safety Base and Safety Extended Capability Sets and meets the applicable objectives in DO-178B or DO-178C. This library implements the Ravenscar tasking features, exception propagation, a last-chance handler, and a mark/release mechanism (not requiring heap management) for functions returning unconstrained arrays. The Ravenscar-Cert library has been implemented for Wind River’s VxWorks 653 and Lynx Software Technologies’ LynxOS-178 RTOSes. The Ravenscar tasking support in this library is less than 40 KB.

Rising to the challenge

Concurrent programming is useful for designing and implementing real-time embedded applications in general and FACE components in particular, but it presents significant software engineering challenges:

• Portability. The Ravenscar subset is defined by the Ada language standard, and its set of restrictions can help guarantee deterministic behavior. A program adhering to the Ravenscar subset (and other restrictions on implementation-dependent features) will be portable across different implementations and platforms, which is a primary goal of the FACE approach. Ada’s Ravenscar tasking subset can help meet these challenges.

• Reliability. For a real-time program, reliability means not only functional correctness (computing the right results) but also temporal predictability (meeting hard deadlines). The Ravenscar subset helps realize these requirements in several ways. Complex features such as asynchrony are prohibited, the simple forms of permitted intertask communication are amenable to static analysis, and the queue restrictions facilitate Worst Case Execution Time calculation. The task-dispatching and object-locking policies specified by the Ravenscar restrictions likewise facilitate schedulability analysis and result in a simpler and more maintainable architecture than the traditional cyclic executive.

• Efficiency. The absence of semantic complexity enables a “lean and mean” run-time implementation. Support for features such as task termination, queue management, and dynamic priorities is not needed, and, as evidenced by implementations such as AdaCore’s Ravenscar-Cert library, the required functionality can be efficiently mapped to the services supplied by an underlying Real-Time Operating System.

The formulation of the Ravenscar subset in the late 1990s was a watershed event, showing that a hard real-time program could use concurrency features and still be certifiable against standards such as DO-178B.

References

[1] RTCA DO-178B/EUROCAE ED-12B, Software Considerations in Airborne Systems and Equipment Certification, December 1992

[2] RTCA DO-178C/EUROCAE ED-12C, Software Considerations in Airborne Systems and Equipment Certification, December 2011

[3] B. Dobbing and A. Burns; The Ravenscar Tasking Profile for High Integrity Real-Time Programs.

http://www.sigada.org/conf/sigada2001/private/SIGAda2001-CDROM/SIGAda1998-Proceedings/dobbing.pdf

[4] FACE Future Airborne Capability Environment) Technical Standard, Edition 3.0.

https://publications.opengroup.org/c17c/

[5] L. Sha, M. H. Klein, J. B. Goodenough; Rate Monotonic Analysis for Real-Time Systems; Technical Report CMU/SEI-91-TR-006; March 1991.

https://resources.sei.cmu.edu/asset_files/TechnicalReport/1991_005_001_15923.pdf

[6] Ada Reference Manual ISO/IEC 8652:2012(E) with Technical Corrigendum 1, Language and Standard Libraries

http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-TTL.html

Dr. Benjamin Brosgol is a senior member of the technical staff at AdaCore. He has been involved with programming language design and implementation throughout his career, concentrating on languages and technologies for high-integrity systems with a focus on Ada and safety certification (DO-178B/C). Dr. Brosgol is an active member of the The Open Group FACE Consortium’s Technical Working Group, and in particular he has been involved with the development of the IDL-to-Ada mapping. Dr. Patrick Rogers has been a computing professional since 1975, primarily working on microprocessor-based real-time applications. He began working with Ada in 1980 and was director of the Ada9X Laboratory for the U.S. Air Force’s Joint Advanced Strike Technology Program, and Principal Investigator in distributed systems and fault-tolerance research projects for the U.S. Air Force and Army. As a member of the technical staff at AdaCore, he is a developer of the bare-board products for Ada and provides support and training focused on embedded real-time applications. Dr. Dudrey Smith is a senior embedded system development consultant at AdaCore. He has been involved with military and commercial embedded system/software development and certification for more than 40 years, with major leadership roles at companies including Lear Siegler, Smiths Aerospace, and General Electric Aviation Systems. Dr. Smith is an active member of the The Open Group FACE Consortium’s Operating Systems and Conformance Subcommittees.

AdaCore • www.adacore.com

21
Sidebar 1

Topics covered in this article