Les débuts d’une approche scientifique des systèmes d’exploitation

1. La notion de virtualisation

L’IBM 704, un ordinateur typique des années 1950.
© Lawrence Livermore National Laboratory, via Wikimedia Commons

Trois dates marquent les débuts de l’histoire des systèmes d’exploitation :

• 1951 : livraison des premiers ordinateurs commerciaux.
• 1956 : réalisation du premier système d’exploitation, un moniteur de traitement par lots pour l’IBM 704, par des ingénieurs de General Motors et North American Aviation.
• 1967 : première édition de la conférence ACM Symposium on Operating Systems Principles (Principes des systèmes d’exploitation), devenue la principale conférence scientifique du domaine.

Un lecteur pressé pourrait en conclure que les ordinateurs ont été gérés pendant cinq ans par des procédures manuelles et que les systèmes d’exploitation des dix années suivantes ont été réalisés sans l’aide de principes scientifiques. Cette dernière affirmation, un peu abrupte, n’est pourtant pas loin de traduire la réalité, une situation qui explique la réputation de « pratiquants de magie noire » longtemps attachée aux programmeurs des systèmes [1].

Rappelons que le système d’exploitation d’un ordinateur a deux fonctions complémentaires (voir le document La naissance des systèmes d’exploitation) : fournir aux utilisateurs une interface plus commode que celle de la machine physique pour réaliser et exploiter leurs applications ; gérer les ressources de cette machine pour les allouer aux activités qui en ont besoin.

L’interface présentée aux utilisateurs par un système d’exploitation est celle d’une machine virtuelle, image idéalisée de la machine physique sous-jacente. La notion de virtualisation est centrale pour comprendre le fonctionnement des systèmes, et c’est d’abord à partir de cette notion qu’est née, dans les années 1965-70, l’approche scientifique des systèmes d’exploitation.

En informatique, la virtualisation est une opération qui met en correspondance un objet concret (physique) et un objet abstrait (virtuel), image idéalisée du premier. C’est d’abord un outil intellectuel qui facilite la conception d’un système informatique. L’association virtuel-physique trouve ensuite une mise en œuvre concrète dans la phase de réalisation.

La virtualisation peut s’exercer de deux manières :

Figure 1. Les deux aspects de la virtualisation.

• dans le sens ascendant (figure 1a). On dispose d’une ressource physique que l’on distribue à un ensemble d’utilisateurs par multiplexage (attribution de la ressource aux demandeurs par tranches de temps successives), créant ainsi des ressources virtuelles. C’est ainsi que l’on parle de processeur virtuel, de mémoire virtuelle, de machine virtuelle, des notions examinées en détail dans la suite. L’interface exportée, celle des ressources virtuelles, peut être identique à celle de la ressource physique, ou peut en être différente. Une ressource virtuelle peut elle-même être virtualisée (c’est-à-dire partagée) ;
• dans le sens descendant (figure 1b). On souhaite réaliser un composant fournissant une certaine interface (dans l’exemple illustré, un envoi de message). On dispose d’un composant fournissant une interface différente (dans l’exemple, une liaison physique de bas niveau). Pour fournir l’interface souhaitée, on définit une hiérarchie descendante de composants qu’on appelle machines abstraites, chacune utilisant la suivante et la dernière s’appuyant sur l’interface existante. La conception procède ainsi par raffinements successifs avec des va-et-vient éventuels.

La virtualisation s’est révélée un outil précieux pour la compréhension et la construction des systèmes d’exploitation, dans lesquels le partage des ressources par multiplexage est un mécanisme central. En outre, la réalisation d’un système fait souvent appel à la décomposition hiérarchique, qui permet de traiter indépendamment ses différentes fonctions, qui relèvent elles-mêmes de la virtualisation. La première illustration de cette démarche a été apportée par l’informaticien Edsger Dijkstra dans un article [2] resté célèbre.

2. Virtualisation des processeurs et de la mémoire

Virtualisation du processeur

