Module 4 - Ordonnancement Processus

Lecture: Chapitre 5

1
 Aperçu du module

Concepts de base

Critères d’ordonnancement

Algorithmes d’ordonnancement

Ordonnancement de multiprocesseurs

Évaluation d’algorithmes

2 Ch. 5
 Diagramme de transition d`états d`un processus

3 Ch. 5
 Files d’attente de processus pour
ordonnancement

file prêt

Nous ferons l’hypothèse que le premier processus dans une file est celui
qui utilise la ressource: ici, proc7 exécute
4 Ch. 5
 Concepts de base

La multiprogrammation est conçue pour obtenir
une utilisation maximale des ressources, surtout
l’UCT

L`ordonnanceur UCT est la partie du SE qui
décide quel processus dans la file ready/prêt
obtient l ’UCT quand elle devient libre
 doit viser à une utilisation optimale de l ’UCT

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).

Doit comprendre le comportement des processus
 Pour faire de bonne décision d’ordonnancement

5 Ch. 5
 Les cycles d’un processus


Cycles (bursts) d’UCT et E/S: l’exécution d’un processus
consiste de séquences d’exécution sur UCT et d’attentes
E/S
6 Ch. 5
 Quand invoquer l’ordonnanceur

L ’ordonnanceur doit prendre sa décision chaque fois que le
processus exécutant est interrompu, c’e-à.-d.
 un processus se présente en tant que nouveau ou se termine ou
 un processus exécutant devient bloqué en attente
 un processus change d’exécutant/running à prêt/ready
 un processus change de attente à prêt/read
 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 proc ou fil aura l’UCT après

Préemption: on a préemption dans les derniers deux cas si on
enlève l’UCT à un processus qui l’avait et peut continuer à s’en
servir

Dans les 1ers deux cas, il n’y a pas de préemption

Plusieurs pbs à résoudre dans le cas de préemption

7 Ch. 5
 Dispatcheur


Le code du SE qui donne le contrôle au
processus choisi par l’ordonnanceur. Il
doit se préoccuper de:
 changer de contexte
 changer à mode usager
 réamorcer le processus choisi

Attente de dispatcheur (dispatcher latency)
 le temps nécessaire pour exécuter les
fonctions du dispatcheur
 il est souvent négligé, il faut supposer qu’il soit
petit par rapport à la longueur d’un cycle

8 Ch. 5
 Critères d’ordonnancement

Il y aura normalement plusieurs processus
dans la file prêt


Quand l’UCT devient disponible, lequel choisir?


L’idée générale est d’effectuer le choix dans
l’intérêt de l’efficacité d’utilisation de la
machine


Mais cette dernière peut être jugée selon
différents critères…

9 Ch. 5
 Critères d’ordonnancement

Raison principale pour l’ordonnancement
 Pourcentage d ’utilisation: garder UCT et modules E/S
occupés

Systèmes à temps partagés?
 Temps de réponse (pour les systèmes interactifs): le temps
entre une demande et la réponse

Serveurs?
 Débit = Throughput: nombre de processus qui complètent
dans l ’unité de temps

Systèmes de traitement par lots (batch)?
 Temps de rotation = turnaround: le temps pris par le proc de
son arrivée à sa termin.

Systèmes chargés?
 Temps d’attente: attente dans la file prêt (somme de tout le
temps passé en file prêt)

10 Ch. 5
 Critères d’ordonnancement: maximiser/minimiser

À maximiser
 Utilisation UCT: pourcentage d’utilisation
 Débit = Throughput: nombre de processus qui
complètent dans l ’unité de temps

À minimiser
 Temps de réponse (pour les systèmes interactifs): le
temps entre une demande et la réponse
 Temps de rotation (turnaround): temps terminaison
moins temps arrivée
 Temps d’attente: attente dans la file prêt

11 Ch. 5
 Exemple de mesure des critères d’ordonnancement
P1 P2 P3 P4 Process arrival

P1 P2 P3 P4 P1 P2
Time 0 45 7 10,11,12 20 22 24

Utilisation de l’UCT:
 100%

Temps de réponse (P3, P2):
 P :3
3
 P :1
2

Débit :
 4/24

Temps de rotation (P3, P2):
 P : 5
3
 P : 20
2

Temps d’attente (P2):
 P : 13
12 2 Ch. 5
 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

13 Ch. 5
 Premier arrivé, premier servi (First come, first serve, FCFS)

• Notez, aucune préemption

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

14 Ch. 5
 Premier arrivé, premier servi

Utilisation UCT = 100%

Débit = 3/30 = 0,1
 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

15 Ch. 5
 Ordonnancement FCFS (suite)
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

Beaucoup mieux!

Donc pour cette technique, le temps d’attente moyen
peut varier grandement

Exercice: calculer aussi le temps moyen de rotation, débit, etc.

16 Ch. 5
 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:
 P2 arrive à temps 0
 P1 arrive à temps 2
 P3 arrive à temps 5

17 Ch. 5
 Effet d’accumulation (convoy effect) dans FCFS

Supposons un processus tributaire de l’UCT et
plusieurs tributaires de l`E/S (situation assez
normale)

