Processus et ordonnancement : cours de Terminale NSI

Quand tu ouvres ton navigateur, que de la musique joue et qu'un éditeur de code est ouvert, tu as l'impression que tout tourne en même temps. En réalité, le nombre de programmes en cours dépasse presque toujours le nombre de processeurs disponibles. ⁴ Quelqu'un doit donc décider, à chaque instant, qui travaille et qui attend.

Ce « quelqu'un » est une partie du système d'exploitation : l'ordonnanceur. Dans ce cours, tu vas comprendre :

• ce qu'est un processus du point de vue du système, et par quels états il passe ;
• ce que fait l'ordonnanceur et à quels moments il intervient ;
• ce que coûte un changement de processus (le changement de contexte) ;
• ce que signifie préemptif ou non, et comment on compare des politiques d'ordonnancement ;
• comment ne pas confondre avec la planification de tâches du type cron.

Tu as déjà vu les systèmes sur puce : ils regroupent plusieurs composants sur une même puce. Ici, on regarde le logiciel qui fait vivre ces ressources, en particulier la plus précieuse de toutes, le processeur.

Un processus a besoin du processeur pour effectuer ses calculs, et il le libère par exemple lorsqu'une interruption survient. ⁴ Beaucoup de processeurs anciens ne savent traiter qu'une seule chose à la fois. ⁴ Avec un seul processeur, la seule façon de faire croire que plusieurs programmes avancent ensemble est de les faire passer à tour de rôle, très vite.

Le rôle de l'ordonnanceur est de permettre à tous les processus de finir par s'exécuter, tout en tirant le meilleur parti du processeur pour l'utilisateur. ⁴

Avec plusieurs processeurs, le problème change de forme : il faut aussi choisir quel processeur accueille quel processus. Cette idée porte le nom d'affinité, et elle compte pour ne pas dégrader les performances. ⁴ Les processeurs multicœurs et l'hyperthreading rendent le sujet encore plus délicat. ⁴ Au programme de Terminale, on raisonne surtout sur un seul processeur, car cela suffit à comprendre les principes.

Un processus ne passe pas toute sa vie à calculer. Il peut attendre une donnée du disque, une frappe au clavier, un message réseau. Pour s'y retrouver, on décrit sa vie par des états, et par les transitions qui le font passer de l'un à l'autre.

Les événements qui obligent l'ordonnanceur à prendre une décision se repèrent justement sur ces transitions. On en trouve notamment trois :

1. un processus apparaît (il est nouveau) ou il se termine ; ³
2. le processus qui s'exécute devient bloqué, parce qu'il attend quelque chose ; ³
3. un processus passe de l'état d'attente à l'état prêt. ³

Pour que chaque tâche s'exécute sans avoir à se soucier des autres, le noyau pratique des commutations de contexte. Elles servent aussi à respecter les contraintes imposées au système, par exemple des contraintes de temps dans un système d'exploitation temps réel. ⁴

Concrètement, le système appelle à intervalles réguliers une procédure d'ordonnancement, qui élit le prochain processus à exécuter. ⁴

Quand le tour du processus sauvegardé revient, le système restaure son PCB. Le processus reprend alors exactement là où il s'était arrêté. ⁴ De son point de vue, rien ne s'est passé : il n'a pas « senti » l'interruption.

Selon que l'ordonnanceur peut ou non retirer le processeur de force, on parle d'ordonnancement préemptif ou non préemptif. Dans un système non préemptif, un processus qui a obtenu le processeur le garde jusqu'à ce qu'il se bloque ou qu'il se termine. Dans un système préemptif, le noyau peut interrompre un processus qui s'exécute, par exemple à intervalles réguliers, pour donner la main à un autre.

Le choix de l'algorithme d'ordonnancement détermine le comportement global du système. ⁴ On distingue deux grandes classes d'ordonnancement : le temps partagé et le temps réel. ⁴ Avant de les voir, commençons par la politique la plus simple.

La politique la plus intuitive est celle de la file d'attente : le processus qui est en tête de file utilise la ressource en premier. ³ On l'appelle souvent FIFO (first in, first out, premier arrivé, premier servi). Elle est simple à programmer et équitable dans l'ordre d'arrivée, mais un long calcul placé en tête fait patienter tous les autres. Tu le vérifieras dans l'exemple chiffré plus bas.

L'ordonnancement en temps partagé équipe la plupart des ordinateurs classiques. ⁴ Un exemple : l'ordonnancement dit « decay », celui qui est utilisé par défaut sous Unix. Il repose sur des priorités adaptatives et favorise les tâches interactives, de façon que leur temps de réponse reste bon. ⁴ Une sous-famille, les ordonnanceurs « proportional share », vise plutôt les stations de calcul et gère les ressources de façon rigoureuse ; on peut citer « lottery » et « stride ». ⁴

Dans un système temps réel, certaines tâches ont des contraintes de temps strictes. ⁴ On dit qu'un ordonnanceur temps réel est optimal pour un ensemble de tâches s'il trouve une solution chaque fois qu'il en existe une. S'il échoue, aucun autre ordonnanceur n'aurait réussi. ⁴

Pour comparer deux politiques, on représente l'occupation du processeur sur une ligne de temps : c'est un diagramme de Gantt. Chaque case indique quel processus occupe le processeur pendant quelle durée. On en déduit des grandeurs mesurables.

Dans les exemples qui suivent, les durées sont exprimées en unités de temps (u.t.) et on suppose que tous les processus sont prêts à l'instant 0.

Le mot « ordonnancement » apparaît dans d'autres contextes, et il est facile de tout mélanger. Jusqu'ici, nous avons étudié l'ordonnanceur du noyau, qui partage le processeur entre des processus pendant quelques millisecondes à la fois. Il existe un autre niveau, celui du lancement automatique de traitements sur des machines, souvent appelés batch. ⁵

L'ordonnancement de travaux consiste à automatiser le déclenchement de traitements sur un ou plusieurs composants d'un système d'information, à l'aide de progiciels spécialisés. ⁵ Ces outils combinent la théorie de l'ordonnancement avec des techniques informatiques : files de traitements, gestion de fichiers, équilibrage de charge. ⁵ Parmi leurs buts, on trouve la réduction des interventions humaines dans les chaînes de production, et la possibilité de relier des processus et des événements par des dépendances. ⁵