LES ALGORITHMES

D'ORDONNANCEMENT

UVCI
 Table des
matières
Objectifs 3

Introduction 4

I - Ordonnancement FCFS (first come first Served) 5

1. Principe ........................................................................................................................................................... 5

2. Application de l'algorithme FCFS .................................................................................................................. 5

II - Exercice 8

III - L'algorithme d'ordonnancement SJF (short job first) 9

1. Principe ........................................................................................................................................................... 9

2. Application ..................................................................................................................................................... 9

IV - Exercice 14

V - Algorithme d'ordonnancement basé sur des priorités 16

1. Principe ......................................................................................................................................................... 16

2. Application ................................................................................................................................................... 16

VI - Exercice 21

VII - Algorithme de tourniquet ou d'ordonnancement circulaire (round robin) 23

1. Principe ......................................................................................................................................................... 23

2. Application ................................................................................................................................................... 23
2.1. Correction .................................................................................................................................................................................. 24

VIII - Exercice 26
 Objectifs

À la fin de cette leçon, vous serez capable de :

Identifier et expliquer les algorithmes d'ordonnancement FCFS

Décrire les algorithmes d'ordonnancement SJF
Identifier les algorithmes d'ordonnancement basés sur des priorités
Identifier et expliquer l'algorithme d'ordonnancement tourniquet

3
 Introduction

Dans un système multitâche, la ressource la plus importante d'une machine est le processeur. Cette ressource est
allouée à un et un processus sélectionné parmi un ensemble des processus éligibles. Par conséquent, il convient à
bien gérer ce dernier afin de le rendre plus productif. Dans cette leçon, nous présenterons quelques algorithmes
d'ordonnancement utilisés par les systèmes d'exploitation pour coordonner l'exécution des programmes par le
processeur.

4
 Ordonnancement FCFS (first come first Served)

Ordonnancement FCFS
(first come first Served) I

1. Principe
On l'appelle aussi ordonnancement FIFO (First In, First Out) ; les processus sont rangés dans la file d'attente
des processus prêts selon leur ordre d'arriver. Les règles régissant cet ordonnancement sont :

1. Quand un processus est prêt à s'exécuter, il est mis en queue de la file d'attente des processus prêts.
2. Quand le processeur devient libre, il est alloué au processus se trouvant en tête de file d'attente des
processus prêts.
3. Le processus élu relâche le processeur s'il se termine ou s'il demande une entrée sortie.

Cet algorithme est classe dans la catégorie des ordonnanceurs non préemptifs ou sans réquisitions. Il n'est pas
adapter à un système partagé car dans un tel système chaque utilisateur obtient le processeur à des intervalles
réguliers.

2. Application de l'algorithme FCFS

Énoncé

Considérons 5 travaux A, B, C, D, E dont le temps d'exécution respectifs et leur arrivage respectifs sont
données dans le tableau suivant :

Processus Temps d’exécution Temps d'arrivée

A 3 0

B 6 1

C 4 4

D 2 6

E0 1 7

En utilisant un algorithme d'ordonnancement FCFS (Fifo) donnez :

- le diagramme de Gantt,

- le temps de séjour de chaque processus,

- le temps moyen de séjour des processus,

5
 Application de l'algorithme FCFS

- le temps d'attente de chaque processus,

- le temps moyen d'attente des processus

Correction

Dans cet exercice, l'algorithme utilisé est le FCFS, ce qui veut dire que :

o lorsqu'on doit choisir un processus pour s'exécuter, c'est le processus en tête de la file d'attente des processus
prêts qui est choisi pour être exécuté par le processeur.

o l'algorithme FCFS est sans réquisition, ce qui veut dire que lorsqu'un processus est en train de s'exécuter, tant
qu'il n'a pas fini de s'exécuter, on ne peut pas lui arracher le processeur pour donner à un autre processus.

- Le diagramme de Gantt des processus

Le diagramme de Gantt, donne la répartition temporelle de l'exécution des processus. Il permettre de

représenter le temps où débute l'exécution de chaque processus, et le temps au bout duquel chaque processus
fini de s'exécuter.

