ENSA de Marrakech SYSTEMES TEMPS REEL

M. Zrikem 2021/2022

Série1 de TD

Exercice 1 :

La figure suivante représente les états d’une tâche. Compléter la en reliant deux états par une
flèche si la transition est possible entre ces deux états.

Déterminer parmi ses actions celles qui sont des primitives de synchronisation et celles qui
sont des décisions de l’ordonnanceur.

Inexistante

Crée Terminée

Prête ac ve

Bloquée

Exercice 2 :

Des pi ces fabriqu es sur une cha ne de production sont d pos es sur un convoyeur et
passent, avec une vitesse de 1 m/s, devant une cam ra qui doit d tecter certaines anomalies de
fabrication. En fonction des anomalies d tect es par le syst me de reconnaissance, les pi ces
sont dirig es vers une cellule de fabrication appropri e. La d tection des anomalies doit se
faire pendant que la pi ce est en mouvement. Par cons quent, le traitement doit s’effectuer au
bout d’un temps bien pr cis tenant compte de la vitesse du convoyeur, pour permettre la
pi ce d’ tre aiguill e vers la bonne cellule.

En quelques lignes, définir les tâches temps réel de ce système en précisant leur
fonctionnement, leur type (périodique ou apériodique) et estimant leur intervalle temporel.

Exercice 3 :

Soit les deux processus compteur /statistiques suivants :

è
ti
è
ê
é

é
é
è
é
î

é

é
é

é
é

è
é
é
é
é
è

à

 Pour éviter la perte d’évènements, indiquer les séquences à exécuter en exclusion.

Exercice 4

Sur un processeur, les tâches du tableau s’exécutent de manière indépendante, sans

synchronisation et sans partage de ressources. La priorité la plus forte est la priorité de valeur
1. Les tâches bénéficient d’un même quantum de temps (1 unité de temps) et disposent
alternativement du processeur en fonction de trois méthodes usuels simples (FIFO, Tourniquet
et priorité). L’ordre d’arrivée des tâches est celui du tableau.
Pour les trois méthodes donner le tableau de déroulement des tâches.

Tâches Capacité Priorité

T1 3 2
T2 5 1
T3 2 2
T4 4 3

Exercice 5

Pour les processus du tableau, dessinez un schéma illustrant leur exécution en utilisant
l'ordonnancement de priorité. Une valeur de priorité élevée correspond à une priorité plus
importante. Discuter les deux cas :
• Préemptif
• Non préemptif

Processus Date d'arrivée Capacité Priorité

A 0 4 3
B 1 3 4
C 2 4 6
D 3 5 5

Exercice 6

Cinq travaux A, B, C, D et E sont soumis à un calculateur dans cet ordre, mais quasi
simultanément. Ces travaux ne font pas d'entrée-sortie. Leurs durées respectives sont de 10, 6.
2, 4 et 8 secondes.

• Déterminez les temps de réponse de chacun des travaux. ainsi que le temps de réponse
moyen, pour les disciplines FIFO (first in, first out) et SJF (shortest job first).
• Même question pour une discipline à priorité (P=1 priorité maximale), avec :
P(A) = 3, P(B) = 5, P(C) = 2, P(D) =1, P(E) = 4
• Même question avec la discipline de tourniquet et un quantum de 2 secondes.
2

 Exercice 7

Soient les trois processus P1, P2, P3 qui arrivent au même temps et avec les durées
d’exécution 20, 15, 10 respectivement ; quel est le temps d’attente moyen d’un ordonnanceur
qui suit la stratégie Shortest Job First

Exercice 8

On considère un système monoprocesseur de type LINUX dans lequel les processus partagent
un disque comme seule ressource (autre que le processeur évidemment). Cette ressource n'est
accessible qu'en accès exclusif et non requérable, c'est-à-dire qu'une commande disque lancée
pour le compte d'un processus se termine normalement avant que l'on puisse en lancer une
autre.
Un processus peut être en exécution, en attente d'entrée-sortie ou en attente de processeur. En
lait, l'état bloqué se divise en deux états: attente de la ressource disque et attente de la fin
d'exécution de l'opération.

Dans ce système, on considère les quatre processus Pl, P2, P3 et P4 pour lesquels on sait que

• PI et P2 sont des processus appartenant à la classe 1. Dans cette classe, le processeur est
donné au processus de plus haute priorité. Ce processus peut être préempté par un
processus de la même classe ayant une priorité supérieure.
• P3 et P4 sont des processus appartenant à la classe 2. Dans cette classe, le processeur est
donné au processus de plus haute priorité pour un quantum de temps égal à 10 ms. La
politique appliquée est celle du tourniquet.

