8. Ordonnancement des Processus.

Systèmes d’exploitation, 1AI.

 Concepts de base

La multiprogrammation vise à obtenir une

– utilisation optimale (maximale) des ressources
– et aussi un bon temps de réponse pour l’usager

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).

L'ordonnanceur UCT est la partie du SE qui décide quel processus dans

la file « Prêt » obtient l’UCT quand elle devient libre

Systèmes d’exploitation, 1AI. 2

 Les cycles d’un processus

Cycles
Détruire le processus FIN
exécution
Actif
Sélectionner un
Bloquer le O processus
processus
rd
o nn Processus
sélectionné
an Création du
Bloqué ce Nouveau processus
m
en
Débloquer le t
Cycles processus Prêt
E/S ou Synch

Cycles d’UCT et E/S: l’activité d’un processus consiste de séquences d’exécution

sur UCT et d’attentes: d’E/S ou de synchronisation avec autres processus

Systèmes d’exploitation, 1AI. 3

 Ordonnanceur UCT

Définition :

Un Ordonnanceur ou un Scheduler est un sous système ou un module

du système d’exploitation gérant l’attribution du processeur, à tour de

rôle, aux différents processus. Cette attribution se fait suivant une

politique (dite politique d’Ordonnancement ou politique de Scheduling)

définie au niveau du système d’exploitation.

Systèmes d’exploitation, 1AI. 4

 Ordonnanceur UCT

Rôles et caractéristiques :

Afin d’optimiser les performances du système, l’Ordonnanceur doit :

 Servir les processus ayant la même priorité d’une manière équitable;

 Désigner le taux d’occupation du processeur, en traduisant le nombre

de travaux réalisés par unité de temps (rendement). Aussi, il doit

minimiser les temps de réponse;

 Assurer une occupation maximale des ressources de la machine.

Systèmes d’exploitation, 1AI. 5

 Quand invoquer l’ordonnanceur
UCT
L’ordonnanceur UCT doit prendre sa décision chaque fois que le processus
exécutant est interrompu, c-à-d.
1. un processus se présente en tant que Nouveau ou Fin
2. un processus exécutant devient Bloqué
3. un processus change d'Actif à Prêt
4. un processus change de Bloqué à Prêt

 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 processus aura
l’UCT après

Systèmes d’exploitation, 1AI. 6

 Quand invoquer l’ordonnanceur
UCT
 Préemption:
on a préemption si on enlève l’UCT à un processus qui l’avait et qui n'a
pas laissée de son propre initiative
- préemption dans le cas 3, pas de préemption dans le cas 2

 La priorité
à discuter par la suite ...

Systèmes d’exploitation, 1AI. 7

 Critères d’ordonnancement

Il y aura normalement plusieurs processus dans la file prêt

Quand l’UCT devient disponible, lequel choisir?

Critères généraux:
– Bonne utilisation de l’UCT
– Réponse rapide à l’usager

Mais ces critères peuvent être jugés différemment...

Systèmes d’exploitation, 1AI. 8

 Critères spécifiques
d’ordonnancement
➢
Utilisation UCT: pourcentage d’utilisation
➢
Débit = Throughput: nombre de processus qui se terminent
dans l’unité de temps
➢
Temps de rotation = turnaround: le temps pris par un
processus de son arrivée à sa terminaison.
➢
Temps d’attente: attente dans la file prêt (somme de tout le
temps passé en file prêt)
➢
Temps de réponse: le temps entre une demande de l’usager et
la réponse

Systèmes d’exploitation, 1AI. 9

 Critères d’ordonnancement:
maximiser/minimiser
 Utilisation UCT
 à maximiser
 Débit
 à maximiser
 Temps de rotation
 à minimiser
 Temps d’attente
 à minimiser
 Temps de réponse
 à minimiser

Systèmes d’exploitation, 1AI. 10

 Méthodes d’ordonnancement

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

Systèmes d’exploitation, 1AI. 11

 Premier arrivé, premier servi (First
come, first serve, FCFS)

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

Systèmes d’exploitation, 1AI. 12

 Premier arrive, premier servi

Utilisation UCT = 100%

Débit = 3/30 = 0,1 (trx/s)
– 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

Systèmes d’exploitation, 1AI. 13

 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:
– P1 arrive à temps 0 et dure 24
– P2 arrive à temps 2 et dure 3
– P3 arrive à temps 5 et dure 3
Donc P1 attend 0 comme avant
--> P2 attend 24-2, etc.
P1 P2 P3

