Thomas Robert

Matthieu Roy

Jean-Charles Fabre

Early Error Detection for Fault Tolerance Strategies

Keywords: run-time monitoring, fault-tolerant, generation, early error detection

In this paper we present an integration of early runtime monitors in real-time systems to improve their fault tolerance properties. Early Error Detection is a mechanism that provides a theoretically optimal run-time error detection service, based on a formal specification of an application, e.g., given by a timed automata. We show how our approach can improve classical fault tolerance strategies by investigating two use-cases, namely for a design pattern that provides several degraded modes of operation, and in on-board avionics safety critical systems.

Introduction

The efficiency of error detection mechanisms is of primary concern for dependable system designers, since it impacts the efficiency of fault-tolerance mechanisms for error-detection and recovery strategies. When an error is detected, these fault-tolerance mechanisms modify the system state to guarantee that the service is still delivered, be it in nominal or in a degraded mode.

In conventional implementation of error-detection and recovery strategies, the approach is reactive in the sense that recovery mechanisms are triggered when the current state of the system is detected as erroneous. This approach has two impacts: i) the latency of error detection can be very high, and indeed the error is never detected before it actually happens, and consequently ii) the time left to perform a recovery action is reduced.

Improvements in error detection can take advantage of recent progresses in run-time verification, by integrating error detectors generated from specifications [START_REF] Havelund | Verify your runs[END_REF]. The inability to assess the gain in predictability brought by such detectors was the reason why they were not widely adopted. Their cost was also most of time prohibitive in terms memory and CPU usage. These aspects can now be mastered and modeled. The behavior of the new generation of formally generated error detectors can be formally inferred including timing aspects, [START_REF] Bauer | Monitoring of real-time properties[END_REF][START_REF] Drusinsky | On-line monitoring of metric temporal logic with time-series constraints using alternating finit automata[END_REF][START_REF] Sammapun | RT-maC: Runtime monitoring and checking of quantitative and probabilistic properties[END_REF][START_REF] Robert | On-line monitoring of real time applications for early error detection[END_REF].

In this paper we propose an approach that is proactive in the sense that it tries to anticipate the detection of an erroneous state in the actual system. Our method performs the detection based on an abstract model of the computation, defined by timed automata.

In previous work [START_REF] Robert | On-line monitoring of real time applications for early error detection[END_REF], we showed that this method, the Early Error Detection (EED), leads to detect in advance a problem that will appear later in the actual system execution. The model is embedded in the implementation and is animated by our monitoring system, based on events related to the system execution. Intuitively, when the continuation of the execution in the model can only reach a failure state, an error is raised. In this work we show how we can use this approach to anticipate effective problems and perform recovery actions before the actual error takes place. We will detail the principle of early error detection, the way it can be implemented in real-time operation systems, and finally how usual fault tolerance strategies can benefit from our monitoring system.

In Section 2, we present and analyze related works on this topics. Section 3 describes in more details the principle of Early Error Detection and its formal foundations. Section 4 focuses on the description of the input formalism to our detector generation framework: timed automata. It also explains how early error detection can be interpreted with respect to this model. Section 5 briefly presents the implementation of our framework in Xenomai. Section 6 is devoted to explain how this mechanism can be used in usual fault tolerance design patterns. Section 7 sums up the contribution and provides some insights on future works.

Problem statement & Related work

Several surveys provide insights on error detection through model driven engineering [START_REF] Chevochot | Experimental evaluation of the fail-silent behavior of a distributed real-time run-time support built from cots components[END_REF][START_REF] Delgado | A taxonomy and catalog of runtime software-fault monitoring tools[END_REF][START_REF] Havelund | Verify your runs[END_REF]. Models are often related to academic formalisms, e.g., temporal logics or timed automaton [START_REF] Bellini | Temporal logics for real-time system specification[END_REF][START_REF] Alur | A theory of timed automata[END_REF].

In this field of research, run-time monitors are independent detection components integrated in a system to enhance its error detection capabilities. The monitor observes the system state and check on-line user-defined properties. Thus, it emits error signals as soon as one of the properties being assessed is violated. This architec-ture is now well established and can be found in several key papers along the past decades [START_REF] Diaz | Observer-A concept for formal on-line validation of distributed systems[END_REF][START_REF] Mok | Early Detection of Timing Constraint Violation at Runtime[END_REF][START_REF] Kim | Monitoring, Checking, and Steering of Real-Time Systems[END_REF][START_REF] Havelund | Verify your runs[END_REF][START_REF] Drusinsky | On-line monitoring of metric temporal logic with time-series constraints using alternating finit automata[END_REF].

In those architectures, two phenomena contribute to detection latency. First, there is the latency introduced by the communication mechanisms used between the system and the monitor to relay observation. Second, there is also an issue when specifications are not expressed as simple invariants, leading to a run-time evaluation overhead.

As soon as the monitor has to store information in order to correlate the system state at two distinct instants, then the algorithm used for the decision procedure may introduce some latency waiting for useless observations. In order to avoid such a situation, the notion of early error detection first appeared in [START_REF] Mok | Early Detection of Timing Constraint Violation at Runtime[END_REF] for monitoring dynamic deadlines on a fixed set of events (chronicles). In [START_REF] Robert | On-line monitoring of real time applications for early error detection[END_REF], we described an implementation of such a run-time monitor detecting on the fly when the system execution is no longer matching behaviors described by a variant of timed automata [START_REF] Alur | A theory of timed automata[END_REF]. A similar approach has been suggested in [START_REF] Bauer | Monitoring of real-time properties[END_REF]. Nevertheless, it was not implemented nor detailed from the algorithmic point of view.

In this paper, we propose to integrate our early monitoring system for real-time applications to usual handling of degraded modes of operation. We rely on our run-time monitor implemented for a real-time kernel, Xenomai [START_REF]Xenomai homepage[END_REF], focussed on application tasks.

Early detection for trace monitors

We pointed out on the fact that there exists a class of monitors providing early error detection services. We recall in this section the ideas behind this notion of early error detection and their formalization in terms of traces.

Correct behavior and error symptoms

We briefly recall some terminology [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF] to identify and describe the threats to dependability: failures, errors and faults.

These notions assume that the system interface, its boundaries, is known. The expected service of a system is embodied by its nominal behavior. A failure is defined by an unexpected behavior. It occurs when there is a gap between the system actual behavior and the expected one according to its specification. An error is an internal state of the system leading to failures. Finally, the fault is the cause of errors. The study of faults is out of the scope of this paper. Nevertheless, the notion of early error detection is directly related to the relationship between errors and failures. Because the duration between the fault activation and the failure may be quite large, there is a real interest to optimize the error detection latency. It would provide more time for recovery actions.

In order to identify erroneous states, a well spread method assumes the following claim: any state that has not been declared correct by the system designer is a priori erroneous. We use this assumption and derive an error detector from a description of the system correct states.

There are usually two ways to specify system correct states: through logical formulas or transition systems. Because many architectural design languages attach transition systems to their component structures, we considered such a formalism to specify correct system behaviors (UML and statecharts [START_REF] Der Beeck | A Comparison of Statecharts Variants[END_REF], AADL and its behavioral annex [START_REF] França | The AADL behaviour annex -experiments and roadmap[END_REF]).

In order to detail the notion of early error detection, we need to formalize the trace notation used to represent system executions.

3.2 From Bad prefixes to early detection.

We are relying on a formalized representation of a system execution: traces. Timed traces are the most common representation of real-time system executions.

Timed traces are sequences of alternating events (start, stop, . . . ) and quantitative durations (1, 5 time units). Such trace model has been extensively studied in [START_REF] Asarin | Timed regular expressions[END_REF]. Alternating durations and events ensures that at most one event can occur at any given instant. The concatenation symbol '.' is used to separate events and durations, e.g. start.10.stop. The durations considered are unit free : no physical duration is actually associated to these numbers. The physical duration unit, e.g. seconds or milliseconds, can be defined afterward.

In order to reason about the detection process, prefixes of traces have been identified as a key concept [START_REF] Bauer | Monitoring of real-time properties[END_REF][START_REF] Havelund | Synthesizing monitors for safety properties[END_REF]. For any traces v and u, if there exists a trace w such that v.w = u, then v is a prefix of u, and u a continuation of v. In practice, prefixes and continuations can be seen as the past and future of a trace. The set of prefixes of a given timed trace represent all the past states of u.

If a trace is not a prefix of some valid trace (let L V be the set of valid traces), then this trace is called a bad prefix. A bad prefix, by definition, does not admit any continuation in L V . It means that the system cannot meet its specification, whatever is executed later in the system. Eventually, any bad prefix corresponds to an erroneous state, and leads to the system failure. The prefixes of a given trace are totally ordered. We presented a detailed justification for considering the following claim in [START_REF] Robert | On-line monitoring of real time applications for early error detection[END_REF]: the lower bound of the prefixes of a bad prefix, that are also bad prefix, is a bad prefix except in rare artificial cases. In other words, there is always a trace that allows identifying the exact border between correct and erroneous traces at run-time. Thus, this lower bound is call the shortest error symptom. In practice, this trace corresponds to the first instant from which the specification can no longer be satisfied. The Figure 1 represents three traces such that tr1 is the prefix of tr2, and tr2 is the prefix of tr3. On the figure, the shortest error symptom of tr3 is between tr2 and tr3.

