Systèmes temps réel et Ordonnancement - B. Sadeglitis.univ-lehavre.fr/~sadeg/enseignement/Master-Rech/1-cours-str... · Systèmes temps réel et Ordonnancement - B. Sadeg Université

HistoriqueOrdonnancement de tâches indépendantes

Ordonnancement de tâches dépendantesOrdonnancement dans des situations de surcharge

Ordonnancement conjoint tâches et messages

Systèmes temps réel et Ordonnancement - B. Sadeg

Université du Havre - UFR ST - LITIS - Équipe STILITIS-Université du Havre

UFR des Sciences et Techniques25 rue Philippe Lebon - BP 540

76058 LE HAVRE [email protected]

Université du Havre - UFR ST - LITIS - Équipe STI Systèmes temps réel et Ordonnancement - B. Sadeg




- page 2/119

SOMMAIRE

1 Historique

2 Ordonnancement de tâches indépendantes

3 Ordonnancement de tâches dépendantes

4 Ordonnancement dans des situations de surcharge

5 Ordonnancement conjoint tâches et messages





- page 3/119

Introduction

le temps : rôle de + en + important dans les services et les applications(informatique industrielle, télécommunications, ...)

Informatique industrielle : prémisses de l’informatique temps réel

En télécom, (1) débits élevés : la durée du trafic est bornée, (2) plusieurs fluxd’information : synchronisation nécessaire (multimédia).

Les services : à chaque service est liée une qualité de service (QoS) : tempsd’établissement d’une connexion, temps de réponse d’une requête, etc.





- page 4/119

Introduction (2)

Maîtrise du temps : d’abord, plus de puissance de calcul, puis apparition demécanismes “légers” (moins de temps gaspillé pour des parties non liées àl’application), enfin méthodes pour prédire les comportements temporels

Plusieurs mécanismes à mettre en oeuvre dans un OS pour supporterles applications temps réel, notamment l’ordonnancement des tâches





- page 5/119

Définition d’un système temps réel (STR)

système dont le comportement dépend non seulement del’exactitude des traitements effectués, mais également du tempsoù les résultats de ces traitements sont fournis, c-à-d qu’un retarddans la production d’un résultat est considéré comme une erreur(pouvant entraîner de graves conséquences)





- page 6/119

En général

Observations

Actions

Système informatisue

de controle

Procédé

− automate

− monoprocesseur

− multi−processeur

− réseau local

− équipements élémentaires

− procédé complexe

mesures

événements

commandes

affichages

− ensemble d’équipements

FIGURE: Schéma d’une application temps réelUniversité du Havre - UFR ST - LITIS - Équipe STI Systèmes temps réel et Ordonnancement - B. Sadeg




- page 7/119

Illustration

Système temps réel : calcul de la position d’un bateau en mouvement.Même si le résultat fourni est exact, il est considéré comme erroné s’ilest fourni en retard (le bateau a changé de position)

Système non temps réel : gestion de notes des élèves. Si les moyennescalculées sont exactes alors le système est correct (aux arrondis près)





- page 8/119

Exemples d’applications temps réel

Commandes de procédés, Systèmes embarqués, Guidage de mobiles,Surveillance de centrales nucléaires,

Conduite d’expériences scientifiques, Robotique,

Fourniture d’images et son pour le multimédia, Suivi d’informationsboursières,

Suivi opératoire en milieu médical,





- page 9/119

Fonctionnement

Les applications déclenchent des événements à occurence périodiqueou aléatoire. Elles imposent au système informatique qui leur estassocié de réagir avant un délai fixé (ou à une date donné).

L’échelle de temps peut varier selon le contexte : la microseconde pourun radar, la seconde pour une IHM, la minute dans une chaîne defabrication, l’heure pour une réaction chimique, ...





- page 10/119

Types d’échéances et de systèmes temps réel

échéance dure (hard) : le dépassement de l’échéance provoque uneexception dans le système (qui peut engendrer des dommages)==> STR durs : les échéances ne doivent en aucun cas être dépassées(sinon catastrophe humaine ou industrielle ou économique, ...)

échéance molle, lâche (soft) : un dépassement d’échéance neprovoquie pas d’exception dans le système==> STR mous : les échéances peuvent être dépasséesoccasionnellement (ex. usine automatisée)





- page 11/119

Caractéristiques dun système temps réel(1)

La prévisibilité d’un STR : est un aspect important.Un STR doit être conçu tel que ses performances soient définies dansle pire cas (alors que dans les systèmes classiques, les performancessont définies en termes de moyenne).

La prévisibilité : le fait de savoir à l’avance si un système va respecterses contraintes temporelles (C.T.). Pour cela, il est nécessaire deconnaître avec précision les paramètres des tâches : temps global decalcul de chaque activité, périodicité, date de réveil, etc.

Ces éléments définissent le choix d’une politique d’ordonnancementdes activités telle que le système soit prévisible





- page 12/119

Caractéristiques (2)

Le déterminisme d’un STR : est le but à atteindre pour assurer laprévisibilité : Pour qu’un système soit prévisible, il faut qu’il soitdéterministe. Donc enlever toute incertitude sur le comportement desactivités (individuelles et mises ensemble)

Dans un STR dur : on cherche à ce que toutes les échéances soientrespectées

Dans un STR mou : minimiser le retard moyen des activités parexemple.





- page 13/119

Commentaires

L’organisation du système en couches facilite son évolution.

Dans ces syst. (classiques), les ressources sont allouéesdynamiquement aux tâches : principalement le processeur et la M.C.Des études ont montré que la ressource sensible est la M.C. Celle-ci estd’abord allouée avec des algos complexes. Le processeur est alloué endernier.

l’ordo. est simplifié. Il porte sur peu de tâches (celles déjà servies).

les algos cherchent à optimiser les ressources, mais pas de respecterles priorités des tâches (différence avec les exécutifs temps réel)

dans un STR, les ressources autres que le processeur sont souventattribuées dynamiquement. Le principal param. d’allocation est leprocesseur (on parle d’exécutif temps réel).





- page 14/119

Sources du non-déterminisme

Charge de calcul (durées d’exécution variées)

Entrées/sorties

Interruption : temps de réaction du système

Fautes et exceptions matérielles et logicielles





- page 15/119

Remarques

Le déterminisme absolu : difficile à atteindre

Mais, on améliore par des méthodes d’ordonnancement qui analysent apriori le comportement temporel du système





- page 16/119

La fiabilité (reliability)

Est un autre aspect important des STR

CAR il est difficile de prédire le comportement d’un système dont lescomposants ne sont pas fiables

DONC conception de systèmes tolérants aux fautes (fiables)

Ex : systèmes embarqués embedded systems





- page 17/119

Systèmes embarqués

Pas d’intervention humaine directe

ESSENTIEL : ils doivent être prévisibles (et fiables)

Ex : métro automatique, pilote automatique d’avion, contrôle de navettespatiale, ...

Ce sont des systèmes dédiés : ”taillés spécialement” pour ...





- page 18/119

Exemples d’application

1. Le robot : doit prendre des objets qui défilent sur un tapis

le robot dispose d’une “fenêtre temporelle” pour agir.

S’il agit tard, il manquera l’objet

S’il agit tôt, il va bloquer l’objet (et les objets suivants)





- page 19/119

Exemples d’application (2)

2. Système de vidéo-conférence : sur un réseau local.

le système numérise l’image, puis la séquence. Il faut que soienttraitées 30 images/sec pour une image acceptable.

Plusieurs opérations vont s’enchaîner dans le temps : numérisation,compression, transmission. La durée de ces opérations = temps delatence du système.

La voix doit également être numérisée, compressée et transmise. Il fautqu’il y ait synchronisation son/image. Un retard léger est acceptable. S’ilest trop long, la scène devient incompréhensible. (temps réel mou, ouéchéances molles, relatives)





- page 20/119

Systèmes d’exploitation classiques

non déterministes

l’ordonnanceur vise l’équité

+ d’autres inadaptations





pilotes rseau

pilotes priphriques

ordonnanceur

gest. memoire

gest. fichiers

Gestion d’objets

Services de l’OS :

Noyau :

gest. M.V.

gest. horloge

gest. it.

gest. semaphores

Service de noms ...

Biblio. de pgms

Bases de donnees

messagerie

gest. de taches Materiel

Plate−forme professionnelle : IHM :

FIGURE: Structure d’un syst. d’expl. classique





- page 22/119

Limites des systèmes classiques pour le temps réel

Reposent sur un OS qui offre des mécanismes mal adaptés au tempsréel

