Chapitre 3 Du système d'exploitation au processus

3.1 Premiers essais

À l'époque des premiers ordinateurs, à la fin des années 1940, il n'y avait rien qui annonçât les systèmes d'exploitation. Maurice Vincent Wilkes a raconté le lancement et l'exécution du premier programme sur l'EDSAC : son texte était sous une forme tout à fait similaire au format binaire donné en exemple à la section ??. Chaque chiffre binaire était introduit manuellement à l'aide de commutateurs. Puis le programme se déroulait durant des dizaines d'heures, pour finalement afficher le résultat attendu (une table de nombres premiers en l'occurrence). On a vu comment l'invention des langages symboliques, puis d'autres niveaux de métalangages, allait simplifier les opérations de rédaction proprement dite du programme. Mais il fallait aussi faire des progrès sur la façon d'introduire programmes et données dans la machine et d'en extraire les résultats.

L'introduction manuelle des données était une perte de temps : un ingénieur qui travaillait dans l'équipe de Gene Amdahl (un des plus fameux architectes d'ordinateurs), Nathaniel Rochester, imagina au début des années 1950 de les enregistrer sur bande magnétique au préalable. Le premier ordinateur qui les utilisa, l'IBM 701, fut livré en 1953 au Department of Defense américain (DoD dans la suite de ce livre), ce qui illustre la tradition continue de financement des progrès de l'informatique sous l'impulsion des commandes militaires, ici celles de la guerre de Corée.

Cette utilisation des bandes magnétiques connut un nouveau développement avec l'IBM 704, livré fin 1955. Sur cette machine conçue par Gene Amdahl, l'ingénieur de General Motors Bob Patrick écrivit un programme qui enchaînait automatiquement entrée des données, calcul, impression des résultats, entrée des données, etc. L'IBM 704 fut d'ailleurs le support d'un nombre considérable d'innovations capitales¹.

Assez vite une constatation se fit jour : l'impression des résultats, à la cadence d'un télétype capable d'imprimer dix caractères par seconde, voire même leur écriture sur bande magnétique, pouvait prendre un temps aussi long que le calcul proprement dit, ce qui immobilisait la coûteuse unité centrale pour une tâche somme toute subalterne. Le mot « coûteuse » doit être replacé dans le contexte de l'époque : le prix du 704, avec sa mémoire de 4096 mots de 36 bits qui semblait énorme à l'époque (elle fut ensuite étendue à 32 768 mots, à comparer aux 128 millions de mots du plus petit ordinateur en vente aujourd'hui au supermarché le plus proche de votre domicile !), se chiffrait en millions de dollars de l'époque, et il n'y eut qu'une vingtaine d'exemplaires construits pour des clients fortunés tels que les militaires ou de grands centres de recherche comme le MIT (Massachusetts Institute of Technology).

Il aurait été possible de réduire la perte de temps due à l'impression des résultats en les écrivant provisoirement sur une mémoire auxiliaire électromagnétique (disque, bande, tambour...) beaucoup plus rapide qu'une imprimante, puis en les imprimant plus tard, pendant que l'unité centrale effectuerait d'autres calculs. Cela semblait possible parce que la tâche d'impression, ralentie par les opérations mécaniques de l'imprimante, n'utilisait les circuits de l'unité arithmétique et logique que fort peu, voire pas du tout si l'on avait pris soin d'enregistrer avec les résultats proprement dits des codes de commande destinés à l'électronique (rudimentaire) de l'imprimante pour indiquer les sauts de ligne, de page, etc.

La réalisation de cet objectif apparemment modeste nécessitait encore un peu de programmation : à la fin du programme de calcul il fallait qu'un programme déclenchât d'une part le démarrage du programme d'impression (destiné à vivre sa vie indépendamment), d'autre part le démarrage du programme de calcul suivant. Avant de lancer le programme d'impression il fallait aussi vérifier que l'impression des résultats précédents était bien terminée. Pendant qu'on y était, on procéderait à une optimisation analogue en autorisant le recouvrement entre le temps de calcul et le temps de lecture des données nécessaires au calcul suivant.

Il apparut vite assez logique de confier cette mission, organiser le recouvrement dans le temps de plusieurs activités, à un « méta-programme », nommé moniteur, chargé de déclencher à l'instant convenable l'exécution des programmes d'application, qui pourraient être considérés comme ses sous-programmes. Nous étions en 1955 et l'ancêtre des systèmes d'exploitation était né.

Nous allons décrire les traits marquants de l'évolution des systèmes à partir de cet ancêtre rudimentaire, mais auparavant il convient de préciser un peu notre vision de ce qu'est un programme : le chapitre 2 nous en a donné une vision statique, centrée sur le texte qui décrit l'algorithme, les sections qui suivent insistent sur l'aspect dynamique, ce qui se passe pendant l'exécution du programme.

3.2 Simultanéité et multiprogrammation

Nous avons annoncé au début du chapitre 2 que nous allions compléter notre définition du système d'exploitation par la capacité qu'il pourrait conférer à l'ordinateur par lui piloté de faire plusieurs choses à la fois. Or nous avons aussi mentionné comme une caractéristique essentielle de l'architecture de von Neumann que les ordinateurs exécutaient une et une seule instruction à la fois. S'agit-il là d'une contradiction ?

En fait, c'est le principe de von Neumann qui est exact, et le système d'exploitation ne procurera que l'illusion de la simultanéité, une pseudo-simultanéité², Devons-nous néanmoins acheter des ordinateurs aussi fallacieux ? Oui. En effet, le temps d'exécution d'une instruction câblée du processeur est très court, de l'ordre de la nano-seconde, ce qui procure plusieurs centaines de millions d'instructions par seconde, et ainsi une tranche de temps de quelques fractions de seconde, partagée entre plusieurs processus, donne à l'échelle macroscopique l'illusion de la simultanéité.

3.2.1 Chronologie d'une entrée-sortie

Voyons ce qui se passe lorsque l'utilisateur d'un ordinateur demande une opération macroscopique au logiciel qu'il utilise, par exemple « déplacer le curseur du traitement de texte à la fin de la ligne » :

Cette opération va peut-être demander l'exécution de plusieurs milliers d'instructions élémentaires, disons dix mille en étant large.
Le temps mis par l'utilisateur pour commander le déplacement du curseur vers la fin de la ligne sera, disons, d'un quart de seconde. Pour simplifier le modèle nous supposerons que l'opération est commandée par un raccourci au clavier qui « consomme » vingt mille instructions. (L'usage de la souris engendre des événements dont la détection et le traitement par le système sont complexes.)
Pour qu'aucun temps d'attente ne soit perceptible à l'utilisateur, ce qui produirait de l'inconfort, il faut que l'action, une fois commandée, soit effectuée dans un délai de deux centièmes de seconde (c'est ici encore très généreux).
Le budget des délais pour notre opération est donc le suivant : nous disposons tout d'abord de 0,25 seconde pour exécuter 20 000 instructions, puis de 0,02 seconde pour exécuter 10 000 instructions. Or si notre ordinateur peut exécuter 500 millions d'instructions par seconde, valeur banale en cette année 2002, nous voyons qu'il nous reste énormément de marge, puisqu'en 0,25 seconde il peut exécuter 125 millions d'instructions élémentaires, et en 0,02 seconde, 10 millions.
Le système d'exploitation va donc permettre l'exécution « pseudo-simultanée » de plusieurs programmes tels que celui que nous avons décrit :
- Nous avons dit qu'il fallait à l'utilisateur 0,25 seconde pour effectuer la commande par un raccourci au clavier : c'est plutôt vers la fin de ce délai que, les opérations manuelles terminées, le logiciel de traitement de texte (et en fait d'autres programmes liés notamment au gestionnaire de fenêtres, mais négligeons ces aspects pour l'instant) vont exécuter les 20 000 instructions nécessaires pour capter cette commande. Ces 20 000 instructions vont s'exécuter en 0,000 040 seconde, ce qui laisse pendant les opérations manuelles (ou plus exactement digitales) un temps inoccupé de 0,249 960 seconde, disponible pour l'exécution de 124 980 000 instructions appartenant à d'autres programmes.
- De la même façon, nous voyons que les 10 000 instructions nécessaires pour envoyer le curseur en bout de ligne vont laisser pendant le délai de 0,02 seconde que nous nous sommes imposé pour le confort de notre utilisateur bien-aimé un temps libre suffisant pour exécuter 9 990 000 instructions au profit d'autres programmes, dits « programmes concomitants » (en anglais concurrent, ou si l'on veut concurrents pour l'accès au temps de processeur).

3.3 Notion de processus

De la section précédente nous pouvons déduire la notion de processus : le rôle du système d'exploitation sera de distribuer harmonieusement le temps disponible (de façon pléthorique semble-t-il d'après l'exemple ci-dessus) entre différents programmes en train de s'exécuter « pseudo--simultanément ». Lorsque l'on considère des programmes sous l'angle de leur concurrence pour l'accès au temps du processeur, nous les appellerons des processus. L'arbitrage de la répartition du temps entre les processus est la fonction fondamentale du système d'exploitation, c'est une fonction, bien sûr, de « bas niveau », qui relève des « couches basses ».

La capacité pour le système d'exploitation d'organiser le partage des ressources entre plusieurs processus concomitants qui s'exécutent en pseudo--simultanéité s'appelle la multiprogrammation.

