Maryline Chetto
email: maryline.chetto@univ-nantes.fr

Hussein El Ghor
email: elghorh@irccyn.ec-nantes.fr

Real-time Scheduling of periodic tasks in a monoprocessor system with rechargeable energy storage

Keywords: scheduling, periodic tasks, earliest deadline, renewable energy

We are interested in a real-time computing system that is powered through a renewable energy storage device. In this context, two constraints need to be addressed: energy and deadlines. Classical task scheduling, in particular Earliest Deadline First, only accounts for timing parameters of the tasks and consequently is not suitable when considering energy constraints. We show here how to modify Earliest Deadline so as to account for the properties of the energy source, capacity of the energy storage as well as energy consumption of the tasks. We present a scheduling framework called EDeg (Earliest Deadline with energy guarantee) and an exact feasibility test that decides for periodic task sets, whether they can be scheduled without deadline violations. To this end, we introduce the concepts of energy demand and slack energy.

I. INTRODUCTION

The problem of scheduling tasks on one processor to meet deadlines and energy constraints has been the focus of great interest for about ten years. However, few papers have been devoted to emerging harvesting systems which need to operate perennially thanks to the environmental energy.

A key consideration that affects power management in an energy harvesting system is that instead of minimizing the energy consumption and maximizing the lifetime achieved as in classical battery operated devices, the system operates in an energy neutral mode by consuming only as much energy as harvested.

The system we target here consists of a processing unit, an energy harvester such as a solar panel or a furl cell, and a rechargeable energy storage such as a battery or a supercapacitor. We consider a single processor that has to execute a set of independent periodic tasks.

So the problem we have to deal with is: How can we schedule the tasks so as to guarantee their timing constraints perpetually by suitably exploiting both the processor and the available ambient energy.

The goal of this work is first to construct an optimal scheduling algorithm and second, to provide an exact schedulability test. Finally, we show how to dimension the capacity of the storage unit, provided that the worst case recharging rate of the storage unit is enough for ensuring neutral operation.

II. RELATED WORKS

In [START_REF] Allavena | Scheduling of Frame-based Embedded Systems with Rechargeable batteries[END_REF], the authors are interested in the problem of scheduling periodic tasks in the so-called frame-based systems with a rechargeable battery. In this model, all task periods are identical, all task deadlines are equal to the common period. Consequently, the order of task execution within a frame is not crucial for whether the task set is schedulable or not. Moreover, the power scavenged by the energy source is assumed to be constant and all tasks consume energy at a constant rate. A solution is presented that schedules tasks in such a way that the wasted recharging energy is minimized and the battery level is at all times within two limits, starting with a battery fully charged. The idea behind this algorithm is to insert as little idle time as necessary for recharging the battery and minimizing the length of the schedule. This work is certainly the first one to concentrate on a rechargeable system with hard real-time constraints. However, the solution only deals with frame based systems under the restrictive hypothesis that each task is characterized by an instantaneous consumption power which is constant along time.

More recently, in [START_REF] Moser | Real-time scheduling for energy harvesting sensor nodes[END_REF] the so-called LSA scheduling algorithm was proved to be optimal under a more generalized model including hard deadline tasks, periodic or not. LSA is a variation of the famous Earliest Deadline First scheduler: the system starts executing a task only if the task is ready and has the earliest deadline among all ready tasks and the system is able to keep on running at the maximum power until the deadline of the task. In that work, the consumption power of the computing system is characterized by some maximum value which implies that for every task, its total energy consumption is directly connected to its execution time through the constant power of the processing device.

However, in practice, the total energy which can be consumed by a task has no correlation with the worst case execution time [START_REF] Jayaseelan | Estimating the Worst-Case Energy Consumption of Embedded Software[END_REF]. For every task, the worst case instantaneous consumption power depends on the circuitry that is used by the task. It clearly appears as impractical to determine the energy consumption of a task from the worst case consumption power for the computing system. While it is easy to determine the average consumption power of a task (given by the execution time and the energy consumption), this parameter is of no interest in the so-called hard real-time applications.

Furthermore, some recent studies focused on how to precisely compute the energy that is consumed by a program, independently of the average or the worst case consumption power of the computing system. More particularly, in [START_REF] Jayaseelan | Estimating the Worst-Case Energy Consumption of Embedded Software[END_REF] a bound on worst-case energy consumption of a task is computed through a static analysis by estimating an upper bound on the energy consumption of all individual basic blocks that make up the task.

III. MODEL AND TERMINOLOGY

A. Task Set

We study the case of a Hard Real-Time system which is composed of periodic tasks. The arrival times, energy demands and deadlines of these tasks are known in advance. Such a periodic task set can be denoted as follows:

τ = {τ i , i = 1, . . . , n}. A four-tuple (C i , E i , D i , T i ) is associated with each τ i .
In this characterization, task τ i makes its initial request at time 0 and its subsequent requests at times kT i , k = 1, 2, ... called release times. The least common multiple of T 1 , T 2 , . . . , T n (called the hyperperiod) is denoted by T LCM . Each request of τ i requires a Worst Case Execution Time (WCET) of C i time units and has a Worst Case Energy Consumption (WCEC) of E i . We assume that the WCEC of a task has no relation with its WCET. A deadline for τ i occurs D i units after each request by which task τ i must have completed its execution. We assume that 0 < C i ≤ D i ≤ T i for each 1 ≤ i ≤ n. We define:

• the processor utilization as U p = n i=1 Ci Ti .

• and the energy utilization as

U e = n i=1
Ei Ti A job is any request that a task makes. A four-tuple (r j , C j , E j , d j ) is associated with a job J j and gives its release time, worst case execution time, worst case energy consumption and (absolute) deadline respectively. A job can be preempted and later resumed at any time and there is no time or energy loss associated with such preemption.

B. Energy

Our system uses an energy storage unit that has a nominal capacity, namely E, corresponding to a maximum energy (expressed in Joules or Watts-hour). The energy level has to remain between two boundaries E min and E max with E = E max -E min . If the storage is fully charged, and we continue to charge it, energy is wasted. In contrast, if the storage is fully discharged, no task can be executed.

In order to characterize the energy source, we define the WCCR (Worst Case Charging Rate), namely P r , which is a lower bound on the harvested source power output. P r is then the instantaneous charging rate that incorporates all losses caused by power conversion and charging process.

We assume that energy production times can overlap with the consumption times.

C. Definitions

• A schedule Γ for τ is said to be valid if the deadlines of all tasks of τ are met in Γ, starting with a storage fully charged. • A task set τ is said to be temporally-feasible if there exists a valid schedule for τ without considering its energy constraints. • A task set τ is said to be feasible if there exists a valid schedule for τ with considering its energy constraints. • A scheduling algorithm will be called optimal if it finds a valid schedule whenever one exists.

IV. BACKGROUND MATERIALS

The problem of scheduling periodic tasks on one processor with no energy constraint has been an active area of research for more than thirty years (see, e.g., [START_REF] Buttazzo | Hard Real-Time Computing Systems[END_REF]). In [START_REF] Dertouzos | Control Robotics: The Procedural Control of Physical Processes[END_REF], Dertouzos showed that Earliest Deadline First (EDF) is optimal among all preemptive scheduling algorithms. EDF schedules at each instant of time t, the ready task (i.e the task that may be processed and is not yet completed) whose deadline is closest to t. The EDF algorithm is typically preemptive, in the sense that, a newly arrived task can preempt the running task if its absolute deadline is shorter. This dynamic priority assignment allows EDF to exploit the full processor, reaching up to 100% of the available processing time.

In general, the implementation of EDF consists in executing tasks according to their urgency, as soon as possible with no inserted idle time. Such implementation is known as EDS (Earliest Deadline as Soon as possible). Nevertheless, in some applications, it can be preferable to postpone execution of periodic tasks, executing them by the so called EDL (Earliest Deadline as Late as possible) strategy, for example when some additional aperiodic tasks with unexpected arrival times require to be run as soon as possible [START_REF] Chetto | Some Results of the Earliest Deadline Scheduling Algorithm[END_REF].

V. FEASIBILITY ANALYSIS UNDER ENERGY

CONSTRAINTS

In order to develop a procedure for the feasibility assessment of a periodic task set with energy constraints, we give some definitions. Let us consider the periodic task set τ and the interval [t 1 , t 2 ).

• The processor demand of τ in [t 1 , t 2 ), is h(t 1 , t 2 ) = Di≤t2-t1 1 + t2-t1-Di Ti C i • The energy demand of τ in [t 1 , t 2 ), is g(t 1 , t 2 ) = Di≤t2-t1 1 + t2-t1-Di Ti E i
The processor demand (resp. the energy demand) is a measure of how much computation (resp. energy) is requested by all the jobs which have both their release times and their deadlines, in a given interval of time. It is clear that for a given time length and among all intervals, the initial one has the maximum fraction of processor and energy demanded by the jobs i.e. h(t 1 , t 2 ) ≤ h(0, t 2 -t 1 ) and g(t 1 , t 2 ) ≤ g(0, t 2 -t 1 ).

