1

ORDONNANCEMENT
(SCHEDULING)
Anissa Omrane
 Concepts de Base
2

 Les 1ers systèmes informatiques permettaient

l’exécution d’un seul programme à la fois.

 Le programme :
 Possédait le contrôle total du système
 Avait accès à toutes les ressources du système

 Les systèmes informatiques actuels permettent

de charger en mémoire plusieurs programmes
afin de les exécuter de manière concurrente .
 Concepts de Base
3

 Cette évolution nécessitait :

 Un contrôle plus ferme des programmes
 Plus de séparation entre les programmes

 Ces besoins ont aboutit au concept du

processus .
 Concepts de Base
4

 Il est nécessaire de pouvoir distinguer entre

deux programmes en mémoire centrale l’un en
cours d’exécution , l’autre en attente

 Tous les SE multiprogrammés modernes sont

bâtit autour du concept de processus . Ainsi, la
plus part des exigences d’un SE sont exprimées
par rapport au processus.
 Concepts de Base
5
 Terminologie
6

Programme Tâche Processus

Data Data
Séquence
d’instructions Séquence Séquence
d’instructions d’instructions

PCB
1. Programme = séquence d'instructions Contexte
2. Tâche = [1] + données d’exécution
3. Processus = [2] + contexte d'exécution (PCB)
 Notion de processus
7

 Définition : Un processus est un programme en cours

d'exécution auquel est associé un environnement
processeur (CO, PSW, registres généraux, …etc.) et un
environnement mémoire appelés contexte du processus

 un programme
 peut être exécuté plusieurs fois
 Peut se trouver dans plusieurs unités d’exécution en même
temps (il constitue un objet inerte)
 Notion de processus
8

 le processus doit connaître à chaque instant:

 le code du programme
 le pointeur d’instruction

 l’état de la pile

 les variables, …etc.

 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 processus est un programme (code)
en exécution (environnement)
 Notion de Ressource
9

 On appelle ressource, tout ce qui est nécessaire à

l’évolution d’un processus : processeur, mémoire,
périphérique, bus, …

 Un processus demande au SE l’accès à une ressource.

 Le SE alloue la ressource au processus.
 Une fois une ressource est allouée, le processus a le
droit de l’utiliser jusqu’à ce qu’il libère la ressource ou
que le SE reprenne la ressource (on parle dans ce cas,
de ressource préemptible, de préemption)
 Notion de Ressource
10

 Une ressource peut être en mode d’accès Partagée

ou en mode d’Accès exclusif

 Uneressource est en mode d’accès exclusif si elle ne

peut être allouée à plus d’un processus à la fois.

 Sinon, on parle de mode d’accès partagé

 Une ressource est Contrôlée par un état : Occupée, Libre

 Process Control Block (PCB)
11

 Un processus est représenté dans les

systèmes d’exploitation par une structure de
données particulière qui permet de le
décrire et de suivre son exécution durant son
cycle de vie.

 Cette structure est le

PCB (Process Control Block).
 Process Control Block (PCB)
12

 PCB contient en général les informations suivantes

Etat du processus
Process ID,
Valeur du compteur ordinal
Valeurs des Registes
Informations pour la gestion de la mémoire ( Tables de page, base/bound
des registres,…)
Information pour l’ordonnacement ( Priorité, etc.)
Etats de opérations d’E/S (Requêtes d’E/S en attente, E/S utilisés, etc.)
Liste des fichiers ouverts
Accounting Information
 Cycle de vie d’un Processus
13

3 Phases :
 Création

 Lancement d’un programme

 Création dynamique de processus : fork() Unix
 Vie du processus

 Existe dans le système

 Pris en charge par le système
 Fin du processus : Un processus peut se terminer :

 D’une manière ordinaire :Fin normale (dernière instruction)

 Ou interrompu d’une manière forcée : Fin anormale
 Cycle de vie d’un Processus
14

 Durant son cycle de vie le processus passe par une phase

d’execution durant laquelle le processus alterne des
phases d’execution CPU et des phases d’E/S

 Le déroulement d’un processus consiste en une suite de cycles

[exécution CPU + attente d’E/S]

Début Exécution Fin

calcul E/S calcul E/S calcul E/S calcul

Début Fin
 Etats de processus
15

 Au cours de son cycle de vie un processus se