1. Le processus A arrive à TA=0, il est le premier arrivé, il est donc exécuté directement à t= 0
2. Le processus B arrive à TA= 1 unité de temps, pendant ce temps, le processus A est en train de
s'exécuter, donc B se met dans la file d'attente en attendant que son tour n'arrive. Le processus A a une
durée d'exécution de 3 unités de temps, donc il finit de s'exécuter à t=3.
3. A t=3 le processus A finit de s'exécuter, le processus B est le seul dans la file d'attente, il va alors
commencer à s'exécuter à partir de t=3. Vu que la durée d'exécution de B est 6, c'est au bout de t=9
unités de temps (9 = 6 + 3 unités de temps. En effet, B à commencer à partir de t= 3)
4. A TA= 4 le processus C arrive, pendant ce temps B est en train de s'exécuter, donc C se met dans la file
d'attente.
5. A TA= 6, le processus D arrive, pendant ce temps B est toujours en train de s'exécuter, donc D se met
dans la file d'attente après le processus C.
6. Le processus E, arrive à TA=7, pendant ce temps, B est toujours en train de s'exécuter, donc E se met
dans la file d'attente après le processus C.
7. A t=9 unités de temps, le processus B finit de s'exécuter, c'est le processus C en tête de la file d'attente
qui est prise pour s'exécuter. Le processus C a une durée d'exécution de 4 unités de temps, donc c'est à
t=13 unités de temps qu'il va finir de s'exécuter.
8. A t=13, le processus C se termine, c'est le processus D qui est en tête de la file d'attente, donc D
commence à s'exécuter à t=13 et finit de s'exécuter à t=15, vu que sa durée d'exécution est 2 unités de
temps.
9. A t=15 le processus E commence à s'exécuter et fini à t=16

Le diagramme de Gantt est donc le suivant :

- Temps de séjour de chaque processus

Pour obtenir le temps de séjour, on fait : TSi = temps fin exécution – temps d'arrivée

6
 Application de l'algorithme FCFS

Processus Temps de séjour

A 3-0=3

B 9-1= 8

C 13-4=9

D 15-6=9

E 16-7=9

- Temps moyen de séjour des processus :

TMS = (3+8+9+9+9) / 5= 7.6

- Temps d'attente de chaque processus

Pour obtenir le temps d'attente, on fait :

TAi = temps de séjour – temps exécution

Processus Temps d'attente

A 3-3=0

B 8-6=2

C 9-4=5

D 9-2=7

E 9-1=8

- Temps moyen d'attente des processus

TMA = 22/5 = 4.4

7
 Exercice

Exercice
II
Considérons 5 processus P1, P2, P3, P4, P5 dont leurs temps d'exécution respectifs et leurs temps
d'arrivée respectifs sont donnés dans le tableau suivant :

Processus durée d’exécution Temps d'arrivée Priorité

P1 7 0 1

P2 5 1 5

P3 2 3 7

P4 4 5 4

P5 3 6 9

Exercice
En utilisant un algorithme d'ordonnancement FCFS (Fifo), le temps de séjour moyen des processus est :

 10

 11.4

 11.2

 9

 10.4

Exercice
En utilisant un algorithme d'ordonnancement FCFS (Fifo), le temps d'attente moyen des processus est :

 7.2

 9.6

 7.3

 9.8

 5.6

8
 L'algorithme d'ordonnancement SJF (short job first)

L'algorithme
d'ordonnancement SJF III
(short job first)

