Solution du TD4 (deuxième partie)

Exo 01

1) FIFO L'exécution se fait selon l ordre d'arrivée des processus

T1 T2 T3 T4 T5 T6 T7

0 1 2 7 11 17 18 20 24 25

T1
T2 T3 T6
T4 T7
T5

𝑡𝑚 = ((7 − 0) + (11 − 0) + (17 − 1) + (18 − 1) + (20 − 1) + (24 − 2) + (25 − 2))⁄7 = 16,42

2)PCTE

A un moment donné, si plusieurs processus demandent la CPU, celui qui possède le temps d'exécution le
plus court est élu.

Au moment 0, la file d'attente ne contient que T2. Celui-ci est donc lancé sans appliquer la stratégie. Au
moment 4 T2 se termine et tout les autres processus sont présents dans la file. A partir de la, la stratégir
d'ordonnancement est appliquée aux processus.

T2 T4 T7 T5 T6 T3 T1

0 1 2 4 5 6 8 12 18 25

T1 T3 T6
T2 T4 T7
T5

𝑡𝑚 = 10,14

3)PCTER

A chaque fois qu'un processus demande la CPU, l'ordonnanceur compare son temps d'exécution avec le
temps d'exécution restant du processus en cours de traitement. Si le processus qui demande la CPU possède
le temps le plus court, il provoque une interruption et prends possession de la CPU. Dans le cas contraire, le
processus en cours de traitement poursuit son exécution.

1
 T2 T4 T7 T5 T2 T6 T3 T1

0 1 2 3 5 8 12 18 25
T6
T1 T3 T7
T2 T4
T5

Interruption

Au moment 0, nous avons dans la file d'attente T1 et T2 uniquement. Le processus qui possède le temps
d'exécution le plus court est alors élu (T2).

Au moment 1, T3, T4 et T5 arrivent et demandent la CPU. L'ordonnanceur compare le temps restant de T2

(3 u) et le temps d'exécution de T3, T4 et T5 (6, 1 et 2 respectivement). L'ordonnanceur élit alors T4 qui
possède le plus court temps d'exécution et provoque une interruption de T2.

Au moment 2, T4 se termine et T6 et T7 arrive dans la file d'attente. A partir de ce moment tous les autres
processus sont dans la file. Aucune interruption ne pourra alors se produire au delà du moment 2. A partir de
la, la stratégie PCTER agit d'une manière similaire que PCTE.

𝑡𝑚 = 9,43

4)Tourniquet (quantum=1)

T1 T2 T3 T4 T5 T1 T6 T7 T2 T3 T5 T1 T6 T2 T3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T6
T3 T7
T1
T4
T2
T5

T1 T6 T2 T3 T1 T6 T3 T1 T3 T1
15 16 17 18 19 20 21 22 23 24 25

Contenu de la file d'attente:

t=0 T2 T1 On attribue le quantum à la tête de la file (T1).

T1 termine avec un quantum au moment 1. Il demande
de nouveau la CPU pour poursuivre son exécution. Il
est inséré derrière T3, T4 et T5 qui viennent d'arriver.
Les processus qui arrivent s'ins1ere toujours en
premiers que ceux que celui qui provient de la CPU.

t=1 T1 T5 T4 T3 T2 T2 est élu

2
 T2 termine avec un quantum au moment 2. Il demande
de nouveau la CPU pour poursuivre son exécution. Il
est inséré derrière T6 et T7 qui viennent d'arriver.

t=2 T2 T7 T6 T1 T5 T4 T3 T3 est élu

T3

A parti du moment 2, aucun autre processus n'arrive dans la file d'attente. On garde alors cette disposition
pour attribuer le quantum de la tête de la file jusqu'à la queue. Quand une tâche termine son exécution, elle
est supprimée de la file et n'affecte pas la position des autres processus.

𝑡𝑚 = 14,86

Exercice 02

