Cahier d'histoire des sciences

L'évolution des systèmes d'exploitation

Un système d'exploitation est le programme qui se tient entre le matériel et nous : il partage le processeur, range les fichiers, protège chacun des autres et dessine les fenêtres. De Multics et Unix à Linux, Windows, macOS et Android, cinq planches pour voir ses grandes inventions à l'œuvre.

Une généalogie en trois grandes familles

Presque tous les systèmes d'aujourd'hui descendent de trois lignées. Celle d'Unix (1969), née aux laboratoires Bell en réaction à la lourdeur de Multics, a donné BSD, puis macOS et iOS d'un côté, Linux et Android de l'autre. Celle de Microsoft part de MS-DOS (1981) et aboutit à Windows NT, dont descendent tous les Windows actuels. Celle des grands systèmes d'IBM (OS/360, 1966) vit toujours dans les ordinateurs centraux des banques. Le noyau est la partie centrale du système, celle qui commande directement le matériel.

Chaque système est placé à son année de sortie. Les flèches indiquent une filiation de code ou de conception. L'animation fait défiler les années.
Planche 1

Plusieurs programmes, des ressources partagées : l'interblocage

1965 – 1968

Dès que plusieurs programmes, les processus, tournent en même temps, ils se disputent des ressources : une imprimante, un fichier, une zone de mémoire. En 1965, Edsger Dijkstra invente le sémaphore pour qu'un seul processus à la fois utilise une ressource, et l'illustre par le dîner des philosophes : cinq philosophes autour d'une table, une fourchette entre chaque voisin ; pour manger il en faut deux. Si chacun saisit d'abord celle de gauche, ils peuvent tous rester bloqués, chacun attendant la fourchette de son voisin : c'est l'interblocage. Dijkstra applique ces idées dans le système THE (1968).

8
Les philosophes (P1 à P5) et les fourchettes (F1 à F5). Vert : mange ; orange : a faim et tient une fourchette ; gris : pense. Une fourchette tenue est dessinée près de son détenteur.
Instant
—
Repas servis
—
État du système
—
Repas par philosophe
—

Mille dîners simulés pour chaque règle

Chaque dîner dure 400 instants ; à chaque instant, un philosophe tiré au hasard fait un pas (avoir faim, prendre une fourchette, finir de manger…).

Ce qu'il faut retenir. L'interblocage n'est pas certain, ce qui le rend redoutable : le même programme fonctionne cent fois puis se fige. Les trois règles correspondent aux remèdes classiques. Numéroter les ressources et les prendre toujours dans le même ordre rend impossible une attente en cercle ; limiter le nombre de concurrents (le portier est lui-même un sémaphore initialisé à 4) garantit qu'au moins un philosophe peut manger. Les systèmes actuels appliquent ces règles, par exemple dans l'ordre fixe dans lequel le noyau Linux pose ses verrous.
Planche 2

La philosophie d'Unix : de petits programmes reliés par des tubes

1969 – 1973

Ken Thompson et Dennis Ritchie conçoivent Unix comme une boîte à outils : chaque commande fait une seule chose et la fait bien, lit du texte et écrit du texte. En 1973, Douglas McIlroy obtient l'ajout des tubes (le caractère |) : la sortie d'une commande devient l'entrée de la suivante, et le noyau fait tourner toutes les commandes en même temps, chacune dans son processus. Voici comment compter les mots les plus fréquents d'un texte en enchaînant six commandes.

