Gem #89: Code Archetypes for Real-Time Programming - Part 1

by Marco Panunzio —University of Padua

Introduction In this series of Ada Gems we propose a set of code archetypes for the development of real-time systems. The code archetypes comply with the restrictions of the Ravenscar Profile, a subset of the Ada language specifically suited for the development of high-integrity real-time systems. The Ravenscar Profile was devised to guarantee that programs written in accordance with it are amenable to static analysis in the time dimension. In fact, the profile excludes all Ada constructs that are exposed to nondeterministic or unbounded execution time. In the space dimension, the profile prohibits the use of constructs that implicitly perform dynamic memory allocation.

As an additional benefit, Ravenscar systems can be implemented on top of real-time kernels that can be very small in size and fast in time, which are attractive characteristics for applications that can afford little overhead and must undergo extensive qualification/certification.

The essential elements of the Ravenscar restrictions are: (i) static existence model. The system is composed of a fixed set of tasks and protected objects, defined at library level and with a statically assigned priority or ceiling priority. No task terminates, and abort statements are disallowed. (ii) communication model. Tasks are only allowed to communicate asynchronously, via protected objects. Task rendezvous is therefore disallowed. (iii) deterministic execution model. The profile excludes all constructs that introduce nondeterminism: relative delays, as they introduce nondeterminism in the suspension time of tasks; requeue statements; the use of the Ada.Calendar package, as all time-related operations rely on the high-precision Ada.Real_Time package; protected objects are restricted to having at most one entry on which only a single task can enqueue; guards of entries are composed of a simple Boolean condition to avoid side effects and nondeterminism in the evaluation time.

In this series of Ada Gems we illustrate a set of code archetypes that realize common programming patterns suited for the development of Ravenscar-compliant real-time systems. The use of the archetypes permits factorization and thus helps reduce the size of the code that implements the concurrent elements of the system.

An important additional goal of these archetypes is to achieve complete separation between the algorithmic/sequential code of the system and the code that manages concurrency and real-time aspects. This separation of concerns permits developing the algorithmic contents of the system (that is, the behavior of the system) independently of the management of tasking and real-time issues.

This goal is achieved by encapsulating the sequential code in a suitable task structure. The figure above depicts the generic structure of our task archetypes.

The sequential code is enclosed in a structure that we term the Operational Control Structure (OPCS). The code is executed by a Thread, which represents a distinct flow of control of the system. The task structure may be optionally equipped with an Object Control Structure (OBCS). The OBCS represents a synchronization agent for the task: as we shall see, we use it mainly for sporadic tasks. The OBCS consists of a protected object that stores incoming requests for services to be executed by the Thread. As multiple clients may independently require services to be executed by that Thread, the operations that post execution requests in the OBCS are protected. Upon each release, the Thread fetches one of those requests (FIFO ordering is the default) and then executes the sequential code, stored in the OPCS, which corresponds with the request.

As we will illustrate in the third Gem of this series, the operations provided by the OBCS, which form the provided interface of the overall entity, match the signature of the sequential operations of the OPCS (Op_A in the figure above). Thanks to that, the callers need not be aware that they are in fact only posting execution requests in the OBCS, while the actual execution will be performed by the Thread.

The sequential code embedded in the OPCS may need to invoke services from other software entities (the operation Op_Z in the figure above). In the fifth Gem of this series we will describe how those functional needs can be fulfilled.

As a conclusion, our entities encapsulate their internal structure and expose to the external world just an interface that matches the signature of the operations embedded in the OPCS. The different concerns dealt with by each such entity are separately allocated to its internal constituents: the sequential behaviour is handled by the OPCS; tasking and execution concerns by the Thread; interaction with concurrent clients and handling of execution requests are handled by the OBCS.

Structure of this Ada Gems Miniseries

Introduction and Cyclic Task
Simple Sporadic Task
Sporadic Task - System Types and Task Types
Sporadic Task - Sequential Code and OBCS
Intertask Communication

Acknowledgments The task structure we adopt is an evolution of the HRT-HOOD design methodology [1], from which we also inherit the terms OBCS and OPCS.

