Chapitre 2

Gestion des processus

Plan
 Introduction
 Notion de processus
 Etats de processus
 Mécanisme de commutation de contexte
 Bloc de contrôle d’un processus (PCB)
 Interruption/ Déroutement
 Ordonnancement des processus
 Ordonnanceur
 Dispatcheur
 Les algorithmes d’ordonnancement

2
Introduction
 Dans un système multitâche, la ressource la plus cruciale
d’une machine est le processeur.
 Le processeur est alloué à un et un seul processus sélectionné
parmi un ensemble de processus prêts.
Il est nécessaire de bien gérer le processeur pour le rendre
plus productif.
 Le SE doit être capable de résoudre les problèmes
suivants:
 Comment choisir le prochain processus à exécuter ?
 Combien de temps processeur à allouer au processus choisi ?

3
Notions de base des processus (1/2)
 Un processus est une entité dynamique: C’est un programme
en cours d'exécution avec ses propres ressources logiques
(données, variables, fichiers) et physiques (mémoire,
processeur, entrée/sortie, …)
 Ne pas confondre un processus avec programme
 Un programme est une suite d'instructions ; c'est du texte,
un code statique.
 Le processus est un concept dynamique, il représente le
déroulement d'une tâche faisant partie d'une application ou
d’un programme système quelconque.

4
Notions de base des processus (2/2)
 Plusieurs processus peuvent se trouver simultanément en
cours d'exécution (multiprogrammation et temps partagé)
 Le SE manipule deux familles de processus
 Processus système : processus lancé par le SE (init
processus père de tous les processus du système)
 Processus utilisateur : processus lancée par l’utilisateur
(commande utilisateur)

5
Structure des processus
 Les processus des utilisateurs sont lancés par un interprète de
commande. Ils peuvent eux-mêmes lancer ensuite d’autres processus
 On appelle le processus créateur, le père, et les processus créés, les fils
 Les processus peuvent donc se structurer sous la forme d’une
arborescence.
 Au lancement du système, il n’existe qu’un seul processus, qui est
l’ancêtre de tous les autres.
P1 Ancêtre

P2 P3 Père et fils de P1

P4 P5 P6 Fils de P3

Figure1: Le hiérarchie des processus 6

 Etats d’un processus (1/3) Actif
En cours d’exécution
 Quand un processus s’exécute, il
change d’états;
 Trois états sont possibles pour un
processus:
 actif (Elu) quand le processeur est en
train d'exécuter une de ses Prêt
instructions.
→ Dans un système monoprocesseur, un seul
processus peut être actif à la fois;
 bloqué quand il est en attente d'un Bloqué
événement ou d’une synchronisation,
→ i.e. la fin d’une entrée-sortie ou plus
généralement en attente d’un autre
processus.
Attente d’un évènement
 prêt s’il n'est ni actif ni bloqué. extérieur

7
 Etats d’un processus (2/3)
•Sémantique des transitions
Actif
Elu 1 Attribution du processeur au
3
1 processus sélectionné

2 2 Réquisition du processeur après

expiration de la durée du temps
Bloqué
Prêt par exemple

3 Blocage du processus actif en attendant

un évènement tel qu’une E/S
4

4 Débloquage du processus après

disponibilité de l’événement bloquant
8
 Etats d’un processus (3/3)
Terminé
Actif
Nouveau Elu

Bloqué
Prêt

•Nouveau: Le SE a créé le processus

•Terminé: Le processus n’est plus exécutable
9
Propriétés d’un processus
 A un instant donné, un processus est caractérisé par
plusieurs informations:
 Son état: Actif, suspendu, etc.;
 Son identificateur;
 Son compteur ordinal: registre qui contient l'adresse
mémoire de l'instruction prochainement exécutée;
 Ses données en mémoire;
 Toutes autres informations utiles à son exécution (E/S,
fichiers ouverts, etc.);

10
PCB: Process Control Bloc
(Bloc de contrôle de processus)
 PCB : est une structure de Identificateur processus
données du noyau d’un SE Etat du processus (Elu, Bloqué, prêt)
représentant l’état d’un Compteur d’instructions: le processus
processus donné doit reprendre à l’instruction suivante
Contexte pour reprise (registre et
pointeur, pile…)
Information mémoire (espace
d’adressage)
Informations sur les E/S, les
périphériques alloués, les fichiers
ouverts…
Bloc de contrôle de processus
11
Mécanismes de commutation
 L’opération de commutation de contexte qui précède le
