A.-E Rugina
email: ana-elena.rugina@astrium.eads.net

J.-C Dalbin

Experiences with the GENE-AUTO Code Generator in the Aerospace Industry

Keywords:

This paper gives an overview of the most recent experimentations that Astrium and Airbus conducted with the GENE-AUTO code generator during 2009. GENE-AUTO is an open source automatic and qualifiable C code generator taking as input Simulink®/Stateflow® and Scilab/Scicos models. It was developed in the context of an ITEA European project that ended in December 2008

(www.geneauto.org). The GENE-AUTO toolset is currently maintained by its developers and evaluated for industrial usage by several end-users. This paper presents the case studies that we used for evaluation purposes, explains the organisation between the users and technology providers with respect to the toolset maintenance and summarizes the experimentation results.

Introduction

The development of real-time embedded systems, such as those in the aerospace domain, faces wellknown increasing constraints, in particular related to higher system complexity and shorter time to market. Such conflicting requirements are the origin of significant efforts towards the improvement of the current development processes. In the aerospace industry, increasing complexity is due to increasing functional requirements as well as related to autonomy, safety, performance and dependability. This complexity maps to a growing number of software functions that must be thoroughly tested and compliant with the certification standards (DO178B for aeronautics, ECSS for the space domain). In addition, in the space industry, the system must be designed to favour maintainability during system operation. On the other hand, reducing the cost and the time to market is mandatory for obvious competitiveness reasons. In this context, the definition of optimized engineering practices is imperative. Automatic code generation has already proven very effective in shortening the time to market and in guaranteeing the quality of the generated code especially if the code generator is qualified. Since 2002, Airbus has extensively used a software development process including Qualified Automatic Code Generation (ACG) with significant and measured savings:

• Airbus has never experienced problems in flight due to coding errors in the Flight Control System software. • Software development time was divided by [START_REF] Izerrouken | Certifying an Automated Code Generator Using Formal Tools: Preliminary Experiments in the GENE-AUTO Project[END_REF] (including verification activities), compared to a process without ACG. In the context of space applications, several experiments were conducted to assess the advantages of automatic code generation. In particular, Astrium demonstrated through several projects and experiments (e.g., DIVAS [START_REF] Diris | Astrosat 250 Core Avionics Hardware in the loop Demonstration using Fast prototyping Technologies[END_REF] and LOLA [2]) that automatic code generation brings a real gain in efficiency in the context of fast prototyping for systems requiring complex algorithms and multi-tasking. Astrium also conducted internal studies (e.g., SCAOGEN) to evaluate the use of modelling and automatic code generation in the regular system and software development process of the satellite Attitude and Orbit Control System (AOCS). The aerospace and automotive industries joined their efforts in order to define a common development workshop for critical embedded systems, using standard formalisms and opensource tools. This objective led to setting up the GENE-AUTO project (www.geneauto.org) in 2006 in the context of the ITEA European research program. Both Airbus and Astrium were members of the GENE-AUTO consortium. The concrete objective of the project was to develop an automatic and qualifiable C code generator from models created with Simulink®/Stateflow® and Scilab/Scicos. The project ended successfully in December 2008. The GENE-AUTO toolset is currently maintained by its developers and evaluated for industrial usage by several end-users. The advantages offered by the GENE-AUTO toolset are as follows:

• It was designed and developed based on a common set of user requirements coming from the automotive and aerospace domains and having in mind certification (DO178B level A).

• It is open-source (GPL licence), which favours the long-term maintenance (up to 30-50 years) and the independence with respect to providers' policies. • Its architecture is modular and flexible. Based on model-driven engineering concepts, GENE-AUTO consists in a set of elementary tools and intermediary models that make it highly evolvable. In particular, the users are able to define their own supported block library (i.e., users can define the code to be generated for model blocks that are not supported by the public GENE-AUTO toolset), or the code optimizations that are required for a specific hardware target. Also, even though the C language has initially been selected as target, it is possible to target a different language, e.g., Ada, with a minimum amount of effort. • It represents a proof that formal methods can be successfully integrated in such tools. Indeed, a proof assistant was used for implementing one of the GENE-AUTO elementary tools [START_REF] Izerrouken | Certifying an Automated Code Generator Using Formal Tools: Preliminary Experiments in the GENE-AUTO Project[END_REF], [START_REF] Izerrouchen | Machine-Checked Sequencer for Critical Embedded Code Generator[END_REF]. This paper presents the experiments conducted in 2009 by Airbus and Astrium with the GENE-AUTO code generator, based on models currently used during system design and that are the basis for software development. The remainder of the paper is structured as follows. Section 2 gives an overview of the experimentation context both from the point of view of the technical objectives and of the industrial organization between the toolset users and its developers. Section 3 sketches the characteristics of the selected case studies, while the main experimentation results are summarized in Section 4. Section 5 concludes the paper.

Context and Industrial Organization

Both Airbus and Astrium had conducted earlier experimentations during the GENE-AUTO ITEA project. Some of the results have been presented in [START_REF] Rugina | GENE-AUTO: Automatic Software Code Generation for Real-Time Embedded Systems[END_REF]. The subsequent experimentations that we have conducted in 2009 aimed at improving both the users' confidence in the toolset and the maturity level of the GENE-AUTO technology. The second objective mentioned above can only be fulfilled if the technology evolves based on the user feedback. This is the reason why we have set up a maintenance contract between Airbus and Astrium as users on the one hand and Alyotech and IB Krates as developers of GENE-AUTO on the other hand. The adopted maintenance scheme had the advantage of federating the efforts both on user and developers sides. From a practical point of view, a common web-based tool was used for the support requests. Periodic Change Control Boards gathering all stakeholders allowed prioritizing the actions with respect to the available budget, distributing the charges and workload and deciding about the contents and dates of new releases. Most of the work has been performed in the framework of the OBSYS EADS demonstrator, which gathers the various EADS Business Units in their efforts towards engineering process optimization and practical integration of new technologies.

Case Studies

Flight Control Logic & Laws (Airbus application)

The targeted objectives of the Airbus case studies were related to two topics: system design and software design, as follows.

From the system design point of view, the aim was:

• to enhance the current design practices by using modelling features such as automata, vectors and buses, • to experiment the ability to modify and to mix existing formalisms (data flow named SAOformer version of SCADE) with Simulink®/Stateflow®, taking advantage of the expressiveness power of new modelling concepts without having to completely re-specify existing specifications. From the software point of view, the aim was:

• to participate in the maturation of the GENE-AUTO toolset by using it on current specifications (within a DO178B software development context), • to test the ability to customize the source code produced by GENE-AUTO for specific needs (coding standards, optimization, reducing CPU consumption), • to evaluate the generated code, in terms of CPU and memory consumption, on a real HW target, • to evaluate the integration of code generated by GENE-AUTO with legacy code. The code generated by GENE-AUTO was compared with reference code generated by tools currently used at Airbus. The model was developed using the R2006b release of TheMathworks TM tools (Simulink®, Stateflow®). The performance analyses (CPU time and memory consumption) were carried out by using logical analysers dedicated to the target HW (Intel 486).