Error signalling and Monitor Synchronization

As defined above, the monitor can signal an error as soon as a shortest error symptom is observed. One of the advantages of such a formal definition of the shortest error symptom is to provide the foundations to build a formal definition of error detection latency.

The shortest error symptoms identify the earliest instants at which the specification allows to distinguish correct from incorrect executions. If an error detector can signal errors as soon as the system execution matches a shortest error symptom, then it means that this detector has a "zero latency".

One of the core issues when dealing with run-time monitor implementations lies in their architecture. The problem comes from the communication methods used to connect the different elements of the monitor. The usual architecture of the run-time monitor is made of three layers shown in Figure 2: an observation layer, a decision layer, and an error dispatch layer or error handling layer. Two main issues have to be handled : the location of the layers, the way they synchronize and communicate, and how observations are delivered to the decision layer. We considered the following setting :

• The layers are deployed on a same node. Our implementation of the monitor is not distributed.

• The layers synchronize themselves thanks to the scheduling services provided by the underlying runtime support (here, it is the Xenomai real-time operating system).

• The observations are handled according to a FIFO policy by the decision layer.

These assumptions guide the design of the monitor using Xenomai programming interface. The usual synchronization scheme assume that the monitor is a purely reactive component waiting for new observations. A monitor enforcing early error detection tries to identify shortest error symptoms. One of the nice properties of shortest error symptoms is to catch both timing and behavioral errors (wrong event).

Consider the following set of correct traces : L

V = {start.X.stop | X ∈ [0, 20[}.
The trace start.24.stop is a bad prefix and corresponds to a deadline miss. The shortest error symptom of start.24.stop is start.20. The monitor will have to wake up as soon as the state represented by start.20 is reached. For these reason, the monitor cannot be implement as a fully reactive system. Timers can be used for this purpose.

The next section explains how to generate a fully operational monitor that provides early error detection for a set of valid traces specified by a timed automaton.

Shortest error symptoms Monitor

In this section, we first highlight the kind of errors and failure targeted through our approach. Then, we explain how timed automata can help to specify and check at runtime relevant misbehaviors. Finally, we show where shortest error symptoms are involved.

Targeted errors and their symptoms

There are usually two kinds of error detection services: generic or application dependent detection services. Using the specification of application valid behaviors, we are targeting the second class of services.

The kind of formalism used for specifying valid behaviors has a strong impact on the kind of detected errors.

Events and timing

Considering timed traces of events, the detector is targeting errors tempering with the control flow of applications. Many operating system have watchdog timers and deadlock detectors. Nevertheless, these mechanisms lack application specific knowledge: watchdog detectors suffer from high latency and poor error confinement, and deadlock detection services lack coverage. The aim here is to use application dependent knowledge to identify wrong timing or suspicious event involved in data race or deadlock conditions.

Three types of constraints can be defined on the elements of an execution trace:

• Compulsory ordering between events, induced by the natural sequence of events,

• Upper bound on the time between two events,

• Lower bound on the time between two events.

The aim of the error detector is to trigger an error signal as soon as it observes that the system will no longer be able to comply with its specification. Whereas the scheduling theory is mostly concerned with comparing different types of upper bounds (i.e. deadline and execution times), EED takes advantage of leveraging information on both lower and upper bounds to identify possible inconsistencies in an erroneous execution. In few words, if we can trace a function execution progress and compare it to its deadline, then if the function is late on schedule, the monitor can decide to trigger an error signal before actually reaching the deadline.

We use formal model to generate the monitor. Thus, if the observations match a shortest error symptom it proves that the specification is not respected.

Example of early detection

Consider the following execution scenario for a task relying on a shared resource for its execution. The task has two modes, i.e. , two execution paths are possible. The shared resource represents a device from which data is read, and the task waits to obtain the read value to complete its execution. Reading the value entails a locking time on the calling task. This locking time depends on the execution path, since the resource is used differently in the two execution paths. In the first path, the call is synchronous and entails a locking time of 10ms. In the second path, the resource is not actually used in the sense that the task only gets the previous measure that is in the cache. In this case, the locking time is so low that it can safely be considered instantaneous. Another (global) timing constraint for both paths is that the completion of any of these two paths must occur within 20ms. In this example, the second path can be considered as a degraded mode of operation of the task, since it will use degraded (with respect to freshness) information to perform the same task, but with a lower WCET. Let us observe the description of the first path. The combination of the minimal locking time with the deadline allows us to claim that if the task is started, and accesses the resource t ms after its starting time, with t > 10ms, then the task will either violate the minimal locking time, or miss the deadline as depicted in Figure 3 1 .

. Conflict between timing constraints

An early termination of the reading on the shared resource as well as the deadline miss could be interpreted here as the observable consequences of either an error in the execution flow of the critical section, or the propagation of a late timing failure before the critical section.

When such a situation can be identified in advance early error detection will provide a mean to save time and avoid the execution of non-reversible actions that would for instance propagate the errors outside of the monitored application.

In most cases inconsistencies come from a clash between the knowledge of what should happen (i.e. deadlines for instance) what would happen in normal circumstances (i.e. the minimal locking time), and what is actually observed. In the next subsection we describe a formalism in which such information can be easily integrated in order to get the best of early detection.

Timed automaton

Timed automata are one of the leading formalisms used to formally specify real-time behaviors. As any other type of automaton, they can be seen as a handy way to define sets of traces (representing valid execution) or analyze state properties (liveness and safety). Through the modeling of the previous example, the descriptive power of this formalism will be illustrated based on the content of the seminal paper [START_REF] Alur | A theory of timed automata[END_REF] Finite state machines are straightforward representations of the state that can be reached during an execution of a system. Transitions represent possible state changes and are statically defined. In the example described above, there would be at least four states: one identifying the initial state from which the execution of a cycle starts; one identifying the intermediate state from which two transitions, representing the two possible execution paths (nominal and fast), can be fire; and two distinct states representing the critical section in each path.

Figure 4. A Timed Automaton to specify valid executions

In addition to states and transition inherited from classical automata, timed automata introduce special timing variables, that can be seen as resettable clocks with uniform time elapse. Edge are labelled with triplets: an event label allowing to identify the transition by a name, a guard being the condition under which the transition can be fired, and the set of clocks that have to be reset when the transition is fired.

For our example of Figure 4, the edge between states standby and processing is a transition that can always be fired, and is fired when event start is observed, leading to reset the clock x. The transition from the state CS1, representing the execution of the critical section in the first execution path, and the standby state is identified by the event complete. This condition has a guard combining a condition on the clock that count the time elapse since the beginning of the current execution of the task, x, and the clock storing the time spent in the critical section, y. This transition can only be fired from states satisfying the guard, i.e. those with clock values such that (x < 20) ∧ (y > 10).

Notice that if an event is observed in a state s whereas no corresponding transition can be fired from s, then it means that the event was unexpected, either because it was in a bad timing, or because it was forbidden. Guards allow defining conditions in which events are forbidden. The definition of final states, i.e., states that need to be reachable, provide the means to define the completion condition of an execution corresponding to requirements related to bounded liveness.

Definition 1 (Accepting condition on traces) A trace is valid if and only if

• It can be executed on the automaton starting from the initial state (state identified by inbound arrow), with all clocks set to zero.

• The last state reached through the execution of the trace is a final state (i.e., a state identified by a double circle).

In the remainder of this paper, the requirement that a final state is actually reachable from the current state will be called the reachability condition. Whereas there is a straightforward way to identify unexpected events, it is far more difficult to identify errors due to the violation of the reachability condition defined by the automaton. This is exactly where the EED property defines the objective to be met.

Intuitively, a monitoring system, based on a description made of timed automata, that complies with the EED property performs the steps described in Figure 5 (a more detailed description can be found in [START_REF] Robert | On-line monitoring of real time applications for early error detection[END_REF][START_REF] Robert | Evaluation of a realtime monitoring framework[END_REF]).

The major point in this skeleton is to be able to efficiently assess at run-time the reachability property, i.e. , we need to have an efficient way to answer the following question at every time instant: "From the current state, is there a continuation that reaches a final state?". The following subsection presents our approach to reach this goal, by using a modified version of time abstractions.

Final states reachability conditions

There are basically two ways to check at runtime the reachability condition. The naive method is to browse the automaton again and again to check the reachability condition on final states. Although simple and easy to implement, this approach is not only very expensive, but, 1. track the current state of the system within the automata by synchronizing it to the observations 2. event-based error detection: when an event e occurs:

(a) check whether e is forbidden, because no such transition exists, (b) if a corresponding transition exists, check that firing the transition will not put the system in a state from which the reachability of final states is violated.

3. pure timing error: handle the case in which the reachability condition is violated, due to time elapse and no transition firing, leading typically to deadline misses.

Figure 5. Major steps of an EED-compliant monitoring system

more importantly, the time needed at each step to check the reachability property is unpredictable.

The approach, we advocate, is to precompute most of the reachability condition and encode it in the monitor, in order to have efficient and predictable reachability tests. Obviously, in this pre-computation step, special care has to be taken to minimize the amount of stored information, limiting it only to what is needed at run-time for the detection of violations of the automaton specification.

Intuitively, this means that the transformation will unfold (or compile) timing constraints and transform guards on transitions so that the evaluation of reachability condition can be performed when firing the transition, without having to browse the automaton. As clock constraints can also be defined on control states of the automaton, it is called an invariant. Thus, it is possible to define the condition under which control states are still alive through a conjunction of inequations defining the upper bound of each clock.

In our example, this results in:

• Adding to all nodes a deadline on x at 20, and adding it also on each transition.

• Updating the constraint on the transition on lock-ing_get by requiring that x is lower than 10 when firing.

When comparing the new automaton with the original specification, it appears that the transformation has made explicit all conditions on clocks that used to be implicit 2 . In most cases a human made timed automaton transforma-tion is not possible, since it is a very burdensome way to specify behaviors.

Yet, such a transformation can be inferred automatically from a well established transformation: timed abstraction. The time abstraction splits up control states as soon as the enabled and valid transitions differ, according to the clock values. In our approach, we used the tool KRONOS [START_REF] Tripakis | Analysis of timed systems using time-abstracting bisimulations[END_REF] to perform this transformation. The aim was to allow local decision in the sense that steps 2 and 3 of Figure 5 can be done in a greedy way. Time abstraction adds clock upper bounds to control states, and integrates the reachability test and the guards in timing bounds put on each state. Hence, the challenge was to be able to interpret all the implicit conditions entailed on transition by the requirement of reachability of final states. This transformation has been proven to be always possible for deterministic timed automata even if it can sometimes lead to an exponential blow up in automaton complexity. This transformation is called time abstraction and the full description of this technique is beyond the scope of this paper.

In the next section, we will discuss how we performed this transformation, and how we used it for our monitoring system that we developed for the operating system Xenomai.

Generating EED from timed automaton

This section presents our proposal for generating realtime error detectors that implement the early error detection property for Xenomai applications. In the previous section, we have briefly presented how a timed automaton can be normalized so that it can be used to identify on-the-fly shortest error symptoms. The next step is to embed such a model in a detector observing the system activity.

Observation layer

This layer is integrated at compilation time in the application source code. Observations are collected through calls to a function triggering the verification in the decision layer. These function calls are inserted by hand within the source code through C macros. The macro has a single parameter that is used to specify which event is observed. The set of observed events is listed in an header (.h) file that has to be included within each file where observations are performed.

In practice, it means that observations can be done in pseudo-concurrence as the verifications can be called by threads reaching observation macros at the same time. The monitor state is thus a shared variable. Each call to the verification function first reads this state, and then updates it. This instrumentation strategy is simplistic but our concern was not to provide another instrumentation tool.

Decision layer

The decision layer is implemented by a function that has access to the data structure storing the normalized automaton description, and especially the location invariants and the transition table. We use the KRONOS tool set [START_REF] Tripakis | Analysis of timed systems using time-abstracting bisimulations[END_REF] to normalize the automaton. Because KRONOS only provides a raw text format, we translate it in a C data structure. Then, this data structure is loaded during the initialization phase of the application.

As said before, the state of a timed automaton is made of a location index and a clock vector. The automaton state is only updated when an observation is performed. This update can affect both the location index and the clock vector. Clocks are increased or reset depending on the transition fired. Invariants are enforced by setting a timer according to the time left in each location. For instance, if we consider the example of the previous section, then the location processing has to comply with "X < 20". Thus, as soon as this location is entered (firing the transition "start"), then a timer is set to enforce the deadline on the clock X. This timer is set to expire at 20 -X time units later.

Each time an event is received, then the transition table of the currently occupied location is searched. The event is validated if and only if the condition is true: there exists a transition with its guard satisfied by the current clock vector, such that its label corresponds to the event being checked. Each time an event is validated, then the transition is fired and a new location is entered, then the timer has to be reset or updated.

The verification function has three possible behaviors :

• check an event and validate it : the function return normally

• check an event and declare it invalid : i) the verification function releases a recovery task concurrent to the calling task with a higher priority, ii) the verification function returns an error code like any C function.

