Informatique

L'évolution des ordinateurs et des systèmes informatiques

De la salle de 27 tonnes au téléphone de 135 grammes, l'ordinateur a rapetissé ; mais ce qui l'a rendu utile, c'est le système qui l'organise : partager le processeur, ruser avec la mémoire, relier les machines, puis les fondre dans un nuage. Cinq planches pour le comprendre en manipulant.

Cinq générations de machines

On découpe souvent l'histoire des ordinateurs en générations, selon le composant qui réalise les calculs. À chaque génération, la machine devient plus petite, moins chère et plus nombreuse, et la manière de l'utiliser change : c'est le rôle du système d'exploitation, le programme qui gère le matériel pour le compte des autres programmes et des utilisateurs.

Les machines à la même échelle qu'un être humain (silhouette grise). L'animation passe d'une génération à la suivante.

Génération	Composant	Exemples	Comment on s'en sert
1 · 1946 – 1958	Tubes à vide	ENIAC (1946), UNIVAC I (1951), Bull Gamma 3 (1952)	Un seul utilisateur à la fois, qui réserve la machine et la programme lui-même.
2 · 1958 – 1964	Transistors	IBM 1401, IBM 7090	Les travaux sont enchaînés par un moniteur : le traitement par lots.
3 · 1964 – 1971	Circuits intégrés	IBM System/360 (1964), mini-ordinateur PDP-8 (1965)	Le temps partagé : des dizaines d'utilisateurs devant des terminaux.
4 · 1971 –	Microprocesseurs	Micral N (1973), Apple II (1977), IBM PC (1981)	L'ordinateur personnel, puis l'interface graphique et le réseau.
5 · 2007 –	Puces mobiles et centres de données	Téléphones intelligents, informatique en nuage	Des milliards d'appareils légers appuyés sur des milliers de serveurs invisibles.

Planche 1

Le traitement par lots : ne plus laisser le processeur attendre

1956 – 1964

Dans les années 1950, un ordinateur coûte des millions et s'utilise à tour de rôle : chaque programmeur vient avec ses cartes perforées, l'opérateur monte les bandes, charge le programme, relance la machine. Pendant ces manipulations, le processeur ne fait rien. En 1956, General Motors et North American Aviation écrivent pour l'IBM 704 le premier moniteur (GM-NAA I/O) : les travaux sont regroupés en lots sur une bande et s'enchaînent automatiquement. C'est l'ancêtre des systèmes d'exploitation.

Organisation

Mise en place manuelle par travail8 min

Ordre des travaux

Chronogramme de la machine pour huit travaux. Gris : mise en place (le processeur attend) ; couleur : calcul utile. Le chiffre sous chaque bloc est l'heure à laquelle le programmeur récupère son résultat.

Durée totale de la journée

—

Taux d'utilisation du processeur (mesuré sur le chronogramme)

—

Contrôle : Σ calcul / (Σ calcul + Σ mise en place)

—

Attente moyenne d'un programmeur jusqu'à son résultat

—

Meilleur ordre possible, cherché parmi les 40 320 ordres

—

Ce qu'il faut retenir. Avec un opérateur, une bonne part de la journée est perdue en manipulations ; le moniteur ramène la mise en place à quelques secondes de lecture de bande et le taux d'utilisation approche 100 %. L'ordre des travaux ne change pas la durée totale, mais il change beaucoup l'attente moyenne : passer les travaux courts d'abord est optimal, et la recherche exhaustive parmi les 8! = 40 320 ordres possibles le confirme. Le prix : le programmeur n'est plus devant la machine, il dépose ses cartes le matin et récupère un listing le soir. En 1964, IBM généralise l'idée avec OS/360, un même système pour toute une gamme de machines compatibles.

Planche 2

Le temps partagé : chacun croit avoir la machine pour lui seul

1961 – 1969

En 1961, au MIT, Fernando Corbató met en service CTSS : plusieurs utilisateurs tapent en même temps sur des terminaux. Le système donne le processeur à chacun pendant un court quantum de temps, puis passe au suivant, à tour de rôle : c'est l'ordonnancement en tourniquet. Chaque changement d'utilisateur, la commutation de contexte, coûte un peu de temps, car il faut ranger l'état d'un programme et recharger celui du suivant. Multics (1965), puis Unix (1969), héritent de cette idée.

Quantum3

Coût d'une commutation0,2

