by Alessandro Paganone
Alessandro Paganone is employed by Intecs Sistemi, S.p.A. in Pisa, Italy, where he was project manager on an ESA/ESTEC study investigating the feasibility to develop an on-board Data Handling Subsystem software in full Ada. This included Ada tasking, applying sound hard real-time concepts and using an appropriate software design method. The EURECA satellite (EUropean REtrievable CArrier) was deployed and flew for 9 months in 1993, retrieved by the Space Shuttle and returned to earth.
Software is increasingly present on board spacecraft, and this trend is expected to grow further in the future. Today, software already plays a prominent role in a considerable share of on-board functions; this includes data management services (DMS), attitude and orbit control activities, and a growing proportion of instrument processing.
The vast majority of current time-critical systems employ simple cyclic scheduling techniques which in spite of their conceptual simplicity can require a considerable amount of effort to ensure that the scheduling load is balanced, while even an apparently simple programming change can result in an inordinate amount of re-adjustments.
It has for some time been argued that the pre-emptive priority-based scheduling is to be regarded as a technology mature enough to use in the new generation of time-critical systems. Within this framework, ESTEC commissioned a study into the practicality of using native Ada tasking for space born applications.
As part of this exercise, a new design method and a set of associated tools have been developed to support the design of time-critical systems. This has resulted in the definition of the HRT-HOOD design method which builds on the foundation of HOOD and augments it with features especially suited for the design of hard real-time (HRT) systems: abstractions, attributes, rules and constraints that support the definition of an HRT design analyzable against timing requirements.
Next step was intended to check:
- the HRT-HOOD suitability to build critical real-time control software around the native Ada tasking and
- the maturity of existing Ada compiler systems in a practical case study.
For this purpose ESTEC started the rewriting in Ada 83 of the data handling software of the EURECA satellite, using HRT-HOOD and the DDC-I 80×86 Ada Cross Compiler System, (DACS-80×86).
The re-development of the EURECA software is an excellent opportunity to apply the mentioned concepts.
First, the native scheduler of the original implementation (still unique in space) adopts a pre-emptive priority-based scheduling paradigm which makes it an intriguing term of comparison with our model.
Secondly, its complexity in terms of number of concurrent activities, timing requirements, code size, and estimated processing load makes it a real challenge from a hard real-time design standpoint.
The activity was performed for the On-Board Data Division of ESTEC by Intecs Sistemi (Italy) with support from Matra Marconi Space (France), in the frame of a TRP contract over the period January through December 1993.
The activity was successively extended to port and test the software on to the actual EURECA test model with support from MBB ERNO (Germany) and DDC-I over the period January to June 1994. The developed code implements about 70% of the functionality of the original DHS, including all the real-time requirements.
The team included Mr. Sten Ekholm, the ESTEC technical officer, Mr. Tullio Vardanega, (ESTEC responsible for HRT-HOOD development). Mr. Ekholm consultant for methodologies, and myself, Alessandro Paganone, the Intecs Sistemi project manager.
The Software Design
The HRT-HOOD Architectural Design Phase defines a breakdown of the software system in a number of objects belonging to a set of specific and well defined categories.
The terminal objects of the architecture that belong to the hard real-time component of the system are either passive or sporadic (to model a-periodic activities) or cyclic (to model periodic activities) or protected (to encapsulate resource control mechanisms).
Intermediate non-terminal objects and/or terminal objects belonging to the background component (running at lower priority levels) can be active in the sense defined by HOOD.
The rules of HRT-HOOD ensure that the passive objects do not use constrained operations of active, sporadic, cyclic or protected objects and do not contain such objects as children objects. Further rules do not allow the hard real-time objects to call constrained operations of terminal active objects.
Furthermore, a good design should ensure that the hard real-time objects do not call operations with functional constraints (whose blocking time cannot be bound).
The HRT objects are annotated with attributes which describe their execution pattern, criticality and worst-case execution time (WCET) requirements.
The execution pattern specifies the period for all cyclic objects, the minimum inter-arrival time for all sporadic objects, the deadline for all cyclic and sporadic objects, and the offset for all objects related by any precedence order. The criticality attribute qualifies the deadline to be hard or soft. The WCET attribute specifies the execution time requirement of all objects and their operations.
The analysis of schedulability is the vehicle to guarantee that an HRT-HOOD design is feasible within the context of the target environment. This analysis is currently performed by a prototype tool developed for ESTEC by British Aerospace under the guidance of the University of York.
The current prototype allocates priorities per criticality level (these being hard, soft or non-critical) and reports on the schedulability of the individual tasks. Priorities are assigned with the Deadline Monotonic Scheduling (DMS) analysis. It requires the adoption of a blocking model based upon the Immediate Priority Ceiling Inheritance (IPCI) protocol.
This protocol causes the priority statically assigned to protected objects to be just greater than the highest priority of their users; in this manner, the blocking resulting from contention for access to shared resources may be easily bounded. The combined use of IPCI and priority queuing ensures full prevention against any sort of priority inversion problems.
An HRT-HOOD design is finally committed only if all hard deadlines are met.
The Software Development
HRT-HOOD incorporates a very natural mapping scheme onto the subset of Ada 83 considered for use. This subset excludes dynamic tasking, dynamic memory allocation and director indirect recursion which may impact on the accuracy of the WCET analysis. A set of mapping rules is available for Ada 9X also.
The current Ada standard does not fully support the model subsumed by HRT-HOOD. Few extensions are required; these have been kept in line with the corresponding features of the forthcoming Ada 9X standard. The full set of required extensions is as follows:
- The range of software priorities must be large enough to accommodate the priorities allocated according to the Deadline Monotonic Scheduling scheme.
- The concept of passive task (with similar semantics to the protected type of Ada 9X) must be provided to model the protected object of HRT-HOOD.
- The concept of absolute delay must be supported so as to permit a more exact modeling of periodic tasks This is perfectly equivalent to the “delay until” statement of Ada 9X.
- The concept of monotonic time (also foreseen in Ada 9X) should be supported so as to reduce the burden of a time-of-day based clock.
- Entry queues should be ordered according to current priority so as to prevent the occurrence of priority inversion.
The DACS-80×86 provided us with good support from this point of view, fulfilling requirements (1) (2) (5) and allowing efficient solutions for (3) and (4).
In spite of the system complexity and problems due to new technologies, my team (Ludovica Meloni, Fabrizio Sciarra and Riccardo Vettori, my blessing upon them!) was able to produce the software in the given time on an Intel 80386 (16 MHz) board plus external computers for device simulation.
About 13,000 Ada statements were produced, including 35 tasks. The actual execution times were measured using an HP analyzer and introduced in the schedulability tool. As expected, given the CPU power, the system was found out, largely schedulable, and the CPU load was less than 30%, including the simulation overhead.
Performance was the major cause of concern for us (Fabrizio Sciarra and myself) when starting the activity to retarget the code on the actual satellite testbed: EURECA has an Intel 8086 CPU and 128 Kbytes of RAM, thus, a big optimization effort was foreseen.
Our estimate (later confirmed by measurements) was a speed reduction of 7 – 9 times: applying such difference in the schedulability analysis tool, only the highest priority tasks were still schedulable.
The optimization followed three main lines:
- changes to the mapping rules of HRT_HOOD to cut out not strictly needed code;
- use of non-standard features of the Ada compiler system – mainly the pragmas Interrupt_Handler and Monitor_Task, the unsigned integer types and the semaphore services;
- deletion of code never stimulated in the performed tests – mainly the management of unissued TeleCommands and the management of devices’ misbehavior.
It is worth noting that the implementation details of the HRT entities were modified but not their semantics and their actual behavior.
Problems were expected also in the adaptation of the Ada RTS to the EURECA testbed environment.
As a matter of fact, the situation was of major concern: the details of the hardware were not very clear; the possibility to operate on the hardware was excluded (in particular, the board EPROMs could not be changed); the host platform for the Ada compiler system at MBB ERNO was a VAX/VMS™ instead of the SPARC~ used at Intecs; the VAX version of the Ada compiler system was earlier than the SPARC version used in the first implementation.
As a consequence, we decided to directly involve DDC-I in this phase. During the first weeks, Mr. Thomas Hansen, senior software engineer, DDC-I, supported us, providing a deep knowledge of the Ada RTS structure and detailed behavior. In the same period, Mr. Stephan Gallet, Matra Marconi Space, was involved in order to fix problems related to the mission database interfaces and the PPU s/w generation and loading.
Such high qualified support allowed us to set up a flexible development and test environment.
After that, only a small effort was needed to adapt our code to the new environment. The code affected by the porting was carefully localized in a few objects during the AD phase.
After further fine tuning of the code, we were able to run a number of the acceptance tests defined for the flight implementation, including a loading test that involves all the HRT features of the system.
The software ran properly except for sporadic overruns (autonomously recovered) of the lowest priority task with hard criticality.
After measurement of the execution times, the schedulability tool confirmed that all the hard tasks are schedulable, but the mentioned one is at the limit. A comparison was also possible with the execution times of the flight version, developed by Matra Marconi Space in C with a relevant percentage of Assembly.
Here is the result, together with other important lessons learned during this work:
- Ada, when explicitly designed and implemented to match HRT constraints, is slower than C and Assembly, but not too much. The execution times of the flight implementation are 30-40% shorter than ours. The overall CPU load is comparable. On the other hand, the Ada executable size is considerably higher.
- The DDC-I Ada Cross Compiler System allows full use of the features of the language, particularly useful in embedded real-time applications.
- HRT-HOOD and Ada are suitable to the design and implementation of hard real-time software systems for embedded applications.
- The cost of code development with HRT-HOOD and Ada (in particular its re-targeting) can be amazingly low.
- The Ada tasking allows a more representative modeling of the concurrent activities. The induced overhead may be reduced without affecting the good structure of the code provided by the object oriented approach.
- The schedulability analysis tools represent valid help to the designer during the software life cycle. They allow to validate the dynamic behavior of the system. The output has a good correlation with the actual (measured) software behavior.
Finally, to summarize all my findings into one conclusion: Yes, there is more code and one has to spend a bit more for RAM, but the benefits of a good design (with appropriate tools) and the security of Ada lower the development test and maintenance costs to a greater extent, while performance pro blems can be well solved by modern 32-bit processors [and/or tasking co-processors].