For simplicity, we respectively denote as h(t) and g(t) the processor demand and the energy demand of the task set τ in [0, t). So, h(t) = Di≤t 1 + t-Di Ti C i and g(t) = Di≤t 1 + t-Di Ti E i . Without energy constraint, the exact schedulability analysis is based on the processor demand criterion and is stated as follows [START_REF] Baruah | Preemptively Scheduling Hard Real-Time Sporadic Tasks on One Processor[END_REF]:

Theorem 1. A task set τ is temporally-feasible if and only if U p ≤ 1 and ∀t > 0, h(t) ≤ t.
This exact feasibility test is of pseudo-polynomial complexity since the points in which the test has to be performed correspond to deadlines within the hyperperiod T LCM . Suggestions for practical improvements in testing Theorem 1 have been given in [START_REF] Ripoll | Improvement in Feasibility Testing for Real-Time Tasks[END_REF] and [START_REF] Zhang | Schedulability Analysis for real-time systems with EDF scheduling[END_REF].

Here, we extend Theorem 1 to account for energy consumption:

Theorem 2. A task set τ is feasible if and only if

• τ is temporally-feasible,

• U e ≤ P r and ∀t > 0, g(t) ≤ E + P r t

VI. THE OPTIMAL SCHEDULING ALGORITHM

The intuition behind the scheduling algorithm is to run tasks according to the earliest deadline first rule. However, before authorizing a task to execute, the storage level must be sufficient to provide energy for all future occurring tasks, considering their timing and energy requirements and the replenishment rate of the storage unit. And if this condition is not verified, the processor has to be idle so that the storage unit recharges as much as possible and as long as the system will be able to meet all the deadlines i.e. the system will have available time to remain idle. Following the idea described above, we propose the EDeg (Earliest Deadline with energy guarantee) algorithm. To formally present the algorithm, we need to introduce two concepts:

• The slack time of the system at current time t, is the length of the longest interval starting at t during which the processor may be idle continuously while still satisfying all the timing constraints. • The slack energy of the system at current time t, is the maximum amount of energy that can be consumed from t continuously while still satisfying all the timing constraints. In the following description, t is the current time, E(t) is the residual capacity of the storage unit at time t i.e. the energy that is currently stored. Slack.energy(t) and Slack.time(t) are respectively the slack energy and the slack time at time t. PENDING is a boolean which equals true whenever there is at least one job in the ready list queue. We use the function wait() to put the processor to sleep and function execute() to put the processor to run the ready job with the earliest deadline.

The framework of the optimal scheduling algorithm is as follows:

Algorithm 1 Earliest Deadline with energy guarantee algorithm (EDeg) while (1) do while PENDING=true do while (E(t) > E min and Slack.energy(t) > 0) do execute() end while while (E(t) < E max and Slack.time(t) > 0) do wait() end while end while while PENDING=false do wait() end while end while

We notice that:

• EDeg degenerates to an EDS policy if E max = 0 and an EDL (Earliest Deadline as Late as possible) policy if E max = ∞. • We never run out of storage (that is, we never dispatch tasks when there is no energy); this is obvious from the algorithm that does not allow tasks to run after E min . • We start charging the storage unit when, either it is empty or there is no more sufficient energy to guarantee the feasible execution of all future occurring tasks i.e. the system has no more slack energy. • the charging process aims to charge at the maximum level provided there is sufficient slack time. • We only waste recharging power when there are no pending tasks and the storage unit is full. As a consequence, we can prove the following theorem. Theorem 3. Algorithm EDeg is optimal.

VII. PRACTICAL CONSIDERATIONS

The computations of Slack.energy(t) and Slack.time(t) are thus the keys to the operation of the EDeg algorithm. As shown in [START_REF] Silly | The EDL Server for Scheduling Periodic and Soft Ape-riodicTasks with Resource Constraints[END_REF], the slack time of a periodic task set at a given time instant can be obtained on-line by computing the dynamic EDL schedule, with complexity O(K.n). n is the number of periodic tasks, and K is equal to R/p , where R and p are respectively the longest deadline and the shortest period of current ready tasks. The slack energy at time t is computed only when there is at least one job, say J j which will be released after t and has a deadline d j that is less than or equal to that of the highest priority job, ready at t. For such job, we compute Slack.energy(J j ,t), given by E(t)+P r (d j -t)-A j where A j is the processor demand within [t, d j ). Slack.energy(J j ,t) clearly represents the amount of energy surplus in the storage that can be used from t until the start time of J j while still guaranteeing its timing and energy requirements. The slack energy of the system is determined by the minimum slack energy of all the jobs. The complexity for computing the slack energy is O(K.n) too.

A suggestion to improve the efficiency of the scheduler in terms of overhead is to compute statically a lower bound on the slack time and a lower bound on the slack energy and use them instead of exact values which are computed on-line. The effect will be only, first to stop charging earlier and second to stop executing tasks earlier. As a consequence, decreasing the processor overheads due to computations will cause increasing the number of tasks preemptions.

VIII. ILLUSTRATIVE EXAMPLE

Consider a task set τ that is composed of the tree following tasks: τ 1 (2, 16, 7, 20), τ 2 (2, 10, 4, 5) and τ 3 [START_REF] Allavena | Scheduling of Frame-based Embedded Systems with Rechargeable batteries[END_REF][START_REF] Jayaseelan | Estimating the Worst-Case Energy Consumption of Embedded Software[END_REF][START_REF] Zhang | Schedulability Analysis for real-time systems with EDF scheduling[END_REF][START_REF] Silly | The EDL Server for Scheduling Periodic and Soft Ape-riodicTasks with Resource Constraints[END_REF]. The storage capacity is E = 10 and we assume that E min = 0 and E max = E. The recharging power P r is constant and equal to 4. To simplify the illustration, we assume that tasks consume energy at constant rate. We note that the processor utilization and the energy utilization are respectively 0.6 and 3.4, consequently no more than 1 and 4. By scheduling the task set τ according to EDF on the first hyper-period i.e. from 0 to 20, we can verify that τ is temporally-feasible. The schedule which is produced by the EDeg scheduler for τ in the first hyper-period is described on (Figure 1). Let us explain how this schedule is constructed in the first steps.

At time 0, the storage is full. τ 2 is the highest priority task, executes until time 2 and consumes 10. At time 2, E 2 = 8. τ 1 is the highest priority task and the slack energy is undefined (no job released after 2 with deadline less than 4). τ 1 executes completely until time 4 and consumes 16. 8 units of energy are produced. At time 4, E 4 = 0. The processor has to remain idle as long as the storage has not refilled it (predicted at time 6.5) and the latest start time has not been attained (at time 6 which is computed using EDL). At time 6, E 6 = 8. τ 2 is the highest priority task, executes until time 8 and consumes 10. At time 8, E 8 = 6. τ 3 is the highest priority task, executes and completes exactly at time 9 that coincides with its deadline.

IX. CONCLUSION

We have presented the framework of a monoprocessor preemptive scheduling algorithm, namely EDeg, that is a variation of EDF able to cope with energy constraints. EDeg has been designed to schedule any set of time critical tasks, periodic or not, given any energy source profile with constant This paper specifically focussed on a system that receives energy at constant rate and has to run periodic tasks with non related computation and energy requirements.

Figure 1 .

 1 Figure 1. The EDeg schedule


Maryline Chetto
email: maryline.chetto@univ-nantes.fr

Christophe Plot
email: christophe.plot@univ-nantes.fr

Garcia Thibault

Conduite D'un

Maryline Silly-Chetto

*-Thibault Garcia-Fernandez
email: thibault.garcia-fernandez@univ-nantes.fr

Conduite d'un Robot Mobile Opto-guidé Par Logiciels Temps-Réel Open-Source Démonstrateur du projet RNTL Cléopatre

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Résumé :

Le travail présenté ici a été réalisé dans le cadre du projet Cléopatre1 , projet national de R&D dans le domaine des technologies logicielles dédiées aux applications temps-réel, terminé en juin 2005. Ce projet avait pour finalité la conception d'un système d'exploitation temps réel baptisé « système Cléopatre » à code source ouvert, gratuit et téléchargeable à partir d'un site public de façon à en faciliter la diffusion. Ce système d'exploitation temps réel a la particularité de se présenter sous forme d'un assemblage de composants sélectionnables par l'utilisateur. Ces derniers peuvent être définis comme des briques logicielles disponibles sur les étagères d'une bibliothèque et implémentant des mécanismes novateurs principalement issus de la recherche en ordonnancement temps réel.

Nous présentons le démonstrateur de ce projet, un AGV (Automated Guided Vehicle) conduit en temps-réel par l'O.S. Cléopatre. L'objectif était d'évaluer ses performances d'un point de vue temporel, le gain engendré par l'approche composant en termes d'empreinte mémoire et d'accessibilité mais aussi vérifier l'inter-opérabilité des composants logiciels développés. L'application mise en oeuvre consiste à conduire cet AGV opto-guidé muni de son informatique embarquée, en exécutant en temps-réel des ordres de mission émis par une liaison sans fil à partir d'une station de supervision.

Mots-clefs : temps-réel, chariot optoguidé, système d'exploitation, logiciel libre

Linux et le temps-réel