On construit la table des priorités qui renvoie la priorité de chaque tâche à un moment donné pour
sélectionner le prochaine tâche à élire (On applique la loi donné dans l'exercice).

Tâche T1 T2 T3 T4 T5 T6 T7
Tempss
0 1 1

1 1/2+1 1 1 1 1

2 1/2+1 1/2+1 1 1 1 1 1

3 1/2+1 1/2+1 1/2+1 1 1 1 1

4 1/2+1 1/2+1 1/2+1 ------ 1 1 1

5 1/2+1 1/2+1 1/2+1 ----- 1/2+1 1 1

6 1/2+1 1/2+1 1/2+1 ----- 1/2+1 1/2+1 1

7 1/2+1 1/2+1 1/2+1 ------ 1/2+1 1/2+1 ------

8 2 1/2+1 1/2+1 ------ 1/2+1 1/2+1 -------

9 2 2 1/2+1 -------- 1/2+1 1/2+1 --------

3
 T1 T2 T3 T4 T5 T6 T7 T1 T2 T3 T5 T6 T1 T2 T3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T3 T6
T1
T4 T7
T2
T5

T6 T1 T2 T3 T6 T1 T3 T1 T3 T1
15 16 17 18 19 20 21 22 23 24 25

Au moment 0: T1 et T2 arrivent. On leur calcule leur priorité. Comme il n'ont passé aucun moment dans la
CPU, leur priorité est égale à la priorité de base qui est fixé à 1 dans l'exercice. Comme l'ordre exacte
d'arrivée n'est pas connu, on choisit soit T1 soit T2 pour commencer le traitement.

Au moment 1: T1 a déjà consommé une unité de temps dans la CPU. En appliquant la règle donné dans
l'exercice, sa priorité est égale à 1/2+1. Comme T2 n'a pas encore commencé son exécution, il garde sa
priorité de base (1). Au même moment T3, T4 et T5 arrivent. Une priorité de base leur est également
affectée. T2, T3, T4 et T5 ont tous la priorité la plus basse. Ils sont alors départagé par FIFO. Comme T2 est
le premier à arriver, il est élu.

Au moment 2: La priorité de T2 passe à 1/2+1 puisqu'il a consommé une unité de temps dans la CPU. P6 et
P7 arrivent avec une priorité de base (1). T3, T4, T5, T6 et T7 ont donc la priorité la plus basse. On les
départagés par FIFO. T3, T4 et T5 s'exécutent alors avant T6 et T7. CommeT3 T4 et T5 sont arrivé au
même moment, on peut choisir l'un d'eux pour l'exécution. On suppose qu'on commence par T3, ensuite T4
et enfin T5 (selon l'ordre croissant des indices).

Au moment 3: T3 se termine et T4 est élu en suivant le même principe

Au moment 4: La priorité de T4 passe à 1/2+1 et T5 est élu en suivant le même principe

Au moment 5: La priorité de T5 passe à 1/2+1 et T6 est élu en suivant le même principe (T6 et T7 ont la
valeur de priorité la plus basse)

Au moment 6: La priorité de T6 passe à 1/2+1 et T7 est élu en suivant le même principe.

Au moment 7: T7 se termine. Tous les processus ont alors la même priorité. Ils ont alors départagés par
FIFO. Selon l'ordre établi, on revient au lancement de T1.

Au moment 8: T1 termine avec une unité. Sa priorité passe à 2 et T2 et élu.

Au moment 9: T2 termine avec une unité. Sa priorité passe à 2 et T3 et élu.

L'exécution de poursuit selon le même ordre jusqu'au moment 25.

Exo 03

Chacune des trois file est géré par un tourniquet (temps partagé avec un quantum égal à 1). Le numéro d'une
file correspond à sa priorité. Le numéro le plus haut (3) correspond à la plus grande priorité. La file d'attente
la plus prioritaire qui contient des processus est active tandis que les autres attendent leur tour.
4
 1) Oui un processus peut être victime de la famine s'il y a constamment une file de niveau supérieur à celle
de ce processus qui est active. Dans ce cas, la file de niveau inférieure à laquelle appartient ce processus
n'est alors jamais active.

2)

T2 T5 T2 T5 T2 T2 T1 T4 T7 T1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

File 3 est File 3 est vide. File 2 est vide.

active File 2 est active. File 1 est active.

T3 T6 T3 T6 T3 T6 T3 T6 T3
15 16 17 18 19 20 21 22 23 24 25

Moment 0: T2

T2 s'exécute car il se trouve dans la file la plus prioritaire. File3

T1
File2

File1
Moment 1:

T2 a avec un quantum. T5 arrive et est inséré dans la file 3. T2 est inséré derrière T2 T5
T5 puisqu'il n; a pas encore terminé son exécution. T 5 est alors sélectionné. File3
Entre temps, T4 et T3 arrivent et sont insérés dans leurs files respectives T4 T1
File2
T3

Moment 2: File1

La file 3 est toujours active puisqu'elle contient encore des processus. T5 a terminé
avec un quantum . Il est inséré dans la file 3 derrière T2 une nouvelle fois puisqu'il T5 T2
n'a pas encore terminé ses traitement. T2 est élu. File3

A partir du moment 2, aucun autre processus n'arrive. On garde l'ordre d'exécution T7 T4 T1

montré sur les files dans le schéma. La file 3 est active jusqu'à la terminaison de
File2
T5 et T2. Ensuite, la file 2 est activée jusqu'à la terminaison de T1, T4 et T7.
Ensuite la file 1 est activé jusqu`à la terminaison de T3 et T6 comme indiqué dans T6 T3
le diagramme de Gantt en haut.
File1