politiques d’ordonnancement visent le partage équitable du tempsd’exécution. Pas adaptées à des tâches plus critiques que d’autres.

les mécanismes d’accès aux ressources partagées sont à adapter pouréliminer les incertitudes temporelles

la gestion des E/S engendre de longues attentes (parfois non bornées)

la gestion des interruptions n’est pas optimisée

les mécanismes de gestion de la mémoire virtuelle sont à revoir(swapping, ...)

les temporisateurs qui organisent le temps n’ont pas une résolutionassez fine (pour beaucoup d’applications temps réel)





- page 23/119

Sources d’incertitude

On ne dispose pas de moyens pour indiquer à l’OS le degré d’urgenced’une tâche

le temps de réponse des événements externes n’est pas prévisible : lesystème n’indique rien sur la durée de prise en compte d’uneinterruption





- page 24/119

Terminologie

Noyau : rend l’ensemble des services de base nécessaires à l’exécutiond’une application (gestion mémoire, processeur, adressage,interruptions, ...)

Exécutif : rend les sevices du noyau plus d’autres sans toucher àl’interface utilisateur (surtout pour les systèmes embarqués)

Système d’exploitation : noyau+exécutif+intéraction avec l’utilisateur





- page 25/119

Ordonnancements classiques : multiprogrammation

Objectifs : maximiser le taux d’utilisation du processeur 1 et minimiser letemps de réponse des tâches (durée séparant l’instant de soumissionau système de l’instant de fin d’exécution)

Autres critères : temps d’attente des tâches (état prêt), débit duprocesseur (nbre de tâches traitées par unité de temps), moyenne dutemps de réponse d’un ensemble de tâches), ...

1. temps où le processeur est actif/temps total. En théorie : 0-100%, en pratique :40-95%Université du Havre - UFR ST - LITIS - Équipe STI Systèmes temps réel et Ordonnancement - B. Sadeg




- page 26/119

Principales politiques (1)

→ déterminer quelle tâche prête doit être élue

1. Premier arrivé, premier servi (les tâches de faible temps d’exécutionsont pénalisées si elles sont précédées dans la file par une tâches delongue durée)

2. Plus court d’abord : remédie à l’inconvénient précédent. Minimise letemps de réponse moyen. Pénalise les travaux longs. Elle imposed’estimer les durées d’exécution des tâches (connues difficilement).

3. Temps restant le plus court d’abord : la tâche en exécution restitue leprocesseur lorsqu’une nouvelle tâche ayant un temps d’exécutioninférieur à son temps d’exécution restant devient prête.





- page 27/119

Principales politiques (2)

4. Tourniquet (RoundRobin) : on définit un quantum de temps (10ms à100ms). Chaque tâche de la file acquiert le processeur pendant aumaximum un quantum de temps, puis le cède à sa suivante dans la file,etc.→ utilisée souvent dans les système à temps partagé. Sesperformances dépendent du quantum de temps. Si trop grand :augmente les temps de réponse, si trop petit : multiplication descommutation de contextes.

Priorités constantes : des priorités sont affectées aux tâches et à uninstant donné, la tâche élue est celle qui a la plus forte priorité. Lestâches de faible priorité peuvent ne pas disposer du processeur(famine). Solution : faire “vieillir” la priorité des tâches en attente(augmenter en fonction du temps d’attente). La priorité devient ainsivariable (et donc non constante !)





Quantum = 4 unites

T1 (C1=20 unites) T2 (C2= 7 unites) T3 (C3= 3 unites)

0

