Algorithmes d'allocation
Algorithme du "premier arrivé, premier servi"
Cet algorithme correspond aux traitements "en batch", dans lequel il n'y a ni préemption, ni priorité, et tout processus commencé s'exécute jusqu'au bout avant de passer au suivant.
Ce modèle, qui n'a pas d'intérêt dans un système moderne multi-programmé, est cependant très facile à modéliser :
Algorithme du "plus court d'abord"
On estime en général que les travaux les plus courts devraient être exécutés en priorité (en anglais "Shortest Job First" ou SJF).
Dans l'algorithme dit du "plus court d'abord", sans préemption, les processus sont classés dans une file d'attente dans l'ordre des temps d'exécution croissante.
Malheureusement, le temps d'exécution est inconnu avant qu'elle ait eu lieu.
D'autre part on risque une privation pour les travaux longs.
Cet inconvénient peut être tourné en augmentant la priorité des processus en attente proportionnellement au temps qu'ils passent dans la file d'attente.
Algorithme du tourniquet ("Round robin")
Cet algorithme est le plus élémentaire mis en place lorsqu'un quantum de temps est alloué à un processus.
Le fonctionnement est celui d'une file d'attente circulaire.
On accède au processus élu par un pointeur.
Lorsque le processus courant a épuisé son quantum de temps, le pointeur "processus actif" passe au suivant, le processus précédent devenant le dernier de la file :
Tout nouveau processus lancé pendant l'exécution du processus actif prend place en fin de la liste, soit juste avant le pointeur "processus actif".
Si au contraire un processus se termine, il est éliminé de la liste et le pointeur "processus actif" passe au processus suivant.
Dans la figure suivante, le processus A s'est terminé, le processus B a épuisé son quantum de temps, et le processus Z a été lancé.
Le quantum de temps doit être ajusté en fonction du temps de commutation de contexte et des délais maximaux de réponse souhaité: un quantum de temps de 20 ms pour un temps de commutation de contexte de 5 ms représente un "overhead" de 20 % ce qui est prohibitif.
En revance, un quantum de temps de 500 ms pour 10 utilisateurs, s'il est acceptable pour l'overhead, représente un délai de réponse de 5 secondes pour un utilisateur, ce qui est trop long pour de la saisie de caractère par exemple.
Algorithme du "plus court restant"
Dans l'algorithme du plus court restant (en anglais du "Shortest Remainded-Time"), le processus dont le temps d'exécution restant est le plus court est prioritaire.
Ce système s'accompagne de préemption qui implique une augmentation de l'"overhead".
Il faut estimer a priori le temps restant d'un processus, tenir à jour la comptabilité de son temps d'exécution déjà effectué, et le chasser si un autre processus (par exemple qui vient d'être lancé) est estimé plus court.
Tourniquet à plusieurs étages
Dans ce schéma, illustré par la figure 4, plusieurs files d'attente correspondant à plusieurs "tourniquets" de priorités différentes sont gérées simulanément.
Un processus nouveau est placé dans la première file où il attend son tour.
Lorsqu'il est exécuté, s'il utilise tout son quantum de temps, il est ensuite préempté, puis placé dans la deuxième file d'attente, un peu moins prioritaire, et ainsi de suite tant qu'il utilise tout son quantum.
Chaque fois qu'un processus passe au niveau de priorité inférieure, il doit non seulement attendre que tous les processus qui sont avant lui dans la file passent, mais aussi qu'aucun processus ne reste plus dans les files des priorités supérieures.
Dans certaines implémentations, on peut augmenter le quantum des processus au fur et à mesure que leur priorité diminue.
Algorithme HRN : "High-Response Ratio Next"
Dans cet algorithme, la priorité tient compte à la fois du temps de service, mais aussi du temps passé à attendre ce service.
Elle est calculée par:
priorité = (temps du service + temps d'attente) / temps du service
Elle rend proportionnel le temps d'attente au temps de service.
Elle ne favorise pas trop les travaux courts ni ne défavorise pas trop les travaux longs.
Dernière mise à jour : 06/07/2001