Systèmes Temps Réel

Prof: Dr Mohammed BOUSMAH

2014-2015

bousmah@[Link]
 Définition

SystèmeTemps Réel, c'est quoi ?

bousmah@[Link]
 Définition

En informatique, on parle d'un système temps

réel lorsque ce système est capable de
contrôler (ou piloter) un procédé physique à
une vitesse adaptée à l'évolution du procédé
contrôlé.

bousmah@[Link]
Définition

bousmah@[Link]
Définition

bousmah@[Link]
Définition

bousmah@[Link]
Définition

bousmah@[Link]
Classification des STR

bousmah@[Link]
Classification des STR

bousmah@[Link]
Classification des STR

bousmah@[Link]
Notion de criticité et de QdS

bousmah@[Link]
Exemples des STR

bousmah@[Link]
Exemples des STR

bousmah@[Link]
Exemples des STR

bousmah@[Link]
 Propriétés des STR

 Fortes interaction avec le procédé

 IHM inexistant, limité ou particulier
 Contraintes temporelles
 période de scrutation, délais
 Contraintes de coût, d’espace, de consommation
 matériel
 taille mémoire
 Prédictibilité
 temps / espace
 Fiabilité / sûreté
 image de marque
 sécurité
 inaccessibilité

bousmah@[Link]
 Validité d’un programme TR

 Outre la correction algorithmique le temps intervient dans la

validité du programme:
 le temps de réaction doit être adapté aux événements externes
 Le programme doit pouvoir fonctionner en continu en maintenant
sa capacité à traiter le flux de données d’entrée
 Faute temporelle  faute algorithmique
exemple: flux audio
 Au sens strict, « valider » un système temps réel c’est
démontrer rigoureusement que le système a le comportement
spécifié (preuve de programme)
 Impossible avec les langages habituels

bousmah@[Link]
 Exemple: navigation aérienne Interfaces opérateurs

sol
Niveau 2
Capteurs à terre Calculs Contrôle de
Radars … d’états l’espace aérien

Données de Calculs
Niveau 1 navigation d’états
Gestion du vol

Niveau 0
Calculs
d’états
Régulation du
vol
avions

Capteurs
actionneurs
embarqués

Introduction à l'Informatique Temps Réel - S. Anvar, J.-P. Babau, P.-Y. Duval - 2005

bousmah@[Link]
Exemple: Multimédia

bousmah@[Link]
Exemple: Multimédia

bousmah@[Link]
Ordonnancement Processus temps réel
 Concepts de base
 Critères d’ordonnancement
 Algorithmes d’ordonnancement
 Évaluation d’algorithmes

21
 Diagramme de transition d`états d`un processus

22 22
 Files d’attente de processus pour
ordonnancement

file prêt

