SE
ORDONNANCEMENT DES
PROCESSUS
1
Plan
o Introduction
o Objectifs de l'ordonnanceur.
o Ordonnanceurs non préemptifs
o SJF
o FCFS
o Priorité.
o Ordonnanceurs préemptifs
o Round Robin.
o Tourniquet avec priorités.
o SRTF
2
Introduction
O plusieurs processus peuvent être présents en mémoire centrale en attente
d'exécution.
O Si plusieurs processus sont prêts, le système d'exploitation doit gérer
l'allocation du processeur aux différents processus à exécuter.
O C'est l'ordonnanceur (scheduler) qui s'acquitte de cette tâche.
O Un ordonnanceur fait face à deux problèmes principaux :
• Le choix du processus à exécuter.
• Le temps d'allocation du processeur au processus choisi.
O Un système d'exploitation multitâche est préemptif quand il peut arrêter
(réquisition) n’importe quel processus pour executer un autre..
O Un système d’exploitation multitâche est coopératif quand il n’arrête pas les
applications jusqu’à ce qu’elles se terminent. 3
Objectifs de l'ordonnanceur
O S'assurer que chaque processus en attente d'exécution reçoive sa part
de temps processeur.
O Minimiser le temps de réponse.
O Utiliser le processeur à 100%.
O Utilisation équilibrée des ressources.
O Prendre en compte des priorités.
O Être prédictibles.
O => Ces objectifs sont parfois complémentaires, parfois contradictoires :
augmenter la performance par rapport à l'un d'entre eux peut se faire
en détriment d'un autre. Il est impossible de créer un algorithme qui
4
optimise tous les critères de façon simultanée.
Ordonnanceurs non préemptifs
o ordonnancement non préemtif ou sans réquisition :
● FCFS : First-Come First- Served ou Premier Arrivé est le
Premier Servi PAPS
● SJF : Short Job First SJF , le plus court d'abord.
● Priorité : À chaque processus une priorité lui est associée.
5
Ordonnanceurs non préemptifs : FCFS
✓ Algorithme FCFS (First Come First Served) -- Premier Arrivé Premier Servi
Q Un processus s'exécute jusqu'à saterminaison, sans retrait forcédela ressource.
Q Modèle adapté au partage du processeur par des processus de même priorité (aucun
privilège entre les processus).
Q Facile à implanter, mais peu efficace (le choix n’est pas lié à l’utilisation de l’UC).
Q Exemple
P r o c e ssu s D u r é e e s t im ée D a t e d ’ a r r iv é e
P1 24 0
P2 8 1
P3 12 2
P4 3 3
✓ Schématiser l’exécution des processus selon leur ordre d'arrivée. Pour cela, on
utilise le DIAGRAMME DE GANTT
P1 P2 P3 P4
0 24 32 44 47 Temps de vie des processus
7
✓ Temps de traitement moyen = [(24 - 0) + (32 - 1) + (44 -2) + (47 -3)]/4 = 35,25
Ordonnanceurs non préemptifs : SJF
O Algorithme SJF -- Shortest Jo b First (STCF -- Shortest
Time to Completion First) : Algorithme du ’’Plus Court
d’Abord ’’ :
Q Suppose la connaissance des temps d'exécution.
Q Exécuter le processus le plus court € Minimise le
temps moyen d'exécution.
6
Ordonnanceurs non préemptifs : Priorité
O A chaque processus est assignée (automatiquement par le SE /externe)
une priorité
Q Assignation statique -- priorités fixes
Q Assignation dynamique : la priorité initiale assignée à un processus
peut être ajustée à d ’autres valeurs
Pb. de famine : un processus de faible priorité peut ne jamais
s'exécuter si des processus plus prioritaires se présentent
constamment
8
Priority Scheduling
Exemple :
12
Temps d’attente moyen = 8,2
Ordonnanceurs préemptifs : RoundRobin
O Algorithme tourniquet -- RR : l’un des algorithmes les plus utilises et des plus fiables
Q Ordonnancement selon l’ordre FCFS € Equitable
Q Chaque processus possède un quantum de temps pendant lequel il s’exécute
Q Lorsqu’un processus épuise son quantum de temps : au suivant !
Q S’il n’a pas fini : le processus passe en queue du tourniquet et au suivant !
O Exemple : Le quantum de temps, Q, est égale à 2 unités; quel est le temps de traitement moyen?
O Sachant que les processus P1.. P8 sont arrivés à l’instant 0 suivant l’ordre de leurs indices,
P2 P3
(4 u n i t é s ) (2 u n i t é s )
Exécution P1 Q Q P4
CPU (3 u n i t é s ) Q Q (3 u n i t é s )
Q Q
P8 P5
(2 u n i t é s ) Q Q (3 u n i t é s )
P7 P6
(4 u n i t é s ) (5 u n i t é s )
Ordonnanceurs préemptifs : Round Robin
P1 P2 P3 P4 P5 P6 P7 P8 P1 P2 P4 P5 P6 P7 P6
0 2 4 6 8 10 12 14 16 17 19 20 21 23 25 26
Temps de vie
D i a g r a m m e d e G a n t t (Q=2 u n i t é s )
Problème = réglage du quantum (petit/grand; fixe/variable; est-il le mêmepourtous les processus?)
Q Lesquanta égaux rendent les différents processuségaux=> similaire à FIFOou bienFCFS.
Q Quantum trop petit : provoque trop de commutations de processus
Le changement de contexte devient coûteux (perte de tempsCPU)
Q Quantum trop grand : augmentation du temps de réponse d’une commande (même
simple)
RR dégénère vers FCFS seulement les processus avec grand quata seront interrompus.
✓ Il existe d ’autres variantes de RR, telle que RRavec priorités
10
Exemple
Soient deux processus A et B prêts tels que A est arrivé en
premier suivi de B, 2 unités de temps après. Les temps de UCT
nécessaires pour l’exécution des processus A et B sont
respectivement 15 et 4 unités de temps. Le temps de
commutation est supposé nul. Calculer le temps de séjour de
chaque processus A et B, le temps moyen de séjour, le temps
d’attente, le temps moyen d’attente, et le nombre de
changements de contexte pour :
– Round robin (quantum = 10 unités de temps)
– Round robin (quantum = 3 unités de temps)
Ordonnanceurs préemptifs : SRTF
O Algorithme SRTF (Shortest Remaining Time First) -- SJF avecréquisition
● Choisir le processusdont le temps d'exécution restant est le plus court
● Il y a réquisition selon le critère detemps d'exécution restant et l'arrivée d’unprocessus
● Nécessité desauvegarder le tempsrestant.
O Exemple :
Processus Durée estimée Date d’arrivée
P1 8 0
P2 5 2
P3 5 3
P4 2 4
Diagramme de Gantt
P1 P2 P4 P2 P3 P1 P1
0 2 4 6 9 14 20
Temps de vie
✓ Temps de traitement moyen = [(20 - 0) + (9 -2) + (14 -3) + (6-4)]/4 = 9,5 12
✓ Théoriquement, + SRTF offre un minimum de temps d’attente; - difficile de prédire lefutur
(quel processus va arriver ?)
Exemple récapitulatif
Soit la liste des processus suivants
1- Représenter les graphes d’exécution pour les algorithmes
d’ordonnancements suivant : FIFO, SJF, SRT et tourniquet (pour
Q=2)
2- Calculer les temps de séjours pour chaque processus ainsi que le
temps moyen de séjours
3- Quel est l’algorithme d’ordonnancement optimal.
Priorités
Exemple :
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é
Algorithme avec priorité
On suppose dans cet exemple que la valeur la plus petite correspond à la
priorité la plus élevée.
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