Le premier objet virtualisé fut le processeur — on parlait à l’époque d’unité centrale — l’organe d’exécution de la suite d’instructions qui constituent un programme. L’intérêt de la virtualisation vient du fait qu’on demande au processeur d’exécuter concurremment plusieurs tâches. Contrairement à ce qu’on pourrait croire, c’est toujours le cas, même quand l’ordinateur n’a qu’un utilisateur unique. En effet, cet utilisateur fait souvent fonctionner plusieurs applications en parallèle (consulter sa messagerie, éditer un document, chercher sur le Web, etc.). Et même dans le cas où il n’exécute qu’une seule application, le processeur doit gérer les communications — échanges sur le réseau, transferts vers le disque dur, gestion de l’écran et du clavier, etc. — même si l’essentiel du travail est délégué à des organes auxiliaires.

Le passage du processeur d’une tâche vers une autre se fait par un mécanisme appelé interruption : un signal est envoyé au processeur, qui suspend l’exécution de la tâche en cours, sauvegarde les données nécessaires à sa reprise ultérieure, reprend les données relatives à la nouvelle tâche et entame l’exécution de celle-ci. En l’absence de précautions particulières, cette interruption peut survenir à un moment quelconque. Elle est déclenchée par une cause extérieure à la tâche en cours, qui peut donc être interrompue en n’importe quel point de son exécution. Les causes d’interruption peuvent être, par exemple, un signal d’horloge marquant la fin d’un temps d’exécution fixé, ou un signal de fin de transfert sur un disque, etc. Ainsi, si plusieurs tâches utilisent le processeur, ce dernier exécutera alternativement des séquences d’instructions de ces tâches (en bleu sur la figure 2 ci-dessous).

Figure 2. Exécution de tâches sur un processeur.

Ces tâches sont logiquement parallèles, au sens où elles sont simultanément en cours d’exécution. Mais sur le plan physique, le processeur n’exécute à un instant donné qu’une seule de ces tâches, les autres étant en attente (on parle alors de pseudo-parallélisme). Pour avoir un parallélisme réel, il faudrait disposer d’autant de processeurs que de tâches.

Utilisé sans autres précautions, ce mode de fonctionnement présente un risque potentiel que nous illustrons par l’exemple d’un ordinateur gérant des comptes bancaires. Imaginons que deux personnes, à partir de points d’accès différents, effectuent au même moment une opération sur un même compte (ici le compte n°867A). La première dépose 1 000 €, la seconde dépose 3 000 €. Ces deux opérations constituent deux tâches, dont nous donnons ci-dessous le programme. On notera que ce programme de dépôt est identique pour les deux tâches, mais que chacune utilise ses propres variables de travail, respectivement courant1, nouveau1 et courant2, nouveau2.

Supposons maintenant que l’exécution de ces deux tâches suive un schéma analogue à celui de la figure 2, et que leurs instructions respectives soient exécutées dans l’ordre suivant :

On voit alors que le résultat final a été d’augmenter le montant du compte de 1 000 €, alors que l’effet attendu était une augmentation de 4 000 € : l’une des mises à jour a été perdue !

On pourra objecter que cet exemple est artificiel et que la probabilité d’occurrence d’une telle situation est extrêmement faible. C’est peut-être vrai dans ce cas particulier ; mais d’une part, une telle erreur n’est pas admissible, d’autre part, il faut surtout remarquer que les entrées-sorties produisaient chaque seconde des dizaines d’interruptions sur les premiers ordinateurs qui exécutaient pendant ce temps des dizaines de milliers d’instructions. La probabilité de survenue d’une incohérence au cours d’une journée devenait alors non négligeable. Et de fait, les premiers systèmes d’exploitation étaient sujets à des pannes aléatoires non-expliquées, que l’on attribuait à des défaillances transitoires du matériel alors moins fiable que de nos jours. En réalité, il s’agissait souvent d’erreurs de synchronisation lors d’un transfert, entraînant une perte d’information et une incohérence de l’état interne du système. Mais l’analyse ci-dessus n’avait pas été faite.

