:tocdepth: 2 .. index:: ordonnanceur ============================= Ordonnancement de processus ============================= .. include:: common.rst.inc 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 .. figure:: _static/ps_states.png :width: 50% États d'un processus Stratégies typiques =================== .. contents:: :local: :depth: 0 :backlinks: none .. index:: single: FIFO; sans préemption (ordonnanceur) .. index:: single: ordonnanceur; coopératif single: multi-tâches; coopératif pair: appel système; yield 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 .. index:: tourniquet see: round robin; tourniquet Tourniquet ++++++++++ .. figure:: _static/roundrobin.png :width: 45% :class: float-right * 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) -------------- .. ifslides:: .. figure:: _static/roundrobin.png :width: 45% :class: float-right * 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) -------------- .. figure:: _static/roundrobin_inequity.png :width: 18% :class: float-right \+ 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) .. index:: SJN (Shortest Job Next) 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) .. index:: HRRN (Highest Response Ratio Next) 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 .. index:: multilevel feedback Multilevel Feedback +++++++++++++++++++ .. figure:: _static/multilevel_feedback.png :width: 50% :class: float-right * 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) ------------------------------- .. ifslides:: .. figure:: _static/multilevel_feedback.png :width: 50% :class: float-right * 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 =============== .. contents:: :local: :depth: 0 :backlinks: none .. index:: priorité 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 ``nice`` permet 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 Partage équitable (*fair share*) ++++++++++++++++++++++++++++++++ * Le processus n'est pas forcément le bon grain pour mesurer l'équité d'un ordonnanceur * Dans certain cas, on peut souhaite partager le temps processeur équitablement entre * les utilisateurs → indépendamment du nombre de processus lancé par chacun d'eux * des groupes d'utilisateurs → indépendamment du nombre d'utilisateur et de processus .. index:: single: temps réel; ordonnancement 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 ============== .. contents:: :local: :depth: 0 :backlinks: none .. index:: single: temps réel; classe de priorité 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) .. index:: single: temps réel; classe de priorité 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 ?