Projet DVD-MIAGE 2010 : Corrigé des Exercices sur l'Ordonnancement
Exercice 1 : Questions de cours sur les algorithmes d'ordonnancement
| Nom | Définition | Préemptif |
|---|
| First Come First Serve (FCFS) | Selon l'ordre d'arrivée des processus. | Non |
| Shortest Job First (SJF) | Le processus avec le temps de traitement le plus court est exécuté en premier. | Non |
| Shortest Remaining Time First (SRTF) | Le processus avec le temps de traitement restant le plus court est exécuté en priorité. | Oui |
| Round-Robin (RR) | Accès au processeur par tranches de temps (quantum) pour garantir une équité de service. | Oui (partiel) |
| Ordonnancement à priorités | Les processus sont exécutés selon leurs priorités attribuées. | Non (sauf si préemptif) |
2) L'augmentation du quantum de temps dans l'algorithme Round-Robin rapproche progressivement son comportement de celui du FCFS. Pour un quantum tendant vers l'infini, l'algorithme RR devient équivalent au FCFS.
3) Dans un contexte d'ordonnancement non préemptif et sans entrées/sorties, chaque processus s'exécute sans interruption. Pour ordonnancer n processus, il existe n! (factorielle de n) permutations possibles. Cela signifie qu'il y a n × (n-1) × (n-2) × ... × 2 × 1 façons différentes d'ordonnancer ces processus.
4) L'ordonnancement par priorité consiste à sélectionner le processus suivant en fonction d'une valeur associée, ici le temps nécessaire à son exécution. Le processus avec le temps le plus court est exécuté en premier.
Exercice 2 : Comparaison des algorithmes FCFS, RR, SJF et SRT
| Temps | Processus | Temps de rotation (FCFS) | Temps d'attente (FCFS) | Rendement (FCFS) |
|---|
| 0-5 | P1 : 30 | P1 : 1 | P1 : 0,86 |
| 5-10 | P2 : 7 | P2 : 10 | P2 : 0,35 |
| 10-15 | P3 : 9 | P3 : 50 | P3 : 0,44 |
| 15-20 | P4 : 12 | P4 : 70 | P4 : 0,42 |
| 20 | P5 : 31 | P5 : 100 | P5 : 0,29 |
| Moyenne | 8,64 | 60 | 0,58 |
| Temps | Processus | Temps de rotation (RR q=1) | Temps d'attente (RR q=1) | Rendement (RR q=1) |
|---|
| 0-5 | P1 : 4 | P1 : 1 | P1 : 0,75 |
| 5-10 | P2 : 17 | P2 : 11 | P2 : 0,35 |
| 10-15 | P3 : 13 | P3 : 9 | P3 : 0,31 |
| 15-20 | P4 : 14 | P4 : 0 | P4 : 0,36 |
| 20 | P5 : 75 | P5 : 29 | P5 : 0,29 |
| Moyenne | 11,7 | 7 | 0,41 |
| Temps | Processus | Temps de rotation (RR q=4) | Temps d'attente (RR q=4) | Rendement (RR q=4) |
|---|
| 0-5 | P1 : 30 | P1 : 1 | P1 : 0,86 |
| 5-10 | P2 : 17 | P2 : 11 | P2 : 0,35 |
| 10-15 | P3 : 73 | P3 : 57 | P3 : 0,57 |
| 15-20 | P4 : 149 | P4 : 36 | P4 : 0,36 |
| 20 | P5 : 97 | P5 : 22 | P5 : 0,22 |
| Moyenne | 106 | 30 | 0,5 |
| Temps | Processus | Temps de rotation (SJF non préemptif) | Temps d'attente (SJF non préemptif) | Rendement (SJF non préemptif) |
|---|
| 0-5 | P1 : 30 | P1 : 1 | P1 : 0,86 |
| 5-10 | P2 : 7 | P2 : 10 | P2 : 0,35 |
| 10-15 | P3 : 11 | P3 : 70 | P3 : 0,36 |
| 15-20 | P4 : 149 | P4 : 36 | P4 : 0,36 |
| 20 | P5 : 31 | P5 : 67 | P5 : 0,67 |
| Moyenne | 7,63 | 30 | 0,65 |
| Temps | Processus | Temps de rotation (SRTF) | Temps d'attente (SRTF) | Rendement (SRTF) |
|---|
| 0-5 | A : 30 | A : 1 | A : 0,75 |
| 5-10 | B : 137 | B : 46 | B : 0,46 |
| 10-15 | C : 40 | C : 1 | C : 0,76 |
| 15-20 | D : 73 | D : 57 | D : 0,57 |
| 20 | P5 : 20 | P5 : 1 | P5 : 0,76 |
| Moyenne | 7,23 | 20 | 0,76 |
Exercice 3 : Ordonnancement FCFS, RR, SJF préemptif et non-préemptif
| Temps | Processus | Temps de rotation (FCFS) | Temps d'attente (FCFS) | Rendement (FCFS) |
|---|
| 0-5 | A : 30 | A : 1 | A : 0,75 |
| 5-10 | B : 8 | B : 20 | B : 0,75 |
| 10-15 | C : 95 | C : 44 | C : 0,44 |
| 15-20 | D : 97 | D : 29 | D : 0,29 |
| Moyenne | 7,25 | 3,50 | 0,58 |
| Temps | Processus | Temps de rotation (SJF non préemptif) | Temps d'attente (SJF non préemptif) | Rendement (SJF non préemptif) |
|---|
| 0-5 | A : 30 | A : 1 | A : 0,75 |
| 5-10 | B : 8 | B : 20 | B : 0,75 |
| 10-15 | C : 117 | C : 36 | C : 0,36 |
| 15-20 | D : 53 | D : 4 | D : 0,4 |
| Moyenne | 6,75 | 30,63 | 0,63 |