In the first case study (named StickPriority), a part of the Flight Control Logics was re-designed using state-machines to improve expressiveness of the specification. From a practical point of view, in this first scenario an existing SAO node (pure data flow) was replaced by a Simulink® model calling a state machine. As we can see in Figure 1, this Simulink® model includes a part of the existing data flow. The use of the automata allows identifying directly the five states previously buried in the pure data flow. This MIMO corrector is composed of two components: the corrector C1 in Figure 3 (activated at a sequencing cycle of 10ms) and the precommand C3 in Figure 4 (activated at a sequencing cycle of 40ms). C1 is a purely vector model, while C3 uses a mix of scalar and vector symbols. Within the Simulink® model all used symbols were defined as subsystems (to have the same interfaces as SAO symbols). Each subsystem was defined with Simulink® native symbols. For each of them an occurrence number was affected within the mask parameter (they are used for code in-lining). Software production Two different pieces of software were developed from each model: 1. For the first one (GeneAuto_Pur), the C source code was produced by GENE-AUTO with no code generation option. 2. For the second one (GeneAuto_Bib_Embarque), GENE-AUTO was used to replace Simulink® symbols by a set of macros call written manually (Airbus macro library used with SAO specification). To allow GENE-AUTO to support the platform specificities (and to allow to re-use of the Airbus library) for the symbols, its standard block library was extended through a set of user-defined typers and backends (the source code for the vectorial symbols was developed from scratch). Relevant symbols were AND, COMP1, LD, OR, PULSE1, PULSE2, ADD, ADD_VEC (vector addition), DELAY, DELAY_VEC (vector delay), DIVR, LIM, MULT, MULT_VEC (matrix / vector multiplication), SUB, SUB_VEC (vector subtraction), SWITCH_N. For these two pieces of software, the code generated by GENE-AUTO was a reusable C function. Wrapping code was developed for updating the input parameters before the call of the function and the output parameters afterwards.

AOCS System (Astrium application)

The case study selected by Astrium is based on a recently-developed demonstrator for the new avionics features of the AstroSat 250 platform (targeting low earth orbit missions). The AstroSat 250 platform is based on a new computer including a LEON3 processor, on a new generation start tracker and on a gyroless attitude and orbit control mode running at 16Hz (based on star tracker and control moment gyro actuators). The architecture of the demonstrator is presented in Figure 5. The on-board software (OBSW) and its environment are both specified in a closed-loop Simulink® model. It is noteworthy that there is strict separation between Simulink® models of the OBSW and of the environment. In the original demonstrator, C code was generated from the model of the application software within the OBSW (the data handling layer was manually coded) and the environment model by using the Real-Time Workshop (RTW®) code generator provided by TheMathworks TM . The generated pieces of code corresponding respectively to the OBSW and to the environment have been each installed on different computers connected with the actuators through a network. The goal of the experimentation with GENE-AUTO was to replace the code generation of the OBSW application software that was originally performed with RTW® by a code generation with GENE-AUTO. The OBSW Simulink® model is formed of 3186 blocks architected in 10 hierarchical levels. To be able to run, about 2000 constants must be initialized prior to the execution (originally, the initialization was done through the workspace by loading a .mat file). Matlab® functions (e.g., trigonometric functions) are extensively used in the model, as well as Embedded Matlab® blocks containing control laws and algorithms representing mode automata. The model also contains a large number of execution control blocks such as Switch and SwichCase.

Two Stateflow® charts were also added on the one hand to evaluate the approach of coupling dataflow with Stateflow® models and on the other hand to fully test the capabilities of GENE-AUTO. The model has been developed using the following releases of TheMathworks TM tools: In addition, we have performed several modifications on the legacy model. They fall into the two following categories that are further detailed in the next paragraphs:

• Matlab® 7.5 (R2007b) • Simulink® 7.0 (R2007b)
• Modifications for compliance of the input model with the GENE-AUTO scope. • Integration of Stateflow® features in order to evaluate on the one hand the approach of coupling dataflow with Stateflow® models and on the other hand to fully test the capabilities of the GENE-AUTO code generator. Model Modifications for Compliance with the GENE-AUTO Scope Parameter Initialization: Usually, the Simulink® simulations require the initialization of a number of parameters before execution. This can be performed in two ways: either by executing a Matlab® script stored in an .m file, or by loading a workspace image (load a binary .mat file). In our legacy model, the initialization is performed by loading a .mat file, while GENE-AUTO is able to parse simple .m files that perform constant initializations. It is not able to read binary .mat files 1 . Thus, we needed to create a .m file from the .mat file. For that, we used a rather artisanal method. We have been able to extract automatically the scalars by using a Matlab® script but this method did not succeed in retrieving the structures. We have thus retrieved them manually by inspecting the workspace once the .mat file has been loaded. Matlab® Expressions: Currently, GENE-AUTO does not support the use of Matlab® expressions in Constant blocks. Our legacy model uses such expressions on a regular basis. Sometimes it is simpler to use such expressions than to use Simulink® blocks. However, they may be replaced by Simulink® blocks (e.g., arithmetic and trigonometric operations) that are currently supported by GENE-AUTO. Unsupported Blocks: Our legacy model was not created having in mind the blocks supported by GENE-AUTO. A number of unsupported blocks were thus present in the model. Some of them could be replaced by equivalent sets of supported blocks. Transitions are guarded by conditions referring to inputs and sometimes specify actions represented as output port data updates. The states specify entry and exit actions for updating the output data ports, e.g., the one corresponding to the current mode. Junctions are used as a simplification facility allowing to represent pseudo-states (states with no associated action but necessary to separate more complex control paths). Figure 6

Experimentation Results

Our experimentations aimed at evaluating the generated code from different perspectives (e.g., code correctness, size, quality, traceability between model and code, CPU and memory consumption) and at investigating the straightforwardness of the integrating of generated code with legacy code. Our results with respect to the various topics are summarized in the following paragraphs. Generated Code Correctness Astrium read parts of the generated code to asses its correctness. The generated code was executed in the model loop. Airbus has even performed a functional verification of the generated code on the real target. During this functional verification, the generated code was stimulated by using standard input value sets and we observed identical behaviour on its outputs as the reference software used in a real context. These activities allowed us to identify few issues regarding the generated code, such as:

• Incorrect use of constants with values between 0 and -1.

• Without optimization option, GENE-AUTO produces a large amount of memory affectations (temporary local data).

• The headers used in the generated code include a "math.h" (which is not qualified in the embedded software context). • Matrix product did not use the correct index (computation with a value out of array limit). • Wrong type propagation between double and simple precision for floating point numbers. The identified issues were reported and most of them are already solved (for the experimentation purpose, the generated code was corrected by hand). We have not found many bugs in the generated code, but on the other hand, we have a number of suggestions for extending GENE-AUTO to support more Matlab®/Simulink® functionality. In particular, Astrium suggested a concrete list of additional Simulink® blocks and a subset of the Embedded Matlab® language. Code Size In our previous experimentation Astrium had compared GENE-AUTO generated code with manual code derived from the same specifications and found that the two were comparable in terms of size, number of comment lines and complexity. In the current experimentation, Astrium compared the GENE-AUTO generated code with RTW® generated code. We noted that the GENE-AUTO generated code size (measured in LOC) is three times smaller than that of the RTW® (RTW® standard edition) generated code from the same Simulink® model. Also, the amount of comment lines for GENE-AUTO generated code is higher (27%) than for the RTW® generated one (16%). Traceability between Model and Code Traceability between model and code was analysed by reading the generated code and comparing it with the input model. We have not identified any particular problem (the analysis was conducted on code generated without using the code optimization module of GENE-AUTO). The comments placed in the generated code point back to the original model elements. It is noteworthy that the names given to intermediary variables and input/output structures corresponding to blocks are rather unreadable if the corresponding names are not specified in the input model. CPU and Memory Consumption Code generated by tools currently used at Airbus (named reference_SAO) was used as reference for the comparison of CPU and memory consumption. The generated software releases did not reach the expected performance level for several reasons (non-optimized legacy code for vector computation, need for updating of the input/output parameters of the C function, extensive uses of temporary local data, use of double precision in the input model). The exploitation of the code optimizer of GENE-AUTO (which suppresses intermediary useless variables) and the use of simple precision variables (instead of double) allowed obtaining results similar to those of the reference code in terms of CPU performance. We observed an increase of the memory consumption (especially the RAM) when using vectors with GENE-AUTO. This is once again due to the important use of local variables instead of global ones (as it is done in the reference code). The ROM consumption is also greater, due to the use of more complex computation (matrix computations, for loops, etc.). Code Quality During the ITEA European project, we had used commercial tools Logiscope TM Rulechecker in order to evaluate the generated code quality with respect to the Astrium C-coding standard that is used for manual code. The additional experimentation conducted in 2009 did not reveal any changes in the characteristics of the generated code: most of the coding rules are fulfilled. Only a naming rule is violated very often but the names in the code depend mainly on the existing names in the input model, which should follow the naming rules set for the manually-written code. MISRA rule 11 is also often violated (Identifiers shall not rely on the significance of more than 31 characters). Longer variable names do exist in the code. However, these names are derived from the model.