0 24 27 30
arrivée P2

Systèmes d’exploitation, 1AI. 14

 FCFS Scheduling (Cont.)
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 était 17
 Temps de rotation moyen: (3+6+30)/3 = 13 était 27
 Beaucoup mieux!
 Donc pour cette technique, les temps peuvent varier grandement par
rapport à l’ordre d’arrivée de différent processus

Systèmes d’exploitation, 1AI. 15

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

Le processus qui demande moins d’UCT part le premier

Optimal en principe du point de vue du temps d’attente moyen
– (v. le dernier exemple)

P2 P3 P1

0 3 6 30
Mais comment savons-nous quel processus demande moins d’UCT!
– Supposons pour l’instant qu’on puisse

Systèmes d’exploitation, 1AI. 16

 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
enlevée au processus courant et donnée à ce nouveau
processus
– SRTF: shortest remaining-time first

Sans préemption: on permet au processus courant de

terminer son cycle

Systèmes d’exploitation, 1AI. 17

 Example de SJF sans préemption
Processus Arrivée Cycle UCT
P1 0 7
P2 2 4
P3 4 1
P4 5 4
 SJF (sans préemption)

P1 P3 P2 P4

0 7 8 12 16

P2 arr. P3 arr. P4 arr

 Temps d’attente moyen = (0+(8-2)+(7-4)+(12-5))/4 = (0 + 6 + 3 + 7)/4 = 4
 Temps de rotation moyen = 7+(12-2)+(8-4)+(16-5) = 8

Systèmes d’exploitation, 1AI. 18

 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 était 4
 P1 attend de 2 à 11, P2 de 4 à 5, P4 de 5 à 7
 Temps de rotation moyen = (16+ (7-2) + (5-4) + (11-5))/4 = 7 était 8

Systèmes d’exploitation, 1AI. 19

 Préemption ou non

La préemption est le cas normal pour l’UCT car l’arrivée d’un

nouveau proc cause une interruption et à ce moment là
l’ordonnanceur devra prendre une décision sur le prochain
proc à exécuter

Mais dans quelques ressources la préemption est impossible:

– P.ex. dans une imprimante il faut toujours terminer
l’impression courante avant d’en amorcer une nouvelle

Systèmes d’exploitation, 1AI. 20

 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é
– p.ex. méthode de la moyenne exponentielle

load A
load B Cycle CPU
read file

Attente E/S Cycle E/S

ADD A, B Cycle CPU

write file

Attente E/S Cycle E/S

…

Systèmes d’exploitation, 1AI. 21

 Différentes méthodes en principe

Hypothèse de comportement constant d’un processus:

– Un processus qui a toujours eu des cycles d’UCT de 3
millisecondes en moyenne continuera d’avoir des cycles de 3
ms

Hypothèse de comportement variable d’un processus:

– Un processus qui avant avait des cycles d’UCT de 3ms,
maintenant a allongé ces cycles, qui sont de 10ms
– La durée des cycles les plus récents est considérée plus
importante pour la prévision des prochains cycles

Systèmes d’exploitation, 1AI. 22

 hypothèse de comportement
