Introduction aux Systèmes Temps Réel

Nicolas NAVET

2010/2011

http://www.loria.fr/~nnavet

Introduction aux systèmes temps réel

Plan du cours

1. Systèmes temps réel : exemples et fondamentaux

2. Conception des applications temps réel : quelles techniques pour véri�er

le respect des contraintes ?

3. Ordonnancement : choix de la bonne séquence d'exécution des activités

du système ..

Introduction aux systèmes temps réel 1

Systèmes temps réel : introduction

4 Systèmes temps réel : correction logique et temporelle des

résultats

4 Contraintes temporelles sont issues de la dynamique du processus

contrôlé

4 Le plus souvent, les systèmes temps réel sont embarqués, c'est à

dire, physiquement liés au processus contrôlé

4 Ordonnancer c'est déterminer un ordre sur les activités d'un système

Introduction aux systèmes temps réel 2

Systèmes embarqués temps réel : exemples

4 Impact dans la société :

� le marché des systèmes embarqués ' architectures clients / serveurs + PC� Chaque jour, on utilise environ 80 processeurs de manière transparente

Introduction aux systèmes temps réel 3

X-by-Wire dans l'automobile

Introduction aux systèmes temps réel 4

Typologie des contraintes de temps

8 Contrainte de date au plus tard sur la �n d'exécution (ou contrainted'échéance - �deadline�)

8 Contrainte de type �(m, k) �rm� : respecter au moins m échéances toutes les kactivations

8 Contrainte de précédence entre tâches

8 Minimisation de la gigue sur les �ns d'exécution des tâches

8 Maximisation de la fraîcheur des données d'entrée d'un algorithme

8 Maximisation de la cohérence temporelle des données d'entrée d'un algorithme

4 On parle de contraintes de temps :

� strictes (hard real-time) : non-respect catastrophique� souples (soft real-time) : non-respect occasionnel sans conséquence� de type best e�ort : on fait pour le mieux ..

4 Ordonnancement est faisable ssi toutes les contraintes sont respectées

Introduction aux systèmes temps réel 5

Contraintes de bout-en-bout : un exemple

t

t

t

ressource (CPU ou réseau) utilisée

BV

réseau

CM

changement de vitesse

couple moteur effectivement réduit

τG

τL

τP

ΙR ΨR

τreaction

τt

τe δ

propa

τα

p_msgr

p_repr

τp_msg

τp_rep

Figure 1: Décomposition d'une contrainte de temps entre un changement de vitesseet la réduction du couple moteur associée

Introduction aux systèmes temps réel 6

Conception d'un système temps réel

Cahier des Charges (fonctionnalités et contraintes)

Architecture Matérielle Architecture Logicielle

Architecture Fonctionnelle

Architecture Opérationnelle

Evaluation de Performances

Contraintesrespectées ?

Remise encause dechoix deconception

Placement et Configuration

Architecture Validée

oui

non

− Modèles analytiques− Modèles de simulation− Prototypes, maquettes− Approches hybrides

4 Dans les systèmes temps réel, la véri�cation du respect des contraintes (=validationdu système) est cruciale ...

Introduction aux systèmes temps réel 7

Techniques de validation (1/2)

4 Observation sur prototypes :

+ pas d'hypothèse simpli�catrice

+ certaines contraintes ne peuvent être véri�ées que sur prototype

- construction, instrumentation longues et coûteuses

- résultats pire-cas sans validité

- intervient tard dans le cycle de vie

4 Modèles analytiques :

+ bien adaptés aux contraintes pire-cas et aux événements rares

+ validité du modèle véri�able

- hypothèses simpli�catrices fortes

- di�cultés de modélisation !

Introduction aux systèmes temps réel 8

Techniques de validation (2/2)

4 Modèles de simulation :

+ moins d'hypothèses simpli�catrices que les modèles analytiques

+ facilité de modélisation

- résultats orientés pire-cas ou événements rares généralement sans validité

- validité des modèles

4 Techniques hybrides :

� couplage de modèles analytiques et de simulation - ex : pro�l decommunication où les couches basses sont modélisées de façon analytique et lescouches hautes sont simulées

� co-simulation hardware / software - ex : on simule l'activation des tâcheset on exécute les tâches sur un processeur réel

Introduction aux systèmes temps réel 9

Classes d'ordonnancement

4 hors-ligne : séquence des exécutions est décidée à la conception puis �déroulée�pendant l'exécution

4 en-ligne : choix d'ordonnancement sont faits en-ligne, ils utilisent certaines carac-téristiques des tâches

4 préemptif (resp. non-préemptif) : une tâche peut être interrompue par uneautre + prioritaire

4 non-oisif (resp. oisif) : le processeur est nécessairement utilisé si il y a du travailen attente d'exécution

4 déterministe : le hasard n'intervient pas dans les choix d'ordonnancement

8 Une politique d'ordonnancement est un algorithme qui détermine en-lignel'activité à exécuter - propriétés requises : décidabilité et implémentabilité

8 Une politique est optimale si elle conduit à un ordonnancement faisable si il enexiste un

Introduction aux systèmes temps réel 10

Modèles de tâches

4 Les tâches sont apériodiques (une seule activation - on parle de jobs) ou, le plussouvent en temps réel, récurrentes

Caractéristiques de tâches récurrentes : τk,n est la nième instance de la tâcheτk avec

� Ak,n sa date d'arrivée : 0 6 Ak,1,6 . . . 6 Ak,n−1 6 Ak,n.

� Tk,ndef= Ak,n+1 − Ak,n est le temps interarrivée. Pour une tâche périodique

Tk,n = Tk ∀n ∈ N.