Les quatre processus ont le comportement suivant (la priorité de démarrage est indiquée entre
parenthèses) :

P1 (100) P2 (99) P3 (99) P4 (98)

Calcul 40 ms Calcul 30 ms Calcul 40 ms Calcul 80 ms
Lecture disque 50 ms Lecture disque 80 Lecture disque 40
Calcul 30 ms Calcul 80 ms Calcul 10 ms
Lecture disque 40 ms Lecture disque 20
Calcul 20 ms Calcul 10 ms

1. Etablissez le chronogramme des 4 processus sur un diagramme en indiquant pour chaque

processus son état.

2. Rétablir les chronogrammes en supposant maintenant que les priorités soient recalculées
chaque fois qu'un processus quitte l'état Attente de la façon suivante :
Nouvelle priorité = Ancienne priorité - ( temps processeur utilisé par le processus/10)

 Exercice 9

Soit T une configuration de n tâches périodiques avec des échéance égales aux périodes telle
que n(2 n − 1) < U ≤ 1: avec U le taux d’utilisation du processeur .
1

Déduire pour l’ordonnaçabilité de la configuration pour les RM, DM, EDF et LLF.

Exercice 10
Soit un système composé de deux tâches périodiques T1 et T2. On suppose que T1 est définie
par une période P1= 12, et une capacité C1 = 6, et T2 par P2=30, C2=15. Les échéances sont
égales aux périodes.

1. Illustrer par un diagramme l’ordonnancement de T1 et T2 suivant la politique EDF. Y-a-t-

il des échéances manquées?
2. Mêmes questions avec l’ordonnancement Rate Monotonic (RM).
3. Ces résultats sont-ils surprenants? Pourquoi?

Exercice 11 :

Soit la configuration suivante :

Tâches P C
A 7 3
B 12 3
C 20 5

1. Est-ce ordonnançable par RMS ?

2. En utilisant le théorème de la zone critique, donner le temps de réponse pour chaque

tâche ?

3. Si A avait besoin de plus de temps CPU, jusque où peut-elle s’étendre ?

Exercice 12
On considère une configuration F de trois tâches {Tp1, Tp2, Tp3}

- Tp1 (R=0, C =1, D =3, P = 3)

- Tp2 (R=0, C =1, D =4, P = 4)
- Tp3 (R=0, C =2, D =3, P = 6)

Décrire graphiquement les séquences obtenues dans le cas des trois ordonnancements RM,
DM, EDF pour cette configuration T.

 Exercice 13 :
Donnez les chronogrammes des ordonnancements produits par RM, DM, EDF et LLF entre
t = 0 et t = 30 pour le jeux de tâches suivant :

ri Ti Di Ci

τ1 0 6 6 2

τ2 0 7 4 3

τ3 0 15 15 3

Exercice 14 :

Soit la configuration suivante :

T1 : C1=3 D1=7 P1=7

T2 : C2=2 D2=4 P2=5

T3 : C3=2 D3=8 P3 = 9

Dans le cadre d’une ordonnancement EDF :

1. Appliquer la condition suffisante à cette configuration et conclure pour l’ordonnaçabilité par EDF.

2. Appliquer la condition nécéssaire à cette configuration et conclure pour l’ordonnaçabilité par EDF.

Exercice 15 :

Soit le système temps réel donné à la table 1. Les tâches sont périodiques, à départ simultané
à échéance sur requête. Nous supposons qu’elles sont indépendantes.

Tâches C P
A 1 4
B 2 6
C 3 8

1. Etant donné une politique d’ordonnacement RM, calculer U le taux d’occupation du

processeur pour cette configuration. Déduire.

2. Appliquer la méthode de la zone critique pour déterminer le temps de réponse des trois
tâches.

3. Tracez l’exécution du système de la table 1 en utilisant la politique d’ordonnancement

Rate Monotonic préemptif. Le système est il ordonnançable ?

4. Tracez l’exécution du système en utilisant la politique d’ordonnancement EDF. Le

système est-il ordonnançable ?

5. Conclure.

 Exercice 16 :
Soit le tableau suivant :
Tâches Temps Période Deadline
d’exécution
T1 1 10 10
T2 18 100 100
T3 2 20 20
T4 5 50 50
T5 x 25 25

1. Calculez le temps d’exécution maximal x de T5 afin d’avoir un ordonnancement