1. Principe
SJF ou SRTF (Shortest Remaining Time first) (plus court temps d'exécution restant PCTER) choisit de façon
prioritaire les processus ayant le plus court temps d'exécution sans réellement tenir compte de leur date
d'arrivée.

Dans cet algorithme les différents processus sont rangés dans la file d'attente des processus prêts selon un ordre
croissant de leur temps d'exécution (cycle de calcul). Les règles régissant cet ordonnancement sont :

1. Quand un processus est prêt à s'exécuter, il est inséré dans la file d'attente des processus prêts à sa
position approprie.
2. Quand le processeur devient libre, il est assigné au processus se trouvant en tête de la file d'attente des
processus prêts (ce processus possède le plus petit cycle processeur.). Si deux processus ont la même
longueur de cycle, on applique dans ce cas l'algorithme FCFS
3. Si le système ne met pas en œuvre la réquisition, le processus élu relâche le processeur s'il se termine ou
s'il demande une entrée sortie. Dans le cas contraire, le processus élu perd le processeur également.
Quand un processus ayant un cycle d'exécution inférieur au temps processeur restant du processus élu,
vient d'entrer dans la file d'attente des prêts. Le processus élu dans ce cas sera mis dans la file d'attente
des éligibles, et le processeur est alloué au processus qui vient d'entrer.
Caractéristiques de l'Ordonnanceur

- Cet Ordonnanceur peut être avec ou sans réquisition

- Implémentation difficile, car il n'existe aucune manière pour connaître le cycle suivant du
processeur.

2. Application
Considérons 5 travaux A, B, C, D, E dont le temps d'exécution respectifs et leur arrivage respectifs sont
données dans le tableau suivant :

9
 Application

Processus Temps d’exécution Temps d'arrivée

A 3 0

B 6 1

C 4 4

D 2 6

E0 1 7

En utilisant un algorithme d'ordonnancement SJF en mode non préemptif donnez :

- le diagramme de Gantt,

- le temps de séjour de chaque processus,

- le temps moyen de séjour des processus,

- le temps d'attente de chaque processus,

- le temps moyen d'attente des processus

Correction

Dans cet exercice, l'algorithme utilisé est le SJF en mode sans préemption, ce qui veut dire que :

- lorsqu'on doit choisir un processus pour s'exécuter, c'est le processus qui a le plus petit temps d'exécution
dans la file d'attente des processus prêts qui est choisi pour être exécuté par le processeur.

- l'algorithme SJF est en mode non préemptif, ce qui veut dire que lorsqu'un processus est en train de
s'exécuter, tant qu'il n'a pas fini de s'exécuter, on ne peut pas lui arracher le processeur pour donner à un
autre processus.

Le diagramme de Gantt des processus :

1. Le processus A arrive à TA=0, il est le premier arrivé, il est donc exécuté directement à t= 0 et doit finir
de s'exécuter avant qu'on ne prenne un autre processus.
2. Le processus B arrive à TA= 1 unité de temps, pendant ce temps, le processus A est en train de
s'exécuter, donc B se met dans la file d'attente en attendant que son tour n'arrive. Le processus A a une
durée d'exécution de 3 unités de temps, donc il finit de s'exécuter à t=3.
3. A t=3 le processus A finit de s'exécuter, le processus B est le seul dans la file d'attente, il va alors
commencer à s'exécuter à partir de t=3. Vu que la durée d'exécution de B est 6, c'est au bout de t=9
unités de temps (9 = 6 + 3 unités de temps. En effet, B à commencer à partir de t= 3)
4. A T= 4 le processus C arrive, pendant ce temps B est en train de s'exécuter, donc C se met dans la file
d'attente.
5. A T= 6, le processus D arrive, pendant ce temps B est toujours en train de s'exécuter, donc D se met
dans la file d'attente après le processus C.
6. Le processus E, arrive à TA=7, pendant ce temps, B est toujours en train de s'exécuter, donc E se met
dans la file d'attente après le processus C.
7. A t=9 unités de temps, le processus B finit de s'exécuter, c'est le processus E qui a le plus petit temps
d'exécution dans la file d'attente qui est prise pour s'exécuter. Le processus E a une durée d'exécution de
1 unité de temps, donc c'est à t=10 unités de temps qu'il va finir de s'exécuter.
8.

10
 Application

8. A t=10, le processus E se termine, c'est le processus D qui a la plus petite durée dans la file d'attente,
donc D commence à s'exécuter à t=10 et finit de s'exécuter à t=12, vu que sa durée d'exécution est 2
unités de temps.
9. A t=12 le processus C commence à s'exécuter et fini à t=16

Le diagramme de Gantt est donc le suivant :

- Temps de séjour de chaque processus

Pour obtenir le temps de séjour, on fait : TSi = temps fin exécution – temps d'arrivée

Processus Temps de séjour

A 3-0=3

B 9-1= 8

C 16-4=12

D 12-6=6

E 10-7=3

- Temps moyen de séjour des processus :

TMS = (8+3+6+12)/5=29/5 = 5.8

- Temps d'attente de chaque processus

Pour obtenir le temps d'attente, on fait :

TAi = temps de séjour – temps exécution

Processus Temps d'attente

A 3-3=0

B 8-6=2

C 9-4=5

D 9-2=7

E 9-1=8

- Temps moyen d'attente des processus :

TAM=(0+2+8+4+2)/5= 16/5 = 3.2

SJF en mode préemptif

- En utilisant un algorithme d'ordonnancement SJF en mode préemptif (avec requisition) donnez :

- Le diagramme de Gantt,
- le temps de séjour de chaque processus,
- le temps moyen de séjour des processus,

11
 Application

- le temps d'attente de chaque processus,

- le temps moyen d'attente des processus

- Correction

Dans cet exercice, l'algorithme utilisé est le SJF en mode préemptif, ce qui veut dire que :

o lorsqu'on doit choisir un processus pour s'exécuter, c'est le processus qui a le plus petit temps d'exécution
dans la file d'attente des processus prêts qui est choisi pour être exécuté par le processeur.

o l'algorithme SJF est avec réquisition, ce qui veut dire que lorsqu'un processus est en train de s'exécuter, s'il n'a
plus la priorité, on peut lui arracher le processeur pour donner à un autre processus.

Le diagramme de Gantt des processus

- Le processus A arrive à TA=0, il est le premier arrivé, il est donc exécuté directement à t= 0.

- Le processus B arrive à TA= 1 unité de temps, pendant ce temps, le processus A est en train de s'exécuter
et lui reste 2 unités de temps d'exécution. Vu que B a 6 unités de temps d'exécution et 2<6, alors le
processus A poursuit son exécution jusqu'à finir à t=3.

- A t=3 le processus A finit de s'exécuter, le processus B est le seul dans la file d'attente, il va alors
commencer à s'exécuter à partir de t=3.

- A TA= 4 le processus C arrive, pendant ce temps B est en train de s'exécuter et il lui reste 5 unités de
temps d'exécution (5= 6-1, car B a déjà utiliser 1 unité de temps, vu qu'il a commencé à s'exécuter à
t=3), le processus C a 4 unités de temps d'exécution et 4<5, alors on arrache le processeur à B pour
donner à C (En effet, l'algorithme d'ordonnancement étant SJF, c'est le processus ayant la plus petite
durée d'exécution qui doit s'exécuter d'abord), et B se met dans la file d'attente, puis C commence à
s'exécuter à t=4.

- A TA= 6, le processus D arrive, pendant ce temps C est toujours en train de s'exécuter, et il lui reste 2
unités de temps d'exécution. D a une durée de 2 unités de temps, ce qui équivaut au temps de C restant,
donc C poursuit son exécution et D se met dans la file d'attente après le processus B.

- Le processus E arrive à TA=7 avec une durée d'exécution de 1 unité de temps, pendant ce temps, C est
toujours en train de s'exécuter et il lui reste aussi 1 unité de temps, donc E se met dans la file d'attente
après le processus D.

- A t=8 unités de temps, le processus C finit de s'exécuter, c'est le processus E qui a le plus petit temps
d'exécution dans la file d'attente qui est prise pour s'exécuter. Le processus E a une durée d'exécution de
1 unité de temps, donc c'est à t=9 unités de temps qu'il va finir de s'exécuter.

- A t=9, le processus E se termine, c'est le processus D qui a la plus petite durée dans la file d'attente, donc
D commence à s'exécuter à t=9 et finit de s'exécuter à t=11, vu que sa durée d'exécution est 2 unités de
temps.

- A t=11 le processus B commence à s'exécuter et finit à t=16 (En effet, il lui restait 5 unités de temps
d'exécution)

Le diagramme de Gantt est donc le suivant :

- Temps de séjour de chaque processus

12
 Application

Pour obtenir le temps de séjour, on fait : TSi = temps fin exécution – temps d'arrivée

Processus Temps de séjour

A 3-0=3

B 16-1= 15

C 8-4=4

D 11-6=5

E 9-7=2

- Temps moyen de séjour des processus :

TSM= (3+15+4+5+2)/5= 29/5 = 5.8

- Temps d'attente de chaque processus

Pour obtenir le temps d'attente, on fait :

TAi = temps de séjour – temps exécution

Processus Temps d'attente

A 3-3=0

B 15-6=9

C 4-4=0

D 5-2=3

E 2-1=1

- Temps moyen d'attente des processus :

TAM = (0+9+0+3+1)/5 = 13/5

13
 Exercice

Exercice
IV
Considérons 5 processus P1, P2, P3, P4, P5 dont leurs temps d'exécution respectifs et leurs temps
d'arrivée respectifs sont donnés dans le tableau suivant :

Processus durée d’exécution Temps d'arrivée Priorité

P1 7 0 1

P2 5 1 5

P3 2 3 7

P4 4 5 4

P5 3 6 9

Remarque : en cas de durées d'exécutions restante égales, le processus le premier venu est prioritaire

Exercice
En utilisant un algorithme d'ordonnancement SJF sans réquisition, le diagramme de Gantt est :

Exercice

14
 Exercice

En utilisant un algorithme d'ordonnancement SJF sans réquisition, le temps d'attente moyen des
processus est :

 7.2

 9.6

 6.1

 5.8

 4.2

Exercice
En utilisant un algorithme d'ordonnancement SJF avec réquisition, le diagramme de Gantt est :

Exercice
En utilisant un algorithme d'ordonnancement SJF avec réquisition, le temps d'attente moyen des
processus est :

 7.2

 4.8

 5.6

 5.6

 7.3

15
 Algorithme d'ordonnancement basé sur des priorités

Algorithme
d'ordonnancement basé V
sur des priorités

1. Principe
Dans cet algorithme les processus sont rangés dans la file d'attente des processus prêts par ordre décroissant de
priorité. L'ordonnancement dans ce cas est régi par les règles suivantes :

- Quand un processus est admis par le système il est insérer dans la file d'attente des processus prêts à sa
position appropries (selon la valeur de priorité)

- Quand le processeur devient libre il est alloue au processus se trouvant en tête de file d'attente des
processus prêts

- Dans un cas de non préemption un processus élu relâche le processeur que s'il se termine ou se bloque.

Remarque :

Si le système met en œuvre la réquisition, quand un processus de priorité supérieure à celle du processus élu
entre dans l'état prêt ; le processus élu sera mis dans la file d'attente des éligibles à la position approprie, et le
processeur est alloué au processus qui vient d'entrer.

Caractéristiques de l'Ordonnanceur

Les principales caractéristiques sont :

- Peut-être avec ou sans réquisition

- Un processus de priorité basse risque de ne pas être servi (problème de famine) d'où la nécessité d'ajuster
périodiquement les priorités des processus prêts. L'ajustement consiste à incrémenter graduellement la
priorité des processus de la file d'attente des éligibles (par exemple à chaque 15 mn on incrémente d'une
unité la priorité des processus prêts)