Nous pouvons emprunter à Andrew Tanenbaum [68] la métaphore du pâtissier qui prépare deux gâteaux : le programme, c'est la recette du gâteau, c'est la même pour les deux gâteaux, elle décrit des actions qui, dans le livre de cuisine, sont à l'état abstrait. Le processus, c'est la suite d'actions effectives qui va mener à la réalisation d'un gâteau concret. Pour aboutir, le processus « gâteau numéro 1 » doit se voir attribuer un certain nombre de ressources : farine, oeufs, sucre, un certain laps du temps du pâtissier, une certaine période de disponibilité du rouleau à pâtisserie, une certaine durée de cuison dans le four. Certaines contraintes doivent être respectées : le rouleau et la planche à pâtisserie doivent être affectés au processus « gâteau numéro 1 » en même temps, et avant l'affectation du four. Nous supposerons que le four ne peut contenir qu'un seul gâteau à la fois, de même que le processeur d'un ordinateur ne peut exécuter qu'une instruction à la fois. Les oeufs, le sucre et la farine de gâteau 1 sont bien entendus distincts de ceux de gâteau 2.

Pour préparer ses gâteaux, le pâtissier a le choix entre deux méthodes : préparer d'abord l'un, jusqu'à la fin du processus, puis l'autre, ou bien mener de front la confection des deux gâteaux, en se consacrant alternativement à l'un, puis à l'autre, ce qui permettra par exemple de rouler la pâte de gâteau 1 pendant que celle de gâteau 2 repose. La seconde méthode permettra sans doute de servir plus rapidement le client du second gâteau, sans trop retarder la livraison du premier, mais il y faudra plus d'organisation et de coordination. Ainsi, lorsque le pâtissier passera du gâteau 1 au gâteau 2, il faudra qu'il note (ne serait-ce que dans sa mémoire) certaines informations sur l'état du processus gâteau 1 : a-t-il déjà mis du sucre, ou pas ? Ce qui revient à cocher au crayon à quel endroit du texte de la recette il s'est interrompu dans le processus gâteau 1 pour passer au processus gâteau 2.

En procédant ainsi, le pâtissier réalise deux gâteaux en « pseudo- simultanéité », ce qui permettra à ses deux clients d'être servis à temps pour le dessert.

Nous avons déjà vu à la page ?? un moyen qu'ont les ordinateurs de noter où ils en sont dans un processus : le compteur ordinal, ou compteur de programme, nommé en abrégé PC (program counter), qui indique à chaque pas du programme l'adresse de l'instruction suivante à exécuter, et qui souvent fait partie du mot d'état de programme. Eh bien le PC sert aussi à cela : pour savoir où on en est dans le processus gâteau 1 au moment où on va l'abandonner pour s'occuper de gâteau 2, on note quelque-part la valeur du PC. Nous entrerons plus en détail dans la description de ces mécanismes, plus particulièrement aux sections 3.7 et 3.11, ce qui précisera notamment la position de ce quelque-part où est notée la valeur du PC.

3.4 Réification du calcul

Nous avons vu à la section ?? que les deux principes à la clé de l'architecture de von Neumann étaient l'exécution séquentielle et le partage d'une mémoire unique pour les instructions et les données du calcul. Cette réunion du programme et des données permet de considérer le programme comme de l'information, au même titre que les données, et cela a des conséquences énormes en termes de raisonnement sur les programmes, de transformations appliquées à des programmes par d'autres programmes, de traduction de programmes, pour tout dire cela permet le concept de programme.

Mais avant que la pensée en son mouvement réunisse données et programme elle avait dû apprendre à les distinguer. En effet pour le mathématicien traditionnel la question de cette distinction n'existe pas, c'est un problème qui n'a pas lieu.

L'idée de réification du processus de calcul apparaît avec Babbage, dont la machine analytique devait comporter une unité de contrôle constituée de cylindres à picots, une unité de calcul (le « moulin »), une mémoire centrale (le « magasin »), un système d'entrées-sorties de données sur carton perforé emprunté aux orgues de barbarie, et enfin un dispositif de circulation de données par tringles à crémaillère. Incidemment, nous voyons ici une autre idée fondamentale de Babbage, la distinction entre unité de contrôle et unité de calcul, la première supervisant l'exécution des opérations de la seconde, ce qui permet d'assurer un de nos postulats de départ : en fonction du résultat d'une opération de calcul, l'unité de contrôle pourra rompre la séquence d'exécution des instructions pour commander un branchement vers une instruction située plus loin dans le texte du programme, ou au contraire un retour en arrière pour répéter une séquence déjà effectuée.

Par données enregistrées sur carton perforé nous entendons aussi les programmes, et Lady Ada Lovelace, fille du poète Byron, mécène de Babbage et d'autres hommes de science anglais tels que Faraday et figure intellectuelle importante de son époque, a rédigé les premiers textes de programmes de l'histoire. C'est en son honneur que le langage de programmation Ada a été ainsi nommé³.

Les logiciens de la première moitié du XX siècle abordent le problème de la réification de façon plus abstraite, sur les traces de Leibniz, par les systèmes formels. Kurt Gödel et à sa suite Alan Turing avaient dû inventer des notations pour désigner des procédures effectives, les transformer, leur faire subir des traitements. Alonzo Church réunit ces idées en un formalisme qui aujourd'hui encore satisfait théoriciens et praticiens de la programmation, le l-calcul. En 1956 John MacCarthy élabore à partir du l-calcul un langage de programmation, LISP, pour lequel il implémente à partir de 1958 un traducteur sur l'IBM 704.

Le l-calcul se distingue des autres notations mathématiques en ceci que les fonctions y sont des objets comme les autres, susceptibles d'être traités comme des variables d'autres fonctions ou comme des termes d'expressions, des l-termes dans des l-expressions. Pour cette raison LISP est appelé un langage fonctionnel, ou encore un langage applicatif, puisqu'aussi bien le propre d'une fonction est de pouvoir être appliquée à des arguments.

3.5 Notion de sous-programme

À ce stade de l'exposé il convient d'exposer une notion d'une importance théorique et pratique cruciale, la notion de sous-programme, par quoi il est possible de diviser la difficulté de rédaction d'un programme en le découpant en plusieurs programmes plus simples.

Un programme significatif représente un texte d'une longueur respectable (par exemple 10 000 lignes), et il faut organiser ce volume d'information pour que les humains qui l'écrivent et le modifient puissent s'y retrouver. Un moyen très général et simple est d'avoir un programme principal qui joue en quelque sorte le rôle de table des matières et qui transfère le contrôle à des sous-programmes chargés de telle ou telle fonction particulière, eux-mêmes découpés en sous-programmes plus petits, etc. Ce transfert de contrôle est nommé « appel de sous-programme » (ou de fonction, ou de procédure, voire de méthode, ces mots désignent des objets similaires dans le contexte envisagé ici). Il faut garder à l'esprit qu'il s'agit essentiellement d'organiser l'information constituée par le texte du programme à l'usage du lecteur humain ; une fois traduit en langage machine il restera une suite monolithique de 0 et de 1.

Quand un programme appelle un sous-programme⁴ il doit lui transmettre des informations : supposons que je dispose d'un sous-programme pour le calcul du cosinus d'un angle ; je vais l'utiliser chaque fois que dans mon travail j'aurai un angle dont j'ai besoin de connaître le cosinus ; il faudra que je transfère au sous-programme la valeur de l'angle, c'est l'argument ou le paramètre de mon sous-programme ; il faut aussi que le sous-programme connaisse deux autres choses, l'adresse à laquelle transférer le contrôle quand il aura fini, dite adresse de retour, et l'adresse où déposer le résultat afin que le programme appelant puisse en prendre connaissance.

Un sous-programme peut être écrit par la même personne que le programme principal, et ils seront assemblés en un tout par un programme spécial, l'éditeur de liens. Un progamme écrit et compilé par nous utilise en fait d'autres programmes fournis par le système d'exploitation, par exemple pour communiquer avec le système, ou par le compilateur. Ces programmes sont dans des bibliothèques, qui sont des fichiers qui contiennent des programmes déjà tout prêts à l'usage. Au moment de l'édition de liens, soit ils sont inclus dans le fichier exécutable (édition de liens statique), soit l'éditeur de liens place dans le fichier exécutable une référence vers leur emplacement dans une bibliothèque partageable (édition de liens dynamique) et c'est au moment du chargement que les références qui permettent la liaison entre ces différents éléments de programmes seront établies par un programme ad hoc nommé chargeur ou, par exemple sous Linux, interpréteur de programmes.

Observons qu'isoler une fonction particulière dans un sous-programme qui sera désigné par un nom particulier (par exemple sinus pour le programme de calcul du sinus d'un angle) revient à créer une méta-instruction qui enrichit notre langage de programmation. Les langages issus du l-calcul tels que LISP et Scheme se prêtent particulièrement bien à ce processus d'enrichissement par abstraction de fonctions.

3.6 Points de vue sur les programmes

Nous commençons à avoir une idée de ce qu'est un programme : arrêtons-nous sur les différentes façons de l'envisager :