faisable (pour T1 à T5), en considérant l’ordonnancement EDF.

2. Choisir une valeur de x dans l’intervalle de faisabilité et donner le diagramme

d’ordonnancement EDF correspondant.

Exercice 17 :
Soient les ensembles de t ches suivants :
Taches Pi Ci Di
T1 5 2 5
T2 3 1 3
T3 4 1 4
T4 20 3 20

Ensemble des taches du système V

Taches Pi Ci Di
T5 11 4 11
T6 14 x 14
Ensemble des taches du système W

On suppose un ordonnancement de type RMA (Rate Monotonic Assignment). Les deux

systèmes roulent sur des processeurs différents et indépendants.
1. Effectuez le test de faisabilité pour l’ensemble des tâches du système V. Que peut-on en
conclure ?
On décide de transférer la tâche T4 sur le système W.
2. Donner le diagramme d’ordonnancement du système V (après transfert). Dites si
l’ordonnancement est possible ou non et pourquoi.
3. Quelle doit être le nombre maximal de cycles d’exécution de la tâche T6 dans le système
W pour que l’ordonnancement soit possible après le transfert de T4 dans ce système?
6

â

 Exercice 19 :
Soit le système temps réel donné à la table 1. Les tâches sont périodiques, à départ simultané
à échéance sur requête. Nous supposons qu’elles sont indépendantes.
Taches Pi Ci Di
T1 5 2 5
T2 10 3 10
T3 15 4 15
1. Etant donné une politique d’ordonnacement RM, calculer U le taux d’occupation du
processeur pour cette configuration. Déduire pour l’ordonnançabilité de la
configuration.

2. Appliquer la méthode de la zone critique pour déterminer le temps de réponse des trois
tâches.

3. Tracez l’exécution du système de la table 1 en utilisant la politique d’ordonnancement

Rate Monotonic préemptif. Le système est il ordonnançable par RM ?

4. Vérifier le test d’ordonnançcabilité pour EDF.

5. Tracez l’exécution du système en utilisant la politique d’ordonnancement EDF.

6. Tracez l’exécution du système en utilisant la politique d’ordonnancement LLF.

Exercice 20 : (dernier exam)

Soit la con gura on suivante :

Tache Période = échéance Capacité

T1 50 10
T2 40 10
T3 20 15

Consid rons un ordonnancement cyclique :

1. Dé nir le cycle mineur et le cycle majeur de cet ordonnancement.

2. Donner le diagramme d’exécu on associé

Consid rons l’ordonnancement bas sur RM :

1. Expliquez ce qu’on entend, lorsqu’on dit que la condi on d’ordonnancement Liu et Layland
est une condi on su sante, mais pas n cessaire : U ≤ n(2 n − 1)
1

2. Appliquer la condi on à la con gura on ci-dessus.

3. Que peut-on dire pour l’ordonnançabilité de la con gura on par EDF? Déduire pour sa
faisabilité.

4. Donner la diagramme d’exécu on de la con gura on par RM. Déduire pour

l’ordonnançabilité de la con gura on par RM.
7

fi
é
é

fi
ti

ti
ti
ffi
fi

ti

fi
ti
é
ti
ti
é

fi
ti
fi
ti
ti

 5. Appliquer la méthode de la zone cri que pour con rmer calculer les temps de réponse des 3
taches et con rmer les résultats de la ques on précédente

Exercice 21 :
L’objectif de cet exercice est de montrer l’optimalité d’un algorithme d’ordonnancement X
qu’on doit découvrir vers la fin.

Pour montrer cette propriété d’optimalité, on applique des transformations successives à une
situation d’ordonnancement de départ jusqu'à aboutir à un ordonnancement X. Ces
transformations consistent à permuter les unités de traitement des tâches entre elles, tout en
respectant les propriétés de ces tâches, à savoir : leurs temps d’exécution, leurs instants
d’activation, leurs échéances

L’algorithme de transformation est itératif : il part de l’instant 0 puis progresse jusqu'à

l’instant t.

A l’instant i, il fait passer d’une situation d’ordonnancement Si à une situation Si+1.

Dans la situation Si, on appelle :

- Ta(i) la tâche courante à l’instant i.
- Tb la tâche prête dont l’échéance est la plus proche de i et qui n’a pas fini son
exécution,
- j l’instant tel que j > i et Tb(j) est la tâche courante

Dans la situation Si+1 on appelle :

- newTa(i) la tâche courante à l’instant i,
- newTc(i) la tâche courante à l’instant j.