Integration of Generated Code with Legacy Code

In a real operational environment, we can expect to have to integrate legacy code (manually written or generated with another tool) with the generated code. Therefore, it is interesting to investigate the ways integration may be performed. The Astrium case study model includes many Embedded Matlab® blocks, which are currently not supported by GENE-AUTO. As a consequence, our strategy was to generate code with RTW® from the Embedded Matlab® blocks and then integrate the code generated with RTW® and GENE-AUTO. There are several ways to integrate parts of code generated by GENE-AUTO with parts of code generated by another tool from a given model. The first method is manual and consists in the following steps:

• Masking all subsystems that are not to be generated by GENE-AUTO thus forcing the code generator to ignore them (a comment will appear in the generated code as replacement of the corresponding function call). • Generating the code from those subsystems with another code generator. • Integrating the pieces of code by hand.

Another method consists in the following steps:

• Generating the code from the selected subsystems with another code generator than GENE-AUTO. • Replacing those subsystems inside the model by legacy code S-functions (using the generated code). • Generating code from the whole model with GENE-AUTO. We have selected this second method, since part of the integration work is performed automatically by the GENE-AUTO code generator. Indeed, GENE-AUTO is able to parse legacy code S-function blocks and call the associated legacy code from the GENE-AUTO generated code, provided that the corresponding S-function blocks are masked and that the mask properties are set properly. In practice, the integration of the RTW-generated code back into the model requires using a wrapper, as the RTW-generated function has no input parameters and no return values (the inputs and outputs of the block are stored in a globally declared structure containing one data for each port). On the other hand, the convention for a legacy code Sfunction is that each return value is converted into an output port of the corresponding Simulink® block and each input parameter is converted into an input port of the block. Hence, it is necessary to wrap the RTW-generated S-function in order to import it back again in the Simulink® model with explicit input and output ports. The wrapper function assigns the values of the parameters of the wrapper function to the elements of the globally declared input structure. Then it calls the automatically-generated function. At the end, it assigns the values of the globally declared output structure elements to the output parameters of the wrapper function. Software Investigation Airbus conducted experiments for the introduction of "investigation variables" or probes represented in the Simulink® model by scopes to give visibility to some internal variables. A particular backend was developed to exploit the scopes in the generated code. These extra-variables used here for the software debugging phase would be also very useful for the validation teams. This has to be further studied in order to determine the relevant (necessary and sufficient) states or signals we need in order to perform the system validation.

Conclusion

The experimentation conducted in the context of the OBSYS EADS demonstrator met its objectives, i.e., increase both our confidence in GENE-AUTO and the maturity level of the toolset. We demonstrated the functional equivalence between the reference code/model and the code generated by GENE-AUTO from models using different formalisms (Simulink®, Stateflow®, SAO). The use of automata and vectors improve the readability and ease the understanding, thus the maintainability of a system specification. We found few bugs in the current GENE-AUTO toolset, whose maturity level is rather good, taken into account its age and history. On the other hand, we have identified useful enhancements for the toolset. In particular, we believe that enriching the supported block library would be of much help for potential users. We have suggested a list of additional blocks to be supported. Moreover, taken into account the confirmed trend to replace C code S-functions by Embedded Matlab® blocks in Astrium Satellites, support for Embedded Matlab® becomes very important. More generally, further investigations related to the code generation could focus on the use of local variables vs. global variables and optimizations (e.g., temporary local data, matrix computation to avoid for example full computation when matrices are not full). It was demonstrated that GENE-AUTO allows to customize and to optimize the source code, similarly to the Airbus code generator. The results in terms of performance (with the right options and with the last releases of the toolset) are similar to those of the Airbus code generator. This experimentation allowed us to estimate the maturity of the technology of the GENE-AUTO code generator, which we consider having reached a level of 5 for Airbus and 4 for Astrium (Airbus conducted experimentation on a real case study involving operational teams with system designers and software developers, while Astrium conducted its experimentation on a representative demonstrator case study). Improvement of performance and extension of capabilities of the generator are still necessary before bringing the tool into the industrialization phase. We found that the maintenance organization that we have set up was effective, allowing to federate efforts both on user and provider sides. The OPEES initiative should enforce these conclusions and the long-term maintenance of the toolset through a community of users and developers.

Figure 1 :

 1 Figure 1: Re-designing the Original Model to Include State Machines In the second case study (named MIMO Corrector), a part of the Flight Control Laws was re-designed using discrete vector based model (see Figure 2). 38 SAO nodes similar to the one shown in Figure 2 are necessary to represent a Kalman filter defined in Simulink® as MIMO correctors.

Figure 2 :

 2 Figure 2: Re-designing the Original Model to Include Vectors

Figure 3 :

 3 Figure 3: MIMO Corrector C1 Simulink® Model

Figure 4 :

 4 Figure 4: MIMO Pre-command C3 Simulink® Model

Figure 5 :

 5 Figure 5 : Demonstrator Architecture

  Embedded Matlab®: Our legacy model made extensive usage of Embedded Matlab® blocks for representing algorithms and mode automata. Since GENE-AUTO supports legacy code but currently has a limited Matlab® support (only for usage in the initialization .m file), we decided to replace the Embedded Matlab® blocks representing algorithms by S-functions generated with RTW®. This also allowed us to experiment the integration of code generated by different tools. This topic is further detailed in section 4. Integration of Stateflow® Features Our legacy model included two mode automata represented by Embedded Matlab® blocks. While the other Embedded Matlab® blocks were replaced by S-functions, we decided to use Stateflow® to model the two mode automata. The Embedded Matlab® representation of the mode automata is a function with data inputs and outputs (the data ports of the block) in which the output values are set depending on the values of the commands received on the input ports (global if-then-else control structure). The translation of such a representation into a Stateflow® chart requires identifying the different states (the different "if" conditions) and the rule allowing to set the outputs depending on the internal state and the values of the inputs. The chart if formed of states, transitions and junctions.

  depicts the translation process for the mode automaton from the Embedded Matlab® block to the Stateflow® chart.

Figure 6 :

 6 Figure 6: Mode Automaton Translation from Embedded Matlab® to Stateflow®

Such files are built directly in Matlab®/Simulink® by saving the workspace and their structure is not public.

Acknowledgements