The two methods proposed to signal the error are intended to allow either local or global error handling policies.

Synchronization and scheduling during verification

The monitor state is a shared variable used for read and write accesses during the verification of an event. Thus, it is necessary to ensure at least mutual exclusion on verifications. Moreover, the verification call enforces a strong synchronization between the application and the monitor. In order to offer maximal error confinement capabilities, the verification is performed synchronously.

For this reason, the verification has to be performed as fast as possible. Before actually starting the verification, the verification function protects itself from any preemption by locking the scheduler. Once the verification is finished the scheduler is released just before returning from the verification function.

This synchronization method can be considered as disappointing with respect to usual best practices in scheduling theory. Verification steps deactivate the scheduler. Thus, a lower priority task can trigger a verification step whereas a higher priority task should have been rescheduled in a close future.

We are dealing with error detection at the scale of a set of tasks. A same automaton describes synchronizations and timing constraints on tasks of the same criticality, a priori. Thus, lower priority tasks may be as relevant as higher priority tasks in order to detect errors. One could consider that the verification task is supposed to have at least a higher priority than any task monitored.

Moreover, the recovery actions triggered by the monitor will comply with application scheduling policy: either the recovery actions are executed by the task (at its own priority level) that called the detector, or by an independent recovery task when global recovery action is needed.

In both cases, the user can rely on the usual properties of the fixed priority scheduler of Xenomai to analyze and predict when the recovery task may finish.

Integration of EED into fault tolerant systems

The objective of this section is to illustrate the interest of EDD in fault-tolerant systems. The first example is based on conventional design patterns used to implement degraded modes of operation. A nominal mode of operation is developed together with a series of degraded modes of operation. The use of EED maximizes the remaining time for running a degraded mode of operation. The second example is extracted from on-board avionics safety critical systems [START_REF] Traverse | Airbus fly-by-wirea total approach to dependability[END_REF]. The "command-monitor" design pattern used in the Airbus 320 to 380 can be improved using EED, i.e., improving the error detection coverage of the monitor in the temporal domain.

Implementing degraded modes of operation

Let us consider a real-time periodic application that implements a service defined by a timed specification, as described in previous sections.

Design

The application, in its nominal mode, implements the full specification Spec(Nominal) which is associated with a worst case execution time WCET(Nominal). We also suppose that there exists a sequence (Deg i ) i=1..n of degraded implementations of the application, with restricted quality of service, that implement degraded specifications (Spec(Deg i )) i=1..n . These degraded implementations are, by nature, associated with lower worst case execution times (WCET(Deg i )) i=1..n :

∀i < n : WCET(Deg i+1 )) ≤ WCET(Deg i )) WCET(Deg i ))
≤ WCET(Nominal))

In safety critical systems, there exist at least two modes: the nominal mode and a safe stop mode. Degraded versions permit to provide more flexibility and availability by trying to reconfigure the application to avoid, when possible, stopping the application. A traditional reconfiguration mechanism may stop the nominal application when a failure occurs, and use one of the available degraded modes of operation. In a real-time system, it is crucial that the reconfiguration occurs as soon as possible, but available failure detectors will not be able to detect a deadline miss before the actual deadline expires. Using Early Error Detection, we are able to catch the failure sooner in the execution, i.e., before the deadline is actually missed, and use the remaining time budget to launch one of the possible degraded modes of operation, as shown in Figure 6.

Figure 6. EED-based reconfiguration

In this example, the application runs in nominal mode with a given time budget (expressed by the variable Deadline). The detection engines monitors the application and signals any deviation to the nominal mode specification. When such a signal occurs, the application is stopped, the reconfiguration engine computes the remaining time budget (remainingTime), and restarts the application, using a degraded mode whose worst case execution time is compatible with the remaining budget remainingTime.

Algorithm

As mentioned above, the application is a periodic task that is scheduled by the system for a maximum budget time, i.e., with a static deadline. Let Spec(Nominal) be the nominal specification of the service, and (Spec(Deg i )) i=1..n be degraded specifications with reduced quality of service. We associate with each specification an EED monitor that checks online whether an implementation satisfies its specification. As soon as a deviation is detected, the monitoring engine signals it to the reconfiguration engine. In practice, each specification is implemented in a separate module, and is available to the reconfiguration engine that can dynamically chose which version is to be run, given a time budget. When an EED signal occurs, the reconfiguration engine first computes the remaining time budget, then looks for the degraded mode that has an expected worst case execution time closest to the remaining time, and then launches it. If no such mode exists, this means that it is not possible to reconfigure the application in a temporally satisfactory manner, and a failure is signaled. The code executed when such a reconfiguration occurs is shown in Figure 7.