Depuis plusieurs années déjà, Linux conquiert un domaine où il n'était pas particulièrement attendu, celui des applications temps réel. Et si l'on retrouve ce système d'exploitation généraliste dans le domaine très spécifique de l'informatique temps réel, c'est qu'on lui reconnaît des qualités autres que celles reconnues dans l'environnement standard type PC grand public, à savoir : sa gratuité, l'ouverture de son code source, les nombreuses distributions proposées, l'aide rapide par la communauté Internet des développeurs… Linux possède en effet de nombreux autres atouts pour son utilisation dans le secteur des systèmes temps réel embarqués : son portage sur processeurs autres que 80x86 tels que PowerPC, ARM ou MIPS, une taille du noyau modeste compatible avec la taille des mémoires utilisées dans les système embarqués (< 500 Ko), un support pour le chargement dynamique de modules qui permet d'optimiser la taille du noyau, une migration rapide et en douceur pour un spécialiste Linux à Linux Temps Réel, réduisant ainsi les temps de formation et par voie de conséquences les coûts… A mi-chemin entre les développements maison effectués sur mesure en interne, et ceux qui se construisent autour de systèmes d'exploitation et de plates-formes propriétaires, Linux ouvre donc une nouvelle voie.

C'est donc dans cette nouvelle voie que nous avons inscrit la conception et le développement du système d'exploitation Cléopatre, extension temps réel de Linux.

Linux est à l'origine un système généraliste élaboré pour le temps partagé, et non pour le temps réel. Deux approches permettent d'octroyer à Linux des spécificités temps réel. Une première idée consiste à modifier directement le noyau en remplaçant son ordonnanceur natif par un ordonnanceur préemptif à priorité qui améliore son comportement. Ce type de solution convient bien aux applications dites temps réel à contraintes légères pour lesquelles la performance s'évalue en termes de temps de réponse moyen. Cependant, lorsque les contraintes temps réel sont strictes, un noyau entièrement dédié aux applications temps réel devient indispensable. La solution consiste alors à ajouter un noyau auxiliaire, permettant de relayer les processus non temps réel à un niveau de priorité le plus bas. Les promoteurs de cette technologie sont ceux qui considèrent que le noyau Linux ne sera jamais véritablement temps réel et lui ajoute des fonctionnalités dont certainement le plus fondamental est un ordonnanceur déterministe. Cette technologie est utilisée par RTLinux et son semblable européen, RTAI, depuis la fin des années 90.

Motivations du projet RNTL Cléopatre

Bien que RTAI et RTLinux soient capables de gérer des applications temps réel dites à contraintes strictes, ces deux versions intègrent des fonctionnalités très basiques en matière d'ordonnancement. Celles-ci se restreignent à l'utilisation de priorités fixes sans prise en compte des contraintes liées aux ressources critiques, ne gèrent pas les tâches apériodiques critiques et non critiques, ne prennent pas en considération les surcharges temporaires de traitement, ne disposent pas de stratégies de recouvrement en cas de faute, etc.

Et pourtant, les applications temps réel s'avèrent de plus en plus complexes et ne sont pas, soit à contraintes strictes, soit à contraintes légères : elles mettent en oeuvre des tâches dont les contraintes sont hétérogènes et leurs caractéristiques temporelles de plus en plus variées. Leur respect ne peut être garanti ni par un système temps réel classique (à priorité fixe calculée sur la période par exemple) comme Linux/RTAI ni par un système d'exploitation dit à temps partagé conventionnel comme Linux.

Les travaux de recherche menés ces dernières années ont d'ailleurs prouvé, par validation théorique des résultats, la nécessité de se tourner vers des ordonnanceurs adaptatifs et flexibles, à priorité dynamique (Earliest Deadline) pour gérer des tâches apériodiques, faire face à des situations de surcharge temporaire de traitement par la garantie d'une qualité de service minimum, mettre en oeuvre des tests d'admission en ligne, etc.

L'objectif du projet RNTL ( Réseau National des Technologies Logicielles) Cléopatre terminé en juin 2005 était donc de faire la preuve de l'intégrabilité de fonctionnalités novatrices dans un système d'exploitation ouvert tel que Linux et ce, sous forme de composants sélectionnables à la carte en fonction du profil de l'application [START_REF] Silly-Chetto | Enhancing Linux/RTAI with Open Source Software Components[END_REF][START_REF] Garcia-Fernandez | Composants logiciels enfouis pour les systèmes temps-réel embarqués[END_REF].

Voulant s'affranchir du développement complet d'un noyau temps réel juxtaposé à Linux et de son interface matérielle, il s'est naturellement fait jour que la meilleure solution était de concevoir Cléopatre comme un patch à une extension temps réel existante de Linux, qui se présenterait sous la forme d'une librairie de composants logiciels munie de son interface. S'inscrivant dans ce point de vue, l'ensemble des membres du consortium Cléopatre a ainsi pris l'option de considérer RTAI comme support de développement avec les principales motivations suivantes : projet communautaire, contributeurs majoritairement européens, excellente documentation, nombreuses architectures supportées, licence LGPL et non GPL, gestion du temps réel dur dans l'espace utilisateur… On peut alors considérer Cléopatre comme un patch de RTAI, lui-même patch de Linux.

Un O.S. temps-réel à la carte