L’algorithme de transformation s’exprime de la façon suivante :

For (i =0, i <= t, i++)

{ Trouver Tb ;
If Tb existe
{ if (Ta(i) == Tb) newTa(i) = Ta(i) /* rien ne change */
Else { newt a(i) = Tb; newt c(j) = Ta(i) } /* permutation des traitements */
}
Else
newt a(i) = Ta(i)
}

Exemple : On considère 4 tâches dont on donne l’ordonnancement arbitraire de la figure

suivante (situation S0). Les flèches montantes indiquent les instants d’activation des tâches
(ex. la tâche 2 est activée au temps 3), les flèches descendantes indiquent les échéances des
tâches (ex. la tâche 2 doit finir son exécution au plus tard à l’instant 7)

fi

ti

ti
fi

 Tâche

Tâche

Tâche

Tâche

0 1 2 3 4 5 6 7 8 9 10 11

Situation de départ S0
Les deux premières itérations ne changent pas l’état d’ordonnancement des tâches. (S1=S0 et
S2=S1)

Pour i=2, Ta(i) = tâche 1, Tb = tâche 3, j=3, newTa(2) = tâche 3, newTc(3) = tâche 1. Les
éléments permutés sont indiqués en noir.

Tâche 1

Tâche 2

Tâche 3

Tâche 4

0 1 2 3 4 5 6 7 8 9 10 11
Situation S3 après 3 itérations

1. Donner le test de faisabilité EDF de cette configuration.

2. Donner le diagramme de l’ordonnancement EDF associé à cette configuration.
3. Appliquer l’algorithme de transformation et donner les situations S4, et S5.
4. La situation finale est la suivante, comparez la au diagramme de la question 2.

 Tâche 1

Tâche 2

Tâche 3

Tâche 4

0 1 2 3 4 5 6 7 8 9 10 11

5. Identifier l’ordonnancement X.
6. Commenter. Ce résultat vous surprend-il ?

10

 Exemples de questions de cours

Exercice 1 :
1. Définir les notions suivantes :

a. Fiabilité

b. Prédictibilité

c. Préemptibilité

d. Exécution dos a dos

e. Système de contrôle

f. système contrôlé

2. expliquer la nécessité des caractéristiques suivantes pour un système temps réel :

a. Aspect multitâches

b. Préemptibilité

3. Dans le cadre d’interaction entre les taches d’un STR :

a. Définir la méthode du plafond de priorité.

b. Expliquer comment il permet d’éviter les interblocages.

4. Dans le cadre d inclusion des taches apériodiques dans un STR :

a. Citer les différents serveurs utilisés.

b. Comparer les.

5. Citer les mécanismes introduits par les STR pour gérer la synchronisation entre les taches.

6. Quand dit-on qu’un système temps réel est ordonnançable ou faisable ?

7. Comment le problème de corruption de la valeur d’une variable globale peut se

produire ? Comment y remédier ?

Exercice 2 :
1. Définir les notions suivantes :

g. déterminisme
h. Synchronisation

i. Test de faisabilité

j. Défaut de page

k. Ordonnancement optimal

l. Système interactif

2. Considérons un ordonnanceur à priorité :

c. Citer les caractéristiques d’un tel ordonnancement.

d. Donner ses intérêts et ses limitations.

11

 3. Définir en citant les avantages et les inconvénients des politiques : RM, EDF, LLF.

4. Définir en citant les avantages et les inconvénients des méthodes : héritage simple, verrou le plus
haut, plafond de priorité.

5. Dans le cadre d’interaction par interruption pour un STR :

a. Définir ce mode d’interaction

b. Donner les différentes origines des interruptions

c. Décrire brièvement et avec précision les étapes de prises en charge d’une interruption

d. Décrire par un diagramme le bilan temporel d’une interruption.

6. Répondre de manière concise et précise :

a. Quelles sont les conditions nécessaires à l’apparition d’un interblocage entre deux tâches ?

b. Le protocole d’héritage de priorité permet–il d’éviter l’apparition d’un interblocage entre deux
tâches ? justifier.

Exercice 3 :

1. Donner et définir les différents types de tâches dans un système temps réel.

2. Donner et définir les différents états d’une tâche dans un système temps réel.

3. Quand peut-on qualifié un système temps réel d’exact (définir les notions nécessaires)

4. Indiquez deux méthodes pour rendre réentrante une fonction en citant leurs avantages et
inconvénients.

5. Verrouillage des interruptions :

a. Définir le principe de verrouillage des interruptions