Comme la description d'un algorithme sous une forme exécutable en machine : c'est le point de vue du programmeur, que nous avons principalement envisagé jusqu'à maintenant.
Comme de l'information sous forme de données en mémoire : c'est le point de vue « métalinguistique » de l'auteur de compilateur, qui doit traduire le texte du programme vers un langage de plus bas niveau et, ultima ratio, en langage machine.
Comme un processus en cours d'exécution et qui à ce titre utilise les ressources de l'ordinateur : mémoire, temps de processeur, dispositifs d'entrée-sortie ; c'est principalement le point de vue du système d'exploitation. Inversement, le processus peut être vu comme le contexte d'exécution du programme.
Enfin le programme a une existence matérielle sous la forme d'un fichier binaire exécutable stocké quelque part sur une mémoire auxiliaire : c'est un point de vue que nous développerons à la section 3.10 et au chapitre 5.

= .9@percent

3.7 Vision dynamique du programme : le processus

= .15@percent

Le programme, du point de vue du système, est une entité active qui consomme des ressources, et qui pour les obtenir entre en concurrence avec d'autres demandes. Le programme vu sous cet angle est appelé un processus, process en anglais (le terme tâche, task en anglais, est parfois employé, dans les sources du noyau Linux par exemple). Ainsi, si à un instant donné quinze personnes utilisent l'éditeur de texte Xemacs sur le même ordinateur, il y aura quinze processus différents, même s'ils partagent la même copie du programme en mémoire (rappelons-nous la métaphore du pâtissier et des gâteaux, ci-dessus page ??), qui nous a permis d'introduire cette notion de processus).

Le système d'exploitation (operating system, OS) est un programme qui arbitre les demandes de ressources des différents processus et les satisfait en se conformant à une stratégie. La stratégie mise en oeuvre par le système vise à satisfaire plusieurs impératifs :

assurer le fonctionnement correct de l'ordinateur, et donc du système lui-même : une allocation incohérente de ressources cruciales comme le temps de processeur ou la mémoire peut provoquer un blocage ou un arrêt complet du système ;
distribuer les ressources de telle sorte que tous les processus « correctement configurés » en reçoivent une allocation suffisante pour s'exécuter « normalement » ;
corollaire des deux points précédents : empêcher qu'un processus « pathologique » n'accapare des ressources cruciales et ne réduise les autres à la « famine » ;
assurer à chaque processus la jouissance paisible des ressources qu'il leur a allouées, et pour cela établir une protection étanche entre les domaines des différents processus, tout en leur permettant de communiquer entre eux s'ils ont été programmés à cet effet. En d'autres termes, c'est au système d'exploitation que revient d'assurer la sécurité de l'ensemble du système informatique.

Le processus réunit deux types d'attributs : certains sont de nature plutôt statique, ce sont les ressources utilisées (espace mémoire, fichiers ouverts), et d'autre plutôt dynamiques, c'est essentiellement ce que nous pouvons appeler un « fil » d'exécution pour un programme, au sens où l'on dit « le fil de la conversation ». Une tendance récente des architectes de systèmes vise à séparer les deux types d'attributs, en considérant le processus comme un ensemble de ressources qu'utilisent un ou plusieurs fils d'exécution. L'ambiguïté du pluriel de fil en français nous conduit à traduire le terme anglais thread par activité. Nous étudierons dans ce chapitre le processus au sens classique. L'étude des activités nécessite l'examen préalable des différents types de ressources à partager, elle trouvera sa place au chapitre 10 page ??.

3.8 Attributs du système d'exploitation

Quelles doivent être les caractéristiques d'un système d'exploitation, propres à mettre en oeuvre la stratégie décrite ci-dessus ? Avant de répondre trop hâtivement à cette question il convient de s'armer de relativisme. Le système d'exploitation des gros ordinateurs centralisés qui ont connu leur apogée pendant les années 1970 ne peut sans doute pas ressembler à celui qui habite dans votre téléphone portable. Moyennant quoi l'examen des systèmes produits du milieu des années 1960 à l'orée des années 2000 révèle une grande stabilité des idées qui ont guidé les réponses aux questions de la section précédente malgré une grande variété d'interfaces personne--ordinateur. C'est sans doute qu'il n'est pas si simple d'imaginer d'autres solutions, ou bien que celles qui se sont dégagées à l'issue des premières expériences se sont révélées assez satisfaisantes dans une grande variété de contextes.

3.8.1 Mode d'exécution privilégié

De ce qui précède découle que le système d'exploitation doit pouvoir faire des choses que les programmes ordinaires ne peuvent pas faire (les programmes ordinaires ne doivent pas pouvoir faire les mêmes choses que le système). Ceci est généralement réalisé par le processeur, qui distingue deux modes d'exécution des instructions : le mode privilégié et le mode normal. Certaines opérations ne sont accessibles qu'au mode privilégié. Nous verrons que certains systèmes ont raffiné cette hiérarchie de modes d'exécution avec plusieurs niveaux de privilèges. Le mode privilégié est aussi appelé mode superviseur, ou mode noyau.

3.8.2 Contrôle des programmes

Lorsque l'on veut exécuter un programme sur un ordinateur piloté par un système d'exploitation, c'est à lui que l'on en demande le lancement. Nous décrirons ce processus plus en détail à la section 3.10 ci-dessous.

3.8.3 Contrôle de l'activité de tous les processus

À partir du moment où le système, premier programme à s'exécuter après le démarrage de l'ordinateur, s'est octroyé le mode d'exécution privilégié, et comme c'est lui qui va lancer les autres programmes, il lui est loisible de leur donner le niveau de privilèges qu'il juge nécessaire, et qui sera sauf exception le mode normal. Il peut également interrompre un programme en cours d'exécution, il contrôle les communications entre processus et empêche toute promiscuité non désirée⁵.

3.8.4 Monopole d'attribution des ressources

C'est le système et lui seul qui attribue aux différents processus les ressources dont ils ont besoin, mémoire, temps de processeur, accès aux entrées-sorties. En effet sans ce monopole plusieurs entités pourraient rivaliser pour l'octroi de ressources, de quoi pourrait résulter une situation de blocage. Même avec le monopole du système les situations de blocage entre processus peuvent advenir, mais elles sont plus rares et plus souvent solubles par le système. À titre d'illustration nous allons décrire une situation classique d'interblocage, l'« étreinte fatale ».

Étreinte fatale

Un groupe de processus P₁, P₂, ... P_n est dit en situation d'étreinte fatale si chaque processus P_i est bloqué en attente d'une ressource détenue par un processus P_j différent. Comme aucun processus n'est en mesure de progresser dans son exécution, aucun ne pourra atteindre le point où il libérerait la ressource attendue par un autre, et la situation est donc fatale, sauf si une entité extérieure est en mesure d'intervenir pour interrompre un des processus en espérant débloquer tous les autres en chaîne. Le diagramme du tableau 3.1 illustre le phénomène avec deux processus seulement.

Processus P₁ Processus P₂

... ...

Allocation de la ressource A ...

... Allocation de la ressource B

... ...

Tentative d'allocation de la ...

ressource B : échec, blocage ...

... ...

... Tentative d'allocation de la

... ressource A : échec, blocage

... ...

Libération de la ressource A : ...

hélas P₁ n'arrivera jamais là. ...

... ...

... Libération de la ressource B :

... P₂ n'y arrivera pas.

Table 3.1 : Étreinte fatale (l'axe du temps est vertical de haut en bas)

3.8.5 Contrôle de la mémoire

De toutes les ressources, la mémoire est la plus cruciale, sans mémoire aucune information ne peut exister dans l'ordinateur, et bien sûr le système a le monopole de son allocation, de sa protection et de sa libération. Rien ne serait plus grave que l'empiètement d'un processus sur une zone mémoire allouée à un autre, et c'est ce qui arriverait sans une instance unique de contrôle.

Dans le cas de la multiprogrammation (voir section 3.2) le partage de la mémoire entre les processus est une fonction essentielle du système d'exploitation.

3.8.6 Contrôle des entrées-sorties

L'accès aux dispositifs d'entrée-sortie est un type de ressource parmi d'autres, et à ce titre le système doit en posséder le contrôle exclusif, quitte à déléguer ce contrôle à un processus dans certains cas particuliers. La règle générale est qu'un processus qui veut effectuer une opération d'entrée-sortie (recevoir un caractère tapé sur le clavier, afficher un caractère à l'écran, écrire un bloc de données sur disque...) adresse une demande au système, qui réalise l'opération pour son compte. Ainsi est assuré le maintien de la cohérence entre les multiples opérations, et évitée l'occurrence d'étreintes fatales. Comment le système d'exploitation s'y prend-il pour orchestrer le fonctionnement coordonné de multiples appareils d'entrée-sortie sans conflits ni perte de temps ? Nous le verrons plus loin.

Comme conséquence (ou contre-partie) de ce monopole des entrée-sorties, le système en procure aux autres processus une vue abstraite et simplifiée.

3.8.7 Contrôle du temps

Le système maintient une base de temps unique pour tous les processus et fournit des services de gestion du temps aux processus qui le demandent : estampillage, chronologie, attente, réveil...

3.8.8 Contrôle de l'arrêt et du démarrage de l'ordinateur

Nous savons déjà que le système d'exploitation est le premier programme à recevoir le contrôle lors du démarrage de la machine. Il doit aussi recevoir le contrôle de l'arrêt de l'ordinateur, du moins quand c'est possible. Lorsqu'il reçoit une commande d'arrêt, le système veille à terminer les entrées-sorties en cours et à arrêter proprement les processus encore en cours d'exécution. Quand cela n'est pas fait, par exemple lors d'une coupure de courant, certains supports de données externes peuvent rester dans un état incohérent, avec le risque de destruction de données.

