SYSTÈME

D’EXPLOITATION
Chapitre 1 : Processus
Processus

Notion de processus
Rappel sur la chaine de production d'un programme exécutable
L'exécution d'un programme
Le processus
Les états du processus
Le bloc de contrôle du processus (PCB)

Notions liées à l'ordonnancement de processus

Qu'est-ce que l'ordonnancement de processus ?
Ordonnancement préemptif ou non préemptif
Les entités système responsables de la fonction d'ordonnancement

Les politiques d'ordonnancement

Objectifs des politiques d'ordonnancement
Les principales politiques d'ordonnancement
premier arrivé, premier servi (First Come First Served)
plus court temps d'abord (Shortest Job First)
tourniquet (Round Robin)
priorités constantes
files de priorités constantes multiniveaux avec ou sans extinction de priorité
Introduction aux systèmes d'exploitation

Notion de processus : Rappel sur la chaine de production d'un programme exécutable

Bibliothèq
ue
prog.exe :
programme
prog.exe : process
prog.c prog.o Exécutable
Exécutable en
source objet sur disque
mémoire

Editeur de Editeur de
Compilateur Chargeur
texte liens
résoudre les alloue de la
dépend du références place
langage externes, mémoire
vérifie que associer les pour les
la syntaxe appels données et
système le
programme
Introduction aux systèmes d'exploitation

Notion de processus : Rappel sur la chaine de production d'un programme exécutable

 La chaine de production de programme transforme un programme écrit dans un langage de haut niveau en
un programme dit exécutable, écrit en langage machine. Cette transformation s'effectue à l'aide de plusieurs
étapes :

 L'utilisateur saisit son programme à l'aide de l'éditeur de texte qui crée un fichier sur le disque que l'on
appelle le fichier source.

 Ce fichier source est ensuite compilé à l'aide d'un compilateur dépendant du langage de programmation
utilisé et dont le rôle est de vérifier que la syntaxe du langage est respectée et de générer alors
l'équivalent du programme source en langage machine : on obtient alors sur disque le fichier objet.

 Ce fichier objet est ensuite soumis à l'éditeur de liens dont le rôle est de résoudre les références
externes, c'est-à-dire par exemple, d'associer les appels système inclus dans le programme à leur
adresse dans le système. L'éditeur de liens produit sur disque le fichier exécutable.

 Lorsque l'utilisateur demande l'exécution de son programme, le fichier exécutable est alors monté en
mémoire centrale : c’est l'étape de chargement. Le système alloue de la place mémoire pour placer le
code et les données du programme.
Introduction aux systèmes d'exploitation

Notion de processus : L'exécution d'un programme

Mémoire
Processus 1
Code
Données
PCB
Processus 2
Code
Données
PCB
Introduction aux systèmes d'exploitation

Notion de processus : L'exécution d'un programme

CPU
Mémoire

CO
103 100
RI 101
Disque
Load imm R1 20 102 load imm R1 20
ri 103 add imm R1 5
104 store dir R1 15
105

UAL
RSP UE

PSW

Bus externe
Introduction aux systèmes d'exploitation

Notion de processus : L'exécution d'un programme

 Le programme à exécuter est placé en mémoire centrale à partir de l'emplacement d'adresse 102.

 Le processeur a commencé l'exécution du programme : la première instruction de celui-ci a été chargée

dans le Registre Instruction (RI), le Compteur Ordinal (CO) contient l'adresse de la prochaine instruction à
exécuter soit 103.

 Lorsque l'instruction courante aura été exécutée, le processeur chargera dans le registre RI l'instruction
pointée par le CO, soit add Imm R1 5 et le compteur ordinal prendra la valeur 104.

 L'exécution de l'instruction add Imm R1 5 va modifier le contenu du registre PSW (Registre de Contrôle)
puisque c’est une instruction arithmétique : les flags de signe, de nullité etc... sont mis à jour.

 On voit donc qu'à chaque étape d'exécution du programme, le contenu des registres du compteur ordinal
évolue. De même le contenu de la mémoire centrale peut être modifié : écriture, lecture dans la pile (Push,
Pop), modification des données par une instruction Store.
Introduction aux systèmes d'exploitation