T1(2

T2(7)

T3(3)

TourniquetFIN

FIN

FIN

Ordonnancement par Tourniquet (Round Robin)

3 4 6 8 9 11 12 15 18 21 24 30

FIGURE: Exemple : Tourniquet (Round Robin)





3 7

1 1

3 4

2 3

T1

T2

T3

T4

4 11 150 1

T3

T2

T1

T4

priorite Ci

T2 −− T4 −− T1 −− T3

temps

T1

T2

T3

T4

Priorites constantes

Ordonnancement Files priorites constantes

FIGURE: Exemple : Files priorites constantes





- page 30/119

Principales politiques (3)Files de priorités constantes multiniveaux : on définit plusieurs files detâches prêtes. Chaque file correspond à un niveau de priorité (n files depriorités variant de 0 à n-1 : file i , tâches de même priorité). Elles sontgérées soit par ancienneté soit par touniquet. Le quantum peut êtredifférent selon la file. L’ordonnanceur sert d’abord les tâches de la file 0,puis celles de la file 1 (dès que la 0 se vide), etc. Deux variantes :les priorités des tâches sont constantes tout au long de leur exécution :une tâche en fin de quantum est réinsérée dans la même fileles priorités des tâches évoluent dynamiquement en fonction desservices dont elles ont déjà bénéficié. Une tâche de la file i , qui n’a pasterminé son exécution à la fin de son quantum est réinsérée dans la filei +1 (moins prioritaire), etc.On minimise ainsi les risques de famine des tâches de faible priorité endiminuant petit à petit les priorités des tâches ayant de fortes prioritésinitiales.





priorite elevee

faible priorite

ELECTION

FILE 0 q0

FILE 1 q1

FILE N−1 q N−1

arrivee

Files multi−niveauxOrdonnancement :

q est le quantum / q0 < q1 < < qN−1

FIGURE: Exemple : Files multi-niveaux : priorités constantes/variables





- page 32/119

Remarques

Aucune des politiques présentées ne permet de remplir les 2 objectifsd’un ordonnancement temps réel.

Notament : pas de prise en compte de l’urgence des tâches (délaicritque)

==> Ordonnancement spécifique aux tâches temps réel





- page 33/119

Terminologie pour l’ordonnancement des tâches temps réel

tâche = unité de base de l’ordonnancement temps réel. Sontpériodiques ou apériodiques. A contraintes temporelles strictes ourelatives.

Modèle : paramètres chronologiques (délais) et chronométriques(dates). Les paramètres de base d’une tâche sont :

r : sa date de réveil, moment de déclenchement de la 1ere requêted’exécutionC : sa durée maximale d’exécution (si elle dispose du processeur à elleseule)D : son délai critique (délai maximal acceptable pour son exécution)P : sa période (si tâche périodique)Si tâche à contraintes strictes : l’échéance d = r + D, est la date dont ledépassement entraîne une faute temporelle.





- page 34/119

Illustration : diagramme temporel d’exécution

D

C

P P

r0 d0 r1 d1 r2

temps

FIGURE: Modèle de tâches





- page 35/119

Commentaires

T (r0, C, D, P) avec 0 ≤ C ≤ D ≤ P

r0 : date de réveil, C : durée max d’exécution,D : délai critique, P : période

rk : date de réveil de la keme requête de la tâche.rk = r0 + kP, représentée par ↑dk : échéance de la keme requête de la tâche.dk = rk + D, représentée par ↓Rem : tâche à échéance sur requête quandD = P, représentée par l





- page 36/119

Remarques

Tâche à contraintes relatives : D parfois omis

Tâche apériodique : pas de paramètre P

Plus les paramètres précédents sont exacts, plus la qualité del’ordonnancement est meilleure





- page 37/119

Autres paramètres déduitsu = C

P (doit être ≤ 1) : facteur d’utilisation du processeur par la tâchech = C

D doit être (≤ 1) : facteur de charge du processeurparamètres dynamiques (pour suivre l’exécution d’une tâche) :

s : date de début de l’exécution d’une tâchee : date de fin d’exécution d’une tâcheD(t) = d− t : délai critique résiduel à la date t(0 ≤ D(t) ≤ D)C(t) = durée d’exécution résiduelle à la date t(0 ≤ C(t) ≤ C)L = D−C laxité nominale de la tâche, retard maximum pour son débutd’exécution s quand la tâche s’exécute seule.L(t) = D(t)−C(t) laxité nominale résiduelle, retard maximum pourreprendre l’exécution d’une tâche si elle s’exécute seule (L(t) égal aussiD+ r − t−C(t)).TR = e− r : temps de réponse de la tâcheCH(t)= C(t)

D(t) : charge résiduelle au temps t





- page 38/119

Plusieurs états d’une tâche

élue : un processeur est alloué à la tâche

bloquée : la tâche attend une ressource, un message ou un signal desynchronisation

prête (éligible) : la tâche attend d’être élue

passive : la tâche n’a pas de requête en cours

inexistante : la tâche n’est pas créée





- page 39/119

Etats d’une tâche

ELUE

PRETEBLOQUEE

PASSIVEINEXISTANTE

faute temporelle

faute

temporelle

FIGURE: Etats d’une tâche





- page 40/119

Exemples de tâches

acquisition de données depuis des capteurs

affichage de résultats sur un écran

capture de la température dans une centrale

envoi d’une scène (image+son) sur un moniteur, ...





- page 41/119

Autres caractéristiques d’une tâche

préemptible : tâche élue qui peut être arrêtée et remise à l’état prêt,pour allouer le processeur à une autre tâche

non préemptible : une fois élue, la tâche ne doit plus être interrompuejusqu’à la fin de la requête (tâches atomiques, à exécution immédiate).Ex : tâche qui s’exécute sous le contrôle d’une interruption





- page 42/119

Autres caractéristiques d’une tâche (2)

tâches indépendantes : lorsqu’elles n’ont pas de relations deprécédence, ni ne partagent des ressources critiques

tâches dépendantes :Par une relation de précédence statique : si elles agissent selon un ordreprédéterminé, ou induit par la communication par messages ou par unerelation explicite de synchronisation. Elle est statique car connue a priori.On peut construire le graphe de dépendance.Par une relation de précédence dynamique : si elles partagent desressources critiques (accès en exclusion mutuelle). La relation estdynamique car l’utilisation de la ressource dépend de l’ordre d’exécutiondes tâches.





- page 43/119

Autres caractéristiques d’une tâche (3)

Priorité externe (fixe) : forme primitive d’ordonnancement temps réel.Tout est détérminé par un ordonnancement hors ligne ou par des règlesqui imposent un ordre a priori (ex : tâche de gestion de l’horloge, tâchede sauvegarde en cas de chute de tension)

Urgence : tâches de même urgence→ même échéance.

Importance : tâches pouvant être supprimées en premier dans certainscas pour permettre aux autres (plus importantes) de respecter leurscontraintes. 2 tâches de même urgence peuvent avoir des importancesdifférentes.





- page 44/119

Ordonnancement temps réel

Son but est de permettre le respect des contraintes temporelles destâches d’une application quand elle s’exécutent en mode courant

Il doit être certifiable, c-à-d prouver a priori le respect des C.T. destâches d’une application (en régime courant)

En régime de surcharge (tâches supplémentaires suite à desanomalies : alarmes, variations des temps d’exécution,→ fautestemporelles...) : l’ordonnancement doit offrir une tolérance auxsurcharges (permettre une exécution dégradée mais sécuritaire dusystème)





- page 45/119

Définitions

Configuration de tâches : mise en jeu d’un ensemble de n tâches quis’exécutent

Départ simultané : même date de réveil (sinon départ échelonné)

Facteur d’utilisation du processeur pour n tâches périodiques : U =∑

i=ni=1

CiPi

Facteur de charge du processeur pour n tâches périodiques : CH =∑

ni=1

CiDi

Laxité du processeur à l’instant t , LP(t) = intervalle de temps à partir det pendant lequel le processeur peut rester inactif sans remettre encause le respect des échéances (LP(t) ≥ 0, ∀ t). LP(t) est égale auminimum des laxités conditionnelles LCi(t) des tâches i

LCi(t) = Di - ∑j Cj(t). Les tâches j sont celles qui sont déclenchées àl’instant t et qui devancent i dans la séquence de planification.





- page 46/119

Définition du problème d’ordonnancement

Le système de conduite d’une application temps réel doit piloter leprocédé en ordonnançant les tâches avec 2 objectifs :

assurer le respect des C.T. en fonctionnement nominalatténuer les effets des surcharges et maintenir le procédé dans un étatcohérent et sûr en fonctionnement anormal (pannes matérielles oulogicielles)→ respecter au moins les CT des requêtes vitales pour leprocédé

L’algorithme d’ordonnancement fournit une description de la séquencede planification de tâches à effectuer de manière à respecter les CT.





- page 47/119

Typologie des algorithmes d’ordonnancement

Hors ligne : l’algorithme construit la séquence complète de planificationdes tâches sur la base de tous les paramètres temporels des tâches.Séquence connue avant l’exécution. Très efficace Mais cette approchestatique est rigide car elle suppose que tous les paramètres, y comprisles dates de réveil, sont figées→ ne s’adapte pas aux changements del’environnement

En ligne : capable à tout instant de l’exécution d’une application dechoisir la prochaine tâche à ordonnancer, en utilisant les informationsdes tâches déclenchées à cet instant. Ce choix peut être remis encause par l’occurence d’un nouvel événement. Cette approchedynamique offre des solutions moins bonnes (car elle utilise moinsd’informations) et entraîne des surcoûts de mise en oeuvre. Lesavantages : permet l’arrivée imprévisible des tâches, autorise laconstruction progressive de la séquence d’ordonnancement.





- page 48/119

Typologie des algorithmes d’ordonnancement (2)

Pour pouvoir traiter les tâches apériodiques (et les surchargesanormales), l’ordonnancement se fait souvent en ligne.

Algorithme préemptif : permet à l’ordonnanceur de déposséder la tâcheélue du processeur au profit d’une autre tâche jugée plus prioritaire.N’est utilisable que si toutes les tâches sont préemptibles. La tâcheayant perdu le processeur passe à l’état prêt pour être élueultérieurement sur le même processeur ou sur un autre.

Algorithme non préemtif : n’arrête pas l’exécution d’une tâche élue. Peuten résulter des fautes temporelles qu’un algorithme préemtif auraitévitées.





- page 49/119

Best effort - Strict

Meilleur effort (Best effort) : pour une application à contraintes relatives,la stratégie d’ordonnancement est celle du meilleur effort : elle essaiede faire au mieux avec les processeurs disponibles.

Pour une application à contraintes strictes : l’ordonnanceur doit garantirle respect des CT. Il y a obligation de réussite et non tolérance auxfautes temporelles.





- page 50/119

Centralisé - Distribué

Centralisé : si l’algorithme d’ordonnancement s’exécute sur unearchitecture centralisée (ou sur un site privilégié d’une architecturedistribuée, qui contient tous les paramètres des tâches).

Distribué : lorsque les décisions d’ordonnancement sont prises surchaque site par un ordonnanceur local après une éventuellecoopération pour effectuer un ordonnancement global (Si global :peuvent intervenir le placement des tâches sur un site et la migrationdes tâches d’un site à un autre)





- page 51/119

Propriétés des algorithmes d’ordonnancement

Séquence valide : un algorithme d’ordonnancemnt délivre uneséquence d’ordonnancement valide pour une configuration de tâchesdonnée si toutes les tâches respectent leur CT.

Une configuration est ordonnançable dès qu’il existe au moins unalgorithme capable de fournir une séquence valide pour cetteconfiguration.

Algorithme optimal : s’il est capable de produire une séquence validepour toute configuration de tâches ordonnançables.





- page 52/119

Tests

Test d’ordonnançabilité : vérifie qu’une configuration de tâchespériodiques donnée soumise à un algorithme d’ordonnancement peutêtre ordonnancée selon une séquence valide.

Test d’acceptabilité : un algorithme en ligne modifie dynamiquement laséquence d’ordonnancement à l’arrivée de nouvelles tâches (ou à lasuite de dépassement d’échéances). Une tâche nouvelle peut êtreajoutée à la configuration s’il existe au moins une séquence valide avecla nouvelle configuration (tâches existantes + celle ajoutée). L’ensembledes conditions à satisfaire est le test d’acceptabilité (routine degarantie).Dans un ordonnancement réparti, le rejet d’une requête par ce test peutêtre résolu en essayant de migrer la tâche sur un autre site.





- page 53/119

Propriétés (2)

Période d’étude : Pour valider une configuration de tâches périodiqueset apériodiques, on effectue une analyse temporelle de l’exécution de laconfiguration.

Pour les tâches périodiques : il suffit d’effectuer l’analyse sur unepériode (car la configuration est périodique, et se répète indéfiniment)

Début de la période d’étude : t = Min{ri0}, c-à-d date de réveil de lapremiere requête de la première tâche de la configuration.

Fin de la période d’étude : Max{ri , 0, rj , Dj } + 2*PPCM(Pi ), i : tâchespériodiques, j : tâches apériodiques (PPCM(Pi ) seulement, sipériodiques).





- page 54/119

Mise en oeuvre d’un ordonnanceur

Table d’élection : lorsque la séquence est connue a priori(ordonnancement hors ligne), cette séquence est inscrite dans une tableconsultée par l’ordonnanceur pour élire les tâches.

Liste d’attente avec priorités : l’ordonnancement en ligne→ créationdynamique d’une séquence de planification. Le 1er élément indique latâche élue (si monoprocesseur), les n 1ers, si n processeurs.La liste est ordonnée selon les clés (priorités).

Priorité fixe : Dans la liste d’attente : la clé (priorité) est fixe si on prendun paramètre fixe comme clé (durée d’exécution, délai critique, période).

Priorité variable : si on prend comme clé un paramètre variable (date deréveil, échéance, ...)





- page 55/119

Algorithme En ligne, à priorité constante

RateMonotonic (RM)

InverseDeadline (ID) ou DeadlineMonotonic (DM)





- page 56/119

Algorithme En ligne, à priorité variable)