voit changer d’état
 On note durant son cycle de vie Trois états
principaux
 Prêt: à être exécuté sur le processeur
 Actif: en cours d’exécution
 Bloqué: attendant une ressource (autre que le
CPU) ou la fin d’une opération d’E/S
 Etats de processus
16

 Le changement d’état d’un processus va dépendre de la

manière avec laquelle le processeur sera alloué aux
processus
 Monoprogrammation

Processus monopolise le processeur jusqu'à sa terminaison

 Multiprogrammation Utilisation CPU maximale
 Etats de processus
17

 Dans le cas monoprocesseur il y a un seul processus actif

à la fois, les autres doivent attendre le processeur
 Le système garde les PCBs des processus prêts dans une
liste de (Processus prêts) implémentée souvent en liste
chainée
 Quand un processus obtient le processeur il s’exécute
pendant un certain temps il peut se terminer ou passer
dans un état bloqué en attente sur une opération d’E/S
 Les processus bloqué sont dans une liste et en général il y
a une liste pour chaque dispositif d’E/S
 Etats de processus
18

 Dans la cas des systèmes multiprogrammé le

processeurs peut basculer de l’exécution d’un
processus en cours à l’exécution d’un autre
processus
 Ceci est possible par un mécanisme d’interruption
qui permet d’interrompre le processus en cours,
L’état (contexte) du processus en cours est
sauvegardé pour qu’il puisse être repris
ultérieurement
 Le contexte d’un processus
19

 Le contexte d’un processus est l’ensemble des

informations qui représente l’état d’exécution
d’un processus

 Le contexte décrit l’état courant d’un processus.

 La commutation de contexte est le mécanisme qui

permet au SE de remplacer un processus élu par un
autre processus.
 Notion d’Interruptions
20

 Signal technologique destiné au processeur afin

d’arrêter l’activité en cours :
(interrompre un Programme en cours d’exécution pour
Exécuter un autre programme et Revenir éventuellement
au programme interrompu)

 Pour ce faire plusieurs étapes sont nécessaires:

Sauvegarde contexte courant
 Chargement du contexte du nouveau

 Restaurer le contexte de l’ancien

 Notion d’Interruptions
21

 Une interruption peut aussi servir comme un

Avertissement pour le processeur de l’arrivée
d’un événement
 Fin d’impression
 Bourrage de papier
 Disquette pleine
 …
 Notion d’Interruptions
22

Causes possibles:
 Externes au programme en cours

 INTERRUPTION
 Touches du clavier : Pause, CTRL+ALT+DEL

 Internes au programme en cours

 DEROUTEMENT (TRAP)
 Instruction en cours : Division par 0
 Interruption Vs Déroutement
23

 Une Interruption est déclenchée par une cause extérieure

au déroulement de l’instruction en cours.

 Un déroutement (en anglais « Trap ») signale une

anomalie dans le déroulement d’une instruction, qui en
empêche l’exécution. Les origines peuvent être diverses
comme par exemple:

 Des données incorrectes (division par zéro)

 Exécution d’une opération interdite par un dispositif de
protection (violation de protection mémoire)
 Commutation de processus
24

Commutation entre processus se produit comme suit :

Exécution de A Exécution de A

Sauvegarder COA Sauvegarder COB

Sauvegarder Registres A Sauvegarder Registres B
Charger COB Exécution de B Charger COA
Charger Registres Charger RegistresB A
(Commutation de contexte) (Commutation de contexte)
 Ordonnancement
25

 L’ordonnancement est une fonction fondamentale

du système d’exploitation
 Quasiment toutes les ressources l’ordinateur sont
ordonnancées avant leur utilisation
 L’unité centrale (UC) est bien sûr l’une des
principales ressources de l’ordinateur
 Son ordonnancement est donc central dans la
conception du SE
 Ordonnancement
26

 Si on considère les systèmes batch il y a toujours

plusieurs processus soumis et qui ne peuvent être
exécuté immédiatement
 Ainsi les processus entrants sont spoolé (vers le

disque).
 L’ordonnacement à long-terme Permet la
sélection de processus depuis ce pool et de
charger les processus dans la mémoire pour
l’execution.
27
 Monoprogrammation
28

 Caractéristiques
 1 Seul programme chargé en MC
 Mémoire partagée entre l’OS et le programme