3.9 Notion d'appel système

Pour mettre en oeuvre les principes énumérés ci-dessus le système d'exploitation reçoit le monopole de certaines opérations, dites opérations privilégiées : allouer des ressources, déclencher et contrôler des opérations d'entrée-sortie, d'autres que nous verrons ultérieurement. Mais les programmes ordinaires risquent d'être singulièrement limités si par exemple ils ne peuvent pas faire d'entrées-sorties : il n'y aurait par exemple plus de logiciel de traitement de texte possible parce qu'il ne serait autorisé ni à recevoir le texte frappé au clavier par l'utilisateur, ni à l'afficher à l'écran, ni à l'imprimer. Et nous savons bien qu'il existe effectivement des logiciels de traitement de texte qui font tout cela. Comment ? Je vais vous le narrer.

Lorsqu'un processus ordinaire a besoin d'effectuer une opération privilégiée il demande au système d'exploitation de la réaliser pour son compte, et éventuellement de lui renvoyer le résultat. Cette demande de service est nommée un appel système. Les opérations privilégiées sont considérées comme autant de primitives du système d'exploitation, qui peuvent être invoquées par les programmes ordinaires pourvu qu'ils soient dotés des autorisations adéquates. Signalons par exemple, pour Unix :

fork, pour créer un processus ;
kill, pour détruire un processus ;
exec, pour charger un programme en mémoire ;
signal, qui permet à un processus de signaler un événement à un autre processus ;
read, pour lire des données ;
write, pour écrire des données ;
brk, pour allouer ou libérer une zone de mémoire dynamiquement.

3.10 Lancement d'un programme

Nous prendrons l'exemple du système Unix. Unix distingue nettement les notions de processus, considéré comme le contexte d'exécution du programme, et le programme lui-même, constitué du texte exécutable en langage machine. Le lancement de l'exécution d'un programme comportera donc deux opérations : la création d'un processus par l'appel système fork et le chargement par l'appel système exec du programme qui va s'exécuter dans le contexte de ce processus. exec est une forme générale parfois spécialisée sous le nom execve.

Nous allons décrire les événements qui se déroulent après l'amorçage du système et le démarrage du noyau qui ont fait l'objet de la section ??. Nous prendrons l'exemple d'Unix, qui crée des processus avec l'appel système fork. fork procède par clonage : le processus fils reçoit au départ une copie de l'environnement du processus père, et c'est exec qui va constituer ensuite son environnement propre.

Au commencement, le noyau lance le premier processus qui se déroule en mode utilisateur et dans l'espace mémoire réservé aux utilisateurs : il s'appelle init. init lance par l'appel système fork divers processus système utilitaires, puis (toujours par fork) une copie de lui-même associée à chaque terminal destiné aux connexions des utilisateurs. Ces clones d'init vont déclencher la procédure d'identification par nom identifiant et mot de passe des utilisateurs qui se connectent⁶. Une fois l'identité authentifiée, le programme login utilise l'appel système execve pour charger en mémoire un interpréteur de commandes de l'utilisateur, ce que l'on nomme un shell. Le shell va prendre en mémoire la place de login et permettre à l'utilisateur d'interagir avec le système d'exploitation ; ce programme mérite que l'on s'y arrête un instant.

3.10.1 Shell

Cette section est consacrée au programme qui est l'intermédiaire principal entre l'utilisateur et le système Unix. C'est à la fois un interpréteur de commandes qui permet le dialogue avec le système et le lancement de programmes, et un langage de programmation. On peut écrire en shell des programmes appelés shell scripts constitués de séquences de commandes agrémentées de constructions telles qu'alternative ou répétition, ce qui permet d'automatiser des tâches répétitives. Ces programmes ne sont pas compilés (traduits une fois pour toutes), mais interprétés, c'est-à-dire que le shell traduit et exécute les commandes une à une comme si l'utilisateur les tapait sur son clavier au fur et à mesure. L'utilisateur a ainsi l'illusion d'avoir affaire à une machine virtuelle dont le langage machine serait celui du shell.

Incidemment, alors que Unix est né en 1969, le shell est plus ancien : il a été inventé en 1963 lors de la réalisation du système d'exploitation CTSS au Massachusetts Institute of Technology par Louis Pouzin, ingénieur français qui s'est également illustré en 1970 à la direction du projet de réseau Cyclades, où il inventa notamment le datagramme. CTSS, dont le développement commença en 1961 sous la direction de Fernando Corbató au MIT sur IBM 709, puis 7090, fut un système d'une grande importance par le nombre de notions, de techniques et de réalisations novatrices qu'il apportait. Ce fut le premier système à temps partagé, c'est-à-dire qu'il permettait l'usage simultané de l'ordinateur par plusieurs utilisateurs qui entraient des commandes et lançaient des programmes depuis des terminaux, en utilisant la disproportion entre le temps de calcul de la machine et le temps de réaction humain telle qu'expliqué à la section 3.2.1.

Après CTSS, Corbató prit la tête du projet MAC⁷ ⁸ qui donna naissance au système d'exploitation Multics sur General Electric GE-645, toujours au MIT. Ces systèmes ont inspiré les auteurs de Unix, tant par ce qu'ils en ont retenu que par ce qu'ils en ont rejeté d'ailleurs. Nous y reviendrons.

De CTSS le shell passa en 1964 à son successeur Multics, et de là à Unix. L'utilisateur d'Unix a d'ailleurs le choix entre plusieurs shells qui diffèrent par le style plus que par les fonctions. La souplesse et la programmabilité du shell sont pour beaucoup dans la prédilection que les développeurs professionnels ont pour Unix. Les utilisateurs moins spécialisés ont tendance à lui préférer les interfaces graphiques interactives offertes par le Macintosh ou Windows, et d'ailleurs disponibles également sous Unix grâce au système de fenêtres X complété plus récemment par des environnements graphiques tels que Gnome ou KDE. Mais pour un utilisateur quotidien taper des commandes au clavier est plus rapide que de cliquer avec une souris, et surtout ces commandes peuvent être enregistrées pour devenir des shell scripts, ce qui assure programmabilité, mémorisation et reproductibilité des actions. Avez-vous déjà essayé de vous rappeler quelle séquence de coups de souris avait produit tel résultat subtil et ardemment désiré dans Word ? ou de dicter au téléphone une telle séquence à un collègue (sauf dans le cas où il est devant son écran et peut effectuer les actions au fur et à mesure de la dictée) ? Tandis qu'une série de commandes du shell, cela s'envoie par courrier électronique de façon sûre.

Bref, muni du shell, rien n'est plus simple à l'utilisateur que de lancer un programme : il suffit de taper le nom du fichier binaire exécutable qui en contient le texte en langage machine, éventuellement suivi de quelques paramètres, puis un retour chariot et l'exécution commence... Il y aura création d'un nouveau processus pour ce programme, un processus en général fils du processus lié au shell. Unix procure aussi des moyens de lancer l'exécution d'un programme en l'absence d'un humain pour taper la commande, mais le principe reste le même.

3.11 Synchronisation de processus, interruption

Nous avons dit que le système d'exploitation, avec l'aide de dispositifs appropriés du matériel, pouvait répartir le temps de processeur entre plusieurs processus pseudo--simultanés. Ceci suppose qu'un processus, à un instant donné, puisse être dans l'état actif, à un instant suivant dans l'état dormant (en attente), puis encore à un autre instant redémarrer, c'est-à-dire passer de l'état dormant à l'état actif.

Nous pouvons concevoir qu'un processus actif se mette volontairement à l'état dormant. En revanche le passage de l'état dormant à l'état actif suppose l'intervention du système d'exploitation ou d'un autre processus pour réveiller le processus endormi. Comment cela peut-il se passer ? Nous allons pour l'exposer prendre un exemple particulièrement significatif et qui découle de la section 3.2 ci-dessus : le déroulement d'une opération d'entrée-sortie, lecture ou écriture sur support externe.

3.11.1 Demande d'entrée-sortie

Les opérations d'entrée-sortie, nous l'avons vu, sont des opérations privilégiées, du monopole du système d'exploitation. Lorsqu'un logiciel veut effectuer une entrée-sortie il doit effectuer un appel système. Pour réaliser cette opération d'entrée-sortie (universellement désignée par IO, comme input-output, E/S en français), plusieurs composants de l'ordinateur et du système entrent en jeu :

Le programme effectue un appel système.
Le système exécute un programme spécial, dit pilote de périphérique (driver), qui transmet la demande au contrôleur de périphérique. Le contrôleur est un circuit de commande du périphérique physique, qui dans le cas des disques durs est un véritable petit ordinateur spécialisé doté de mémoire pour le stockage des données en transit et de capacités de multiprogrammation pour conduire plusieurs disques simultanément.
Le périphérique physique effectue l'action réelle : lire, écrire, enregistrer, imprimer, émettre un son... Puis il prévient le contrôleur quand il a fini en émettant un signal particulier sur un fil particulier. La durée de l'action du périphérique mécanique, nous l'avons vu, est beaucoup plus longue que toutes les actions des composants électroniques : de l'ordre de 100 000 fois plus longue pour une écriture sur disque.

Comment cela finit-il ? Nous allons le voir. Le diagramme des opérations est décrit par la figure 3.1.