Earliest Deadline (ED) ou Earliest Deadline First (EDF )

Least Laxity (LL) ou Least Laxity First (LLF )





- page 57/119

Ordonnancement de tâches indépendantesAlgorithme En ligne, à priorité constante (où D=P)

Rate Monotonic (ou RM) : priorité d’une tâche = f(sa période). La tâchede plus petite période est la plus prioritaire. L’algorithme est optimaldans la classe des algorithmes à priorité constante pour uneconfiguration de tâches à échéances sur requête. Dans ce cas, onconnaît une condition suffisante d’existence d’une borne minimalepour l’acceptation d’une configuration de n tâches :

∑ni=1

CiPi≤ n(2

1n −1)

Cette borne = pire cas et tend vers ln 2 quand n très grand (c-à-d 69%).Elle peut être dépassée (en moyenne elle est de 88%)





- page 58/119

Exemple d’ordonnancement avec RM

la figure 8 montre l’exemple d’un ordonnancement “Rate Monotonic”pour 3 tâches périodiques à échéance sur requête (échéance=période).T1(r0 = 0,C = 3,P = 20), T2(r0 = 0,C = 2,P = 5),T3(r0 = 0,C = 2,P = 10). Tâche de plus haute priorité : T2, tâche deplus basse priorité : T1.

La période d’étude est l’intervalle [0, 20] 2.

Les 3 tâches respectent leur CT car la condition suffisante est vérifiée :on a bien 3

20 + 25 + 2

10 ≤ 0.779 (0.15+0.4+0.2=0.75 ≤ 0779).

Rmq : l’utilisation de la période comme critère d’ordonnancement limitel’application de “Rate Monotonic” aux seules tâches où l’échéance estégale à la période (échéances sur requête).

2. Configuration à départ simultané, période d’étude [0, PPCM(Pi )]Université du Havre - UFR ST - LITIS - Équipe STI Systèmes temps réel et Ordonnancement - B. Sadeg




- page 59/119

Chronogramme de ces tâches avec ’Rate Monotonic’

T1 (r1=0, C=3, P=20)

0

20

T2 (r2=0, C=2, P=5)

T3 (r3=0, C=2, P=10)

0

0

4 5

2 5 7 10 12 15 17

20

20

207 9

2 4 10

temps

temps

temps

12 14

FIGURE: Ordonnancement “Rate Monotonic”





- page 60/119

Ordonnancement de tâches indépendantesAlgorithme En ligne, à priorité constante (où D <> P)

Inverse Deadline ou Deadline Monotonic : priorité d’une tâche = f(sondélai critique). La tâche la + prioitaire est celle de + petit délai critique.Cet algo est égal en performances à “Rate Monotonic” pour les tâches àéchéances sur requête, et meilleur pour les autres types deconfigurations de tâches. Condition suffisante d’acceptabilité :

∑ni=1

CiDi≤ n(2

1n −1) (facteur de charge)





- page 61/119

Exemple d’ordonnancement avec ’DM’ (ou ’ID’)

la figure 9 montre l’exemple d’un ordonnancement “Deadline Monotonic”pour 3 tâches périodiques.T1(r0 = 0,C = 3,D = 7,P = 20), T2(r0 = 0,C = 2,D = 4,P = 5),T3(r0 = 0,C = 2,D = 9,P = 10). Tâche de plus haute priorité : T2,tâche de plus basse priorité : T3.

La condition suffisante n’est pas vérifiée : 37 + 2

4 + 29 = 1.14 > 0.77.

Cependant, le chronogramme construit sur la période d’étude montrequ’elles sont ordonnançables sans faute temporelle.





- page 62/119

Chronogramme de ces tâches avec ’Deadline Monotonic’

0

0

temps

temps

temps

0

2 5 7 20

20

2019

19171514121097542

4 5 7 9 10 12 14

T2 (r0=0, C=2, D=4, P=5)

T3 (r0=0, C=2, D=9, P=10)

T1 (r0=0, C=3, D=7, P=20)

FIGURE: Ordonnancement “Inverse Deadline ou Deadline Monotonic”





- page 63/119

Ordonnancement de tâches indépendantesAlgorithmes en ligne à priorité variable : EDF

La priorité d’une tâche varie dans le temps.

Earliest Deadline : (ED) : La + haute priorité à l’instant t est accordée àla tâche dont l’échéance est la + proche. Pour les tâches à échéancessur requête, une CNS d’ordonnancement est : ∑

ni=1

CiPi≤ 1

Pour des tâches périodiques quelconques, une condition suffisante est :∑

ni=1

CiDi≤ 1 et une condition nécessaire est : ∑

ni=1

CiPi≤ 1.





- page 64/119

Exemple

la figure 10 montre l’exemple d’un ordonnancement “Earliest Deadline”pour 3 tâches périodiques. T1(r0 = 0,C = 3,D = 7,P = 20),T2(r0 = 0,C = 2,D = 4,P = 5), T3(r0 = 0,C = 1,D = 8,P = 10).

à t=0 : au réveil des 3 tâches, T2 prioritaire, elle s’exécute pendant 2unités.

A t=2, T2 termine. C’est T1 la + prioritaire. Elle s’exécute pendant 3unités de temps.

A t=5, T1 se termine et T2 se réveille de nouveau (car période 5), maisc’est T3 qui est cette fois la + prioritaire car son échéance est 8, elles’exécute pendant une unité.

Ici, on voit que les priorités des tâches varient dans le temps : parexemple, à t=0, c’est T2 + prioritaire (que T1 et T3), mais à t=5, c’est T3

la plus prioritaire.





- page 65/119

Chronogramme de ces tâches avec ’ED’ (ou ’EDF’)

0 2 5 7 20

20

20

5

5

5

0

0

6 8

6 8

4 9 10 12 14 15 17 192

12 13 1810

T2 (r0=0, C=2, D=4, P=5 )

T1 (r0=0, C=3, D=7, P=20 )

T3 (r0=0, C=1, D=8, P=10 )

Ordonnancement ED (ou EDF)

FIGURE: Ordonnancement “Earliest Deadline”





- page 66/119

Ordonnancement de tâches indépendantesAlgorithmes en ligne à priorité variable : LLF

La priorité d’une tâche varie dans le temps.

Least Laxity (LL) : La tâche de + haute priorité à l’instant t est celle qui ala + petite laxité dynamique Li(t). Cet algorithme est optimal et lesconditions d’ordonnançabilité des tâches sont les mêmes que pourEarliest Deadline. Les séquenecs produites par LL sont équivalentes àcelles produites par ED lorsque les valeurs des laxités sont calculéesaux dates de réveil. Par contre, si on calcule la laxité à chaque instantalors la séquence produite par LL entraîne plus de changements decontextes que par ED.





- page 67/119

ExempleLes figures 11 et 12 montrent l’ordonnancement avec LL pour les 3tâches de l’exemple sur ED, avec un calcul de laxité effectué aux seulesdates de réveil.A t=0, les 3 tâches sont réveillées. Laxité dynamique de T1=7-3=4.Laxité de T2=4-2=2. Laxité de T3=8-1=7. C’est donc T2 (la + prioritaire)qui s’exécute à t=0 (pour 2 unités).A t=2, c’est T1 qui s’exécute (sa laxité [7-2-3] est plus petite que celle deT3 [8-2-1] ).A t=5, T2 se réveille de nouveau. Sa laxité dynamique (9-5-2 = 2èmeéchéance - temps courant - durée exécution) est égale à 2 , celle de T3

(8-5-1) est de 2 également (retard ’toléré’ t.q l’échéance est toujoursrespectée). On peut choisir T3 (cas a) ou t2 (cas b) pour êtreordonnancée et s’exécuter.Rappel : L(t) = D(t)−C(t) laxité nominale résiduelle, retard maximumpour reprendre l’exécution d’une tâche si elle s’exécute seule (= aussiD+ r − t−C(t)).





- page 68/119

Chronogramme de ces tâches avec ’LL’ : ici T3 élue à t=5

0 2 5 7 20