En 1965, Edsger Dijkstra publie l’article fondateur [3] de la théorie de la synchronisation, en introduisant la notion de processus, une activité séquentielle autonome pouvant interagir avec d’autres processus. Il formalise ainsi la notion intuitive de « tâche », un travail confié à un ordinateur, en séparant la description du travail à effectuer par une machine (le programme) de l’entité dynamique et évolutive dans le temps que constitue son exécution (le processus). Cette différence est comparable à celle qu’il y a entre la description d’une recette dans un livre de cuisine et son exécution concrète avec l’utilisation d’ingrédients et d’ustensiles divers.

On peut dès lors séparer l’aspect fonctionnel du processus, la description de ce qu’il fait, de la gestion des ressources nécessaires à son exécution : de ce point de vue fonctionnel, le processus peut être vu comme s’exécutant sur un processeur virtuel toujours disponible, un processus en attente s’exécutant à vitesse nulle. On dissocie ainsi l’activité logique, la seule intéressante pour l’utilisateur, des contingences matérielles de son exécution et notamment de l’allocation d’un processeur réel. Ces derniers aspects ne disparaissent pas, mais ils sont du ressort du système d’exploitation et demeurent invisibles à l’utilisateur. Ne restent alors à régler pour ce dernier que les interactions voulues entre plusieurs processus, telles que l’échange d’information ou la création de sous-processus pour décomposer un travail en unités élémentaires.

Qu’il s’agisse de compétition entre processus pour l’allocation de ressources au niveau du système d’exploitation, ou de coopération au niveau logique, il faut identifier et régler les cas d’incohérence potentielle tels que celui illustré plus haut. Dans cet exemple, la solution consiste à imposer qu’une seule des séquences d’instructions présentées puisse s’exécuter à la fois, chacune d’elle étant « atomique » (non sécable). Ainsi, leur effet global ne peut être que celui résultant de l’exécution de ces séquences l’une après l’autre, tout entrelacement étant exclu.

Les problèmes de synchronisation entre processus peuvent être réduits à un petit nombre de situations simples, dont celle illustrée ci-dessus appelée exclusion mutuelle. Ces problèmes ont été élégamment résolus par divers mécanismes, dont les sémaphores, inventés par Dijkstra en 1965, et les moniteurs, à un niveau plus élevé d’expression, introduits au début des années 1970 par les informaticiens C. A. R. Hoare et Per Brinch Hansen. Plus tard, la notion d’exécution atomique a été étendue pour couvrir les cas de défaillance, grâce à la notion de transaction, due à Jim Gray. Cette notion est maintenant standard dans tous les systèmes de gestion de bases de données.

Ces problèmes de synchronisation connaissent depuis quelques années un regain d’actualité avec l’apparition des processeurs multicœurs qui introduisent le parallélisme à un niveau beaucoup plus fin que dans les situations antérieures.

L’allocation de ressources (processeur, mémoire) aux processus peut par ailleurs donner lieu à deux phénomènes indésirables qui ont été identifiés et compris dès la fin des années 1960 :

• l’interblocage (en anglais deadlock), qui se traduit par le blocage mutuel de plusieurs processus, dont chacun attend des ressources occupées par les autres ;
• la privation, qui résulte de l’usage de priorités : un processus de faible priorité peut voir ses demandes indéfiniment retardées par une arrivée continue de processus plus prioritaires. En outre, l’usage de priorités peut donner lieu à un autre phénomène indésirable, plus subtil à analyser, l’inversion de priorités, dans lequel l’ordre d’exécution des processus n’est pas conforme aux priorités qui leur sont attachées.

Divers remèdes sont connus, dont les plus usuels reposent sur l’utilisation d’un ordre : l’interblocage est évité si tous les processus demandent leurs ressources dans le même ordre ; la privation est évitée si les processus sont servis dans l’ordre de leur arrivée ; si on veut néanmoins utiliser des priorités, on peut faire croître la priorité d’un processus avec son temps d’attente.