Notion de processus : L'exécution d'un programme

 On appelle processus l'image de l'état du processeur et de la mémoire au cours de l'exécution d'un
programme.

 Le programme est statique et le processus représente la dynamique de son exécution.

 Lors de l'étape de chargement, le système alloue de la place mémoire pour placer le code et les données du
programme et crée la pile d'exécution RSP de ce qui est en train de devenir un processus.

 Il alloue alors une structure de donnée descriptive du processus destinée à regrouper toutes les informations
du contexte du processus : le bloc de contrôle du processus.

 Le processus est alors créé. Il est prêt à s'exécuter.

Introduction aux systèmes d'exploitation

Notion de processus : Le processus

Définition : Processus

 Un processus est un programme en cours d'exécution auquel est associé un environnement processeur
(CO, PSW, RSP, registres généraux) et un environnement mémoire appelés contexte du processus.

 Un processus est l'instance dynamique d'un programme et incarne le fil d'exécution de celui-ci dans un
espace d'adressage protégé (objets propres : ensemble des instructions et données accessibles)

 Un programme réentrant est un programme pour lequel il peut exister plusieurs processus en même temps
Introduction aux systèmes d'exploitation

Notion de processus : Le processus

Système multiprocessus – état des processus

Réveil

En attente
du
processeur
Prêt

Débloca Electio
ge n

En
Bloqu exécution
Elu
é
En attente
de Blocag
ressources e

Fin
Introduction aux systèmes d'exploitation

Notion de processus : Le processus

Les états du processus : Lors de son exécution, un processus est caractérisé par un état :

 Lorsque le processus obtient le processeur et s'exécute, il est dans l'état élu. L'état élu est l'état d'exécution
du processus.

 Lors de cette exécution, le processus peut demander à accéder à une ressource (réalisation d’une
entrée/sortie, accès à une variable protégée) qui n'est pas immédiatement disponible : le processus ne peut
pas poursuivre son exécution tant qu'il n'a pas obtenu la ressource (par exemple, le processus doit attendre
la fin de l'entrée/sortie qui lui délivre les données sur lesquelles il réalise les calculs suivants dans son
code) : le processus quitte alors le processeur et passe dans l'état bloqué. L'état bloqué est l'état d'attente
d'une ressource autre que le processeur.

 Lorsque le processus a enfin obtenu la ressource qu'il attendait, celui-ci peut potentiellement reprendre son
exécution. Cependant, nous nous sommes placés dans le cadre de systèmes multiprogrammés, c'est-à-dire
qu'il y a plusieurs programmes en mémoire centrale et donc plusieurs processus.. Lorsque le processus est
passé dans l'état bloqué, le processeur a été alloué à un autre processus. Le processeur n'est donc pas
forcément libre. Le processus passe alors dans l'état prêt. L'état Prêt est l'état d'attente du processeur.

 Le passage de l'état prêt vers l'état élu constitue l'opération d'élection. Le passage de l'état élu vers l'état
bloqué est l'opération de blocage. Le passage de l'état bloqué vers l'état prêt est l'opération de déblocage.
Introduction aux systèmes d'exploitation

Notion de processus : Le processus

Etat des processus simplifié

Mode Actif
Utilisat Utilisat
eur eur

Actif
Mode Nouvea Prêt Noyau Zombi
Noyau u
en
Mémoir
e Endorm
i

Mode Endorm
Prêt
Swappe i
Swappe
Swappe
Introduction aux systèmes d'exploitation

Notion de processus : Le processus

Exemple sous Unix

La figure ci-dessous présente le graphe d'états simplifié pour un processus Unix.

 Un processus évolue entre trois modes au cours de son exécution :

 le mode utilisateur qui est le mode normal d'exécution,
 le mode noyau en mémoire qui est le mode dans lequel se trouve un processus prêt ou bloqué
(endormi)
 le mode swappé qui est le mode dans lequel se trouve un processus bloqué (endormi) déchargé de la
mémoire centrale.

 En effet, le système Unix décharge de la mémoire centrale les processus endormis depuis trop longtemps