Cinq utilisateurs soumettent au même instant des demandes de durées différentes (en unités de temps). Chaque ligne montre quand le processeur travaille pour l'utilisateur ; les petits traits rouges sont les commutations. Le losange marque la première réponse, le trait vertical la fin.

Première réponse, en moyenne

—

Fin de la demande, en moyenne

—

Commutations / temps perdu

—

Contrôle : durée totale = Σ demandes + commutations × coût

—

Sans partage (chacun son tour, en entier) : première réponse moyenne

—

Ce qu'il faut retenir. Un petit quantum donne à chacun une réponse presque immédiate, d'où l'impression d'avoir la machine pour soi ; mais il multiplie les commutations, et le temps perdu grandit. Un grand quantum revient au traitement par lots : très peu de pertes, mais les derniers servis attendent longtemps leur première réponse. Tout système interactif, du terminal de 1961 au téléphone d'aujourd'hui, règle ce compromis ; les systèmes modernes changent de tâche des centaines de fois par seconde.

Planche 3

La mémoire virtuelle : faire croire à une mémoire plus grande qu'elle n'est

1962

La mémoire rapide coûte cher. En 1962, l'ordinateur Atlas de l'université de Manchester invente la mémoire virtuelle : le programme est découpé en pages de taille fixe, rangées sur un tambour magnétique, et seules quelques-unes sont chargées dans les cadres de la mémoire rapide. Quand le programme demande une page absente, c'est un défaut de page : le système va la chercher et doit choisir une page à renvoyer. Trois stratégies : la plus ancienne (FIFO), la moins récemment utilisée (LRU), ou, en théorie, celle dont on aura besoin le plus tard (OPT, Bélády, 1966), impossible en pratique car elle exige de connaître l'avenir.

Suite des pages demandées

Stratégie

Cadres en mémoire3

Chaque colonne est une demande de page (en haut) ; dessous, le contenu des cadres juste après. Rouge : défaut de page, la page entrante est soulignée ; vert : la page était déjà là.

Défauts de page (stratégie choisie)

—

Les trois stratégies avec ce nombre de cadres

—

Contrôle : OPT ne fait jamais pire, de 1 à 6 cadres

—

Anomalie de Bélády (FIFO fait pire avec un cadre de plus)

—

Défauts de page en fonction du nombre de cadres pour les trois stratégies.

Ce qu'il faut retenir. Plus de cadres signifie en général moins de défauts, sauf avec FIFO : sur l'exemple de Bélády, 3 cadres donnent 9 défauts et 4 cadres en donnent 10. Cette « anomalie de Bélády » (1969) a convaincu les concepteurs d'abandonner FIFO pour des approximations de LRU. Sur la boucle de 5 pages, LRU est catastrophique tant qu'il manque un seul cadre : la page renvoyée est justement la prochaine demandée. La mémoire virtuelle fonctionne parce que les vrais programmes ont de la localité : ils réutilisent longtemps les mêmes pages. Elle est aujourd'hui dans tous les ordinateurs et téléphones, et protège en plus chaque programme des autres.

Planche 4

Les réseaux : découper les messages en paquets

1969 – 1991

Le téléphone réserve un circuit pour toute la durée d'un appel. Les réseaux informatiques font autrement : le message est découpé en paquets qui voyagent chacun pour soi, de nœud en nœud, par le meilleur chemin du moment. ARPANET relie quatre universités américaines en 1969 ; en France, le réseau Cyclades de Louis Pouzin (1972) invente le datagramme, un paquet entièrement autonome, idée reprise par TCP/IP, adopté par ARPANET le 1ᵉʳ janvier 1983. Touchez une liaison pour la couper : les paquets trouvent un autre chemin.

Départ

Arrivée

Un réseau inspiré d'ARPANET au début des années 1970. Le nombre sur chaque liaison est son délai en millisecondes. Le meilleur chemin, calculé par l'algorithme de Dijkstra, est en bleu ; une liaison coupée est en pointillé rouge.

Meilleur chemin (Dijkstra)

—

Délai / nombre de sauts

—

Contrôle : énumération de tous les chemins simples

—

Liaisons à couper au minimum pour séparer départ et arrivée

—

Paquets arrivés / remis dans l'ordre par numéro

—

Ce qu'il faut retenir. Un réseau maillé survit aux pannes : tant qu'il reste un chemin, les paquets passent, simplement un peu plus lentement. Le nombre minimal de liaisons à couper pour isoler deux nœuds (calculé ici par un algorithme de flot maximal) mesure cette robustesse. Comme les paquets peuvent prendre des chemins différents, ils arrivent parfois dans le désordre : chacun porte un numéro, et le protocole TCP les remet en ordre et redemande ceux qui manquent. Sur ces fondations, Tim Berners-Lee crée le Web au CERN (1989-1991).