Virtualisation de la mémoire

Dans les premiers ordinateurs, la mémoire centrale était une ressource coûteuse, donc peu abondante. Même dans les applications mono-utilisateurs, elle était souvent trop petite pour contenir l’ensemble des programmes et des données. Les programmeurs devaient alors recourir à des schémas d’exécution avec recouvrement (overlay), où un découpage ingénieux des programmes permettait de les charger par « tranches » à la demande depuis une mémoire secondaire de grande capacité (tambour ou bande magnétique). Cela causait un surcroît de travail non négligeable pour les programmeurs et pénalisait le temps d’exécution.

Une avancée décisive fut réalisée en 1961 à l’université de Manchester, avec le concept de « mémoire à un niveau », mis en œuvre dans l’ordinateur Atlas [4]. Les programmes d’application pouvaient utiliser un espace d’adressage beaucoup plus grand que celui disponible sur la mémoire principale, l’information étant contenue dans l’ensemble constitué par la mémoire principale et la mémoire secondaire à tambour. Deux notions essentielles étaient ainsi introduites :

• la dissociation entre les adresses utilisées par les programmes — nous les appelons « virtuelles » bien que ce terme n’ait été introduit que plus tard — et les adresses physiques des emplacements correspondants en mémoire principale ou secondaire ;
• la gestion automatique par le système d’exploitation, et non par les programmeurs, de la correspondance entre adresses virtuelles et adresses physiques.

Ce dernier aspect impliquait la gestion des transferts entre mémoire principale et mémoire secondaire pour amener en mémoire principale l’information nécessaire, lors de son utilisation. Ce transfert était réalisé par « pages » de taille fixe (512 mots sur l’Atlas). Comme les programmes étaient souvent réutilisés, un algorithme d’apprentissage était mis en place pour réduire le temps global de ces transferts, ses performances étant voisines de celles obtenues par un programmeur expérimenté. Néanmoins, les performances se dégradaient rapidement quand la charge dépassait un certain seuil. Ce phénomène d’« écroulement » ne fut compris et traité qu’en 1968 (voir plus loin).

Dans les années 1965-68 furent posées les bases scientifiques de la mémoire virtuelle, toujours largement en vigueur aujourd’hui [5]. Deux aspects complémentaires furent ainsi approfondis :

• l’organisation et la protection de la mémoire virtuelle, telle que vue par les utilisateurs ;
• la mise en œuvre concrète de cette mémoire, notamment dans les systèmes en temps partagé, qui se développaient rapidement à cette époque.

La figure 3 montre schématiquement le principe de réalisation d’une mémoire virtuelle pour un processus. On a distingué, dans la mémoire physique, la notion de page (contenu) de la notion de case (contenant, ou suite d’emplacements pouvant accueillir une page).

Figure 3. Réalisation d’une mémoire virtuelle.
La mémoire virtuelle peut être plus grande que la mémoire physique mais pas plus grande que la capacité d’adressage du processeur. Une page virtuelle dont le contenu est en mémoire physique est immédiatement accessible. Une page virtuelle dont le contenu n’est que sur disque doit être amenée en mémoire physique pour être accessible ; il faut pour cela lui trouver une case libre. S’il n’y a plus de case libre, il faut en libérer une et donc copier son contenu sur disque s’il a changé.

Dans ce schéma, la mémoire virtuelle est implicitement définie comme un espace unique d’un seul tenant. Un schéma plus élaboré fut proposé en 1965 par Jack Dennis, du MIT [6]. Il repose sur la notion de segment, c’est-à-dire d’unité logique d’information constituée d’une tranche de mémoire de taille variable composée d’emplacements contigus. Un utilisateur peut ainsi organiser ses informations en plusieurs segments (modules de programmes, différentes données, etc.). Des segments peuvent être partagés entre plusieurs utilisateurs. L’accès aux segments doit pouvoir être protégé contre des accès non-autorisés. Le schéma initial (illustré par la figure 3 ci-dessus) devient un cas particulier, celui d’un segment unique de taille fixe.