Figure 3.1 : Diagramme d'une opération d'entrée-sortie (E/S)

Le haut de ce diagramme correspond aux étapes initiales d'une opération d'entrée-sortie, elles sont compréhensibles avec les notions que nous possédons déjà :

Le programme s'exécute normalement, puis il émet une demande d'entrée-sortie (un appel système).
Immédiatement après la demande d'entrée-sortie⁹ le programme se met volontairement en attente, en sommeil. La mise en sommeil se fait par un appel système qui transfère le contrôle au superviseur après avoir sauvegardé en mémoire le contexte d'exécution du processus (PSW, registres).
Pour que cette mise en sommeil ne soit pas définitive il faut prévoir un mécanisme de réveil. En effet un programme qui s'est arrêté ne pourra pas se remettre en action spontanément. On pourrait imaginer un hôtel où chaque client avant de se coucher accrocherait à l'extérieur de sa chambre une petite fiche où il aurait écrit l'heure à laquelle il souhaite être réveillé et ce qu'il veut manger à son petit déjeuner. Au matin, l'employé d'étage effectue une ronde périodique dans le couloir, consulte les fiches et réveille les clients dont le temps de sommeil est expiré. Dans notre cas l'appel système (sleep ou wait selon les cas) place à un endroit connu du système les informations qui permettront, lorsque l'E/S sera terminée, de savoir quel processus réveiller et quelle information lui donner. Sinon on ne saurait jamais établir le lien entre le résultat de l'entrée-sortie et le programme qui l'avait demandée, et celui-ci ne pourrait jamais reprendre son exécution. Un tel ensemble d'informations est appelé une structure de données. Son adresse est mentionnée par une toute petite structure appelée, par exemple, bloc de contrôle d'événement (ECB, Event Control Block) dans les systèmes OS/360.
La demande d'entrée-sortie est prise en charge par le système, qui s'empresse de la mettre en file d'attente. Sur un système en multiprogrammation les demandes d'entrée-sortie sont en effet multiples et il faut y mettre un ordre.
La partie du système chargée de traiter les demandes d'entrée-sortie va, plus tard, extraire notre demande de la file et la traiter, soit en bref la transmettre au contrôleur, qui la transmettra au périphérique physique. Et là commencera le délai, incommensurablement long au regard de ce qui précède, nécessaire à l'action elle-même.

3.11.2 Interruption de fin d'entrée-sortie

Puis l'entrée-sortie suit son cours, et viendra le moment où le périphérique (disque dur, clavier, écran...) aura fini son travail. Comment le signaler au programme interrompu ? Celui-ci est dormant, il ne peut recevoir d'information. Il faut donc passer par l'intermédiaire du système d'exploitation.

À l'issue du délai considérable durant lequel le périphérique a travaillé, il envoie au contrôleur un signal pour le prévenir, quelques informations qui constituent un compte-rendu d'exécution de la tâche, et éventuellement les données qui lui étaient demandées, si par exemple il s'agissait d'une lecture de données sur un disque. Voyons la suite des opérations, pour laquelle nous allons supposer qu'il s'agit précisément d'une lecture sur disque.