cat texte.txt | tr -cs '[:alpha:]' '\n' | tr '[:upper:]' '[:lower:]' | sort | uniq -c | sort -rn | head -5
Les sept processus et les six tubes. Chaque point est une ligne de texte qui passe d'un processus au suivant. Le premier sort retient tout : il ne peut rien écrire avant d'avoir tout lu.

    

      
Lignes produites à chaque étape
—

      
Processus créés par le shell (fork puis exec)
7

      
Les cinq mots les plus fréquents (sortie du tube)
—

      
Contrôle : comptage direct par une table en JavaScript
—

    

  

  
Ce qu'il faut retenir. Aucune de ces commandes ne sait ce qu'est un « mot fréquent » : c'est leur assemblage qui produit le résultat, sans écrire une ligne de programme. Tout passe par du texte et par des fichiers, et pour Unix presque tout est un fichier, y compris le clavier, l'écran et les tubes eux-mêmes. Pendant que les commandes de flux (tr, uniq) traitent les lignes dès qu'elles arrivent, sort doit attendre la fin de son entrée : le noyau le met en sommeil, puis le réveille. Cette philosophie a été reprise par Linux et macOS, et les commandes ci-dessus y fonctionnent toujours.







  
Planche 3
Ranger et protéger : l'arborescence, les i-nœuds et les droits
1965 – 1974

  
Multics (1965) invente l'arborescence de répertoires et le chemin d'accès comme /home/jc/notes.txt. Unix la simplifie : un fichier est décrit par un i-nœud (sa taille, son propriétaire, ses droits, l'emplacement de ses données sur le disque), et un répertoire n'est qu'une liste de couples « nom, numéro d'i-nœud ». Le nom n'appartient donc pas au fichier : un même fichier peut avoir plusieurs noms, des liens. Unix attache à chaque fichier neuf droits : lire, écrire, exécuter, pour le propriétaire, son groupe et les autres.

  

  

    

      

      
      
      
      
    

    

      
L'arborescence. Chaque boîte porte son numéro d'i-nœud ; les fichiers sont en vert, les répertoires en bleu. Pendant la résolution, l'i-nœud lu est en rouge.

      
Table des i-nœuds
« liens » compte les noms qui désignent l'i-nœud ; quand il tombe à 0, le système libère les données.

    

    

      
Étape de la résolution
—

      
I-nœuds lus pour ce chemin
—

      
Contrôle : nombre de composants du chemin + 1 (la racine)
—

      
État du fichier notes
—

    

  

  

    

      
Droits

      

    

    

      

      

    

    
Le système commence par déterminer la classe du demandeur (propriétaire, groupe ou autre), puis ne regarde que le bit correspondant à l'action.

    

      
Notation symbolique (ls -l)
—

      
Notation octale (chmod)
—

      
Contrôle : Σ bit × 2^position
—

      
Décision du noyau
—

    

  

  
Ce qu'il faut retenir. Ouvrir /home/jc/photos/ete.jpg demande de lire cinq i-nœuds : la racine, puis un par composant ; c'est pourquoi les systèmes gardent en mémoire les répertoires récemment parcourus. Après ln, il n'y a pas de copie : deux noms pour le même i-nœud. Après rm du premier nom, le fichier existe toujours sous le second : rm retire un nom, pas un fichier. Quant aux droits, chaque chiffre octal résume trois bits : 7 = lire + écrire + exécuter = 4 + 2 + 1. Neuf bits suffisent à décrire presque toute la sécurité d'un système Unix ; Windows NT (1993) leur préfère des listes de contrôle d'accès plus détaillées.







  
Planche 4
L'interface graphique : des fenêtres qui se chevauchent
1973 – 1995

  
Au Xerox PARC, l'Alto (1973) montre pour la première fois des fenêtres, des icônes et une souris. Le Macintosh d'Apple (1984), puis Windows (1985, et surtout Windows 95), les apportent au grand public. Le système doit alors gérer l'ordre d'empilement des fenêtres et redessiner l'écran à chaque déplacement. La méthode la plus simple est l'algorithme du peintre : peindre les fenêtres de la plus profonde à la plus proche, chaque nouvelle couche recouvrant les précédentes. Faites glisser les fenêtres par leur barre de titre ; touchez-en une pour la ramener au premier plan.

  

    
    
  

  

  
Un écran de 640 × 360 points. Pendant la repeinture, chaque fenêtre est peinte entièrement, puis recouverte en partie par les suivantes.

  

    
Ordre d'empilement (du fond vers le premier plan)
—

    
Surface visible de chaque fenêtre (calcul exact sur les rectangles)
—

    
Contrôle : comptage point par point de l'écran
—

    
Points peints par le peintre / points visibles
—

  

  
Ce qu'il faut retenir. L'algorithme du peintre est simple mais gaspilleur : il peint des points qui seront aussitôt recouverts, et le rapport entre points peints et points visibles le mesure. Les premiers systèmes graphiques, très lents, calculaient donc les régions visibles de chaque fenêtre, comme le fait le calcul exact ci-dessus, pour ne redessiner que le nécessaire ; QuickDraw, le moteur graphique du Macintosh de 1984, était célèbre pour cela. Aujourd'hui, la carte graphique garde l'image de chaque fenêtre et les compose à chaque image : c'est le compositeur de macOS (2001), de Windows Vista (2007) et des bureaux Linux.







  
Planche 5 · signature
L'ordonnanceur équitable de Linux : partager le processeur selon des poids
1991 – 2023

  
En 1991, l'étudiant finlandais Linus Torvalds publie un petit noyau, Linux, aujourd'hui présent dans les serveurs, les supercalculateurs et, par Android, dans des milliards de téléphones. Le cœur de tout noyau est l'ordonnanceur, qui décide quel processus tourne. De 2007 (Linux 2.6.23) à 2023, Linux a utilisé le CFS d'Ingo Molnár, l'ordonnanceur « complètement équitable ». Chaque processus a un temps virtuel qui avance d'autant plus lentement que son poids est grand ; l'ordonnanceur choisit toujours celui dont le temps virtuel est le plus petit. Le poids dépend de la valeur nice donnée par l'utilisateur : de −20 (prioritaire) à 19 (très effacé).


temps virtuel ← temps virtuel + durée exécutée × 1024 / poids          (poids : 1024 pour nice = 0)

  

  

    
    
    
4

  

  

    
Les temps virtuels des quatre processus : l'ordonnanceur choisit toujours la barre la plus courte (encadrée de rouge). Dans le vrai noyau, ils sont rangés dans un arbre rouge-noir qui donne le plus petit en temps logarithmique.

    
En haut, les 120 dernières millisecondes : qui a eu le processeur. En bas, la part du processeur reçue par chacun (barres) et la part prévue (traits noirs), poids / somme des poids.

  

  

    
Temps écoulé
—

    
Parts mesurées
—

    
Parts prévues, poids / Σ poids
—

    
Plus grand écart observé entre temps virtuels / borne : avance maximale d'une tranche
—

    
Contrôle sur une seconde simulée d'un coup
—

  

  
Ce qu'il faut retenir. Au lieu de donner à chacun le même temps, le CFS égalise des temps virtuels : un processus deux fois plus lourd voit son compteur avancer deux fois moins vite, et reçoit donc deux fois plus de processeur. Les poids suivent une progression régulière, environ × 1,25 par cran de nice, si bien que deux processus séparés d'un seul cran se partagent le processeur à 55,5 % contre 44,5 %. Les temps virtuels restent toujours proches les uns des autres : leur écart ne dépasse jamais l'avance que donne une seule tranche, et aucun processus n'est oublié. En 2023, Linux 6.6 remplace le CFS par EEVDF, qui garde ces poids mais tient mieux compte des délais de réponse ; la quête d'un partage à la fois équitable et réactif, commencée avec CTSS en 1961, continue.






  
Frise des jalons

  






  
En résumé

  

    
Coordonner
Sémaphores et règles d'ordre évitent que des processus concurrents se bloquent mutuellement.

    
Composer
Unix fait de petits outils reliés par des tubes, et de presque tout un fichier.

    
Ranger et protéger
Arborescence, i-nœuds, liens et neuf bits de droits organisent et protègent les données de chacun.

    
Montrer et partager
Les fenêtres rendent l'ordinateur accessible à tous ; l'ordonnanceur partage le processeur selon des poids.

  






  Pour aller plus loin
  
  
Les poids de la planche 5 sont ceux de la table sched_prio_to_weight du noyau Linux. La simulation utilise des tranches de 1 ms ; le vrai noyau ajuste la longueur des tranches au nombre de processus.