Avec les performances des processeurs de l’époque, une mise en œuvre efficace de la segmentation supposait qu’elle soit inscrite dans l’architecture même de la machine. Quelques machines à mémoire segmentée furent ainsi réalisées, notamment le GE 645, utilisé par Multics, un système expérimental en temps partagé construit au MIT de 1965 à 1970 en association avec les Bell Labs et General Electric (voir le document La naissance des systèmes d’exploitation). Néanmoins, l’idée d’une architecture à mémoire segmentée ne s’imposa pas généralement. Même si les processeurs actuels permettent d’utiliser des adresses segmentées, les systèmes d’exploitation courants comme Unix ou Windows n’utilisent pas ce mécanisme (sinon pour un usage interne limité).

La notion de segment, gardant toutefois tout son intérêt, est simulée par une voie logicielle, en définissant des tranches de mémoire à l’intérieur d’une mémoire virtuelle unique de grande taille, elle-même réalisée par un mécanisme matériel de pagination. Les systèmes usuels adoptent cette solution et assurent, également par voie logicielle, la protection sélective des segments.

Dans un système multi-utilisateur, comme l’étaient les systèmes en temps partagé du début des années 1970, chaque utilisateur peut exécuter un ou plusieurs processus, dont chacun dispose de sa mémoire virtuelle (comme illustré sur la figure 4 ci-dessous). L’isolation entre mémoires virtuelles est assurée par les tables de pages séparées, conservées par le système d’exploitation dans des zones protégées.

Bien que la mémoire virtuelle soit un outil de travail remarquable, il ne faut pas oublier qu’elle représente en quelque sorte un achat à crédit : pour que son contenu puisse être utilisé, un emplacement de mémoire virtuelle doit recevoir en fin de compte un support réel en mémoire centrale. Cet aspect avait été mal perçu par les concepteurs des premiers systèmes en temps partagé : à force de distribuer abondamment le « crédit », il arrivait un moment où les ressources physiques ne pouvaient plus faire face aux demandes cumulées. C’était le phénomène d’écroulement, qui conduisait à une paralysie complète du système.

Figure 4. Mémoire virtuelle dans un système multi-utilisateur.
Chaque processus possède sa propre mémoire virtuelle, indépendante de celles des autres processus (il a donc sa propre table de pages). Des processus peuvent partager des pages, à la même adresse (page V0) ou à des adresses différentes (page V6 de p1 et V7 de p2).

Les causes de ce phénomène furent expliquées en 1968 en utilisant un modèle simple de comportement des programmes, et un remède fut trouvé, fondé sur l’observation et la limitation de la charge instantanée de la même manière qu’on traite la congestion d’une autoroute par une restriction temporaire des entrées. Le principe de la limitation de charge est toujours utilisé aujourd’hui, bien que la grande taille des mémoires physiques rende le problème moins aigu.

3. Vers des machines virtuelles

Machines virtuelles et hyperviseurs

Après le processeur et la mémoire, l’étape suivante de la virtualisation est celle d’une machine tout entière. En fait, le terme de « machine virtuelle » recouvre plusieurs modes de fonctionnement. Nous nous intéressons seulement ici à la virtualisation d’une machine complète ; une autre forme de virtualisation, dont nous ne parlerons pas, réalise un mécanisme d’interprétation des langages de programmation.

Le principe d’un système de machines virtuelles, tel qu’il a été introduit par IBM entre 1965 et 1967, est schématisé sur la figure 5 (ci-dessous). Au-dessus d’une machine physique sont réalisées un certain nombre de machines « virtuelles » qui présentent à leurs utilisateurs une interface (jeu d’instructions, système d’interruptions, organes d’entrée-sortie) identique à celle de la machine sous-jacente. Ces machines sont complètement isolées les unes des autres : un programme s’exécutant sur une machine virtuelle ne peut lire ou modifier le contenu d’une autre machine virtuelle ; une défaillance logicielle d’une machine virtuelle n’a aucun effet sur les autres machines.