� Dk,n son échéance, l'échéance relativement à Ak,n est Dk,n, on a Dk,ndef=

Ak,n +Dk,n,� Ck,n son temps d'exécution sur la machine cible - en pratique di�cile à évaluer !

Modèles d'activation : périodique, sporadique (il existe un temps minimum entre2 activations de tâches) ou plus complexes : tâches multi-périodiques, tâches à tempsd'exécution alternés, tâches MPEG etc ...

Introduction aux systèmes temps réel 11

Le paradoxe du lièvre et de la tortue

8 Le processeur 1 (�lièvre�) sous FIFO est 10x plus rapide que le processeur 2 sous EDF(�tortue�)

8 Job A (Ctortue = 200, D = 220, A = 0) - Job B (Ctortue = 10, D = 15, A = 2)

Ordonnancement sur les processeurs �Tortue� et �Lièvre� (G. Le Lann)

4 Nécessité de faire les bons choix d'ordonnancement ... une analyse d'ordonnan-çabilité permet d'étudier la faisabilité du système

Introduction aux systèmes temps réel 12

Analyse d'ordonnançabilité par simulation

Principe : simuler le déroulement de l'ordonnancement du système pendant �unepériode� du système et véri�er que toutes les instances de tâches respectent leuréchéance.

Avantages :

� permet de traiter des politiques d'ordonnancement ou des modèles de tâches quiseraient di�ciles à analyser mathématiquement,

� requiert peu de connaissances en ordonnancement pour être mise en oeuvre.

Inconvénients :

� non utilisable pour des ensembles de tâches quelconques car la période du systèmeest au minimum un PPCM des périodes des tâches,

� comme pour tout modèle de simulation se pose la question de la validité /correction du modèle ...

Introduction aux systèmes temps réel 13

Analyse d'ordonnançabilité par test de faisabilité

Principe : appliquer une formule (close) qui en fonction des caractéristiques destâches décide de la faisabilité. Ex : faisabilité sous EDF ssi

∑ CiTi

6 1 avec Ti la

période et Ci le temps d'exécution de la tâche τi.

Avantages :

� simplicité de mise en oeuvre,� en général le calcul a une complexité faible : souvent le test est basé uniquement

sur la charge du système.

Inconvénients :

� n'existe pas pour toutes les politiques,� ne couvre pas tous les modèles de tâches : généralement tâches périodiques avecDk = Tk,

� il ne s'agit souvent que de conditions su�santes et non de conditions su�santeset nécessaires,

� en cas de non-faisabilité, ne donne pas d'indication sur les tâches qui posentproblèmes.

Introduction aux systèmes temps réel 14

Analyse d'ordonnançabilité par calcul

de bornes sur les temps de réponse

Principe : appliquer une formule de récurrence qui calcule itérativement les datesde �n d'exécution sur un morceau de trajectoire. Le morceau de trajectoire a étéconstruit/choisi de façon à contenir les plus grands temps de réponse que la tâcheconsidérée pourra recontrer.

Avantages :

� le calcul de bornes sur les temps de réponse est possible pour la quasi totalité despolitiques ayant un intérêt dans le temps réel,

� des modèles de tâches complexes peuvent être pris en compte,� en cas de non-faisabilité, des informations sont disponibles sur les tâches qui posent

problème.

Inconvénients :

� calculs parfois complexes algorithmiquement.

Introduction aux systèmes temps réel 15

Ordonnancement : la politique Earliest Deadline First (EDF)

Principe : “plus petite l’échéance, plus grande la priorité”

Propriétés : optimalité vis-à-vis de la contrainte d’échéance pour l’ordonnancementmono-processeur préemptif

Exercice : décider de la faisabilité des deux tâches périodiques τ1 (C1 = 2, T1 =5, D1 = 5, A1,1 = 0) et τ2 (C2 = 4, T2 = 7, D2 = 7, A2,1 = 0) sous la politique EDF.

0

τ2

τ1

10 20 30 40 50

Introduction aux systèmes temps réel, ENSEM 16

Ordonnancement : autres politiques de base

Fixed-Priority Preemptive (FPP) : toutes les instances d’une tâche possèdent lamême priorité (6=EDF). Allocation des priorités : Rate-Monotic (+petite la période,+grande la prio), Deadline Monotonic ou selon l’importance de la tâche.

Round-Robin : chaque tâche possède le CPU pendant un quantum de temps puisla tâche suivante prend la main

Ψk,n τ2,n

τ5,n

τ4,n

τ6,n

τ3,n

τ7,n τ1,n

Moins utilisées : Shortest Remaining Time First (optimale vis-à-vis du temps deréponse moyen), First-In First-Out (FIFO), Last-In First-Out (LIFO), ...

Introduction aux systèmes temps réel, ENSEM 17

Perspectives

4 L'informatique embarquée temps réel prend une place de + en + importante dansnotre société

4 De plus en plus de systèmes sont critiques du point de vue sécurité d'où l'importancede la validation ...

4 Sous des hypothèses de fonctionnement déterministe du système (pas d'erreurs detransmission, pas d'erreurs logicielles, temps d'exécution connu, ...), on sait véri�erla faisabilité d'un système temps réel

4 En pratique, des aléas peuvent survenir .. les approches de conception s'oriententvers

� validation probabiliste des contraintes (ex : distribution des temps de réponse)� intégrer les problématiques de sûreté de fonctionnement (ex : �abilité, disponibi-

lité,. . . )� avec pour objectif de se situer sous un certain seuil de risque jugé acceptable (ex :

10−9défaillance grave par heure de fonctionnement pour l'avionique)

Introduction aux systèmes temps réel 19