|
Gem #89: Code Archetypes for Real-Time Programming – Part 1
Author: Marco Panunzio, University of Padua
Abstract: Ada Gem #89 — In the programming of real-time systems, code that deals with concurrency and real time often draws from explicit or implicit recurring patterns. Therefore it is best factored out. In this series of Ada Gems, we illustrate a set of code pattern archetypes that are intended to ease the development of real-time systems.
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
Posted
in Ada / Ada 2005 / Ada 2012, Development Log, Devt log - Gem of the Week
Have your own idea for a Gem?
If you have an idea for a Gem you would like to contribute please feel free to contact us at: gems@adacore.com
Simon Wright said:
A couple of nits: Why does Cyclic_Task’s spec use System? and why does it mention Ada.Real_Time at all?
Anh Vo said:
Thank you for your GEM. I do enjoy it.
What does the System_Time look like?
Matteo Bordin said:
@Simon
System is necessary for Thread_Priority which is of type Priority. Ada.Real_Time is not necessary, as it is with-ed in the body. I will fix the gem code.
@Anh
An example is the following:
with Ada.Real_Time;
package System_Time is
System_Start_Time : constant
Ada.Real_Time.Time := Ada.Real_Time.Clock;
Task_Activation_Delay : constant
Ada.Real_Time.Time_Span := Ada.Real_Time.Milliseconds (5_000);
end System_Time;
Marco Panunzio said:
I see that Matteo was faster than me. :-)
In the package example in the comment by Matteo, you use System_Start_Time to know the time your system is activated.
Task_Activation_Delay defines a stipulated timespan after system activation on which all “synchronous” tasks are simultaneously released for the first time (5 seconds in the example).
Using that approach, you may want to use in the body of the archetype:
Next_Time : Time := System_Time.System_Start_Time +
System_Time.Task_Activation_Delay;
As suggested in the gem, then you can also add a per-task static offset (w.r.t. the synchronous release), passing the desired offset as an additional parameter when you are instantiating the generic.
In that case, you simply have to add the offset when you are defining the time instant of the first release of the task.
Next_Time : Time := System_Time.System_Start_Time +
System_Time.Task_Activation_Delay +
Offset;
This guarantees the task preserves its phase w.r.t. the “synchronous” tasks (with 0 offset).
Simon Wright said:
@Matteo: Sorry; I get the “with System;”, what I was questioning was the “use System;”. Told you it was a nit.
Anh Vo said:
To increase efficiency, the period should be made constant, too. The calculation / conversion is done only once in this case.
The_Period : Ada.Real_Time.Time_Span := Ada.Real_Time.Milliseconds (Period);
…
…
Next_Time := Next_Time + The_Period;
…
Denk Padje said:
Wouldn’t it be better if Period in the specification of Thread_T is of type Milliseconds instead of Positive? Then clients immediately see the task expects a period in the order of milliseconds.