La gestion des processus

GIF-1001 Ordinateurs: Structure et Applications, Hiver 2017

Jean-François Lalonde
Image: fugly.com
Analogies
• Un illusionniste :
• Fait disparaître certaines limites du
matériels

• Donne l’illusion que la machine a une

mémoire infinie et une infinité de
processeurs

• Un gouvernement :
• Protège les utilisateurs les uns des autres

• Partage des ressources de façon efficace

et équitable

2
Crédit: P. Giguère
Programmes, processus et threads
• Un programme est un ensemble d’instructions et de variables
dont le but est d’accomplir une tâche précise. Un programme
est habituellement créé par un programmeur doté du
compilateur adéquat.

• Un processus est composé d’un programme et de l’ensemble

des ressources reliées à l’exécution du programme. Ces
ressources incluent de la mémoire, des fichiers ouverts par le
programme, du temps de CPU et autres. Un processus n’est
pas un programme! Un processus est créé par:
• une requête de l’usager (ex: exécution de programme),

• le système d’exploitation

• ou un autre processus.

3
Programmes, processus et threads
• Un « thread » est une partie d’un processus qui peut
être exécutée indépendamment des autres éléments du
processus (en parallèle).

• Un thread a ses propres registres (incluant le compteur

de programme) et sa propre pile, mais il partage le reste
de ses ressources avec les autres constituant du
processus.

• Les threads sont créés habituellement au début d’un

programme. Ils peuvent servir à répondre à des
événements dans des programmes (exemples
d’événement: clic de souris, touche de clavier enfoncée,
message reçu par port série, etc.).

4
Exécution multi-tâches
• Exécuter un seul programme à la fois est un gaspillage de temps
et de ressources, car les programmes attendent souvent après un
périphérique. Par exemple, un programme peut attendre qu’un
fichier sur le disque dur soit lu. Pendant ce temps, le
microprocesseur tourne à vide.

• Certains programmes ont une vitesse d’exécution limitée par la

puissance du microprocesseur (CPU Bound), mais la plupart des
programmes sont limités par de nombreux accès aux
périphériques (I/O Bound).

• Un système d’exploitation multi-tâches est un SE où plusieurs

programmes roulent « simultanément ». Il faut rappeler que le
microprocesseur n’exécute qu’un programme à fois. L’acétate
suivante montre deux façons d’exécuter plusieurs programmes «
simultanément ».

5
Exécution multi-tâches
• Partage du CPU lors d’attente après les entrées-sorties (I/O)


 Programme 1 Exécution Requête I/O Attente Exécution



 Programme 2 Exécution Requête I/O Attente


Programme 3 Exécution Requête I/O

• Partage du CPU dans le temps

Programme 1 Exécution Attente Exécution

Sélection de
Programme 2 Exécution Attente
programme

OS dispatcher Attente Attente Attente

Interrupts
d'horloge 1quantum

6
Rappel: Interruptions et système d’exploitation

• Les interruptions permettent l’exécution de

plusieurs processus

• Comment?
• Une horloge génère des interruptions périodiquement

• À chaque interruption, on change le processus à

exécuter

7
Exécution multi-tâches
• Le SE change le programme exécuté:
• lorsque ce programme attends après un périphérique. Lorsqu’un programme utilise les
services d’I/O, un nouveau programme est exécuté.

• lorsque l’horloge du système émet une interruption.

• Le SE interrompt le programme qui roule avec une interruption répétitive (basée sur
l’horloge du système). Lorsque cette interruption survient, le système d’exploitation
utilise un peu de temps de CPU afin de déterminer quel est le prochain programme
à exécuter. Chaque programme est ainsi exécuté en petits morceaux (time-slicing)
de temps appelés quantum. L’opération consistant à choisir le prochain programme
exécuté se nomme ordonnancement (dispatching).

• L’ordonnanceur (dispatcher) choisit le prochain programme à effectuer en fonction