Figure 5. Hyperviseur et machines virtuelles.

La réalisation d’un système de machines virtuelles repose sur un composant logiciel appelé hyperviseur, qui s’exécute directement sur la machine physique, dont il constitue en quelque sorte un « super système d’exploitation ». La réalisation d’un hyperviseur pose des problèmes techniques délicats, car il doit virtualiser l’intégralité de la machine de base, y compris les mécanismes physiques de bas niveau tels que les interruptions, tout en assurant l’isolation mutuelle des machines virtuelles.

À quoi servent les machines virtuelles ? L’isolation mutuelle permet de faire fonctionner plusieurs systèmes d’exploitation différents sur une même machine physique. Néanmoins, la première utilisation des machines virtuelles a consisté à faire exécuter un grand nombre d’instances du même système, chacun servant un utilisateur unique : on simule ainsi un système en temps partagé. C’est le principe du système CP/CMS introduit en 1967 par le centre de recherche d’IBM de Cambridge sur l’ordinateur 360/67, spécialement conçu pour réaliser la mémoire virtuelle. Ce système, qui combinait un générateur de machines virtuelles (CP) et un logiciel interactif d’interprétation de commandes (CMS), exécuté sur chacune des machines, connut un grand succès, alors que le système d’exploitation « officiel » en temps partagé développé par IBM, Time Sharing System (TSS), ne réussit pas à atteindre ses objectifs.

Une extension du principe des machines virtuelles consiste à simuler des machines ayant un jeu d’instructions différent de celui de la machine physique sous-jacente. On peut ainsi expérimenter le jeu d’instructions d’une machine avant de la construire, ou faire exécuter des programmes écrits pour une machine dont on ne dispose pas d’exemplaire physique.

La réalisation d’un système de machines virtuelles pose le problème suivant : chaque machine virtuelle, étant une copie de la machine physique, doit fournir exactement la même interface que cette dernière. Or cette interface comporte des instructions dites « privilégiées », qui touchent aux mécanismes de base de la machine physique : système d’interruptions, commande des entrées-sorties, mémoire virtuelle. Comment réaliser ces instructions en exemplaires multiples tout en évitant les interférences sur le fonctionnement de la machine ? La solution repose sur des détails de mise en œuvre de ces instructions privilégiées.

Virtualisation descendante

Les exemples vus jusqu’à présent illustrent la forme « ascendante » de virtualisation (partage de ressources par mutiplexage), la plus répandue. Donnons maintenant un exemple de virtualisation « descendante » (hiérarchie de machines abstraites).

Le système de gestion de fichiers (SGF) est un élément central de tout système d’exploitation. Il contient l’ensemble de l’information — programmes et données — gérée par le système, y compris divers composants du système lui-même.

L’interface externe du système de gestion de fichiers accessible aux utilisateurs comporte quelques opérations de base (créer, détruire, lire, écrire, etc.). Ces opérations ne sont pas toujours explicitement visibles par les utilisateurs, qui n’accèdent aux fichiers que par le biais de leurs applications ou d’une interface graphique (par exemple, placer dans la corbeille l’icone représentant un fichier). À ce niveau, les fichiers sont désignés par des noms symboliques attribués par les utilisateurs.

En dernier ressort, un fichier est représenté physiquement par une suite de bits sur le disque dur de l’ordinateur. La distance entre l’interface externe du système de gestion de fichiers et cette représentation physique des fichiers est franchie en plusieurs étapes, que nous illustrons par l’exemple du système de gestion de fichiers d’Unix (simplifié pour les besoins du document).

Figure 6. Système de gestion de fichiers.

En partant du niveau le plus bas (voir figure 6), le contenu d’un fichier est un ensemble de pages (sections de taille fixe) sur le disque. Ces pages ne sont pas nécessairement contiguës, car les emplacements disponibles ne le sont pas, en raison de l’ordre non prévisible des allocations et libérations. Chaque fichier possède une table d’implantation (i-node) indiquant les emplacements sur disque des pages qui le constituent.