Nous ferons l’hypothèse que le premier processus dans une file est celui
qui utilise la ressource: ici, proc7 exécute
23
Concepts de base
La multiprogrammation est conçue pour obtenir
une utilisation maximale des ressources, surtout
l’UCT
L`ordonnanceur UCT est la partie du SE qui décide
quel processus dans la file ready/prêt obtient
l ’UCT quand elle devient libre
doit viser à une utilisation optimale de l ’UCT
l ’UCT est la ressource la plus précieuse dans un
ordinateur, donc nous parlons d’elle
Cependant, les principes que nous verrons
s ’appliquent aussi à l ’ordonnancement des autres
ressources (unités E/S, etc).
Doit comprendre le comportement des processus
Pour faire de bonne décision d’ordonnancement
Les cycles d’un processus

Cycles (bursts) d’UCT et E/S: l’exécution d’un processus

consiste de séquences d’exécution sur UCT et d’attentes
E/S
Histogramme de durée des cycles UCT

Observation expérimentale:
dans un système typique, nous observerons un grand nombre de
court cycles, et un petit nombre de long cycles
Les programmes tributaires de l ’UCT auront normalm. un
petit nombre de long cycles UCT
Les programmes tributaires de l ’E/S auront normalm. un
grand nombre de court cycles UCT
Quand invoquer l’ordonnanceur
L ’ordonnanceur doit prendre sa décision chaque fois que le
processus exécutant est interrompu, c’e-à.-d.
un processus se présente en tant que nouveau ou se termine ou
un processus exécutant devient bloqué en attente
un processus change d’exécutant/running à prêt/ready
un processus change de attente à prêt/read
en conclusion, tout événement dans un système cause une
interruption de l’UCT et l’intervention de l’ordonnanceur, qui devra
prendre une décision concernant quel proc ou fil aura l’UCT après
Préemption: on a préemption dans les derniers deux cas si on
enlève l’UCT à un processus qui l’avait et peut continuer à s’en
servir
Dans les 1ers deux cas, il n’y a pas de préemption
Plusieurs pbs à résoudre dans le cas de préemption
Dispatcheur

Le code du SE qui donne le contrôle au

processus choisi par l’ordonnanceur. Il
doit se préoccuper de:
changer de contexte
changer à mode usager
réamorcer le processus choisi
Attente de dispatcheur (dispatcher latency)
le temps nécessaire pour exécuter les
fonctions du dispatcheur
il est souvent négligé, il faut supposer qu’il soit
petit par rapport à la longueur d’un cycle

28
Critères d’ordonnancement
Il y aura normalement plusieurs processus
dans la file prêt

Quand l’UCT devient disponible, lequel choisir?

L’idée générale est d’effectuer le choix dans

l’intérêt de l’efficacité d’utilisation de la
machine

Mais cette dernière peut être jugée selon

différents critères…

29 Ch.
Critères d’ordonnancement
Raison principale pour l’ordonnancement
Pourcentage d ’utilisation: garder UCT et modules E/S
occupés
Systèmes à temps partagés?
Temps de réponse (pour les systèmes interactifs): le temps
entre une demande et la réponse
Serveurs?
Débit = Throughput: nombre de processus qui complètent
dans l ’unité de temps
Systèmes de traitement par lots (batch)?
Temps de rotation = turnaround: le temps pris par le proc de
son arrivée à sa termin.
Systèmes chargés?
Temps d’attente: attente dans la file prêt (somme de tout le
temps passé en file prêt)

30 Ch.
Critères d’ordonnancement: maximiser/minimiser
À maximiser
Utilisation UCT: pourcentage d’utilisation
Débit = Throughput: nombre de processus qui
complètent dans l ’unité de temps
À minimiser
Temps de réponse (pour les systèmes interactifs): le
temps entre une demande et la réponse
Temps de rotation (turnaround): temps terminaison
moins temps arrivée
Temps d’attente: attente dans la file prêt

31
 Exemple de mesure des critères d’ordonnancement
P1 P2 P3 P4 Process arrival

P1 P2 P3 P4 P1 P2
Time 0 45 7 10,11,12 20 22 24
Utilisation de l’UCT:
100%
Temps de réponse (P3, P2):
P3: 3
P2: 1
Débit :
4/24
Temps de rotation (P3, P2):
P3: 5
P2: 20
Temps d’attente (P2):
P2: 13
Examinons maintenant plusieurs méthodes
d’ordonnancement et voyons comment elles se
comportent par rapport à ces critères

nous étudierons des cas spécifiques

l’étude du cas général demanderait recours à techniques probabilistes ou de
simulation
Premier arrivé, premier servi (First come, first serve, FCFS)

• Notez, aucune préemption

Exemple: Processus Temps de cycle

P1 24
P2 3
P3 3
Si les processus arrivent au temps 0 dans l’ordre: P1 , P2 , P3
Le diagramme Gantt est:

P1 P2 P3

0 24 27 30

Temps d’attente pour P1= 0; P2= 24; P3= 27

Temps attente moyen: (0 + 24 + 27)/3 = 17
Premier arrivé, premier servi
Utilisation UCT = 100%
Débit = 3/30 = 0,1
3 processus complétés en 30 unités de temps
Temps de rotation moyen: (24+27+30)/3 = 27

P1 P2 P3

0 24 27 30
 Ordonnancement FCFS (suite)
Si les mêmes processus arrivent à 0 mais dans l’ordre
P2 , P3 , P1 .
Le diagramme de Gantt est:

P2 P3 P1

0 3 6 30

Temps d’attente pour P1 = 6 P2 = 0 P3 = 3

Temps moyen d’attente: (6 + 0 + 3)/3 = 3
Beaucoup mieux!
Donc pour cette technique, le temps d’attente
moyen peut varier grandement
Exercice: calculer aussi le temps moyen de rotation, débit, etc.
Tenir compte du temps d’arrivée!
Dans le cas où les processus arrivent à
moment différents, il faut soustraire les
temps d’arrivée
Exercice: répéter les calculs si:
P2 arrive à temps 0
P1 arrive à temps 2
P3 arrive à temps 5
Effet d’accumulation (convoy effect) dans FCFS
Supposons un processus tributaire de l’UCT et
plusieurs tributaires de l`E/S (situation assez
normale)
Les processus tributaires de l’E/S attendent pour
l ’UCT: E/S sous-utilisée (*)
Le processus tributaire de l’UCT fait une E/S: les
autres proc exécutent rapidement leur cycle UCT
et retournent sur l’attente E/S: UCT sous-utilisée
Processus tributaire de l’UCT fini son E/S, puis les
autres procs aussi : retour à la situation (*)
Une possibilité: interrompre de temps en temps le
proc tributaires de l’UCT pour permettre aux
autres procs d’exécuter (préemption)