constant
Ti : la durée du ième cycle de l’UCT pour ce processus
Si : la valeur estimée du ième cycle de l’UCT pour ce processus.
– Sn+1 l’estimée courante
– Sn l’estimée précédente
Un choix simple est:
– Sn+1 = (1/n) Σ{i=1 à n} Ti (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

Systèmes d’exploitation, 1AI. 23

 hypothèse de comportement
variable
Mais les cycles récents peuvent être plus représentatifs des
comportements à venir
La moyenne exponentielle permet de donner différents poids aux
cycles plus ou moins récents:
– Sn+1 = α Tn+ (1-α) Sn ; 0 <= α <= 1

α : le coéfficient d’importance
Tn: la durée du cycle le plus récent
S: l’estimée
– Sn+1 l’estimée courante (après le cycle Tn)
– Sn l’estimée précédente
Systèmes d’exploitation, 1AI. 24
 Pourquoi ‘exponentielle’

Par expansion, nous voyons que le poids de chaque cycle

décroît exponentiellement 0

– Sn+1 = αTn + (1-α)αTn-1 + ... (1-α)i αTn-i + ... + (1-α)n S1

la valeur estimée S1 du 1er cycle peut être fixée à 0 pour

donner priorité max. aux nouveaux processus

Systèmes d’exploitation, 1AI. 25

 Importance de différents valeurs
Durée du cycle de coefficients

S1 = 0 (priorité aux nouveaux processus)

Un coefficient plus élevé réagit plus rapidement aux
changements de comportement
Systèmes d’exploitation, 1AI. 26
 Comment choisir le coefficient α
Un petit α assouplit les changements de comportement d’un processus
– Il donne moins d’importance aux cycles récents
– Il est avantageux quand un processus peut avoir des anomalies de
comportement, après lesquelles il reprend son comportement
précédent
– Cas limite: α = 0
• on reste sur l’estimée initiale
Un gros α réagit rapidement aux changements
– Il donne plus d’importance aux cycles récents
– Il est avantageux quand un processus est susceptible de changer
rapidement de type d’activité et il reste sur ça
– Cas limite: α = 1: S n+1 = Tn
• Le dernier cycle est le seul qui compte

Systèmes d’exploitation, 1AI. 27

 Exercice: Travailler cet exemple

estim.

réel

Systèmes d’exploitation, 1AI. 28

 Le plus court d’abord SJF: critique

➢
Difficulté d’estimer la longueur à l’avance
➢
Plus pratique pour l’ordonnancement travaux que pour
l’ordonnancement processus
– on peut plus facilement prévoir la durée d’un travail entier que la
durée d’un cycle
➢
Il y a assignation implicite de priorités: préférences aux travaux
plus courts
– Famine possible pour les travaux aux cycles longs

Systèmes d’exploitation, 1AI. 29

 Difficultés majeures avec les
méthodes discutées
Premier arrivé, premier servi, FCFS:
– Temps moyen d’attente non-optimal
– Mauvaise utilisation des ressources s’il y a apport continu de
processus aux cycles longs

Plus court servi, SJF:

– Nous venons de voir …

Donc besoin d’une méthode systématiquement préemptive

– Le tourniquet

Systèmes d’exploitation, 1AI. 30

 Difficultés majeures avec les
méthodes discutées

– si vous faites toujours les devoirs les plus courts en premier,

vous pourriez avoir l’impression de faire beaucoup mais vous
pourriez ne jamais arriver aux plus longs…
– si vous faites les devoirs dans l’ordre d’arrivée, les longs
pourraient vous bloquer pour longtemps…
– donc votre solution est de donner un peu de temps à chacun,
cycliquement

Systèmes d’exploitation, 1AI. 31

 Tourniquet = Round-Robin (RR)
Le plus utilisé en pratique

➢
Chaque processus est alloué une tranche de temps (p.ex. 10-100
millisecs.) pour exécuter

Tranche aussi appelée quantum
➢
S’il exécute pour tranche entière sans aucunes interruptions, il est
interrompu par la minuterie et l’UCT est donnée à un autre processus
➢
Le processus interrompu redevient prêt (à la fin de la file)
➢
Méthode préemptive
P[0] P[1]
La file prêt est un
P[7] P[2]
cercle (dont RR)
P[6] P[3]

P[5] P[4]

Systèmes d’exploitation, 1AI. 32

 Exemple: Tourniquet tranche = 20
Processus Cycle
P1 53
P2 17
P3 68
P4 24

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

 Calculez et Observez :
 temps de rotation et temps d’attente moyens beaucoup plus
élevés que SJF
 mais aucun processus n’est favorisé

Systèmes d’exploitation, 1AI. 33

 Performance de tourniquet

S’il y a n processus dans la file prêt et la tranche est t, alors

chaque processus reçoit 1/n du temps UCT dans unités de
durée max. t

➢
Si t grand ⇒ FCFS
➢
Si t petit... nous verrons

Systèmes d’exploitation, 1AI. 34

 Une petite tranche augmente les
commutations de contexte (temps de SE)

Systèmes d’exploitation, 1AI. 35

 Exemple pour voir l’importance
d’un bon choix de tranche
à développer comme exercice :

Trois cycles:
– A, B, C, toutes de 10 cycles
Essayer avec:
– t=1
– t=10
Dans ce deuxième cas, tourniquet fonctionne comme FIFO et
le temps de rotation moyen est meilleur

Systèmes d’exploitation, 1AI. 36

 Le temps de rotation (turnaround)
varie avec la tranche

= FIFO

Exemple qui montre que le temps de rotation moyen n’améliore pas

nécessairement en augmentant la tranche (sans considérer les
temps de commutation contexte)

Systèmes d’exploitation, 1AI. 37

 Choix de la tranche pour le
tourniquet
 doit être beaucoup plus grande que le temps requis pour
exécuter le changement de contexte

 devrait être un peu plus grand que le cycle d’UCT typique

 plus précisément on pourrait dire: un peu plus grand que la
médiane des durées des cycles des processus en exécution
 pour donner le temps à la plupart des proc de terminer leur
cycle.

Systèmes d’exploitation, 1AI. 38

 Comment déterminer la tranche
en pratique

Évidemment la durée médiane des cycles des processus en

attente est impossible à déterminer!

En pratique, les observations passées peuvent être utilisées:

– le SE peut garder une trace des durées des cycles des
processus récemment exécutés et ajuster la tranche
périodiquement

Systèmes d’exploitation, 1AI. 39

 Priorités

Affectation d’une priorité à chaque processus (p.ex. un nombre

entier)
– souvent les petits chiffres dénotent des hautes priorités
• 0 la plus haute
L’UCT est donnée au processus prêt avec la plus haute
priorité
– avec ou sans préemption
– il y a une file prêt pour chaque priorité

Systèmes d’exploitation, 1AI. 40

 Problème possible avec les
priorités

Famine: les processus moins prioritaires n’arrivent jamais à

s'exécuter
Solution: vieillissement:
– modifier la priorité d’un processus en fonction de son âge
et de son historique d’exécution
– le processus change de file d'attente
Plus en général, la modification dynamique des priorités est
une politique souvent utilisée

Systèmes d’exploitation, 1AI. 41

 Files à plusieurs niveaux
(multiples)
La file prêt est séparée en plusieurs files, p.ex.
– travaux `d’arrière-plan` (background - batch)
– travaux `de premier plan` (foreground - interactive)
Chaque file a son propre algorithme d’ordonnancement, p.ex.
– FCFS pour arrière-plan
– Tourniquet pour premier plan
Comment ordonnancer entre files?
– Priorité fixe à chaque file → famine possible, ou
– Chaque file reçoit un certain pourcentage de temps UCT, p.ex.
• 80% pour arrière-plan
• 20% pour premier plan

Systèmes d’exploitation, 1AI. 42

 Ordonnancement avec files
multiples (ex.: serveur principal d’une université)

Systèmes d’exploitation, 1AI. 43

 Files multiples et à retour

Un processus peut passer d’une file à l’autre, p.ex. quand il a

passé trop de temps dans une file
À déterminer:
– nombre de files
– algorithmes d’ordonnancement pour chaque file
– algorithmes pour décider quand un proc doit passer d’une file
à l'autre
– algorithme pour déterminer, pour un proc qui devient prêt, sur
quelle file il doit être mis

Systèmes d’exploitation, 1AI. 44

 Files multiples et à retour

PRIO = 0
la + élevée

PRIO = 1

PRIO = 2

Systèmes d’exploitation, 1AI. 45

 Exemple de files multiples à
retour
Trois files:
– Q0: tourniquet, tranche = 8 msecs
– Q1: tourniquet, tranche = 16 msecs
– Q2: FCFS
Ordonnancement:
– Un nouveau processus entre dans Q0, il reçoit 8 msecs
d ’UCT
– S’il ne finit pas dans les 8 msecs, il est mis dans Q1, il reçoit
16 msecs additionnels
– S’il ne finit pas encore, il est interrompu et mis dans Q2
– Si plus tard il commence à avoir des cycles plus courts, il
pourrait retourner à Q0 ou Q1

Systèmes d’exploitation, 1AI. 46

 En pratique...

➢
Les méthodes que nous avons vu sont toutes utilisées
➢
Les SE sophistiqués fournissent aux gérants de grands
systèmes des librairies de méthodes, qu’ils peuvent choisir et
combiner au besoin après avoir observé le comportement du
système
➢
Pour chaque méthode, plusieurs paramètres sont
disponibles: p.ex. durée des tranches, coefficients, etc.
➢
Ces méthodes évidemment sont importantes surtout pour les
grands ordinateurs qui ont des fortes charges de travail

Systèmes d’exploitation, 1AI. 47

 Aussi…
Notre étude des méthodes d’ordonnancement est théorique, ne considère
pas en détail tous les problèmes qui se présentent dans l’ordonnancement
UCT
P.ex. les ordonnanceurs UCT ne peuvent pas donner l’UCT à un
processus pour tout le temps dont il a besoin
– Car en pratique, l’UCT sera souvent interrompue par quelque
événement externe avant la fin de son cycle
Cependant les mêmes principes d’ordonnancement s’appliquent à unités
qui ne peuvent pas être interrompues, comme une imprimante, une unité
disque, etc.
Dans le cas de ces unités, on pourrait avoir des infos complètes
concernant le temps de cycle prévu, etc.
Aussi, cette étude ne considère pas du tout les temps d’exécution de
l’ordonnanceur, du dispatcheur, etc.
Systèmes d’exploitation, 1AI. 48
 Ordonnancement avec plusieurs
UCTs identiques: homogénéité
UCT
Méthodes symétriques: chaque
UCT peut exécuter UCT
l’ordonnancement et la répartition UCT
– Une seule liste prêt pour
toutes les UCTs (division UCT
travail = load sharing)
Méthodes asymétriques: certaines UCT
fonctions sont réservées à des
UCT spécifiques UCT
– Files d’attentes séparées UCT
pour chaque UCT
UCT

Systèmes d’exploitation, 1AI. 49

 Symétrique ou non?
La manière la plus normale de gérer plusieurs UCT est la
symétrique
– Plus simple à gérer
Cependant l’asymétrique a un avantage important:
– Étant donné que chaque UCT exécute des
fonctionnalités indépendantes, le temps perdu en
synchronisation est réduit!
• Chapitre suivant

Systèmes d’exploitation, 1AI. 50

 Systèmes temps réel
systèmes temps réel rigides (hard):
– les échéances sont critiques (p.ex. contrôle d’une chaîne
d'assemblage, animation graphique)
– il est essentiel de connaître la durée des fonctions
critiques
– il doit être possible de garantir que ces fonctions sont
effectivement exécutées dans ce temps (réservation de
ressources)
– ceci demande une structure de système très particulière
systèmes temps réel souples (soft):
– les échéances sont importantes, mais ne sont pas
critiques (p.ex. systèmes téléphoniques)
– les processus critiques reçoivent la priorité

Systèmes d’exploitation, 1AI. 51

 Systèmes temps réel:
Problèmes d’attente dans plus. systèmes (ex. UNIX)

Dans UNIX ‘classique’ il n’est pas permis d’effectuer

changement de contexte pendant un appel du système - et ces
appels peuvent être longs
Pour le temps réel il est nécessaire de permettre la préemption
des appels de systèmes ou du noyau en général
Donc Unix ‘classique’ n’est pas considéré approprié pour le
temps réel
Mais des variétés appropriées de UNIX ont été conçues

Systèmes d’exploitation, 1AI. 52

 Inversion de priorité et héritage de
priorités

Quand un processus de haute priorité doit attendre pour des

processus de moindre priorité (p.ex. a besoin de données
produites par ces derniers)

Pour permettre à ces derniers de finir rapidement, on peut lui

faire hériter la priorité du processus plus prioritaire

Systèmes d’exploitation, 1AI. 53

 Tableau de comparaison

Le tableau suivant fait une comparaison

globale des différentes techniques étudiées

Assurez-vous de comprendre chaque case

Systèmes d’exploitation, 1AI. 54

 Critère Préempt Motivation Temps de rotat. Temps de Effect sur Famine
sélection et atten. système processus
PAPS Max [w] non Simplicité Variable Minim. Favor. proc. Non
FCFS trib. UCT

Variable selon Élevé si

Tourniq. Tour fixe oui Equité tranche, tranches Équitable Non
Normalement courtes
élevé

Bon pour
PCS Min[s] non Optimisation des Optimal, mais Peut être élevé proc. courts, Possible
temps souffre si des (pour estimer pénalise
SJF
procs longs les longs. des proc. longs
arrivent au début trames)

PCS Min[s-e] oui Évite le Meilleur, même Peut être élevé Pénalise plus
SJF problème de si des procs encore Possible
préemp. procs longs au longs arrivent au proc. longs
début début

Files v. détails oui Varie la longueur Variable Peut être élévé Variable Peut être
multiniv. des tranches en évitée
fonction des
besoins

w: temps total dans système jusqu’à présent; e: temps en exec jusqu’à présent s: temps demandé;

Systèmes d’exploitation, 1AI. 55