0 2 4 5 6 8 9 10 12 14 15 17 19 20

0 5 6 8 10 13 18 2012

tempstemps

temps

temps

T2 (r0=0, C=2, D=4, P=5)

T3 (r0=0, C=1, D=8, P=10)

T1 (r0=0, C=3, D=7, P=20)

FIGURE: Ordonnancement “Least Laxity”. Cas (a) : c’est T3 qui est élue à t=5





- page 69/119

Chronogramme de ces tâches avec ’LL’ : ici T2 élue à t=5

0 2 5 7 20

0 2 4 5 9 10 12 14 15 17 19 20

0 8 10 13 18 2012

tempstemps

temps

temps

7

7

T2 (r0=0, C=2, D=4, P=5)

T1 (r0=0, C=3, D=7, P=20)

T3 (r0=0, C=1, D=8, P=10)

FIGURE: Ordonnancement “Least Laxity”. Cas (b) : c’est T2 qui est élue à t=5





- page 70/119

tâches tâches périodiques et tâches apériodiquesAlgorithmes qui prennent en compte les tâches apériodiques

But : les CT des tâches périodiques doivent être respectées et

(1) soit minimiser le temps de réponse des tâches apériodiques àcontraintes relatives Best Effort),

(2) soit maximiser le nombre de tâches apériodiques à contraintesstrictes qui respectent leurs CT .





- page 71/119

Tâches apériodiques à contraintes relatives :1. Traitement en arrière-plan (BackgroundProcessing)

les tâches apériodiques sont ordonnancées lorsque le processeur estoisif (pas de tâche périodique prête).

Si ∃ plusieurs tâches apériodiques, traitement par dates de réveil(FIFO).





- page 72/119

Exemple : Prise en compte des tâches apériodiques :Ordonnancement “en arrière plan”

La figure montre un tel ordonnancement sur un intervalle égale à 2 foisla période d’étude d’une configuration de 2 tâches périodiques àéchéances sur requête T1(r0 = 0,C = 2,P = 5),T2(r0 = 0,C = 2,P = 10).

L’application de ’Rate Monotonic’ à cette configuration laisse leprocesseur oisif sur les intervalles [4,5], [7,10], [14,15] et [17,20].

La tâche apériodique Ta3(r = 4,C = 2) survenant à t = 4 peutimmédiatement commencer son exécution qu’elle finit sur le tempscreux suivant c-à-d entre les temps t = 7 et t = 8.

La tâche apériodique Ta4 (r=10, C=1) qui survient à t=10 doit attendre letemps creux [14,15] pour s’exécuter. La tâche apériodique Ta5 (r=11,C=2) doit attendre le temps creux [17,20] pour s’exécuter.





- page 73/119

Chronogramme : Ordonnancement “en arrière plan’

T1 (r0=0, C=2, P=5)

Temps creux

Taches apériodiques

Tap (r=4, C=2)Tap (r=10, C=1)

Tap (r=11, C=2)

0

0

0

0

2 5 7 10 12 15 17 20

20

20

20

2 4 10 12 14

4 5 7 10 14 15 17

4 5 7 8 14 15 17 1910 11

temps

temps

temps

temps

T2 (r0=0, C=2, P=10)

Arriere−plan (background)

FIGURE: Ordonnancement “en arrière plan”





- page 74/119

Remarque

La méthode d’ordonnancement en arrière-plan est simple et peucoûteuse et est applicable ∀ l’algorithme d’ordonnancement des tâchespériodiques. Mais les temps de réponse des tâches apériodiquespeuvent être mauvais surtout si la charge des tâches périodiques estimportante.





- page 75/119

Tâches apériodiques à contraintes relativeaffine le résultat et s’exécutes’il reste assez de temps avant l’échéance.s : 2. Les serveurs de tâches

un serveur est une tâche périodique créée spécialement pour veiller àl’ordonnancement des tâches apériodiques.Elle est caractérisée par une période et un temps d’exécution (lacapacité du serveur).Elle est souvent ordonnancée avec le même algo que les autres tâchespériodiques.Une fois active, la tâche serveur sert les tâches apériodiques dans lalimite de sa capacité. L’ordre de service des tâches apériodiques nedépend pas de l’algo d’ordonnancement des tâches périodiques (il peutêtre FIFO, f(échéances), f(temps d’exécution), ...).∃ plusieurs types de serveurs : le plus simple est le serveur parscrutation. Les autres (serveur ajournable, à échange de priorité,sporadique) en sont des améliorations.





- page 76/119

Les serveurs de tâches : Traitement par ’scrutation’ (“Polling”)

à chaque activation, le serveur traite les tâches apériodiques en attentedepuis son activation précédente, jusqu’à épuisement de sa capacité(ou plus de tâches en attente).

Si, lors d’une nouvelle activation, il n’y a aucune tâche apériodique enattente, le serveur se suspend jusqu’à la prochaine occurence : sacapacité (tps d’exécution) est récupérée par les tâches périodiques.

La figure montre le fonctionnement d’un serveur par scrutation.Configuration : 2 tâches périodiques à échéances sur requête T1(r0=0,C=3, P=20) et T2(r0=0, C=2, P=10).

La tâche serveur est Ts(r0=0, C=2, P=5) est de plus grande priorité (carplus petite période) avec “Rate Monotonic” appliqué pour ordonnancerles 3 tâches. On vérifie que la condition d’acceptabilité est remplie :3

20 + 210 + 2

5 = 0.75 ≤ 0.77





- page 77/119

Chronogramme : Ordonnancement “avec un serveur par scrutation”

0

0

0

0

20

20

20

20

2 10 12 14

temps

temps

temps

temps

T1 (r0=0, C=3, P=20)

T2 (r0=0, C=2, P=10)

Tps (r0=0, C=2, P=5)

taches apériodiques

2 5

4 5 107

capacité du serveur

5 7 10 12 15 16

11 12 15 16

12

Tap3(r=4, c=2)Tap4(r=10, c=1) Tap5(r=11, c=2)

Serveur par scrutation

FIGURE: Ordonnancement “avec un serveur par scrutation”





- page 78/119

Commentaires : “avec un serveur par scrutation”

à t=0, aucune tâche apériodique, donc le serveur se suspendimmédiatement. C’est T2 de priorité élevée suivante qui s’exécute, puisc’est T1.

à t=4, la tâche apériodique Ta4 survient. elle doit attendre l’occurencesuivante du serveur (t=5) pour s’exécuter. Elle épuise alors toute lacapacité (C=2) du serveur.

A t=10, le serveur se réveille de nouveau, il sert la tâche apériodiqueTa4 qui vient d’être activée. Puis il sert Ta5. La tâche Ta5 ne peuts’exécuter entièrement car elle épuise la capacité restante du serveur.Elle doit attendre l’occurence suivante du serveur à t=15 pour finir sonexécution. Il reste encore une unité au serveur, il la perd car il n’y aaucune tâche apériodique à servir.





- page 79/119

Commentaires : “avec un serveur par scrutation” (suite)

Remarques : Faiblesses : lorsque le serveur est prêt, si pas de tâches àtraiter, sa capacité est perdue. Si des tâches apériodiques surviennent,elles doivent attendre l’occurence suivante.

Améloration : serveur “ajournable” : si pas de tâche apériodique à servir,le serveur prêt conserve sa capacité. Il est donc prêt à servird’éventuelles tâches apériodiques qui surviennent. MAIS, il viole leprincipe de “Rate Monotonic” (tâche prête de plus haute priorité doits’exécuter). Il diminue le taux d’utilisation du processeur par les tâchespériodiques.





- page 80/119

Les serveurs de tâches : Serveur sporadique

améliore le temps de réponse des tâches apériodiques sans diminuer letaux d’utilisation du processeur des tâches périodiques.

Ce serveur est également une tâche périodique de + haute priorité, quiconserve sa capacité de traitement si, à son réveil, il n’y a pas de tâcheapériodique à servir. Mais ici, le serveur sporadique ne retrouve pas sacapacité initiale à chaque occurence.





- page 81/119

Commentaires : “Serveur sporadique”

La figue montre le fonctionnement d’un serveur sporadique sur le mêmeensemble de tâches que précédement : T1(r0=0, C=3, P=20) et T2(r0=0,C=2, P=10). La tâche serveur est Ts(r0=0, C=2, P=5).

A t=0, le serveur se réveille, mais se suspend car pas de tâchesapériodique à traiter (mais il conserve sa capacité, 2).