Remarque : la priorité adoptée est celle la plus élevée.

2. Application
Considérons 5 travaux A, B, C, D, E dont le temps d'exécution respectifs et leur arrivage respectifs sont
données dans le tableau suivant :

En utilisant un algorithme d'ordonnancement basé sur des priorités en mode non préemptif donnez :

Processus Temps d’exécution Temps d'arrivée Priorités

16
 Application

A 3 0 2

B 6 1 6

C 4 4 3

D 2 6 5

E 1 7 4

- le diagramme de Gantt,

- le temps de séjour de chaque processus,

- le temps moyen de séjour des processus,

- le temps d'attente de chaque processus,

- le temps moyen d'attente des processus

Correction

Dans cet exercice, l'algorithme utilisé est l'algorithme de priorités en mode non préemptif, ce qui veut dire que :

- lorsqu'on doit choisir un processus pour s'exécuter, c'est le processus qui a la plus grande priorité dans la
file d'attente des processus prêts qui est choisi pour être exécuté par le processeur.

- l'algorithme des priorités est en mode non préemptif, ce qui veut dire que lorsqu'un processus est en train
de s'exécuter, tant qu'il n'a pas fini de s'exécuter, on ne peut pas lui arracher le processeur pour donner à
un autre processus.

Le diagramme de Gantt des processus