Au second niveau sont réalisées les opérations d’accès au fichier : lecture et écriture, matérialisées par des accès aux emplacements du disque contenant le fichier. À ce stade, un fichier est désigné par un simple « numéro de descripteur », obtenu au moment de l’ouverture, qui permet un accès rapide à l’i-node gardé en mémoire principale, et donc à toutes les informations du fichier.

Au troisième niveau est organisée la désignation des fichiers par des noms symboliques choisis par les utilisateurs. On y trouve des structures arborescentes, les catalogues, qui organisent la désignation selon un modèle hiérarchique. Les catalogues sont eux-mêmes des fichiers, et chaque catalogue donne accès via leurs i-nodes aux fichiers qu’il contient.

Une couche supplémentaire réalise la mise sous forme graphique de ce système de désignation : les catalogues sont présentés à l’utilisateur comme une hiérarchie de dossiers, sous-dossiers, etc., visualisés sous forme d’icones. Les accès aux fichiers se font au travers d’applications (à chaque fichier est associée la liste des applications qui peuvent le manipuler). Ainsi, les opérations de création, lecture, écriture, etc., sont exécutées dans l’application et sont rendues invisibles aux utilisateurs. Néanmoins, les utilisateurs avertis peuvent avoir accès à ces opérations en utilisant l’interface disponible au niveau inférieur.

Au total, un système de gestion de fichiers réalise une virtualisation du disque physique mise en œuvre au moyen d’une hiérarchie de machines abstraites. Ainsi se combinent les deux formes de virtualisation.

La modélisation et les débuts d’une approche quantitative

La fin des années 1960 voit aussi se développer une approche quantitative des systèmes d’exploitation. Avec l’avènement des systèmes en temps partagé, cet aspect devient important car les performances du système sont beaucoup plus directement ressenties par ses usagers que dans un environnement non interactif. Or, en raison de la complexité de ces nouveaux systèmes, les performances dépendent de l’interaction de nombreux facteurs dont la compréhension nécessite une analyse fine.

L’outil proposé pour cette analyse repose sur la théorie des réseaux de files d’attente. Initialement développé pour des applications de recherche opérationnelle, cet outil est bien adapté à l’analyse des systèmes d’exploitation, dans lesquels les requêtes des usagers doivent « faire la queue » pour obtenir diverses ressources existant en quantité limitée : processeur, mémoire, bande passante pour l’accès à la mémoire secondaire, etc. Les méthodes à base de files d’attente vont permettre d’abord une modélisation partielle des systèmes : allocation du processeur, gestion des disques. On passe ensuite à la modélisation de systèmes d’exploitation complets, puis de réseaux d’ordinateurs. Les outils de simulation alors développés permettent de prévoir les performances d’un système existant, d’identifier les facteurs de dégradation de ces performances, et de dimensionner une installation pour répondre à une charge prévisible.

Qu’en est-il aujourd’hui ?

En quelques années, entre 1965 et 1969, le domaine des systèmes d’exploitation des ordinateurs est passé du stade d’un savoir-faire technique, d’ailleurs fort développé, à celui d’une discipline scientifique aidant à la compréhension et à la construction de ces objets complexes. Comment se sont aujourd’hui transformés les principaux aspects de ce domaine ?

Les recherches sur la virtualisation, très actives dans les années 1970, connurent une pause au début des années 1980. En effet, la large diffusion des ordinateurs individuels a fait passer au second plan les techniques de temps partagé.

Néanmoins, dans les années 1990, les ordinateurs individuels dépendaient de plus en plus de ressources distantes accessibles par les réseaux, et les systèmes multiprocesseurs connaissaient un grand développement. La complexité de ces nouveaux systèmes amenait un retour en grâce des techniques de virtualisation [8]. Aujourd’hui, l’informatique en nuages (cloud computing) repose entièrement sur la virtualisation, à très grande échelle, de ressources à différents niveaux : machines physiques, plates-formes logicielles, applications. Les problèmes de garantie de performance, d’isolation mutuelle et de sécurité continuent de se poser, mais dans un environnement technique beaucoup plus complexe.

