SYSTÈMES D’EXPLOITATION 2

Module 4

Mondher Bouden
Maître assistant

Semestre 2
2023-2024
Ordonnancement

2
 Ordonnancement
• Processus en concurrence pour l’exécution (état
prêt)

• Décider quel processus exécute sur CPU

• Algorithme/paramètres employés va affecter :
– le temps de réponse
– l’expérience ressentie par l’utilisateur
– la capacité de traitement (débit)
3
 Changement de processus
• Coûte généralement cher :
– basculer en mode noyau (0)
– sauvegarder le contexte du processus
– changer l’espace d’adressage du MMU (Memory
Management Unit)
– pollution des caches mémoires (L1, L2, L3)

• Changements ne doivent pas être trop fréquents

4
 Quand S.E. doit ordonnancer?
• Créer un processus
• Processus se termine
• Processus bloque sur E/S, mutex, condition, …
• Processus libère mutex, signale sémaphore/condition
• Processus fait un yield
• Interruption :
– sur E/S qui était bloquée (e.g. lecture bloc disque)
• après l’interruption on repart :
– le processus interrompu ?
– le processus bloqué ?
– un processus de plus grande priorité?
– un processus qui a été le moins exécuté dernièrement?
5
 Quand S.E. doit ordonnancer? (2)
• Si S.E. préemptif, quand quantum expire
– (~5-20 ms sur votre machine)
– être équitable entre processus
quantum
– ordinateur fonctionne même si
un processus fait une
boucle sans fin

6
 Pas d’ordonnanceur parfait
• Dépend du type d’application
• Traitement par lot :
– non préemptif ou préemptif avec long quantum
– Windows server ~200 ms
– bonne capacité de traitement (débit)
• Interactifs :
– préemptif + rapide. Windows : quantum 5-20 ms
– compromis entre temps réponse et débit
• Temps réel
– QNX ajustable jusqu’à 40 ms
– temps de réponse et prédictibilité
7
 Considérations
• Maximiser l’utilisation
– Chercher à maximiser l’utilisation de toutes les
composantes du système (disque, CPU, etc)
– si beaucoup Entrées/Sorties, redonner le contrôle
vite à ce processus (pour lancer la prochaine E/S)
requête E/S
processus A
bloqué

• Équitable
– chaque processus ait accès au même temps de
calcul, en moyenne
8
 Algorithmes d’ordonnancement
• Il en existe plusieurs :
– Premier arrivé, premier servi
• FCFS: First-Come First-Served
– Job le plus court en premier
• SJB : Shortest Job First
– Temps restant le plus court se concentrer
– Tourniquet (Round Robin) sur eux
– Priorité
– O(1)
– CFS : Completely Fair Scheduler (Linux)
– Windows
– BFS : Brain Fuck Scheduler (Linux)
– et plein d’autres… 9
 Premier arrivé, premier servi
• L’ordre d’exécution dépend de l’ordre d’arrivée
• Une seule file d’attente
• Pas de préemption
• Si un processus bloque, on exécute le prochain
• Quand le processus débloque, place à la fin de la
file

10
 PREMIER ARRIVÉ, PREMIER SERVI
FCFS - First-Come, First-Served

processus temps d'arrivée temps CPU

P1 0.0000 24
P2 0.0001 3
P3 0.0002 3

P3 P2 P1 CPU
 processus temps d'arrivée temps CPU
P1 0.0000 24
P2 0.0001 3
P3 0.0002 3

file
temps = 0 P3 P2 P1 CPU

P1
0 24 27 30
 processus temps d'arrivée temps CPU
P1 0.0000 24
P2 0.0001 3
P3 0.0002 3

file
temps = 24 P3 P2 CPU

P1 P2
0 24 27 30
 processus temps d'arrivée temps CPU
P1 0.0000 24
P2 0.0001 3
P3 0.0002 3

file
temps = 27 P3 CPU

P1 P2 P3
0 24 27 30
 processus temps d'arrivée temps CPU
P1 0.0000 24
P2 0.0001 3
P3 0.0002 3

file
temps = 30 CPU

P1 P2 P3
0 24 27 30
 P1 P2 P3
