Ordonnancement des processus — Concepts des systèmes d’exploitation

L’ordonnancement des processus est la décision du système d’exploitation concernant le prochain processus prêt à recevoir le CPU. En termes simples, c’est la règle qui détermine qui s’exécute maintenant et qui attend. Cette règle modifie le temps d’attente, le temps de réponse, l’équité et le débit global.

L’ordonnancement des processus est important, car le même ensemble de processus peut se terminer dans un ordre très différent selon FCFS, SJF ou round robin. Si vous comprenez cette idée, la plupart des exemples de manuel deviennent beaucoup plus faciles à lire.

Ce que signifie l’ordonnancement des processus dans un OS

Dans le modèle habituel d’un OS, les processus passent par des états comme prêt, en cours d’exécution et en attente. L’ordonnanceur choisit parmi les processus prêts.

C’est pourquoi l’ordonnancement des processus est souvent appelé ordonnancement CPU. Il ne crée pas de nouveau travail. Il décide de l’ordre dans lequel le travail en attente reçoit du temps CPU.

Dans les systèmes modernes, le noyau ordonnance souvent directement les threads, mais le terme classique « ordonnancement des processus » reste le terme standard dans l’enseignement.

Ce qu’un ordonnanceur essaie d’optimiser

Un ordonnanceur cherche généralement à équilibrer plusieurs objectifs :

• faible temps d’attente
• réponse rapide pour les tâches interactives
• bon débit
• équité
• comportement prévisible

Ces objectifs peuvent entrer en conflit. Une politique qui réduit le temps d’attente moyen dans un exemple simplifié peut quand même sembler injuste en pratique, et une politique équitable de partage du temps peut retarder l’achèvement d’un travail court.

Ordonnancement préemptif vs non préemptif

Un ordonnanceur non préemptif laisse un processus en cours d’exécution garder le CPU jusqu’à la fin de sa rafale CPU ou jusqu’à ce qu’il se bloque. First-come, first-served en est l’exemple standard.

Un ordonnanceur préemptif peut interrompre un processus en cours d’exécution et donner le CPU à un autre. Round robin et de nombreux ordonnanceurs par priorité fonctionnent ainsi.

Cette distinction est importante, car le temps de réponse s’améliore souvent lorsque le système est autorisé à préempter un travail de longue durée.

Algorithmes courants d’ordonnancement des processus

First-Come, First-Served

First-come, first-served, ou FCFS, exécute les processus dans l’ordre d’arrivée. Il est facile à comprendre et simple à implémenter, mais un long travail placé en tête peut obliger tous les travaux courts derrière lui à attendre.

Shortest Job First

Shortest job first, ou SJF, privilégie le processus ayant la plus petite rafale CPU. Dans un cadre simplifié où les durées de rafale sont connues avec précision, il peut réduire le temps d’attente moyen. Dans les systèmes réels, cette durée doit généralement être estimée.

Round Robin

Round robin donne à chaque processus prêt une petite tranche de temps appelée quantum. Si le processus ne se termine pas pendant cette tranche, il retourne dans la file des processus prêts. Cela améliore généralement l’équité et la réactivité pour les charges de travail interactives.

Priority Scheduling

L’ordonnancement par priorité exécute d’abord le processus prêt de plus haute priorité. Il peut être utile lorsque certaines tâches comptent plus que d’autres, mais si les tâches de faible priorité attendent trop longtemps, le risque de famine apparaît.

Un exemple détaillé avec le temps d’attente

Supposons que trois processus arrivent tous à l’instant $0$ et que chacun n’ait besoin que de temps CPU :

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

Supposons :

• il y a un seul CPU
• il n’y a pas de blocage d’E/S
• le coût de changement de contexte est ignoré

Dans ces conditions, le temps d’attente désigne le temps passé dans la file des processus prêts avant qu’un processus ne s’exécute. Le temps de séjour est

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

Si FCFS est utilisé, l’ordre est $P_1 \rightarrow P_2 \rightarrow P_3$.

Chronologie :

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

Temps d’attente :

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

Temps d’attente moyen :

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

Si SJF non préemptif est utilisé, l’ordre est $P_3 \rightarrow P_2 \rightarrow P_1$.

Chronologie :

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

Temps d’attente :

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

Temps d’attente moyen :

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

Cet exemple montre l’intuition principale. La charge de travail n’a pas changé, mais la règle a changé le résultat. Ici, SJF donne un temps d’attente moyen plus faible, car les travaux courts ne restent pas bloqués derrière le long.

Cela ne signifie pas que SJF est toujours le meilleur choix dans le monde réel. Cela signifie que, selon les hypothèses de cet exemple, l’ordre d’ordonnancement compte énormément.

L’intuition à retenir

Considérez l’ordonnancement des processus comme la discipline de file d’attente du CPU. La file des processus prêts peut contenir les mêmes travaux, mais la règle de service de cette file change ce que les utilisateurs ressentent.

Si vous vous souciez surtout d’obtenir une première réponse rapide, vous pouvez préférer un partage fréquent. Si vous voulez surtout terminer rapidement beaucoup de travaux courts, vous pouvez préférer une politique qui favorise les courtes rafales. Si vous avez besoin d’un timing strict, il vous faudra peut-être encore un autre ordonnanceur.

Erreurs fréquentes dans les problèmes d’ordonnancement

Supposer qu’une politique est universellement meilleure

Il n’existe pas de gagnant unique pour toutes les charges de travail. Une politique peut sembler excellente pour le temps d’attente moyen et rester mauvaise pour l’équité ou les échéances.

Confondre temps d’attente, temps de réponse et temps de séjour

Ces métriques sont liées, mais elles ne sont pas identiques. En particulier, le temps de réponse désigne généralement le temps jusqu’au premier service CPU ou à la première réponse visible, tandis que le temps de séjour mesure tout le travail depuis l’arrivée jusqu’à l’achèvement.

Ignorer la condition derrière la formule

Les métriques n’ont de sens que sous les hypothèses indiquées. Si un problème inclut un blocage d’E/S, des temps d’arrivée différents ou le surcoût des changements de contexte, la chronologie et les résultats changent.

Oublier si la politique est préemptive

SJF et shortest remaining time first ne sont pas la même règle. L’ordonnancement par priorité se comporte aussi différemment selon qu’un travail de priorité plus élevée peut interrompre le travail courant ou non.

Où l’ordonnancement des processus est utilisé

L’ordonnancement des processus est important partout où un système d’exploitation doit partager le temps CPU :

• systèmes de bureau et mobiles qui ont besoin d’applications réactives
• serveurs qui traitent de nombreuses requêtes
• systèmes batch qui privilégient le débit
• systèmes temps réel qui exigent des garanties temporelles

Les ordonnanceurs réels sont généralement plus complexes que les versions de manuel, mais les mêmes compromis réapparaissent.

Essayez votre propre version

Modifiez l’exemple pour que $P_2$ arrive plus tard, ou remplacez FCFS par round robin avec un quantum de $2\ \mathrm{ms}$, et observez comment le schéma d’attente change. Si vous voulez aller un peu plus loin après l’avoir fait à la main, essayez votre propre version dans GPAI Solver et comparez votre chronologie prévue avec celle calculée.