A t=4, la tâche apériodique Ta3 survient. Elle est servie immédiatemententre t=4 et t=6 et consomme toute sa capacité. Comme le serveur s’estexécuté, une date de réinitialisation de sa capacité est calculée : ce serat=4+5. La valeur de réinitialisation est 2.





- page 82/119

Commentaires : “Serveur sporadique” (suite)

A t=9, le serveur retrouve toute sa capacité, mais il se suspend car iln’ya pas de tâche apériodiques en attente.

A t=10, la tâche Ta4 arrive et s’exécute tout de suite pendant une unité(C=1). Puis Ta5 arrive et commence à s’exécuter pendant une unité etelle est suspendue jusqu’à nouvelle occurence du serveur (car sacapacité est épuisée). Une nouvelle date de réinitialisation de lacapacité est calculée : t=10+5. La tâche Ta5 poursuivra son exécutionpour une unité quand le serveur aura récupéré sa capacité à t=15. Ilreste au serveur 1 unité qu’il récupérera à t=20.





- page 83/119

Chronogramme : Ordonnancement “avec un serveur sporadique”

0

0

0

0

20

20

20

20

2 10 12 14

temps

temps

temps

temps

T1 (r0=0, C=3, P=20)

T2 (r0=0, C=2, P=10)

Tps (r0=0, C=2, P=5)

taches apériodiques

2

4 10

capacité du serveur

11 12 15 16

4 6 7

6

1210012

96 15

Tap3(r=4, c=2)Tap4(r=10, c=1) Tap5(r=11, c=2)

FIGURE: Ordonnancement “avec un serveur sporadique”





- page 84/119

Tâches apériodiques à contraintes strictes

Une méthode consiste à doter les tâches apériodiques avec despseudo-périodes : c’est l’intervalle minimal entre deux occurencessuccessives d’une tâche apériodique. On utilise “RM” pour ordonnancerles 2 types de tâches. Difficulté : l’évaluation de la pseudo-période et lasous-utilisation du processeur.

Une autre méthode : les tâches apériodiques sont traitées sanshypothèse sur leur rythme d’arrivée. Elles sont ordonnancées selon“Earliest Deadline”. A chaque arrivée d’une tâche apériodique, une“routine” de garantie teste dynamiquement si la nouvelle peut s’exécuteren respectant ses CT, celles des tâches périodiques et celles des autrestâches apériodiques précédemment acceptées mais non terminées. Sile test est positif, la tâche est acceptée.





- page 85/119

Méthodes pour tâches apériodiques à contraintes strictes

∃ 2 politiques d’acceptation dynamique de tâches apériodiques quifavorisent toutes les 2 les tâches périodiques, car les tâchesapériodiques génératrices de surcharge sont rejetées. Ces politiquessont applicables natament sur un système réparti où un mécanisme departage de charge permet de faire exécuter une tâche rejetée sur unsite par un autre site moins chargé. Ces 2 politiques sont :

1. Acceptation dans les temps creux d’une séquence rigide de tâches :consiste à ordonnanncer les tâches apériodiques dans les temps creuxde la séquence d’ordonnancement “ED” des tâches périodiques. Prochede la politique en ’arrière-plan’ vue précédemment, mais ici les tâchesapériodiques ont des CT à respecter et sont elles-mêmesordonnancées selon “ED”. A chaque réveil d’une tâche apériodique, uneroutine de garantie est exécutée.





- page 86/119

Routine de garantie

1. teste l’existence d’un temps creux suffisant pour l’exécution de latâche apériodique entre sa date de reveil et son échéance.

2. si ce temps creux existe, elle vérifie que l’acceptation de la nouvelletâche ne remet pas en cause le respect des CT de tâches apériodiquesprécédemment acceptées, non encore achevées. Cette vérification neconcerne que les tâches apériodiques dont les échéances sont ≥ àcelle de la nouvelle tâche.

Si au moins une des condition 1 ou 2 n’est pas satisfaite, alors la tâcheest rejetée, sinon elle est ajoutée à l’ensemble des tâches apériodiquesacceptées, pour être exécutée selon son échéance.





- page 87/119

Exemple

La figure 16 montre que la configuration périodique “ED” présentedurant la période d’étude 3 intervalles de creux : [8,10], [13,15] et[17,20]. Les 3 tâches apériodiques Ta4, Ta5 et Ta6 peuvent êtreacceptées dans ces temps creux :





- page 88/119

Exemple : déroulement

à t=4, Ta4 se réveille.Le temps creux existant entre sa date de réveil etson échéance est l’intervalle [8,10] = 2 unités juste suffisantes pourexécuter la tâche. Ta4 dispose donc d’assez de temps pour s’exécuterdans le respect de ses CT, et comme il n’a pas d’autre tâchesapériodiques précédemment acceptées mais non terminée, elle estacceptée.

à t=10, Ta5 se réveille. Le temps creux existant entre sa date de réveil10 et son échéance 18, est de 3 unités (tout l’intervalle [13,15] + 1 unitéde l’intervalle [17,20]). Il y a donc d’assez de temps pour exécuter Ta5

qui a un temps d’exécution égal à 1. Et comme il n’a pas de tâchesapériodiques acceptées et non terminées (Ta4 s’était exécutée entre 8et 10), alors Ta5 peut être acceptée.





- page 89/119

Déroulement (suite)

A t=11, Ta6 se réveille. Le temps creux existant entre sa date de réveil11 et sont échéance 16 est de 2 unités ( [13,15]), donc juste suffisantpour l’exécuter dans le respect de son échéance. Mais, il faut vérifierque son acceptation ne remet pas en cause les CT des autres tâchesapériodiques acceptées non terminées (et d’échéances plus éloignéesque la sienne). Ici Ta5 qui n’a pas encore commencé son exécution etdont l’échéance est 18. L’ordre d’exécution devient Ta6 puis Ta5 et onconstate que chacune peut s’exécuter dans le respect de ses CT (carC=2 pour Ta6 et C=1 pour Ta5). lon son échéance.





- page 90/119

Ordonnancement dans les temps creux : Routine de garantie

0

0

20

202

temps

temps

2 5

8

T1 (r0=0, C=3, D=7, P=20)

temps

0

7

4 5 6 9 10 12 14 1715 19

65 10 1812 13 208

8 10 13 15 17 20

temps creux

4 8 10 13 18 2011 15 1716

taches aperiodiques

T2 (r0=0, C=2, D=4, P=5)

T3 (r0=0, C=1, D=8, P=10)

Ta5(r=10, c=1, d=18) Ta6(r=11, c=2, d=16)Ta4(r=4, c=2, d=10)

FIGURE: Ordonnancement “ dans les temps creux”





- page 91/119

2. Acceptation des tâches apériodiques et ordonnancement conjointaux tâches périodiques

2. Acceptation des tâches apériodiques et ordonnancement conjoint auxtâches périodiques : à chaque arrivée d’une nouvelle tâche apériodique,il y a construction d’une nouvelle séquence “ED” comprenant à la foisles tâches périodiques, les tâches apériodiques précédemmentacceptées mais non terminées et la nouvelle tâche. Si la séquence peutêtre construite, alors la tâche est acceptée. Les figures 17 et 19 montreun exemple de fonctionnement et on voit que les 3 tâches apériodiquesTa4, Ta5 et Ta6 peuvent être ordonnancées conjointement aux tâchespériodiques.A t=4, Ta4 se réveille. La séquence “ED” construite à t=4 comprend lestâches périodiques actives T1(C(4)=1, d=7) et T3, les requêtes à venirdes tâches périodiques ainsi que la tâche qui arrive Ta4. L’exécution decelle-ci sera planifiée entre t=8 et t=10. La séquence respecte les CT detoutes les requêtes qui la composent.





- page 92/119

2. suite

A t=10, Ta5 se réveille. La séquence “ED” construite à t=10 comprendles requêtes à venir des tâches périodiques T2 et T3 et celle de Ta5. Iciaussi, la séquence “ED” permet le respect des CT de toutes lesrequêtes qui la composent. L’exécution de Ta5 acceptée est planifiéeentre 13 et 14.

A t=11, Ta6 se réveille (figure suivante 2.12). La séquence “ED”construite à t=11 comprend les tâches périodiques actives T2(C(11)=1,d=14) et T3, les requêtes à venir de la tâche périodique T2 ainsi que lestâches apériodiques Ta5 et Ta6. La tâche Ta6 peut être ordonnancéesans remettre en cause ni les échéances des tâches périodiques, nicelle de la tâche apériodique Ta5. Ta6 est donc acceptée.





- page 93/119

Ordonnancement conjoint

0

0

20

202

temps

temps

2 5

8

T1 (r0=0, C=3, D=7, P=20)