utilisateur

OS Programme utilisateur

 Avantage: Le Processeur est Alloué entièrement au

programme utilisateur et toutes les ressources de la machine
sont allouées à un seul programme
 Monoprogrammation
29

processus
Exécution

Programme A
début attente attente attente fin
E/S E/S E/S

Programme B
attente
début attente attente attente fin
E/S E/S E/S

0 temps
 Monoprogrammation
30

 Inconvénients
 Mauvaise utilisation des ressources :
 Espace mémoire inutilisé
 Taux d’occupation du processeur faible
 Opération de calcul : Processeur utilisé à plein rendement
 Opération d’entrée/sortie : Processeur non utilisé

 Temps d’attente des programmes

 TA(Pi) = j=1..(i-1) TE(Pj)
 Déséquilibre entre temps d’utilisation d’une machine et
temps d’attente
 P1 : 1 heure de calcul – 1mn E/S
 P2 : 2mn de calcul – 1s d’E/S ( Temps d’attente de P2: 61mn)
 Multiprogrammation
31

 Caractéristiques
 Chargement de plusieurs programmes utilisateurs en MC
 Contenu de la MC: OS + N programmes utilisateurs (N  1)

OS P1 P2 ... Pn

 simultanéité entre calcul et E/S

◼ P1 fait du calcul
◼ P2, …, Pn en attente du processeur
◼ P1 commence une E/S
◼ Canal prend en charge l’E/S (Processeur Libre)
◼ Processeur alloué à P2 (Commutation de contexte)
◼ …
 Multiprogrammation
32

Exécution avec multiprogrammation

Programme A
début attente attente attente fin
E/S E/S E/S

Programme B
début attente attente attente fin
E/S E/S E/S

0
temps

 Chargement de plusieurs programmes en MC : Gestion de l’espace

mémoire ( Allocation, Libération de l’espace)
 Simultanéité Calcul et E/S : Existence de canaux d’E/S Indispensables
pour permettre la simultanéité entre calcul et E/S
 Multiprogrammation
33

 Avantages : Meilleure gestion des ressources

 Espace mémoire
 Temps processeur
 Simultanéité entre UC et Canaux d’E/S
 Remarque : Libération processeur ( Fin programme courant ou E/S)

 Inconvénients: c’est un système complexe la ou il faut gérer la

mémoire, l’allocation du processeur et la simultanéité entre les calculs
et les E/S.
 Ce système ne satisfait pas forcément les utilisateurs. En effet le temps
d’attente devient plus long lorsque le calcul est dominant par rapport
aux E/S
 Exemple : P1: 1h (UC)+2mn (E/S) - P2: 1mn (UC)+2s (E/S)
Temps d’attente de P2 : 60mn
 Multiprogrammation
34

Mode batch
Le processus actif rend la main :
◼ lorsqu'il se termine
◼ lorsqu'il se bloque en attente d'une E/S

terminaison
élection Elu

création E/S
Prêt

fin d'E/S Bloqué

 Multiprogrammation
35

Temps partagé
Le processus actif rend la main :
◼ lorsqu'il se termine
◼ lorsqu'il se bloque en attente d'une E/S
◼ lorsqu'il a épuisé son quantum de temps

terminaison
élection Elu

création fin E/S

Prêt quantum

fin d'E/S Bloqué

 Ordonnanceur CPU
36

 Choisit parmi les processus prêts en mémoire

-> alloue le CPU à l’un d’eux

 Déclenchement d'une décision d’ordonnancement

1. changement d’état : “bloqué” -> “prêt”
2. changement d’état : “élu” -> “prêt”
3. changement d’état : “élu” -> “bloqué”
} préemptif
4. terminaison d’un processus
 Dispatcheur
37

Donne le contrôle du CPU au processus élu

1. Commutation de contexte
2. Passage en mode utilisateur
3. Relance à partir du PC

Latence du Dispatcheur
temps pris par le dispatcheur pour stopper un processus et en
(re)lancer un autre
 Critères d’Ordonnancement
38

 Utilisation maximale de la CPU

 Débit (Throughput)
Nombre de processus qui terminent leur exécution par unité de temps

 Temps de rotation (Turnaround time)

Temps {lancement -> terminaison} du processus (attentes incluses)

 Temps d’attente
