Ordonnancement du processeur

L'ordonnancement du processeur est la fonction du système d'exploitation qui décide quel processus ou fil d'exécution prêt s'exécutera ensuite sur un processeur, en conciliant des objectifs tels que la réactivité, le débit, l'équité et le respect des échéances.

Definition

L'ordonnancement du processeur est la politique et le mécanisme par lesquels un système d'exploitation sélectionne, parmi les processus ou fils d'exécution exécutables, celui auquel allouer le processeur et pour combien de temps, afin d'optimiser les objectifs de performance et d'équité choisis.

Scope

Ce sujet couvre les politiques d'ordonnancement et leur évaluation : premier arrivé, premier servi ; plus court travail en premier ; tourniquet ; priorité ; et files d'attente à rétroaction multiniveau ; l'ordonnancement préemptif versus non-préemptif ; les critères d'utilisation du processeur, de débit, de temps de cycle, de temps d'attente et de temps de réponse ; et l'ordonnancement sur multiprocesseurs et pour les systèmes temps réel. Il exclut la représentation des tâches à ordonnancer (gestion des processus et des fils d'exécution) et la synchronisation (concurrence).

Core questions

• Selon quels critères la qualité de l'ordonnancement est-elle mesurée ?
• Comment les algorithmes d'ordonnancement courants diffèrent-ils en termes d'équité et d'efficacité ?
• Quand l'ordonnanceur doit-il préempter une tâche en cours d'exécution ?
• Comment l'ordonnancement est-il adapté aux multiprocesseurs et aux échéances en temps réel ?

Key concepts

• premier arrivé, premier servi
• plus court travail en premier
• tourniquet et quantum de temps
• ordonnancement par priorité
• files d'attente à rétroaction multiniveau
• préemptif vs non-préemptif
• temps de cycle, temps d'attente et temps de réponse
• inanition et vieillissement
• ordonnancement temps réel

Key theories

Objectifs et compromis de l'ordonnancement

Aucune politique unique n'optimise tous les objectifs : le plus court travail en premier minimise le temps d'attente moyen mais peut affamer les tâches longues, le tourniquet borne le temps de réponse au prix d'un certain coût en débit, et les schémas de priorité risquent l'inanition ; les ordonnanceurs équilibrent donc le débit, l'équité et la réactivité pour leur charge de travail.

Mechanisms

L'ordonnanceur s'exécute lorsqu'un processus se bloque, cède le processeur ou que son quantum de temps expire, choisissant la tâche suivante dans la file d'attente des processus prêts selon sa politique. Le tourniquet accorde à chaque tâche une tranche de temps à tour de rôle ; les files d'attente à priorité et à rétroaction multiniveau ordonnent les tâches par importance et comportement observé, utilisant le vieillissement pour prévenir l'inanition. Les ordonnanceurs préemptifs peuvent interrompre une tâche en cours d'exécution pour passer à une tâche de priorité plus élevée, ce qui est essentiel pour l'interactivité et le respect des échéances en temps réel.

Clinical relevance

L'ordonnancement façonne directement l'expérience utilisateur et l'efficacité du système : il détermine si les applications interactives semblent réactives, si les charges de travail par lots s'achèvent rapidement et si les tâches temps réel respectent les échéances. Les ordonnanceurs des systèmes de production tels que Linux équilibrent ces objectifs concurrents sur de nombreux cœurs et diverses charges de travail.

History

Les problèmes d'ordonnancement sont apparus avec la multiprogrammation et le partage de temps dans les années 1960, lorsque des schémas de tourniquet et de priorité ont été développés pour partager les processeurs. La théorie de l'ordonnancement temps réel, incluant les analyses à taux monotone et à échéance la plus proche en premier, a été formalisée dans les années 1970, et les ordonnanceurs multicœurs modernes ont étendu ces idées à de nombreux processeurs.

Debates

Équité versus débit et priorité

Les ordonnanceurs doivent concilier l'équité entre les tâches avec la maximisation du débit et le respect des priorités ; une priorisation agressive améliore les tâches importantes mais risque d'affamer les autres, tandis qu'une équité stricte peut sous-utiliser le système ; les ordonnanceurs pratiques ajustent donc cet équilibre.

Key figures

• Edsger W. Dijkstra
• Abraham Silberschatz
• Andrew S. Tanenbaum
• C. L. Liu
• James W. Layland

Seminal works

• silberschatz2018
• tanenbaum2014os

Frequently asked questions

Quelle est la différence entre l'ordonnancement préemptif et non-préemptif ?

L'ordonnancement non-préemptif permet à une tâche en cours d'exécution de conserver le processeur jusqu'à ce qu'elle se bloque ou se termine. L'ordonnancement préemptif peut retirer de force le processeur — par exemple lorsque sa tranche de temps expire ou qu'une tâche de priorité plus élevée devient prête — ce qui améliore la réactivité et est requis pour les garanties temps réel.

Qu'est-ce que l'inanition et comment est-elle prévenue ?

L'inanition se produit lorsqu'une tâche n'est jamais ordonnancée parce que des tâches de priorité plus élevée prennent continuellement le pas. Elle est généralement prévenue par le vieillissement, qui augmente progressivement la priorité des tâches en attente depuis longtemps afin qu'elles finissent par s'exécuter.