1. Le processus A arrive à TA=0, il est le premier arrivé, il est donc exécuté directement à t= 0 et doit finir
de s'exécuter avant qu'on ne prenne un autre processus à t=3
2. Le processus B arrive à TA= 1 unité de temps, pendant ce temps, le processus A est en train de
s'exécuter, donc B se met dans la file d'attente en attendant que son tour n'arrive.
3. A t=3 le processus A finit de s'exécuter, le processus B est le seul dans la file d'attente, il va alors
commencer à s'exécuter à partir de t=3. Vu que la durée d'exécution de B est 6, c'est au bout de t=9
unités de temps (9 = 6 + 3 unités de temps. En effet, B à commencer à partir de t= 3)
4. A T= 4 le processus C arrive, pendant ce temps B est en train de s'exécuter, donc C se met dans la file
d'attente.
5. A T= 6, le processus D arrive, pendant ce temps B est toujours en train de s'exécuter, donc D se met
dans la file d'attente après le processus C.
6. Le processus E, arrive à TA=7, pendant ce temps, B est toujours en train de s'exécuter, donc E se met
dans la file d'attente après le processus C.
7. A t=9 unités de temps, le processus B finit de s'exécuter, c'est le processus D qui a la plus grande
priorité dans la file d'attente qui est prise pour s'exécuter. Le processus D a une durée d'exécution de 2
unités de temps, donc c'est à t=11 unités de temps qu'il va finir de s'exécuter.
8. A t=11, le processus D se termine, c'est le processus E qui a la plus grande priorité, donc E commence à
s'exécuter à t=11 et finit de s'exécuter à t=12, vu que sa durée d'exécution est 1 unité de temps.
9. A t=12 le processus C commence à s'exécuter et fini à t=16
Le diagramme de Gantt est donc le suivant :