Les processus tributaires de l’E/S attendent pour
l ’UCT: E/S sous-utilisée (*)

Le processus tributaire de l’UCT fait une E/S: les
autres proc exécutent rapidement leur cycle UCT
et retournent sur l’attente E/S: UCT sous-utilisée

Processus tributaire de l’UCT fini son E/S, puis les
autres procs aussi : retour à la situation (*)

Une possibilité: interrompre de temps en temps le
proc tributaires de l’UCT pour permettre aux
autres procs d’exécuter (préemption)

18 Ch. 5
 Plus Court d’abord = Shortest Job First (SJF)


Le processus le plus court part le
premier

Optimal en principe du point de vue
du temps d’attente moyen
 (v. le dernier exemple)

Mais comment savons-nous

19 Ch. 5
 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 donnée à
ce nouveau processus
 SRTF: shortest remaining-time first

Sans préemption: on permet au processus
courant de terminer son cycle
 Observation: SRTF est plus logique car de toute façon le
processus exécutant sera interrompu par l’arrivée du
nouveau processus
 Il est retourné à l’état prêt

20 Ch. 5
 Exemple de SJF sans préemption
Processus Arrivée Cycle
P1 0 7
P2 2 4
P3 4 1
P4 5 4


SJF (sans préemption)

P1 P3 P2 P4

0 3 7 8 12 16

P2 arr. P3 arr. P4 arr


Temps d’attente moyen = (0 + 6 + 3 + 7)/4 = 4

21 Ch. 5
 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