(ils sont alors dans l'état Endormi swappé). Ces processus réintègrent la mémoire centrale lorsqu'ils
redeviennent prêts (transition de l'état prêt swappé vers l'état prêt).

 Un processus qui se termine passe dans un état dit zombi. Il y reste tant que son PCB n'est pas entièrement
démantelé par le système.
Introduction aux systèmes d'exploitation

Notion de processus : Le processus

Le bloc de contrôle du processus (PCB)

Identificateur processus Etat du processeur

Contexte du reprise
Compteur instruction (registres, pointeurs,
piles, …)

Pointeurs sur files Informations mémoire

d’attente et priorité (tables,
(ordonnancement) pages/segments)

Informations de
comptabilisation et sur
les E/S, périphériques,
fichiers ouvert
PCB {
PID: 1234
PPID: 5678
State: Running Priority: 7
Registers: { SchedulingPolicy: "Round Robin"
PC: 0x004000F0, Resources: {
IR: 0x0A1B2C3D, FilesOpened: ["file1.txt",
Flags: 0x00000001 "file2.log"],
} FileDescriptors: [3, 5, 7],
StackPointer: 0x7FFF0000 Devices: ["Printer", "Disk Drive"]
MemoryInfo: { }
BaseAddress: 0x00400000, TimeInfo: {
MemoryLimit: 10 MB, TimeRemaining: 10 ms,
PageTableBase: 0x00500000 TotalExecutionTime: 50 ms
} }
IOWaiting: True
WaitingDevice: "Network Interface"
Threads: ["Thread1", "Thread2",
"Thread3"]
}
Introduction aux systèmes d'exploitation

Notion de processus : Le processus

Le bloc de contrôle du processus (PCB)

Le bloc de contrôle d'un processus (PCB) contient les informations suivantes :

 un identificateur unique du processus (un entier) : le PID

 l'état courant du processus (élu, prêt, bloqué)

 le contexte processeur du processus : la valeur du CO, la valeur des autres registres du processeur

 le contexte mémoire : ce sont des informations mémoire qui permettent de trouver le code et les données du
processus en mémoire centrale

 des informations diverses de comptabilisation pour les statistiques sur les performances système

 des informations liées à l' ordonnancement du processus. Le PCB permet la sauvegarde et la restauration
du contexte mémoire et du contexte processeur lors des opérations de commutations de contexte
Ordonnancement

Ordonnancement de processus: Notions

Système Multiprocesseur
P
élu
1 Disque
P
attente E/S
2
P
attente CPU
3
P
attente E/S
4
P P P
attente CPU
5 2 4
P
attente CPU P
6
1 UE

Mémoire CPU

Bus externe
Ordonnancement

Ordonnancement de processus: Qu'est-ce que l'ordonnancement de processus

 La figure schématise le fonctionnement d'une machine multiprocessus. Plusieurs processus sont présents
en mémoire centrale.

 P1 est élu et s'exécute sur le processeur. P2 et P4 sont dans l'état bloqué car ils attentent tous les deux une
fin d'entrée/sortie avec le disque.
 Les processus P3, P5 et P6 quant à eux sont dans l'état prêt : ils pourraient s'exécuter (ils ont à leur
disposition toutes les ressources nécessaires) mais ils ne le peuvent pas car le processeur est occupé par
P1.

 Lorsque P1 quittera le processeur parce qu'il a terminé son exécution, les trois processus P3, P5 et P6
auront tous les trois le droit d'obtenir le processeur. Mais le processeur ne peut être alloué qu'à un seul
processus à la fois :

 il faudra donc choisir entre P3, P5 et P6 : c'est le rôle de l' ordonnancement qui élira un des trois processus

Définition : Ordonnancement
La fonction d'ordonnancement gère le partage du processeur entre les différents processus en attente pour
s'exécuter, c'est-à-dire entre les différents processus qui sont dans l'état prêt. L'opération d'élection consiste à
allouer le processeur à un processus.
Ordonnancement

Ordonnancement de processus: Ordonnancement préemptif ou non préemptif

Réveil Système Multiprocesseur

Etats des Processus
En attente
du
processeur
Prêt

Débloca Préemption /
ge Réquisition

Electio
Bloqu n
Elu En
é exécution
En attente
de Blocag
ressources e

Fin
Ordonnancement

Ordonnancement de processus: Ordonnancement préemptif ou non préemptif

 La figure reprend le graphe d'états tel qu'il a été vu à la leçon précédente concernant les processus.

 Une transition a été cependant ajoutée entre l'état élu et l'état prêt : c'est la transition de préemption.

 La préemption correspond à une opération de réquisition du processeur, c'est-à-dire que le processeur est
retiré au processus élu alors que celui-ci dispose de toutes les ressources nécessaires à la poursuite de son
exécution. Cette réquisition porte le nom de préemption.

Définition : Préemption
Selon si l'opération de réquisition du processeur est autorisée ou non, l'ordonnancement sera qualifié
d'ordonnancement préemptif ou non préemptif :
 si l'ordonnancement est non préemptif, la transition de l'état élu vers l'état prêt est interdite : un processus
quitte le processeur si il a terminé son exécution ou si il se bloque.
 si l'ordonnancement est préemptif, la transition de l'état élu vers l'état prêt est autorisée : un processus quitte
le processeur si il a terminé son exécution , si il se bloque ou si le processeur est réquisitionné.
 Ordonnancement

Ordonnancement de processus: Les entités système responsables de la fonction d'ordonnancement

Système Multiprocesseur
Ordonnanceur et Répartiteur
Préempt Ordonnance
ion Réveil
ur
CP
U Elu Prêt

CP

PCB
PCB
PCB
PCB
PCB
Fin Répartite
U
ur
CP Classement selon une Débloca
U politique ge
d’ordonnancement

PCB
PCB
PCB
PCB
PCB
Blocage

Bloqué
Ordonnancement

Ordonnancement de processus: Les entités système responsables de la fonction d'ordonnancement

 Le système d'ordonnancement gère une file des processus (bloc de contrôle) prêts et une file des processus
bloqués. La file des processus prêts est classée selon une politique d'ordonnancement qui assure que le
processus en tête de file est le prochain processus à élire au regard de la politique mise en œuvre. Ce
classement est effectué par l' ordonnanceur et est réactualisé à chaque fois qu'un processus est préempté
ou qu'un processus est débloqué (ajout d'un nouvel élément prêt).

 C'est le répartiteur qui élit le processus en tête de file, c'est-à-dire qui lui alloue un processeur libre. La figure