b. Expliquez pourquoi le verrouillage des interruptions n’est pas toujours suffisant.

c. Comment pourrait-on assurer une protection supplémentaire la section critique.

6. Etant donné un ensemble de n taches avec des échéance égales aux périodes où Ci et Ti sont
n Ci
∑i=1 Ti
respectivement la capacité et la période la tache i. U = est le taux d’utilisation du
processeur. Que peut-on dire de l’ordonnançabilité de l’ensemble des n tâches avec RM dans
chacun des cas suivants :
a. Si U  ≤ n(2 n − 1)
1

b. Si U > 1
c. n(2 n − 1) < U ≤ 1
1

7. Dans système de contrôle de voiture une tâche critique peut être :

a. Contrôle climatisation

b. Contrôle pneumatique
c. Contrôle vitres

8. Présentez les avantages et les désavantages d’un ordonnancement hors ligne dans des systèmes
temps réel.

12

à

 9. un contrôle activ par le temps est plus fréquent dans les systèmes temps réel durs, alors qu’un
contrôle activ par les évènements est plus fréquent dans les systèmes temps réel mou. Expliquez
pourquoi il en est ainsi.
10. Les défauts de page ont été mentionnés comme étant un problème important dans les systèmes
temps réel. Indiquez en quoi ceci est un problème et de quelle façon peut-on l’éviter

Exercice 4 :

Le système informatique de contrôle des billets à l’entrée du métro est-il un système temps
réel ? On distinguera les fonctions « lecture du billet », « contrôle sur place par la borne de
validité du billet » et contrôle à l’aide d’un serveur de la validité des cartes d’abonnement ».
Les sous systèmes assurant ces fonctions sont-ils temps réel ?

Exercice 5 :

Le système informatique de gestion d’un distributeur de boissons est-il un système temps

réel ?
Si c’est le cas, est-il dur ou mou ? Distinguer les différentes fonctionnalités de ce système et
discuter et justifier vos choix en quelques lignes (maximum 10 lignes)

Exercice 6 :

Pour chacune des transitions suivantes entre les états des processeurs, indiquez si la transition
est possible. Si c’est le cas, donnez quelques explications en donnant un exemple qui pourrait
en être à l’origine.
• En exécution - Prêt
• En exécution - bloqué
• Bloqué - en exécution
• En exécution - terminé

Exercice 7 :
Parmi les contraintes suivantes lesquelles sont temps réel :
a. Prélever la température toutes les 50 secondes.
b. Déclencher l’airbag au plus tard 10 ms après l’impact.
c. Envoyer 25 images par seconde
d. Prendre 48h pour prédire le temps qu’il fera le lendemain
e. Calculer un seuil de vente ou d’achat d’actions au bout de 7 jours
f. Arriver à 9h pour prendre le train de 8h32
g. Lancer la sirène de l’usine à midi
h. Mettre à jour l’état du stock au plus tard 10 min après la vente de produit.

13

é
é

 Exercice 8 :
Répondre par vrai ou faux :
a. Temps réel non strict = absence de contraintes
b. Optimisation des temps de réponse ⇒ Temps réel
c. Temps réel = rapidité
d. haute criticité ⇒ besoins stricts de correction, sûreté de fonctionnement,
prédictibilité
Exercice 9 :
Classer les systèmes suivants dans l’ordre croissant de leur complexité :

a. Systèmes mono-utilisateur monotâche

b. Systèmes mono-utilisateur multitâches
c. Systèmes temps réel et distribués
d. Systèmes distribués
e. Système multi-utilisateurs multitâches
f. Systèmes temps réel centralisés
Exercice 10 :

Définir les classes d’ordonnancement ci-dessous en précisant les intérêts et les limitations de
chacune :
a. Ordonnancement en ligne / hors ligne
b. Ordonnancement préemptif / non préemptif

Exercice 11 :
On considère deux taches Th1 et Th2. Th1 est la plus prioritaire.
A l’instant 0, Th1 lance une E/S. Le dessin ci-dessous schématise la suite des événements :
Préciser sur le graphique ci-dessous à quoi correspond les différents temps désignés par des
flèches :

14

 Exercice 12 :
Soit la procédure suivante :

Demande d’accès mémoire

Si page disponible en mémoire alors Accès
Sinon
Suspendre la tâche
Dé-allouer une page %choix en fonction de la politique%
Charger nouvelle page
Signaler
Fsi

a. Quel problème décrit cette procédure ?

b. Qu’offrent les systèmes temps réel pour remédier à ce problème ?

15