Processus et ordonnancement
Ce que ce chapitre apporte
- Distinguer un programme d'un processus.
- Nommer les informations que le système conserve pour chaque processus.
- Décrire les états d'un processus et les transitions entre eux.
- Expliquer ce qu'est une commutation de contexte et ce qu'elle coûte.
- Situer monoprogrammation, multiprogrammation et temps partagé.
- Comparer les principaux algorithmes d'ordonnancement.
- Distinguer ordonnancement préemptif et coopératif.
Programme et processus
Un programme est un fichier passif : une suite d'instructions sur un disque.
Un processus est un programme en cours d'exécution, avec son espace mémoire, ses registres, sa pile et ses ressources ouvertes.
Un même programme lancé trois fois donne trois processus indépendants, avec chacun ses variables et sa position d'exécution. La distinction paraît évidente et se retrouve pourtant au cœur de tout le chapitre : ce que le système gère, ce n'est jamais un programme, c'est un processus.
Le bloc de contrôle
Pour pouvoir interrompre un processus et le reprendre plus tard exactement là où il en était, le système conserve un ensemble d'informations qui constituent son bloc de contrôle.
| Information | Ce qu'elle permet |
|---|---|
| Identifiant (PID) | désigner le processus sans ambiguïté |
| État | savoir s'il peut s'exécuter |
| Compteur ordinal | reprendre à l'instruction suivante |
| Registres du processeur | retrouver les valeurs en cours de calcul |
| Pointeur de pile | retrouver les appels de fonction en cours |
| Espace mémoire alloué | savoir ce qui lui appartient |
| Liste des fichiers ouverts | reprendre les lectures et écritures |
| Informations d'ordonnancement | priorité, temps consommé |
Sans l'un d'eux, la reprise serait fausse. C'est cette exigence qui détermine le contenu du bloc de contrôle, et non une convention.
Les états d'un processus
Trois états suffisent à décrire l'essentiel, auxquels on ajoute deux états de bord.
creation
|
v
+-------+ elu par l'ordonnanceur +--------+
| pret | -------------------------> | actif |
+-------+ <------------------------- +--------+
^ preempte ou fin de quantum |
| | demande d'entree-sortie
| l'entree-sortie est terminee v
+----------------------------------+ bloque +
+--------+
|
v
terminaison
Un processus prêt peut s'exécuter mais attend son tour. Un processus actif occupe un processeur. Un processus bloqué attend un événement extérieur, le plus souvent la fin d'une opération d'entrée-sortie, et ne peut pas être élu tant que cet événement ne s'est pas produit.
La distinction explique une observation courante : un programme qui lit beaucoup sur disque paraît lent alors que le processeur est peu chargé. Il passe l'essentiel de son temps bloqué, et le processeur est disponible pour d'autres.
La commutation de contexte
La commutation de contexte est l'opération par laquelle le système sauvegarde l'état du processus actif dans son bloc de contrôle, charge celui d'un autre processus, et lui donne la main.
Elle est fréquente, et elle n'est pas gratuite. Elle coûte le temps de sauvegarde et de restauration des registres, mais surtout l'invalidation des caches du processeur : le nouveau processus travaille sur d'autres données, les caches se vident et se remplissent à nouveau.
Le réglage cherche un compromis entre réactivité et rendement, et les valeurs employées par les systèmes actuels se comptent en quelques dizaines de millisecondes.
Les modes de fonctionnement
Quatre organisations se sont succédé, et les nommer situe le reste.
| Mode | Principe | Limite |
|---|---|---|
| Monoprogrammation | un seul programme en mémoire, exécuté jusqu'au bout | le processeur attend pendant chaque entrée-sortie |
| Multiprogrammation | plusieurs programmes en mémoire, on change quand l'un se bloque | un programme long monopolise la machine |
| Temps partagé | changement périodique, imposé par une horloge | commutations nombreuses |
| Multitraitement | plusieurs processeurs exécutent réellement en parallèle | synchronisation nécessaire |
Le passage de la multiprogrammation au temps partagé est celui qui compte. Dans le premier cas, le système attend qu'un processus rende la main. Dans le second, il la reprend.
En ordonnancement coopératif, un processus conserve le processeur jusqu'à ce qu'il se bloque ou qu'il rende la main volontairement.
En ordonnancement préemptif, le système peut lui retirer le processeur à tout moment, typiquement à l'expiration d'un quantum de temps.
Le coopératif est plus simple et plus efficace quand tous les processus se comportent bien. Il suffit qu'un seul entre dans une boucle sans fin pour que le système entier se fige, puisque personne ne peut lui reprendre la main. C'est la raison pour laquelle tous les systèmes généralistes actuels sont préemptifs.
Les algorithmes d'ordonnancement
Le temps d'attente est le temps passé à l'état prêt. Le temps de réponse est le délai avant la première exécution. Le temps de rotation est la durée totale, de l'arrivée à la fin.
Un ordonnanceur cherche aussi à éviter la famine : qu'aucun processus ne soit indéfiniment écarté.
| Algorithme | Principe | Force | Faiblesse |
|---|---|---|---|
| Premier arrivé, premier servi | ordre d'arrivée | simple, sans famine | un long processus bloque tous les autres |
| Plus court d'abord | le plus court en premier | temps d'attente moyen minimal | suppose de connaître les durées, famine possible |
| Tourniquet | chacun son tour, par quantum | équitable, réactif | mauvais temps moyen, commutations nombreuses |
| Par priorité | le plus prioritaire d'abord | reflète l'importance métier | famine, sauf vieillissement |
Les systèmes réels combinent : plusieurs files de priorités, un tourniquet à l'intérieur de chaque file, et un vieillissement qui remonte progressivement la priorité des processus qui attendent depuis longtemps.
Le tourniquet le supprime en imposant une rotation. C'est son principal argument, davantage que ses temps moyens.
Exercices type
Trois exemplaires du même programme sont lancés. Combien de processus ?
Trois, avec trois identifiants distincts, trois espaces mémoire séparés, trois piles et trois positions d'exécution.
Le programme sur disque reste unique. Ce qui est dupliqué, c'est le contexte d'exécution.
Les trois processus peuvent partager des pages en lecture seule, notamment le code lui-même, ce qui économise de la mémoire. Cela ne change rien à leur indépendance : les variables de l'un sont invisibles pour les autres.
Le processeur est à 15 % et le programme est lent. Que se passe-t-il ?
Le processus passe son temps à l'état bloqué, en attente d'entrées-sorties.
Il demande une lecture disque ou réseau, se bloque, attend, est réveillé, traite brièvement, et redemande. Pendant ses attentes, il ne consomme aucun processeur, ce qui explique le chiffre observé.
La piste d'optimisation n'est donc pas le calcul mais les accès : réduire leur nombre, lire par blocs plus grands, ou les recouvrir avec du traitement en les rendant asynchrones.
Regarder le taux d'occupation du processeur pour diagnostiquer une lenteur conduit régulièrement à optimiser ce qui n'est pas le problème.
Pourquoi le plus court d'abord n'est-il pas utilisé tel quel ?
Pour deux raisons.
Il suppose de connaître les durées à l'avance, ce qui est impossible pour un système généraliste. On peut les estimer à partir de l'historique, avec une précision limitée.
Il peut affamer les processus longs : tant que des tâches courtes arrivent, la longue ne passe jamais.
Les systèmes réels s'en inspirent sans l'appliquer littéralement, en favorisant les processus qui se bloquent souvent, donc les interactifs, et en remontant la priorité de ceux qui attendent depuis longtemps.
Que se passe-t-il si le quantum est très grand ? Très petit ?
Très grand : le tourniquet dégénère en premier arrivé premier servi. Chaque processus va au bout de son exécution avant de rendre la main, et la réactivité disparaît.
Très petit : les commutations deviennent si fréquentes que leur coût occupe une part importante du temps processeur. La machine s'agite sans avancer.
Le réglage cherche un quantum grand devant le coût d'une commutation, et petit devant le temps de réponse acceptable pour un utilisateur. Les valeurs employées se comptent en dizaines de millisecondes.
Pourquoi les systèmes modernes sont-ils préemptifs ?
Parce qu'en coopératif, un seul processus fautif fige la machine entière. Une boucle sans fin, un blocage sur une ressource, et le système ne peut plus reprendre la main puisqu'il attend que le processus la rende.
Le préemptif retire le processeur à l'expiration du quantum, quoi que fasse le processus. Un programme bloqué reste bloqué, mais les autres continuent.
Le coût est une complexité supplémentaire : puisqu'un processus peut être interrompu n'importe où, y compris au milieu d'une modification de données partagées, la synchronisation devient nécessaire. C'est le sujet du chapitre sur les threads.
Qu'est-ce que le vieillissement dans un ordonnancement par priorité ?
Un mécanisme qui augmente progressivement la priorité d'un processus resté longtemps en attente.
Il répond au défaut principal de l'ordonnancement par priorité : un processus de faible priorité peut ne jamais s'exécuter si des processus plus prioritaires arrivent continuellement.
Avec le vieillissement, l'attente finit par élever sa priorité au-dessus des nouveaux arrivants, ce qui garantit qu'il passera.
C'est le compromis habituel entre respecter une importance métier et garantir qu'aucun travail n'est indéfiniment écarté.
La méthode
- Distingue le programme du processus. Ce qui s'ordonnance est le second.
- Situe l'état avant de diagnostiquer une lenteur : prêt, actif ou bloqué.
- Compte le coût des commutations avant de conclure qu'un quantum plus court améliorerait les choses.
- Nomme le critère optimisé par un algorithme, et celui qu'il dégrade.
- Cherche la famine dans tout algorithme non équitable, et le vieillissement qui la corrige.
- Souviens-toi que le préemptif impose la synchronisation dès qu'il y a des données partagées.
En résumé
- Un programme est un fichier, un processus est une exécution avec son contexte.
- Le bloc de contrôle conserve PID, état, compteur ordinal, registres, pile, mémoire et fichiers ouverts.
- Trois états : prêt, actif, bloqué. Un processus bloqué n'est pas candidat à l'élection.
- La commutation de contexte coûte la sauvegarde des registres et l'invalidation des caches.
- Coopératif : le processus rend la main. Préemptif : le système la reprend.
- Premier arrivé est simple et sujet à l'effet convoi ; plus court d'abord minimise l'attente moyenne et peut affamer ; tourniquet est équitable et dégrade la moyenne.
- Les systèmes réels combinent files de priorités, tourniquet et vieillissement.
Et ensuite ? Un processus a besoin de mémoire, et le système doit la lui attribuer sans la donner deux fois ni la gaspiller. Le chapitre suivant traite de la gestion de la mémoire.