Ordonnancement de processus

Comme vous avez pu le voir, beaucoup de processus sont actifs en même temps. Mais un processeur ne peut faire qu'une chose à la fois. Même si une machine moderne possède 4 processeurs ou plus, elle ne peut exécuter tous ces processus simultanément. Il faut donc les exécuter tour à tour et se donner une règle pour décider à quel processus donner le prochain tour.

Exemple

Pour illustrer les différents choix possibles, prenons un exemple avec 4 processus.

Processus	Soumission	Durée	Priorité
P1 - Rouge	0	3	0
P2 - Bleu	2	2	0
P3 - Vert	1	4	0
P4 - Violet	3	3	1

Soumission : moment auquel est demandé l'exécution du processus. On soumet au système d'exploitation une demande d'exécution, c'est le système d'exploitation qui décide.
Durée : temps d'exécution nécessaire pour le processus. Difficile à déterminer à priori.
Priorité : certains processus peuvent être jugés plus urgents que d'autres et donc passer devant les autres. Dans une file d'impression par exemple, l'utilisateur peut indiquer que tel document est prioritaire. Dans le cas des processus, c'est au système d'exploitation d'évaluer les priorités.

FIFO : Premier arrivé, premier servi

Exercice 1

Complétez le graphique représentant l'enchaînement des processus dans ce cas. Le principe est simple : premier arrivé, premier servi.

Correction

Le graphique et le titre me semblent assez explicites…

Temps d'attente : délai entre l'instant de soumission et l'instant de la première exécution.
Temps d'exécution : délai entre l'instant de soumission et l'instant où le processus est complètement terminé.

Exercice 2

Mesurez le temps d'attente pour chacun des processus.
Calculez le temps d'attente moyen pour l'ensemble des 4 processus.
Mesurez le temps d'exécution pour chacun des processus.
Calculez le temps d'exécution moyen pour l'ensemble des 4 processus.

Avantages inconvénients

Pas de notion de priorité sur les processus,
non préemptif – un processus démarré n'est pas interrompu pour en exécuté un autre,
pas de connaissance sur la durée des processus,
temps d'attente augmente vite

FIFO avec priorité

Chaque fois que le système est libre, le système d'exploitation liste les processus qui lui ont été soumis. Parmi ceux là, il sélectionne le plus prioritaire. A priorité égale, il sélectionne celui soumis en premier.

Exercice 3

Complétez le graphique représentant l'enchaînement des processus dans ce cas.

Remarque : Dans ce cas il ne s'agit pas d'améliorer des performances. Même si l'ensemble de la file est ralentie, la prise en compte d'urgences est plus importante. C'est le principe d'une file d'attente de supermarché où l'on peut donner la priorité à certaines personnes.

Shortest Job First : Le plus court d'abord

Chaque fois que le système est libre, le système d'exploitation liste les processus qui lui ont été soumis. Parmi ceux là, il évalue les temps d'exécutions et il sélectionne celui dont le temps d'exécution sera le plus court.

Exercice 4

Complétez le graphique représentant l'enchaînement des processus dans ce cas.

Exercice 5

Même chose que l'exercice 2

Avantages et inconvénients

Pas de notion de priorité sur les processus,
non préemptif,
nécessite une évaluation de la durée des processus,
risque de privation : si des processus court se présentent constamment, un processus long ne pourra jamais s'exécuter !

Round Robin : Tourniquet

Plus compliqué que les précédents :

On découpe l'exécution en quantum – pour faire simple on prend des quantum de 1 unité de temps.
Quand un processus se présente, il se met à la fin de la file d'attente,
au début d'un nouveau quantum, on sélectionne le processus en tête de file,
le processus sélectionné se place aussitôt à la fin de la file – en effet, on suppose que l'exécution du prochain quantum ne suffira pas à terminer le processus.

Anecdotique : Round Robin vient de Ruban Rond. AU XVIIe siècle, quand les paysans souhaitaient se plaindre au roi, ils lui remettaient une pétition. La réaction du roi était souvent de faire exécuter les 2 ou 3 premier signataires. Pour échapper à la punition, noms et signatures furent disposés en cercle pour qu'il n'y ait plus de premier ou de dernier !

Exercice 6

Complétez le graphique représentant l'enchaînement des processus dans ce cas.

Correction

Quelques explications pour bien comprendre :

(a) à l'instant 0, le processus P1 est seul dans la file,
P1 est sélectionné pour un premier quantum, est retiré de la file, mais se replace aussitôt à la file puisque 1 quantum ne suffira pas. Entre 0 et 1, la file contient donc seulement P1 (b)
(c) à l'instant 1, P3 se présente et se met en bout de file,
P1 est sélectionné pour le quantum suivant et est donc retiré de la file. Comme P1 demande 3 quantum, P1 se place aussitôt en bout de file. C'est pour cela que la file (d) est composée de P3 puis P1.
(e) à l'instant 2, P2 se met en bout de file.
P3, en tête, est sélectionné, retiré de la file et reprend une place en bout de file (f)
etc.
(g) à l'instant 4, c'est P1 qui est sélectionné. Comme les fois précédentes, P1 est retiré du début de la file et se replace aussitôt en bout de file (h). J'ai ajouté une croix sur P1 pour mettre en évidence que cette prise de file pour P1 était inutile puisque P1 va terminer en 3 quantums. Mais le système ne le sait pas encore !
(k) à l'instant 5, P1 se termine complètement, le système d'exploitation peut donc supprimer P1 de la file.

Exercice 7

Même chose que l'exercice 2

Avantages et inconvénients

pas de notion de priorité sur les processus,
préemptif – un processus démarré s'interrompt pour faire place à un autre,
ne nécessite pas de connaissance sur la durée des processus.