de plusieurs critères (priorité, temps inactif, bloqué par un accès aux
périphériques…).

• Un SE qui limite le temps d’exécution d’un programme afin de faire de la supervision

est dit préemptif (avec réquisition). Lorsqu’il n’y pas de réquisition, les programmes
s’exécutent un peu plus vite car le système d’exploitation ne revient pas
continuellement. Toutefois, il ne faut pas que le programme plante…

8
Un processus… dans tous ses états

• Lorsqu’un processus est démarré, il est tout

d’abord examiné par l’admission de haut niveau
(high level scheduler)

• Celui-ci détermine si l’ordinateur possède les

ressources nécessaires pour exécuter le processus

• Si oui (la vaste majorité du temps), le processus est

admis et tombe dans l’état « prêt »

9
Processus: état « prêt »

• Le micro-processeur est occupé à exécuter un

autre processus

• Le processus est prêt d’être exécuté, mais il ne

peut pas: il est en attente du micro-processeur

• Il reste dans cet état jusqu’à ce que l’ordonnanceur

le sélectionne comme prochain processus à
exécuter

10
L’ordonnanceur

• Programme (du système d’exploitation) qui

sélectionne le prochain processus à exécuter
• S’exécute périodiquement grâce à des interruptions qui
redonnent le contrôle au système d’exploitation

• Il en existe plusieurs variantes (voir plus loin…)

11
Processus: état « en cours »

• Le processus contrôle le micro-processeur!

• Il le fait jusqu’à ce que:

• il demande à utiliser un périphérique (entrée-sortie)
• il tombe alors dans l’état « bloqué »

• l’ordonnanceur reprenne le contrôle pour pouvoir

exécuter un autre processus
• il revient alors à l’état « prêt »

12
Processus: état « bloqué »

• Le processus est en attente d’un périphérique

(entrée-sortie)

• Il doit donc attendre après ce périphérique!

• Jusqu’à ce que ce dernier soulève une interruption
pour indiquer au système d’exploitation qu’il a terminé
la tâche qu’on lui a demandé de faire

• Le processus est alors remis dans l’état « prêt »

13
Processus: état « terminé »

• Lorsque le processus a complété son exécution,

ou lorsqu’on le ferme volontairement, il devient
dans l’état « terminé ».

14
Un processus… dans tous ses états

Ordonnancement
Nouveau Terminé

Prêt En cours
Admission, Fin du
Planification de Quantum
terminé processus
haut-niveau

Requête E/S
Attente d'E/S
finie
Bloqué Attente de temps
Temps écoulé
ou en
attente

15
Process Control Block (PCB)
• Chaque processus:
Process ID (PID)

• a un bloc de contrôle qui le décrit; Pointer to parent process

• a un IDentifieur unique; Pointers to child processes

• peut avoir des enfants ou un parent; Process state

Program Counter
• a un état;
Registers
• a ses registres, sa mémoire et sa pile;
Memory pointers
• a une priorité.
Priority information

• Les processus peuvent partager de Accounting information

la mémoire, des processus, des Pointers to shared ressources

fichiers, des I/Os et autres.
PCB Typique

16
Ordonnancement (Dispatching)
• L’ordonnancement des processus consiste simplement à
décider quel processus sera exécuté dans le quantum suivant.

• Un algorithme d’ordonnancement a les objectifs suivants:

Assurer l’équité Tous les processus sont traités également

Maximiser l’exécution Terminer le plus de processus possible

Temps d’exécution min. Temps d’exécution le plus court possible

Utilisation max du CPU Le CPU doit être utilisé au maximum

Utilisation max ressources Les ressources doivent être utilisées au max.

Détérioration graduelle Un système surchargé doit ralentir, pas planter

Temps d’attente min. Petit délai entre l’admission et l’exécution

Temps de réponse correct Tâches longues, longues et tâches courtes, courtes