Quand le contrôleur a reçu la demande d'entrée-sortie, elle contenait un certain nombre de renseignements, notamment l'adresse de la zone de mémoire où il faut déposer les données résultant de la lecture. Il place donc les données à l'emplacement convenu.
Comment le contrôleur place-t-il les données en mémoire ? Par où passent-elles ? Par le bus. Le bus comporte des lignes de données et des lignes de signalisation (ou de commande). Les lignes de signalisation permettent aux différents éléments de l'ordinateur de coordonner leurs actions, d'échanger des commandes ; les lignes de données leur permettent d'échanger, donc, des données. Le contrôleur sait accéder à la mémoire et sélectionner la bonne adresse.
Une fois les données placées au bon endroit en mémoire, il faut prévenir le processeur. À cette fin le contrôleur envoie sur une ligne de signalisation particulière un signal qui va déclencher une interruption du processeur. L'interruption est un mécanisme capital pour la synchronisation des ordinateurs, nous allons en exposer le principe.
Le signal d'interruption a deux effets :
- il interrompt, donc, le programme en cours d'exécution ;
- le PSW courant (cf. section ?? pour la définition du PSW et du PC) est sauvegardé en mémoire et remplacé par un nouveau PSW qui comporte une valeur de PC qui pointe vers une section particulière du système, le superviseur d'interruption ; c'est donc ici que va se continuer l'exécution.
La première chose que fait le superviseur d'interruption est de déterminer la nature de l'interruption. Ici le signal lui donne la réponse : interruption d'entrée-sortie, mais il y a d'autres types (interruption volontaire par appel système, interruption déclenchée par l'horloge interne, interruption provoquée par une condition particulière de programme comme dépassement de capacité numérique...). Il se débranche donc à la section appropriée, le superviseur d'interruption d'entrée-sorties.

Le traitement des interruptions et le transfert du contrôle à la section adéquate du superviseur ou du noyau sont des éléments de l'architecture de l'ordinateur et du système d'exploitation cruciaux pour les performances et les possibilités de l'ensemble. Les éléments matériels et logiciels sont étroitement associés. Nous avons décrit une réalisation possible. Il en existe d'autres, par exemple l'architecture Intel IA-64 utilise un vecteur d'interruptions : chaque élément matériel ou logiciel du système susceptible de déclencher une interruption, et notamment chaque contrôleur de périphérique, est associé à une structure de données résidant à une adresse en mémoire fixée au démarrage du système et qui contient elle-même l'adresse de la section appropriée du superviseur. L'ensemble de ces adresses constitue le vecteur d'interruptions. L'occurrence d'une interruption provenant de tel contrôleur déclenche automatiquement le transfert du contrôle à l'adresse correspondante, qui pointe sur la section appropriée du superviseur. Ce dispositif, dit de vectorisation des interruptions, est apparu sur les ordinateurs PDP 11 de Digital Equipment.

Une fois le contrôle transféré au superviseur d'interruption d'entrée-sortie, celui-ci retouve dans ses tables la référence du drapeau associé à la demande d'entrée-sortie concernée, par là il retrouve la structure de données qui la décrit, puis le processus dormant qui l'avait émise.
Le superviseur fait passer le processus émetteur de l'état dormant à l'état dispatchable ou prêt, c'est-à-dire candidat à redevenir actif, éligible pour l'exécution.
Le superviseur d'interruptions passe ensuite la main à une autre partie du système, l'ordonnanceur, ou programmateur (en anglais scheduler).

3.12 Ordonnancement de processus

Les systèmes que nous envisageons permetttent la multi-programmation, c'est-à-dire que plusieurs processus sont à un moment donné en concurrence pour disposer du processeur, dont on rappelle qu'en vertu de l'architecture de von Neumann il exécute une seule instruction à la fois¹⁰. Pour permettre cette concurrence, aux deux sens du terme, commercial et étymologique, il faut que le système soit capable de retirer le contrôle du processeur à un processus pour le donner à un autre. La partie du noyau du système qui fait cela est l'ordonnanceur ou programmateur (en anglais scheduler).

L'ordonnanceur reçoit la main à un moment où tous les processus sont dans l'état d'attente. Certains sont prêts (éligibles) pour l'exécution (dispatchable), c'est-à-dire qu'ils ne sont pas en attente d'un événement tel qu'une fin d'entrée-sortie ou l'expiration d'un délai, et qu'ils n'attendent que le feu vert pour recommencer à s'exécuter. D'autres sont à l'état dormant, par exemple en attente sur un drapeau. Le rôle de l'ordonnanceur est de sélectionner parmi les processus prêts celui qui va être activé. La méthode de sélection peut dépendre de plusieurs paramètres : délai d'attente déjà écoulé pour chaque processus, niveau de priorité, etc. Puis l'ordonnanceur passe la main au distributeur (en anglais dispatcher), qui remet effectivement en activité le processus sélectionné en restaurant son contexte d'exécution (PSW, registres). C'est sur ce processus complexe que s'appuie l'exemple de la figure 3.1.

Cette description du traitement d'entrée-sortie nous a amené à préciser notre vision de la gestion des processus et à comprendre le fonctionnement effectif de la multiprogrammation. Tout programme réel interagit avec le monde extérieur par des entrées-sorties ; ce faisant, nous venons de le voir, il se met en attente d'un résultat d'entrée-sortie, et par là même il donne à l'ordonnanceur l'occasion de donner la main à un autre programme. Et c'est ainsi que chaque programme s'exécute à son tour, en pseudo--simultanéité avec les autres. Nous avons vu aussi le rôle fondamental des interruptions pour le fonctionnement de la multiprogrammation.

Nous comprenons aussi qu'un programme qui ferait beaucoup de calculs et très peu d'entrées-sorties, par exemple un programme qui devrait calculer et afficher la millionième décimale de p, risquerait de bloquer tous les autres parce qu'il ne rendrait jamais la main. Pour parer une telle menace, plusieurs solutions sont envisageables.

3.12.1 Stratégies d'ordonnancement

La solution d'ordonnancement la plus simple consiste à découper le temps en tranches et à dire qu'aucun processus ne pourra avoir la main pendant deux tranches de temps consécutives. Chaque expiration d'une tranche de temps déclenche une interruption et donne la main à l'ordonnanceur, qui peut ainsi éviter la monopolisation du processeur par un programme gourmand.

Une autre solution consiste à affecter à chaque processus une priorité. L'ordonnanceur donne toujours la main au processus prêt (dispatchable) de plus haute priorité. Il suffit de donner une priorité basse aux processus qui font peu d'entrées-sorties et une priorité haute à ceux qui en font beaucoup, et dont on sait qu'ils vont se mettre en attente « volontairement » souvent.

Il est possible de combiner toutes ces stratégies de répartition du temps de processeur pour obtenir un système auto--régulé. Nous aurons des tranches de temps et des priorités, qui de surcroît seront variables dynamiquement. Un processus aura deux façons de s'interrompre : soit « volontairement » en faisant une demande d'entrée-sortie ou tout autre appel système suivi d'une mise en attente, soit en atteignant la fin d'une tranche de temps. L'ordonnanceur se voit attribuer une prérogative supplémentaire : les « bons » processus qui se seront interrompus « volontairement » verront leur priorité augmentée, les « mauvais » processus qui auront atteint la limite d'une tranche de temps, manifestant par là une tendance néfaste à la monopolisation, verront leur priorité diminuée, ce qui améliorera la fluidité de la multiprogrammation. L'hypothèse sous-jacente est : qui a fait des entrées-sorties, en refera ; qui a calculé, calculera. Notons néanmoins que ce dispositif n'implique pas de prédestination, et qu'il laisse grande ouverte la porte de la rédemption.

3.12.2 Interruptions et exceptions

Nous avons examiné le cas particulier de l'interruption d'entrée-sortie, qui est provoquée par un élément matériel extérieur au processeur, indépendant du cadencement des instructions. C'est une interruption asynchrone. Il existe par ailleurs des interruptions provoquées par le processeur lui-même, par exemple lorsqu'il détecte une condition anormale, ou simplement à la demande d'un programme. Ces interruptions sont synchrones, parce que le processeur ne les produit qu'après avoir terminé l'exécution d'une instruction, et elles sont aussi nommées exceptions.

3.12.3 Préemption

Ainsi que nous venons de le voir, le fonctionnement du processeur est cadencé par des interruptions. Une interruption peut survenir du fait de la terminaison d'une entrée-sortie, de l'expiration de la tranche de temps de processeur allouée à un processus, de l'occurrence d'une erreur du système ou du matériel, ou simplement à la demande d'un processus, comme lors d'une demande d'entrée sortie.

À chaque interruption, l'ordonnanceur prend la main. C'est pour cela que les interruptions jouent un rôle si important dans le fonctionnement du système. L'ordonnanceur examine la file d'attente des processus prêts (éligibles) pour l'exécution (dispatchable), comme déjà dit. Souvent, et même presque toujours, le déclenchement d'une interruption procède d'un événement à la suite duquel cette file d'attente est modifiée : après une demande d'entrée-sortie, le processus qui l'a émise, et qui était donc actif, entre dans l'état non-prêt (dormant) ; au contraire, après la terminaison d'une entrée-sortie, le processus qui en attendait le résultat redevient prêt. Les interruptions sont les seules circonstances à l'occasion desquelles un processus peut passer d'un état (prêt, non-prêt, actif, terminé) à un autre.

Dans tous les cas, l'ordonnanceur examine la file d'attente sans préjugé et donne la main au processus prêt de plus haute priorité, sans respect pour les positions acquises. Il y a des exceptions : par exemple, si le système est paramétré pour une stratégie d'ordonnancement par tranches de temps, et si le processus le plus prioritaire vient d'épuiser la tranche précédente, la règle de répartition interdit de lui rendre la main. Mais de façon générale, tout processus de haute priorité redevenu prêt prendra la main au processus moins prioritaire qui s'exécutait jusqu'alors. On dit que le système d'exploitation qui permet ce transfert de contrôle du processeur est un système préemptif. Un vrai système d'exploitation doit être préemptif.

3.12.4 Systèmes non-préemptifs

Certains concepteurs de systèmes pour micro-ordinateurs ont cru pouvoir faire l'économie de la préemption, qui suppose en effet beaucoup de complexité¹¹. Leur idée (dans les années 1980) était que les utilisateurs de leur système n'utiliseraient qu'un seul programme à la fois, et qu'il était donc inutile de gaspiller de la mémoire pour implanter des mécanismes qui ne serviraient que si l'on voulait faire deux choses à la fois, ou plus. En fait, ce raisonnement est fallacieux : même si l'utilisateur ne lance que le logiciel de traitement de texte, par exemple, dès qu'il veut imprimer il fait deux choses à la fois, parce qu'il veut pouvoir continuer à taper son texte pendant l'impression.

Dès que le micro-ordinateur est en réseau, les choses se corsent : par définition, dès que l'on est en réseau on fait plusieurs choses à la fois, le traitement local et les interactions avec le réseau. En outre, les manifestations du réseau viennent de l'extérieur, donc par définition à un instant non prévu (on dit que ce sont des événements asynchrones). Nous venons de voir un bon moyen de faire face à ce type de situation : le traitement des interruptions. Mais justement ces systèmes sans préemption ne disposent pas d'un vrai système de traitement des interruptions. Du coup, ils s'en remettent à la chance : l'utilisateur de traitement de texte, nous l'avons vu à la section 3.2.1, n'utilise qu'un part infime du temps du processeur, qui la plupart du temps est donc inactif ; la probabilité que l'interruption en provenance du réseau survienne pendant une période d'activité est infime ; chaque fois qu'il se met en attente d'un événement (par la fonction WaitNextEvent dans le cas de MacOS 9, par exemple) le système accorde aux interruptions un certain délai pendant lequel elles pourront survenir impunément, parce qu'il suppute que pendant ce délai rien ne se passera : le doigt de l'utilisateur ne tapera ni ne cliquera. Si l'improbable conflit survient, le système « se plantera », mais après tout cela n'arrivera pas trop souvent et puisqu'il s'agit d'un ordinateur bon marché utilisé par une seule personne, le client se fera une raison.

Les résultats de ce calcul mesquin ont bien sûr été catastrophiques. Avec le développement des réseaux, ces micro-ordinateurs se sont vite trouvés dans des environnements plus complexes que prévu, sur des réseaux de centaines ou de milliers de postes. Les « plantages » ne survenaient plus tous les deux ou trois jours mais deux ou trois fois par jour. Les clients ont commencé à utiliser des logiciels plus exigeants, notamment les jeux, qui ont souvent des interfaces graphiques très complexes et qui consomment énormément de temps de calcul. Comme ce qui tenait lieu de système d'exploitation était indigent, toutes les fonctions complexes ont été déportées ailleurs, beaucoup dans les cartes graphiques, et le reste dans le logiciel lui-même. Cela ne va pas trop mal tant qu'on utilise un seul logiciel avec une seule carte graphique, mais il vient bien un moment où il faut sortir de l'autisme et changer de logiciel : et là, en général, cela se passe assez mal.

Du fait de la déficience du système d'expoitation, c'est au logiciel de traitement de texte, par exemple, d'assurer lui-même les fonctions qui normalement incomberaient à celui-là, comme l'allocation de mémoire, les entrées-sorties, et surtout la réaction aux interruptions asynchrones ; le logiciel devient énorme et complexe, mais en plus il doit espérer que les autres logiciels auront la même vision du monde que lui et adopteront les mêmes conventions, sinon il y aura des conflits. Par exemple, chaque logiciel gère lui-même ses entrées-sorties, et comporte une heuristique pour estimer le temps que cela va prendre ; il rend la main pendant ce délai afin qu'un autre logiciel « en tâche de fond », comme on dit dans cet univers, puisse s'exécuter. En procédant ainsi, on commet deux actes de foi : on espère que les autres logiciels ont des comportements compatibles avec le sien, notamment pour rendre la main à l'issue du délai supputé, et que le délai sera bien respecté, parce que si l'entrée-sortie se termine inopinément plus tôt que prévu, c'est le plantage assuré. Évidemment, si on achète tous ses logiciels chez le même fournisseur, qui serait aussi le brillant concepteur du non--système d'exploitation, on peut espérer limiter les risques...

J'ai lu des articles où ces bricolages étaient présentés par leurs auteurs comme une nouvelle façon de concevoir les programmes, plus sympathique et décontractée que l'ancienne méthode encadrée par des règles rigides. C'était de la programmation « orientée vers les applications », avec des applications « coopératives ». Bref, c'était cool et moderne, alors que les vieux systèmes d'exploitation avaient bien l'air d'avoir été écrits par de sévères instituteurs du XIXsiècle en blouse grise... Dans un monde où le client est le plus souvent incompétent, ce genre de démagogie fonctionne assez bien, et présenter ses déficiences comme des qualités peut marcher.

Les systèmes qui ont succédé à ces réalisations discutables, Windows NT, 2000, XP et la suite, sont dotés de mécanismes de préemption et de traitement multi--tâches, mais comme il fallait bien assurer la compatibilité avec la passé, les logiciels courants sont toujours dotés de leurs excroissances palliatives censées corriger les lacunes des systèmes d'exploitation, d'où de nouvelles sources de conflits qui résultent désormais en écrans bleus, caractéristiques des plantages de ces systèmes (voir aussi le chapitre 11 consacré à la micro-informatique). Le comble de l'horreur est atteint avec les pilotes de cartes graphiques, grandes sources de catastrophes...

3.12.5 Synchronisation de processus et sections critiques

Nous sommes bien contents d'avoir un système préemptif, mais si nous réfléchissons un peu nous voyons apparaître quelques inconvénients. Un processus qui s'exécute peut à tout moment être interrompu, même en plein milieu d'une instruction en cas d'interruption asynchrone (et les interruptions asynchrones comportent, dans le cas des multi-processeurs, les interruptions par un autre processeur accédant à la mémoire commune), le noyau du système d'exploitation va prendre la main pour traiter l'interruption, et à l'issue de ce traitement ce sera peut-être un autre processus qui recevra la main.

Ce risque d'être interrompu à tout instant impose des précautions. Les éléments essentiels du vecteur d'état du programme doivent pouvoir être sauvegardés, afin de permettre la reprise du traitement. Ces éléments sont essentiellement la valeur du PSW, qui permet notamment de retrouver l'instruction en cours au moment de l'interruption, et le contenu des registres, qui permet de retrouver les différentes zones de mémoire utilisées. Comme nous le verrons au chapitre 4, dans un système à mémoire virtuelle moderne chaque processus dispose de son espace de mémoire virtuelle privé, ce qui simplifie les choses. Cette opération de sauvegarde du contexte d'exécution du processus interrompu et d'initialisation du contexte d'exécution du processus promu s'appelle commutation de contexte (context switch). Selon les processeurs et les systèmes, ce peut être une opération figée dans le matériel et invoquée par une instruction spécifique unique, ou une séquence d'instructions répétées comme un refrain au début de chaque section de programme, comme dans l'OS 360/370. Nous avons déjà rencontré ce mécanisme aux sections ?? et 3.11.1.

Mais même si ces précautions ont été prises, il y a des opérations au cours desquelles une interruption, suivie ou non d'une commutation de contexte, risque d'avoir des conséquences catastrophiques. La séquence des instructions qui constitue le programme d'une telle opération est appelée section critique. Les sections critiques sont généralement dans le noyau du système d'exploitation. Le cas le plus courant est celui d'une allocation de ressource matérielle, ce qui suppose la mise à jour de tables : dans le cas de l'allocation d'une zone de mémoire réelle, la table des cadres de pages (ici nous anticipons sur le chapitre 4), dans le cas d'une écriture sur support externe, la table des blocs libres sur le disque et la i-liste, qui décrit la cartographie des fichiers et des blocs qui leur sont alloués sur le disque (ce sera vu au chapitre 5).

Lorsqu'un processus veut acquérir une ressource contrôlée par le noyau, il émet un appel système. Le traitement de cet appel système va résulter en l'allocation de la ressource, ce qui se traduit en mémoire par la modification des tables qui décrivent cette ressource. L'exécution de la séquence des instructions du noyau qui effectuent ce traitement est appelée chemin de contrôle du noyau. Tout ou partie du chemin de contrôle est une section critique.

La programmation d'une telle section critique impose une protection particulière pour préserver l'intégrité des données, il faut garantir une des deux conditions suivantes :

-2mm

Assertion 1 :: Aucune interruption ne pourra avoir lieu pendant le déroulement de la section critique.

OU BIEN :
Assertion 2 :: Si une interruption survient, elle peut avoir pour effet de rendre prêt un chemin de contrôle du noyau qui était dormant, par exemple dans le cas d'une interruption de fin d'entrée-sortie. De ce fait, le chemin de contrôle du noyau qui était en train d'allouer des ressources à cet instant peut perdre la main au profit du nouveau concurrent, peut-être doté d'une priorité plus élevée. Il faut alors garantir que les tables et les autres structures de données en cours de modification ne pourront pas être modifiées par ce nouveau chemin de contrôle.

C'est compliqué, et plusieurs méthodes peuvent être employées selon les circonstances.

Nous avons introduit la notion de système préemptif, qui permet aux processus de prendre la main à des processus moins prioritaires lorsqu'ils repassent à l'état prêt. Lorsqu'un processus émet un appel système et qu'il exécute des instructions du noyau, en mode noyau (on dit aussi superviseur) donc, il n'est par construction pas préemptible par un processus en mode utilisateur (qui exécute des instructions ordinaires écrites par le commun des mortels). Mais ne risque-t-il pas la préemption par un autre processus en mode noyau ? Cela dépend du système. Les premières versions du noyau Linux n'étaient pas préemptives, un processus en mode noyau ne pouvait pas subir la préemption. Mais même un noyau non préemptif doit tenir compte des interruptions et des systèmes multi-processeurs. Les moyens d'assurer la véracité d'une de ces deux assertions sont examinées ci-dessous.

Le noyau Linux version 2.4 a vu apparaître un « patch » développé par Robert Love, destiné à le rendre préemptif. Le résultat est une amélioration assez spectaculaire des temps de réponse des processus. Le prix à payer est une complexité accrue, mais avec l'avantage associé d'un code¹² de meilleure qualité, intrinsèquement adapté aux multi-processeurs.

Atomicité des opérations

Le premier moyen qui vient à l'idée pour interdire la préemption d'un processus en section critique dans le noyau, c'est d'assurer l'ininterruptibilité de la section critique. Le moyen le plus radical, c'est que cette section critique soit réduite à une instruction unique. Même cela ne suffit pas, puisqu'une instruction qui consomme plusieurs cycles de processeurs (cas courant pour les processeurs CISC¹³ tels que le Pentium) peut être interrompue par une interruption asynchrone émise par un organe périphérique ou en provenance d'un autre processeur sur un système multi-processeur. Il faut donc que la section critique soit composée d'une instruction unique sur un cycle unique. Là on est sûr que le système reste dans un état où la section critique est exécutée soit totalement soit pas du tout : cette propriété d'une opération est nommée atomicité, et elle garantit que :

si le système était dans un état cohérent avant l'opération ;
si l'opération n'introduit pas d'incohérence ;
le système est cohérent à l'issue de l'opération.

La solution répond parfaitement à l'énoncé, le problème est qu'en un cycle de processeur on ne fait pas grand chose, et notamment on n'accède pas à la mémoire principale, on ne peut donc espérer effectuer de cette façon la mise à jour complexe de tables d'allocation de ressources. En fait, il est seulement possible, au prix d'une certaine virtuosité dans la conseption des circuits logiques, de tester une position de mémoire (par exemple un registre du processeur) qui représente un drapeau logique (0 libre, 1 verrouillé, par exemple) et, dans le même cycle, si le test est favorable, d'en modifier une autre. Cette instruction est généralement nommée TAS (Test and Set). Un programme en langage C ne peut garantir l'atomicité d'une de ses expressions, parce que cela dépend de l'usage qui sera fait du langage machine par le compilateur. Pour franchir cet obstacle, le noyau Linux procure des fonctions destinées à faire usage des possibilités « atomiques » du langage machine, nommément atomic_dec_and_test(v) et atomic_inc_and_test(v).

Les processeurs modernes disposent d'instructions éventuellement plus complexes mais qui assurent l'atomicité de façon brutale, même dans le cas de multi-processeurs, en bloquant l'accès au bus mémoire jusqu'à la fin de l'instruction.

Les opérations atomiques sont très limitées par leur concision, mais elles peuvent servir de base à des mécanismes plus complexes de protection de sections critiques, comme ceux que nous allons examiner ci-dessous.

Masquage des interruptions

Tous les processeurs courants possèdent un dispositif de masquage des interruptions. Pour la gamme IBM 360 et ses successeurs, il s'agit simplement d'un bit du PSW, pour les processeurs Intel récents un champ du registre eflags. Ici encore, nous disposons d'un moyen radical de protection d'une section critique : aucune interruption ne peut se manifester tant que le drapeau est positionné. Les limites de cette méthode tiennent à sa puissance même : pendant que les interruptions sont masquées, tous les échanges entre le processeur et les organes périphériques sont bloqués. De plus, il est impossible de masquer les interruptions pendant une séquence d'instructions qui risque elle-même de faire une demande d'entrée-sortie, c'est-à-dire d'entrer dans un état dormant : le système ne se réveillera jamais et restera gelé, le seul recours sera le bouton RESET...

Verrouillage de la section critique

Quand il faut créer une section critique trop longue ou trop complexe pour qu'il soit possible de la réaliser atomiquement, ou de la protéger en masquant les interruptions, il faut recourir au verrouillage par un procédé plus complexe. Il existe classiquement trois familles de procédés, dont on peut démontrer qu'elles donnent des résultats équivalents : les sémaphores inventés par Edsger Wybe Dijkstra, les moniteurs dûs à C. Antony R. Hoare[29], les bibliothèques de fonctions.

Toutes les méthodes de verrouillage reposent sur des principes communs. Un chemin de contrôle du noyau qui doit accéder, par exemple, à une table d'allocation d'une ressource système doit auparavant acquérir un verrou pour cette table. Le verrou n'est rien d'autre qu'une structure de données en mémoire : c'est purement logique, il ne faut imaginer là aucun dispositif matériel qui verrouillerait physiquement une zone de mémoire, ou un élément du processeur, ou un périphérique. C'est-à-dire qu'il n'a d'efficacité que parce que tous les chemins de contrôle susceptibles d'accéder à la même ressource utilisent la même convention de verrouillage, donc cherchent à acquérir le même verrou. En pratique, ils doivent utiliser tous la même séquence d'instructions. Inutile de dire que cette séquence est partie intégrante du noyau, et qu'il est vivement conseillé de ne pas laisser les programmes en mode utilisateur accéder aux félicités du verrouillage... ce que s'empressent de faire, bien évidemment, les applications destinées aux systèmes non préemptifs, avec les résultats que chacun peut constater.

Dans son état le plus simple, le verrou se réduit à un bit : libre ou occupé. Il peut avoir une structure plus complexe, et accéder ainsi au rang de sémaphore, qui confère les champs suivants (pour le noyau Linux) :

count: valeur numérique : si elle est supérieure à 0, la ressource est libre, si elle est inférieure ou égale à 0 la ressource est occupée et la valeur absolue de count est égale au nombre de chemins de contrôle qui attendent pour y accéder ;
wait: adresse de la file d'attente des processus¹⁴ en attente d'accès à la ressource ;
waking: une variable dont la valeur sert à sélectionner dans la file d'attente le prochain chemin de contrôle qui accédera à la ressource, selon un algorithme dont nous dirons deux mots ci-dessous.

Bref, le sémaphore est un verrou doté d'une valeur qui dit combien de clients on peut laisser passer à la fois. Traditionnellement, les sémaphores sont manipulés au moyen de deux opérations primitives mystérieusement nommées P et V, initiales de leurs noms néerlandais¹⁵, puisque oeuvre d'E.W. Dijkstra. P est invoquée par un processus qui cherche à accéder à la ressource, V par un processus qui la libère et laisse la place au suivant. Claude Kaiser, un des auteurs de Crocus [15], m'a confié un procédé mnémotechnique pour ne pas les confondre : P pour « Puis-je ? » et V pour « Vas-y ! ». Le noyau Linux les a prosaïquement baptisées down (qui décrémente count) et up (qui incrémente count).

Lorsqu'un processus invoque P avec en argument l'adresse d'un sémaphore, la primitive décrémente le champ count du sémaphore et examine son signe (les deux actions au moyen d'une unique instruction atomique vue à la section 3.12.5, sinon un autre processus pourrait tenter la même opération en même temps). Si count est positif ou nul, le processus acquiert le contrôle du sémaphore, et l'exécution continue normalement. Si count est négatif, le processus entre dans l'état dormant et est placé dans la file d'attente désignée par wait.