montre le cas d’un système multiprocesseur ; le répartiteur doit alors choisir quel processeur allouer. Dans
un système monoprocesseur, cette question ne se pose évidemment pas et souvent alors, ordonnanceur et
répartiteur sont confondus.

 Une fois élu par le répartiteur, le processus s'exécute. S'il quitte le processeur, sur préemption, il réintègre la
file des processus prêts ; au contraire, s'il quitte le processeur sur un blocage, il intègre la file des processus
bloqués. Dans les deux cas, un nouveau processus est élu (la tête de file des processus prêts). Plus
précisément, la file d'attente des processus bloqués est souvent organisée en files multiniveaux, chaque
niveau correspondant à une attente d'un événement/ ressource particulier auquel peut être éventuellement
associé une priorité. Dans le cas où des événements se produisent simultanément, cette priorité sert alors à
déterminer quel événement doit être traité en premier.

Définition : Ordonnanceur
L'ordonnanceur est un programme système dont le rôle est d'allouer le processeur à un processus prêt.
Ordonnancement

Les politiques d'ordonnancement: Objectifs des politiques d'ordonnancement

diffèrent en fonction
du type de systèmes
• Le but est de maximiser le débit du processeur ; c'est-à-dire le
nombre moyen de processus traités par unité de temps.
Systèmes de
traitements par lots • maximiser le taux d'occupation du processeur, le rapport entre
le temps où le processeur est actif et le temps total. peut
Systèmes varier entre 0% et 100 %
interactifs • minimiser le temps de réponse des processus, la durée
séparant l'instant de soumission du processus au système de
la fin d'exécution du processus.
Systèmes temps
réel • Le but principal est d'assurer le respect des contraintes de
temps liées aux processus, permet de savoir si le processus a
été préempté ou non
Ordonnancement

Les politiques d'ordonnancement: Objectifs des politiques d'ordonnancement

Définition : Politique d'ordonnancement
La politique d'ordonnancement détermine le choix d'un processus à élire parmi tous ceux qui sont prêts.

Les buts de l' ordonnancement diffèrent en fonction du type de systèmes.

 Systèmes de traitements par lots. Le but est de maximiser le débit du processeur ; c'est-à-dire le nombre
