49
CHAPITRE 3
L’ordonnancement des processus
Introduction
50
Si le processeur devient inactif :
le SE doit sélectionner un processus de la file d’attente des processus prêts
Et lui passe le contrôle.
D’une manière plus concrète, cette tâche est prise en charge par deux
« routines système » :
le Scheduleur (Ordonnanceur).
le Dispatcheur
Ordonnanceur et Dispatcheur
51
Ordonnanceur :
Sélectionne le processus suivant à exécuter parmi ceux
qui sont prêts.
Dispatcheur :
Il s’occupe de l’allocation du processeur à un processus
sélectionné par l’ « Ordonnanceur »
Étapes :
Commutation de contexte : sauvegarder le contexte du processus
qui doit relâcher le processeur et charger le contexte de celui
qui aura le prochain cycle processeur
Branchement : se brancher au bon emplacement dans le
processus utilisateur pour le faire démarrer.
Problématique de l’ordonnancement
52
Un ordonnanceur doit être capable de résoudre les problèmes
suivants:
Comment choisir le prochain processus à exécuter?
Combien de « temps processeur » à allouer au processus choisi?
Ordonnancement des processus
53
Objectifs :
S'assurer que chaque processus en attente d'exécution reçoive sa
part de temps processeur.
Minimiser le temps de réponse.
Utiliser le processeur à 100%.
Utilisation équilibrée des ressources.
Prendre en compte des priorités.
Réduire le nombre et la durée des changements de contexte.
→ impossible de créer un algorithme qui optimise tous les critères
de façon simultanée.
Critères d’ordonnancement
54
À maximiser
Utilisation
UCT : pourcentage d’utilisation
Débit : nombre de processus qui complètent dans l’unité de temps
À minimiser
Temps de réponse :
Temps de la première exécution – temps arrivée
Temps de rotation (turnaround/séjour) :
Temps fin d’exécution – temps arrivée.
Temps d’attente : la somme des durées d’attentes dans la file « prêt »
Exemple de mesure
55 P1 P2 P3 P4
P1 P2 P3 P4 P1 P2 Temps
0 45 7 10,11,12 20 22 24
Processus Temps de Temps de rotation Temps d’attente
réponse (ou de séjour)
P1
P2
P3
P4 Processus Durée Arrivée
P1 7 0
Utilisation de l’UCT : ? ; Débit ?
P2 7 4
Temps moyen de réponse : ?
P3 2 7
Temps moyen de rotation : ?
P4 8 11
Temps moyen d’attente : ?
Processus Durée Arrivée
Exemple de mesure P1
P2
7
7
0
4
P3 P4 P3 2 7
56 P1 P2
P4 8 11
P1 P2 P3 P4 P1 P2 Temps
0 45 7 10,11,12 20 22 24
Processus Temps de Temps de rotation Temps d’attente
réponse (ou de séjour)
P1 0=0–0 22 = 22 – 0 15 = 0 + (20 – 5)
P2 1=5–4 20 = 24 – 4 13=(5-4)+(22-10)
P3 3 = 10 – 7 5 = 12 – 7 3 = 10 – 7
P4 1 = 12 – 11 9 = 20 – 11 1 = 12 – 11
Utilisation de l’UCT : 100% ; Débit : 4/24 = 0.16
Temps moyen de réponse : (0+1+3+1)/4 =1,25
Temps moyen de rotation : (22+20+5+9)/4=14
Temps moyen d’attente : (15+13+3+1)/4=8
Types d’ordonnancement
57
Il existe 2 types d’ordonnancement :
Ordonnancement coopératif (sans réquisition) :
Ordonnancement jusqu’à achèvement : le processus élu garde le contrôle jusqu’à
épuisement du temps qui lui a été alloué même si des processus plus prioritaires ont
atteint la liste des Prêts (PAPS/FCFS, PCA/SJF)
Ordonnancement préemptif (avec réquisition)
l’Ordonnanceur peut interrompre un processus en cours d’exécution (Circulaire/RR,
SRTF, PRIO)
Premier Arrivé, Premier Servi (PAPS)
First Come, First Serve (FCFS)
58
Ordonnancement non préemptif.
Principe :
Quand un processus est prêt à s’exécuter, il est mis en queue de la file
d’attente des processus prêts.
Quand le processeur devient libre, il est alloué au processus se trouvant en
tête de file d’attente des processus prêts.
Le processus élu relâche le processeur s’il se termine ou s’il demande une
entrée sortie
Premier Arrivé, Premier Servi (PAPS)
First Come, First Serve (FCFS)
59
Processus Durée Arrivée
P1 24 2
P2 P1 P3 Temps P2 3 0
0 3 27 30 P3 3 5
Processus Temps de Temps de rotation
réponse (ou de séjour)
P1 1=3–2 25 = 27 – 2
P2 0=0–0 3=3–0
P3 22 = 27 – 5 25 = 30 – 5
Utilisation de l’UCT : 100% ; Débit : 3/30 = 0.1;
Temps moyen de réponse : (1+0+22)/3 =7,66 = Temps moyen d’attente
Temps moyen de rotation : (25+3+25)/3=17,66
Plus Court d’abord = Shortest Job First (SJF)
60
Le processus le plus court part le premier
Optimal, théoriquement, du point de vue du temps d’attente moyen
Mais comment savons-nous ? (le plus court)
Plus Court d’abord = Shortest Job First (SJF)
61
Processus Durée Arrivée
P1 P3 P2 P4
P1 7 0
P2 4 2
0 3 7 8 12 16
P3 1 4
Processus Temps de Temps de rotation P4 4 5
réponse (ou de séjour)
P1 0=0–0 7=7–0
P2 6=8–2 10 = 12 – 2
P3 3=7–4 4=8–4
P4 7 = 12 – 5 11 = 16 – 5
Utilisation de l’UCT : 100% ; Débit : 4/16 = 0,25;
Temps moyen de réponse : (0+6+3+7)/4 = 4 = Temps moyen d’attente
Temps moyen de rotation : (7 + 10 +4 + 11)/4=8
Critiques de SJF
62
Les processus longs souffriront de famine lorsqu’il y a un apport
constant de processus courts
La préemption est nécessaire pour un environnements à temps partagé
Un processus long peut monopoliser l’UCT s’il est le 1er à entrer dans le
système et il ne fait pas d’E/S
Circulaire / Tourniquet / Round-Robin (RR)
63
Algorithme d’ordonnancement préemptive
Le plus utilisé en pratique
Un quantum (q ou Q) de temps est alloué pour chaque
processus (exemple : 10-100 millisecs.) pour s’exécuter.
S’il s’exécute pour un quantum entier sans aucune interruption,
il est interrompu par la minuterie.
→ l ’UCT est donnée à un autre processus
Le processus interrompu redevient prêt (à la fin de la file)
→ La file des processus « prêts » est un cercle P[0] P[1]
P[7] P[2]
P[6] P[3]
P[5] P[4]
Performance de tourniquet
64
Si q grand FCFS
Si q petit Un petit quantum augmente les commutations de contexte.
Exemple :
Troisprocessus : A, B, C qui arrivent à t=0 et durent 5 u.t
Essayer avec :
q =1
q = 10
Dans le deuxième cas, tourniquet fonctionne comme FCFS et le temps de
rotation moyen est meilleur
Circulaire / Tourniquet / Round-Robin (RR)
65 Quantum = 20
Processus Durée Arrivée
P1 53 0
P2 17 0
P3 68 0
P4 24 0
Circulaire / Tourniquet / Round-Robin (RR)
66 Quantum = 20 Processus Durée Arrivée
P1 53 0
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 P2 17 0
P3 68 0
0 20 37 57 77 97 117 121 134 154 162 P4 24 0
Processus Temps de Temps de rotation (ou Temps d’attente
réponse de séjour)
P1
P2
P3
P4
Utilisation de l’UCT : ? ; Débit : ?
Temps moyen de réponse :
Temps moyen de rotation :
Temps moyen d’attente :
Circulaire / Tourniquet / Round-Robin (RR)
67 Quantum = 20 Processus Durée Arrivée
P1 53 0
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 P2 17 0
P3 68 0
0 20 37 57 77 97 117 121 134 154 162 P4 24 0
Processus Temps de Temps de rotation (ou Temps d’attente
réponse de séjour)
P1 0=0–0 134 = 134 – 0 81 = (77-20) + (121- 97)
P2 20 = 20 – 0 37 = 37 – 0 20 = 20 – 0
P3 37 = 37 – 0 162 = 162 – 0 94 = (37-0) + (97-57) +(134-117)
P4 57 = 57 – 0 121 = 121 – 0 97 = (57-0) + (117-77)
Utilisation de l’UCT : 100% ; Débit : 4/162 = 0.02
Temps moyen de réponse : 28,5
Temps moyen de rotation : 113,5
Temps moyen d’attente : 73
SRTF: shortest remaining-time first
68
C’est l’ordonnancement du plus petit temps de séjour ou « Shortest
Remaining Time first ».
Version préemptive de l’algorithme SJF.
Déroulement :
Un processus arrive dans la file de processus.
L’ordonnanceur compare la durée espérée de terminaison pour ce processus
contre la valeur du processus actuellement en exécution.
Si le temps du nouveau processus est plus petit, il rentre en exécution
immédiatement.
SRTF: shortest remaining-time first
Processus Durée Arrivée
P1 P2 P3 P2 P4 P1
P1 7 0
P2 4 2
0 3 7 11 16
P3 1 4
Processus Temps de Temps de rotation Temps P4 4 5
réponse (ou de séjour) d’attente
P1 0=0–0 16 = 16 – 0 9 = 11-2
P2 0=2–2 5=7–2 1=5–4
P3 0=4–4 1=5–4 0=4–4
P4 2=7–5 6 = 11 – 5 2=7–5
Utilisation de l’UCT : 100% ; Débit : 4/16 = 0,25;
Temps moyen de réponse : 2/4 = 0,5 // Temps moyen de rotation : 28/4=6,25
Temps moyen d’attente : 12/4 = 3
Ordonnancement basé sur les priorités (PRIO)
70
L’ordonnanceur à priorité donne à chaque processus une priorité qui peut être statique ou
dynamique.
Le choix du processus à élire dépend des priorités des processus prêts.
Les processus ayant la même priorité sont regroupés dans une file FIFO
Il y a autant de files qu’il y a de niveau de priorité
L’ordonnanceur choisit le processus le plus prioritaire qui se trouve en tête de file
Attribution et évolution des priorités (dans le cas des priorités dynamique) :
L’ordonnanceur diminue régulièrement la priorité du processus actif (ou augmente la priorité des
autres) afin d’empêcher le processus de priorité élevée de s’exécuter pour une longue durée.
Priorités avec files d’attente
71
La priorité du processus en cours d’exécution (A) est toujours comparée à celle
du processus prêt (B) le plus prioritaire (tête de file)
Une commutation entre les deux processus est exécutée quant la priorité de (A)
est inférieure à celle de (B)
Dans ce cas, le processus suspendu est inséré à la fin de la file correspondant à
la nouvelle priorité calculée.
Priorité 4 P5 P3 P1
Priorité 3 P2
Priorité 2 P4 P6
Priorité 1 P7
Priorités avec files d’attente
72
Processus Durée Arrivée Priorité 1 E
A 10 0 3
B 5 2 7 2 D C
C 15 5 2 3 A
D 1 10 2
E 3 15 1 7 B
A C E D C A B
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
B C D E
Priorités avec files d’attente
73
Processus Durée Arrivée Priorité 1 E
A 10 0 3
B 5 2 7 2 D C
C 15 5 2 3 A
D 1 10 2
E 3 15 1 7 B
A C E D C A B
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
B C D E
Priorités avec files d’attente
74
A C E D C A B
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
B C D E
Processus Temps de Temps de rotation (ou de Temps d’attente
réponse séjour)
A 0=0–0 29 19 = 24 – 5
B 27 = 29 – 2 32 27 = 29 – 2
C 0=5–5 19 4 = 19 – 15
D 8 = 18 – 10 9 8 = 18 – 10
E 0 = 15 – 15 3 0=3–3
Utilisation de l’UCT : 100% ; Débit : 5/34 = 0,14;
Temps moyen de réponse : 40/5 = 8 // Temps moyen de rotation : 19,2
Temps moyen d’attente : 12,4