Prévenir la famine (starvation) L’exécution d’un processus ne doit pas être reportée indéfiniment.

17
Analogie de la vie de tous les jours™

18
Algorithmes d’ordonnancement
Processus 1 Processus 2
terminé terminé

P1 P1 P1 P1 P2 P2 P2 P3

• Premier arrivé, premier servi (exemple de

mauvais algorithme)
• Le premier processus admis est exécuté jusqu’à sa fin.
Puis, on exécute le suivant.

• Cet algorithme n’est jamais utilisé. Il équivaudrait à

remplacer le noyau du système d’exploitation par une
file d’exécution des processus et détruirait l’illusion
d’une exécution simultanée de plusieurs processus.

19
Algorithmes d’ordonnancement
Processus 2 Processus 1
terminé terminé

P2 P2 P1 P1 P1 P1 P3 P3 P3 P3 P3

• Le plus court d’abord: On exécute le processus le

plus court d’abord.
• Avantages: Maximise l’exécution et le temps
d’exécution

• Désavantages: Famine possible, inéquitable

20
Algorithmes d’ordonnancement
P1 P2 P3 P4

• Le tourniquet (round-robin): On exécute les

processus à tour de rôle.
• Avantages: Tous les processus ont du temps de CPU,
très équitable

• Désavantages: Ne maximise pas l’exécution ni le temps

d’exécution

21
Exercice #1
• Les processus suivants sont admis à l’ordonnanceur
(dans l’ordre):
• P1, durée: 5

• P2, durée: 3

• Écrivez quel processus est exécuté par le micro-

processeur à chaque quantum de temps si l’algorithme
utilisé par l’ordonnanceur est:
• premier arrivé, premier servi

• plus court d’abord

• tourniquet

22
Exercice #1: solution
• Les processus suivants sont admis à l’ordonnanceur (dans
l’ordre):
• P1, durée: 5

• P2, durée: 3

• Écrivez quel processus est exécuté par le micro-processeur

à chaque quantum de temps si l’algorithme utilisé par
l’ordonnanceur est:
• premier arrivé, premier servi: P1—P1—P1—P1—P1—P2—P2—P2

• plus court d’abord: P2—P2—P2—P1—P1—P1—P1—P1

• tourniquet: P1—P2—P1—P2—P1—P2—P1—P1

23
Arrivée dynamique des processus
• En pratique, les processus arrivent à différents
moments. Il faut donc recalculer quel processus
sera exécuté en prochain.

• Plus court d’abord

• On maintient une liste des processus, et on sélectionne
le plus court

• Tourniquet
• On maintient une file d’attente. Lorsqu’un nouveau
processus arrive, on le place à la fin de la file d’attente.

24
Exercice #2
• Les processus suivants sont admis à l’ordonnanceur (dans l’ordre):
• P1, durée: 5, temps d’arrivée: 0

• P2, durée: 4, temps d’arrivée: 0

• P3, durée: 1, temps d’arrivée: 2

• P4, durée: 3, temps d’arrivée: 5

• Écrivez quel processus est exécuté par le micro-processeur à

chaque quantum de temps si l’algorithme utilisé par l’ordonnanceur
est:
• premier arrivé, premier servi

• plus court d’abord

• tourniquet

25
 Exercice #2: tourniquet
Temps: 0

File d’attente: P1 P2

P1: 5
Temps restant

P2: 4

P3:

P4:

Ordonnancement:

26
 Exercice #2: tourniquet
Temps: 0

File d’attente: P1 P2 P1

P1: 5 4
Temps restant

P2: 4

Ordonnancement: P1

27
 Exercice #2: tourniquet
Temps: 1

File d’attente: P1 P2 P1

P1: 5 4
Temps restant

P2: 4

Ordonnancement: P1

28
 Exercice #2: tourniquet
Temps: 1

File d’attente: P1 P2 P1 P2

P1: 5 4
Temps restant

P2: 4 3