The authors would like to thank the toolset development and maintenance team from IB Krates and Alyotech for its valuable support and responsiveness.


Keywords: Infotainment, Genivi, Moblin, Linux realtime, latency measurements

Real Time on Moblin/Linux

Yannick MEYER 1 (main author), Abdelillah YMLAHI OUAZZANI [START_REF] Blaess | Programmation système en C sous Linux[END_REF] 1: ESG Automotive France, Centre Paris Pleyel -153, Boulevard Anatole France -93521 -Saint-Denis Cedex Abstract: The automotive manufacturers are more than ever facing many challenges. With the tremendous involvement of electronics in the achievement of end-customers needs, automotive suppliers must accommodate themselves to the constantly changing features of carmakers. Infotainment is one of the most challenging fields, where the carmakers and suppliers realized that the use of a dedicated platform for each new car is no longer possible. This is why the GENIVI alliance was founded on March 2nd, 2009 with the goal of establishing an open platform for the automotive invehicle infotainment industry. GENIVI's strategy is to use Moblin as the baseline code within its reference implementation. Moblin is a Linux-based distribution designed for mobile devices and can perfectly be used in embedded devices such as those targeted by the infotainment industry.

In this paper we experiment the real-time performances of Moblin as a standalone operating system and show how those performances can be improved by means of adding some customized realtime extensions. The main contribution of this work is to outline how those extensions are in fact necessary to comply with the real-time constraints required by automotive hosts on which infotainment applications are embedded.

Introduction

GENIVI is self-described as a non-profit industry alliance committed to create and promote an In-Vehicle Infotainment (IVI) reference platform. The platform consists of Linux-based core services, middleware, and open application layer interfaces. It establishes a base upon which carmakers and suppliers can add their variety of products and services.

At ESG, we anticipated at early stage the development of an automotive infotainment platform similar to what GENIVI alliance would expect. We invested ourselves in technical training and purchase of a "GENIVI-like" platform and started evaluating its software and hardware performances. After few weeks of evaluations, we explicitly expressed our motivation to actively participate in the development of automotive Infotainment architectures within the GENIVI alliance and we joined it as associate member on January 2010.

Moblin is an open source operating system, acting as an independent distribution for the first GENIVI open source implementation. The combination of the Moblin and GENIVI codes will be used to provide carmakers and suppliers with an automotive infotainment reference platform mixing the best from both consumer and automotive worlds. In automotive field, any embedded software system must deliver both speed and accuracy. Speed is needed to run large bodies of software ECUs, including real-time operating systems and network protocol stacks. Accuracy, reflected by the latency time, is needed to ensure correct and predictable behavior in the vehicle. In fact, deterministic latency time is one of the core requirements of "hard" realtime constraints.

Moblin is

In contrast to those "hard" constraints, Linux and mostly all distributions based on it satisfy only "soft" real-time requirements. For example, Linux can provide speed to manage tasks priorities but with unpredictable latency time, varying from less than one millisecond in most cases up to several milliseconds in some others.

Missing a deadline in "hard" real-time requirements implies a catastrophic behavior (like activating a security airbag too late in time). In "soft" real-time requirements such a missing causes system failure but doesn't alter the general behavior (like losing a video frame or gps connection).

In this paper, we report our experience in evaluating the real-time capabilities of Moblin v.2.0b3 on a generic infotainment platform composed of the following peripherals:

• Processor: the Intel Atom Z530 (1.6 GHz) • Memory : 1GB RAM DDR2, 2GB Flash • Display : VGA touch screen • Audio : HD-Audio • Connectivity: Ethernet, GPS antenna, CAN • Misc: 8 x USB 2.0, RS232/422/485, GPIO In addition to that, we used an external board called "Measurement Board" to stimulate the "Moblin platform" and measure its reaction time to the input stimulus.

We tested first the real-time behavior of Moblin-Linux APIs to point out its limitations. Then we added the real-time extensions RTAI and XENOMAI (Cf. §.5 and §.6), once at a time, and evaluated again the new behavior.

The rest of the paper is organized as follows. Section 2 describes the testing methods. Section 3 is dedicated to the real-time capabilities of Moblin. Section 4 explains how the real-time extensions can be added to Linux. Section 5 and 6 discuss the realtime performances of Moblin with the real-time extensions RTAI and XENOMAI respectively, and Section 7 concludes.

Testing methods

Preparation

We reserved the first activity of this project to the building of the Moblin image from the kernel source package kernel-2.6.29.4-6.1.moblin2.src.rpm available online at Moblin's repository [3]. Then, with some few adjustments, we were able to drive the hardware platform.

The second activity consisted in setting up the test bench by connecting the "Moblin platform" to the "Measurement Board". Figure 1 illustrates how we connected the boards; the hardware connection was ensured by a serial RS232 cable for data exchange and a double wired cable to control a GPIO pin. The evaluation of the real-time capabilities of the "Moblin platform" is composed of two sets of tests:

• Measuring the latency time the "Moblin platform" takes before responding to an external event.

• Measuring the scheduling time of a periodic task implemented in the "Moblin platform".

Those two tests cover mostly all cases in which embedded software is to be used. In the next subsections we explain the tests design and setup.

Measurement of the latency time in response to an external event

The main purpose of this test is to measure the minimal, average and maximal latency time consumed by the "Moblin Platform" before it reacts to an external event. Figure 2 shows how we designed this test. We stimulated the "Moblin platform" by an external event generated by the "Measurement board". The event consisted in sending a character through the serial communication device. We saved the time stamp when the character was released on the "Measurement board". We labeled it the "Test starting time". Upon the reception of that character, the "Moblin platform" toggled the GPIO pin, the "Measurement board" detected this change of state immediately and saved its occurrence time as the "Test ending time".

Based on the "Test starting time" and the "Test ending time", the "Measurement board" calculated the "latency time" and sent it back to the "Moblin platform" through the RS232.

Finally, we compared the obtained results to the reference value of 40µs which reflects a targeted value of the system at early characterization phases.

The way we found this reference value is outside the scope of this document.

Measurement of the scheduling time of a periodic task

The main objective of this test is to measure how accurate is the management of internal scheduling of tasks within the "Moblin platform". Figure 3 depicts the test design. We implemented a periodic task which consisted in changing the state of a GPIO pin in the "Moblin platform". We were interested in calculating the periodicity of this task when the "Moblin platform" was "lightly" and "fully" loaded. (Cf. §2.4)

We configured the "Measurement board" to calculate the time separating two consecutive GPIO rising edges and transmit this time back to the "Moblin platform" for measurement statistics accumulation.

Finally, we compared the cumulated statistics to the task reference period; the acceptance range has been set from -5% below to +5% above that reference period.

Tests conditions

We ran the set of tests described above in different configurations to simulate multiple environments where the infotainment applications can be incorporated. Intel's Atom processor CPU frequency can be adjusted on the fly from 800 MHz to 1.6 GHz depending on the system load. For the purpose of tests we have chosen to run at known frequency.

We evaluated the application test in both "light" and "full" loads configurations.

We define the "light" load configuration as the case when only the test application process is running along with Moblin on the "Moblin platform".

We define the "full" load configuration as the case when the test application process is sharing the 100% CPU load with two other hardware resources consuming processes: one is reading endlessly a USB memory stick and the other one is incrementing a counter. We set up the test application process with the highest priority level over all other processes.

Note:

We have chosen the USB key reading process in order to put the system in interaction with an external environment, like that, the reading process preempted the kernel scheduling constantly.

Real-time capabilities of Moblin-Linux