Une conséquence de cette complexité est que l’administration et la commande des grands systèmes actuels dépassent désormais les capacités des opérateurs humains. La gestion autonome des systèmes informatiques (autonomic computing) est devenue un sujet de recherche très actif, à la frontière de l’informatique et de l’automatique. Des techniques élaborées de modélisation et de commande sont appliquées pour adapter les systèmes aux variations de charge, pour réagir aux défaillances, pour survivre aux attaques, pour économiser l’énergie, tout en évitant la dégradation des performances.

Le parallélisme reste un défi majeur. Il intervient aujourd’hui dans des contextes très divers. D’une part, le calcul parallèle à grande échelle, que ce soit sur des multiprocesseurs ou des « grilles » de machines en réseau, fait intervenir jusqu’à des centaines de milliers de processeurs. D’autre part, l’augmentation de la vitesse des processeurs réalisés en circuits intégrés trouve ses limites en raison de la difficulté d’évacuer la chaleur dans des circuits de plus en plus denses. L’augmentation des performances passe alors par la réalisation de systèmes « multicœurs » comportant un grand nombre de processeurs à l’intérieur d’une même puce de silicium.

En dépit de ces avancées techniques, le parallélisme demeure un domaine mal compris, pour lequel des progrès fondamentaux restent à accomplir.

Enfin, il faut mentionner une percée décisive récente dans le domaine des systèmes d’exploitation : en 2008-2009, une équipe australienne [9] a réalisé la preuve complète, au sens mathématique, de la validité d’un noyau de système d’exploitation, c’est-à-dire de la conformité de ce noyau à ses spécifications, elles-mêmes exprimées dans un formalisme rigoureux. Un système commercial réalisé autour de ce noyau certifié est maintenant très largement diffusé dans le public, notamment à l’intérieur de téléphones portables.

Ce document fait partie d’une série consacrée à divers aspects de l’histoire de l’informatique, réalisée en conjonction avec un projet de musée virtuel sur ce thème, porté par l’association ACONIT.

Remerciements à Claude Kaiser pour ses précieuses remarques.

Notes

[1] Nous utilisons souvent le terme de « système » à la place de « système d’exploitation », lorsqu’il n’y a pas d’ambiguïté.
[2] Dijkstra, Edsger W. The structure of the THE multiprogramming system. Communications of the ACM, vol. 11, 5 (1968), pp 341-346.
[3] Dijkstra, Edsger W. Cooperating sequential processes, Technological University, Eindhoven (1965). In Programming Languages, F. Genuys, ed., Academic Press, 1968, pp. 43–112.
[4] Kilburn, T., Edwards, D. B. G., Lanigan, M. J., and Sumner, F. H. One-level storage system. IRE Transactions, EC-11, 2 (April 1962), pp. 223-235.
[5] Denning, Peter J. (1970). « Virtual Memory ». ACM Computing Surveys 2 (3): 153–189
[6] Dennis, Jack B. Segmentation and the design of multiprogrammed computer systems. Journal of the ACM, vol. 12, 4, Oct. 1965, pp. 589-602.
[8] Smith, James E. and Nair, Ravi. Virtual Machines, Morgan Kaufmann, 2005.
[9] Klein, Gerwin; Elphinstone, Kevin; Heiser, Gernot; Andronick, June; Cock, David; Derrin, Philip; Elkaduwe, Dhammika; Engelhardt, Kai; Kolanski, Rafal; Norrish, Michael; Sewell, Thomas; Tuch, Harvey; Winwood, Simon « seL4: Formal verification of an OS kernel » (PDF). 22nd ACM Symposium on Operating System Principles. Big Sky, MT, USA (October 2009).