TNSI : Processus - Politiques d'Ordonancements⚓︎

Politiques/Algorithmes d'Ordonnancement/de Scheduling⚓︎

Il existe plusieurs politiques/algorithmes d'ordonnancement / algorithmes de scheduling¹ dont le choix va dépendre des objectifs du système. En voici quelques exemples:

Premier Arrivé Premier Servi (FCFS - First Arrived First Served)⚓︎

Algorithme simple mais peu adapté à la plupart des situations. Les processus sont stockés dans une File. Le premier arrivé est admis immédiatement et s'exécute tant qu'il n'est pas dans l'état Bloqué ou Terminé. En cas de blocage du processus courant, le processus suivant commence à s'exécuter, tandis que le processus bloqué se met en bout de la File d'attente.

Avantages : Algorithme Très Simple (simple Liste Chaînée). Ordonnancement équitable.
Inconvénients : Après allocation d'un processus au CPU, le processus ne sera jamais interrompu avant qu'il finisse totalement : c'est algorithme non-préemptif (aucun autre processus ne peut intrrompre le CPU de manière prioritaire). Ainsi, Le processus qui demande davantage de temps est favorisé par rapport aux autres, en particulier par rapport à ceux qui font beaucoup d'appels aux Entrées/Sorties (E/S). La performance de cet algorithme est plutôt faible, et les temps d'attente (d'accès au CPU) élevés.

de Premier Arrivé Premier Servi, dans la vraie vie

C'est la bonne file d'attente pour acheter une baguette à la boulangerie (même les très gros acheteurs, qui aiment raconter leurs vies creuses font partie de la modélisation)

Plus Court D'abord / Shortest Job Forst( SJF)⚓︎

Le processus dont le temps de traitement supposé est le plus court est prioritaire. Si \(4\) tâches (jobs) ont des durées (en secondes) respectivement égales à a, b, c, d, alors la première se termine après a secondes, la deuxième après a+b, etc..
Dans cet exemple, la Durée de Rotation moyenne (TAT- TurnAround Time) est alors :

\(TAT = \dfrac{4a+3b+2c+d}{4}\)

Avantages: Algorithme très efficace
Inconvénients : La plupart du temps, il est impossible de connaître à l'avance le temps d'exécution d'un processus.: ce n'est qu'une supposition. De plus, si de nombreux processus courts arrivent sans cesse, les plus longs ne sont jamais exécutés.

de Plus Court D'abord, dans la vraie vie

C'est typiquement l'algorithme d'attente aux caisses d'un supermarché, lorsque des clients laissent passer ceux qui n'ont que peu d'articles.

Temps Restant le Plus Court / Shortest Remaining Time First (SRTF)⚓︎

Une version plus agressive du précédent. L'ordonnanceur place en tête de File (le premier à passer) le processus dont il estime/suppose qu'il mettra le moins de temps à Terminer. Avec interruption possible d'un autre processus en cours (ce qu'on appelle la préemption). Et non pas le temps total, du processus.

de Temps Restant Le Plus Court, dans la vraie vie

Imaginez un client n'ayant qu'un article arrivant à la caisse d'un supermarché: il vient carrément interrompre le client en cours de traitement par la caissière pour passer devant lui (s'il reste au client doublé plus d'un article à faire passer)

Avantages: Algorithme très efficace (débits de traitement maximisés)
Inconvénients: Une famine est possible, spécialement dans un système très occupé avec de nombreux petits processus exécutés

Tourniquet / Round Robin (RR)⚓︎

Un quantum de temps est alloué à chaque processus (SCHED_RR sous Linux), et à tour de rôle, chacun d'entre eux est traité par le processeur. Si le processus n'est pas terminé au bout de ce temps, il est interrompu (préemption) et mis en bout de file en état prêt. En général dans les OS multitâches, c'est cet algorithme qui est utilisé avec un quantum de temps entre \(20\) et \(50\) ms (millisecondes). Les débits de traitement sont compris entre le FCFS (FIFO) et le SJF/SRTF.