changement du processus actif (le basculement de l’activité entre
deux processus) est l’enchaînement indivisible des deux
opérations suivantes:
 Sauvegarde des propriétés du processus actif à un emplacement
particulier de la mémoire.
 Chargement des propriétés d’un autre processus depuis un
emplacement spécifique de la mémoire vers le processeur.

 Cette sauvegarde est nécessaire pour pouvoir poursuivre

ultérieurement l’exécution du processus suspendu.
 PCB permet la sauvegarde et la restauration du contexte mémoire
et du contexte processeur lors des opérations de commutations de
contexte
12
 Mise en œuvre de la commutation
Système
Processus P1 L’ordonnanceur Processus P2

Points interruptibles
Commutation
de contexte
Sauvegarder l’état dans PCB1

Restaurer l’état de PCB2

Sauvegarder l’état dans PCB2

Restaurer l’état de PCB1

13
 Les déroutements/Les interruptions
Une commutation de contexte peut se produire dans les cas suivants:
 Les interruptions qui sont d’origine externe (produite par un autre processus ou
par le matériel). Ce sont des signaux envoyés de façon asynchrone au processeur
qui le forcent à suspendre l’activité en cours au profil d’une autre (Horloge…).
 Les déroutements sont déclenchés par une cause interne au programme en cours