Nous avons fourni sous forme de composants à code source ouvert, des fonctionnalités de niveau noyau innovantes en matière de tolérance aux fautes (mécanisme à échéance et calcul imprécis), de synchronisation (protocoles d'accès aux ressources critiques avec héritage de priorité et priorité plafond) et d'ordonnancement (ordonnancement à priorité dynamique, serveur de tâches apériodiques, tests d'admission en ligne de tâches critiques) ( voir Figure 1). Nous avons démontré l'applicabilité et l'interopérabilité des composants par des tests en simulation puis sur des applications réelles mises en oeuvre par les différents partenaires de notre consortium et en particulier sur une application de robotique mobile décrite ci-dessous.

Scheduling Synchronization Fault Tolerance

Aperiodic task servicing

OS Abstraction Layer : TCL Overload Management

Cléopatre library

A p p l i c a t i o n Figure 1. La librairie de services temps-réel

Cette gamme de composants se répartit sur plusieurs étagères de la bibliothèque et est suffisamment étendue pour toucher un panel le plus large possible de secteurs d'applications, allant des applications les plus critiques, en général à caractère fortement cyclique (industrie militaire, avionique) aux applications les moins critiques (multimédia, vidéo à la demande) en passant par des applications où cohabitent des contraintes à degré de criticité échelonnés (robotique mobile avec téléopération).

Nous avons doté le système Cléopatre de propriétés d'extensibilité qui lui permettent de s'adapter aux futurs besoins des industriels et aux nouvelles idées des chercheurs par le biais de développement de nouveaux composants interopérables. Les composants d'une même étagère ont la propriété de s'interchanger, ce qui laisse les utilisateurs libres de choisir le mécanisme le plus adapté à leurs besoins parmi plusieurs ou d'en tester de nouveaux sans modifier leurs applications.

Les développements de composants Cléopatre pour plusieurs configurations système et matérielles sont factorisés par une couche de contrôle des tâches (TCL) qui en fait abstraction ( voir Figure 2).

Ainsi les composants sont génériques et le système s'adapte à un nouvel environnement pour un investissement réduit. D'ailleurs une couche de contrôle des tâches a déjà été développée en quelques mois pour la version 3.0 de RTAI qui ne repose plus sur le patch RTHAL qui donne le contrôle du système Linux à un noyau temps réel, mais sur le patch ADEOS qui est un pipeline de systèmes d'exploitation.

R T A I L i n u x H a r d w a r e R T A I Tasks L i n u x processes

Interrupts

Hardware

Instrumentation du robot

La propulsion est réalisée à l'aide de deux moteurs de traction contrôlés par des variateurs de vitesse en mode RI (CM1 et CM2). Deux moteurs de direction (CM3 et CM4) dirigent les roues. Ces moteurs peuvent être bloqués pour offrir la possibilité d'utiliser le robot en mode holonome ou non. Son tapis roulant est actionné par un dernier moteur (MT) ( voir Figure 4).

Le robot mobile est pourvu de photo-résistances permettant de réaliser le suivi de la piste (SdP1 et SdP2), de capteurs de présence de bacs (PB1 et PB2), de capteurs infrarouges TOR détectant les catadioptres présents sur la piste (PA0 à PA2) et de capteurs de proximité détectant les obstacles (DIR1 à DIR4). Le robot mobile est contrôlé par PC industriel embarqué PC104 relié au matériel par une carte d'entrées/sorties PC104-AIO12-8 avec 8 entrées analogiques, 4 sorties analogiques, 24 entrées/sorties numériques et 3 compteurs/timers. Une mémoire compact flash de 32 Mo joue le rôle de disque dur. La mémoire compact flash contient le système Cléopatre et l'application qui contrôle le robot selon les ordres transmis par liaison radio.

Implémentation

Le logiciel d'application se décompose en trois tâches apériodiques dédiées à la réception de nouveaux ordres, à l'émission de messages de progression du robot, et à l'exécution des ordres. Cette dernière tâche coordonne d'autres tâches dédiées aux différents ordres que le robot mobile est susceptible d'exécuter : suivre la piste, tourner à gauche, tourner à droite, faire demi-tour, charger un bac, suivre une direction pour un aiguillage… Ces tâches agissent sur deux tâches de commande qui appliquent chacune une vitesse à une des roues du robot mobile ( voir Figure 5).

Par exemple, la tâche de suivi de piste est chargée de faire progresser le robot le long de la piste. Elle utilise les données fournies par un système matériel de suivi de piste connecté aux photorésistances (SdP1 et SdP2) qui déterminent si le robot se trouve à gauche, à droite ou au centre de la piste. Ces données sont appelées erreur. A partir de cette erreur, la tâche de suivi de piste calcule une correction d'erreur qu'elle transmet aux tâches de contrôle des roues pour rectifier la trajectoire du robot et éviter qu'il quitte la piste.

Deux stratégies de calcul de la correction d'erreur ont été envisagées afin de valider les mécanismes de tolérance aux fautes du système Cléopatre. Il s'agit de la correction proportionnelle (rapide mais peu précise) et de la correction proportionnelle intégrale (plus lente mais précise).

Toutefois, des mesures ont montré un écart temporel insuffisant entre les deux stratégies pour valider les composants de tolérance aux fautes du système Cléopatre.

Le robot possède également des capteurs de proximité permettant de détecter les obstacles. Ces capteurs génèrent une interruption dont la routine réveille la tâche de priorité maximale qui est chargée d'immobiliser le robot dans les plus brefs délais. Un système de retour vidéo a également été développé pour qu'un opérateur suive le déplacement du robot à l'aide de caméras embarquées à l'avant et à l'arrière du robot.

Conclusion

Les travaux menés sur cette plate-forme mobile ont permis d'évaluer le système Cléopatre et la plupart de ses composants logiciels. Une application robotique offre en effet la particularité de faire cohabiter des tâches périodiques tournant à des cadences élevées (asservissement) et des tâches événementielles déclenchées lorsque surviennent des événements extérieurs (informations capteurs, commande opérateur). Cette cohabitation de ces deux types de tâche a été une bonne validation pour les ordonnanceurs et les serveurs de tâches apériodiques et vérifier l'inter-opérabilité de ces services offerts sur des étagères différentes de la librairie.

L'O.S. Cléopatre et l'applicatif ont été installés sur 2 Mo de la mémoire compact flash. En effet, le chargement à la carte des composants logiciels système se caractérise par une très faible empreinte mémoire, critère de performance primordial pour les systèmes embarqués mais également critère économique.

Cléopatre a été développé en mettant l'accent sur l'amélioration de l'accessibilité de Linux temps réel. Pour cela, il met à disposition de nombreuses fonctionnalités qui simplifient le travail du programmeur et réduisent le temps de prise en main du système. Remarquons que ce travail d'intégration a été réalisé en moins de six mois par un stagiaire élève-ingénieur sans connaissance préalable de ce système d'exploitation. Des outils novateurs tel que l'arrêt d'urgence logiciel, les zones de non préemption, les signaux d'abandon des tâches, etc. sont autant d'outils d'aide au développement dont l'utilité a pu être démontrée par le biais de cette application.

Figure 2 . : Architecture logicielle 4 .

 24 Figure 2. : Architecture logicielle

Figure 3 .

 3 Figure 3. : La plate-forme mobile

Figure 4 .:

 4 Figure 4. : Capteurs du robot mobile

Figure 5 .

 5 Photorésistances

Projet financé par le Ministère de la Recherche, notification n° 01 K 0742


Audrey Marchand
email: audrey.marchand@univ-nantes.fr

Maryline Chetto
email: maryline.chetto@univ-nantes.fr

The need for supporting dynamic real-time environments where changes in workloads may occur requires a scheduling framework that explicitly addresses overload conditions, allows the system to achieve graceful degradation and supports a mechanism capable of determining the load to be shed from the system to handle the overload. In applications ranging from video reception to air-craft control, tasks enter periodically and have response time constraints, but missing a deadline is acceptable, provided most deadlines are met. Such tasks are said to be occasionally skippable and have an assigned skip parameter. We look at the problem of uniprocessor scheduling of skippable periodic tasks which consists in maximizing the robustness of the system defined as the global completion ratio. In this paper, we propose a novel scheduling Skip-over algorithm, called RLP/T, a variant of Earliest-Deadline First which adjusts the system workload such that tasks adhere to their timing and skip constraints and guarantees the best robustness.

Dynamic Scheduling of Periodic Skippable Tasks in an Overloaded Real-Time System 1. Introduction

While it is imperative that all time constraints are met in hard real-time systems, firm or soft real-time systems do not have as stringent timeliness requirements, allowing for some degree of tardiness (soft) or miss ratio (firm). A significant body of research within the soft and firm realtime area has focused on minimizing tardiness and/or miss ratio, but without quantifying acceptable levels. In this paper, we focus on scheduling firm periodic tasks which have additional requirements specifying the minimum acceptable completion ratios that should be met in order to maintain system correctness. In a hard real-time system all hard deadline tasks must meet their deadlines to maintain system correctness; otherwise, the system has failed. In contrast, a deadline is considered to be soft if it can be missed occasionally (or not by much), and hence, a task missing a single soft deadline is not considered as a failure. In a soft real-time system correctness is determined by the degree to which timeliness has been enforced for the entire task set. However, completion of a tardy firm deadline task is not meaningful, since late delivery of the result is considered to be of no value to the real-time system. Although firm deadlines can occasionally be missed, there is normally an upper limit on the number of misses within a defined interval. The hard real-time paradigm is well established and it has received considerable attention by researchers and practitioners within academia and industry. Numerous techniques and algorithms, especially in the area of scheduling, have been developed. Most scheduling algorithms developed for soft and firm real-time systems lack the ability to enforce constraints on the upper limit of misses. Without such enforcement, unbounded consecutive time constraint violations may occur. Realistically, if consecutive instances of a task fail to complete before their deadlines, then the system will eventually suffer from a failure. This indicates that there are additional constraints expressing the minimum degree of timeliness for firm real-time tasks, that must be enforced. Unfortunately, little work has been done on scheduling of firm tasks with such constraints, and this is the subject of our paper. The most significant firm real-time constraint is (m, k)-firm constraint and consists of guaranteeing m out of k consecutive task executions or message transmissions. New strategies to schedule systems with (m, k)-firm constraints or other similar constraints (e.g. window-constrained [START_REF] West | Analysis of a windowconstrained scheduler for real-time and best-effort packet streams[END_REF] and skipover [START_REF] Koren | Skip-over algorithms and complexity for overloaded systems that allow skips[END_REF]) have been defined. Koren and Shasha identified a model, called skip-over, for overloaded systems allowing skips. In this paper, we focus on dynamic scheduling of periodic tasks with firm deadlines, where each firm task has an additional constraint specifying the acceptable level of timeliness, the skip factor. If a task has a skip factor s, it will have at most one invocation skipped out of s. We have presented, in an earlier paper, a scheduling framework [START_REF] Marchand | Rlp: Enhanced qos support for real-time applications[END_REF], RLP (Red Tasks as Late as possible) for handling dynamic workloads consisting of periodic firm deadline tasks. In this paper, we introduce a variation of RLP, called RLP/T. We add a novel admission control mechanism to RLP, which enables the algorithm to enforce robustness constraints by performing a dynamic test to accept or not a skippable task for execution, so as to lost minimum processing time. The admission controller tests for schedulability of a new instance upon its arrival. It acts as a task filter guaranteeing that the scheduler is always able to find a feasible schedule. Our performance evaluation shows that RLP/T outperforms the basic skip-over algorithms, RTO (Red Tasks Only) and BWP (Blue When Possible) [START_REF] Koren | Skip-over algorithms and complexity for overloaded systems that allow skips[END_REF]. The paper is structured as follows. In section 2 we describe the Skip-Over model and recall some background materials in section 3. In section 4 and 5 we respectively describe in detail the algorithm RLP and its extension RLP/T. In section 6 we present results of a simulation study. Implementation and validation issues are considered in section 7. At the end of the paper, we make a short summary and directions for future work in section 8.

The skip-over model

Terminology and assumptions

In what follows, we consider the problem of scheduling periodic tasks which allow occasional deadline violations (i.e. skippable periodic tasks), on a uniprocessor system. The system under study has a workload consisting of tasks that can be preempted at any time and they do not have precedence constraints. A task T i is characterized by a worst-case computation time C i , a period P i , a relative deadline equal to its period, and a skip parameter s i . This parameter represents the tolerance of this task to miss deadlines. That means that the distance between two consecutive skips must be at least s i periods. When s i equals to infinity, no skips are allowed and T i is a hard periodic task.

Every task T i is divided into instances where each instance occurs during a single period of the task. Every instance of a task is either red or blue [START_REF] Koren | Skip-over algorithms and complexity for overloaded systems that allow skips[END_REF]. A red task instance must complete before its deadline whereas a blue task instance can be aborted at any time. However, if a blue instance completes successfully, the next task instance is still blue.

RTO and BWP algorithms

Two scheduling algorithms were introduced about ten years ago. The first one proposed by Koren and Shasha is the Red Tasks Only (RTO) algorithm. Red instances are scheduled as soon as possible according to Earliest Deadline First (EDF) algorithm [START_REF] Chetto | An adaptive scheduling algorithm for fault-tolerant real-time systems[END_REF], while blue ones are always rejected. The second algorithm studied is the Blue When Possible (BWP) algorithm which is an improvement of the first one. Indeed, BWP schedules blue instances whenever their execution does not prevent the red ones from completing within their deadlines. In other words, blue instances are served in background relatively to red instances.

Illustration

Hereafter is presented a scheduling example with two tasks T i (C i , P i , s i ) defined according to the Skip-Over model. Task T 1 is a hard real-time periodic task (s i = ∞) while task T 2 allows deadline skips (s i = 3). Tasks are scheduled as soon as possible according to their deadline. The system is overloaded (U p = n i=1

Ci Pi = 4 6 + 1 2 = 1.17), but we can see that tasks can be schedulable provided T 2 exactly skips one instance every 3.

Background material on Earliest Deadline

Despite of not being implemented yet in any commercial RTOS, dynamic scheduling policies and more particularly Earliest Deadline First algorithm (EDF) offer many advantages such that accomplishing a 100% processor utilization. Let us review the fundamental properties of Earliest Deadline First algorithm, stated in [START_REF] Chetto | Some results of the earliest deadline scheduling algorithm[END_REF] [START_REF] Koren | Skip-over algorithms and complexity for overloaded systems that allow skips[END_REF] which are the basic foundation of our approach for scheduling tasks in the skipover model.

Earliest Deadline as Soon as possible (EDS)

In general, implementation of EDF consists in executing tasks according to their urgency, as soon as possible with no inserted idle times. Such implementation is known as EDS (Earliest Deadline as Soon as possible). Nevertheless, in some applications, this implementation presents drawbacks, for example when soft aperiodic tasks need to be served with minimal response times. In that case, it is preferable to postpone the execution of periodic tasks, executing them by the so-called EDL (Earliest Deadline as Late as possible) strategy.

Earliest Deadline as Late as possible (EDL)

Such approach is known as Slack Stealing since it makes any spare processing time available as soon as possible.

In doing so, it effectively steals slack from the hard deadline periodic tasks. A means of determining the maximum amount of slack which may be stolen, without jeopardizing the hard timing constraints, is thus key to the operation of the EDL algorithm. In [START_REF] Chetto | Some results of the earliest deadline scheduling algorithm[END_REF], we described how the slack available at any current time can be found. This is done by mapping out the processor schedule produced by EDL for the periodic tasks from the current time up to the end of the current hyperperiod (the least common multiple of task periods). This schedule is constructed dynamically whenever necessary and is computed from a static EDL schedule, constructed off-line and memorized by means of the two following vectors:

• K, called static deadline vector. K represents the time instants from 0 to the end of the first hyperperiod, at which idle times occur and is constructed from the distinct deadlines of periodic tasks.

• D, called static idle time vector. D represents the lengths of the idle times which start at time instants of K.

The complexity for computing the EDL static schedule is O(N ) where N is the total number of periodic instances in the hyperperiod. Formula that give K and D can be found in [START_REF] Silly | The edl server for scheduling periodic and soft aperiodic tasks with resource constraints[END_REF].

The computation of the EDL static schedule is illustrated in Figure 2 with a set of two task T i (C i , P i , D i ). Note that in this example there are 7 potential idle times denoted by k i , i = 0, .., 6. Results of the computation of vectors K and D are summarized in At run-time, the dynamic EDL schedule is updated from the static one by taking into account the execution of current ready tasks. It is described by means of the two following vectors:

Table 1. K and D computation K 0 6 10 12 18 20 24 D 3 0 0 2 0 1 0

• K t , called dynamic deadline vector. K t represents the time instants posterior to t in the current hyperperiod, at which idle times occur.

• D t , called dynamic idle time vector. D t represents the lengths of the idle times that start at time instants given by K t .

The complexity for computing the EDL dynamic schedule is O(K.n) where n is the number of periodic tasks, and K is equal to ⌊ R p ⌋, where R and p are respectively the longest deadline and the shortest period of current ready tasks [START_REF] Silly | The edl server for scheduling periodic and soft aperiodic tasks with resource constraints[END_REF]. Formula that give K t and D t can be found in [START_REF] Silly | The edl server for scheduling periodic and soft aperiodic tasks with resource constraints[END_REF].

Assume now that, given the same task set as introduced before, we want to compute idle times from time instant t = 5 when tasks are processed by EDS from 0 to t. The resulting schedule is depicted in Figure 3. Then, from time t = 5 until the end of the hyperperiod, tasks are scheduled as late as possible according to EDL. Nonzero idle times resulting from the computation of vectors K t and D t (see Table 2) appear at times t = 5, t = 6, t = 12 and t = 20.

Chetto and Chetto in [START_REF] Chetto | Some results of the earliest deadline scheduling algorithm[END_REF] showed that the EDL schedule computation can be efficiently used for improving the service of aperiodic tasks. By definition, soft aperiodic requests must not compromise the guarantees given for periodic tasks and should be completed as soon as possible. No acceptance test is performed for soft aperiodic requests; they are served on a best-effort basis within the computed idle times, the goal being to minimize their response times. With respect to hard aperiodic tasks, every task is subject to an acceptance-rejection test upon arrival. Indeed, given their absolute deadline and their worst-case execution time, hard aperiodic tasks can easily be admitted or rejected on the basis of the knowledge of idle times localization.

In [START_REF] Chetto | An adaptive scheduling algorithm for fault-tolerant real-time systems[END_REF] the same authors presented how EDL can be used to generate fault-tolerant schedules. The authors assume that every task is composed of primary and alternate jobs as specified by the Deadline Mechanism model [START_REF] Campbell | Simulations of a fault-tolerant deadline mechanism[END_REF]. The main feature of their method lies in the ability of dynamically changing the schedule and accounting for runtime situations such as successes or failures of primaries.

In our approach, we propose to use the EDL scheduling algorithm with the Skip-Over task model ascertaining the fact that the Deadline Mechanism and the Skip-Over models present analogous features. In both cases, the objective is to manage overload situations. The Deadline Mechanism performs commutations to a degraded mode in which results of lower quality are produced, but still meeting all the deadlines. As regards the Skip-Over model, it also performs commutations to a degraded mode, processing results of constant quality, but allowing some results to be not produced at all. Blue task instances of the Skip-Over model can be compared to primary jobs of the Deadline Mechanism, whereas red task instances can be associated with alternate jobs.

The RLP algorithm

Principles

The objective of RLP algorithm [START_REF] Marchand | Rlp: Enhanced qos support for real-time applications[END_REF] is to bring forward the execution of blue task instances so as to minimize the ratio of aborted blue instances, thus enhancing the robustness (i.e., the total number of task completions) of periodic tasks. From this perspective, RLP scheduling algorithm, which is a dynamic scheduling algorithm, is specified by the following behaviour:

• if there are no blue task instances in the system, red task instances are scheduled as soon as possible according to the EDF (Earliest Deadline First) algorithm.

• if blue task instances are present in the system, they are scheduled as soon as possible according to the EDF algorithm (note that it could be according to any other heuristic), while red task instances are processed as late as possible according to the EDL algorithm. Deadline ties are always broken in favor of the task with the earliest release time.

Applying EDL to Red instances

The main idea of this approach is to take advantage of the slack of red periodic task instances. Determination of the latest start time for every red instance of the periodic task set requires preliminary construction of the schedule as described previously and taking skips into account [START_REF] Marchand | Qos scheduling components based on firm real-time requirements[END_REF][START_REF] Marchand | Dynamic real-time scheduling of firm periodic tasks with hard and soft aperiodic tasks[END_REF]. In the EDL schedule established at current time t, we assume that the instance following immediately a blue instance which is part of the current periodic instance set at time t, is red. Indeed, none of the blue task instances is guaranteed to complete within its deadline. Moreover, in [START_REF] Silly | The edl server for scheduling periodic and soft aperiodic tasks with resource constraints[END_REF] it was proved that the online computation of the slack time is required only at time instants corresponding to the arrival of an instance while no other is already present on the machine. In our case, the EDL sequence is constructed not only when a blue task is released (and no other was already present) but also after a blue task completion if blue tasks remain in the system (the next task instance of the completed blue task has then to be considered as a blue one). Note that blue tasks are executed in the idle times computed by EDL and are of same importance beside red tasks (contrary to BWP which always assigns higher priority to red tasks).

Illustrative example

To illustrate RLP, let us consider a set of five periodic tasks T = {T 1 , T 2 , T 3 , T 4 , T 5 } whose parameters are described in Table 3. We assume that all the tasks have the same skip parameter s i = 2. We note that the processor utilization factor for this task set is equal to 1.15 and consequently some instances will necessarily miss their deadlines.

Table 3. Task parameters

T i T 1 T 2 T 3 T 4 T 5 C i 3 4 1 7 2 P i 30 20 15 12 10
It can be observed that, thanks to RLP scheduling, the number of violations of deadline relative to blue task instances equals three. They occur at time instants t = 40 (task T 5 ), and t = 60 (tasks T 4 and T 5 ). Until time t = 10, red task instances run as soon as possible. From time t = 10 to the end of the hyperperiod, red task instances do execute as late as possible in the presence of blue task instances, thus enhancing the robustness of periodic tasks.

The RLP/T algorithm

Principles

The main disadvantage of RLP lies in that this scheduler attempts to process as soon as possible blue instances at the risk of not completing them before their deadlines due to possible overload. Such strategy then generates wasted processing times due incomplete execution of tasks and does not provide the best degradation during overload periods. Consequently, we propose to handle overload by performing admission control before deciding to execute a ready blue instance. The so-called RLP/T (Red Tasks as Late as Possible with blue acceptance Test) then leads to maximize the robustness. Considering the worst-case execution time of each occurring blue instance we can ensure that the set of admitted blue instances is feasibly schedulable. And as soon as a blue instance is admitted, the next task instance of the completed blue instance which was necessarily red is considered as a blue one. A blue instance is normally rejected once it is determined that it cannot be admitted given the current workload composed of red instances and already admitted blue instances.

The admission test

The acceptance test of blue tasks within a system involving Skip-Over tasks presented below in Theorem 1, is based on results established by Silly and al. [START_REF] Silly | An optimal algorithm for guranteeing sporadic tasks in hard real-time systems[END_REF] for the acceptance of sporadic requests occurring in a system consisting of basic periodic tasks (i.e., without skips).

THEOREM 1 Task B is accepted if and only if, for every task

B i ∈ B(τ ) ∪ {B} such that d i ≥ d, we have δ i (τ ) ≥ 0, with δ i (τ ) defined as: δ i (τ ) = Ω EDL T (τ ) (τ, d i ) - i j=1 c j (τ ) (1)
B(τ ) denotes the blue task set supported by the machine at time τ . δ i (τ ) is called slack of task B i at time τ and represents the maximum units of time during which the task could not be served by the processor without missing its deadline. Ω EDL T (τ ) (τ, d i ) denotes the total units of time that the processor is idle in the time interval [τ, d i ]. The total computation time required by blue tasks within [τ, d i ] is given by i j=1 c j (τ ). Hence, a blue task occurring at time τ can be accepted provided that all the slacks (including the ocurring task's one) of the blue tasks having a deadline greater than or equal to the occurring task, which are computed at τ , remain greater than or equal to zero.

Example

RLP/T scheduling is illustrated in Figure 5 with the periodic task set T defined in Table 3. It is easy to see that RLP/T improves on RLP. Only two violations of deadline relative to blue task instances are observed: at time instants t = 40 (task T 5 ) and t = 60 (task T 4 ). The acceptance test contributes to compensate for the time wasted in starting the execution of blue tasks which are not able to complete within their deadline. As we can observe, in the RLP case (see Figure 4), T 4 blue instance released at time t = 48 is aborted at time t = 60 (2 units of time were indeed wasted). Note that the rejection of this blue task instance, performed with RLP/T, contributes to save time used for the successful completion of T 5 blue instance released at time t = 50. 6. Performance evaluation

Simulation details

We report part of a performance analysis which consists of three simulation experiments designed to evaluate RLP/T with respect to RTO, BWP and RLP. In the first experiment, we measure the robustness, in the second one, the wasted time ratio (i.e the percentage of unuseful processing time) and in the third one, the percentage of processor idle time. The study is done by varying the periodic task load U p .

The simulator generates 50 periodic task sets. Each one contains 10 tasks with a least common multiple equal to 3360. Tasks are defined with uniform skip factor s i . The worst-case computation times depend on the setting of the periodic load U p . Deadlines are equal to the periods and greater than or equal to the computation times. Simulations have been processed over 10 hyperperiods.

Experiment 1

Simulation results reported in Figure 6 are carried out for a skip parameter s i equal to 2, varying the periodic load and measuring the robustness given by the percentage of periodic task instances that complete successfully. We report here the results of 2 simulation studies where tasks have an actual computation time (ACET) equal to 100% and 75% of the worst-case computation time (WCET) respectively. Let us recall that in practice, tasks have variable actual computation times assumed to be less than an estimated worst-case computation time. The assumption that a task will consume its WCET in all the activations does not have to be necessarily true, which implies that the real utilization of the CPU is less than the estimated in the schedulability test. On one hand, we observe that, for any processor workload, BWP and RLP outperform RTO for which the robust-ness is constant and minimal. For U p ≤ 1, the processor is underloaded, and both BWP and RLP success in completing all blue tasks instances which are respectively executed after and before red task instances. In overload situations, RLP and BWP give quite the same performances. However, compared with RLP, RLP/T provides a significant performance improvement.

On the other hand we can see that, for an identical periodic load, the success ratio of tasks observed for BWP, RLP et RLP/T is higher when the task execution time is less than its worst-case execution time. This is due to the fact that the amount of time (WCET-ACET) that is not used by each instance and which is in fact additional CPU time, is used for completing a greater number of task instances.

Moreover, note that for low overloads and ACET=0.75*WCET, BWP and RLP outperform RLP/T. This is due to the fact that the admission test performed by RLP/T is based upon the assumption that tasks execute according to their WCET, the value of ACET being not known a priori. Consequently, RLP/T will necessarily reject tasks that after all could have been accepted on the basis of their ACET. This is exactly what we can observe for the periodic load equal to 130%, RLP/T temporarily offers lower performances than BWP and RLP. Note that this phenomenon is not observable any more once the skip parameters are higher (e.g. s i = 6).

Finally, other tests not reported here show that, higher is the skip parameter more significant is the advantage of RLP/T over the other algorithms.

Experiment 2

It seemed wise to perform measurements about the CPU time wasted in incomplete executions of blue tasks. Simulation results for s i = 2 and s i = 6 are depicted in Figure 7.

Wasted CPU time is equal to zero for RTO since the algorithm schedules only red tasks. For RLP/T, the wasted CPU time is also equal to zero, whatever is the periodic load. This has been achieved thanks to the admission test implementation which prevents the abortion of blue tasks. A blue task is accepted if and only if it will be able to complete before its deadline.

With respect to BWP and RLP, the wasted CPU time is always positive once the system is overloaded (U p > 1). For U p = 115% and s i = 2, BWP et RLP involve the greatest amount of wasted CPU time, namely 24% et 26% respectively. Beyond that load, BWP and RLP curves present a decline. This is due to the fact that when the system is highly overloaded, it means that there are more red tasks to execute, hence less available CPU time for the execution of blue tasks. In addition, results not reported here show that the wasted CPU time is all the less significant as the skip parameters are higher.

Experiment 3

Finally, we made a performance comparison on the basis of another criterion : the CPU idle time ratio (i.e. the ratio of time during which the processor is not processing any task). This measure represents the system ability to face a dynamic surplus of processing (e.g. the arrival of an aperiodic task). Simulation results for s i = 2 et s i = 6 are presented in Figure 8.

First, let us remark that the CPU idle time ratio under RTO is the biggest one. This one declines in a linear fashion according to the periodic load U p applied to the system. In the case s i = 2, it varies from 55% for U p = 90%, to 10% for U p = 180%. Note the singular points of the curves s i = 2 et s i = 6: when U p = 100%, idle time ratios are respectively equal to 1 2 = 50% and 1 6 = 16.7%, thus corresponding exactly to the allowed skip ratios.

As regards BWP, RLP and RLP/T, idle time ratios are identical when the system is underloaded (U p < 100%). They become positive (idle time = 10% for U p = 90%) and decline in a linear fashion until reaching a zero value for U p = 100%. However, when the system is overloaded (U p > 100%), results differ. RLP doesn't involve CPU idle time whatever are the skip parameters. We observe that BWP involves a low idle time ratio only for low skip ratios. As regards RLP/T, it seems the most performant keeping a non neglecting idle time ratio when the system is lightly overloaded. Indeed, the idle time ratio under RLP/T for s i = 2 and U p = 115% is equal to 9%. Morever, even when the system is highly overloaded, RLP/T presents an idle time ratio which is low, certainly, but always positive.

As a matter af fact, all the experiments show that RLP/T seems the most suitable for facing transient overloads.

Implementation and validation issues

Integration in a Linux based operating system

There are two approaches to provide real-time performance in a Linux system: 1. Improving the Linux kernel preemption. 2. Adding a new software layer beneath Linux kernel with full control of interrupts and processor key features. This second approach is the one used by RTAI [START_REF] Mantegazza | Diapm. rtai programming guide 1[END_REF]. RTAI is the acronym of Real Time Application Interface. It was first started at the Dipartimento di Ingeneria Aerospaziale, Politecnico di Milano by Professor Paolo Mantegazza. RTAI started as a variant of RTLinux in 1999. Recently, RTAI developers have replaced the underlying hardware control RTHAL, based on the RTLinux original code and patented by Victor Yodaiken [START_REF] Yodaiken | The rtlinux approach to real-time[END_REF], with a new technology called ADEOS "Adaptive Domain Environment for Operating Systems" [START_REF] Yaghmour | Adaptive domain environment for operating systems[END_REF]. The basic structure of RTAI is the same than RTLinux. A new software layer is beneath Linux kernel with full control of interrupts and processor key features. RTAI scheduler treats the Linux operating system kernel as the idle task. Linux only executes when there are no real time tasks to run, and the real time kernel is inactive. Linux processes can never block interrupts or prevent themselves from being preempted. In this way, it is possible to have a complete general purpose operating system running on top of a small predictable RTOS. RTAI provides an execution environment "below" the Linux kernel. One consequence of this is that real-time tasks can not use Linux services because deadlock or system inconsistencies may happen. To overcome this problem, a FIFObased mechanism can be used to communicate threads in both layers.

An optional tracer module (Linux Trace Toolkit) can be included in the system. The tracer will register all the relevant system events and user-defined ones. LTT provides developers with all of the information necessary to reconstruct a system's behavior over a certain period of time and find logical and temporal bugs of the system or the application. Linux and RTAI both lack some important facilities needed in real-time systems.

The CLEOPATRE framework

CLEOPATRE, that stands for Open Components on Shelves for Embedded Real-time Applications, is a french national project, based on Open Source, which aims to provide an integrated execution environment for embedded real-time applications with flexible and portable components. So, it was mandatory to design the components taking as starting point a given RTOS. Without a basic infrastructure, it was not possible to develop new functionalities. RTAI was adopted for this project because we wanted the CLEOPATRE components to be distributed under the LGPL license which is also the one used in the RTAI project.

The CLEOPATRE library offers selectable COTS (Commercial-Off-The-Shelf) components dedicated to dynamic scheduling, aperiodic task service, resource control access, fault-tolerance and now, QoS scheduling (see Figure 9). RTO, BWP, RLP and RLP/T algorithms have been put into an additional shelf called Quality of Service. The QoS services are available as independent software components. This enables developers to build their own applicationspecific operating system.

Tests and validation criteria

To validate the correct implementation of this component two types of tests have been developed:

• Conformance tests. These tests have checked the correct behavior of the API.

• Overhead tests. These tests have validated the following criteria (for a Pentium III 400 MHz): overhead<400 microseconds incurred with RLP/T and overhead<100 microseconds incurred with RLP, for a set of 20 tasks whose execution was simulated during 34 seconds.

Details of implementation and tests can be found in [7].

Conclusions and Future Work

It is generally accepted that occasionally missing some firm deadlines is acceptable and is not considered as a fail-ure. Hence, during transient overloads, some of the noncritical tasks can be dropped without jeopardizing system correctness. Most research in the area of scheduling firm tasks assume that there is no requirement on the minimum number of tasks that must successfully complete. In this paper, we have focused on scheduling firm periodic tasks which may skip occasionnaly. In other words, system correctness is maintained if, for all tasks, the scheduler enforces the skip factor while maximizing the robustness (i.e. the task completion ratio). We have suggested an overload scheduling algorithm, RLP, for a periodic workload that complies to the Skip-Over model and we have presented a variant of RLP, called RLP/T based on an admission control mechanism. Tasks having better chances to successfully complete with RLP/T, robustness of the system i.e the completion ratio is increased. We have evaluated RLP/T by conducting a simulation-based performance analysis. The results show that the performance of firm tasks gracefully degrades as the load increases. We have presented CLEOPA-TRE, a library of free software components for the design of a high variety of embedded real-time systems to cover several classes of applications. Overload scheduling strategies including RLP and RLP/T are provided by one shelf of the library and are the key features needed to provide a powerful and usable RTOS, that permits to manage overload conditions for firm real-time systems. We intend to present, in future papers, the feasability of using the RLP/T algorithm for scheduling skippable periodic tasks in presence of soft and hard aperiodic tasks under resource access constraints.

Figure 2 .

 2 Figure 2. EDL computation of static idle times

Figure 3 .

 3 Figure 3. EDL computation of dynamic idle times at time t = 5

Figure 4 .

 4 Figure 4. A RLP schedule (si = 2)

Figure 5 .

 5 Figure 5. A RLP/T schedule (si = 2)

Figure 6 .

 6 Figure 6. Robustness for ACET=WCET and ACET=0.75*WCET

Figure 7 .

 7 Figure 7. Wasted CPU time for high (si = 2) and low (si = 6) skips

Figure 8 .

 8 Figure 8. CPU idle time for high (si = 2) and low (si = 6) skips

Figure 9 .

 9 Figure 9. The CLEOPATRE framework

Table 1 .

 1

	6 6 0 0	6 6	6 10	6 12	6 18	6 20	6 24	6 -30 6 -30
	k0	k1	k2 k3	k4 k5	k6	-

T 1 (3, 10, 10) T 2 (3, 6, 6) f EDL : processing of periodic tasks according to EDL : idle time 6 : release time

Table 2 .

 2 K and D computation K

	t 5 6 10 12 18 20 24
	D t 1 2 0	2	0	1	0


Maryline Chetto

Results on the slack of a periodic task set

Keywords: real time systems, scheduling, periodic tasks, slack, earliest deadline

Introduction

In many real-time applications, the computer is required to execute preemptable periodic tasks (e.g sensory processing) with strict deadlines.

A periodic task set can be denoted as follows: T = {T i (C i , R i , P i ), i = 1 to n}.

In this characterization, every task T i makes its initial request at time 0 and its subsequent requests at times kP i , k = 1, 2, ... The execution time required for each request of T i is C i time units and a deadline for T i occurs R i units after each request by which task T i must have completed its execution. We assume that 0 < C i ≤ R i ≤ P i for each 1 ≤ i ≤ n. A schedule Γ for T is said to be valid if the deadlines of all tasks of T are met in Γ. A task set is said to be feasible on one processor if there exists a valid schedule for T on one processor. A scheduling algorithm is said to be optimal if it produces a valid schedule for every task set which is feasible.

Preprint submitted to Elsevier

The problem of scheduling periodic tasks on one processor has been an active area of research (see, e.g., [START_REF] Buttazzo | Hard real-time computing systems[END_REF]). Liu and Layland have shown that ED is optimal [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. ED schedules at each instant of time t, the ready task (i.e the task that may be processed and is not yet completed) whose deadline is closest to t. Deciding if a task set T is feasible requires to construct the ED schedule and to see if the deadlines of all the requests are met from 0 to P where P (called the hyperperiod) is the least common multiple of P 1 , P 2 , . . . , P n since the processor does exactly the same thing at time t (t ≥ 0) that it does at times t + kP (k = 2, 3, . . .) [START_REF] Leung | A note on preemptive scheduling of periodic real-time tasks[END_REF]. We define the slack of T at current time t, denoted by δ(t), as the maximum time for defering the execution of the periodic requests from t without comprimising the validity of the ED schedule.

Computation at run time of the slack can be used to authorize or forbid the execution of a nonpreemptable task that requires to be run upon arrival from start to completion without interruption (e.g. interrupt handling or exception handling).

At this point, two fundamental questions arise:

(1) how to determine the slack at run time?

(2) are there lower bounds to the slack? 2 Background materials Two versions of ED, namely EDS and EDL are proposed by the author [START_REF] Chetto | Some Results of the Earliest Deadline Scheduling Algorithm[END_REF].

Under EDS, the ready tasks are processed as soon as possible, whereas under EDL they are processed as late as possible. Let S be a sporadic task set defined as follows: S = {S i (r i , C i , d i ), i = 1 to m}. In this characterization, task S i becomes ready at time r i , requires C i units of time and a deadline occurs at d i .

the total processor idle time available in [t 1 , t 2 ] when S is scheduled according to algorithm X. We now recall fundamental properties of EDS and EDL.

Theorem 1 For any instant t such that t ≤ D,

Ω EDS S (0, t) ≤ Ω X S (0, t) ≤ Ω EDL S (0, t) (1)
Proof: See [START_REF] Chetto | Some Results of the Earliest Deadline Scheduling Algorithm[END_REF] Theorem 1 says that applying EDS (respectively EDL) to a task set S guarantees the minimum (respectively maximum) available idle time within any time interval [0, t], 0 ≤ t ≤ D. Given that at current time t, the set of periodic requests available from t up to the end of the current hyperperiod behaves like a sporadic task set, Theorem 1 gives us theoretical basis of an algorithm for computing the slack. This is done by mapping out the EDL schedule which can be represented by means of two arrays. The first, K = (k 0 , k 1 , ...k p ), represents the times at which idle times occur, necessarily after the deadline of a periodic request. The second, D = (∆ 0 , ∆ 1 , ...∆ p ) represents the lengths of these idle times. Details of computation are given in [START_REF] Silly-Chetto | The EDL server for scheduling periodic and soft aperiodic tasks with resource constraints[END_REF].

The complexity of the algorithm is O(K.n) where K is equal to R/p , where R and p are respectively the longest deadline and the shortest period of current ready tasks. So, it may vary from O(n) to O(N) where N is the number of distinct periodic requests that occur in the hyperperiod. As the overhead can be very large, we are interested in providing properties on the variation in slack over time so as to avoid unnecessary on-line computations of the exact value.

3

First, let compute the length of the initial slack, δ(0), obtained by applying EDL to T at time 0. Consequently, δ(0) = ∆ 0 . Let x j = P j -R j for j=1 to n.

Proposition 1 ∆ 0 = min 0≤i≤p k i - n j=1 k i + x j P j C j (2)
Proof: Consider the schedule produced by EDL for T from 0 to P. Let k be the first instant between 0 and P such that there is no idle time within [0 + ∆ 0 , k] and all the tasks with a deadline greater than k are entirely processed within [k, P]. It follows that ∆ 0 is equal to the length of the time interval [0, k] minus the total quantity of processor time assigned to the requests with a deadline less than or equal to k. All the requests of every task T j whose ready time is greater than k+x j must then be rejected. It comes that ∆

0 = k-n j=1 k+x j P j C j
Let t be any time instant in K and α(t) = t -n j=1 t+x j P j C j . Let us prove that ∀t = k, α(t) ≥ ∆ 0 .

Case 1: t < k. From definition of k, we know that there exist some requests with a deadline posterior to t which are processed within [0, t]. Let Q(t) be the processor time reserved to these tasks. It comes that ∆ 0 = α(t) -Q(t) and consequently ∆ 0 < α(t).

Case 2: t > k. There may exist some idle time within [0 + ∆ 0 , t] and there may exist some requests with a deadline posterior to t which are processed within

[0 + ∆ 0 , t]. Then, ∆ 0 = α(t) -Q(t) -ϕ(t)
where ϕ(t) denotes the total idle time within [0 + ∆ 0 , t]. Consequently, ∆ 0 < α(t). Finally, it comes that ∆ 0 = min{α(t); t ∈ K} which corresponds to (2). 2

We show first a lemma which is used later to a derive lower bound to the slack at any time.

Lemma 1 For any released time e that concides with the end of an idle time interval, δ(e) ≥ ∆ 0 Proof: At time e, all the available tasks released before e have been processed.

Consider the set of requests available from time e to time P and form the associated set of sporadic tasks. Let S be this set and consider time e as a new time zero. From theorem 1, applying EDL to S from e will produce a schedule where the total idle time that follows e is maximized and corresponds to the slack, δ(e) . Now, we show that ∆ 0 provides a lower bound to the length of this idle time. For this purpose, let t be the first deadline after e such that t is followed by an idle time interval and the processor is fully utilized between e + δ(e) and t. Assume that time t coincides with the deadline of a request, for every task in T . In particular, t coincides with the deadline of the request that is released at time e. Let T l be this task. Then, ∃k, k ∈ N; e = kP l and t = k P l -x l . This assumption takes care of the worst possible case in the sense that the processor is required to provide maximum service in the time interval

[kP l , k P l -x l ]. Let ζ = (k -k)P l -x l .It comes that δ(e) ≥ ζ -n j=1 ζ+x j P j C i .
Since ζ ∈ K, proposition 1 enables us to conclude that δ(e) ≥ ∆ 0 . 2 Theorem 2 For any time t, δ(t) ≥ ∆ 0 Proof: Without loss of generality,, we assume that t ∈ {0, 1, 2, ..., P} since the schedule is periodic, and consequently δ(t) = δ(t + kP), k = 1, 2, . . . The theorem is proved by induction on the units of time t. The basis of induction corresponds to t = 0. To carry out the induction step, we assume that the theorem is true at t i.e δ(t) ≥ ∆ 0 and prove that δ(t + 1) ≥ δ 0 . Introduce Γ(t) to be the schedule produced by EDS from 0 to t and by EDL from t to P on T . δ(t) is then given by the length of the idle time that follows time t in Γ(t). Now, consider the schedule Γ(t + 1). We examine three cases.

Case 1: The processor is processing a task T with a current deadline d in [t, t + 1] and there is no task released after t with a deadline anterior to d. As tasks are scheduled by EDS, T has the earliest deadline among the ready tasks at t. This implies that this task is the first one to be scheduled after t in Γ(t), according to EDL. It follows that Γ(t + 1) is obtained from Γ(t) by a permutation of the quantum of idle time between t and t + 1 and the quantum of processor time for T between t + δ(t) and t + δ(t) + 1.

Then, δ(t) = δ(t + 1) and consequently δ(t + 1) ≥ ∆ 0 .

Case 2: The processor is processing a task T with a current deadline d and there is at least one task released after t with a current deadline anterior to d. Let e i and d i be the release time and the deadline of the first request after t that verifies e i > t and d i ≤ d.We have to examine two subcases: Subcase 1: T is not scheduled before time d i in Γ(t + 1). Consequently, T is not scheduled within [e i , d i ] in Γ(e i ). As there is no ready task with a deadline less than d between t + 1 and e i , this means that there is no task scheduled by EDL within [t + 1, e i ] and so, δ(t + 1) = δ(e i ) + (e i -(t + 1)). Since δ(e i ) ≥ ∆ 0 from Lemma 1, then δ(t + 1) ≥ ∆ 0 . Subcase 2: T is partially scheduled before time d i in Γ(t + 1). As T is scheduled after T i in [e i , d i ], Γ(t + 1) is obtained from Γ(t) by a permutation of the quantum of idle time between t and t + 1 and the quantum of processor time for T i between t + δ(t) and t + δ(t) + 1.

Case 3: The processor is not occupied in [t, t + 1]. The processor will remain inactive until the next release time. Let e i be this time instant. It comes that δ(t + 1) = e i -t + δ(e i ). Since δ(e i ) ≥ ∆ 0 from Lemma 1, then

δ(t + 1) ≥ ∆ 0 . 2
From demonstration of theorem 2, we conclude that δ(t) has local maximum at the beginning of every idle time interval, is linear decreasing within any idle time interval,and non increasing in any busy time interval. Besides, δ(t) is never less than ∆ 0 .

Slack with additional tasks

Consider once again the periodic task set T defined previously. And assume that sporadic tasks have been accepted for execution between 0 and t without comprimising the validity of the resulting ED schedule. We have now established the two following theorems: Theorem 3 For any time t such that δ(t) ≥ ∆ 0 and for any length q such that no additional task has been accepted within [t, t + q], then δ(t + q) ≥ ∆ 0 .

Proof: We prove that the existence of a time instant t such that δ(t) = ∆ 0 implies δ(t + 1) ≥ ∆ 0 . Let Γ(t + 1) be defined as in the proof of theorem 2 and examine the two possible situations: Case 1: the processor is idle within [t, t + 1] in Γ(t + 1). So, there is no ready task to be processed at time t. Time interval [t, t + 1] is then included in an idle time interval and schedule Γ(t + 1) from t + 1 does not depend on the execution of sporadic tasks within [0, t + 1]. From theorem 2, δ(t) ≥ ∆ 0 .

Case 2: the processor is active within [t, t + 1] in Γ(t + 1). Let d be the deadline of the sporadic task or the request of the periodic task which is processed between t and t + 1. Then, two situations are possible: Case 2-a: there is at least one idle time in [t + 1 + δ(t + 1), d]. The end of this idle time coincides with a deadline which necessarily belongs to a request of a periodic task, ready to be executed at or after t + 1. The existence of an idle time after d j means that the schedule Γ(t + 1) restricted to [t + 1, d j ] does not depend on the execution of sporadic tasks within [0, t + 1]. Therefore, according to theorem 2, δ(t + 1) ≥ ∆ 0 Case 2-b: there is no idle time in [t + 1 + σ(t + 1), d] Consequently, there is no idle time in [t + δ(t + 1), d]. The quantity of processor idle time between t and d respectively in Γ(t) and Γ(t + 1) are identical. As a result, we have δ(t + 1) = δ(t) -((t + 1) -t) + 1, i.e δ(t + 1) = δ(t). Since δ(t) = ∆ 0 by hypothesis, it follows that δ(t + 1) = ∆ 0 . 2 Theorem 3 says that if periodic tasks are jointly scheduled with sporadic tasks and if at a given time instant, the slack is greater than or equal to ∆ 0 (notably whenever the processor is idle), the slack will never decrease below ∆ 0 as long as no additional task is accepted. Consequently, without any test, we may accept in the future any preemptable or nonpreemptable sporadic task whose execution time is less than or equal to ∆ 0 . Theorem 4 For any time t such that δ(t) < ∆ 0 and for any length q such that no additional task has been accepted within [t, t + q], then δ(t + q) ≥ δ(t).

Proof: Let us prove that, if at time t, δ(t) < ∆ 0 then δ(t + 1) ≥ δ(τ ). This proof is obvious when one considers the different cases of Proposition 8:

In cases 1 and 2.1, we have δ(t + 1) ≥ ∆ 0 . Since δ(t) < ∆ 0 by hypothesis, then δ(t + 1) ≥ δ(t).

In case 2.2, we have δ(t + 1) = δ(t). Consequently, δ(t + 1) ≥ δ(t). 2

A first result was to show that a lower bound to the slack of a periodic task set is the slack at time zero, obtained by an off-line computation in O(N). Properties on the slack stated in theorems 3 and 4 are used to improve efficiency and predictivity of the scheduler in the on-line acceptance of sporadic tasks. It will be interesting to determine similar properties under resource constraints.