Lorsque le processus qui contrôlait le sémaphore a fini d'utiliser la ressource correspondante, il invoque la primitive V. Celle-ci incrémente le champ count et examine son signe (les deux actions au moyen d'une unique instruction atomique vue à la section 3.12.5, sinon un autre processus pourrait tenter la même opération en même temps). Si count est positif, aucun processus n'attendait la ressource, et l'exécution de V se termine. Sinon, elle incrémente le champ waking (opération protégée par un verrou et le masquage d'interruptions pour éviter toute concurrence) et réveille les processus de la file d'attente pointée par wait. Chaque processus réveillé exécute alors la suite de P, qui contient une section critique pour tester si waking est positif. Le premier à exécuter cette section critique décrémente waking et acquiert le contrôle du sémaphore, les suivants trouvent waking négatif ou nul et se rendorment.

L'effet produit par l'invocation de P et de V dépend de la valeur initiale de count ; si elles est de 1, P et V réalisent l'exclusion mutuelle entre des processus qui essaient d'accéder à une ressource partagée ; P est exécuté à l'entrée d'une section critique, V à sa sortie, et le résultat est que seul un processus peut s'exécuter dans la section critique à la fois.

Cet algorithme donne le résultat voulu parce que tous les processus en concurrence exécutent les mêmes appels système et obéissent aux mêmes conventions pour se synchroniser. Inutile de dire que dans un système (ou prétendu tel) non préemptif qui table sur la bonne volonté coopérative des logiciels d'application pour assurer cette cohérence, il suffit d'un logiciel mal écrit pour provoquer des catastrophes, et l'expérience prouve que cela se produit.

1: Le parti-pris de cet ouvrage est de ne pas entrer dans le détail de l'histoire des ordinateurs, à laquelle ont déjà été consacrés des livres excellents dont le lecteur trouvera les références dans la bibliographie de celui-ci. Je me contenterai de donner la liste de ces innovations sans les décrire : seconde utilisation (derrière l'UNIVAC 1103A) de la mémoire à tores de ferrite inventée par An Wang en 1950, arithmétique à virgule flottante, premier langage de programmation évolué (Fortran), premier langage de programmation fonctionnelle (Lisp).
2: Ceci est vrai pour les ordinateurs qui ont un seul processeur. Il y a des ordinateurs à plusieurs processeurs capables d'exécuter plusieurs programmes en vraie simultanéité. En première approximation nous considérerons un ordinateur à n processeurs comme n ordinateurs indépendants. Un tour d'horizon des extensions et des dépassements de l'architecture de von Neumann figure au chapitre 9.
3: La genèse de ces programmes met en scène un autre personnage fameux, l'ingénieur et mathématicien italien Luigi Menabrea, futur premier ministre de son pays, qui publia en 1842 (en français ; il était natif de Chambéry, mais c'est sans doute le rôle prééminent du français dans le monde mathématique qui a déterminé le choix de cette langue ; incidemment, Leibniz écrivait aussi en français) le premier article sur les travaux de Babbage. Babbage avait demandé à Ada de les traduire en anglais ; c'est au cours de ce travail de traduction et d'additions qu'Ada commença à écrire des programmes destinés à résoudre différents problèmes d'analyse mathématique. Lorsque le langage machine de Babbage se révélait trop peu maniable pour un certain problème, elle en demandait la modification. Une abondante littérature est maintenant disponible sur ce sujet passionnant, y compris en édition française.
4: Incidemment tout programme est un sous-programme, le « programme principal » est appelé par le système d'exploitation auquel il rend la main en se terminant.
5: L'anthropomorphisme débridé de cet alinéa et d'autres à venir peut choquer : le système bien sûr ne désire ni ne juge ni ne s'octroie quoi que ce soit. Les algorithmes écrits par son concepteur et les paramètres qui leur sont fournis sont les seuls déterminants des mécanismes en jeu. Néanmoins ces façons de parler allègent l'expression des périphrases qu'il faudrait sans cesse y introduire. Nous demandons au lecteur d'imaginer leur présence.
6: Les programmes concernés sont getty et login
7: Au cinquième étage du bâtiment du MIT qui l'abritait, MAC signifiait Multiple Access Computers, au neuvième étage, Man and Computer. L'initiateur du projet était Robert M. Fano, professeur au MIT, sur une suggestion de J. C. R. Licklider.
8: J. C. R. Licklider est une des personnalités dont l'influence sur le développement de l'informatique a été la plus forte. Il fut directeur de la division Information Processing Techniques Office (IPTO) de l'ARPA (Advanced Research Projects Agency), une agence du ministère américain de la défense, dans les années 1960, et fut ainsi à l'origine de projets qui débouchèrent sur les interfaces personnes--ordinateurs que nous utilisons aujourd'hui, ainsi que sur la création de l'Internet. Ses deux articles les plus célèbres portent des titres prophétiques : Man-Computer Symbiosis (1960) et The Computer as a Communications Device (1968, en collaboration avec Robert Taylor).
9: Par immédiatement on entend « avant la fin de l'exécution de l'E/S par le matériel », contrôleur et périphérique proprement dit, ce qui, nous l'avons vu à la section 3.2.1, laisse au processeur largement le temps d'exécuter quelques milliers d'instructions
10: Rappelons aussi que tous les systèmes utilisés réellement aujourd'hui (17 septembre 2002) sont conformes macroscopiquement à l'architecture de von Neumann, c'est-à-dire que les modifications qu'ils lui apportent ne modifient pas substantiellement les conséquences que l'on peut tirer du principe d'exécution séquentielle.
11: Les systèmes dont nous parlons sont essentiellement MS-DOS et les systèmes à fenêtres qui reposaient sur lui.
12: Le terme code est employé ici dans l'acception de « texte du programme ». On parle de code source pour désigner le texte du programme tel qu'il a été écrit par le programmeur dans le langage de développement, le code objet est le programme traduit en langage machine par le compilateur, le code exécutable est le programme sous forme binaire auquel l'édition de liens a ajouté tous les sous-programmes compilés séparément et les références aux bibliothèques partagées nécessaires à l'exécution. On notera que les détracteurs de l'informatique utilisent de façon péjorative la série de termes code, coder, codage pour dévaluer l'activité de programmation en suggérant que ce serait une activité triviale, l'application mécanique d'un code.
13: Les abbréviations CISC (pour Complex Instruction Set Computer), RISC (pour Reduced Instruction Set Computer) et VLIW (pour Very Long Instruction Word) désignent des classes dans la zoologie des processeurs, dont la signification est donnée à la section 9.2.3.
14: Conformément à l'usage nous employons ici et dans les lignes qui suivent « processus » à la place du fastidieux « chemin d'accès du noyau exécuté pour le compte d'un processus » qui serait plus exact.
15: P est pour passeren, passer, et V pour vrijgeven, libérer.

Processus P₁	Processus P₂
...	...
Allocation de la ressource A	...
...	Allocation de la ressource B
...	...
Tentative d'allocation de la	...
ressource B : échec, blocage	...
...	...
...	Tentative d'allocation de la
...	ressource A : échec, blocage
...	...
Libération de la ressource A :	...
hélas P₁ n'arrivera jamais là.	...
...	...
...	Libération de la ressource B :
...	P₂ n'y arrivera pas.