0 24 27 30
(quand il termine) (quand il commence)
temps de temps
processus
traitement d'attente
P1 24 0
P2 27 24
P3 30 27
total 81 51
moyenne(÷3) 27 17
 change l’ordre d’arrivé : P2, P3 et P1

P2 P3 P1
0 3 6 30
(quand il termine) (quand il commence)
temps de temps CPU temps
processus
traitement (d'exécution) d'attente
P1 30 - 24 =6
P2 3 -3 =0
P3 6 -3 =3
total 39 - 30 =9
moyenne(÷3) 13 - 10 =3
(comparé à 27) (comparé à 17)

FCFS n'est pas optimum pour temps moyen d’exécution

 Avantages / défauts
• Avantages
– facile à comprendre / implémenter
– efficace, car peu de changements de contexte

• Défaut
– pas optimal pour le temps moyen d’exécution
– punir les processus qui font beaucoup E/S
• si replacé à la fin de la file
– très mauvais temps de réponse
• traitement de texte ?
18
Job/processus le plus court en premier
• Suppose qu’on connait le temps d’exécution à
l’avance
(pas le cas en général)
• Exécuter le job le plus court en premier
• Sans préemption
– quand on lance un job, on ne peut pas le remplacer
par un autre job

19
PROCESSUS LE PLUS COURT EN PREMIER
SJF - Shortest Job First

processus temps d'arrivée temps CPU

P1 0 6
P2 0 8
P3 0 7
P4 0 3
plus court
P4 P3 P2 P1 CPU doit connaître
le temps
d’exécution
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 0 3

plus court
temps = 0 P4 P3 P2 P1 CPU

P4
0 3 9 16 24
temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 0 3

plus court
temps = 0 P4 P3 P2 P1 CPU Ordonnanceur
examine pour
trouver le plus
P4 court
0 3 9 16 24
temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 0 3

plus court
temps = 0 P4 P3 P2 P1 CPU Ordonnanceur
examine pour
trouver le plus
P4 court
0 3 9 16 24
temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 0 3

plus court
temps = 3 P3 P2 P1 CPU Ordonnanceur
examine pour
trouver le plus
court
P4 P1
0 3 9 16 24
temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 0 3

plus court
temps = 9 P3 P2 CPU Ordonnanceur
examine pour
trouver le plus
P4 P1 P3 court

0 3 9 16 24
temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 0 3

plus court
temps = 16 P2 CPU Ordonnanceur
examine pour
trouver le plus
court
P4 P1 P3 P2
0 3 9 16 24 temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 0 3

plus court
temps = 16 P2 CPU Ordonnanceur
examine pour
trouver le plus
court
P4 P1 P3 P2
0 3 9 16 24 temps

… exécution en ordre croissant de temps CPU…

 P4 P1 P3 P2
0 3 9 16 24
(quand il termine) (quand il commence)
temps de temps
processus
traitement d'attente
P1 9 =3
P2 24 = 16
P3 16 =9
P4 3 =0
total 52 = 28
moyenne(÷4) 13 7
OPTIMAL si les tâches arrivent en même temps
Temps d'attente très long pour les processus longs
Si on modifie le temps d'arrivée de P4 …

processus temps d'arrivée temps CPU

P1 0 6
P2 0 8
P3 0 7
P4 3 3
plus court
P3 P2 P1 CPU
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 3 3

plus court Ordonnanceur

temps = 0 P3 P2 P1 CPU examine pour
trouver le plus
court
P1
0 3 temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 3

plus court
temps = 3 P3 P2 P1 CPU
commence à exécuter P1…
P1
0 3 temps

P4 arrive!
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 3 3

plus court
temps = 3 P3 P2 P1 CPU

P1
0 3 temps

P4 arrive!
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 3 3

temps = 3
P4 P3 P2 P1 CPU

?
P1
0 3 temps
La sélection du prochain processus se fait seulement à la
fin de l'exécution d'un processus : pas de préemption
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 3 3

temps = 3 Ordonnanceur
P4 P3 P2 P1 CPU
examine pour
trouver le plus
P1 court

0 6 temps

P1 continue donc de s’exécuter jusqu’à la fin

 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 3 3

plus court
temps = 6 P4 P3 P2 CPU Ordonnanceur
examine pour
trouver le plus
P1 P4 court

0 6 9 temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 3 3

plus court
temps = 9 P3 P2 CPU Ordonnanceur
examine pour
trouver le plus
P1 P4 P3 court

0 6 9 16
temps
 processus temps d'arrivée temps CPU
P1 0 6
P2 0 8
P3 0 7
P4 3 3

plus court
temps = 16 P2 CPU Ordonnanceur
examine pour
trouver le plus
P1 P4 P3 P2 court

0 6 9 16 24 temps
PROCESSUS LE PLUS COURT EN PREMIER
SJF - Shortest Job First
est l'algorithme optimum
 les temps d'exécution sont connus
 sans préemption

P1 P2

temps d'attente

P2 P1

temps d'attente
réduction
 Temps restant le plus court
• Version préemptive du job le plus court
• Va exécuter un nouveau processus si plus court
que le temps restant du processus actuel
• Risques de famine pour les tâches très longues

39
 TEMPS RESTANT LE PLUS COURT (EN PREMIER)
SRT - Shortest Remaining Time ( First )
avec préemption
processus temps d'arrivée temps CPU
P1 0 8
P2 1 4
P3 2 9
P4 3 5
plus court
P4 P3 P2 P1 CPU
 processus temps d'arrivée temps CPU temps restant
P1 0 8 8
P2 1 4
P3 2 9
P4 3 5

plus court
temps = 0 P1 CPU

P1
01 5 10 20 26
 processus temps d'arrivée temps CPU temps restant
P1 0 8 -1 = 7
P2 1 4 4
P3 2 9
P4 3 5

plus court
temps = 1 P2 P1 CPU

P1 P2
01 2 5 10 20 26
 processus temps d'arrivée temps CPU temps restant
P1 0 8 -1 = 7
P2 1 4 -1 = 3
P3 2 9 9
P4 3 5

plus court
temps = 2 P3 P2 P1 CPU

P1 P2
01 3 5 10 20 26
 processus temps d'arrivée temps CPU temps restant
P1 0 8 -1 = 7
P2 1 4 -2 = 2
P3 2 9 9
P4 3 5 5

plus court
temps = 3 P4 P3 P2 P1 CPU

P1 P2
01 3 5 10 20 26
 processus temps d'arrivée temps CPU temps restant
P1 0 8 -1 = 7
P2 1 4 -4 = 0
P3 2 9 9
P4 3 5 5

plus court
temps = 5 P4 P3 P1 CPU

P1 P2 P4
01 3 5 10 20 26

À partir du temps 5, il n'y a plus de préemption, car tous les

processus sont arrivés.
 processus temps d'arrivée temps CPU temps restant
P1 0 8 -1 = 7
P2 1 4 -4 = 0
P3 2 9 9
P4 3 5 -5 = 0

plus court
temps = 10 P3 P1 CPU

P1 P2 P4 P1
01 5 10 17 26
 processus temps d'arrivée temps CPU temps restant
P1 0 8 -8 = 0
P2 1 4 -4 = 0
P3 2 9 9
P4 3 5 -5 = 0

plus court
temps = 17
P3 CPU

P1 P2 P4 P1 P3
01 5 10 17 26
 Tourniquet (round robin)
• Très utilisé car :
– simple
– relativement équitable
– sert de base pour d’autres algorithmes
• Préemptif :
– processus reçoit un quanta de temps (e.g. 20 ms)
– s’exécute pendant le quanta, puis interruption sur horloge
• préemption
– s’il pourrait continuer à s’exécuter, l’ordonnanceur le place à la
fin de la file
– ordonnanceur prend prochain processus dans la file

48
 Taille du quanta?

• bon temps de réponse

• meilleure illusion de • bon débit (efficace)
simultanéité

petit quanta grand

1 ms 20-50 ms 500 ms
•perte temps •mauvais temps de
changement processus réponse

49
 ROUND ROBIN OU TOURNIQUET
pour système à temps partagé ou interactif

processus temps d'arrivée temps CPU

P1 0 20
P2 0 3
P3 0 7
quantum = 4 ut
P3 P2 P1 CPU

retourne à la fin de la
file après un quantum
 processus temps d'arrivée temps CPU temps restant
P1 0 20 20
P2 0 3 3
P3 0 7 7
quantum = 4 ut
P3 P2 P1 CPU

P1
0 4 10 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 16
P2 0 3 3
P3 0 7 7
quantum = 4 ut
P3 P2 P1 CPU

P1
0 4 10 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 16
P2 0 3 3
P3 0 7 7
quantum = 4 ut
P1 P3 P2 CPU

P1
0 4 10 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 16
P2 0 3 3
P3 0 7 7
quantum = 4 ut
P1 P3 P2 CPU

P1 P2
0 4 7 10 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 16
P2 0 3 0
P3 0 7 7
quantum = 4 ut
P1 P3 X CPU

fin
P1 P2
0 4 7 10 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 16
P2 0 3 0
P3 0 7 7
quantum = 4 ut
P1 P3 CPU

P1 P2 P3
0 4 7 11 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 16
P2 0 3 0
P3 0 7 3
quantum = 4 ut
P3 P1 CPU

P1 P2 P3
0 4 7 11 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 16
P2 0 3 0
P3 0 7 3
quantum = 4 ut
P3 P1 CPU

P1 P2 P3 P1
0 4 7 11 15 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 12
P2 0 3 0
P3 0 7 3
quantum = 4 ut
P1 P3 CPU

P1 P2 P3 P1
0 4 7 11 15 20 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 12
P2 0 3 0
P3 0 7 3
quantum = 4 ut
P1 P3 CPU

P1 P2 P3 P1 P3
0 4 7 11 15 18 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 12
P2 0 3 0
P3 0 7 0
quantum = 4 ut
P1 X CPU

fin
P1 P2 P3 P1 P3
0 4 7 11 15 18 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 8
P2 0 3 0
P3 0 7 0
quantum = 4 ut
P1 CPU

P1 P2 P3 P1 P3 P1
0 4 7 11 15 18 22 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 4
P2 0 3 0
P3 0 7 0
quantum = 4 ut
P1 CPU

P1 P2 P3 P1 P3 P1 P1
0 4 7 11 15 18 22 26 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 0
P2 0 3 0
P3 0 7 0
quantum = 4 ut
P1 CPU

P1 P2 P3 P1 P3 P1 P1 P1
0 4 7 11 15 18 22 26 30
 processus temps d'arrivée temps CPU temps restant
P1 0 20 0
P2 0 3 0
P3 0 7 0
quantum = 4 ut
P1 CPU total : 30

P1 P2 P3 P1 P3 P1 P1 P1
0 4 7 11 15 18 22 26 30
 P1 P2 P3 P1 P3 P1 P1 P1
0 4 7 11 15 18 22 26 30
(quand il termine)
temps de temps CPU temps
processus
traitement (d'exécution) d'attente
P1 30 - 20 = 10
P2 7 -3 =4
P3 18 -7 = 11
total 55 - 30 = 25
moyenne(÷3) 18.33 = 8.33
 Exemple question tourniquet
• 5 Jobs qui arrivent en même temps. Trouver quand chaque job se
termine (approx.) avec tourniquet, quantum ~10 ms. Négliger le
temps pour changement de contexte.
Dernier job doit terminer à 10+6+2+4+8 = 30
Job Temps A
traitement B
(min) C
A 10 D
E
B 6
# job qui tournent

5
C 2 4
D 4 3
E 8 2

67
10 20 30
 Priorités
• Concept clé des S.E.
• Pour pouvoir choisir quel thread/processus est
plus « important »
– vous « suggérez » au S.E.
• Affecter
– le temps de réponse
– le % de CPU alloué à chaque processus/thread

68
 Pourquoi priorités
• Toutes les tâches ne sont pas égales
– défragmenter disque dur vs. jeu vidéo en ligne
– vérifier nouveau courrier vs. traitement de texte
• Ajuster le comportement du timing
– bouger un curseur sur l’écran
– déplacer fenêtre
– son, vidéo, animations
• Encore plus critique pour temps réel
– contraintes de temps sont importantes
69
 Réaliser avec plusieurs files
• Une file par priorité

• Faire un tourniquet sur chaque file

70
Ordonnanceur Linux O(1)

71
 Ordonnanceur Linux
• Basé sur les threads et non pas processus

Version Noyau Linux Ordonnanceur

Linux pre 2.5 Multilevel Feedback Queue
Linux 2.5-2.6.23 O(1) scheduler
Linux post 2.6.23 Completely Fair Scheduler

72
 Threads
• Avant : 1 processus = 1 fil d’exécution
• Parfois besoin de plusieurs fils d’exécutions :
– plusieurs activités en même temps
– activités avec grands temps d’attentes
• disque, clavier, port sériel, etc.
• Va vouloir ajouter d’autres fils d’exécutions dans
un processus : threads
• Au démarrage, un processus n’a qu’un thread

73
 Threads
• Un peu comme si vous aviez plusieurs main()
dans votre programme en C/C++

• Excepté vous décidez quand vous

démarrez/arrêtez les autres threads

• Partage de l’espace d’adressage

– partager variables globales
– « joue dans le même carré de sable »

74
 Utilisation des threads
• Chaque thread va avoir son contexte de processeur
– Program Counter (EIP) par thread, copie des registres CPU
– « mini-processus » → light weight process (LWP)
– tourne indépendamment des autres threads
• Thread partage l’espace d’adressage + ressources du
processus : pas de protection mémoire entre threads
1 2 3

75
 États d’un thread
• Comme un processus, un thread peut être
– bloqué
– en cours d’exécution
– en attente d’exécution

76
 Élements des processus et threads
Éléments par processus Éléments par thread
Espace d’adressage (mém.) Compteur ordinal (EIP)
Variables Globales Registres (EAX, EBX, …)
Fichiers ouverts Pile
Processus enfant (si applicable) État
Alertes en attentes
Signaux et gestionnaires de
signaux

77
 Utilisation des threads
• Beaucoup plus rapide à créer qu’un processus,
car moins de ressources associées (tableau de
données beaucoup plus petit)
• Utile quand on a une
partie CPU intensive,
et une partie bloquant
sur E/S (disque)
• Serveur web
(pages html sur disque)
78
 Utilisation des threads
• Traitement de texte :
– un thread qui bloque pour lire le clavier/souris
– un thread pour la mise en page et l’affichage
– un thread pour écrire sur le disque

79
 Utilisation des threads
• Multi-cœurs : distribuer une tâche en parallèle
transcodage d’un fichier mp3

80
 Processus vs threads

Processus Threads
Indépendants Sous-ensemble d’un processus
Beaucoup d’information d’état Peu d’information d’état
Espaces d’adressage séparés Espace d’adressage partagé
Intercommunication via S.E. Intercommunication via mémoire

81
 Ordonnanceur Linux
• Beaucoup d’évolution au fil du temps
– par exemple, avec multi-processeurs
Kernel 2.4 Kernel 2.6

1 file
d’exécution n files ...
d’exécution
goulot
d’étranglement

CPU1 CPU2 CPU3 CPU1 CPU2 ... CPU n

82
 O(1)
File d’exécution
• 1 File d’exécution par CPU
• 1 file expirée, 1 file active
• 140 niveaux de priorités voir un peu
• Petit numéro = grande priorité plus loin…
• Quand une tâche expire, file expirée file active
elle passe de active → CPU-X CPU-X

expirée
Priorité
• Quand toutes les tâches temps réel
sont expirées, échanger
les files : epoch
tâches
(inverse les pointeurs des files) utilisateur
83
 O(1)
Ordonnanceurs Linux 2.6
• Trois policy :
– SCHED_FIFO
• temps réel, pas de préemption→ pas de quantum
– SCHED_RR
• temps réel, préemption → timeslice (quantum différent en
fonction de la priorité)
– SCHED_NORMAL
• pour les thread normaux
• donc, vos processus et threads

84
 O(1)
SCHED_FIFO
• FIFO : First In First Out
– Premier arrivé, premier servi
– Sans préemption, sauf si nouveau plus haute priorité
arrive
– Processus doit avoir les droits superuser
File
priorité
+ élevée

- élevée
85
 O(1)
SCHED_FIFO
• Préemption si nouveau processus + haute priorité

priorité File
+ élevée

- élevée

86
 O(1)
SCHED_FIFO
• Préemption si nouveau processus + haute priorité

priorité File File

+ élevée

- élevée

87
 O(1)
SCHED_FIFO
• Préemption si nouveau processus + haute priorité

priorité File File File

+ élevée

- élevée

88
 O(1)
SCHED_FIFO
• Préemption si nouveau processus + haute priorité

priorité File File File

+ élevée

- élevée

89
 O(1)
SCHED_RR
• Peuvent être préemptée par SCHED_FIFO
• Possèdent un quantum
• Tourniquet par niveau de priorité
• Processus doit avoir les droits superuser

priorité File
+ élevée

- élevée

Exécution : 90
 O(1)
SCHED_FIFO et SCHED_RR:temps réel

• SCHED_FIFO et SCHED_RR vont tourner tant qu’ils ont

besoin de temps (risque de boucle infinie)
• Lorsqu’ils ont tous terminé, l’ordonnanceur O(1)
commence à exécuter les threads dans SCHED_NORMAL

91
 O(1)
SCHED_NORMAL : priorité statique
• Vous attribuez à chaque processus un niveau de
priorité statique Pstatique
• Varie entre -20 et 19 (40 niveaux)
(encore ici, petit veut dire haute priorité)
élevée basse
• Par défaut, Pstatique =0
• Changer Pstatique avec nice ou setpriority()
– valeur positive → réduire priorité
• pour des longues simulations à tourner
– valeur négative → augmenter priorité
• besoin d’être superuser

92
 O(1)
SCHED_NORMAL : priorité dynamique
• Pdynamique est ajustée automatiquement par le S.E.
• Basée sur des heuristiques (algorithmes approximatifs)
• « Récompenser » processus E/S [-1 … -5]
(valeur négative
(I/O bound) hausse la priorité)

bloqué

(CPU bound)
• « Punir » processus gourmand CPU [+1 +5]

93
 O(1)
SCHED_NORMAL : priorité dynamique
-5 <= Pdynamique <= 5
• Calculé à partir du temps qu’un thread passe
bloqué
– plus il bloque longtemps, plus Pdynamique augmente
• Ne s’applique pas aux temps réel
– SCHED_FIFO
– SCHED_RR

94
 O(1)
SCHED_NORMAL : Niveaux de priorités
• Psched = 120 + Pstatique + Pdynamique
[-20 … 19] [-5 +5]
• Doit rester dans la plage 100 à 139
SCHED_FIFO
SCHED_RR SCHED_NORMAL

Priorité Priorité
+ élevée + faible

95
 O(1)
SCHED_NORMAL : timeslice
Les processus hautes priorités statiques vont recevoir
plus de temps de calcul : timeslice
Priorité NICE Timeslice
statique
Haute priorité 100 -20 800 ms
110 -10 600 ms
120 0 100 ms
130 +10 50 ms
Basse priorité 139 +19 5 ms

(besoin superuser)
Timeslice

96
 O(1)
SCHED_NORMAL : algorithme
• En commençant par priorité 100
• Pour chaque niveau P :
– on exécute chaque processus pendant timeslice
– si le processus ne termine pas, préempte et transfert
dans la file expirée, et exécute le suivant dans P
– si P est vide, on fait P = P+1 (descend)
– si P est à 140, la file active est vide :
• interverti la file vide avec la file expirée
• P = 100
• et l’on recommence…
97
 O(1)
SCHED_NORMAL : Exécution timeslice
• Exemple
timeslice : 100 → 800 ms
120 → 100 ms
139 → 5 ms

140 ms 43 ms
niveau de
priorité
143 ms

100 ms

• S’il y a surplus, la tâche « expire » et on la place dans la file

expirée.
• Si un niveau est vide ou tout expiré, on descend au niveau suivant
 O(1)
Thread bloquée
• Quand un thread bloque, il passe d’une file
d’exécution à une file d’attente
– État : en cours d’exécution → bloqué
• Quand le thread débloque, il est placé dans une
des files d’exécutions
– État : bloqué → (prêt, en cours d’exécution)
– dépendre de la charge des CPU : équilibrage
...
n files
d’exécution

CPU1 CPU2 ... CPU n 99

 O(1)
sched_yield()
• Pour indiquer au S.E. qu’on veut céder son
tour… (coopératif)
• Facile! l’ordonnanceur déplace le thread
appelant de la file active à file expirée
• Tous les autres threads seront ré-exécutés avant
que l’appelant du sched_yield() ne reçoive le
processeur de nouveau

100