AU : 2024-2025

Systèmes d’Exploitation

Chapitre 3 : Ordonnancement des Processus

Classe : LIM-1

Mohamed Chiheb BEN CHAABANE

mohamedchiheb.benchaabane@sesame.com.tn
Plan du Chapitre
• Notion d’Ordonnacement
• Problématique de l’Ordonnacement
• Objectifs d’un Ordonnanceur
• Critères d’Ordonnancement
• Types d’Ordonnancement
• Algorithmes d’Ordonnacement
• Performance des algorithmes d’Ordonnancement
Notion d’Ordonnancement
• On appelle ordonnancement la stratégie d'attribution
des ressources aux processus qui en font la demande.
• Différents critères peuvent être pris en compte :
a. Temps moyen d'exécution minimal.
b. Temps de réponse borné pour les systèmes interactif.
c. Taux d'utilisation élevé de l'UC.
d. Respect de la date d'exécution au plus tard, pour le temps
réel, etc...
Problématique de l’Ordonnacement

• Un ordinateur possède forcément plusieurs processus en

concurrence pour l’obtention du temps processeur, cette
situation se produit lorsque 2 ou plusieurs processus sont en état
prêt simultanément.
• Cette condition nécessite le partage des ressources partagées
d’un ordinateur.
• Les ressources partagées sont généralement :
a. Le Microprocesseur (CPU).
b. La mémoire RAM.
c. Les périphériques ..
 États d’un Processus
• Les appels système relatifs aux processus permettent d'effectuer les
états suivants :
• Création d'un processus (fils) par un processus actif (d'où la structure
d'arbre de processus gérés par un SE).
• Destruction d'un processus.
• Mise en attente, réveil d'un processus.
• Suspension et reprise d'un processus, grâce à l'Ordonnanceur de
processus (Scheduler).
• Demande de mémoire supplémentaire ou restitution de mémoire
inutilisée.
• Attendre la fin d'un processus fils.
• Remplacer son propre code par celui d'un programme différent.
• Échanges de messages avec d'autres processus.
• Modifier la priorité d'un processus
 Objectifs d’un Ordonnanceur
• L’Ordonnanceur (planificateur, scheduler) est la partie (un
programme) du système d’exploitation responsable de régler les
états des processus (Prêt, Actif,…etc.) et de gérer les transitions
entre ces états → c’est l’allocateur du microprocesseur aux
différent processus.
• Les objectifs d’un Ordonnanceur sont :
1. Maximiser l’utilisation du processeur.
2. Présenter un temps de réponse acceptable.
3. Respecter l’équité entre les processus selon le critère
d’ordonnancement utilisé.
 Critères d’ordonnancement
• Utilisation de l’UC : Pourcentage de temps pendant lequel l’UC exécute un processus.
L’importance de ce critère varie généralement en fonction du degré de partage du système.
• Utilisation répartie : Pourcentage du temps pendant lequel est utilisé l’ensemble des
ressources (outre l’UC, mémoire, périphérique d’E/S…)
• Débit : Nombre de processus pouvant être exécutés par le système sur une période de
temps donnée.
• Temps de rotation (Temps de Séjour): durée moyenne qu’il faut pour qu’un processus
s’exécute. Le temps de rotation d’un processus comprend tout le temps que celui-ci passe
dans le système. Il est inversement proportionnel au débit.
• Temps d’attente : durée moyenne qu’un processus passe à attendre. Mesurer la
performance par le temps de rotation présente un inconvénient : Le temps de production
du processus accroît le temps de rotation ; Le temps d’attente représente donc une mesure
plus précise de la performance.
• Temps de réponse : Temps moyen qu’il faut au système pour commencer à répondre aux
entrées de l’utilisateur.
• Équité : degré auquel tous les processus reçoivent une chance égale de s’exécuter.
• Priorités : attribue un traitement préférentiel aux processus dont le niveau de priorité est
supérieur.
Types d’ordonnancement

• Il existe 2 types d’ordonnancement :

a. Ordonnancement préemptif : Avec réquisition où
l’Ordonnanceur peut interrompre un processus en cours
d’exécution si un nouveau processus de priorité plus élevée
est inséré dans la file des Prêts.
b. Ordonnancement coopératif : Ordonnancement jusqu’à
achèvement : le processus élu garde le contrôle jusqu’à
épuisement du temps qui lui a été alloué même si des
processus plus prioritaires ont atteint la liste des Prêts.
Algorithmes d’ordonnancement (1) : FIFO

• FIFO (First In First Out) appelé aussi (FCFS : First Come First
Served) : L'ordonnancement est fait dans l'ordre d'arrivée en
gérant une file unique des processus sans priorité ni réquisition.
• Chaque processus s’exécute jusqu’à son terme.
• Le processus élu est celui qui est en tête de liste des Prêts : le
premier arrivé.
Algorithmes d’ordonnancement (1) : FIFO
• Exemple : Soit le Tableau de Processus et son diagramme de
GANTT Processus
Temps
Temps
d’exécution
d’arrivée
(CPU)
P1 0 3
P2 1 3
P3 4 4
P4 6 2

Algorithme FIFO (Diagramme de GANTT)

Axe des Processus Légende : En Exécution En Attente

(Pi)

P4
P3
P2
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13

<axe du temps (t)>

• L’ordre d’exécution est : P1 , P2 , P3 , P4 .

Algorithmes d’ordonnancement (2) : SJF
• SJF (Shortest Job First) : Le choix se fait en fonction du temps
d’exécution estimé du processus. Ainsi, l’ordonnanceur va laisser
passer d'abord le plus court des processus de la file d’attente.
• À temps d’arrivée égal, le travail le plus court sera en exécution.
Algorithmes d’ordonnancement (2) : SJF
• Exemple : Soit le Tableau de Processus et son diagramme de
GANTT Temps
Temps
Processus d’exécution
d’arrivée
(CPU)
P1 0 3
P2 1 4
P3 4 4
P4 6 2
P5 7 1

