Algorithmes de Scheduling
Politique « Premier Arrivé Premier Servi » (FCFS, First Come First Served- FIFO)
Consiste à servir le 1er processus arrivé dans le système.
C’est une politique non préemptive qui désavantage les processus courts.
Exemple:
Considérons cinq processus A, B, C, D et E dont les durées d’exécution et les dates d’arrivée respectives
sont données dans la table ci-après. Faites un schéma qui illustre leur exécution et calculez le temps de
rotation de chaque processus, le temps moyen de rotation, le temps d'attente et le temps moyen d'attente
en utilisant la politique FCFS.
Le temps de rotation pour chaque processus est obtenu en soustrayant le temps d'arrivée du processus du
temps de terminaison :
Temps de rotation(Le temps de séjour)= Date de fin d’Exe. – Temps d’arrivée.
Le temps d’attente est calculé en soustrayant le temps d’exécution du temps de rotation :
Temps d’attente = Temps de rotation – Durée d’Exe.
Le schéma d’exécution est : AAABBBBBBCCCCDDE
Remarque
Temps moyen d’attente élevé si de longs processus sont exécutés en premier
Politique du Job le Plus Court d’Abord (SJF, Shortest Job First)
Consiste à servir les processus courts avant les processus longs.
C’est une politique non préemptive, dont la mise en œuvre nécessite la connaissance préalable du temps
d’exécution des processus.
Exemple :
Reprenez l’exemple précédent avec la politique SJF.
Le schéma d’exécution : AAABBBBBBEDDCCCC
Politique du Job ayant le Plus Court Temps Restant (SRTF, Shortest Remaining Time First)
lorsqu’un processus est en cours d’exécution, et qu’un nouveau processus ayant un temps d’exécution
plus court que celui qui reste pour terminer l’exécution du processus en cours, ce processus est arrêté
(préempté), et le nouveau processus est exécuté.
Cette méthode équivaut à la méthode SJF mais préemptive.
Exemple:
Reprenez l’exemple précédent avec la politique SRTF.
Le schéma d’exécution : AAABCCCCEDDBBBBB
1
Algorithmes de Scheduling
Politique à base de priorité
Des priorités sont affectées aux différents processus et ils sont activés en fonction de cette priorité. Le
processus élu par le scheduler est celui qui a la plus haute priorité parmi les processus éligibles.
Exemple:
Considérons quatre processus A, B, C et D dont leurs durées d’exécution, leurs dates d’arrivée et leurs
priorités respectives sont données dans la table ci-après. Faites un schéma qui illustre leur exécution et
calculez le temps de rotation de chaque processus, le temps moyen de rotation, le temps d'attente et le
temps moyen d'attente en utilisant la politique à base de priorité avec préemption.
Le schéma d’exécution : AAABBBDDBBBCCCC
Remarque
La méthode SJF est un cas particulier de la politique de Scheduling par priorité p où p=1/t (t est le temps
CPU estimé).
Lorsque ce temps t est important, sa priorité p diminue ⇒ le processus est moins prioritaire.
Politique du Tourniquet (Round Robin, RR)
Cette politique consiste à allouer le processeur aux processus suivant une durée d’exécution limitée
appelée « Quantum ». C’est une politique préemptive, qui s’adapte bien aux systèmes à temps partagé.
Exemple1:
Considérons trois processus A, B, et C dont les durées d’exécution et les dates d’arrivée respectives sont
données dans la table ci-après. Faites un schéma qui illustre leur exécution et calculez le temps de rotation
de chaque processus, le temps moyen de rotation, le temps d'attente et le temps moyen d'attente en
utilisant la politique RR.
On suppose que le Quantum = 3 et que la durée de commutation = 0.
Le schéma d’exécution : AAABBBAAABBBCCCAABBC
Exemple2:
Considérons trois processus A, B, et C dont les durées d’exécution et les dates d’arrivée respectives sont
données dans la table ci-après. Faites un schéma qui illustre leur exécution et calculez le temps de rotation
de chaque processus, le temps moyen de rotation, le temps d'attente et le temps moyen d'attente ainsi que
le nombre de changements de contexte effectués en utilisant la politique RR.
La notation x(y)z signifie que le processus fait x UT calcul, ensuite y UT E/S et enfin z UT calcul.
On suppose que le Quantum = 3 et la durée de commutation = 1.
2
Algorithmes de Scheduling
Exercice :
FIFO. Schéma d'exécution :
A A A B B B B B B C C C C D D E
1 5 10 15
Le temps de séjour pour chaque processus est obtenu soustrayant le temps d'entrée du processus du temps de
terminaison. Ainsi :
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
Le temps d'attente est calculé soustrayant le temps d'exécution du temps de séjour (rotation) :
Processus Temps de séjour
A 3-3=0
B 8-6=2
C 9-4=5
D 9-2=7
E 9-1=8
2. Le plus court d'abord(SJF). Schéma d'exécution :
A A A B B B B B B E D D C C C C
1 5 10 15
Pour la stratégie SJF nous aurons la séquence d'exécution A,B,E,D,C, et le temps de
séjour(rotation) est :
Processus Temps de séjour
A 3-0=3
B 9-1=8
E 10-7=3
D 12-6=6
C 16-4=12
Processus Temps de séjour
A 3-3=3
B 8-6=8
E 3-1=2
D 6-2=4
C 12-4=8