// Initial nominal mode startTime = System.currentTime() EED.startMonitoring(Spec(Nominal)) Exec (Nominal) // Code executed when an EEDSignal occurs when EEDSignal is received execTime=System.currentTime()-startTime remainingTime=budgetTime-execTime-reconfigurationTime availVersions = {Degi : WCET(Degi)<remainingTime} // only look at degraded versions that are supposed // to finish before the actual deadline if availVersions=Ø then // in this case it is no longer possible to match // the deadline signal ApplicationFailure else // choose the best degraded mode and launch it next=Degj such that WCET(Degj)=max(WCET(availVersions)) EED.startMonitoring(Spec(next)) Exec(next)

Figure 7. Nominal and reconfiguration code

Notice that this approach assumes that degraded modes can be started at any time, and that nominal and degraded modes do not interfere with each other. This is the case, for example, when the periodic task is a calculus task, or a filter task, that do not write information in memory before it is finished.

Integration into avionics systems

The electrical flight control systems in modern aircrafts control the slats, flaps and spoilers. These systems have very stringent safety requirements (in the sense that the runaway of these control surfaces is generally classified as Catastrophic and must then be extremely improbable). The use of such system is nowadays common practice in civil aircraft, from the A320 to the big Jumbo A380 developed by Airbus [START_REF] Traverse | Airbus fly-by-wirea total approach to dependability[END_REF], but also in concurrent aircrafts done by Boeing.

Technical approach

In Airbus systems, the implementation of safety critical functions relies on duplication and diversification. Such function is implemented with a PRIM ("active") and a SEC computer ("standby", hot spare). The PRIM computer is responsible for service delivery until it fails, i.e. becomes silent. The assumption coverage of the fail silent assumptions relies on a typical architecture, based on the "command-monitoring" design pattern. The command channel ensures the function allocated to the computer (for example, control of a moving surface). The monitoring channel ensures that the command channel operates correctly. Command and monitoring are running in parallel on two different processors. Failure detection is mainly achieved by comparing the outputs between the command and monitoring commands with a predetermined threshold.

The diversified redundancy at system level (PRIM/SEC) enable safety requirements to be reached for certification purposes. From a practical standpoint, the dissimilarity is such that the SEC computer runs a simpler version of the command software. In summary, at software level, the architecture of the system leads to use four software packages (for instance ELAC/-COM, ELAC/MON, SEC/COM, SEC/MON) when, functionally, one would suffice.

EED integration and interest

The EDD mechanisms could be integrated into both the command and/or the monitoring channel of each computers. The EED mechanisms would improve the detection in the temporal domain, but also to the behavioral domain depending on the granularity of the functional software modeling. This implies, at least, that a model of the command specification has been developed for its runtime verification. The integration into the COM is a direct application of the use of EDD for handling several degraded modes of operation. It means that the COM software must be developed with degraded versions, the bottom version being the reset of the processor hosting the COM. The execution of the EED monitoring is thus collocated with the COM and thus the EED monitoring can access the event and data required to animate the model. This approach enables the COM to improve its behavior with respect to transient physical faults that could impair the outputs and their delivery time. The integration of EDD has an impact on the development of the COM but no impact on the whole COM-MON architecture. However, the EED monitor being run on the same processor with the COM is also subject to error propagation. Conversely, the integration of EED into the MON provides better separation of concerns and physical isolation between the COM and the MON. However, this solution implies a slightly different architecture or, at least requires more complex interactions between the COM and the MON, which is not the case in the standard configuration. Indeed, this solution requires a more detailed interaction between the "command" and the "monitoring" channels. All events required to animate the model at runtime must be extracted and forwarded to the monitoring "channel". At present the interaction between the "command" and the "monitoring" channels is very limited, just a watchdog mechanism. We would assume that the communication channel between COM and MON in this case is reliable. All messages sent are correctly received in FIFO order until one fails. In both cases, the use of EED would improve the standard behavior. On the PRIM computer, instead of waiting for COM-MON output discrepancy, the EED-based monitoring will suspend the "command" channel as soon as possible and stop sending the "I'm healthy signal". This implies a switch to the SEC computer that can provide output results early. This approach enables the SEC channel to take over the lead without waiting the detection of the PRIM failure on outputs.

Conclusion

Many run-time monitoring frameworks are intended to be used during the debug phase of system development. Few of them have been extended in order to support the integration of error recovery actions at run-time, and all such prototypes are developed in Java as remote objects.

The interest of our solution lies in the way the detector is integrated in a real-time system in order to provide timely reaction. Our implementation in Xenomai benefits from the fact that Xenomai provides several ports of usual RTOS APIs, thus enabling the integration of heterogenous off-the-shelf applications. In this context, the monitor will ensure that all these applications behave as expected especially in the case they use API ports instead of Xenomai native system calls.

The overhead introduced by our approach can be decreased at least by a factor 2. An implementation of this service as a kernel module of Xenomai would decrease highly the time spent switching between kernel and user space during the verification. From our measurements [START_REF] Robert | Evaluation of a realtime monitoring framework[END_REF], the time spent in system calls is always greater than the time spent checking events and computing deadlines (case study drawn from UPPAAL case studies). Our prototype is available at the following address: [START_REF] Robert | RTRV -real-time run-time verification framework[END_REF].

Interestingly, we showed in this paper that our approach can be easily integrated with usual resilience patterns, namely degraded modes of operation and the critical system that runs in many Airbus airplanes.

The next step is to consider a specification language that fully integrates the architectural dimension of modern real-time applications, like AADL. Generating monitors from such models could take into account the scope of errors and specifications. It would be an opportunity to study optimization strategies to use early error detection when the gain in terms of detection latency is high.

Figure 1 .

 1 Figure 1. Good and bad prefixes

Figure 2 .

 2 Figure 2. Abstract architecture of a monitorbased detector

Figure 3

 3 Figure 3. Conflict between timing constraints

Figure 8 .

 8 Figure 8. Computer global architecture

In this case, the WCET is at least t + 10, so WCET ≥ t + 10 >

[START_REF] Traverse | Airbus fly-by-wirea total approach to dependability[END_REF], whereas WCET < 20 by the deadline specification

Recall the example: the process could access the shared data at x > 10 because no guard prevent it locally -the transition can be fired-. Nevertheless, it will lead the system to the kind of conflict depicted in

later on.


Franc ¸ois Dorin

Patrick Meumeu Yomsi
email: patrick.meumeu.yomsi@ulb.ac.be

Joël Goossens
email: joel.goossens@ulb.ac.be

Pascal Richard
email: richardp@ensma.fr

Semi-Partitioned Hard Real-Time Scheduling with Restricted Migrations upon Identical Multiprocessor Platforms

Algorithms based on semi-partitioned scheduling have been proposed as a viable alternative between the two extreme ones based on global and partitioned scheduling. In particular, allowing migration to occur only for few tasks which cannot be assigned to any individual processor, while most tasks are assigned to specific processors, considerably reduces the runtime overhead compared to global scheduling on the one hand, and improve both the schedulability and the system utilization factor compared to partitioned scheduling on the other hand.

In this paper, we address the preemptive scheduling problem of hard real-time systems composed of sporadic constrained-deadline tasks upon identical multiprocessor platforms. We propose a new algorithm and a scheduling paradigm based on the concept of semi-partitioned scheduling with restricted migrations in which jobs are not allowed to migrate, but two subsequent jobs of a task can be assigned to different processors by following a periodic strategy.

Introduction