moyen de processus traités par unité de temps.

 Systèmes interactifs.
 Les buts principaux de l'ordonnancement sont premièrement de maximiser le taux d'occupation du
processeur, c'est-à-dire le rapport entre le temps où le processeur est actif et le temps total. En théorie,
ce taux peut varier entre 0% et 100 % ; dans la pratique, on peut observer un taux d'occupation variant
entre 40 % et 95 %.
 Deuxièmement, on va chercher à minimiser le temps de réponse des processus, c'est-à-dire la durée
séparant l'instant de soumission du processus au système de la fin d'exécution du processus. Au mieux,
le temps de réponse peut être exactement égal au temps d'exécution du processus, lorsque le
processus a immédiatement été élu et s'est exécuté sans être préempté.

 Systèmes temps réel. Le but principal est d'assurer le respect des contraintes de temps liées aux processus.
Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Nous décrivons ci-dessous les politiques mises en œuvre dans des systèmes interactifs ou à traitements par
lots.

Politique d'ordonnancement "premier arrivé, premier servi" (FIFO). First Come First Serve (FCFS)

 C'est une politique à l'ancienneté, sans préemption/réquisition ; l'unité centrale est allouée selon l'ordre de
soumission des processus. Dans cette politique, des processus de faible temps d'exécution peuvent être
pénalisés parce qu'un processus de longue durée les précède dans la file.

Algorithme Premier Arrivé Premier Servie

FIFO sans réquisition

P1 P2 P3 Temps de Cycle
millisecondes
24 3 3 P3

Temps de Cycle P2

P1
Temps Moyen d’attente
(0 + 24 + 27) / 3
17 millisecondes 24 27 30
Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Le plus court travail d'abord

l'unité centrale est allouée au processus de plus petit temps d'exécution

minimiser le temps de réponse moyen pour l'ensemble des algorithmes

d'ordonnancement sans réquisition

pénalise les travaux longs

impose également d'estimer la durée des processus ce qu'on ne connaît

pas habituellement

une version avec réquisition de cette politique appelée "temps restant le

plus court d'abord« , le processus en exécution restitue le processeur
lorsqu'un nouveau processus de temps d'exécution inférieur à son temps
d'exécution restant devient prêt
Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Politique d'ordonnancement "plus court d'abord" Short Job First (SJF)

 Cette politique tente de remédier à l'inconvénient mentionné pour la politique précédente.

 Maintenant, l'unité centrale est allouée au processus de plus petit temps d'exécution.

 Cette politique est également une politique sans réquisition.

 Elle a la propriété de minimiser le temps de réponse moyen pour l'ensemble des algorithmes
d'ordonnancement sans réquisition.

 Elle pénalise les travaux longs.

 Elle impose également d'estimer la durée des processus ce qu'on ne connaît pas habituellement.

 Il existe une version avec réquisition de cette politique appelée "temps restant le plus court d'abord" : dans
ce cas, le processus en exécution restitue le processeur lorsqu'un nouveau processus de temps d'exécution
inférieur à son temps d'exécution restant devient prêt.
Exercice

Tâche T1 T2 T3 T4 T5 T6 T7
Durée 7 4 6 1 2 4 1
Date
0 0 1 1 1 2 2
d'arrivée
Priorité
2 3 1 2 3 1 2
(n)
 First Come First Serve (FCFS)
 Short First (SJF)

Temps Moyen d’attente?

Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Politique d'ordonnancement par tourniquet (Round Robin)

 On définit une tranche de temps appelée quantum qui peut varier de 10 ms à 100 ms. Chaque processus
présent dans la file des processus prêts acquiert le processeur à tour de rôle, et ce pour au maximum un
temps égal au quantum de temps. Si le processus a terminé son exécution avant la fin du quantum, il libère
le processeur et le processus suivant dans la file des processus prêts est élu. Si le processus n'a pas
terminé son exécution avant la fin du quantum, il perd le processeur et est réinséré en fin de file des
processus prêts. Cette politique du tourniquet est usuellement utilisée dans les systèmes en temps partagé.
Sa performance dépend largement de la taille du quantum. Un quantum trop grand augmente les temps de
réponse alors qu'un quantum trop petit multiplie les commutations de contexte jusqu'à les rendre non
négligeables.
Algorithme Tourniquet