temps

0

7

4 5 6 9 10 12 14 1715 19

65 10 1812 13 208

8 10 13 20

taches aperiodiques

4

temps

14 18

T2 (r0=0, C=2, D=4, P=5)

T3 (r0=0, C=1, D=8, P=10)

Ta4(r=4, c=2, d=10) Ta5(r=10, c=1, d=18)

FIGURE: Ordonnancement “conjoint”





- page 94/119

Ordonnancement conjoint

��

��

��

��

��

��

��

��

0

0

20

202

temps

temps

2 5

8

T1 (r0=0, C=3, D=7, P=20)

temps

0

7

4 5 6 9 10 12 14 15 19

65 10 188

8 10

taches aperiodiques

4

temps

14 18

1816

14 15

12 15 1611 20

20

T2 (r0=0, C=2, D=4, P=5)

T3 (r0=0, C=1, D=8, P=10)

Ta4(r=4, c=2, d=10) Ta5(r=10, c=1, d=18) Ta6(r=11, c=2, d=16)

FIGURE: Ordonnancement “conjoint”





- page 95/119

Ordonnancement de tâches dépendantesParamètres de priorité

définis selon l’application industrielle (fréquence d’acquisition desdonnées, ...)

certaines applications induisent des contraintes de précédence que l’ondoit retrouver dans le modèle de tâches.





- page 96/119

Exemple : Caméra pour la reconnaissance et la vérification

T1, T2 : acquisition

T3, T4 : pré-traitement

T5 : extraction de caractéristiques

T6 : détection de contours

T7 : estimation de la hauteur

T8 : Reconnaissance finale





- page 97/119

Graphe de précédence

T1

T4 T5

T3T2

tache

pecedence

FIGURE: précédence





- page 98/119

Commentaires

Tx → Ty : Tx est un prédécesseur direct de Ty . Ex. T1 → T2

Tx < Ty : Tx est un prédécesseur direct ou indirect de Ty . Ex. T1 < T4





- page 99/119

Ordonnancement de tâches dépendantesA. Contraintes de précédence

Ti → Tj si Tj doit attendre la fin de l’exécution de Ti pour commencerson exécution.

Si A précéde B alors {(1) rB ≥ rA, (2) si A périodique alors B l’estégalement et (3) priorité(A) > priorité (B)}





- page 100/119

Contraintes de précédence et ’Rate Monotonic’

Idée : Une tâche ne doit pas commencer avant son prédecesseur, et nedoit préempter son successeur.

dans le cas de l’ordonnancement selon “RM”, on transforme hors lignel’ensemble des tâches liées par une contrainte de précédence en unens. de tâches indépendantes pour lesquelles le test d’acceptabilité de“RM” est valide, en faisant :

calcul des dates de réveil : r∗i = max{ri , r∗pred } avec r∗pred date de réveil dela tâche précédant la tache i .et Si A et B ont même période avec A qui précéde B alors priorité (A) >priorité (B)





Precedence C∗i r∗i P∗i—————– ———- ———– ————

/0 -> T∗i Ci ri Pi

—————– ———- ———– ————T∗j -> T∗i Ci max(ri , r∗j ) Pi et > P∗j

—————– ———- ———– ————T∗j -> T∗iT∗k -> T∗i Ci max(ri , r∗j , r∗k ) Pi et max(P∗j , P∗k )

—————– ———- ————— ——————-

Tj

Tk

Ti

FIGURE: graphe 3 noeuds





- page 101/119

Exemple/Exercice : précédence avec RM

T1*

T2*

T3*

T4*

T5*

FIGURE: exemple de précédence





tache Ci ri Pi r∗i—————– ———- ———– ———— ————

T∗1 1 0 12 r∗1=r1=0—————– ———- ———– ———— ——————–

T∗2 2 5 14 r∗2=r2=5—————– ———- ———– ———— ——————–

T∗3 2 0 10 r∗3=max(r3,r∗1)=max(0,0)=0—————– ———- ———– ———— ——————–

T∗4 1 0 8 r∗4=max(r4,r∗1,r∗2)=max(0,0,5)=5—————– ———- ———– ———— ———————–

T∗5 3 0 16 r∗5=max(r5,r∗3,r∗4)=max(0,0,5)=5—————– ———- ————— ——————- ——————–

Calcul des r∗i





tache Ci ri Pi P∗i—————– ———- ———– ———— ————

T∗1 1 0 12 P∗1=P1 -> 12—————– ———- ———– ———— ——————–

T∗2 2 5 14 P∗2=P2 -> 14—————– ———- ———– ———— ——————–

T∗3 2 0 10 P∗3=(P3=10) et > (P∗1=12) -> 13

—————– ———- ———– ———— ——————–T∗4 1 0 8 P∗4=(P4=8) et > max(P∗1=12,P∗2=14) -> 15

—————– ———- ———– ———— ———————–T∗5 3 0 16 P∗5=(P5=16) et > max(P∗3=13,P∗4=15) -> 16

—————– ———- ————— ——————- ——————–

Calcul des P∗i





- page 102/119

Conservation des conditions après transformation