This first experiment evaluates the real-time performances of Moblin-Linux APIs. The test application uses the Linux native APIs and the realtime parts (latency or task scheduling) use specific drivers to achieve the test objectives. In this case the drivers are also using the Linux-APIs. The detailed architecture is shown below: We set up the CPU frequency at 1.6 GHz and we ran the test application in "light" load configuration.

Latency time measurement test

We tested one million samples, for each sample we calculated the latency time of the "Moblin platform". The cumulated statistics are shown in Figure 5. We found that almost 90% of samples had a latency time less than 40µs, whereas almost 1% of samples had that time higher than 5,5 ms. the latest 1% samples don't comply with the real-time deterministic requirement.

Periodic task scheduling measurement test

We ran the periodic task scheduling test one million cycles, each time we saved the task activation period in the "Moblin platform".

The smallest timer period that can be configured in "Moblin platform" is 1ms, so we set the task reference period to 2ms. The cumulated statistics are illustrated in Figure 6. The y-axis is given in a logarithmic scale. This graph shows that almost 98 % of calculated periods were from -3.5% to +2.6% around the expected value. However we noticed a high dispersion of all remaining values, which means that Moblin is not managing the task scheduling uniformly. In addition to that, more than 2000 samples had their periods 170% above the reference period (the peak on the right side) and this was out of the tolerated range.

Note: the maximum value that the "Measurement Board" can return is 5,5 ms. In other words, the real maximum latency time and task scheduling period values observed are in fact higher than the 5,5 ms limit reached in tests.

Assessment

Those two tests demonstrated the weaknesses of Moblin with respect to real-time constraints. Linux lacks determinism in response to interrupt events, and it can not manage periodic tasks scheduling adequately.

Moblin can not then be categorized in "hard" realtime systems class because it can not afford the desired deadlines of real-time tasks. However it can be considered to support the expected deadlines on average since it has an average time response lesser than 50µs; this is why it is said to belong to "soft" real-time systems class.

In the next section we will discuss how Moblin's realtime capabilities can be hardened by means of realtime extensions.

Adding a real-time extension to Linux

There are several options available to enhance the real-time features of Linux, some of these are based on Linux alone (changing the kernel configuration), some use Linux with an additional sub-kernel, and since kernel 2.6 software patches are used to improve the real-time behavior of Linux. Here we focus our study on the configuration of Linux with a sub-kernel; this technique consists in using a second kernel as an abstraction layer between the hardware and the Linux kernel. The non-real-time Linux kernel runs in the background as a lower-priority task of the sub kernel and manages all non-real-time tasks. The real-time tasks are processed by the sub kernel. (See Figure .7)

Figure 7: The real-time extension approach Among all solutions we have chosen the RTAI and XENOMAI sub-kernels. We configured those extensions to run on the "Moblin platform".

The test application uses the Linux native APIs and the real-time parts (latency or task scheduling) use specific drivers to achieve the test objectives. In this case the drivers are using the real-time APIs instead of the Linux APIs. The detailed architecture is shown below:

Figure 8: Test application with Linux and real-time APIs architecture

We executed the same set of tests already described in section 2 to evaluate their added-values in improving the real-time performances of Moblin.

Real-time capabilities of Moblin + RTAI

RTAI stands for Real-Time Application Interface. It is a real-time extension for the Linux kernel, we setup and configured Moblin + RTAI to get it running on the platform.

Latency time measurement test

We carried out the latency time measurement test on lightly and fully loaded systems at both 800 MHz and 1,6 GHz CPU frequencies. We tested one million samples, for each sample we recorded the latency time. The total statistics are represented by Figures 9 and10. At 800 MHz, the dashed line graph represents the response of a fully loaded system; in this case the average latency time was 13,8 µs with 99% of samples below 28,8 µs.

The straight-line graph represents the response of a lightly loaded system; the average latency time was 20,3 µs with 99% of samples below 33,1 µs. Two peaks centered on 13 µs and 24 µs were detected, the reason behind is due to the internal architecture of the Intel's atom processor. Indeed, we noticed that when the processor is not fully loaded it goes into a sleep state and the response to an external event is then delayed by the wake-up time the processor takes before resuming normal operations.

Figure 10: Moblin + RTAI latency time at 1,6 GHz At 1,6 GHz, the dashed line graph represents the response of a fully loaded system; the average latency time was 13,3 µs with 99% of samples below 32,1 µs, the main difference compared to the 800 MHz case was that the values were more squeezed to the left and the average was slightly smaller.

The straight-line graph represents the case of a lightly loaded system; the average latency time was 15,6 µs with 99% of samples below 25,5 µs, which means that the performance has been improved by 25% compared to the 800 MHz case.

Most of the samples were between 10 and 15 µs and here also we observed another small peak around 23 µs, this was caused by the processor wakeup time.

Note: Only 0.1% of measured samples exceeds the reference latency time of 40 µs but remains below 100 µs.

Periodic task scheduling measurement test

We set the task reference period to 2.5 ms, we carried out the periodic task scheduling test one million cycles; at each cycle we recorded the task activation period in the "Moblin platform".

The cumulated statistics are illustrated in Figures 11 and12.

Figure 11: Moblin + RTAI periodic task at 800 MHz At 800 MHz, the graphs almost matched, for both fully and lightly loaded systems 98 % of samples were from -0.6% to 0.54% around the reference period.

Figure 12: Moblin + RTAI periodic task at 1.6 GHz At 1,6 GHz, for a fully loaded system, 98% of values were from -0.16% to 0.17% around the reference period.

For a lightly loaded system, 98 % of values were from -0.16% to 3.15% around the reference period.

In this case we noticed a high dispersion of values above the expected period.

Assessment

We obtained the best real-time performances of Moblin plus RTAI extension with fully loaded systems. RTAI improved the Moblin management of external events but lacked determinism in scheduling periodic tasks.

Real-time capabilities of Moblin + XENOMAI

XENOMAI is a real-time extension cooperating with the Linux kernel, newer than RTAI and more "hard" real-time oriented. We setup and configured Moblin + XENOMAI to get it running on the platform.

Latency time measurement test

We carried out the latency time measurement test on lightly and fully loaded systems at both 800 MHz and 1,6 GHz CPU frequencies. We evaluated one million samples. The total statistics are depicted by Figures 13 and14.

Figure 13: Moblin + Xenomai latency at 800 MHz At 800 MHz, fully loaded system has an average latency time of 14 µs with 99% of samples below 19,1 µs while lightly loaded system has an average latency time of 16,2µs with 99% of samples below 25,8µs.

Like RTAI, we observed another peak due to the processor low power mode around 23 µs. Figure 15: Moblin + Xenomai periodic task at 800 MHz At 800 MHz, both fully and lightly loaded systems had 98% of samples situated from between -0.6% and 0.56% around the reference period.

Figure 16: Moblin + Xenomai periodic at 1.6 GHz At 1.6GHz, fully loaded system has 98 % of values located at +/-0.2% around the reference period, while lightly loaded system has 98% of samples from -2.4% to 2.9% around the expected value.

In the second case, due to the processor low power mode, we noticed a dispersion of values but the average remained acceptable.

Assessment

The best real-time performances of Moblin + XENOMAI extension were obtained with both fully and lightly loaded systems; XENOMAI is deterministic with respect to "hard" real-time constraints governing the handling of external events and the scheduling of periodic tasks.

Conclusion