Temps de Cycle
millisecondes
P3
P1 P2 P3 Quantum = 4
P2
20 7 3 P1
Temps de Cycle
4 8 11 15 18 22 26 30
Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Politique d'ordonnancement par priorités constantes

 Un niveau de priorité constant est affecté à chaque processus et à un instant donné, le processus élu est
toujours celui de plus forte priorité. Cet algorithme présente une version sans réquisition et une version avec
réquisition. Le défaut de cette politique est le risque de famine encouru par le processus de faible priorité.
Une solution à ce problème est de faire "vieillir" la priorité des processus en attente, c'est-à-dire d'augmenter
celle-ci en fonction du temps d'attente. La priorité des processus devient ainsi variable.
Algorithme Avec Priorités

Proces Priorit Tps Temps de Cycle

s é Exec millisecondes
P1 3 10
P2 1 1 P4

P3 3 5 P3
P4 2 3
P2

Temps Moyen d’attente P1

(0 + 1 + 4 + 14) / 4
4.75 millisecondes
Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Politique d'ordonnancement par files de priorités constantes multiniveaux avec ou sans extinction de
priorité

Priorité
Prêt Priorité
Arrivée n-1 Prêt
Arrivée n-1

n-2
n-2

Election
Election
n-3
. n-3
. .
. .
.
0
0
Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Politique d'ordonnancement par files de priorités constantes multiniveaux avec ou sans extinction de
priorité

 Les politiques présentées jusqu'à présent utilisent une seule file d'attente des processus prêts. On choisit ici
de définir plusieurs files de processus prêts, chaque file correspondant à un niveau de priorité ; on peut alors
avoir n files de priorités différentes variant de 0 à n-1.
 Dans une file donnée, tous les processus ont la même priorité et sont servis soit selon une politique à
l'ancienneté sans préemption, soit selon une politique de tourniquet. Le quantum peut être différent selon le
niveau de priorité de la file.
 L' ordonnanceur sert d'abord tous les processus de la file de priorité n, puis ceux de priorité n-1 dès que la
file de niveau n est vide et ainsi de suite...

 On peut définir deux variantes de l'algorithme, fonction de l'évolution de la priorité des processus :
 les priorités des processus sont constantes tout au long de leur exécution. A ce moment-là, un
processus en fin de quantum est toujours réinséré dans la même file d'attente, celle correspondant à
son niveau de priorité.
 les priorités des processus évoluent dynamiquement en fonction du temps de service dont a bénéficié le
processus. Ainsi un processus de priorité n, à la fin du quantum de la file n, si il n'a pas terminé son
exécution, n'est pas réinséré dans la file de priorité n, mais dans la file de priorité n-1. Et ainsi de suite...
On cherche ici à minimiser les risques de famine pour les processus de faible priorité en faisant petit à
petit baisser la priorité des processus de plus forte priorité.
Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Question : Soient trois processus A, B, C soumis dans cet ordre de temps d'exécution respectif 4, 2, 9.
Quelles propositions sont exactes ?
1) Avec une politique FIFO, l'ordre d'exécution est C, B puis A
2) Avec une politique Plus Court d'Abord, l'ordre d'exécution est B, A, puis C
3) Avec une politique par priorité fixe, l'ordre d'exécution est A, B, puis C

Question : Le processus A de priorité 5 s'exécute. Le processus B de priorité 7 se réveille. Quelles sont

les propositions justes ?
4) B interrompt l'exécution de A car B est plus prioritaire et l'ordonnancement est préemptif
5) A continue son exécution car il est plus prioritaire et l'ordonnancement est préemptif
6) A continue son exécution car l'ordonnancement est non préemptif
7) B interrompt l'exécution de A car B est plus prioritaire et l'ordonnancement est non préemptif

Question : Un processus réentrant est :

8) Un programme exécutable lancé plusieurs fois en parallèle
9) Un processus qui a terminé son exécution
10)Un programme exécutable qui modifie son code.
Ordonnancement

Les politiques d'ordonnancement: Les principales politiques d'ordonnancement