Somme(Ci /Pi <= n(21/n-1) :1/12+2/14+2/10+1/8+3/16 <= 5(21/5-1)

0.738 <= 0.743

—————————————————————

Somme(C∗i /P∗i <= n(21/n-1) :1/12+2/14+2/13+1/15+3/16 <= 5(21/5-1)

0.634 <= 0.743





- page 103/119

Contraintes de précédence et ’Earliest Deadline’

la prise en compte de la précédence est réaliséeen modifiant ri , di ,r∗i , d∗i , selon les formules :

r∗i = max{ ri , max(r∗pred + Cpred ) }, c-à-d la date de début d’une tâche doitêtre supérieure à toutes les dates de début de ses prédécesseursimmédiats augmentées de leurs durées d’exécution.d∗i = min{di , min(d∗succ - Csucc ) }, c-à-d pour une instance donnée,l’échéance d’une tâche doit être inférieure à toutes les échéances de sessuccesseurs immédiats diminuées de leurs temps d’exécution.





C∗i = prec. r∗i = prec. D∗i =—————– ———- ———– ———— ————

Ci /0 -> Ti ri Ti -> /0 Di—————– ———- ———– ———— ————

Ci Tj -> Ti max(ri , r∗j + Cj ) Ti -> Tj min(Di , D∗j -Cj )

—————– ———- ———– ———— ————Ci Tj -> Ti et Tk -> Ti max(ri , r∗j + Cj , r∗k +Ck ) Ti -> Tj et Ti -> Tk min(Di , D∗j -Cj , D∗k -Ck )

—————– ———- ————— ——————- ————

*

*

*

Tj

Tk

Ti

Tj*

Tk*

Ti*

FIGURE: graphes 3 noeuds pour EDF





- page 104/119

Exemple/Exercice : précédence avec EDF

T1*

T2*

T3*

T4*

T5*

FIGURE: exemple de précédence





tache Ci =C∗i ri Di r∗i—————– ———- ———– ———— ————

T∗1 1 0 12 r∗1=r1=0—————– ———- ———– ———— ——————–

T∗2 2 5 14 r∗2=r2=5—————– ———- ———– ———— ——————–

T∗3 2 0 10 r∗3=max(r3,r∗1+C1)=max(0,1)=1—————– ———- ———– ———— ——————–

T∗4 1 0 8 r∗4=max(r4,r∗1+C1,r∗2+C2)=max(0,1,7)=7—————– ———- ———– ———— ———————–

T∗5 3 0 16 r∗5=max(r5,r∗3+C3,r∗4+C4)=max(0,3,8)=8—————– ———- ————— ——————- ——————–

Calcul des r∗iNB : On commence par calculer r1, puis r2, puis .... r5





tache Ci =C∗i ri Di r∗i D∗i—————– ———- ———– ———— ———— ————

T∗1 1 0 12 =0 min(D1, D4*-C4, D3*-C3)= min(12,7,8) = 7—————– ———- ———– ———— ——————– ——————–

T∗2 2 5 14 =5 min(D2, D4*-C4) = min(14,7) = 7—————– ———- ———– ———— ——————– ——————–

T∗3 2 0 10 =1 min(D3, D5*-C5) = min(10, 13) = 10—————– ———- ———– ———— ——————– ——————–

T∗4 1 0 8 =7 min(D4, D5*-C5) = min(8,13) = 8—————– ———- ———– ———— ———————– ——————–

T∗5 3 0 16 =8 D5 = 16—————– ———- ————— ——————- ——————– ——————–

Calcul des D∗iNB : On commence par calculer D5, puis D4, puis .... D1





- page 105/119

Conservation des conditions après transformation

Somme(Ci /Di <= 1 : 1/12+2/14+2/10+1/8+3/16 <= 1

0.738 <= 1

—————————————————————

Somme(C∗i /D∗i <= 1 : 1/7+2/7+2/10+1/8+3/16 <= 1

0.941 <= 1





- page 106/119

Ordonnancement de tâches dépendantesB. Tâches partageant des ressources critiques

Problèmes :Evaluer le temps de réponse d’une tâcheInversion de priorité : apparaît quand une tâche A est retardée par unetâche moins prioritaire B (car A a demandé une ressource déjà détenuepar C, moins prioritaire que A et B)Interblocage (la tâche A détient la ressource R1 et demande la ressourceR2. En même temps, la tâche B détient la ressource R2 et demande R1).





R1

R2 R1

R2

Ri

la ressource Ri

une tache demande

Interblocage !

temps

temps

Figure : probleme d’interblocage

=> une solution : les classes ordonnees (chaque tache demande les ressources dans l’ordre)

temps

temps

R1

R2

R2

R2R1,R2

Fin de T1

T1

T2

T1

T2

Fin de T2

R1,R2

Liberation de Ri

Ri

Prio(T1) > Prio(T2)

FIGURE: Exemple de problème d’interblocage et une solution





R1 R1

R1 R1

T1

T2

T3

T4

sans ress. critique

avec ress. critique

RiRi

temps

temps

temps

temps

On a : Pri(T1) > Pri (T2) > Pri(T3) > Pri(T4)

demande ress. crit.liberation ress. crit.

FIGURE: Exemple du problème d’inversion de priorité





- page 107/119

Protocoles prenant en compte les ressources partagées

Héritage de priorité (PIP, Priority Inheritance Protocole) : résoud le problèmed’inversion de priorité : la tâche en section critique hérite de la plus hautepriorité parmi celles des tâches en attente (bloquées). La durée de l’attente destâches peut être très grande (car l’interblocage n’est pas résolu).

Priorité plafond (PCP, Priority Ceiling Protocol) : Limite la durée maximale deblocage des tâches à la durée d’une section critique et prévient lesinterblocages (deadlock). L’idée est que chaque ressource se voit affectée unepriorité égale à celle de la tâche de plus haute priorité qui va y accéder.





T1

T2

T3

R1 R2

R2

R2R1

R1 R1

R2

temps

temps

temps

tache elueRi

Ri

demande ress. crit. libration ress. crit.

heritage prio. de T2 heritage prio. de T1

tache occupant la ress. R2

tache occupant la ress. R1

tache occupant la ress. R1 et R2

FIGURE: Solution au pb d’inversion de priorite avec PIP





FIGURE: Solution au pb d’inversion de priorite avec PCPUniversité du Havre - UFR ST - LITIS - Équipe STI Systèmes temps réel et Ordonnancement - B. Sadeg




- page 108/119

Situations de surchargeQuelques éléments

quand la charge du processeur devient telle qu’il est impossible de respectertoutes les échéances

Ex. EDF et RM –> mauvaises performances en situations de surcharge

Eviter ces fautes temporelles => plusieurs politiques, qui se basent sur desmodèles de tâches plus élaborés





- page 109/119

Tolérance aux surcharges pour tâches périodiques

1. Méthode du mécanisme à échéance

2. Méthode du calcul approché





- page 110/119

Méthode du mécanisme à échéance

Chaque tâche = version primaire et version secondaire

Version primaire : fournit un résultat avec une bonne QdS mais au bout d’untemps indéterminé.

Version secondaire : fournit un résultat acceptable en un temps borné (connu àl’initialisation)





- page 111/119

Méthode du mécanisme à échéancealgorithme de tolérance aux fautes

Doit assurer le respect des échéances soit par le primaire, soit par lesecondaire.

Si le primaire et le secondaire sont exécutés => le résultat du primaire est utilisé.

L’ordonnancement consiste en la juxtaposition d’une séquence des primaires etd’une séquence des secondaires et d’une régle de décision pour commuter del’une à l’autre.

Il existe 2 politiques : 1ère chance et 2ème chance





- page 112/119

Tâches périodiques-Mécanisme à échéance : politque 1ère chance

politque 1ère chance

Priorié(Secondaires) > priorité (Primaires) => Primaires ordonnancéesdans les temps creux des secondaires associées

politque 2ème chance

Priorié(Primaires) > priorité (Secondaires) => Primaires exécutées avantleurs secondaires associées, lesquelles sont ordonnancées plus tard.Si l’exécution du la primaire réussit, la secondaire n’est pas exécutée.





- page 113/119

Méthode du calcul approché

Chaque tâche = partie obligatoire + partie optionnelle

Partie obligatoire : fournit un résultat approché et doit s’exécuter avantl’échéance.

Partie optionnelle : affine le résultat et s’exécute s’il reste assez de temps avantl’échéance.





- page 114/119

Éléments sur la tolérance aux surcharges pour tâches quelconques

En plus de l’échéance, ces politiques prennent encompte le critèredimportance d’une tâche, qui définit son caractère primordial dans l’application=> 2 tâches de même échéance peuvent avoir des importances différentes.

Ordonnancement à importance : à chaque réveil de tâche (périodique ou non),un test de garantie définit si la nouvelle tâche engendre une faute temporelle ounon.

Ce test est basé sur la laxité dynamique du système LP(t), qui devient négativesi une surcharg est détectée.





- page 115/119

Quelques éléments

Systèmes temps réel et répartis : Communication intra et inter sites. Envoi demessages. Problème : respecter les temps de transfert des messages enbornant les délais.

Un message peut être caractérisé par :

sa criticité (criticality ) : ce sont les contraintes de temps associées aumessagesa longueur : nombre d’octets composant le message. Les messages sonttransmis trame par trame sur le réseau. La longueur d’une trame = f(typede réseau)son type : synchrone, asynchroneson adresse de destination





- page 116/119

Protocoles

Plusieurs protocoles sont définis, en fonction du type de réseau :

- Réseau à commutation de paquets : chaque station est reliée au réseauet ne connait pas les protocoles utilisés pour communiquer à l’intérieur duréseau. La station établit une connexion selon un contrat lui garantissantune certaine QoS (taux de perte, délai max, ...). La station (considéréecomme un abonné) s’adresse au noeud (commutateur ATM par exemple)auquelle elle est raccordée, et le noeud se charge du transfert. Lesstations ne rentrent pas en conflit.- Réseau à accès multiple : Les stations connectées au réseau contrôlentl’accès au réseau via une technique MAC (Medium Access Control)implantée sur chaque station. L’accès au médium est soit par compétition,soit par consultation (jeton). Les mécanismes d’ordonnancement desmessages sont implantées dans les stations (pour respecter les CT)





- page 117/119

Types d’ordonancements

Ordonnancement des messages : les techniques d’ordonnancement sontadaptées de celles des tâches (ED, RM, notamment)

Pour ordonnancer les tâches, on doit connaître leurs temps d’exécution. Pourordonnancer les messages, il faut connaître leurs temps de transmission. Ladurée de transmission est fonction de la taille du message, du débit et de lalongueur du réseau, du format des trames-réseau utilisées et du protocole.Exemple : pour le bus à jeton, la durée de transmission d’un message de noctets est 96+8xn µs (on considère que les adresses sont codées sur 2 octets,un seul octet est utilisé comme information pour la trame, on néglige le délaiinter-trames. Le délai de transmission du jeton est 96 µs)





- page 118/119

Exemple : Bus à jeton

Ensemble des station = anneau logique. Le droit d’émettre est réservé à uneseule station : celle qui a le jeton. Quand une station a le jeton, elle émet destrames pendant une durée fixée, puis transmet le jeton. Le bus à jeton peutfonctionner avec ou sans priorités. Des paramètres sont utilisés : temps deposssession du jeton, 3 compteurs de rotation du jeton, notamment.Avec tous ces éléments, des protocoles spécifiques sont définis pourordonnancer les tâches et les messages dans un système distribué.





- page 119/119

Les SGBD Temps Réel

Systèmes de gestion de bases de données permettant de respecter :

Les contraintes logiques de la base de données (respecter les contraintesd’intégrité), etSes contraintes temporelles (Chaque transaction doit respecter sonéchéance)


Documents

Systèmes temps réel et Ordonnancement - B. Sadeglitis.univ-lehavre.fr/~sadeg/enseignement/Master-Rech/1-cours-str... · Systèmes temps réel et Ordonnancement - B. Sadeg Université