17
 9.
Application

- Temps de séjour de chaque processus

Pour obtenir le temps de séjour, on fait : TSi = temps fin exécution – temps d'arrivée

Processus Temps de séjour

A 3-0=3

B 9-1= 8

C 16-4=12

D 11-6=5

E 12-7=5

- Temps moyen de séjour des processus :

TMS = (3+8+12+5+5)/5=33/5 = 6.6

- Temps d'attente de chaque processus

Pour obtenir le temps d'attente, on fait :

TAi = temps de séjour – temps exécution

Processus Temps d'attente

A 3-3=0

B 8-6=2

C 12-4=8

D 5-2=3

E 5-1=4

- Temps moyen d'attente des processus :

TAM= (0+2+8+3+4)/5= 17/5 =3.4

Priorité en mode avec réquisition

En utilisant un algorithme d'ordonnancement basé sur des priorités en mode préemptif (avec réquisition)
donnez :

- le diagramme de Gantt,

- le temps de séjour de chaque processus,

- le temps moyen de séjour des processus,

- le temps d'attente de chaque processus,

- le temps moyen d'attente des processus

Correction

18
 Application

Dans cet exercice, l'algorithme utilisé est l'algorithme basé sur des priorités en mode préemptif, ce qui veut dire
que :

- lorsqu'on doit choisir un processus pour s'exécuter, c'est le processus qui a la plus grande priorité dans la file
d'attente des processus prêts qui est choisi pour être exécuté par le processeur.

- l'algorithme basé sur des priorités est avec réquisition, ce qui veut dire que lorsqu'un processus est en train de
s'exécuter, s'il n'a plus la priorité, on peut lui arracher le processeur pour donner à un autre processus.

- Le diagramme de Gantt des processus

