Institut de Recherche en Informatique de Toulouse | IRIT - … · 2010-03-30 · essentielle. Le résultat ne sert plus à rien une fois le deadline passé. (définition alternative

Introduction aux systèmes temps réel (Partie 1)

Iulian Ober IRIT www.irit.fr/~Iulian.Ober

2 avril 07 – Iulian Ober – Introduction aux systèmes temps réel

Définition

Systèmes dont la correction ne dépend pas seulement des valeurs des résultats produits mais également des délais dans lesquels les résultats sont produits

!! le système doit répondre à des stimuli externes sous un délai spécifié

!! L’absence de réponse est aussi grave qu’une réponse erronée, voire plus

Exemples : !! contrôle de véhicules (automobiles, trains, avions…), !! robotiqe !! systèmes militaires de contrôle / commande !! contrôle du trafic (aérien, terrestre) !! contrôle de processus industriels !! ...


Exemples typiques Un système de contrôle du débit (*)

Pipe

Flow meter

Valve

Interface

Computer Time

Input flow reading

Processing

Output valve angle

(*) Source: “Real Time Systems and Programming Languages” © Alan Burns and Andy Wellings, 2001


Exemples typiques Un système de contrôle de la production (*)


Production Control System

Parts

Machine Tools Manipulators Conveyor Belt

Finished Products

Operator Console


Catégories de systèmes temps réel

"! Temps réel dur (hard real time)

"! Temps réel ferme (firm real time)

"! Temps réel mou (soft real time)


Temps réel dur

La réponse du système dans les délais est vitale. L’absence de réponse est catastrophique (plus qu’une réponse incorrecte)

utilité de la réponse

temps deadline

Exemples : contrôle aérien, contrôle d’une centrale nucléaire…


Temps réel ferme

La réponse du système dans les délais est essentielle. Le résultat ne sert plus à rien une fois le deadline passé.

(définition alternative : la pénalité de non-réponse est dans le même ordre de magnitude que la valeur de la réponse)

temps deadline

Exemples : transactions en bourse… (c’est subjectif : le temps réel ferme de l’un peut être le temps

réel dur de l’autre)



Temps réel mou

L’utilité de la réponse du système après les délais se réduit progressivement. Les pénalités ne sont pas catastrophiques.

temps deadline

Exemples : Video-on-demand, logiciel embarqué de votre téléphone, iPod, etc.



Classification – mot de fin

"! Un même système peut avoir des sous-systèmes TR-dur, TR-ferme ou TR-mou

"! …en fait, la fermeté est une caractéristique de chaque échéance (deadline)


Sommaire

"! Caractéristiques récurrentes des STR "! Notions de base en STR "! Types de problèmes soulevées "! Quelques résultats de base

En 2ème partie: "! Modélisation et développement

modèles, langages, architectures

"! Sûreté de fonctionnement et comment la prouver


Sommaire

"! Caractéristiques récurrentes des STR "! Notions de base en STR "! Types de problèmes soulevées "! Quelques résultats de base

En 2ème partie: "! Modélisation et développement

modèles, langages, architectures

"! Sûreté de fonctionnement et comment la prouver


Cas typique : le contrôleur

Les systèmes temps réel sont souvent embarqués dans un équipement spécialisé, leur but étant de contrôler l’équipement et/ou son environnement

!! Environ 99% des processeurs produits dans le monde sont dédiés aux systèmes embarqués

Contrôleur temps réel

(matériel + logiciel)

capteur

capteur

actuateur

actuateur

environnement logique du STR

environnement réel


Systèmes réactifs

système ouvert répondant constamment aux sollicitations de son environnement en produisant des actions sur celui-ci

"! par opposition : systèmes transformationnels (e.g., indexation d’une base de données…)

"! abstraction => système qui tourne à l’infini

"! vie du système divisée en modes d’exécution (e.g., sol, décollage, croisière, …)

contrôleur (STR)

senseur

senseur

actuateur

actuateur environnement

réel


Contraintes temporelles

"! sont souvent dérivées de lois physiques "! se présentent souvent sous forme de

fréquences E.g., pour contrôler un avion en croisière à la vitesse

V, il faut ajuster la position des gouvernes à la fréquence ! => le contrôleur doit produire une sortie vers actuateurs toutes les 1/! sec. => les calculs de chaque cycle doivent terminer en moins de 1/! sec.


Concurrence

La tâche du système se décompose souvent en plusieurs activités, qui doivent parfois être exécutées en parallèle.

!! …parce que l’environnement est déjà parallèle: quand le vent bat, la gravitation ne s’arrête pas…

!! ça peut être implanté par "! des tâches concurrentes sur un mono-processeur "! un système réparti (avec en plus de la concurrence dans

les nœuds)

!! les ! activités sont plus ou moins critiques ordinateur de bord de votre voiture gère : ESP, ABS, auto-

radio…


PRÉDICTIBILITÉ

« LA » caractéristique requise avant tout d’un système temps réel: !! sous un ensemble d’hypothèses concernant la

charge (e.g., fréquence des entrées) et les erreurs non-contrôlables (e.g., fréquence des erreurs de bit sur le bus), arriver à prouver que…

!! …toute les contraintes (notamment les délais) sont respectées…

!! …au moins pour les tâches critiques du système

Que préférez-vous: un ordinateur de bord qui déclanche l’ABS à 1ms du blocage dans 99% de cas, ou un qui le déclanche à 10ms, mais dans 100% de cas ?


Systèmes embarqués

Cela impose des contraintes supplémentaires "! Haute disponibilité requise

!! resets coûteux ou impossibles !! updates – idem

"! Capacités de calcul et stockage prédéterminées et souvent limitées !! les limites sont toutefois très variables

e.g. téléphone GSM vs. satellite militaire "! Autres contraintes non-fonctionnelles

!! e.g., consommation (durée de vie des batteries),…

!! Processeurs et couches système personnalisés !! overhead dans le processus de développement


Autres caractéristiques(*)

"! Grande taille et complexité parfois !! E.g. millions of LoC for the ISS !! => importance de la modularité

"! Interaction avec du matériel dédié !! Nécessité de programmer et d’interagir avec des pilotes à

un niveau abstrait et sûr "! Échantillonnage des entrées

!! => manipulation des valeurs continues dans un domaine discret

!! algorithmes numériques, gestion d’erreurs "! Rapidité et efficacité parfois importante



Malentendus fréquents (*)

"! système temps réel = système rapide et performant "! la programmation temps réel veut dire assembleur,

interruptions et pilotes "! il n’y a aucune science derrière le développement des

systèmes temps réel, tout est une question de bidouillage

"! toutes les problèmes du temps réel ont été déjà résolus dans d’autres domaines de l’informatique

"! …et l’augmentation de la vitesse des processeurs va résoudre ce qui reste

(*) inspiré de J. Stankovic, « Misconceptions about real-time computing », IEEE Computer, 21(10):10--19, Oct. 1988


Sommaire

"!Caractéristiques récurrentes des STR "!Notions de base en STR "!Types de problèmes soulevées "!Quelques résultats de base


Programmation concurrente

Motivation: !! le système interagit avec des parties

concurrentes de son environnement (le monde réel)

!! reconnaître le parallélisme dans le programme mène à une structure plus naturelle "! dans le cas contraire, le programme est rendu séquentiel

de façon plus ou moins arbitraire "! …par exemple en exécutant une boucle:

TQ vrai FAIRE si evt1 : exécute tâche 1 si evt2 : exécute tâche 2 … FIN TQ

!! la structure n’a rien à voir avec le pb. initial !! la décomposition du problème est plus difficile !! la parallelisation sur plus d’un processeur est difficile


Un exemple temps réel simple(*)


T

S

P Interrupteur

ADC

ADC

DAC Ecran

Brûleur

Thermocouple

Capteur pression

Valve

Objectif: garder la température et la pression dans un domaine prédéfini


Architectures possibles

"! un programme séquentiel unique " on ignore la concurrence logique de T, P et S " aucun support OS n’est nécessaire

"! T, P et S sont les tâches d'un programme concurrent (tâches OS ou tâches dans un langage concurrent comme Java, Ada). " la concurrence logique de T, P et S est préservée " un OS ou un run-time est nécessaire.


Solution séquentielle

class controleur { CT : Capteur_Temp; CP : Capteur_Pres; OT : Commande_Temp; OP : Commande_Pres; ... int main(String[] args) { while(true) { // boucle infinie CT.read(); // lecture de l’ADC (bloquant) ConversionTemp(CT, OT); // calcul OT.write(); // envoi au brûleur CT.writeToScreen(); // affichage

CP.read(); // lecture de l’ADC (bloquant) ConversionPression(CP, OP); // calcul OP.write(); // envoi à la valve CP.writeToScreen(); // affichage } } }


Discussion

"! la lecture de température et de pression se fait au même rythme

"! on peut y remédier avec des compteurs "! mais dans ce cas, on a probablement besoin de fragmenter

ConversionTemp et ConversionPression pour effectuer le travail

!! exemple : "! ConversionTemp doit s’exécuter toutes les 1ms et prend 0.5ms "! ConversionPression doit s’exécuter toutes les 2ms et prend 1ms !! c’est faisable, mais il faut sectionner ConversionPression en 2

tranches (égales!)

"! pendant qu’on fait CT.read(), on ne peut pas s’occuper de la pression

! si le capteur température tombe en panne, on ne regarde plus le capteur pression non plus!!


Solution séquentielle améliorée

class controleur { CT : Capteur_Temp; CP : Capteur_Pres; OT : Commande_Temp; OP : Commande_Pres; TempReady : boolean; PresReady : boolean; ... int main(String[] args) { while(true) { // boucle infinie if(TempReady) { // polling -- attente active CT.read(); ConversionTemp(CT, OT); OT.write(); CT.writeToScreen(); } if(PresReady) { CP.read(); ConversionPression(CP, OP); OP.write(); CP.writeToScreen(); } }


Discussion

"! solution plus fiable "! …mais terriblement inefficace – ça consomme

le processeur tout le temps pour regarder 2 booleens

"! la fragmentation du calcul reste nécessaire si les fréquences de réponse l’impose

"! difficile à généraliser pour des systèmes plus conséquents


Solution dans un langage concurrent (Java)

class T implements Runnable { void run() { while(true) { CT.read(); ConversionTemp(CT, OT); OT.write(); CT.writeToScreen(); } }

class P implements Runnable { void run() { while(true) { CP.read(); ConversionPres(CP, OP); OP.write(); CP.writeToScreen(); } }

class root { int main(String[] args) { Thread t1 = new Thread( new T() ); Thread t1 = new Thread( new P() ); }


Solution dans un langage concurrent (SDL)

P

T

CP

CT

OP

écran

OT


Solution dans un langage concurrent (SDL)

process T

CT(ct)

Calcul(ct,ot)

OT(ot)

wait

OEcran(ct)

wait


Discussion

"! les tâches sont identifiées, la logique de l’application est apparente dans la structure du programme

"! la communication et la synchronisation sont souvent plus faciles à exprimer qu’en faisant des appels OS

"! quand une tâche est suspendue dans un read, l’autre peut exécuter

"! si les deux sont suspendues, l’attente est passive (ne consomme pas de CPU)


Conclusion sur la prog. concurrente

"! les domaines d’application des systèmes temps réel sont généralement parallèles

"! la concurrence disponible directement dans le langage de programmation rend la vie plus facile

"! sans concurrence, un système TR est en général une boucle infinie !! la structure de la boucle ne montre pas la structure

logique des tâches !! on ne peut pas préciser les caractéristiques des

tâches (période, temps de réponse) sans les identifier

!! la solution de passe pas à l’échelle de grandes applications


Concept de tâche

"! le système est une collection de tâches autonomes exécutant en parallèle (parallélisme logique)

"!une tâche !! (statiquement) est décrite par un programme séquentiel !! (à l’exécution) a son propre fil de contrôle !! peut communiquer et partager des ressources avec

d’autres tâches "! l’interprétation varie au cours du cycle de

développement: !! analyse / conception : tâche = une série d’actions

déclanchée par un stimulus venant d’un capteur ou par l’arrivée d’une échéance temporelle

!! implémentation : tâche = processus ou thread ou co-routine ou objet actif ou …


Types de tâches "! Tâches périodiques

!! Déclanchées par le temps. Caractéristiques connues à l’avance. !! Ti est caractérisée par:

-! pi – période d’arrivée -! ci – temps de calcul au pire cas (WCET) -! di – échéance relative à l’arrivée

!! Exemple : Guidage-Navigation-Contrôle (GNC) dans un AOCS (ex. Ariane-5)

"! Tâches apériodiques !! Déclanchées par un événement extérieur. Caractéristiques

partiellement non-connues. !! Ti est caractérisée par:

-! ci – temps de calcul au pire cas (WCET) -! di – échéance relative à l’arrivée -! (éventuellement) ai – temps d’arrivée / contraintes

"! Tâches sporadiques !! tâches apériodiques avec temps minimum entre arrivées connu. !! Exemple : Séparation des étages dans un lanceur (Ariane-5)


Le modèle simplifié d’une tâche

halted

suspended executing

arrival

dispatch

preempt

done

blocked

attente ressource

ressource acquise


Contraintes sur les tâches

"! échéance (deadline) "! contraintes de ressources partagées

!! ressource en lecture : accès partagé !! ressource en écriture : accès exclusif

"! contraintes de précédence !! T1 ! T2 : T2 ne peut commencer que si T1 a déjà

terminé

"! contraintes de criticité !! ex. 5 niveaux (A-E) dans DO178B !! redondance pour la tolérance aux fautes !! …


Sommaire



Problèmes rencontrés

"! allocation de ressources !! ordonnancement, tolérance aux fautes, récupération

de ressources…

"! architecture !! caractéristiques du processeur, du système de

communication, des E/S

"! méthode de développement !! spécification de besoins, validation, langages et

modèles


Allocation de ressources

Problème principal : l’ordonnancement !! allocation des tranches de temps processeur !! i.e., les moments où une tâche est livrée au

processeur (dispatch) / suspendue (preempt)

Objectif de l’ordonnancement : assurer le respect des échéances de manière prouvable Une méthode d’ordonnancement est caractérisée par: !! le critère de test d’ordonnançabilité (offline) !! la méthode effective de construction de l’emploi du

temps (schedule) du processeur (online ou offline)


Problèmes d’architecture

Pour supporter un logiciel temps-réel, l’architecture (matériel + OS) doit être prédictible:

!! temps d’exécution des instructions !! changement de contexte !! opérations avec la mémoire !! traitement des interruptions !! …

Implications !! Les mémoires cache et les processeurs supérscalaires

sont évités !! La tolérance aux fautes est supportées dans le matériel

(self-checking, voting and monitoring…) !! Support pour des communications rapides et prédictibles

(e.g., pas de Ethernet, ou alors amélioré)


Problèmes d’architecture (cont)

"! Support pour algorithmes d’ordonnancement dans l’OS, préemption rapide, contextes multiples, priorités…

"! Fault Containment Regions "! gestion des interruptions "! synchronisation d’horloges "! etc.


Problèmes de méthode de développement

"! Spécification des besoins !! fonctionnelle : ce que le système doit calculer !! non-fonctionnelle : e.g., contraintes temporelles !! la spécification des deux aspects doit être conjointe

et suffisamment précise (formelle?) (pour permettre d’examiner ses implications et ses propriétés indépendamment de l’implantation)

"! Conception et développement !! constructions de langage pour gérer le temps, les

ressources !! support de la communication et de la concurrence !! constructions pour supporter la vérification du

critère d’ordonnançabilité à la compilation


Sommaire



Prédictibilité temporelle des STR

Prédictibilité = assurer a priori que toutes les tâches respectent leurs échéances

Les 2 piliers sont:

!! l'analyse de pire temps d'execution (WCET – Worst Case Execution Time)

"! problèmes: !! liés au programme (structure dynamique – boucles,

branches…; appels externes – OS, MW…) !! liés au matériel (cache, pipeline, exécution prédictive…)

"! méthodes: analyse statique de programmes, interprétation abstraite, analyse dynamique, hybride…

!! l'ordonnancement des tâches


Un modèle basique

"! Le système consiste d’un ensemble fixé de tâches

"! Toutes les tâches sont périodiques

"! les tâches sont indépendantes (pas de communication/synchronisation)

"! on suppose un temps de changement de contexte zéro


Ordonnancement cyclique

"! Conception concurrente, mais implantation séquentielle cyclique

"! Les tâches sont mappées sur un ensemble de procédures

Exemple:

Tâche Pt Ct

A 25 10

B 25 8

C 50 4

D 50 6

25 50

cycle mineur

cycle majeur


Implémentation

!! interruption horloge: période = cycle mineur

while(true) { A(); B(); C(); attendre interruption; A(); B(); D(); attendre interruption; }


Discussion

pour: !! pas de processus à l’exécution

"! espace mémoire partagé "! pas besoin de protection de régions critiques –

accès concurrent impossible

!! exécution complètement déterministe

contre: !! impossible d’introduire des activités sporadiques !! cycles « longs » difficiles à gérer !! nécessité de découper des calculs longs sur

plusieurs cycles mineurs ! erreurs !! emploi de temps difficile à obtenir (NP-hard)


Ordonnancement préemptif ou non

"! Ordonnancement non-préemptif !! quand une tâche commence, elle va jusqu’au bout !! … mais des fois c’est impossible de tenir les délais:

"! Ordonnancement préemptif !! la transition préempt est permise;

une tâche peut être interrompue et reprise plus tard !! la préemption a lieu quand une tâche de plus grande priorité

arrive !! permet une meilleure occupation du processeur !! …donc permet de rendre ordonnançable des systèmes qui ne le

sont pas autrement !! mais : implique une surcharge pour le changement de contexte

Tâche Pt Ct Dt

A 1000 25 1000

B 10 1 2

Chaque fois que A exécute, B va rater 2

fois son échéance


Ordonnancement préemptif à priorité fixe (FPPS)

"! l’approche la plus utilisée dans les systèmes réels

"! chaque tâche a une priorité fixe, statique, calculée off-line. (Toutes les instances de la tâche ont la même priorité.)

"! à tout moment, la tâche la plus prioritaire a le CPU !! changements de contexte:

-! préemption : quand une tâche arrive, si elle est plus prioritaire que la tâche en cours

-! quand la tâche en cours se termine (" idle)


Comment affecter les priorités

Exemple : la centrale nucléaire la moins chère au monde(*)

-! tâche 1 : barres de contrôle (cœur du réacteur) -! tâche 2 : vanne du lave-vaisselle (cafeteria)

(*) thanks to D.C. Locke for this example

Tâche Pt Ct

T1 4 1

T2 1 0.02

T1 > T2

1

!!

2 3 4

!!






Tâche Pt Ct

T1 4 1

T2 1 0.02

T2 > T1

1 2 3 4






Tâche Pt Ct

T1 4 1

T2 1 0.02

Conclusion: La priorité n’est pas basée sur l’importance, mais uniquement sur les contraintes temporelles !


Notion d’ordonnanceur optimal

Définition: Un algorithme d’ordonnancement est appelé optimal (pour une classe de problèmes*) quand il produit un emploi du temps processeur faisable chaque fois qu’un autre algorithme d’ordonnancement peut le faire.

* classe de problèmes: par exemple, ensemble de tâches cycliques sans interactions, avec FPPS


Ordonnancement « Rate Monotonic » (RMS)

Résultat : Il existe une politique optimale avec priorités statiques, c’est RMS :

!! affecter les priorités aux tâches dans l’ordre de leur périodes: les tâches avec des périodes plus courtes sont plus prioritaires.


Exemple

Tâche Pt Ct

A 10 5

B 20 6

C 50 7

A > B > C

5

5

10

5

20 30 40 50

1

4

5

5

5

1

3

5

5


Critère statique d’ordonnançabilité RMS

Théorème : Un ensemble de n tâches périodiques indépendantes est ordonnançable par RMS indifféremment de l’ordre d’arrivée si :

Utilisation du processeur


Critère statique d’ordonnançabilité RMS

"! la condition est restrictive: U(1) = 1 U(2) " 0.828 U(3) " 0.779 U(4) " 0.756 U(5) " 0.743 U(6) " 0.734 pour n ! " , U ! ln 2 " 69%

U(n)


Application du critère

Tâche Pt Ct

A 10 5

B 20 6

UA = CA / PA = 0.5

UB = CB / PB = 0.3

U = UA + UB = 0.8 <U(2)

l’ensemble est ordonnançable

!


Application du critère

Tâche Pt Ct

A 10 5

B 20 6

C 50 7

UA = CA / PA = 0.5

UB = CB / PB = 0.3

UC = CC / PC = 0.14

U = UA + UB + UC = 0.94 > U(3) " 0.779


Améliorer le critère

"! La condition est suffisante, mais pas nécessaire

"! Il existe un test précis:

Théorème: Si un ensemble de n tâches indépendantes avec priorités fixes affectées par RMS respecte la 1ère échéance de chaque tâche quand toutes les tâches sont démarrées en même temps (à T0), alors l’ensemble est toujours ordonnançable.


Un cas particulier

Tâche Pt Ct

A 10 5

B 20 10

UA = CA / PA = 0.5

UB = CB / PB = 0.5

U = UA + UB = 1

pourtant :

5

5

10

5

20 30 40 50

5 OK!


Un cas particulier

De manière générale : un ensemble de tâches périodiques harmoniques est ordonnançable si l’utilisation du processeur est # 100%

Tâches harmoniques : {T1, T2,…, Tn } avec P1# P2#… # Pn et #i,j, i<j " Pi | Pj

Tâche Pt Ct

A 10 5

B 20 10

UA = CA / PA = 0.5

UB = CB / PB = 0.5

U = UA + UB = 1


Application à l’exemple

Tâche Pt Ct

A 10 5

B 20 6

C 50 7

A > B > C

5

5

10

5

20 30 40 50

1

4

5

5

5

1

3

A ok

B ok

C ok


Ordonnancement à priorités dynamiques Earliest Deadline First (EDF)

Objectif : obtenir une meilleure occupation du processeur.

Politique EDF (définition) : à tout moment, la tâche qui a l’échéance la plus proche occupe le CPU.

Remarques: !! toutes les instances d’une tâche n’ont pas la même priorité

-- priorité dynamique !! la priorité d’une tâche reste fixe par rapport aux priorités

des tâches qui sont déjà admises à exécution quand elle arrive

!! préemption : quand une tâche arrive, si elle a l’échéance plus proche que la tâche en cours


Critères d’ordonnançabilité EDF

[si di = pi] Condition nécessaire et suffisante: un ensemble de n tâches est ordonnanceable par EDF ou LLF si l’utilisation du processeur est inférieure à 100%

!! difficile de faire mieux ! (sans déborder)

[si di < pi] Condition suffisante mais pas nécessaire:

!! analyse du temps de réponse plus difficile qu’en RMS


2

Comparaison RMS - EDF

Tâche Pt Ct

A 5 2

B 7 4

EDF 2

5

4

2

4

2

1

2

10 15 20

3

2

4

2

25

RMS

5 10 15 20 25

2

3

7

!!!

Ordonnançable avec EDF, pas avec RMS !


Comparaison RMS - EDF

"! RMS/DMS sont des algorithmes optimaux avec priorités statiques

"! EDF/LLF sont des algorithmes optimaux avec priorités dynamiques

"! RMS : des nombreux résultats existent et sont largement utilisés en pratique.

"! EDF offre des utilisations de processeur supérieures, donc une meilleure ordonnançabilité, mais il est plus difficile à implémenter et instable en cas de surcharge


Extensions possibles du modèle basique

"! temps de changement de contexte ! zéro

"! Toutes les tâches ne sont pas périodiques

"! les tâches ne sont pas indépendantes: elles communiquent et se synchronisent

"! …


Interactions et blocage

"! on considère les interactions par ressources protégées (e.g., moniteurs, protection par sémaphores, etc.) !! une tâche peut être suspendue en attente d’une

action par une autre tâche

"! anomalie : si A > B et A est bloqué par une ressource détenue par B. B s’exécute pendant que A attend. (inversion de priorité)


Exemple

A > B > C, ressource partagée R

A

B

C block R

wait R

release R

block R échéance

ratée


Un exemple réel

La mission Mars Pathfinder, 4 Juillet 1997 !! système ordonnancé par RMS, sur VxWorks !! inversion selon le modèle précédent entre:

"! T1 tâche du bus "! T2 tâche de communication sol "! T3 tâche de recueil d’information météorologiques "! R = le bus (mutex)

!! corrigé à distance en activant PCP


Discussion

A

B

C block R

wait R

release R

block R

C bloque A: blocage nécessaire pour

l’intégrité de R

B bloque A: pas nécessaire

! nécessité de politiques pour minimiser le temps de blocage et le rendre déterministe


Priority inheritance protocol

Quand une tâche TH est bloquée en attente d’une ressource utilisée par une tâche TL , alors TL hérite temporairement la priorité de TH.

Quand TL libère la ressource, elle reprend sa priorité normale.

A

B

C block R

wait R

3

release R

block R

C passe à priorité 3

L’héritage doit être transitif: si C devient bloqué par D pendant qu’il bloque A, D hérite la priorité de A !


Calcul du temps de blocage

"! avec PIP, une tâche peut subir un blocage alors qu’elle n’utilise pas de ressource partagée :

A

B

C block R

wait R

release R

B est bloqué alors qu’un processus de moindre priorité s’exécute (C)

"! Soit :

util(k,i) =

si la ressource k peut être utilisée 1, par une tâche <i et par une tâche $ i

0, sinon


Calcul du temps de blocage

On suppose que pour toute ressource k, le temps de calcul entre acquisition et libération est C(k) (quelque soit la tâche qui)

!! e.g., k est une opération de moniteur et C(k) est son WCET

Le temps de blocage maximum pour une tâche de priorité i est:


Critère basé sur l’utilisation

On peut adapter le critère suffisant basé sur l’utilisation du CPU pour prendre en compte le temps de blocage Bi, en augmentant l’occupation du processeur de Bi/pi

Théorème: T1..Tn sont ordonnançables par RMS si


Ordonnancement : résumé

"! une politique d’ordonnancement est caractérisée par !! un algorithme pour allouer la ressource partagée (p.e.

CPU) !! une technique pour prédire le comportement au pire cas

de la politique

"! ordonnancement cyclique !! le système est programmé comme un ensemble de

procédures !! les appels sont groupés dans des cycles mineurs

(déclanchés par le temps). Au bout de plusieurs cycles mineurs, le schéma se répète (cycle majeur)

!! beaucoup d’inconvénients, résolus par des politiques préemptives à base de priorités


Ordonnancement : résumé

"! politiques à base de priorités fixes !! affectation optimale des priorités : RMS, DMS !! critère suffisant d’ordonnançabilité simple !! analyse de temps de réponse (critère nécessaire et

suffisant) flexible, peut prendre en calcul "! processus sporadiques "! temps de blocage causé par la synchronisation "! temps de changement de contexte "! etc.

!! implémentées en POSIX, Ada, RT Java, …

"! politiques à base de priorités dynamiques !! politiques optimales en mono-processeur: EDF, LLF !! meilleure occupation du processeur !! critère nécessaire et suffisant simple quand D # P !! implémentation plus complexe, instabilité en cas de

surcharge,…


Aller plus loin

"! en priorités fixes, l’analyse de temps de réponse peut être étendue pour couvrir: !! imprécision du moment d’arrivée des tâches (jitter) !! échéances arbitraires, en particulier D > P !! déphasage des tâches périodiques !! …

"! ordonnancement avec plusieurs niveaux de criticité

"! ordonnancement en milieu multi-processur !! EDF, RMS ne sont plus optimaux !! anomalie du multiprocesseur : une tâche qui finit plus

vite que prévu peut faire déborder une autre !!


STR : conclusions

"! systèmes dont la correction est définie par les résultats et aussi par les moments où ces résultats doivent être disponibles (échéances)

"! haute criticité ! besoins stricts de correction, sûreté de fonctionnement, prédictibilité

"! techniques employées !! programmation concurrente, synchronisation

(causes : environnement parallèle, système réparti) !! programmation des aspects temporels (attente,

interruption par temporisation,…) !! gestion des échéances par une politique

d’ordonnancement temps réel, prédiction du comportement au pire cas


STR : aller plus loin

Techniques employées (pas couvertes dans le cours) !! architectures matérielles prédictibles;

estimation du pire temps d’exécution (WCET) !! méthodes et langages d’analyse

"! formalisation des besoins et des propriétés du système !! méthodes et langages de conception

"! langages dédiés: langages à base de flots de données, langages à base d’automates ou commandes gardées, langages synchrones / asynchrones,…

!! techniques de validation et certification "! vérification formelle "! sélection de cas de test "! génération automatique de tests "! …

Documents

Institut de Recherche en Informatique de Toulouse | IRIT - … · 2010-03-30 · essentielle. Le résultat ne sert plus à rien une fois le deadline passé. (définition alternative