Exercice 0. QCM d’activation
Pour chaque question, une seule réponse est correcte.
Question 1. Un processus est :
- A) un programme stocké sur le disque dur
- B) un programme en cours d’exécution en mémoire
- C) un fichier exécutable
- D) une instruction du processeur
Correction
Réponse B. Un processus est une instance d’un programme en cours d’exécution. Il possède son propre espace mémoire, un compteur de programme et un état (prêt, élu, bloqué).
- A est faux : sur le disque, c’est un programme (code), pas un processus ;
- C est faux : un fichier exécutable est un programme, pas encore un processus ;
- D est faux : une instruction est une opération élémentaire du processeur, pas un processus.
Question 2. Dans l’ordonnancement FIFO (premier arrivé, premier servi), l’inconvénient principal est :
- A) il est trop complexe à implémenter
- B) les processus courts peuvent attendre longtemps derrière un processus long
- C) il nécessite de connaître la durée des processus à l’avance
- D) il provoque toujours un interblocage
Correction
Réponse B. En FIFO, les processus sont exécutés dans l’ordre d’arrivée sans préemption. Un processus court arrivé juste après un processus très long devra attendre la fin complète de ce dernier, ce qui augmente le temps d’attente moyen.
- A est faux : FIFO est l’algorithme le plus simple ;
- C est faux : c’est l’inconvénient de SJF (plus court d’abord), pas de FIFO ;
- D est faux : FIFO ne provoque pas d’interblocage (c’est un problème lié aux ressources partagées).
Question 3. Un processus est dans l’état « bloqué » lorsque :
- A) il attend son tour dans la file des processus prêts
- B) il est en cours d’exécution sur le processeur
- C) il attend la fin d’une opération d’entrée/sortie
- D) il a terminé son exécution
Correction
Réponse C. Un processus bloqué attend un événement externe (lecture disque, saisie clavier, réponse réseau). Il ne peut pas être exécuté tant que cet événement n’est pas survenu. Une fois l’événement reçu, il repasse à l’état « prêt ».
- A est faux : dans ce cas, il est à l’état « prêt » ;
- B est faux : dans ce cas, il est à l’état « élu » (en cours d’exécution) ;
- D est faux : dans ce cas, il est « terminé ».
Question 4. L’ordonnancement par tourniquet (round-robin) avec un quantum de temps $q$ :
- A) exécute chaque processus complètement avant de passer au suivant
- B) accorde à chaque processus au plus $q$ unités de temps avant de le préempter
- C) choisit toujours le processus le plus court
- D) ne permet pas de gérer plus de deux processus simultanément
Correction
Réponse B. Le tourniquet attribue un quantum de temps $q$ à chaque processus. Si le processus n’a pas terminé au bout de $q$ unités de temps, il est préempté (interrompu) et placé en fin de file d’attente. C’est un algorithme équitable.
- A est faux : c’est le principe de FIFO, pas du tourniquet ;
- C est faux : c’est le principe de SJF ;
- D est faux : le tourniquet gère un nombre quelconque de processus.
Question 5. Un interblocage (deadlock) se produit quand :
- A) un processus utilise trop de mémoire
- B) deux processus ou plus s’attendent mutuellement pour libérer des ressources
- C) le processeur est trop lent pour exécuter tous les processus
- D) un processus entre dans une boucle infinie
Correction
Réponse B. L’interblocage survient quand chaque processus d’un ensemble détient une ressource et attend une ressource détenue par un autre processus de l’ensemble. Aucun ne peut avancer. C’est une situation d’attente circulaire.
- A est faux : c’est un problème de dépassement mémoire, pas d’interblocage ;
- C est faux : c’est un problème de performance, pas d’interblocage ;
- D est faux : une boucle infinie concerne un seul processus et ne bloque pas les autres.
Exercice 1 — FIFO
| Processus | P1 | P2 | P3 |
|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 |
| Date d’arrivée | 8 | 3 | 0 |
Représenter l’ordonnancement des processus ci-dessus à l’aide du modèle FIFO. Calculer le temps de terminaison, le temps de séjour et le temps d’attente de chaque processus, ainsi que le temps d’attente moyen.
Solution
Principe : en FIFO (premier arrivé, premier servi), les processus sont exécutés intégralement dans leur ordre d’arrivée : P3 (t=0), P2 (t=3), P1 (t=8).
Frise chronologique :
0 → 9
9 → 14
14 → 22
P2 arrive à t=3 et attend la fin de P3. P1 arrive à t=8 et attend la fin de P2.
| Processus | P1 | P2 | P3 |
|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 |
| Date d’arrivée | 8 | 3 | 0 |
| Temps de terminaison | 22 | 14 | 9 |
| Temps de séjour | 14 | 11 | 9 |
| Temps d’attente | 6 | 6 | 0 |
Calculs détaillés :
- P3 : terminaison = 9, séjour = 9 − 0 = 9, attente = 9 − 9 = 0
- P2 : terminaison = 14, séjour = 14 − 3 = 11, attente = 11 − 5 = 6
- P1 : terminaison = 22, séjour = 22 − 8 = 14, attente = 14 − 8 = 6
Temps d’attente moyen = (0 + 6 + 6) / 3 = 4 quanta.
Exercice 2 — SJF
| Processus | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 | 2 |
| Date d’arrivée | 4 | 0 | 3 | 7 |
Représenter l’ordonnancement des processus ci-dessus à l’aide du modèle SJF. Calculer le temps de terminaison, le temps de séjour et le temps d’attente de chaque processus, ainsi que le temps d’attente moyen.
Solution
Principe : en SJF (Shortest Job First) non préemptif, on exécute intégralement le processus prêt dont la durée est la plus courte.
Frise chronologique :
0 → 5
5 → 13
13 → 15
15 → 24
À t=0, seul P2 est arrivé. À t=5, P1 (durée 8) et P3 (durée 9) sont prêts : on choisit P1 (le plus court). À t=13, P3 (durée 9) et P4 (durée 2) sont prêts : on choisit P4. À t=15, seul P3 reste.
| Processus | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 | 2 |
| Date d’arrivée | 4 | 0 | 3 | 7 |
| Temps de terminaison | 13 | 5 | 24 | 15 |
| Temps de séjour | 9 | 5 | 21 | 8 |
| Temps d’attente | 1 | 0 | 12 | 6 |
Calculs détaillés :
- P2 : terminaison = 5, séjour = 5 − 0 = 5, attente = 5 − 5 = 0
- P1 : terminaison = 13, séjour = 13 − 4 = 9, attente = 9 − 8 = 1
- P4 : terminaison = 15, séjour = 15 − 7 = 8, attente = 8 − 2 = 6
- P3 : terminaison = 24, séjour = 24 − 3 = 21, attente = 21 − 9 = 12
Temps d’attente moyen = (0 + 1 + 6 + 12) / 4 = 4,75 quanta.
Exercice 3 — Round Robin (trois processus)
| Processus | P1 | P2 | P3 |
|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 |
| Date d’arrivée | 1 | 0 | 3 |
Représenter l’ordonnancement des processus ci-dessus à l’aide du modèle Round Robin avec un quantum de 2. Calculer le temps de terminaison, le temps de séjour et le temps d’attente de chaque processus, ainsi que le temps d’attente moyen.
Solution
Principe : chaque processus s’exécute pendant au plus 2 quanta. S’il n’a pas terminé, il retourne en bout de file. Les nouveaux arrivants rejoignent la file avant le processus préempté.
Frise chronologique (quantum = 2) :
| 0–2 | 2–4 | 4–6 | 6–8 | 8–10 | 10–11 | 11–13 | 13–15 | 15–17 | 17–19 | 19–21 | 21–22 |
| P2 | P1 | P2 | P3 | P1 | P2 ✓ | P3 | P1 | P3 | P1 ✓ | P3 | P3 ✓ |
Le symbole ✓ indique la terminaison du processus. P2 n’a besoin que d’un quantum pour son dernier passage (t=10–11) ; de même P3 termine en un quantum (t=21–22).
| Processus | P1 | P2 | P3 |
|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 |
| Date d’arrivée | 1 | 0 | 3 |
| Temps de terminaison | 19 | 11 | 22 |
| Temps de séjour | 18 | 11 | 19 |
| Temps d’attente | 10 | 6 | 10 |
Calculs détaillés :
- P2 : terminaison = 11, séjour = 11 − 0 = 11, attente = 11 − 5 = 6
- P1 : terminaison = 19, séjour = 19 − 1 = 18, attente = 18 − 8 = 10
- P3 : terminaison = 22, séjour = 22 − 3 = 19, attente = 19 − 9 = 10
Temps d’attente moyen = (6 + 10 + 10) / 3 ≈ 8,67 quanta.
Exercice 4 — Round Robin (sept processus)
| Processus | P1 | P2 | P3 | P4 | P5 | P6 | P7 |
|---|---|---|---|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 | 2 | 6 | 8 | 4 |
| Date d’arrivée | 1 | 0 | 2 | 3 | 4 | 6 | 5 |
Représenter l’ordonnancement des processus ci-dessus à l’aide du modèle Round Robin avec un quantum de 2. Compléter le tableau suivant.
| Processus | P1 | P2 | P3 | P4 | P5 | P6 | P7 |
|---|---|---|---|---|---|---|---|
| Temps de terminaison (optionnel) | |||||||
| Temps d’exécution/Temps de séjour | |||||||
| Temps d’attente |
Solution
Principe : chaque processus s’exécute pendant au plus 2 quanta. S’il n’a pas terminé, il retourne en bout de file. Les processus arrivant pendant un quantum, y compris à l’instant exact où il se termine, rejoignent la file avant le processus préempté.
Frise chronologique (quantum = 2) :
| 0–2 | 2–4 | 4–6 | 6–8 | 8–10 | 10–12 | 12–14 | 14–16 | 16–18 | 18–20 | 20–21 | 21–23 | 23–25 | 25–27 | 27–29 | 29–31 | 31–33 | 33–35 | 35–37 | 37–39 | 39–41 | 41–42 |
| P2 | P1 | P3 | P2 | P4 ✓ | P5 | P1 | P7 | P6 | P3 | P2 ✓ | P5 | P1 | P7 ✓ | P6 | P3 | P5 ✓ | P1 ✓ | P6 | P3 | P6 ✓ | P3 ✓ |
Gestion de la file : à chaque fin de quantum, les processus arrivés entre-temps (y compris ceux qui arrivent à l’instant exact où le quantum se termine) rejoignent la file avant le processus préempté, comme dans l’exemple du cours. Par exemple, à t=2 (fin du quantum de P2), P1 (arrivée t=1) et P3 (arrivée t=2) sont placés dans la file, puis P2 préempté passe en bout de file → [P1, P3, P2]. Un processus préempté conserve ensuite sa position dans la file.
| Processus | P1 | P2 | P3 | P4 | P5 | P6 | P7 |
|---|---|---|---|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 | 2 | 6 | 8 | 4 |
| Date d’arrivée | 1 | 0 | 2 | 3 | 4 | 6 | 5 |
| Temps de terminaison | 35 | 21 | 42 | 10 | 33 | 41 | 27 |
| Temps de séjour | 34 | 21 | 40 | 7 | 29 | 35 | 22 |
| Temps d’attente | 26 | 16 | 31 | 5 | 23 | 27 | 18 |
Calculs détaillés :
- P1 : terminaison = 35, séjour = 35 − 1 = 34, attente = 34 − 8 = 26
- P2 : terminaison = 21, séjour = 21 − 0 = 21, attente = 21 − 5 = 16
- P3 : terminaison = 42, séjour = 42 − 2 = 40, attente = 40 − 9 = 31
- P4 : terminaison = 10, séjour = 10 − 3 = 7, attente = 7 − 2 = 5
- P5 : terminaison = 33, séjour = 33 − 4 = 29, attente = 29 − 6 = 23
- P6 : terminaison = 41, séjour = 41 − 6 = 35, attente = 35 − 8 = 27
- P7 : terminaison = 27, séjour = 27 − 5 = 22, attente = 22 − 4 = 18
Temps d’attente moyen = (26 + 16 + 31 + 5 + 23 + 27 + 18) / 7 ≈ 20,9 quanta.
Exercice 5 — Comparaison des trois algorithmes
| Processus | P1 | P2 | P3 | P4 | P5 | P6 | P7 |
|---|---|---|---|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 | 2 | 6 | 8 | 4 |
| Date d’arrivée | 1 | 0 | 2 | 3 | 4 | 6 | 5 |
On considère les processus ci-dessus. Quel algorithme, parmi les trois que l’on a étudiés (FIFO, SJF, Round Robin), permet l’exécution la plus rapide ?
Solution
La durée totale d’exécution est la même pour les trois algorithmes (8+5+9+2+6+8+4 = 42 quanta). C’est le temps d’attente moyen qui les différencie.
FIFO (ordre d’arrivée : P2, P1, P3, P4, P5, P7, P6) :
0 → 5
5 → 13
13 → 22
22 → 24
24 → 30
30 → 34
34 → 42
Temps d’attente moyen = (0+4+11+19+20+25+28) / 7 ≈ 15,3 quanta.
SJF (non préemptif, on choisit le plus court parmi les prêts) :
0 → 5
5 → 7
7 → 11
11 → 17
17 → 25
25 → 33
33 → 42
Temps d’attente moyen = (0+2+2+7+16+19+31) / 7 = 11 quanta.
Round Robin (quantum 2) : d’après l’exercice 4, le temps d’attente moyen est d’environ 20,9 quanta.
Conclusion : c’est le SJF qui permet le temps d’attente moyen le plus faible (11 quanta), devant le FIFO (15,3 quanta) et le Round Robin (20,9 quanta). Cependant, le Round Robin est plus équitable car aucun processus n’attend démesurément longtemps avant d’obtenir un premier accès au processeur, contrairement au FIFO où P6 attend 28 quanta.