1. Le processus A arrive à t=0, il est le premier arrivé, il est donc exécuté directement à t= 0.
2. Le processus B arrive à t= 1 unité de temps, pendant ce temps, le processus A est en train de s'exécuter
et il lui reste 2 unités de temps. La priorité de B est supérieure à celle de A, on arrache alors le
processeur pour donner à B. Le processus A se met dans la file d'attente et B commence alors à
s'exécuter à t=1
3. A t= 4 le processus C arrive, pendant ce temps B est en train de s'exécuter. Le processus B a une priorité
supérieure à celle de C, donc il poursuit son exécution, et le processus C se met dans la file d'attente
après A.
4. A t= 6, le processus D arrive, pendant ce temps B est toujours en train de s'exécuter, et il lui reste 1
unité de temps d'exécution. D a une priorité inférieure à celle de B, donc B poursuit son exécution et D
se met dans la file d'attente après le processus C.
5. Le processus E arrive à t=7 avec une durée d'exécution de 1 unité de temps, pendant ce temps, B vient
de finir de s'exécuter. Le processus D a la plus grande priorité parmi tous les processus présents, donc D
commence à s'exécuter à t=7 et E se met dans la file d'attente après le processus C.
6. A t=7 unités de temps, le processus D commence à s'exécuter et finit a t=9. Le processus E a la plus
grande priorité donc il va être sélectionné pour s'exécuter.
7. A t=9, le processus E commence à s'exécuter et se termine à t=10. Le processus C a la plus grande
priorité dans la file d'attente des processus prêts, il va donc commencer à s'exécuter à t=10 et se termine
à t=14.
8. A t=14 le processus A poursuit son exécution et finit à t=16 (En effet, il lui restait 2 unités de temps
d'exécution)

Le diagramme de Gantt est donc le suivant :

- Temps de séjour de chaque processus

Pour obtenir le temps de séjour, on fait : TSi = temps fin exécution – temps d'arrivée

Processus Temps de séjour

A 16-0=16

B 7-1= 6

C 14-4=10

D 9-6=3

E 10-7=3

- Temps moyen de séjour des processus :

19
 Application

TSM= (16+6+10+3+3)/5= 38/5 = 7.6

- Temps d'attente de chaque processus

Pour obtenir le temps d'attente, on fait :

TAi = temps de séjour – temps exécution

Processus Temps d'attente

A 16-3=13

B 6-6=0

C 10-4=6

D 3-2=1

E 3-1=2

- Temps moyen d'attente des processus :

TAM = (0+0+6+1+2)/5 = 9/5 = 1.8

20
 Exercice

Exercice
VI
Considérons 5 processus P1, P2, P3, P4, P5 dont leurs temps d'exécution respectifs et leurs temps
d'arrivée respectifs sont donnés dans le tableau suivant :

Processus durée d’exécution Temps d'arrivée Priorité

P1 7 0 1

P2 5 1 5

P3 2 3 7

P4 4 5 4

P5 3 6 9

Exercice
En utilisant un algorithme d'ordonnancement avec priorité en mode non préemptif, le diagramme de
Gantt est :

 s

Exercice
En utilisant un algorithme d'ordonnancement avec priorité en mode non préemptif, le temps d'attente
moyen des processus est :

21
 Exercice

 7.3

 4.6

 5.6

 6.2

 5.8

Exercice
En utilisant un algorithme de scheduling avec priorité en mode préemptif, le diagramme de Gantt est :

Exercice
En utilisant un algorithme de scheduling avec priorité en mode préemptif, le temps d'attente moyen des
processus est :

 4.8

 7

 4.2

 9.6

 5.6

22
 Algorithme de tourniquet ou d'ordonnancement circulaire (round robin)

Algorithme de tourniquet
ou d'ordonnancement VII
circulaire (round robin)

1. Principe
Dans cet algorithme les processus sont rangés dans une file d'attente des éligibles, le processeur est alloué
successivement aux différents processus pour une tranche de temps fixe Q appelé Quantum.

Cet Ordonnancement est régit par les règles suivantes :

1. Un processus qui rentre dans l'état éligible est mis en queue de la file d'attente des prêts.
2. Si un processus élu se termine ou se bloque avant de consommer son quantum de temps, le processeur
est immédiatement alloué au prochain processus se trouvant en tête de la file d'attente des prêts.
3. Si le processus élu continue de s'exécuter au bout de son quantum, dans ce cas le processus sera
interrompu et mis en queue de la file d'attente des prêts et le processeur est réquisitionné pour être
réalloué au prochain processus en tête de cette même file d'attente.

Caractéristiques de l'Ordonnanceur

- Avec réquisition

- Adapté aux systèmes temps partagé.

- La stratégie du tourniquet garantit que tous processus sont servis au bout d'un temps fini. Son avantage est
d'éviter la famine. On dit qu'un processus est en famine lorsqu'il est prêt à être exécuté et se voit refuser
l'accès à une ressource (ici le processeur) pendant un temps indéterminé

- L'efficacité de cet ordonnanceur dépend principalement de la valeur du quantum Q:

- Le choix d'un Q assez petit augmente le nombre de commutation.

- Le choix d'un Q assez grand augmente le temps de réponse du système

2. Application
Considérons 5 travaux A, B, C, D, E dont le temps d'exécution respectifs et leur arrivage respectifs sont
données dans le tableau suivant :

En utilisant un algorithme d'ordonnancement circulaire donnez :

Processus Temps d’exécution Temps d'arrivée Priorités

A 3 0 2

23
 B 6 1 6

C 4 4 3

D 2 6 5

E 1 7 4

- le diagramme de Gantt,

- le temps de séjour de chaque processus,

- le temps moyen de séjour des processus,

- le temps d'attente de chaque processus,

- le temps moyen d'attente des processus

2.1. Correction
Dans cet exercice, l'algorithme utilisé est le tourniquet avec q=2, ce qui veut dire que :

o Lorsqu'un processus arrive, il se met dans la file d'attente, puis les processus sont choisir tour à tour pour
s'exécuter à chaque 2 unités de temps, jusqu'à ce que leur durée d'exécution soit atteinte. Si la durée d'exécution
d'un processus fini avant d'épuiser son quantum de temps, il est alors retiré du processeur, et un autre processus
est choisi pour s'exécuter.

- Le diagramme de Gantt des processus

1. Le processus A arrive à TA=0, il est le premier arrivé, il est donc exécuté directement à t= 0
2. Le processus B arrive à TA= 1 unité de temps, pendant ce temps, le processus A est en train de
s'exécuter alors le processus B se met dans la file d'attente.
3. A t=2 le processus A a épuiser son quantum de 2 unités de temps. Il est alors mis dans la file d'attente et
le processus B commence à s'exécuter.
4. A TA= 4 le processus C arrive et se met dans la file d'attente après le processus A, pendant ce temps B
vient d'épuiser son quantum de temps. Alors le processus B est mis en attente après le processus C, et le
processus A reprend son exécution.
5. A TA= 5 le processus A finit son exécution car sa durée est 3 unités de temps, et il avait déjà consommé
deux unités de temps. Le processus B en tête de la file d'attente est à nouveau choisi et poursuit son
exécution (B ayant déjà consommer 2 unités de temps lors de son premier quantum, il lui reste 4 unités
de temps d'exécution pour se terminer)
6. A TA= 6, le processus D arrive, pendant ce temps B est toujours en train de s'exécuter, alors le
processus D est mis dans la file d'attente après le processus C
7. Le processus E arrive à TA=7 avec une durée d'exécution de 1 unité de temps, il est mis en attente après
le processus D. Pendant ce temps, le processus B vient d'épuiser son quantum de temps, et il lui reste 2
unités de temps d'exécution. Le processus C est alors sélectionné pour s'exécuter et B se met dans la file
d'attente après le processus E.
8. A t=9 unités de temps, le processus C a épuisé son quantum de temps et il lui reste deux unités de temps
d'exécution, vu que C fait 4 unités de temps d'exécution. Le processus C est alors mis dans la file
d'attente après le processus B, et le processus D est choisi pour s'exécuter.
9. A t=11, le processus D épuise son quantum de temps et se termine car il fait 2 unités d'exécution, c'est
le processus E qui est en tête de la file d'attente, il est alors choisi pour s'exécuter.

10.

24
 10. A t=12 le processus E se termine car il fait 1 unité de temps. Le processus C est sélectionné pour
s'exécuter.
11. A t=14 le processus C finit son quantum de temps et se termine. Le processus B restant dans la file
d'attente est choisi pour s'exécuter
12. A t=16 le processus B finit de s'exécuter.
Le diagramme de Gantt est donc le suivant :

- Temps de séjour de chaque processus

Pour obtenir le temps de séjour, on fait : TSi = temps fin exécution – temps d'arrivée

Processus Temps de séjour

A 5-0=5

B 16-1= 15

C 14-4=10

D 11-6=5

E 12-7=5

- Temps moyen de séjour des processus :

TMS = (5+15+10+5+5)/5=40/5 = 8

- Temps d'attente de chaque processus

Pour obtenir le temps d'attente, on fait :

TAi = temps de séjour – temps exécution

Processus Temps d'attente

A 5-3=2

B 15-6=9

C 10-4=6

D 5-2=3

E 5-1=4

- Temps moyen d'attente des processus :

TAM = (2+9+6+3+4)/5= 24/5 =4.8

25
 Exercice

Exercice
VIII
Considérons 5 processus P1, P2, P3, P4, P5 dont leurs temps d'exécution respectifs et leurs temps
d'arrivée respectifs sont donnés dans le tableau suivant :

Processus durée d’exécution Temps d'arrivée Priorité

P1 7 0 1

P2 5 1 5

P3 2 3 7

P4 4 5 4

P5 3 6 9

Exercice
En utilisant l'algorithme de scheduling tourniquet de quantum q=2, le temps moyen

de séjour des processus est :

 10

 14

 11.4

 9.2

 10.6

Exercice
En utilisant l'algorithme de scheduling tourniquet de quantum q=2, le temps moyen

d'attente des processus est :

 9.6

 5.6

 9.8

 5.8

26
 Exercice

 10.1

27