Algorithme SJF (Diagramme de GANTT)

Axe des Processus Légende : En Exécution En Attente

(Pi)

P5
P4
P3
P2
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

<axe du temps (t)>

• L’ordre d’exécution est : P1 , P2 , P5 , P4 , P3 .

Algorithmes d’ordonnancement (3) : SRTF
• SRTF (Shortest Remaining Time First) : SJF + préemption
• Il est plus souple. Si un processus dont le temps d’exécution est
plus court que le reste du temps d’exécution du processus en
cours de traitement entre dans la file d’attente, alors il prendra sa
place. Il y a alors une commutation de contexte, et le traitement
du processus interrompu reprendra plus tard là ou il avait été
laissé.
• Inconvénient : SRTF favorise les travaux courts : les travaux longs
en revanche peuvent être victimes de famine.
• Exemple :
Algorithmes d’ordonnancement (3) : SRTF
• Exemple : Soit le Tableau de Processus et son diagramme de GANTT
Temps
Temps
Processus d’exécution
d’arrivée
(CPU)
P1 0 4
P2 1 2
P3 3 2

Algorithme SRTF (Diagramme de GANTT)

Axe des Processus Légende : En Exécution En Attente

(Pi)

P3
P2
P1
0 1 2 3 4 5 6 7 8 9

<axe du temps (t)>

• L’ordre d’exécution est : P1 , P2 , P3 , P1 .

Algorithmes d’ordonnancement (4) :
Round Robin (Tourniquet)
• RR (Round Robin) ou Tourniquet
• Le processeur gère une liste circulaire de processus.
• Chaque processus dispose d'un quantum de temps pendant
lequel il est autorisé à s'exécuter. Si le processus actif se bloque
ou s'achève avant la fin de son quantum, le processeur est
immédiatement alloué à un autre processus.
Algorithmes d’ordonnancement (4) :
Round Robin (Tourniquet)
• Exemple : Soit le Tableau de Processus et son diagramme de GANTT
Temps
Temps
Processus d’exécution
d’arrivée
(CPU)
P1 0 3
P2 1 5
P3 4 4

Algorithme Round Robin avec Quantum = 3ms (Diagramme de GANTT) File d'Attente

Axe des Processus Légende : En Exécution En Attente àt=0 P1

(Pi)
àt=3 P2
P3
P2 àt=6 P2 P3
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 àt=9 P3 P2

<axe du temps (t)> à t = 11 P3

• Avec Round Robin, il est préférable de faire une file d’attente.

• L’ordre d’exécution est : P1 , P2 , P3 , P2 , P3 .
Algorithmes d’ordonnancement (5) : HPF

• HPF (Highest Priority First)

• L'Ordonnanceur lance le processus prêt de priorité la plus élevée
(la valeur numérique la plus grande).
• En cas de priorités égales on utilise l’algorithme FIFO.
• L’ordonnancement des priorités peut être préemptif ou non.
Algorithmes d’ordonnancement (5) : HPF
• Exemple : Soit le Tableau de Processus et son diagramme de
GANTT Temps
Temps
Processus d’exécution Priorité
d’arrivée
(CPU)
P1 0 3 1
P2 2 2 3
P3 3 3 5

Algorithme HPF SANS PRÉEMPTION (Diagramme de GANTT)

Axe des Processus Légende : En Exécution En Attente

(Pi)

P3
P2
P1
0 1 2 3 4 5 6 7 8 9

<axe du temps (t)>

• L’ordre d’exécution est : P1 , P3 , P2 . (car à t=3 , P3 est plus

prioritaire que P2).
Algorithmes d’ordonnancement (5) : HPF
• Exemple : Soit le Tableau de Processus et son diagramme de
GANTT Processus
Temps
Temps
d’exécution Priorité
d’arrivée
(CPU)
P1 0 3 1
P2 1 2 3
P3 3 3 5

Algorithme HPF AVEC PRÉEMPTION (Diagramme de GANTT)

Axe des Processus Légende : En Exécution En Attente

(Pi)

P3
P2
P1
0 1 2 3 4 5 6 7 8 9

<axe du temps (t)>

• L’ordre d’exécution est : P1 , P2 , P3 , P1 . (car à t=1 , P2 est plus

prioritaire que P1).
 Critères de Performance des algorithmes
d’Ordonnancement
• Temps de Rotation (Séjour) = (Temps fin d’exécution - Temps
d’arrivée)
• Temps Moyen de Rotation (Séjour) = (∑ Temps séjour) / (nbre de
processus)
• Temps d’attente = (Temps de rotation – Durée d’exécution)
• Temps Moyen d’attente = (∑ Temps attente) / (nbre de processus)
• Rendement (Pi)= (Temps CPU(Pi)) / (Temps de Fin d’Exécution(Pi)
– Temps de Début d’Attente (Pi))
• Rendement Moyen(Pi) = (∑ Rendement (Pi)) / (nbre de processus))
 Évaluation des Critères de Performance des
algorithmes d’Ordonnancement
• Un Algorithme est Performant s’il possède ces 3 critères:
a. Le Temps Moyen d’Attente le plus Minimal.
b. Le Temps Moyen d’Exécution (Séjour) le plus Minimal.
c. Le Rendement Moyen le plus Maximal.
 Références:

• https://fr.wikipedia.org/wiki/Processus_(informatique)
• https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics)
• https://cours.polymtl.ca/inf2610/documentation/notes/chap8.p
df
FIN de ce Chapitre

MERCI pour votre attention

DES QUESTIONS ?