Avantages : Famines impossibles (car aucune priorité n'est utilisée).
Inconvénients :

Priorité / Earliest Deadline First (EDF)⚓︎

Le système alloue un niveau de priorité à chaque processus (SCHED_FIFO sur Linux), la priorité pouvant varier dynamiquement. On implémente ce modèle avec des Files de Priorité. Cependant des processus de faible priorité peuvent très bien ne jamais être élus⁶. Par exemple, pour ne pas encombrer la mémoire avec des processus qui passent beaucoup de leur temps à attendre des E/S, on leur accorde une priorité d'autant plus grande qu'ils ne consomment une petite partie de leur quantum. Supposons que la valeur du quantum est fixée à \(40\) ms.

Un processus qui n'utilise que \(1\) ms avant d'être bloqué (ce processus passe beaucoup de temps à attendre) aurait droit à une priorité de \(\dfrac {40 \,ms}{1 \,ms} = 40\) (donc très prioritaire)
Un processus qui utilise \(8\) ms avant d'être bloqué (ce processus passe un temps "dans la moyenne" à attendre) aurait droit à une priorité de \(\dfrac {40 \,ms}{8 \,ms} = 5\) (donc une priorité moyenne)
Un processus qui utilise \(40\) ms avant d'être bloqué (ce processus ne passe pas beaucoup de temps à attendre) aurait droit à une priorité de \(\dfrac {40 \,ms}{40 \,ms} = 1\) (donc peu prioritaire)

Sur Linux : Mélange Tourniquet/Priorité⚓︎

Un système hybride entre Tourniquet et Priorité qu'on retrouve dans les systèmes Unix.

Quelques Métriques liées à l'Efficacité⚓︎

Les métriques citées ci-dessous sont des métriques utilisées pour mesurer l'efficacité des Algorithmes de Scheduling/Ordonnancement.

Arrival Time / Heure/Instant/Temps d'Arrivée⚓︎

AT - Arrival Time / Heure/Instant/Temps d'Arrivée³

L'Heure d'Arrivée / Arrival Time désigne l'instant où un processus entre dans la File des processus Prêts.

Waiting Time / Temps/Durée d'Attente⚓︎

WT - Waiting Time / Temps/Durée d'Attente³

Le Temps/Durée d'Attente / Waiting Time désigne le temps/durée passé (à attendre) par un processus dans la File des processus Prêts, avant d'accéder au CPU.

Waiting Time, TAT & Burst Time

Temps d'Attente \(=\) Durée de Rotation \(-\) Temps d'Exécution Waiting Time \(=\) Turn Around Time \(-\) Burst Time

de Calculs de Temps d'Attente / Waiting Time ⁴ avec l'Algorithme d'Ordonnancement FCFS

Processus	Heure d'Arrivée	Temps d'Exécution
`P1`	\(0\) ms	\(8\) ms
`P2`	\(1\) ms	\(7\) ms
`P3`	\(2\) ms	\(10\) ms

Diagramme de Gantt
          P1                   P2                  P3
+-------------------+--------------------+---------------------+
| 0 ms         8 ms | 8 ms         15 ms | 15 ms         25 ms |
+-------------------+--------------------+---------------------+

Temps d'Attente de P1 : \(0\) ms
Temps d'Attente de P2 : \(8-1=7\) ms car P2 arrive à \(1\) ms après le début de l'exécution de P1 qui mettra au total \(8\) ms
Temps d'Attente de P3 : \(8+7-2=13\) ms car P3 arrive à \(2\) ms après le début de l'exécution de P1, et l'exécution de P1 et P2 mettra au total \(8+7\) ms

Response Time / Temps/Durée de Réponse⚓︎

RT - Response Time / Temps/Délai de Réponse³

Le Temps/Délai de Réponse / Response Time désigne le temps/durée passé par un processus dans la File d'attente (des processus Prêts), avant d'accéder pour la première fois au CPU.

Response Time, Temps de premier accès & Arrival Time

Response Time \(=\) Temps de premier accès au CPU d'un processus \(-\) Temps d'Arrivée

de Calculs de Temps de Réponse/Response Time ⁴ avec l'Algorithme d'Ordonnancement FCFS

Processus	Heure d'Arrivée	Temps d'Exécution
`P1`	\(0\) ms	\(8\) ms
`P2`	\(1\) ms	\(7\) ms
`P3`	\(2\) ms	\(10\) ms

Temps de Réponse P1 : \(0\) ms
Temps de Réponse P2 : \(8-1\) ms \(= 7\) ms, car P2 doit attendre \(8\) ms que P1 libère le processeur, il aura alors accès au processeur pour la première fois. Mais P2 est arrivé \(1\) ms après le début de l'exécution de P1
Temps de Réponse P3 : \(8+7-2\) ms \(= 13\) ms, car P3 doit attendre \(8+7\) ms que P1 et P2 libèrent le processeur, il aura alors accès au processeur pour la première fois. Mais P3 est arrivé \(2\) ms après le début de l'exécution de P1.

Burst Time / Running Time / Execution Time / Temps/Durée d'exécution⚓︎

BT - Burst/Execution Time / Temps/Durée d'exécution³

Le Temps/Durée d'exécution / Burst Time / Execution/Running Time désigne le temps/durée mis par un processus à être totalement exécuté, en tenant compte du temps d'exécution CPU ET du temps d'exécution pour les Entrées/Sorties (E/S) :

Temps d'Exécution = Temps d'exécution CPU + Temps d'Exécution E/S

Remarque Il est fréquent de négliger le temps d'exécution pour les E/S, ce qui revient alors à supposer que le temps d'exécution est seulement le temps d'exécution CPU.

On ne peut pas connaître à l'avance cette durée: il n'est connu exactement qu'après avoir fini d'exécuter le processus. On ne peut que l'estimer à priori, en faisant des suppositions.

Completion/Exit Time / Instant/Temps de Sortie⚓︎

CT - Completion/Exit Time / Instant/Temps de Sortie³

Le Instant/Temps de Sortie / Completion/Exit Time désigne l'instant où un processus à été totalement exécuté ET est totalement sorti du système.

TAT - TurnAround Time / Durée de Rotation⚓︎

Durée/Temps de Rotation

La durée/temps de rotation moyenne / TurnAroundTime (TAT)² d'un processus/thread/tâche/programme est définie par :

Durée de Rotation (TAT) = Temps d'Attente + Temps d'Exécution Durée de Rotation (TAT) = Temps de Sortie - Temps d'Arrivée

Elle peut être vue également comme le temps écoulé entre (début) le moment de la soumission d'un processus/thread/tâche/programme pour être exécuté, et (fin) sa complétion totale (renvoi de sa sortie finale).
Elle ne tient compte que des délais internes de traitement.

Durée de Rotation

La Durée/Temps de Rotation / TAT - TurnAround Time d'un processus est la Somme Totale des :

temps d'attente (pour être dans l'état Prêt),
temps d'exécution CPU
temps d'exécution des Entrées/Sorties (E/S) (fréquemment négligées en première approche)

On rappelle que temps d'exécution = temps d'exécution CPU + temps d'Exécution E/S (ces derniers étant souvent négligés) :

Durée de Rotation

Durée de Rotation = Temps d'Attente + Temps d'exécution (=Temps CPU +Temps E/S) Turn Around Time = Waiting Time + Burst Time \(\Leftrightarrow\) Temps d'Attente = Durée de Rotation \(-\) Temps d'Exécution

Throughput / "Débit Moyen de Processus"⚓︎

Throughput / Débit Moyen de Processus

Le Throughput / "Débit (moyen) de processus" est une métrique qui mesure l'efficacité d'un processeur à traiter des processus rapidement.
En pratique, le Throughput est le nombre (moyen) de processus traités par unités de temps.

Throughput

Disons que le processus P1 prend \(2\) secondes, P2 prend \(5\) secondes, et P3 prend \(10\) secondes.
Le Throughput est \(=\dfrac {2+5+10}{3} \, secondes = \dfrac {17}{3} \, secondes \approx 5,67\) secondes

etc.., il existe d'autres métriques..

Références et Notes⚓︎

Vidéos YouTube⚓︎

Références⚓︎

Ordonnancement des Processus, Hanifa Boucheneb, École Polytechnique de Montréal