Ordonnancement de processus¶
Introduction¶
Rappel¶
Rôle de l’ordonnanceur: choisir, parmi tous les processus élibibles, lequel va devenir élu → politique d’ordonnancement
- stratégies typiques
- autres critères
États d’un processus
Stratégies typiques¶
FIFO sans préemption¶
- Premier arrivé, premier servi
- Ordonnancement coopératif (pas de préemption) :
les processus rendent la main « de leur plein gré »,
- lorsqu’ils se terminent,
- lorsqu’ils se bloquent,
- lorsqu’ils font l’appel système
yield.
Note
L’appel système yield sert au processus à céder le processeur aux autres.
FIFO sans préemption: inconvénients¶
- temps de réponse dépend du processus qui a la main
- tant qu’il ne rend pas la main, les autres doivent attendre
- pénalise les processus courts
- proportion temps d’attente / temps d’exécution
FIFO sans préemption: avantages¶
- simple
- surcoût faible
- équitable
Adapté dans les contextes suivants
- nombreux cœurs de calcul
- processus très fréquemment bloqués (gestions E/S)
- machine peu puissante, ou le surcoût doit être minimisé
FIFO sans préemption (3)¶
Utilisations :
- certains systèmes batch
- faible surcoût, meilleure utilisation du/des processeur(s)
- pas de contrainte de temps de réponse
- Mac OS < X (multitâche coopératif)
- faible surcoût, intéressant pour une machine lente
- Processus « temps réel » sous Linux
- processus de gestion des E/S, fréquemment bloqués mais nécessitant une réaction très rapide aux interruptions matérielles
Tourniquet¶
- FIFO avec préemption
- Chaque processus reçoit un quantum de temps
- Une fois le quantum épuisé, le processus passe la main au retourne dans la file d’attente
- En anglais : round robin (ruban rond)
Tourniquet (2)¶
- En diminuant la durée du quantum :
- le temps de réponse diminue, mais…
- le surcoût augmente
- Le quantum idéal dépend de la durée moyenne d’une interaction et du nombre de processus…
Tourniquet (3)¶
+ temps de réponse borné, indépendamment des processus (calculs ou E/S)
+ équitable
- très sensible au choix du quantum
- défavorise les processus orientés E/S (bloqués avant la fin de leur quantum)
Shortest Job Next¶
- On donne toujours la main à celui qui va mettre le moins de temps avant de se bloquer / terminer
- suppose d’avoir une connaissance / estimation de ce temps pour chaque processus : hypothèse forte
- Avantages
- maximise le temps de réponse, le débit (nombre de processus terminés par unité de temps)
- Inconvénients
- surcoût
- inéquitable, famine possible (processus calculatoires)
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
Supprime le problème de famine
- plus un processus attend, plus il augmente ses chances d’obtenir la main
Mais suppose toujours la connaissance du temps d’exécution
Multilevel Feedback¶
- Plusieurs files, ordonnées par priorité
- 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
- Favorise le temps de réponse des processus orientés E/S
Multilevel Feedback (variantes)¶
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)
Autres critères¶
Notion de priorité¶
Certaines stratégies donnent la priorité à certains types de processus (ex: SJN, HRRN, ML Feedback)
On souhaite aussi donner à l’utilisateur la possibilité d’influer sur la priorité d’un processus
Distinction entre :
priorité externe
→ propriété définie par l’utilisateur, variant peu
priorité interne
→ propriété gérée par l’ordonnanceur, variant plus souvent
Notion de priorité (2)¶
- Exemple sous UNIX: la commande
nicepermet de modifier la priorité externe - Influence de la priorité externe:
- en fixant leur priorité interne de départ
- en limitant la plage de priorité interne dans laquelle ils peuvent évoluer
- Les systèmes modernes possèdent plusieurs classes de priorité, hermétiques entre elles, et gérées différemment
Temps réel¶
Objectif : garantir autant que possible aux processus certains délais
Inconvénient : le système doit faire des estimations « dans le pire des cas »
→ dégrade les performances (temps de réponse, débit)
Exemple de stratégie : EDF (Earliest Deadline First)
optimal lorsqu’il est possible de respecter tous les délais…
…mais très mauvais lorsque le système est surchargé
Exemples réels¶
Linux¶
Trois classes de priorité, chacune comportant plusieurs niveaux de priorité
« Temps réel » FIFO
→ une FIFO par niveau de priorité
« Temps réel » tourniquet
→ un tourniquet par niveau de priorité
Autre
→ ML Feedback « amélioré » (priorité utilisateur)
Windows¶
32 niveaux de priorité, divisés en deux classes
« Temps réel » (16-31)
→ priorité fixe, chaque niveau géré par un tourniquet
Variable (0-15)
- les processus migrent d’un niveau à l’autre en fonction de la consommation de leur quantum, et du type d’E/S qu’ils effectuent
- favorise les processus interactifs (E/S clavier, souris, écan…)
Windows (suite)¶
Sur un système à N processeurs
- les N-1 processus les plus prioritaires ont chacun un processeur
- tous les autres processus se partagent le dernier processeur
Conclusion¶
À retenir¶
- Stratégies typiques
- Variantes (compromis, priorité externe)
- Pas de stratégie idéale : dépend des besoins
- Applicable dans d’autres contextes (transparent suivant)
Ordonnanceur « applicatif »¶
Exemple : serveur HTTP, gérant de nombreuses connexions simultanées:
utiliser un processus ou un thread par connexion,
- en laissant le système d’exploitation gérer l’ordonnancement.
utiliser un nombre fixe de threads (potentiellement un seul),
en gérant « à la main » l’ordonnancement entre les connexions.
→ avantages ?