38
Plus Court d’abord = Shortest Job First (SJF)

Le processus le plus court part le

premier
Optimal en principe du point de vue
du temps d’attente moyen
(v. le dernier exemple)
Mais comment savons-nous
SJF avec préemption ou non
Avec préemption: si un processus qui dure
moins que le restant du processus courant
se présente plus tard, l’UCT est donnée à
ce nouveau processus
SRTF: shortest remaining-time first
Sans préemption: on permet au processus
courant de terminer son cycle
Observation: SRTF est plus logique car de toute façon le
processus exécutant sera interrompu par l’arrivée du
nouveau processus
Il est retourné à l’état prêt
Exemple de SJF sans préemption
Processus Arrivée Cycle
P1 0 7
P2 2 4
P3 4 1
P4 5 4

SJF (sans préemption)

P1 P3 P2 P4

0 3 7 8 12 16

P2 arr. P3 arr. P4 arr

Temps d’attente moyen = (0 + 6 + 3 + 7)/4 = 4

 Exemple de SJF avec préemption
Processus Arrivée Cycle
P1 0 7
P2 2 4
P3 4 1
P4 5 4
SJF (préemptive)

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

P2 arr. P3 arr. P4 arr

Temps moyen d`attente = (9 + 1 + 0 +2)/4 = 3
P1 attend de 2 à 11, P2 de 4 à 5, P4 de 5 à 7
42 42
Comment déterminer la longueur des cycles à l’avance?

Quelques méthodes proposent de

déterminer le comportement futur d ’un
processus sur la base de son passé
[Link]. moyenne exponentielle

43
Estimation de la durée du prochain cycle

 Ti : la durée du ième cycle de l’UCT pour

ce processus
 Si : la valeur estimée du le ième cycle de
l’UCT pour ce processus. Un choix simple
est: n

 S n+1 = (1/n)
i 1
T i (une simple
moyenne)
 Nous pouvons éviter de recalculer la
somme en récrivant:
 Sn+1 = (1/n) Tn + ((n-1)/n) Sn
 Ceci donne un poids identique à chaque
cycle

44
46
47
48
50
51
52
53
54
55
56
57
58
59
60 Ch.
61 Ch.
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
Master 2 pro
Programmation temps-réel
Cours 1 et 2
Introduction et ordonnancement

Isabelle PUAUT / Rémi COZOT

Université de Rennes I
Ordonnancement temps réel
Pierre-Yves Duval
Ecole d’informatique temps réel - La Londes les Maures 7-11
Octobre 2002

95
Questions

bousmah@[Link]
Annexes

bousmah@[Link]
• En mathématiques et plus précisément en arithmétique, le plus petit commun
multiple – en abrégé PPCM – de deux entiers non nuls a et b est le plus petit
entier strictement positif qui soit à la fois multiple de ces deux nombres. On le
note a ∨ b1 ou PPCM(a, b), ou parfois simplement [a, b]2.
• Le PPCM de a et b peut également se définir comme un multiple commun
de a et de b qui divise tous les autres. Cette seconde définition se généralise à
un anneau commutatif quelconque, mais on perd en général l'existence et
l'unicité ; on parle alors d'un PPCM de deux éléments. L'existence est assurée
dans les anneaux intègres factoriels ou même seulement à PGCD.
• Le PPCM peut se définir plus généralement pour un nombre quelconque
d'éléments : par exemple le PPCM de n entiers non nuls est le plus petit entier
strictement positif multiple simultanément de ces n entiers.

bousmah@[Link]
Exemple
Prenons les nombres 60 et 168 et décomposons-les en
produits de facteurs premiers. On a :
60 = 2×2×3×5 = 22×3×5 ;
168 = 2×2×2×3×7 = 23×3×7.
Pour le nombre premier 2, le plus grand exposant est 3.
Pour les nombres premiers 3, 5 et 7, le plus grand
exposant est 1.
On a ainsi PPCM(60, 168) = 23×3×5×7 = 840.

bousmah@[Link]