Temps d’un processus dans la file d’attente des processus prêts
 Temps de réponse
Temps mis entre une requête émise et la première réponse
 Critères d’Optimisation
39

 Utilisation maximale du CPU

 Débit maximum
 Temps de rotation minimal
 Temps d’attente minimal
 Temps de réponse minimal
 Algorithmes d'ordonnancement
40

Objectif
Suivre les critères de manière optimale
En particulier :
guarantir l'équité (mais pas l'égalité !)
éviter les famines

Un grand nombre d'algorithmes

eg. FIFO, SJF, RR, EDF, RMS, ...
Choix du bon algorothme dépend de l'utilisation du système
(nombre de tâches, types, ...)
 Ordonnancement FIFO
Processus Date d’arrivée Temps CPU
41 P1 0 10
processus P2 0+e 6
P3 0+2e 2

Le diagramme de Gantt correspondant est :

P3

P2

P1

temps
0
10 16 18
P1 P2 P3
P2 P3
File

P3
 Ordonnancement FIFO (FCFS)
42

Processus Date Date Temps Temps

Arrivée Sortie Traitement Attente
P1 0 10 10-0=0 0
P2 0+e 16 16 10
P3 0+2e 18 18 16

Temps moyen de traitement =σ 𝑡𝑒𝑚𝑝𝑠 𝑑𝑒𝑠 𝑡𝑟𝑎𝑖𝑡𝑒𝑚𝑒𝑛𝑡𝑠

𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒𝑠 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑢𝑠
=(10+16+18)/3= 14,66

Temps moyen de d’attente = σ 𝑡𝑒𝑚𝑝𝑠 𝑑 ′ 𝑎𝑡𝑡𝑒𝑛𝑡𝑒

𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒𝑠 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑢𝑠

=(0+10+16)/3= 8,66
 Ordonnancement
Shortest Job First (SJF)
43

 Principe
Associer à chq processus son prochain tps d’utilisation CPU
Choisir le processus avec le temps le plus petit
 Deux schémas:
 Non préemptif
Dès que le CPU est donné à un processus, ce dernier ne peut être interrompu
avant la fin de son temps CPU
 Préemptif : Shortest-Remaining-Time-First (SRTF)
Si un nouveau processus arrive avec un temps CPU plus petit que le reste du
temps CPU du processus courant, on commute vers le nouveau processus.
 SJF est optimal
Il guarantit un temps d'attente moyen minimal.
 Ordonnancement SJF
Processus Date d’arrivée Temps CPU
44 P1 0 10
processus P2 0+e 6
P3 0+2e 2

Le diagramme de Gantt correspondant est :

P3

P2

P1

temps
0
2 8 18
P2 P1
P3
P3 P1
P2
P2
File
File

P1
P1
 Ordonnancement SJF
45

Processus Date Date Temps Temps

Arrivée Sortie Traitement Attente
P1 0 18 18 10
P2 0+e 8 8 2
P3 0+2e 2 2 0

Temps moyen de traitement =σ 𝑡𝑒𝑚𝑝𝑠 𝑑𝑒𝑠 𝑡𝑟𝑎𝑖𝑡𝑒𝑚𝑒𝑛𝑡𝑠

𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒𝑠 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑢𝑠
=(18+8+2)/3= 9,33

Temps moyen de d’attente = σ 𝑡𝑒𝑚𝑝𝑠 𝑑 ′ 𝑎𝑡𝑡𝑒𝑛𝑡𝑒

𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒𝑠 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑢𝑠

=(10+2+0)/3= 4
 Exemple de SJF Non-Préemptif
Processus Date d’arrivée Temps CPU
46
P1 0 7
processus
P2 2 4
P3 4 1
P4 5 4
P4

P3

P2

P1
temps
0
2 7 8 12 16
P2 P3 P3 P2
P2 P2 P4 P4
P4
File
 Exemple de SJF Préemptif (SRTF)
Processus Date d’arrivée Temps CPU
47
P1 0 7
processus P2 2 4
P3 4 1
P4 5 4
P4

P3

P2

P1
4 5 temps
0
2 7 11 16
P1 P2 P4
P1 P1 P1 P4
File

P2 P3
 FIFO
48

processus Processus Date d’arrivée Temps CPU