In this work, we consider the preemptive scheduling of hard real-time sporadic tasks upon identical multiprocessors. Even though the Earliest Deadline First (EDF) algorithm [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] turned out to be no longer optimal in terms of schedulability upon multiprocessor platforms [START_REF] Dhall | On a real-time scheduling problem[END_REF], many alternative algorithms based on this scheduling policy have been developed due to its optimality upon uniprocessor platforms [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. Again, the primary focus for designers is at improving the worst-case system utilization factor with guaranteeing all tasks to meet deadlines. Unfortunately, most of the algorithms developed in the literature suffer from a trade-off between the theoretical schedula-bility and the practical overhead of the system at run-time: achieving high system utilization factor leads to complex computations. Up to now, solutions are still widely discussed.

In recent years, multicore architectures, which include several processors upon a single chip, have been the preferred platform for many embedded applications. This is because they have been considered as a solution to the "thermal roadblock" imposed by single-core designs. Most chip makers such as Intel, AMD and Sun have released dual-core chips, and few designs with more than two cores have been released as well. However given such a platform, the question of scheduling hard real-time systems becomes more complicated, and thus, has received considerable attention [START_REF] Baker | Schedulability analysis of multiprocessor sporadic task systems[END_REF][START_REF] Goossens | Real-time scheduling on multiprocessors[END_REF]. For such systems, most results have been derived under either global or partitioned scheduling techniques. While both approaches might be viable, each has serious drawbacks on this platform and none will likely utilize the system very well while considering EDF scheduling policy.

In global scheduling [START_REF] Bertogna | Schedulability analysis of global scheduling algorithms on multiprocessor platforms[END_REF], all tasks are stored in a single priority-ordered queue. The global scheduler selects for execution the highest priority tasks from this queue. Unfortunately, algorithms based on this technique may lead to runtime overheads that are prohibitive. This is due to the fact that tasks are allowed to migrate from one processor (CPU) to another in order to complete their executions and each migration cost may not be negligible. Moreover, Dhall et al. showed that global EDF may cause a deadline to be missed if the total utilization factor of a task set is slightly greater than 1 [START_REF] Dhall | On a real-time scheduling problem[END_REF].

In partitioned scheduling [START_REF] Baruah | The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems[END_REF], tasks are first assigned statically to processors. Once the task assignment is done, each processor uses independently its local scheduler. Unfortunately, algorithms based on this technique may lead to task systems that are schedulable if and only if some tasks are not partitioned. Moreover, Lopez et al. showed that the total utilization factor of a schedulable system using this technique is at most 0.5(m + 1), where m is the number of processors in the system.

These two scheduling techniques are incomparableat least for priority driven schedules -, that is, there are systems which are schedulable with partitioning and not by global and conversely. It thus follows that the effectiveness of a scheduling algorithm depends not only on its runtime overhead, but also its ability to schedule feasible task systems.

Recent work [START_REF] Andersson | Sporadic multiprocessor scheduling with few preemptions[END_REF][START_REF] Kato | Real-time scheduling with task splitting on multiprocessors[END_REF][START_REF] Kato | Portioned EDF-based scheduling on multiprocessors[END_REF] came up with a novel and promising technique called semi-partitioned scheduling with the main objectives of reducing the runtime overhead and improving both the schedulability and the system utilization factor. In semi-partitioned scheduling techniques, most tasks, called non-migrating tasks, are fixed to specific processors in order to reduce runtime overhead, while few tasks, called migrating tasks, migrate across processors in order to improve both the schedulability and the system utilization factor. However, the migration costs depend on the instant each migrating task is migrated during execution: migrating a task during the execution of one of its jobs is more time consuming than migrating it at the instant of its activation. As such, we can distinguish between two levels of migration: job migration where a job is allowed to execute on different processors [START_REF] Andersson | Sporadic multiprocessor scheduling with few preemptions[END_REF] and task migration where task migration is allowed, but job migration is forbidden. Between the two techniques, the task migration is the one which minimizes the migration costs. To the best of our knowledge, only one solution using the latter semi-partitioned scheduling technique was established but it is only applicable to soft real-time systems [START_REF] Anderson | An EDF-based scheduling for multiprocessor soft real-time systems[END_REF].

In this paper, we study the scheduling of hard real-time systems composed of sporadic constrained-deadline tasks upon identical multiprocessor platforms. For such platforms, all the processors have the same computing capacities.

Related work. On the road to solve the above mentioned problem, sound results using semi-partitioned scheduling techniques have been obtained by S. Kato in terms of both schedulability and system utilization factor. However, these results are all based on "job-splitting" strategies [START_REF] Kato | Portioned EDF-based scheduling on multiprocessors[END_REF], and consequently, may still lead to prohibitive runtime overheads for the system. Indeed, the main idea of S. Kato consists in using a "job-splitting" (i.e., job migration is allowed) strategy based on a specific algorithm for tasks which cannot be scheduled by following the First Fit Decreasing (FFD) algorithm [START_REF] Kato | Semi-partitioned scheduling of sporadic task systems on multiprocessors[END_REF]. Figure 1 illustrates that the entire portion of job τ k is not partitioned but it is split into τ k,1 , τ k,2 and τ k,3 which are partitioned upon CPUs π 1 , π 2 and π 3 , respectively. The amount of each share is such a value that fills the assigning processor to capacity without timing violations.

Due to such a "job-splitting" strategy, it is necessary to have a mechanism which ensure that each job cannot be executed in parallel upon different processors. Such a mechanism has been provided by the introduction of execution windows 3 . Using this mechanism, each share can 3 An execution window for a job is a time span during which it is allowed to execute. execute only during its execution window. Hence, multiple executions of the same job upon several processors at the same time are prohibited by guaranteeing that the execution windows do not overlap [START_REF] Kato | Semi-partitioned scheduling of sporadic task systems on multiprocessors[END_REF].

π 1 π 2 π 3 π 4 0% 100% CPU load τ k,1 τ k,2 τ k,3 τ k+1,1 τ k+2,1 τ k+2,2 τ k τ k,1 τ k,2 τ k,3 τ k+1 τ k+1,1 τ k+2 τ k+2,1 τ k+2,2
This research. In this paper, we propose a new algorithm and a scheduling paradigm based on the concept of semi-partitioned scheduling with restricted migrations: jobs are not allowed to migrate, but two subsequent jobs of a task can be assigned to different processors by following a periodic strategy. Our intuitive idea is to limit the runtime overhead as it may still be prohibitive for the system when using a job-splitting strategy. The algorithm starts with a classical step where tasks are partitioned among processors using the FFD algorithm for sake of comparison of our results to those obtained by S. Kato. Then, for the remaining tasks (i.e., those whose all the jobs cannot be assigned to one processor by following FFD without exceeding its capacity), a semi-partitioning scheduling technique with restricted migrations is used by following a periodic strategy detailed later on.

Paper organization. The remainder of this paper is structured as follows. Section 2 presents the task model and the platform that are used throughout the paper. Section 3 provides the principles of the proposed algorithm. Section 4 elaborates the conditions under which the system is schedulable. Section 5 presents experimental results. Finally, Section 6 concludes the paper and proposes future work.

System model

We consider the preemptive scheduling of a hard realtime system τ def = {τ 1 , τ 2 , . . . , τ n } comprised of n tasks upon m identical processors. In this case, all the processors have the same computing capacities. The k th processor is denoted π k . Each task τ i is a sporadic constraineddeadline task characterized by three parameters (C i , D i , T i ) where C i is the Worst Case Execution Time (WCET), D i ≤ T i is the relative deadline and T i is the minimum inter-arrival time between two consecutive releases of τ i . These parameters are given with the interpretation that task τ i generates an infinite number of successive jobs τ i, j with execution requirement of at most C i each, arriving at time a i, j such that a i, j+1a i, j ≥ T i and that must completes within [a i, j , d i, j ) where d i, j def = a i, j + D i , the absolute deadline of job τ i, j .

The utilization factor of task τ i is defined as u i def = C i /T i and the total utilization factor of task system τ is defined as U sum (τ) def = ∑ n i=1 u i . A task system is said to fully utilize the available processing capacity if its total utilization factor equals the number of processors (m). The maximum utilization factor of any task in τ is denoted u max (τ). A task system is preemptive if the execution of any of its jobs may be interrupted and resumed later due to the execution of another job with a higher priority. In this paper, we consider preemptive scheduling policies and we place no constraints on total utilization factor.

We consider that tasks are scheduled by following the Earliest Deadline First (EDF) scheduler with restricted migrations. That is, on the one hand, the shorter the absolute deadline of a job the higher its priority. On the other hand, tasks can migrate from one processor to another but when a job has started upon a given processor then it must complete without any migration. Such a strategy is a compromise between task partitioning and global scheduling strategies.

We assume that all the tasks are independent, that is, there is no communication, no precedence constraint and no shared resource (except for the processors) between tasks. We assume that the jobs of a task cannot be executed in parallel, that is, for any i and j, τ i, j cannot be executed in parallel on more than one processor. Moreover, this research assumes that the costs of preempting and migrating tasks are included in the WCET, which makes sense since we limit migrations at task arrival instants and preemptions at task arrival or completion instants (EDF is the local scheduler).

Principle of the algorithm

In this section, we provide to the reader the main steps of our algorithm. Its design is based on the concept of semi-partitioned scheduling with restricted migrations and consists of two phases:

(1) The assigning phase: here, each non-migrating task is assigned to a specific CPU by following the FFD algorithm and the jobs of each migrating tasks are assigned to CPUs by following a periodic strategy.

(2) The scheduling phase: here, each migrating task is modeled upon each CPU as a multiframe task and thus the schedulability analysis focuses on each CPU individually, using the rich and extensive results from the uniprocessor scheduling theory.

Semi-partitioning scheduling algorithm

This section describes our semi-partitioning algorithm based on the concept of semi-partitioned scheduling. Like traditional partitioned scheduling algorithms, the schedulers have the same scheduling policy upon each CPU, that is EDF in this case, but each of them is not completely independent, because several CPUs may share a migrating task. The principle of the algorithm is as follows.

• Sort the tasks in decreasing order of their utilization factor.

• For each task considered individually:

-Select one CPU and set it as the one with the smallest index.

-If the current task is schedulable upon the selected CPU while using the FFD algorithm (i.e. all jobs meet their deadlines), then assign the task to this CPU.

-If the current task is neither schedulable upon the selected CPU and nor upon the others by using the FFD algorithm, then determine the number of jobs that can be scheduled upon the selected CPU w.r.t. an EDF scheduler. Assign those jobs to the selected CPU by using the multiframe task approach defined earlier. Then, move to the next CPU. Repeat this process until all the jobs of the task are assigned to a CPU.

In the end, the intuitive idea behind our algorithm is to consider one task at each step and defines the minimum number of CPUs required to execute all its jobs (this takes at most m iterations, where m is the number of CPUs). At the beginning, the algorithm performs using an FFD algorithm. Then, whenever a task cannot be assigned to a particular CPU, its jobs are assigned to a subset of CPUs belonging to the platform (at most m). Thus, the algorithm requires at most O(nm) schedulability tests.

The assigning phase

In this phase, each task τ k is assigned to a particular processor π j by following the FFD algorithm, as long as the task does not cause the system not to be schedulable upon π j . That is, Load(τ

π j ) def = sup (t≥0) DBF(τ π j ,t) t ≤ 1
, where τ π j denotes the subset of tasks assigned to CPU π j and DBF is the classical Demand Bound Function [START_REF] Baruah | Generalized multiframe tasks[END_REF],

DBF(τ π j ,t) def = ∑ τ k ∈τ π j t+T k -D k T k •C k . Such a task is clas- sified into a non-migrating task. Now, if Load(τ π j ) > 1,
that is, all the jobs of a task cannot be assigned to the same processor, then the task is classified into a migrating task. The jobs are assigned to several processors by following a periodic strategy and are executed upon these by using a semi-partitioned scheduling with restricted migrations. Details on this strategy, obviously chosen for sake of simplicity during the implementations, are provided in the Section 3.3.

Example. In order to illustrate this strategy for a system with a single migrating task task τ i = (C i , D i , T i ), we assume that τ i has been assigned to a set of CPUs containing at least π 1 and π 2 with the periodic sequence σ def = (π 1 , π 2 , π 1 ). This means, the first job of τ i will be assigned to π 1 , the second one to π 2 , the third one to processor π 1 and from the fourth job of τ i , this very same process will repeat cyclically upon processors π 1 and π 2 . Figure 2 depicts this job assignment.

π 1 π 2 0% 100% CPU load τ i τ 1 i (C i , 0, C i ) τ 2 i (0, C i , 0) τ 1 i τ 2 i Multiframe tasks Figure 2. Periodic job assignment.
From the schedulability point of view, task τ i will be duplicated upon CPUs π 1 and π 2 and according to the scheduling phase, it will be seen as two multiframe tasks (see [START_REF] Mok | A multiframe model for real-time tasks[END_REF] for further details on multiframe tasks). These multiframe tasks will be denoted by τ 1 i and τ 2 i and will have the following parameters:

τ 1 i def = ((C i , 0,C i ), D i , T i ) and τ 2 i def = ((0,C i , 0), D i , T i ).
As such, we will be able to perform the schedulability analysis upon each CPU individually, using uniprocessor approaches, already well understood.

Periodic job assignment strategy

Since each task consists of an infinite number of jobs, a potentially infinite number of periodic job assignment strategies can be defined for assigning migrating tasks to the CPUs. In this section, we propose two algorithms to achieve this: The most regular-job pattern algorithm and the alternative-job pattern algorithm.

In this paper, since each migrating task is modeled as a multiframe task upon each CPU it has at least one job assigned to, we assume that the number of frames obtained from each migrating task is equal to a non-negative integer K which is known beforehand for sake of readability. This assumption will be relaxed in future work.

Let

A[1 • • • n, 1 • • • m] be a matrix of integers where A[i, j] def = x (with 1 ≤ i ≤ n and 1 ≤ j ≤ m)
indicates that x jobs among K consecutive jobs of task τ i will be executed upon processor π j . In the following, we provide the reader with details on two algorithms used to initialize matrix

A[1 • • • n, 1 • • • m],
while guaranteeing for every task τ i that ∑ j=1,...,m A[i, j] = K.

Before going any further in this paper, it is worth noticing that if K = 1, then task migrations are forbidden. Thus, our model extends the classical partitioning scheduling model. If the A[i, j] are known beforehand, then the most regular-job pattern algorithm is considered, otherwise we consider the alternative-job pattern algorithm.

Most regular-job pattern algorithm

A uniform assignment of jobs of each migrating task τ i among the subset of CPUs S i upon which τ i will execute at least one job seems to be a good idea at first glance (but we have no theoretical result proving that). For this reason we introduce the principle laying behind such a strategy [START_REF] Karp | The organization of computations for uniform recurrence equations[END_REF]. In S i , we assume that the CPUs are ranged in a non-decreasing index-order. If S i = / 0, then the system is clearly not schedulable.

The job assignment is performed according to the following two steps for task τ i .

• Step 1. The matrix A is computed thanks to Algorithm 1 (see Section 3.1 for details).

• Step 2. The assignment sequence σ of task τ i is defined through K sub-sequences as follows.

σ def = (σ 0 , σ 1 , . . . , σ ℓ , . . . , σ K-1 ) (1)
where the (ℓ + 1) th sub-sequence σ ℓ (with ℓ = 0, . . . , K -1) is given in turn by the following mtuple:

σ ℓ def = (σ 1 ℓ , σ 2 ℓ , . . . , σ m ℓ ) (2)
To define sub-sequence σ ℓ using the uniform assignment pattern, there is at most one job per CPU each time w.r.t. Equation 3. The ℓ th job of τ i will be assigned to π j if and only if:

σ j ℓ def = ℓ + 1 K • A[i, j] - ℓ K • A[i, j] = 1 (3)
The goal is to assign A[i, j] jobs among K consecutive jobs of task τ i to CPU π j by following a step-case function. For the ℓ th job, σ j ℓ yields 1 when the job is assigned to π j and 0 otherwise. Figure 3 Thanks to these rules, it follows, depending on the value of parameter K, that a direct advantage of this cyclic job assignment is its ability to considerably reduces the number of task migrations.

Example. In order to illustrate our claim, consider a platform comprised of 3 identical CPUs π 1 , π 2 , π 3 . We assume that K = 11. For a migrating task τ i , let us consider that A[i, 1] = 4, A[i, 2] = 2 and A[i, 3] = 5, meaning that 4 jobs of τ i are assigned to CPU π 1 , 2 jobs to CPU π 2 and 5 jobs to CPU π 3 . The computations for defining the job assignment sub-sequences using Equation 3 are summarized in Table 1.

ℓ 0 1 2 3 4 5 6 7 8 9 10 total π 1 1 0 1 0 0 1 0 0 1 0 0 4 π 2 1 0 0 0 0 1 0 0 0 0 0 2 π 3 1 0 1 0 1 0 1 0 1 0 0 5

Table 1. Most regular-job assignment sequence

At step ℓ = 5 for instance, one job of τ i will be assigned to π 1 , then one job to π 2 , and no job will be assigned to π 3 . Whenever σ j k = 0 (∀ j), as this is case at steps 1, 3, 7 and 10 in Table 1, then none of the jobs is assigned to none of the CPUs. Such a sub-sequence can be ignored while defining the cyclic assignment controller. In this example, the complete assignment sequence, that will be used to define the cyclic assignment controller for jobs of task τ i is derived as follows.

σ = (σ 0 , σ 1 , . . . , σ K-1 ) = (π 1 , π 2 , π 3 , π 1 , π 3 , π 3 , π 1 , π 2 , π 3 , π 1 , π 3 )
While using this strategy, even though this algorithm considerably reduces the number of task migrations, we have a recursion problem since to determine the jobpattern we need actually to know the job-pattern. Indeed, in order to know that A[i, j] jobs of task τ i are assigned to CPU π j , we need to perform a schedulability test. However, such a test needs the pattern of the multiframe tasks assigned to each CPU to be known beforehand. A solution to this recursion problem is to use a schedulability test which requires only the number of jobs. That is, the one based on a worst-case scenario, which necessarily introduces a lot of pessimism.

The next job-pattern determination technique will address this drawback and consequently schedules a larger number of task systems.

Alternative job-pattern algorithm

This cyclic job assignment algorithm has been designed in order to overcome the drawback highlighted in the previous one (see algorithms 2-3). It considers each CPU individually and compute the matrix A incrementally. Initially, A[i, 1] is initialized at K. If the obtained multiframe task is not schedulable upon π 1 , then A[i, 1] is decremented to K -1. The decrement is repeated until we get the largest number jobs of τ i which are schedulable upon π 1 . In the previous example, integers between 11 and 5 have been tested without success, but A[i, 1] = 4 succeeded, then the multiframe task which will be considered upon this CPU is

τ 1 i = ((C i , 0,C i , 0, 0,C i , 0, 0,C i , 0, 0), D i , T i ) using
Step 2 of the previous method (Equation 3 in particular). In addition, instead of directly considering a multiframe task with K frames each time, this alternative algorithm allows us to temporarily consider multiframe tasks with a number of frames equal to the number of remaining jobs.

In order to determine the multiframe task τ 2 i that will be executed upon CPU π 2 , we temporarily consider a multiframe task τ ′ 2 i with (J = K -A[i, 1]) frames (corresponding to the number of remaining jobs for τ 2 i ). This temporal multiframe task τ ′ 2 i is built by using the Step 2 of the previous method (Equation 3 in particular), and then we determine its pattern by considering τ

′ 2 i def = ((σ 2 1 C i , . . . , σ 2 J C i ), D i , T i ) with σ 2 ℓ ∈ {0, 1}, 1 ≤ ℓ ≤ J.
After this operation has been performed, the multiframe task τ 2 i is provided with K frames by using τ 1 i and τ

′ 2
i , based on the following two rules: (i) If the j th frame of τ 1

i is nonzero, then the j th frame of τ 2 i equals zero. (ii) If the j th frame of τ 1

i is zero and corresponds to the q th zero-frame of τ 1 i , then the j th frame of τ 2 i is determined by using the value of the q th frame of τ ′ 2 i . These rules can be generalized very easily. Suppose our aim is determining the multiframe task τ k i corresponding to τ i upon CPU π k . The steps to perform are as follows. We first determine the amount of remaining jobs

J def = K -∑ k-1 q=1 A[i, q]
. Then, we compute τ ′ k i thanks to Equation 3, by using J rather than K. Finally, we determine τ k i by using the pseudo-code of Algorithm 2 where τ ℓ i ( j) denotes the j th frame of τ ℓ i . That is, if

τ ℓ i = ((C i , 0,C i ), D i , T i ), then τ ℓ i (1) = C i , τ ℓ i (2) = 0 and τ ℓ i (3) = C i . Algorithm 2: Computation of τ k i Input: K, k, τ = (τ 1 i , . . . , τ (k-1) i ), τ ′ k i Output: Multiframe task τ k i Function Compute (in τ ′ k i , in K, in τ) begin q ← 1 ; for (j = 1 . . . K) do Free ← True; ζ ← 1; while (ζ < k and Free) do if τ ζ i ( j) = 0 then ζ ← ζ + 1; else Free ← False; if Free then τ k i ( j) ← τ ′ k i (q); q ← q + 1; else τ k i ( j) = 0; return τ k i ;
Algorithm 3: Jobs assignment for migrating task τ i

Input: K, task τ i Output: True and A if τ i is schedulable, False otherwise Function Algo2 (in τ i , in K, out A) begin RemJobs ← K ; /* Remaining jobs*/ for (k = 1 • • • m) do for ( j = RemJobs • • • 1) do Compute τ ′ k
i by using Equation 3where K is replaced by RemJobs ;

τ k i = Compute(τ ′ k i , K, (τ 1 i , . . . , τ (k-1) i )); if (τ k i is schedulable on π k ) then A[i, k] ← j; RemJobs ← RemJobs -j ; Exit;
if RemJobs = 0 then return True ;

return False

Example. Consider the same task τ i as in the previous example. Assuming only 4 jobs can be assigned to π 1 , then the multiframe task τ 1 i upon π 1 is

τ 1 i = ((C i , 0,C i , 0, 0,C i , 0, 0,C i , 0, 0), D i , T i ) by using Algo- rithm 2. If τ 1
i is schedulable upon π 1 , then we consider π 2 and we repeat the same process. If not, we try to assign jobs to π 1 , now assuming only 3 jobs can be assigned this time.

In this example, we assume that 4 jobs have successfully been assigned to π 1 . We now assume that neither 4, nor 3 jobs of τ i cannot be assigned to π 2 , but 2 jobs can. Computing the intermediate task τ

′ 2 i using J = 11 -4 = 7 leads us to τ ′ 2 i = ((C i , 0, 0,C i , 0, 0, 0), D i , T i ).
By applying Algorithm 2 again, we obtain τ 2 i = ((0,C i , 0, 0, 0, 0,C i , 0, 0, 0, 0), D i , T i ).

We repeat the same process for CPU π 3 . When trying to assign the 5 remaining jobs, computing τ

′ 3 i with J = 5 gives τ ′ 3 i = ((C i ,C i ,C i ,C i ,C i ), D i , T i ).
Again, applying Algorithm 2, we obtain

τ 3 i = ((0, 0, 0,C i ,C i , 0, 0,C i , 0,C i ,C i ), D i , T i ).

Schedulability analysis

This section derives the schedulability conditions for our algorithm. Because each migrating task is modeled as a multiframe task on each CPU upon which it has a job assigned to, the schedulability analysis is performed on each CPU individually, using results from the uniprocessor scheduling theory. As tasks are scheduled upon each CPU according to an EDF scheduler, a specific analysis is necessary only for CPUs executing at least one multiframe task. For such a CPU, classical schedulability analysis approaches such as "Processor Demand Analysis" cannot applied, unfortunately. This is due to migrating tasks. We consider two scenarios to circumvent this issue: the packed scenario and the scenario with pattern and we develop a specific analysis based on an extension of the Demand Bound Function (DBF) [START_REF] Baker | Schedulability analysis of multiprocessor sporadic task systems[END_REF][START_REF] Baruah | Generalized multiframe tasks[END_REF] to multiframe tasks. We recall that a natural idea to cope with each migrating task is to duplicate it as many time as the number of CPUs it has a job assigned to and consider a multiframe task upon each CPU.

Packed scenario

As each migrating task τ i is modeled as a collection of at most m multiframe tasks τ 1 i , τ 2 i , . . . , τ m i , where τ j i is to be executed upon CPU π j (m is the number of CPUs), this scenario considers the worst-case. This occurs when, for each multiframe task associated to τ i , all nonzero execution requirements are at the beginning of the frames and the remaining execution requirements are set to zero. That is τ k i is modeled as

τ k i def = ((C i ,C i , . . . ,C i , 0, . . . , 0), D i , T i )
, where C i is the execution requirement of task τ i . (see Appendix for the proof).

In order to define DBF at time t (that is, our adapted Demand Bound Function for systems such as those considered in this paper), we need to define the contribution of each task in the time interval [0,t). As K denote the number of execution requirements in a multiframe task τ k i associated to τ i , let ℓ k i denote the number of nonzero execution requirements in τ k i . When using the packed scenario,

τ k i can be modeled as τ k i = ((C i , . . . ,C i ℓ k i elements , 0, . . . , 0), D i , T i ).
The challenge is to take into account that only ℓ k i jobs of task τ k i will contribute to the DBF in the time interval [0, K • T i ).

Based on Figure 4, the contribution to DBF at time t for the multiframe task τ k i is determine as follows.

• First, consider the number of intervals of length K • T i by time t. Letting s denote that number, we have:

s def = t K • T i (4)
As such, the contribution of

τ k i to the DBF is at least s • ℓ k i •C i . • Second, consider the time interval [s • K • T i ,t),
where several jobs may have their deadlines before time t.

Assuming that all the jobs are assigned to the considered CPU, the number of jobs ("a") is given by:

a def = max 0, (t mod K • T i ) -D i T i + 1 (5)
Since at most ℓ k i jobs over K will be executed upon that CPU, then the exact contribution of

τ k i in interval [s • K • T i ,t) is given by: min(ℓ k i , a) •C i .
Putting all of these expressions together, the DBF of τ k i at time t is defined as follows.

DBF(τ

k i ,t) def = s • ℓ k i •C i + min ℓ k i , a •C i (6)
Schedulability Test 1. Let τ = {τ 1 , τ 2 , . . . , τ n } be a set of n constrained-deadline sporadic tasks to be scheduled upon an identical multiprocessor platform. For each selected CPU π, if N ⊆ τ denotes the subset of nonmigrating tasks upon π, then a sufficient condition for the system to be schedulable upon π is given by

∑ τ j ∈N DBF(τ j ,t) + ∑ τ k i ∈π\N DBF(τ k i ,t) ≤ t ∀t (7)
In Equation 7, τ j is a non-migrating task, DBF is the classical Demand Bound Function and τ k i is a multiframe task assigned to π.

Scenario with pattern

This scenario, in contrast to the packed one which considers the worst-case, takes the pattern of job assignment provided by our algorithm into account. Indeed, implementations showed that the schedulability analysis based on the packed scenario may be too pessimistic, unfortunately.

The schedulability test developed in this section is similar to the one developed previously for packed scenarios in that it is also based on the DBF. However the pattern of job assignment to CPUs is taken into account. Therefore, the only noticeable difference comes from the second term of Equation 6 which is replaced by:

K-1 max c=0 c+nb i (t)-1 ∑ j=c C i, j mod K (8) In Expression 8, nb i (t) def = (t mod K•T i )-D i T i
+1 and denotes the number of jobs of τ k i in the time interval [s • K • T i ,t). This is, we compute the processor demand by considering that the "critical instant" coincide with the first job of the pattern, then the second and so on, until the K th job. After that, we consider the maximum processor demand in order to capture the worst-case. Hence we obtain:

DBF(τ k i ,t) def = s • ℓ k i •C i + K-1 max c=0 c+nb i (t)-1 ∑ j=c C i, j mod K (9)
Schedulability Test 2. Let τ = {τ 1 , τ 2 , . . . , τ n } be a set of n constrained-deadline sporadic tasks to be scheduled upon an identical multiprocessor platform. For each selected CPU π, the sufficient condition for the system to be schedulable upon π is as the previous one except that in Expression 7 the value of DBF is now replaced by DBF. Note that Lemma 1 in the Appendix provides a proof of the "dominance" of Schedulability Test 2 over Schedulability Test 1. That is, all systems that are schedulable using the Test 1 are also schedulable using Test 2.

Experimental results

In this section, we report on the results of experiments conducted using the theoretical results presented in Sections 3 and 4. These experiments help us to evaluate the performances our algorithms relative to both the FFD and the S. Kato algorithms. Moreover, they help us to point out the influence of some parameters such as the value of parameter K and the number of CPUs in the platform. We performed a statistical analysis based on the following characteristics: (i) the number of CPUs is chosen in the set M def = {2, 4, 8, 16, 32, 64} for practical purpose. Indeed multicore platforms often have a number of cores which is a power of 2, (ii) the system utilization factor for each CPU varies between 0.70 and 1 using a step of 0.05, as the results are identical when the CPU utilization is less than 0.7.

During the simulations, 10.000 runs have been performed for each configuration of the pair (number of CPUs in the platform, system utilization factor). In the figures displayed below, a "success ratio" of 2% of an algorithm A over an algorithm B means that A leads to a schedulability ratio of y%, where B leads to a schedulability ratio (y -2)%.

For comparison reasons, the same protocol as the one described in [START_REF] Kato | Semi-partitioned scheduling of sporadic task systems on multiprocessors[END_REF] by S. Kato for generating task systems has been considered. That is:

0T τ 1 i (1)
1T

τ 1 i (2) 2T τ 1 i (3) 3T τ 1 i (1) KT 4T τ 1 i (2) 5T τ 1 i (3) 6T τ 1 i (1) KT 7T τ 1 i (2) 8T τ 1 i (3) 9T τ 1 i (1)
10T

τ 1 i (2) t KT KT t -t KT KT t Figure 4. Illustration of the multiframe task τ 1 i = ((C i , 0,C i ), T i , T i ).
1. the utilization factor of each task is randomly generated in the range [0, 1] with the constraint that the sum of utilization factors of all tasks must be equal to the utilization factor of the whole system, 2. the period T i of task τ i is randomly chosen in the range [100, 3000],

3. the relative deadline D i of task τ i is set equal to its period, 4. the WCET C i of task τ i is computed from its period T i and its utilization factor u i as

C i def = u i • T i .
It is worth noticing that we have no control of the number of tasks composing the system. This number depends on the utilization factors of the tasks.

Figure 5 depicts the curve of the success ratio relative to parameter K for "packed scenarios". As we can see, the lower the value of K, the higher the success ratio. This result may be surprising and counter-intuitive at first glance as we would expect the contrary, that is, increasing K would improve the success ratio. A reason to this is provided by the pessimism introduced when packing all the nonzero frames at the beginning of each multiframe task. Indeed in this case, the processor demand is overestimated at time t = 0 for each CPU upon which there is a multiframe task. To illustrate our claim, when K = 2, each migrating task is assigned to at most 2 CPUs, thus increasing the pessimism for these CPUs. Consequently, the larger the value of K, the larger the number of CPUs for which the processor demand will be over-estimated.

Figure 6 depicts the curve of the success ratio relative to parameter K for the "scenario with pattern". Here, in contrast to the results obtained for "packed scenarios", the curves behave as we would intuitively expect them. That is, increasing the value of K leads to a higher success ratio. This is due to the fact that a higher value of K allows the jobs of a migrating task to be assigned to a larger set of CPUs, thus reducing the global computation requirement upon each CPU. Now, it is worth noticing that both the packed scenario and the scenario with pattern lead to the same algorithm when K = 2. In fact, while considering a scenario with pattern, the multiframe execution requirements which are allowed for a migrating task τ i are (C i , 0) and (0,C i ).

Hence, from the schedulability analysis view point, the one that will be considered is (C i , 0), which corresponds to the packed scenario.

Figure 7 compares the performances of the algorithms which provided the best results using our approach during the simulations, that is, the one using packed scenarios when K = 2 and the one using scenarios with pattern when K = 20, and those of both the FFD and the S. Kato algorithms.

We can see that our algorithms always outperform the FFD algorithm and are a bit behind the one proposed by S. Kato in terms of success ratio. However, the results provided by our algorithms strongly challenge those produced by the S. Kato one for large number of CPUs. Note that our algorithms in contrast to the S. Kato one do not allow job migrations, thus limiting runtime overheads which may be prohibitive for the system. Hence, we believe that our approach is a promising path to go for more competitive algorithms and for practical use.

Conclusion and Future work

In this paper, the scheduling problem of hard real-time systems comprised of constrained-deadline sporadic tasks upon identical multiprocessor platforms is studied. A new algorithm and a scheduling paradigm based on the concept of semi-partitioned scheduling with restricted migrations has been presented together with its schedulability analysis. The effectiveness of our algorithm has been validated by several sets of simulations, showing that it strongly challenges the performances of the one proposed by S. Kato. Future work will address two issues. The first issue is relaxing the constraint on parameter K as we think that is possible to define a value K for each task such that the number of frames are kept as small as possible. The second issue is solving the optimization problem taking into account the number of migrations.

A. Appendix

Let τ i be a multiframe task with a pattern σ def = (σ 1 , . . . , σ K ), that is, τ i = ((σ 1 C i , . . . , σ K C i ), D i , T i ) with σ j ∈ {0, 1}, 1 ≤ j ≤ K. Let ℓ i denotes the number of nonzero execution requirements. Let τ (p) i be the packed version of τ i that is: σ j = 1 if j ≤ ℓ i and σ j = 0, otherwise.

Lemma 1

DBF(τ i ,t) ≤ DBF(τ

(p) i ,t) (10)
Proof By definition:

DBF(τ i ,t) = s • ℓ i •C i + K-1 max c=0 c+nb i (t)-1 ∑ j=c C i, j mod K
In this Equation, the max term can be rewritten as:

K-1 max c=0 c+nb i (t)-1 ∑ j=c C i, j mod K = K-1 max c=0 C i c+nb i (t)-1 ∑ j=c σ i, j mod K (11)
Note that since σ j ∈ {0, 1} and we perform the sum of nb i (t) terms.

c+nb i (t)-1 ∑ j=c σ j mod K ≤ min(ℓ i , max(0, nb i (t)))

Because we have at most ℓ i nonzero execution requirements, so, we take the minimum between ℓ i and nb i (t).

As such,

K-1 max c=0 c+nb i (t)-1 ∑ j=c C i, j mod K ≤ K-1 max c=0
(C i min(ℓ i , max(0, nb i (t)))) [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] leading to

K-1 max c=0 c+nb i (t)-1 ∑ j=c C i, j mod K ≤ C i min(ℓ i , max(0, nb i (t))) (14)
Finally, DBF(τ i ,t) ≤ s • ℓ i •C i +C i min(ℓ i , max(0, nb i (t))).

That is, DBF(τ i ,t) ≤ DBF(τ (p) i ,t). The lemma follows.

Theorem 1 Let τ i be a multiframe task. The worst-case pattern for τ i is the packed pattern.

Proof A pattern A is said worse than a pattern B if and only if A schedulable implies B also schedulable. If the packed pattern is schedulable and thanks to the previous lemma, then DBF(τ i ,t) ≤ DBF(τ p i ,t) ≤ t, ∀t, that is, the pattern Σ is schedulable, and thus, the packed pattern is worse than Σ. Since Σ represent any pattern, the packed pattern is the worst-case pattern. The theorem follows.

Figure 1 .

 1 Figure 1. S. Kato's algorithm [12].

Figure 3 .

 3 Figure 3. Job assignment sequence to π 1 .

Acknowledgment. The authors would like to thank Ahmed Rahni from LISI/ENSMA for his insightful comments on the schedulability tests of multiframe tasks.