Question : Soient trois processus A, B, C soumis dans cet ordre de temps d'exécution respectif 4, 2, 9.
Quelles propositions sont exactes ?
1) Avec une politique FIFO, l'ordre d'exécution est C, B puis A
2) Avec une politique Plus Court d'Abord, l'ordre d'exécution est B, A, puis C
3) Avec une politique par priorité fixe, l'ordre d'exécution est A, B, puis C
Réponse : Avec une politique Plus Court d'Abord, l'ordre d'exécution est B, A, puis C

Question : Le processus A de priorité 5 s'exécute. Le processus B de priorité 7 se réveille. Quelles sont

les propositions justes ?
4) B interrompt l'exécution de A car B est plus prioritaire et l'ordonnancement est préemptif
5) A continue son exécution car il est plus prioritaire et l'ordonnancement est préemptif
6) A continue son exécution car l'ordonnancement est non préemptif
7) B interrompt l'exécution de A car B est plus prioritaire et l'ordonnancement est non préemptif
Réponse : A continue son exécution car il est plus prioritaire et l'ordonnancement est préemptif ou A continue
son exécution car l' ordonnancement est non préemptif

Question : Un processus réentrant est :

8) Un programme exécutable lancé plusieurs fois en parallèle
9) Un processus qui a terminé son exécution
10)Un programme exécutable qui modifie son code.
Réponse : un programme exécutable lancé plusieurs fois en parallèle
Donner la définition des termes suivants :
• le taux d’utilisation du processeur ;
• le débit ;
• le temps de traitement moyen ;

Donner une formule reliant le temps de traitement, le temps d’attente et

le temps de calcul.
À partir des données du tableau des tâches suivant, déduire les temps
de traitement moyen dans le cas d’un algorithme sans réquisition et
d’un algorithme avec réquisition. On rappelle qu’à chaque tâche Ti sont
associés deux valeurs, ζi, indicatif de sa durée d’exécution et ti,
représentant sa date d’arrivée dans la file d’attente de l’état prêt.
ζi ti
T1 5 0
T2 1 2
1. Donner l’assignation réalisée par l’ordonnancement dans l’ordre
d’arrivée (FIFO).
2. Calculer le temps de traitement moyen pour cette assignation.
3. Proposer une autre assignation pour améliorer le temps de traitement
moyen.
4. Donner les inconvénients de l’algorithme d’ordonnancement FIFO
ζi ti
T1 30 0
T2 5 1
T3 2 2
Le principe de l’algorithme d’ordonnancement dans l’ordre inverse des
temps d’exécution (PCTE) est de choisir la tâche prête ayant le plus
court temps d’exécution (PCTE), sans tenir compte de l’ordre d’arrivée.
1. Donner l’assignation produite par l’algorithme PCTE.
2. Calculer le temps de traitement moyen.
3. Que se passe-t-il si l’assignation commence à l’instant 5 ? Justifier
votre réponse.
ζi ti
T1 10 0
T2 5 2
T3 15 3
T4 3 4
D’après le tableau des tâches ci-dessous, donnez l’assignation produite
par l’algorithme plus court temps d’exécution restant (PCTER) avec un
quantum q=1 u.t.

ζi ti
T1 8 0
T2 5 2
T3 5 3
T4 2 4
Soit le tableau des tâches ci-dessous.
1. En utilisant l’algorithme Round Robin, calculer le temps de traitement
moyen dans les 2 cas suivants :
a) quantum = 1 u.t
b) quantum = 10 u.t
2. Déduire l’influence qu’a la valeur du quantum sur les performances
de l’algorithme.

ζi ti
T1 30 0
T2 5 1
T3 2 2
1) On désire exécuter ces tâches en utilisant différents algorithmes
d’ordonnancement. Pour cela, on vous demande de donner les
diagrammes de Gantt correspondants aux algorithmes suivants :
a) First In Fist Out (FIFO).
b) Short Job First (SJF).
c) Priorité avec un quantum égale à 2 secondes (q=2 u.t.).
d) Round-Robin avec un quantum égale à 3 secondes (q=3 u.t.).
2) Calculer pour chaque algorithme, le temps de traitement moyen.
3) Quel est l’algorithme optimal et pourquoi ?

ζi ti Priorit
é
T1 5 0 3
T2 4 0 1
T3 3 2 2
T4 6 12 3