d’exécution. un déroutement lié à l'exécution de l'instruction en cours :
traitement d'une erreur ou situation exceptionnelle. Exemples :
 Lorsqu’un programme effectue une opération interdite (exp : débordement
de tableaux hors de la zone d'adresses allouée au programme)
 Lorsque les données sont incorrectes (exp : division par 0)
 Lorsque l’instruction ne correspond pas à un code exécutable (Exemple: dive
au lieu de div)
 un appel au superviseur lié à l'instruction en cours qui nécessite l'usage d'une
fonction du système d'exploitation. Exemple : traitement d'une entrée-sortie
14
(lecture/écriture).
Ordonnancement des processus (1/4)

 Chaque fois, que le processeur devient non actif, le système

d’exploitation doit sélectionner un processus de la file
d’attente des processus prêts, et lui passe le contrôle.

 Cette tâche est effectuée par deux routines système :

– Un ordonnanceur (scheduleur): Il prend en charge la mise en
ordre des processus qui demandent le processeur (quel
processus à activer)
– Un dispatcheur: Il est responsable au changement de
contexte et l’allocation du processeur à un processus choisi par
le scheduleur (le quantum de temps alloué au processus)
15
Ordonnancement des processus (2/4)

16
Ordonnancement des processus (3/4)
 Les objectifs d'un ordonnanceur d'un système multi-tâches
sont :
– S'assurer que chaque processus en attente d'exécution reçoive
sa part de temps processeur.
– Minimiser le temps de réponse.
– Utiliser le processeur à 100%.
– Utilisation équilibrée des ressources.
– Prendre en compte des priorités.
– Réduire le nombre et la durée des changements de contexte

17
Ordonnancement des processus (4/4)
 Objectifs d’ordonnancement : Critères de performances
– Temps de séjour d’un processus (temps de rotation ou de virement) : temps
entre l’entrée du processus et sa sortie.
– Temps d'attente d’un processus : somme des périodes que le processus passe
à attendre.
– Capacité de traitement : nombre de processus traités par unité de temps.
– Taux d’utilisation d’un processeur : rapport entre la durée où le CPU est
actif et la durée totale.
– Etc.
 2 types d’ordonnanceurs selon si l’opération de réquisition
est autorisée ou non :
– Ordonnanceurs non-préemptifs (Actif Prêt)
– Ordonnanceurs préemptifs (Actif Prêt)

18
I- Les ordonnanceurs non-préemptifs ou
sans réquisition
I- Les ordonnanceurs non-préemptifs ou
sans réquisition
 Le système d’exploitation choisit le processus suivant à
exécuter selon :
 Premier arrivé, Premier servi (FCFS, First-Come First-Served)
 Plus court d’abord (SPF, Short Process First ou SJF Short Job
First).
 Plus prioritaire d’abord
 Il alloue le processeur au processus jusqu’à ce dernier se
termine ou se bloque (en attente d’un événement). Il n’y a
pas de réquisition.

20
 Algorithme FCFS (1/2)
Processus Temps d’exécution Temps d’arrivage
A 3 0
B 6 1
C 4 4
D 2 6
E 1 7

A A A B B B B B B C C C C D D E
1 5 10 15

Arrivée de B
Arrivée de c Le temps de séjour pour chaque processus ?
Arrivée de D Le temps d'attente pour chaque processus ?

Arrivée de E 21
Algorithme FCFS (2/2)
 Le temps de séjour: C’est la durée moyenne nécessaire pour l’exécution
d’un processus. Le temps de séjour est calculé en soustrayant le temps d'entrée
du processus du temps de terminaison
 Le temps d'attente: C’est la durée moyenne qu’un processus passe à
attendre. Il est calculé en soustrayant le temps d'exécution du temps de séjour
Processus Temps de séjour Temps d’attente
A 3-0 = 3 3-3 = 0
B 9-1 = 8 8-6 = 2
C 13-4=9 9-4=5
D 15-6 = 9 9-2 = 7
E 16-7=9 9-1= 8

Temps de séjour moyen=7,6

Temps d’attente moyen=4,4
3,2 unités de temps par processus 22
 Algorithme SPF (1/2)
Processus Temps d’exécution Temps d’arrivage
A 3 0
B 6 1
C 4 4
D 2 6
E 1 7

A A A B B B B B B E D D C C C C
1 5 10 15

Arrivée de B
Arrivée de c
Arrivée de D

Arrivée de E 23
Algorithme SPF (2/2)
Processus Temps de séjour Temps d’attente
A 3-0 = 3 3-3 = 0
B 9-1 = 8 8-6 = 2
C 16-4=12 12-4=8
D 12-6 = 6 6-2 = 4
E 10-7=3 3-1 = 2

Temps de séjour moyen=6,4

Temps d’attente moyen=3,2
3,2 unités de temps par processus
 Meilleur temps d’attente

24
Exercice d’application
 Cinq travaux A, B, C, D et E arrivent pratiquement en même
temps dans un centre de calcul. Leur temps d’exécution
respectif est estimé à 10, 6, 2, 4 et 8 secondes.
 Tracez le digramme de Gantt et déterminez le temps moyen de
rotation (séjour) pour chacun des algorithmes
d’ordonnancement suivants.
• Premier arrivé, premier servi FCFS (exécution dans
l’ordre 10, 6, 2, 4, 8) ;
• Plus court d’abord SJF ;

25
 Algorithme du plus prioritaire d’abord (1/2)

Processus Temps d’exécution Temps d’arrivage Priorité

A 10 0 3
B 6 0 5
C 2 0 2
D 4 0 1
E 8 0 4

D D D D C C A A A A A A A A A A E E E E E E E E B B B B B B

26
Algorithme du plus prioritaire d’abord (1/2)

Processus Temps d’exécution Temps d’arrivage Priorité

A 10 0 3
B 6 1 5
C 2 4 2
D 4 6 1
E 8 7 4

27
Algorithme du plus prioritaire d’abord (2/2)
Processus Temps de séjour Temps d’attente
A 16 6
B 30 24
C 6 4
D 4 0
E 24 16

Temps de séjour moyen=16

Temps d’attente moyen=10
6 unités de temps par processus

28
Difficultés majeures avec les méthodes
discutées
 Premier arrivé’ premier servi (FCFS)
 Temps moyen d’attente non optimal
 Mauvaise utilisation des ressources s’il y a apport continu de processus aux
cycles longs (effet d’accumulation)
 Plus court d’abord (SJF) et plus court temps restant (SRT)
 Difficulté de prévoir la durée du prochain cycle
 Famine possible des processus ‘longs’ s’il y a apport continu de processus aux
cycles courts
 Donc besoin d’une méthode systématiquement préemptive:
 Le Tourniquet
 Si vous faites toujours des devoirs les plus courts en premier, vous pourriez avoir
l’impression de faire beaucoup mais vous pourriez ne jamais arriver aux plus
longs…
 Si vous faites les devoirs dans l’ordre d’arrivée, les longs pourraient vous
bloquer pour longtemps…
 Donc la solution est de donner un peu de temps à chacun, cycliquement

29
II- Les ordonnanceurs préemptifs ou avec
réquisition
II- Les ordonnanceurs préemptifs
 Ordonnanceur préemptif = avec réquisition
 Pour garantir qu’aucun processus ne s’exécute pas pendant trop
de temps, les ordinateurs ont une horloge électronique qui génère
périodiquement une interruption d’horloge.
 A chaque interruption d’horloge, le SE reprend la main et décide
si le processus courant doit poursuivre son exécution ou s’il doit
être suspendu pour laisser place à un autre
 Le processeur passe d’un processus à un autre en exécutant
chaque processus pendant quelques dizaines ou centaines de
millisecondes.
 Le temps d’allocation du processeur au processus est appelé
quantum
 La commutation entre processus doit être rapide  exiger un
temps nettement inférieur au quantum 31
Ordonnanceur circulaire: Round Robin (1/3)
 L’algorithme du tourniquet, circulaire, ou round robin mémorise
dans une file de type FIFO (First In First Out) la liste des processus
prêts, c’est-à-dire en attente d’exécution
Fin
E D C B A Processeur

Processus suspendu

 Il alloue le processeur au processus en tête de file, pendant une durée de

temps (quantum)
 Si le processus courant se bloque ou se termine avant la fin de son
quantum, le processeur est alloué immédiatement au processus en tête
de la file d’attente
 Si le processus ne se termine pas au bout de son quantum, son exécution
est suspendue. Ce processus est alors placé à la fin de la file d’attente.
32
Ordonnanceur circulaire: Round Robin (2/3)
 Les processus qui arrivent ou qui passent de bloqué à prêt sont insérés
en queue de file
 Choix de la valeur du quantum
 Un quantum trop petit cause plusieurs commutations de processus et
réduit l’efficacité du processeur.
 Un quantum très élevé augmente le temps de réponse (temps passé
dans la file d’attente des processus prêts avant la première exécution)
 Un quantum entre 20 et 50 ms est raisonnable

33
 Ordonnanceur circulaire: Round Robin (3/3)
Processus Temps d’exécution Temps d’arrivage
A 15 unités de temps 0
B 4 unités de temps 2 unités de temps
Le temps de commutation est supposé nul, Quantum=10

A A A A A A A A A A B B B B A A A A A

Processus Temps de séjour Temps d’attente

Arrivée de B A 19-0=19 19-15=4
B 14-2=12 12-4=8

Temps de séjour moyen=15,5

Temps d’attente moyen=6
3 commutations de contexte
34
 Ordonnanceur circulaire: Round Robin (3/3)
Processus Temps d’exécution Temps d’arrivage
A 15 unités de temps 0
B 4 unités de temps 2 unités de temps
Le temps de commutation est supposé nul, Quantum=3

A A A B B B A A A B A A A A A A A A A

Processus Temps de séjour Temps d’attente

Arrivée de B A 19-0=19 19-15=4
B 10-2=8 8-4=4

Temps de séjour moyen=13,5

Temps d’attente moyen=4
5 commutations de contexte
35
Ordonnanceur du plus court temps
restant(SRT) (1/2)

 L’ordonnancement du plus court temps restant ou Shortest

Remaining Time est la version préemptive de l’algorithme

SJF

 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, alors il prendra sa place.

36
 Ordonnanceur du plus court temps restant
(SRT) (2/2)
Processus Temps d’exécution Temps d’arrivage
A 15 unités de temps 0
B 4 unités de temps 2 unités de temps
Le temps de commutation est supposé nul

A A B B B B A A A A A A A A A A A A A

Processus Temps de séjour Temps d’attente

Arrivée de B A 19-0=19 19-15=4
B 6-2=4 4-4=0

Temps de séjour moyen=11,5

Temps d’attente moyen=2
3 commutations de contexte
37
 Exercice d’application
Considérons cinq Processus P1, P2, P3, P4, P5, dont les temps
d'exécution et leurs temps d’arrivée respectifs sont les suivants

Le temps de commutation est supposé nul.

 Dessiner le diagramme de GANTT pour l’ordonnancement SRT
et Round Robin (quantum = 3 unités de temps)
 Calculer le temps de séjour de chaque processus, le temps
moyen de séjour, le temps d’attente, le temps moyen38
d’attente, et le nombre de changements de contexte
Ordonnanceur préemptif basé sur les
priorités
 L’ordonnanceur à priorité donne à chaque processus une priorité
qui peut être statique ou dynamique
 Le choix du processus à élire dépend des priorités des processus
prêts
 Les processus ayant la même priorité sont regroupés dans une file
FIFO
Il y’a autant de files qu’il y a de niveau de priorité
Entête de file d’attente (Priorité supérieure)
Priorité 4
Priorité 3
Priorité 2
Priorité 1 (Priorité inférieure) 39
Ordonnanceur préemptif basé sur les
priorités
 L’ordonnanceur choisit le processus le plus prioritaire qui se
trouve en tête de file
 Si un processus plus prioritaire arrive, on suspend le processus
actif et on exécute le nouveau. Le processus passe à la fin de la file
d’attente de la priorité correspondante.
 Si un processus arrive avec la même priorité, on continue sans
réquisition (Minimiser le nombre de commutations).

 Remarque : Il y a des SE qui utilisent différents algorithmes

d‘ordonnancement pour chaque file de priorité

40
 Ordonnanceur préemptif basé sur les priorités
Exemple (1/2) (Priorité supérieure)
Processus Temps Temps Priorité 1 E
d’exécution d’arrivage
2 C C
D
A 10 0 3
3 A
B 5 2 7 7 B
C 15 5 2 (Priorité inférieure)
D 1 10 2
E 3 15 1
On suppose que les priorités sont statiques

A A A A A C C C C C C C C C C E E E DC C C C C A A A A A B B B B B

A B C D E

41
 Ordonnanceur préemptif basé sur les priorités
Exemple (2/2)
A A A A A C C C C C C C C C C E E E DC C C C C A A A A A B B B B B

A B C D E
Processus Temps de séjour Temps d’attente
A 29 29-10=19
B 32 32-5=27
C 19 19-15=4
D 9 9-1=8
E 3 3-3=0

Temps de séjour moyen=18,4

Temps d’attente moyen=11,6
7 commutations de contexte
42
 Processus Temps Temps Priorité (Priorité supérieure)
d’exécution d’arrivage
1 E
A 10 0 3
2 D C
C
B 5 2 3
3 B A
A
C 15 5 2
(Priorité inférieure)
D 1 10 2
E 3 15 1
Utiliser priorité fixe et RR avec quantum = 5 ms
A A A A A C C C C C DC C C C E E E C C C C C C B B B B B A A A A A

A B C D E

Note : Placer le nouveau processus dans la file d’attente puis y remettre le processus suspendu
43
 Processus Temps Temps Priorité (Priorité supérieure)
d’exécution d’arrivage
1 E
A 10 0 3
2 D C
C
B 5 2 3
3 B A
A
C 15 5 2
(Priorité inférieure)
D 1 10 2
E 3 15 1
Utiliser priorité fixe et RR avec quantum = 10 ms
A A A A A C C C C C C C C C C E E E D C C C C C B B B B B A A A A A

A B C D E

Que se passe si le temps d’exécution de E prend des heures ?? 44

Ordonnanceur basé sur les priorités avec
files d’attente à rétroaction ou retour (1/2)
Attribution et évolution des priorités
 Pour empêcher les processus de priorité élevée de s’exécuter
indéfiniment (privation de ressources ou famine), l’ordonnanceur
diminue régulièrement la priorité du processus en cours d’exécution.
 L’attribution et l’évolution des priorités dépendent des objectifs fixés et
de beaucoup de paramètres.
Exemple
• Les processus qui font beaucoup d’E/S doivent acquérir le processeur
dès qu’ils le demandent.
• La nouvelle valeur de priorité est le rapport : quantum/temps
réellement utilisé par le processus.
• Les processus qui ont le plus grand rapport sont les plus prioritaires : –
Si le quantum = 100 ms et le temps utilisé = 2 ms, la nouvelle priorité
est 50. – Si le quantum = 100 ms et le temps utilisé = 50 ms, la
nouvelle priorité est 2. 45
Ordonnanceur Windows
 L’ordonnancement au niveau du SE Windows se base sur
l’algorithme priorité dynamique.
 Une priorité qui évolue au cours de l’exécution du processus.
 L’ordonnanceur parcourt chaque file en utilisant l’algorithme
du Tourniquet

46
Ordonnanceur Linux
 Une priorité est affectée à chaque processus
 La priorité la plus importante est celle qui est la plus élevée
 Un quantum est affecté à un processus selon sa priorité
 Un processus ayant une priorité de 10 aura un quantum de 100
ms.
 Après 10 ms, le quantum diminue de 1 ms
 Le processus ayant la note la plus élevée sera exécuté en
premier
 Note= priorité + quantum E

47
 Exercice d’application
Soient trois processus A, B et C. Le processus A arrive en premier suivi
de B (20 msec après), puis C (46 msec après A). On suppose que
l’exécution du processus A nécessite 80 msec de temps d’exécution.
L’exécution du processus B nécessite d’abord 50 msec de temps
d’exécution, bloquera ensuite durant 20 msec pour une entrée/sortie,
puis exigera finalement 30 msec de temps d’exécution. L’exécution du
processus C nécessite 40 msec de temps d’exécution. Le temps de
changement de contexte est de 1 msec.
 Dessiner le diagramme de GANTT pour l’ordonnancement Round
Robin en considérant quantum = 30 msec, 50 msec et 20 msec.
 Calculer le temps de séjour de chaque processus A, B et C, le temps
moyen de séjour, le temps d’attente, le temps moyen
d’attente, et le nombre de changements de contexte
48