Many Linux real-time extensions and distributions are becoming available, they are responding to the high technical use of embedded Linux in various domains. Since multiple approaches are available, it is obvious that no one solution will serve all applications best. In this paper, we have evaluated and tested the real-time extensions RTAI and XENOMAI with Moblin in different configurations. We outlined the limitations of Moblin and the RTAI approach and highlighted how XENOMAI is improving the real-time behavior of Moblin, enabling it to satisfy some "hard" real-time constraints. Other solutions based on kernel patches will be addressed in future work.

Glossary

OS:

Operating

  Intel's open source initiative project created to develop software for the next generation of mobile devices including Netbooks, Mobile Internet Devices, and In-vehicle infotainment systems based on Intel's Atom target processor.

Figure 1 :

 1 Figure 1: Hardware connections setup The reason behind choosing the serial communication device rather than any other way (CAN, Timer…) is its hardware availability on the measurement board.

Figure 2 :

 2 Figure 2: Latency time measurement test cycle

Figure 3 :

 3 Figure 3: Periodic task scheduling test

Figure 4 :

 4 Figure 4: Test application with Linux APIs architecture

Figure 5 :

 5 Figure 5: Moblin latency time test results

Figure 6 :

 6 Figure 6: Moblin periodic task scheduling test results

Figure 9 :

 9 Figure 9: Moblin + RTAI latency time at 800 MHz

Figure 14 :

 14 Figure 14: Moblin + Xenomai latency time at 1,6 GHz At 1,6 GHz, fully loaded system has an average latency time of 13 µs with 99% of samples below 29,8 µs; while lightly loaded system has an average latency time of 23,6 µs with 99% of samples below 32,5 µs. Most of the samples were between 20 and 30µs. Here again we have seen a small peak around 13µs due to the processor internal architecture. Note: Only 0.1% of measured samples exceeds the reference latency time of 40 µs but remains below 100 µs.

Acknowledgement

We would like to express our warm thanks and regards to our CTO Mr. Thierry SEYNAEVE and the embedded software department head Mr. Thierry BOUQUIER for their guidance and encouragement throughout this project. We are also grateful to our mother company ESG-GERMANY for providing financial support to this project.


M Destelle

J.-L Dufour

Deterministic scheduling reconciles cache with preemption for WCET estimation

Keywords: preemptive scheduling, WCET, cache memory, robust partitioning, lock-free communication

Inertial Reference Systems are highly critical in the avionics context. As a result, their software components are submitted to a rigorous demonstration of the Worst-Case Execution Time ("WCET"), together with a demonstration of "robust" partitioning. With a processor using cache memory, if task scheduling is preemptive, these demonstrations become a real challenge. The difficulty comes in adequately bounding the cache refill cost due to context switches. This paper presents the solution we have adopted on our new generation of Inertial Reference Systems: it consists in a particular scheduling policy, which allows in turn a particular cache management policy. This cache policy is a key point for performance, because modern processors rely radically on cache to achieve the promised MIPS: the result is -to our knowledge -an unrivalled use of cache on a DAL A system. Lastly, the new scheduling policy puts the final touch to our lock-free inter-task communication protocol.

Introduction

Inertial Reference Systems are highly critical avionics systems, because -among other thingsthey deliver pitch and roll angles directly involved in the stability of the aircraft. When the DO-178B/ED-12B recommendation is applicable, the majority of the software is "level A" : this implies a rigorous demonstration of the impossibility of a CPU-time overload. Moreover, "robust" partitioning may be requested between pure inertial computations, barometric computations and hybrid inertial/GPS computations: this implies that "A software partition should be allowed to consume shared processor resources only during its period of execution" ([DO-248B/ED-94B] §4.14.5), and of course CPU time can be considered as one of the shared processor resources. In the context of a real project certification, we decided to not open Pandora's box and to strictly follow this recommendation, but in the conclusion we will take the liberty to technically challenge it.

To deal with these issues, we use traditionally on our Inertial Navigation Systems a very simple multi-tasking architecture: a purely periodic preemptive scheduling (no aperiodic task: asynchronous events are polled, with hardware time-tagging of events when needed), with a fixed-priority rate-monotonic policy (no priority inversion) and harmonic periods (see the annex). With this architecture, the CPU-time overload issue breaks down immediately into task level issues: each task must have a WCET less than its allocated "deadline" (defined here as a limit duration, in contrast to a limit date). To enforce these deadlines, at each task launch the scheduler arms a watchdog with the corresponding duration, and if the watchdog goes off, the faulty task is no more scheduled.

On the simple processors we used until now (pipelined, but without cache), context switches had mainly a deterministic cost (the saving and restoration of the registers), because the disruptions of the pipeline had a "random" but negligible cost. So, on a given application with an average of let's say 3 task switches every ms, with 30µs per switch, the CPU-load of the scheduler was valued at 3*30/1000 = 9%, and the application had to fulfill:

∑ i D i /T i < 91%

[1] (D i is the deadline and T i the period of the task number i) and of course WCET i < D i with moreover a security margin. To summarize, the cost of preemptions was not taken into account in the application tasks, but via an extra "scheduler task".

On our new generation, this architecture has been confirmed, but a "new mature" processor has been introduced: a PowerPC 8270 (Freescale), containing a 500MHz "G2" core, fed by a 100MHz external memory. This frequency gap is not (on average) a problem, because the G2 core contains two 16Kb caches: one for instructions, and one for datas. They allow (with the help of the pipeline) one instruction fetch and data access per cycle, to be compared to the 15 cycles (30ns) needed by an instruction or data external read: the global performance ratio can reach 30. The next section details the subtle problems the cache can create when it is associated with a preemptive scheduler.

The subtle interaction cache / preemption

The impact of caches on performance is well known [START_REF] Agarwal | An analytical cache model[END_REF][Mogul91], but not so well dealt with by tools [START_REF] Wilhelm | The Determination of Worst-Case Execution Times-Overview of the Methods and Survey of Tools[END_REF]:

-For a single non-interrupted task, the average execution time can be significantly shorter (see the former ratio), but the variation can be significantly larger (the data cache can even increase the WCET; for the instruction cache, this is reserved to pathological programs [START_REF] Sebek | Instruction cache memory issues in real-time systems[END_REF]). This variation is inherent in the memory accesses: a cache hit takes one cycle, a cache miss takes 60 cycles (120ns) if the cache line to be replaced needs to be written back before it can be filled (a read or write burst takes 60ns). This variability is not a difficult issue, in particular it must not be confused with "non-determinism" (the G2 behavior is deterministic): it just puts a greater emphasis on the exhaustive determination of the WCET path(s) and on the security margins applied on the measurements.

-For an interrupted task, the problem is different, and we can really speak of "nondeterminism", because the preemption points are really "non-deterministic": o When a task is interrupted, the proportion of "dirty" (defined in section 4.1) cache lines is random, so the next task -even if it starts from the beginning and makes always the same accesses -will have to evict a random number of cache lines: the standard solution in real-time systems is to ensure a "clean" cache at each context switch. o When a task is restarted, the miss ratio will be increased (compared to the same execution of the task, but non-interrupted) in a hard-to-predict way: we have a cold-start in the middle of the execution, because useful lines have been lost due to the former preempting tasks (Linux/Windows case) or due to the scheduler (real-time case). The key notion of "useful cache block" has been defined hardly 15 years ago [START_REF] Lee | Analysis of cacherelated preemption delay in fixed-priority preemptive scheduling[END_REF], and since it is still an active research area, not yet operational in the commercial WCET tools (to our knowledge). This cache refill cost after a preemption is both hardto-predict and not-easily-diminished:

