ENSI 2012/2013
S.E & Prog Conc
M.Nasri
ORDONNANCEMENT DES PROCESSUS
1
Plan
o Introduction o Objectifs de l'ordonnanceur. o Ordonnanceurs non préemptifs
o SJF o FCFS o Priorité. Priorité.
o Ordonnanceurs préemptifs
o Round Robin. o Tourniquet avec priorités. o SRTF
o Hiérarchie d’Ordonnancement. o Thread Scheduling. o Exemples d’ordonnancement
2
Introduction
(cid:1) plusieurs processus peuvent être présents en mémoire centrale en attente
d'exécution.
(cid:1) Si plusieurs processus sont prêts,
le système d'exploitation doit gérer
l'allocation du processeur aux différents processus à exécuter.
(cid:1) C'est l'ordonnanceur (scheduler) qui s'acquitte de cette tâche.
(cid:1) Allocation du processeur se fait par l’allocateur (dispatcher).
(cid:1) Un ordonnanceur fait face à deux problèmes principaux :
(cid:1) Le choix du processus à exécuter.
(cid:1)
Le temps d'allocation du processeur au processus choisi.
(cid:1) 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..
(cid:1) 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
(cid:1) S'assurer que chaque processus en attente d'exécution reçoive sa part
de temps processeur.
(cid:1) Minimiser le temps de réponse.
(cid:1) Utiliser le processeur à 100%.
(cid:1) Utilisation équilibrée des ressources. (cid:1) Utilisation équilibrée des ressources.
(cid:1) Prendre en compte des priorités.
(cid:1) Être prédictibles.
(cid:1) => 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
optimise tous les critères de façon simultanée.
4
Ordonnanceurs non préemptifs
o ordonnancement non préemtif ou sans réquisition :
(cid:1) FCFS : First-Come First- Served ou Premier Arrivé est le
Premier Servi PAPS
(cid:1) SJF : Short Job First SJF , le plus court d'abord.
(cid:1) Priorité : À chaque processus une priorité lui est associée.
5
Ordonnanceurs non préemptifs : SJF
(cid:1) Algorithme SJF -- Shortest Job First (STCF -- Shortest Time to Completion First) : Algorithme du ’’Plus Court d’Abord ’’ : (cid:1) Suppose la connaissance des temps d'exécution. (cid:1) Exécuter le processus le plus court (cid:1) Minimise le
temps moyen d'exécution.
6
Ordonnanceurs non préemptifs : FCFS
(cid:1) Algorithme FCFS (First Come First Served) -- Premier Arrivé Premier Servi
(cid:1) Un processus s'exécute jusqu'à sa terminaison, sans retrait forcé de la ressource. (cid:1) Modèle adapté au partage du processeur par des processus de même priorité (aucun
privilège entre les processus).
(cid:1) Facile à implanter, mais peu efficace (le choix n’est pas lié à l’utilisation de l’UC).
(cid:1) Exemple
P r o c e s s u s
D u r é e e s t i m é e D a t e d ’ a r r i v é e
P 1
P 2 P 2 P 3 P 4
2 4
8 8 1 2 3
0
1 1 2 3
Publicité
(cid:1) Schématiser l’exécution des processus selon leur ordre d'arrivée. Pour cela, on
utilise le DIAGRAMME DE GANTT
P1P1
P2P2
P3P3
P4P4
00
2424
3232
4444
4747
Temps de vie des processus Temps de vie des processus
(cid:1) Temps de traitement moyen = [(24 - 0) + (32 - 1) + (44 -2) + (47 -3)]/4 = 35,25
7
Ordonnanceurs non préemptifs : Priorité
(cid:1) A chaque processus est assignée (automatiquement par le SE /externe)
une priorité
(cid:1) Assignation statique -- priorités fixes (cid:1) facile à implanter
(cid:1) Assignation dynamique : la priorité initiale assignée à un processus
peut être ajustée à d ’autres valeurs (cid:1) difficile à implanter
(cid:1) Pb. de famine : un processus de faible priorité peut ne jamais
s'exécuter s'exécuter
si des processus plus prioritaires si des processus plus prioritaires
se présentent se présentent
constamment
(cid:2) Recalculer périodiquement le numéro de priorité des processus (plusieurs FA) (cid:1) la priorité d’un processus décroît (croit) au cours
du temps pour ne pas bloquer les autres FA
(cid:1) Principe : On lance le processus ayant la plus grande priorité.
8
Round Robin Ordonnanceurs préemptifs : Round Robin
(cid:1) Algorithme tourniquet -- RR : l’un des algorithmes les plus utilises et des plus fiables
(cid:1) Ordonnancement selon l’ordre FCFS (cid:1) Equitable
(cid:1) Chaque processus possède un quantum de temps pendant lequel il s’exécute
(cid:1) Lorsqu’un processus épuise son quantum de temps : au suivant !
(cid:1) S’il n’a pas fini : le processus passe en queue du tourniquet et au suivant !
(cid:1) Exemple : Le quantum de temps, Q, est égale à 2 unités; quel est le temps de traitement moyen?
(cid:1) Sachant que les processus P1.. P8 sont arrivés à respectgivement à l’instant 0,..7,
P2 (4 unités)
P3 (2 unités)
Exécution Exécution CPUCPU
P1 (3 unités)
P8 (2 unités)
Q
Q
Q
Q
Q
Q
Q
Q
P4 (3 unités)
P5 (3 unités)
P7 (4 unités)
P6 (5 unités)
9
Round Robin Ordonnanceurs préemptifs : Round Robin
P1P1
P2P2 P3P3 P4P4 P5P5 P6P6 P7P7 P8P8 P1P1 P2P2 P4P4 P5P5 P6P6
P7P7 P6P6
00
22
44
66
88
1010 1212
1414 1616 1717 1919 2020 2121
2323
Publicité
2525 2626
Temps de vie Temps de vie
Diagramme de Gantt (Q=2 unités)
(cid:1) Temps de traitement moyen =
[(17-0) + (19-1) + (6-2) + (20-3) + (21-4) + (26-5) + (25-6) + (16-7)] /8 = 15,25
(cid:1) Problème = réglage du quantum (petit/grand; fixe/variable; est-il le même pour tous les processus ?)
(cid:1) Les quanta égaux rendent les différents processus égaux => similaire à FIFO ou bien FCFS. (cid:1) Quantum trop petit : provoque trop de commutations de processus
(cid:2) Le changement de contexte devient coûteux (perte de temps CPU)
(cid:1) Quantum trop grand : augmentation du temps de réponse d’une commande (même
simple) (cid:2) RR dégénère vers FCFS seulement les processus avec grand quata seront interrompus.
(cid:1) Il existe d ’autres variantes de RR, telle que RR avec priorités
10
Ordonnanceurs préemptifs : Tourniquet avec priorités
(cid:2) Le système de gestion possède n FA à différents niveaux de priorités
(+ différents quanta).
--
FA FA n-1 (Q (Q n-1))
Réquisition
FAFA1 1 (Q(Q1)) (Q(Q ))
FA FA 0 (Q 0)) (Q
CPUCPU
≤≤ Q Q 1 Q Q 0 0 ... ... ≤≤ Q Q n-1 ... ... ≤≤ Q Q
1
≤≤ Q Q 2
2
≤≤
Terminaison Terminaison
Scheduler
Dispatcher
Arrivée Arrivée
++
Priorité Priorité
(cid:1) A son arrivée, le processus est rangé dans la FA la plus prioritaire FA0 (cid:1) Si un processus dans FAi épuise son quantum de temps Qi (0 ≤≤ii ≤≤n-2), il sera placé dans la FAi+1
(moins prioritaire) (cid:1) Une FAi (0 ≤≤ i ≤≤n-1 ) ne peut être servie que si toutes les FAj (0 ≤≤ j< i) sont vides (cid:1) un processus qui a traversé toutes les FA sans épuiser son temps de traitement reste dans la FA la moins
11
prioritaire.
Ordonnanceurs préemptifs : SRTF
(cid:2) Algorithme SRTF (Shortest Remaining Time First) -- SJF avec réquisition
(cid:1) Choisir le processus dont le temps d'exécution restant est le plus court (cid:1) Il y a réquisition selon le critère de temps d'exécution restant et l'arrivée d’un processus (cid:1) Possibilité de morcellement d’un processus. (cid:1) Nécessité de sauvegarder le temps restant.
(cid:2) Exemple :
Processus Durée estimée Date d’arrivée
P1 P1 P2 P3 P4
8 8 5 5 2
0 0 2 3 4
Diagramme de Gantt
P1P1
P2P2
00
22
P4P4 66
44
P2P2
P3P3
99
1414
P1P1
P1P1 2020
Temps de vie Temps de vie
(cid:1) Temps de traitement moyen = [(20 - 0) + (9 -2) + (14 -3) + (6-4)]/4 = 9,5 (cid:1) Théoriquement, + SRTF offre un minimum de temps d’attente; - difficile de prédire le futur
12
(quel processus va arriver ?)
Hiérarchie d’Ordonnancement
(cid:1) L’ensemble des processus prêts est-il souvent en mémoire centrale?
(cid:1) Un processus élu, qui est sur disque, prend beaucoup plus de temps qu’un
processus en RAM pour être chargé.
(cid:1) Les algorithmes d’ordonnancement complexes permettent de distinguer entre 2
types différents: (cid:1) Ordonnancement à court terme (short term scheduling): considère
Publicité
seulement les processus prêts en mémoire centrale.
(cid:1) Ordonnancement à long terme (long term scheduling): consiste à utiliser un deuxième algorithme d’ordonnancement pour gérer les les utiliser un deuxième algorithme d’ordonnancement pour gérer ‘’swapping ’’ des processus prêts entre le disque et la RAM
’’Swap out’’ Processus ’’Swap out’’ Processus
Arrivée Arrivée
File d’attente des Prêts File d’attente des Prêts
Sortie Sortie
UCUC
E/SE/S
Files d’attente des E/S Files d’attente des E/S
13
Hiérarchie d’Ordonnancement
(cid:1) Ordonnancement multi-niveaux (F.A avec priorités) permet de:
(cid:1) Favoriser les processus courts (cid:1) Favoriser les processus ‘’I/O Bound’’, qui ne demandent pas trop l ’UC (cid:1) Déterminer la nature de chaque processus le plutôt possible et effectuer
l’ordonnancement correspondant.
(cid:1) Files d’attente sans liens : un processus se trouvant dans dans FAi ne peut se
trouver dans FAj (j≠i); il reste dans FAi jusqu’à ce qu’il se termine
-- --
(RR)
FA FA n-1
FAFA1
Réquisition
(FCFS/SJF)
Processus Interactifs
++ Priorité fixe Priorité fixe
FA FA
0
Processus Système
Terminaison Terminaison
CPUCPU
14
Hiérarchie d’Ordonnancement
(cid:2) Files d’attente avec liens : hiérarchiser les FAs
Arrivée niveau n-1 (RR)
Arrivée niveau 1
(FCFS) (FCFS)
Arrivée niveau 0
(FCFS)
FA FA n-1
FAFA1
FA FA
0
Réquisition
Terminaison Terminaison
CPUCPU
(cid:1) Un processus dans FAi ne peut être sélectionné que si toutes les FAj (j<i) sont toutes vides (cid:1) Permettre aux processus de se déplacer d’une FA à une autre (cid:1) Hiérarchie descendante/ascendante/bidirectionnelle (cid:1) Changement dynamique dans le comportement des processus (cid:1) Chaque FA a son propre algorithme d’ordonnancement
(cid:1) Descendante FAn-1 est gérée avec RR. (cid:1) Ascendante F0 est gérée avec FCFS
15
Thread Scheduling
(cid:1) Local Scheduling – How the threads library decides which
user thread to run next within the process
(cid:1) Global Scheduling – How the kernel decides which kernel
thread to run next
16
Exemples d’ordonnancement
(cid:1) Unix: multi-niveaux, plusieurs politiques, qui peuvent changer dans le
temps
(cid:1) Linux – multi-niveaux avec 3 niveaux les plus importants
(cid:1) Realtime FIFO
(cid:1) Realtime round robin
(cid:1) Timesharing
(cid:1) Windows Vista – politique avec priorité à deux dimensions:
(cid:1) Classe des processus prioritaires
(cid:1) Real-time, high, above normal, normal, below normal, idle
(cid:1) Les priorités des threads sont relatives dela la classe des priorités. 17
(cid:1) Time-critical, highest, …, idle