P1 0 5 calcul - 10 E/S - 5 calcul
P2 0+e 5 calcul - 5 E/S - 5 calcul
P3 0+2e 5 calcul
P3

P2 E/S

P1 E/S

temps
0 20 35 40
P1 P2 P3
P2 P3
File

P3
 Multiprogrammation simple
périphérique E/S indépendants
49

processus Processus Date d’arrivée Temps CPU

P1 0 5 calcul - 10 E/S - 5 calcul
P2 0+e 5 calcul - 5 E/S - 5 calcul
P3 0+2e 5 calcul
P3

P2 E/S

P1 E/S

temps
0 20 25
P2 P3
P1 P2
P3
P2
File

P3
50
51
52
 Ordonnancement avec Priorité
53

 Une priorité (nombre entier) est associée à chaque processus

 Le CPU est alloué au processus de plus grande priorité

 Préemptif
 Non préemptif
 SJF est un ordonnancement à priorité
La priorité correspond au temps CPU suivant

 Problème  Famine
Les processus de faible priorité peuvent ne jamais s’exécuter
 Solution  Vieillissement
Avec le temps, incrémenter la priorité des processus en attente
 Tourniquet/Round Robin (RR)
54

 Principe
Chq processus se voit allouer le CPU pour un temps limité
quantum : en général 10-100 millisecondes.
Lorsque son quantum est écoulé, le processus est remis en fin de la file d’attente des
processus prêts.

 Equité
Si n processus sont dans la file d’attente des processus prêts et si le quantum est q,
alors chaque processus reçoit 1/n du temps CPU en parties de q unités.
Aucun processus n'attend plus de (n-1)q.
 Performance
 q large : FIFO
 q petit : se rapproche du temps de commutation  fort surcoût
 Exemple de RR
avec Q = 20
55

Processus Temps CPU

P1 53
P2 17
P3 68
P4 24

 Le diagramme de Gantt est :

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

 Typiquement, une moyenne de temps de rotation plus grande que SJF, mais
un meilleur temps de réponse
 Quantum et Temps de Commutation de
56
Contexte
Exercice 2: Algorithme Round Robin

Soit le tableau de processus suivant :

Processus Temps d’exécution Temps d’arrivée
T1 9 0
T2 10 5
T3 7 10
Le temps de début d’exécution est t = 0.
1. Représenter graphiquement l’affectation des taches en utilisant Round Robin en supposant
que la valeur du Quantum est Qt=3.
2. Représenter graphiquement l’affectation des taches en utilisant Round Robin en supposant
que la valeur du Quantum est Qt=10. Que peut-on déduire ?
 File Multi-niveaux
60

 La file d’attente est partagée en files séparées:

premier plan/foreground (interactif)
arrière plan/background (batch)
 Chaque file a sa propre politique d’ordonnancement
 foreground – RR
 background – FCFS
 Un ordonnancement inter-files doit exister
 Ordonnancement à priorité fixe
ie. servir tous les processus de la file FG puis ceux de la file BG
=> Possibilité de famine.
 Time slice
chaque file obtient une partie du temps CPU qu’elle utilise pour ordonnancer ses
processus en attente
eg. 80% pour la file FG en RR et 20% pour la file BG en FCFS
 Ordonnancement à Files Multi-
61
niveaux
 Ordonnancement avec Files Multi-
niveaux à Retour
62

 Un processus peut changer de file

Implémentation du vieillissement
 Un ordonnanceur de files multi-niveaux à retour est défini selon
les paramètres suivants :
 Nombre de files
 Politique d’ordonnancement pour chaque file
 Méthode déterminant la promotion d’un processus vers une file d’attente
plus prioritaire
 Méthode déterminant la destitution d’un processus dans une file moins
prioritaire
 Méthode déterminant dans quelle file placer un nouveau processus
 Exemple de File Multi-niveaux à
Retour
63

Trois files
 Q0 – quantum de 8 millisecondes
 Q1 – quantum de 16 millisecondes
 Q2 – FCFS
Ordonnancement
 Un nouveau processus est placé dans Q0 au début
A sa première exécution, il reçoit 8 millisecondes.
S’il ne termine pas son exécution, il est déplacé dans Q1.
 Si un processus de la file Q1 est servi (16 msec) et ne se termine pas, il
est déplacé dans Q2.
 Files avec Multi-niveaux à Retour
64