-Software-based cache partitioning [START_REF] Mueller | Compiler support for softwarebased cache partitioning[END_REF] is very restrictive for the compilation chain and very memoryinefficient with our constraints of spatial partitioning.

-Hardware-based cache partitioning [START_REF] Liedtke | OScontrolled cache predictability for real-time systems[END_REF] is not easy in the G2 core, because the 4 cache ways are not individually lockable, and a locked way doesn't survive to an invalidation.

-The explicit choice of preemption points [START_REF] Simonson | Use of preferred preemption points in cache-based real-time systems[END_REF] is not compatible with the constant evolution of the software (the subtasks limits move at each new version).

With the performance ratio of 30 in mind, even if it is sometimes still practiced [START_REF] Rodríguez | Challenges in Calculating the WCET of a Complex Onboard Satellite Application[END_REF], the approach of disabling the caches to ensure an easy WCET estimation is completely unrealistic in our context. So we will have to assume that at each preemption, we have to refill completely the cache. This cost has to be multiplied by the maximum number of preemptions: this number is also a current research topic [START_REF] Burguière | Cache-related preemption delay computation for setassociative caches -Pitfalls and solutions[END_REF], but for this, we can do a simple thing: make the scheduling deterministic, in such a way to make the number of preemptions constant and statically computable. This is the topic of the next paragraph.

Deterministic scheduling

3.1 Foreword: What is a "periodic task" ?

Before describing the new deterministic scheduling, we will shortly describe a key point of our scheduling policies, to make easier the understanding of the next sections.

Generally (and fortunately), real-time schedulers don't change the design patterns used in non-realtime computing, they just adapt them. This is typically true for communication (semaphores, …), this is also true for the very basic notion of "periodic task". For example with an [ARINC-653] scheduler, a periodic task looks like: entry: while(1) { applicative_state_update(); PERIODIC_WAIT(); } where the last call is a system call meaning "suspend me until the next period". The scheduler calls the entry point only once in the very first period, and then its an endless repetition of suspend/resume at the level of the system call. In particular it means that at this place the context is saved and then restored, at each period.

Our notion of "periodic task" follows another pattern: entry: applicative_state_update() and the repetition (the former while loop) is done by the scheduler, which calls the entry point at each period. We say that the task is "started" at each period, or that each period contains a "run" of the task. In particular no context is saved nor restored between successive runs. On a high frequency task (1ms period), the CPU saving reaches 2%.

Principle

[ARINC-653] has been the initial source of inspiration: it can be summarized as the avionics "multi-user time-sharing system", where "user" means "equipment supplier". Each supplier has a statically specified periodic set of time-slots (a timeslot is a time interval defined by its offset from the start of the period and its duration) called a partition, and an ARINC-653 scheduler is able to ensure robust partitioning between the partitions. Inside a partition, multi-tasking is performed with a prioritybased preemptive scheduler.

Inter-partition communication must use messages (addressed to partition: a specific task cannot be referred to). Intrapartition (task to task) can also use classical shared areas with mutual exclusion dynamically guaranteed by semaphores, together with task priority changes to avoid task interlocks.

We don't have the multi-supplier constraint, so to avoid a needless complexity (coexistence of partition scheduling and task scheduling, priority inversion) and to maintain the efficiency of our classic scheduling (task-level communication between partitions, based on shared areas statically protected [section 5]), we had the idea to keep only the static philosophy of the partitions and to apply it to the tasks: the only difference between our classic ratemonotonic scheduler and the new one is that tasks execute now in a constant time, and formally, like ARINC-653 partitions, tasks are now static periodic sets of time-slots. More precisely, a task of period T can be defined as follows in any interval [nT, (n+1)T[:

-A non-interrupted task is a single time-slot, -A task which is pre-empted k times is a sequence of (k+1) time-slots. The notion of partition still exist: it is reduced to a set of tasks such that, as soon as one of them fails, the other ones must also be declared faulty.

The implementation is quite simple : instead of giving back the control to the scheduler at the end of the applicative computations of a task, tasks always terminate in an empty endless loop, the "IDLE" loop, and it is the watchdog timer programmed with the deadline of the task which transfers the control to the scheduler. This way, tasks have a constant duration, equal to their deadline. In other words, the deadline watchdog is promoted from a safety status to a scheduling status. The negative aspect is the lost time in the IDLE loop, but first it can be used for "background" jobs like memory BIST, and second in a DAL A certification context we considered it was a very "attractive lost". This new scheduler is named "DMS" for Deterministic Monotonic Scheduler. A good summary of its specificity is: "At any time, we know who is running". Together with the cache policy (next section), it is the key property for obtaining: -a constant number of preemptions for tasks, which permits a safe but fine task-WCET estimation, -a compositional estimation of the global CPUload, because the task-WCETs can be estimated independently.

It is the result of:

our strict rate-monotonic scheduling policy (no aperiodic task, no priority change), -tasks of constant duration, -scheduler system calls of "nearly constant" duration (next subsections).

Implementation

Like all preemptive schedulers in the real-time domain, our standard scheduler is based on the concept of "tick scheduling": preemptions are initiated by a periodic InTerrupt ("IT"), triggered by a Real-Time Clock ("RTC", "HTR" in French), with a fixed period typically equal to 1ms or 2ms on our systems.

The new scheduler is based on an additional IT, the Deadline IT (previously the "watchdog" used to enforce deadlines). We call it also the DECrementer ("DEC") IT, because it is trigged by an internal G2 timer called the "decrementer", programmed by the scheduler at each task switch.

The job of the RTC IT is to "preempt and schedule", i.e.:

a) save the context (registers, among them the decrementer) of the pre-empted task, -b) declare "eligible" (i.e. ready to be scheduled) the tasks for which the current time is a multiple of their period (2ms tasks are re-elected every 2ms, …), -c) choose the next task to (re-)start: it is the eligible task which has highest priority, -d) configure the MMU for this task, -e) launch the task; it be either an initial launch, and in this case no context restoration has to be done, or a re-launch if the task was interrupted (pre-empted), and in this case the context has to be restored. The job of the DEC IT is to "terminate and schedule", i.e.:

a) declare the finished task as "no more eligible", and if applicative computations were not terminated, declare a fault at the task and partition level, -b) perform the c/d/e actions of the RTC IT.

A task of period T is in one of the following states: We illustrate the scheduling with the following configuration:

the RTC has a 1ms period,

task 1 has a 1ms period and 480us deadline, -task 2 has a 10ms period and 750us deadline. The DMS "phantom task" is the background task that is launched when no more applicative task is eligible.

What means "deterministic" ?

This section clarifies the claim "at any time, we know who is running", explaining that, strictly speaking, it is false, but also how it can be made practically all the time true, and in any case sufficiently true to be able to demonstrate a constant number of preemptions.

The first problem comes from the non-interruptibility of the two IT handlers: if the RTC IT occurs while the DEC handler is running, the RTC handler has to wait the end of the DEC handler. We say that the RTC handler has been "pushed". In fact it is not a real problem, because we know when Deadlines occur, so we can schedule in such a way to avoid this case.

The second problem comes from the variability of the duration of the two IT handlers. This variability does not come from their design, because we have followed "WCET-oriented" principles first advocated in [START_REF] Puschner | Writing Temporally Predictable Code[END_REF]. It comes from the architecture of our PowerPC: the internal bus is not exclusively hold by the G2 core, but is shared with a communication core. With a high-speed network like AFDX, it can steal a few percents of the internal bus bandwidth available for the G2 core, in a completely asynchronous way. A solution could have been to terminate the handlers with a timer-polling loop to enforce a constant duration, but it has not been necessary: variations are small enough to be manageable. This handler variability generates a variability on the Deadline instants (not on the task durations), and this variability increases with the length of the task (more precisely, with the number of preemptions) and inversely with the priority of the task (a task is launched after the tasks with higher priority).