Planche 5 · signature

Le nuage : des milliers de machines qui n'en font qu'une

2006 – aujourd'hui

Quand vous consultez une messagerie ou un site de cartes, aucune machine particulière ne vous répond : la demande est reçue par un répartiteur de charge qui la confie à l'un des milliers de serveurs d'un centre de données, et vos données existent en plusieurs copies sur des serveurs différents. En 2006, Amazon commence à louer cette puissance (Amazon Web Services) : c'est l'informatique en nuage. Deux idées mathématiques simples la rendent possible.

Chaque serveur est indisponible une petite fraction p du temps (panne, mise à jour, coupure). Si une donnée existe en r copies sur des serveurs qui tombent en panne indépendamment, elle n'est inaccessible que si les r serveurs sont en panne ensemble.

Indisponibilité d'un serveur p10 %

Nombre de copies r3

Les r serveurs qui portent une copie, simulés en continu (vert : en marche, gris : en panne). En bas, le ruban du temps : une bande rouge chaque fois que les r copies sont tombées en même temps.

Indisponibilité mesurée (2 millions de pas simulés)

—

Formule pʳ (pannes indépendantes)

—

Disponibilité et nombre de « neuf »

—

Temps d'indisponibilité par an

—

On répartit n demandes entre n serveurs. Envoyer chaque demande à un serveur tiré au hasard est simple, mais certains serveurs reçoivent beaucoup plus que leur part. Une variante presque aussi simple tire deux serveurs au hasard et choisit le moins chargé des deux (Azar, Broder, Karlin et Upfal, 1994).

Stratégie

Les 100 serveurs et le nombre de demandes reçues par chacun. La ligne rouge marque le serveur le plus chargé, qui ralentit tout le service.

Charge du serveur le plus chargé (ce tirage)

—

Serveurs restés sans travail

—

Contrôle : somme des charges

—

Ce qu'il faut retenir. La copie transforme des machines médiocres en un service presque parfait : avec p = 10 %, une copie est indisponible 36 jours par an, trois copies moins de 9 heures, la mesure suivant la formule pʳ. Encore faut-il que les pannes soient indépendantes : c'est pourquoi les copies sont placées dans des bâtiments, voire des régions, différents. Pour la charge, le simple fait de comparer deux serveurs au lieu d'un fait passer la charge maximale d'une croissance en ln n / ln ln n à une croissance en ln ln n : le tableau le montre, le maximum grimpe avec le hasard simple et reste presque immobile avec deux choix. Le tourniquet est parfait ici, mais il exige un chef d'orchestre unique, ce qui est impossible quand des milliers de répartiteurs travaillent en parallèle.

Frise des jalons

En résumé

Enchaîner

Le moniteur de traitement par lots supprime l'attente entre les travaux : le système d'exploitation naît pour rentabiliser une machine coûteuse.

Le temps partagé découpe le processeur en tranches et la mémoire virtuelle découpe la mémoire en pages : chacun croit disposer d'une machine entière.

Relier

Les paquets et le routage font des réseaux qui contournent les pannes ; TCP/IP et le Web relient toutes les machines.

Fondre

Le nuage réunit des milliers de serveurs ordinaires ; copies et répartition de charge leur donnent la fiabilité d'une seule machine parfaite.

Pour aller plus loin

Andrew Tanenbaum et Herbert Bos, Systèmes d'exploitation, Pearson (trad. de Modern Operating Systems).
Paul Ceruzzi, A History of Modern Computing, MIT Press, 2ᵉ éd. 2003.
Pierre Mounier-Kuhn, L'Informatique en France, de la seconde guerre mondiale au Plan Calcul, Presses de l'université Paris-Sorbonne, 2010.
László Bélády, « A study of replacement algorithms for a virtual-storage computer », IBM Systems Journal, 1966.
Louis Pouzin, « Presentation and major design aspects of the CYCLADES computer network », 1973.
Yossi Azar, Andrei Broder, Anna Karlin et Eli Upfal, « Balanced allocations », STOC, 1994.

Les durées de la planche 1 et les délais du réseau de la planche 4 sont des valeurs d'illustration ; les durées et masses citées dans l'introduction (ENIAC, PDP-8, premier iPhone) sont celles des fiches historiques.