Ordonnancement: P1 P2

29
 Exercice #2: tourniquet
Temps: 2

File d’attente: P1 P2 P1 P2 P3

P1: 5 4
Temps restant

P2: 4 3

P3: 1

Ordonnancement: P1 P2

30
 Exercice #2: tourniquet
Temps: 2

File d’attente: P1 P2 P1 P2 P3 P1

P1: 5 4 3
Temps restant

P2: 4 3

P3: 1

Ordonnancement: P1 P2 P1

31
 Exercice #2: tourniquet
Temps: 3

File d’attente: P1 P2 P1 P2 P3 P1

P1: 5 4 3
Temps restant

P2: 4 3

P3: 1

Ordonnancement: P1 P2 P1

32
 Exercice #2: tourniquet
Temps: 3

File d’attente: P1 P2 P1 P2 P3 P1 P2

P1: 5 4 3
Temps restant

P2: 4 3 2

P3: 1

Ordonnancement: P1 P2 P1 P2

33
 Exercice #2: tourniquet
Temps: 4

File d’attente: P1 P2 P1 P2 P3 P1 P2

P1: 5 4 3
Temps restant

P2: 4 3 2

P3: 1

Ordonnancement: P1 P2 P1 P2

34
 Exercice #2: tourniquet
Temps: 4

File d’attente: P1 P2 P1 P2 P3 P1 P2

P1: 5 4 3
Temps restant

P2: 4 3 2

P3: 1 0

Ordonnancement: P1 P2 P1 P2 P3

35
 Exercice #2: tourniquet
Temps: 5

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4

P1: 5 4 3
Temps restant

P2: 4 3 2

P3: 1 0

P4: 3

Ordonnancement: P1 P2 P1 P2 P3

36
 Exercice #2: tourniquet
Temps: 5

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4 P1

P1: 5 4 3 2
Temps restant

P2: 4 3 2

P3: 1 0

P4: 3

Ordonnancement: P1 P2 P1 P2 P3 P1

37
 Exercice #2: tourniquet
Temps: 6

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2

P1: 5 4 3 2
Temps restant

P2: 4 3 2 1

P3: 1 0

P4: 3

Ordonnancement: P1 P2 P1 P2 P3 P1 P2

38
 Exercice #2: tourniquet
Temps: 7

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4

P1: 5 4 3 2
Temps restant

P2: 4 3 2 1

P3: 1 0

P4: 3 2

Ordonnancement: P1 P2 P1 P2 P3 P1 P2 P4

39
 Exercice #2: tourniquet
Temps: 8

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4 P1

P1: 5 4 3 2 1
Temps restant

P2: 4 3 2 1

P3: 1 0

P4: 3 2

Ordonnancement: P1 P2 P1 P2 P3 P1 P2 P4 P1

40
 Exercice #2: tourniquet
Temps: 9

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4 P1

P1: 5 4 3 2 1
Temps restant

P2: 4 3 2 1 0

P3: 1 0

P4: 3 2

Ordonnancement: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2

41
 Exercice #2: tourniquet
Temps: 10

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4 P1 P4

P1: 5 4 3 2 1
Temps restant

P2: 4 3 2 1 0

P3: 1 0

P4: 3 2 1

Ordonnancement: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4

42
 Exercice #2: tourniquet
Temps: 11

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4 P1 P4

P1: 5 4 3 2 1 0
Temps restant

P2: 4 3 2 1 0

P3: 1 0

P4: 3 2 1

Ordonnancement: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4 P1

43
 Exercice #2: tourniquet
Temps: 12

File d’attente: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4 P1 P4

P1: 5 4 3 2 1 0
Temps restant

P2: 4 3 2 1 0

P3: 1 0

P4: 3 2 1 0

Ordonnancement: P1 P2 P1 P2 P3 P1 P2 P4 P1 P2 P4 P1 P4