Early work on code generation from HRT-HOOD to Ada was described in [2] and [3].

The code archetypes that we describe in this Ada Gems miniseries were used for the code generation in the HRT-UML track of the EU-funded ASSERT project [4]. In that project, Matteo Bordin, then at the University of Padua, was the main designer of the code generation strategy and code archetypes.

Finally we would like to thank Tullio Vardanega for his preliminary review of the contents of this miniseries, and Matteo Bordin, now with AdaCore, for his extensive review of the contents and his useful suggestions.

Let’s get started…

Cyclic Task

In this section we illustrate our code archetype for cyclic tasks. It allows the developer to create a cyclic task by instantiating a generic package, passing the operation that needs to be executed periodically.

The archetype is quite simple. In fact, we only need to create a task type that cyclically executes a given operation with a fixed period. The specification element of the archetype is:

with System; use System;

generic
   with procedure Cyclic_Operation;
package Cyclic_Task is

   task type Thread_T
      (Thread_Priority : Priority;
       Period : Positive) is
      pragma Priority (Thread_Priority);
   end Thread_T;

end Cyclic_Task;

The specification above defines the task type for the cyclic thread. Each thread is instantiated with a statically assigned priority and a period which stays fixed throughout the whole lifetime of the thread. The task type is created inside a generic package, which is used to factorize the code archetype and make it generic on the cyclic operation. The Ada body is specified as follows:

with Ada.Real_Time;
with System_Time;

package body Cyclic_Task is

   task body Thread_T is
      use Ada.Real_Time;
      Next_Time : Time := System_Time.System_Start_Time;
   begin
      loop
         delay until Next_Time;
         Cyclic_Operation;
         Next_Time := Next_Time + Milliseconds (Period);
      end loop;
   end Thread_T;

end Cyclic_Task;

The body of the task consists of an infinite loop. Just after activation, the task enters the loop and is immediately suspended until a system-wide start time (System_Start_Time). This initial suspension is used to synchronize all the tasks that are to execute in phase and let them have their first release at the same absolute time. When resuming from the suspension (which notionally coincides with the release of the task), the task contends for the processor and executes the Cyclic_Operation specified in the instantiation of its generic package. Then it calculates the next time it needs to be released (Next_Time) and as first instruction of the subsequent loop, it issues a request for absolute suspension until the next multiple of its period.

The code archetype is simple to understand, yet a few comments are in order.

Firstly, we must stress that the use of absolute time and thus of the construct delay until (as opposed to relative time and the construct delay) is essential to prevent the actual time of the periodic release from drifting.

Secondly, the reader should note that the Cyclic_Operation is parameterless. That is not much of a surprise, as it is consistent with the very nature of cyclic operations which are not requested explicitly by any software client.

Finally, this version of the cyclic task assumes that all tasks are initially released at the same time (System_Start_Time). Support for a task-specific offset (phase) is easy to implement: we just need to specify an additional Offset parameter on task instantiation, which is then added to System_Start_Time to determine the time of the first release of the task. The periodic release of the task will then assume the desired phase with respect to the synchronized release of the tasks with no offset. In the next Ada Gem we will illustrate a simple code archetype to realize sporadic tasks.

References

[1] Alan Burns and Andy J. Wellings: "HRT-HOOD: A Structured Design Method for Hard Real-Time Ada Systems". Elsevier Science, 1995. ISBN 978-0444821645.

[2] Juan Antonio de la Puente, Alejandro Alonso, and Angel Alvarez: "Mapping HRT-HOOD Designs to Ada 95 Hierarchical Libraries." Reliable Software Technologies - Ada-Europe, Springer Volume LNCS 1088, 1996.

[3] Matteo Bordin and Tullio Vardanega: "Automated Model-Based Generation of Ravenscar-Compliant Source Code". Proceedings of the 17th Euromicro Conference on Real-Time Systems, IEEE Computer Society, 2005. ISBN 0-7695-2400-1.

[4] ASSERT project (Automated proof-based System and Software Engineering for Real-Time Systems) http://www.assert-project.net