Temps . P3 arr. d`attente
P2 arrmoyen P4 arr = (9 + 1 + 0 +2)/4 = 3
 P1 attend de 2 à 11, P2 de 4 à 5, P4 de 5 à 7

22 Ch. 5
 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. moyenne exponentielle

23 Ch. 5
 Estimation de la durée du prochain cycle

Ti : la durée du ième cycle de l’UCT pour
ce processus

Si : la valeur estimée du le ième cycle de
l’UCT pour ce processus. Un choix simple
est: n

 S n+1  T
= (1/n)  (une simple
i 1
i

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

24 Ch. 5
 Le plus court d’abord SJF: critique

Difficulté d’estimer la longueur à l’avance

Les processus longs souffriront de famine lorsqu’il
y a un apport constant de processus courts

La préemption est nécessaire pour 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

Il y a assignation implicite de priorités:
préférences aux travaux plus courts

25 Ch. 5
 Priorités

Affectation d’une priorité à chaque processus (p.ex. un
nombre entier)
 souvent les petits chiffres dénotent des hautes priorités (dans
UNIX)
 0 la plus haute
 Windows fait l’inverse – donne un plus haute priorité aux plus
grands chiffres

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é

Priorités sont explicites
 Pour raisons politiques ou techniques

Priorités implicites
 Voir SJF - critiques

26 Ch. 5
 Problème possible avec les priorités

Famine: les processus moins prioritaires
n’arrivent jamais à 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 (v. files à
rétroaction ou retour)

Que faire avec les processus de même priorités?
 FCFS
 Ajoutons la préemption -> le Tourniquet

27 Ch. 5
 Tourniquet = Round-Robin (RR)
Le plus utilisé en pratique

Chaque processus est alloué un quantum de
temps (p.ex. 10-100 millisecs.) pour s’exécuter
 (terminologie du livre: tranche de temps)

S’il s’exécute pour un quantum entier sans autres
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]
28 Ch. 5
 Performance de tourniquet

S ’il y a n processus dans la file prêt et le
quantum est q, alors chaque processus
reçoit 1/n du temps UCT dans unités de
durée max. q

Si q grand  FCFS

Si q petit... nous verrons

29 Ch. 5
 Exemple: Tourniquet Quantum = 20
Processus Cycle
P1 53
P2 17
P3 68
P4 24

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3


Normalement,
0 20 37 57 77 97 117 121 134 154 162
 temps de rotation (turnaround) plus élevé que SJF
 mais temps attente moyen meilleur

30 Ch. 5
 Un petit quantum augmente les commutations
de contexte (temps de SE)

31 Ch. 5
 Exemple pour voir l’importance d’un bon choix
de quantum (à développer comme exercice)

Trois cycles:
 A, B, C, toutes de 10

Essayer avec:
 q=1
 q=10

Dans ce deuxième cas, tourniquet
fonctionne comme FCFS et le temps de
rotation moyen est meilleur

32 Ch. 5
 Exercices d’ordonnancement
Trois processus P1, P2, P3 arrivent au temps 0 dans la file prêt

Cycles UCT de P1: 14,12,17

Cycles UCT de P2: 2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3

Cycles UCT de P3: 6,3,8,2,1,3,4,1,2,9,7

Opération E/S de 6 unités de temps entre chaque cycle UCT
(en parallèle)

Algorithmes d’ordonnancement
 FCFS
 Tourniquet (quantum de 5)
 Non-preemptive SJF ou Preemptive SJF
 Tourniquet avec priorité: P2=P3>P1

33 Ch. 5
 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.
 tourniquet pour premier plan
 FCFS pour arrière-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 premier plan
 20% pour arrière-plan

34 Ch. 5
 Ordonnancement avec files multiples

35 Ch. 5
 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

36 Ch. 5
 Files multiples et à retour (trois files)

PRIO = 0

PRIO = 1

PRIO = 2

37 Ch. 5
 Exemple de files multiples à retour

Trois files:
 Q0: tourniquet, quantum 8 msecs
 Q1: tourniquet, quantum 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 à demander des quantums
plus petits, il pourrait retourner à Q0 ou Q1

38 Ch. 5
 En pratique...

Les méthodes que nous avons vu sont
toutes utilisées en pratique (sauf plus
court servi pur qui est impossible)

Les SE sophistiqués fournissent au gérant
du système une librairie de méthodes, qu’il
peut choisir et combiner au besoin après
avoir observé le comportement du système

Pour chaque méthode, plusieurs params
sont disponibles: p.ex. durée du quantum,
coefficients, etc.

39 Ch. 5
 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 aux 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 aussi 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

40 Ch. 5
 Résumé des algorithmes d’ordonnancement

Premier arrivé, premier servi (FCFS)
 simple, petit temps de système (overhead), qualités faibles

Plus court d’abords (SJF)
 Doit savoir les temps de traitements (pas pratique)
 Doit prédire en utilisant la moyenne exponentielle du passé

Ordonnancement avec priorité
 Un classe d’algorithmes

Tourniquet
 FCFS avec préemption

Files à plusieurs niveaux (Multilevel Queues)
 Possible d’utilisé différents algorithmes avec chaque file

Files multiples à retour (Multilevel Feedback Queues)
 Combine plusieurs techniques

41 Ch. 5
 Survol des sujets avancés de l’ordonnancement

L’ordonnancement avec plusieurs UCTs
identiques

Modèle d’évaluation

42 Ch. 5
 Ordonnancement avec plusieurs UCTs
identiques: homogénéité

Une seule liste prêt pour toutes les UCTs
(division travail = load sharing)
 une liste séparée pour chaque UCT ne
permettrait pas ça
 méthodes symétriques: chaque UCT peut exécuter
l ’ordonnancement et la répartition
 méthodes asymétriques: ces fonctions sont
réservées à une seule UCT

43 Ch. 5
 Solaris 2:

Priorités et préemption

Files multiniveau à retour avec changement de
priorité

Différentes quantums pour les différentes priorités
(plus grands pour priorités plus élevées)

Priorité élevée pour les procs interactifs, plus
petite pour les procs tributaires de l’UCT

La plus haute priorité aux procs temps réel

Tourniquet pour les fils de priorités égales

44 Ch. 5
 Méthode d’évaluation et comparaison
d’algorithmes (section plutôt à lire)


Modélisation déterministe

Modèles de files d ’attente (queuing theory)

Simulation

45 Ch. 5
 Modélisation déterministe

Essentiellement, ce que nous avons déjà
fait en étudiant le comportement de
plusieurs algorithmes sur plusieurs
exemples

46 Ch. 5
 Utilisation de la théorie des files (queuing th.)


Méthode analytique basée sur la théorie
des probabilités

Modèle simplifié: notamment, les temps du
SE sont ignorés

Cependant, elle rend possibles des
estimées

47 Ch. 5
 Théorie des files: la formule de Little

Un résultat important:

n = W
 n: longueur moyenne de la file d ’attente
  : débit d ’arrivée de travaux dans file
 W: temps d ’attente moyen dans la file

P. ex.
  si les travaux arrivent 3 par sec.
 W et il restent dans la file 2 secs
 n la longueur moyenne de la file sera???

Exercice: Résoudre aussi pour etW

Observer que afin que n soit stable,   W doit être stable
 Un débit d’arrivée plus rapide doit impliquer un temps de
service mineur, et vice-versa
 Si n doit rester 6 et  monte à 4, quel doit être W?

48 Ch. 5
 Simulation

Construire un modèle (simplifié...) de la
séquence d’événements dans le SE

Attribuer une durée de temps à chaque
événement

Supposer une certaine séquence
d’événements extérieurs (p.ex. arrivée de
travaux, etc.)

Exécuter le modèle pour cette séquence
afin d’obtenir des stats

49 Ch. 5
 Points importants dans ce chapitre

Files d ’attente pour UCT

Critères d ’ordonnancement

Algorithmes d ’ordonnancement
 FCFS: simple, non optimal
 SJF: optimal, implantation difficile
 moyennage exponentiel
 Priorités
 Tourniquet: sélection du quantum

Évaluation des méthodes, théorie des files,
 formule de Little
50 Ch. 5