1-Introduction
Un processus actif est dit élu s'il est en cours d'exécution.
S'il ne peut s'exécuter, faute de disponibilité du processeur, mais qu'il présente toutes les qualités pour être exécuté on dit qu'il est éligible.
Les états d'un processus sont schématisés dans la figure 1.
Un processus éligible est élu (1) lorsque le processeur devient disponible.
Il peut revenir à l'état éligible (2) si le processeur est requis par un processus plus prioritaire ou s'il a consommé la tranche de temps qui lui est allouée, dans le cas d'un système en temps partagé.
Un processus est bloqué (3) lorsqu'il est en attente d'une ressource (entrées-sorties...) ou volontairement arrêté et devient éligible lorsqu'il a été réveillé (4).
Rôle de l’ordonnanceur: choisir, parmi tous les processus élibibles, lequel va devenir élu (politique d’ordonnancement).
Les objectifs d’un ordonnanceur d’un système multi-utilisateur sont, entre autres :
– S’assurer que chaque processus en attente d’exécution reçoive sa part de temps processeur.
– Minimiser le temps de réponse.
– Utiliser le processeur à 100%.
– Utilisation équilibrée des ressources.
– Prendre en compte des priorités.
– Être prédictibles.
2-Stratégies typiques
- FIFO sans préemption
- Tourniquet
- Shortest Job Next
- Highest Response Ratio Next
- Multilevel Feedback
2.1-FIFO sans preemption
- Premier arrivé, premier servi
- Ordonnancement coopératif (pas de préemption) : les processus rendent la main « de leur plein gré » :
o lorsqu’ils se terminent.
o lorsqu’ils se bloquent.
Avantages
- Simple
- Surcoût faible Adapté dans les contextes suivants
* nombreux coeurs de calcul
* processus très fréquemment bloqués (gestions E/S)
*machine peu puissante, ou le surcoût doit être minimisé
Inconvénients
- temps de réponse dépend du processus qui a la main
o tant qu’il ne rend pas la main, les autres doivent attendre
- pénalise les processus courts
o proportion temps d’attente / temps d’exécution
2.2- Tourniquet (circulaire ou round robin)
La liste des processus prêts est mémorisée dans une file du type FIFO (First In First Out), c’est-à-dire en attente d’exécution.
Chaque processus reçoit un quantum de temps.
Une fois le quantum épuisé, le processus passe la main à un autre processus (celui en tête de file).
-En diminuant la durée du quantum :
o le temps de réponse diminue, mais…
o le surcoût augmente
- Le quantum idéal dépend de la durée moyenne d’une interaction et du nombre de processus…
2.3- Shortest Job Next
On donne toujours la main à celui qui va mettre le moins de temps avant de se bloquer / terminer
o suppose d’avoir une connaissance / estimation de ce temps pour chaque processus : hypothèse forte
Avantages
o maximise le temps de réponse, le débit (nombre de processus terminés par unité de temps)
Inconvénients
o surcoût
2.4- Highest Response Ratio Next
- Variante de la stratégie précédente :
- on prend en compte le ratio du temps que le processus a passé à attendre sur le temps dont il a besoin.
- Plus un processus attend, plus il augmente ses chances d’obtenir la main.
- Mais suppose toujours la connaissance du temps d’exécution.
2.5- Multilevel Feedback
- Les processus de même priorité sont regroupés dans une file du type FIFO.
- Il y a autant de files qu’il y a de niveaux de priorité.
- L’ordonnanceur choisit le processus le plus prioritaire qui se trouve en tête de file.
En général, les processus de même priorité sont ordonnancés selon l’algorithme du tourniquet.
- Lorsqu’un processus se bloque ou se termine, il retourne dans la même file.
- Lorsqu’il épuise son quantum, il passe dans la file suivante Une variante de Multilevel Feedback :
- En cas d’attente prolongée dans la dernière file (famine), un processus peut « remonter » progressivement
- Chaque file peut avoir une durée de quantum différente : (priorité haute → quantum court)