In fact, a quick analysis shows that the property "constant number of preemptions" is implied by "no RTC handler pushed". So, to ensure a "deterministic" scheduling, a sufficient criterion is to determine the time intervals where the Deadline handler may be running, and to check that they don't contain any RTC IT.

Cache management policy

4.1 Foreword: Cache configuration w.r.t. certification Each writable data area declared to the MMU must be configured in one of the two following modes:

-"write-through", means that every write is "simultaneously" done in cache and in memory, -"copy-back", means that writes are done only in the cache, and memory updating is performed later (possibly while the execution of another task). A data in cache but not yet in memory is said "dirty", and a cache containing at least one such data is said "dirty". The action of updating memory with all the dirty data is called a "flush" of the cache. It takes a non negligible time essentially proportional to the amount of dirty data (between 1 and 32µs on our hardware configuration). It must not be confused with an "invalidation", which is an instantaneous reset of the cache: any dirty data is lost.

The delayed memory update in copy-back mode is a violation of time partitioning (not of spatial partitioning, as is sometimes found). That's why a clean cache is recommended at each scheduling. Moreover, if some data or code have survived between two successive invocations of a task, the second invocation may be quicker, and this can lead to optimistic measurements. This is also a violation of time partitioning, so it is recommended on a task launch that the cache doesn't contain any task data or code. When a cache satisfies this last property and is clean, we will say that it is "neutral".

Copy-back at the end of the tasks

The standard and easy way to ensure a neutral cache is to invalidate it, which implies that the cache must already be "clean" at the schedule point. So:

if the task is not interrupted, the application can work on copy-back areas, provided that it explicitly flushes the cache at the end; -if the task is pre-empted, the application must run in write-through mode only: the impact on CPU time can be significant.

But with a deterministic scheduling, the scheduler knows if the task it currently launches will be preempted or will terminate before the next RTC IT.

With this information, we can launch tasks either in write-through mode (on an intermediate time-slot) or in copy-back mode (on the final time-slot), and in this last case an explicit flush of the cache is performed at the end of the task (the flush time is counted in the execution time of the task).

It is a generalization of the fact that non-interrupted tasks can easily run in copy-back mode (with an explicit flush at the end).

Copy-back unlimited

The remaining problem is to ensure a clean cache before the invalidation in the RTC handler. The obvious solution is to ask the RTC handler to flush the cache. But a cache flush takes a very variable time, and this will destroy the deterministic aspect of the scheduling. The solution is to perform the flush in a constant time: like tasks, it is followed by an idle loop, not infinite but waiting for a defined duration (32µs). On a 1ms RTC period, it represents 3% of CPUtime: much less than the potential gain of the copyback mode.

Lock-free communication

Synchronous communication

The constraint of purely periodic tasks simplifies drastically the mutual exclusion problem. Schedulers permitting aperiodic tasks (like ARINC-653) are forced to dynamically protect the shared memory accesses (more generally the critical sections), typically with semaphores. This dynamic aspect makes task interlocks unpredictable, which makes necessary priority inversion mechanisms. With periodic tasks (harmonic periods and ratemonotonic scheduling help also), potentially critical sections become predictable. Moreover, our systems use the simplifying paradigm "one writer / many readers".

When a writer is writing into shared memory, it must not be preempted by its readers because they could obtain a mix of old and new values. Symmetrically, when a reader is reading into shared memory, it must not be preempted by its writer because the reader could again obtain a mix of old and new values. With fixed priority rate-monotonic scheduling, we don't know exactly when all preemptions occur, but we know when they don't occur: a task can never be preempted by lower-priority tasks, so it can never be preempted by slower tasks. The consequence is that the following protocol is safe:

Between a fast task T1 and a slow task T2, -T2 can always communicate (read and write their shared variables) without taking any precaution, -T1 communicates only in its First run in a T2 period, and T1 knows that it is in such a particular run by evaluating the system predicate "First(T2)".

The following figure illustrates this with a fast task running a the RTC period and a slow task running 3 times slower. Vertical arrows indicate reads and writes to a shared memory.

The « Last » primitive becomes static

To minimize latencies, it is sometimes useful to a fast task T1 to be able to communicate with a slow task T2 not in its first run, but in its last run in a T2 period. To know that it is in this run, T1 can evaluate the "Last(T2)" system predicate. Of course, the underlying assumption is that T2 will have finished its execution when the Last run of T1 begins. This is a fundamental difference with First, where the absence of preemption was ensured by the very principle of rate-monotonicity. This assumption had to be demonstrated with timing measurements. Deterministic scheduling changes that: we know when preemptions occur, so we are able to statically check that T2 will not be preempted by the last run of T1.

Conclusion

The static determination of the number of preemptions allows to secure the WCET estimations (obtained by test or static analysis) with a justified margin. Nevertheless, the cost of a complete cache refill is very expensive and clearly over-estimates the real cache-related preemption cost: even with an exact determination of the number of preemptions, the price to pay is very high, and confirms the urgent need of having a good estimation of the preemption costs in WCET tools. This analysis has brought us to wonder about the validity of the partitioning recommendation, more precisely: what are exactly the feared events it must block ? Our impression is that it must address events with unpredictable effect (like a CPU overload of a task), and that the expulsion of dirty lines of a cache could be considered out of the scope, because the impact is well-known: maximum 32µs. So, to ensure safety without any cache invalidation or flush is possible: we simply have to add the good margins on the WCET estimations. This is a good subject for the current decade.

(but of course the authors think that it is the best), and François de Virel for having patented with lightning speed, allowing us to have a substantial paper.

Annex: harmonic periods

A set of periods is said "harmonic" when for any periods T1 and T2, either T1 divides T2 or the opposite. This a fundamental property which is often overlooked, but which permits to check very simply the schedulability of a task set:

∑ i D i /T i < 1 [2] (D i is the deadline and T i the period of the task number i). This was demonstrated for the first time in [START_REF] Lehoczky | Fixed priority scheduling theory for hard real-time systems[END_REF] (theorem 3.4), but we can find traces of this in one of the first papers of the discipline: [START_REF] Liu | Scheduling algorithms for multiprogramming in hard realtime environment[END_REF] (the remark on the "utilization factor" between theorems 3 and 4). The demonstration of [START_REF] Lehoczky | Fixed priority scheduling theory for hard real-time systems[END_REF] is complex, because it starts from a more general case with nonharmonic periods. The engineer is often surprised by this complexity, because in the harmonic case, the expression ∑ i D i /T i is simply the definition of the CPU load.

Among the practical interests of this constraint, we can mention the absence of beats: informations transmitted between tasks of different periods have always the same freshness.

  Figure 2 : scheduling example It is visible in the previous figure that the two DMS handler have a non-negligible duration (a few tens µs), which must be taken into account to determine correctly the time-slots, and in particular the number of preemptions.

Figure 3

 3 Figure3: the "First" predicate This is very similar to the way data-flows on different clocks communicate in synchronous languages like LUSTRE (see the operators "when" and "current",[START_REF] Caspi | LUSTRE: a declarative language for programming synchronous systems[END_REF]).

Figure 4

 4 Figure 4 : the "Last" predicate

Acknowledgements

The authors acknowledge Frédéric Titeux for technical discussions around the fact that a strict "determinism" is not the only answer to the DO178B