44
Exercice #2: solution
• Les processus suivants sont admis à l’ordonnanceur (dans l’ordre):
• P1, durée: 5, temps d’arrivée: 0

• P2, durée: 4, temps d’arrivée: 0

• P3, durée: 1, temps d’arrivée: 2

• P4, durée: 3, temps d’arrivée: 5

• Écrivez quel processus est exécuté par le micro-processeur à chaque

quantum de temps si l’algorithme utilisé par l’ordonnanceur est:
• premier arrivé, premier servi
• P1—P1—P1—P1—P1—P2—P2—P2—P2—P3—P4—P4—P4

• plus court d’abord

• P2—P2—P3—P2—P2—P4—P4—P4—P1—P1—P1—P1—P1

• tourniquet
• P1—P2—P1—P2—P3—P1—P2—P4—P1—P2—P4—P1—P4

45
Algorithmes d’ordonnancement

• Priorité: On exécute les processus selon leur

priorité.
• Avantages: Temps de réponse correct, temps d’attente
minimum

• Désavantages: Ne maximise pas l’exécution ni le temps

d’exécution, famine possible, le programmeur doit
déclarer des priorités

46
Algorithmes d’ordonnancement

• Priorité Variable: On exécute les processus selon

leur priorité. La priorité d’un processus change
dynamiquement en fonction d’évènements (fin
d’attente, le processus a faim, admission, …).
• Avantages: Temps de réponse correct, temps d’attente
minimum

• Désavantages: Même que l’algorithme de priorité, mais

avec un impact beaucoup moindre.

47
Algorithmes d’ordonnancement
Processus 2
terminé

P1 P1 P1 P2 P2 P2 P3 P3 P3

P1 P3

• File avec tourniquet (round-robin): On exécute

plusieurs fois les processus nouvellement admis,
puis les processus non terminés sont mis dans un
tourniquet.
• Avantages: Tous les processus ont du temps de CPU;
très équitable.

• Désavantages: Même que tourniquet, mais avec un

impact moindre

48
Algorithmes d’ordonnancement

• Le plus critique (RTOS surtout): Le processus

devant être exécuté dans les plus brefs délais est
d’abord exécuté.
• Avantages: Garantit l’exécution d’un processus critique
à l’intérieur d’un certain temps.

• Désavantages: Ne maximise pas l’exécution ni le temps

d’exécution, famine possible, le programmeur doit
déclarer des priorités

49
Ordonnancement — Windows
• Algorithme: “Multilevel Feedback Queues”

Nouveau processus

Q8 (priorité maximale) Proc. Proc.

Q7
Q6 Proc.

Q5
Q4
Q3
Q2 Proc. Proc.

Proc.
Dernière queue opère avec
Q1 (priorité minimale)
un tourniquet (“round-robin”)
50
Ordonnancement — Windows

• Variantes:
• Nombre de queues

• L’algorithme d’ordonnancement à utiliser pour chaque

queue (peut être différent)

• Comment assigner un processus à une queue à priorité

plus élevée (ou plus faible)

51
Ordonnancement — Linux

• Algorithme: “Completely Fair Scheduler”

• Arbre “rouge-noir” — arbre binaire balancé

• Assigne un “score” à chaque processus basé sur une

comparaison avec un OS idéal
• OS idéal: traite tous les processus en parallèle

• Le score est élevé si la différence entre le temps de

traitement alloué au processus et le temps que ça
aurait dû prendre est élevé

52
“Swapping”

• Tous les PCBs sont habituellement en mémoire

parce que le dispatcher doit avoir les informations
sur les processus rapidement.

• Lorsqu’un processus est inactif depuis longtemps

(il est bloqué par une opération très longue par
exemple), son PCB peut être mis sur le disque dur
pour récupérer de la mémoire. Le PCB sur le
disque dur est un swap file.

53
Références et exercices

• Références
• Irv Englander: chap. 15.3, 18 (jusqu’à 18.5)

54