Chapitre 2 Principe de fonctionnement de l'ordinateur

Introduction

Nous avons défini le système d'exploitation d'abord comme un logiciel destiné à faciliter l'utilisation d'un ordinateur, puis comme un programme dont la fonction principale est de déclencher l'exécution d'autres programmes. Nous allons le définir maintenant comme un programme qui permet à un ordinateur de faire plusieurs choses à la fois.

Pour pouvoir élaborer et nuancer cette définition, et comprendre notamment ce qu'elle comporte de paradoxe, il nous faut approfondir un peu notre vision de l'ordinateur que nous avons défini comme un automate capable d'effectuer des actions dites primitives (déterminées par ses concepteurs) selon l'énumération qu'en donne le texte d'un programme.

2.1 Modèle de l'ordinateur

C'est John von Neumann, mathématicien hongrois émigré aux États--Unis, qui dans un document tout à fait remarquable de 1945 intitulé First Draft of a Report on the EDVAC et désormais disponible en ligne [50] a proposé pour l'ordinateur l'architecture représentée par la figure 2.1¹.

Figure 2.1 : Structure de l'ordinateur

Les unités de contrôle², arithmétique et d'entrée--sortie constituent à elles trois l'unité centrale, ou le processeur de l'ordinateur. Le processeur est constitué de circuits électroniques qui peuvent exécuter des actions ; de nos jours il est généralement réalisé sous la forme d'un composant électronique unique nommé microprocesseur. L'ensemble des actions « câblées » dans le processeur constitue le jeu d'instructions du processeur (les « actions primitives ») et détermine le langage élémentaire de son utilisation, appelé « langage machine ». À chaque instruction identifiée par son code correspond un circuit particulier.

Le rôle de l'unité de contrôle consiste à permettre le déclenchement de l'action (l'instruction) voulue au moment voulu. Cette instruction peut appartenir à l'unité arithmétique, à l'unité d'entrée-sortie ou à l'unité de contrôle elle-même. Une instruction peut en outre consulter le contenu de la mémoire (la « lire ») ou modifier le contenu de la mémoire (y « écrire »). De façon générale, une action consiste soit à consulter ou à modifier l'état de la mémoire ou d'un des registres A ou R (qui sont des éléments de mémoire spéciaux incorporés à l'unité centrale), soit à déclencher une opération d'entrée-sortie (communication avec le monde extérieur et notamment l'utilisateur humain), soit encore à modifier la séquence des instructions formulées par le programme en commandant de « sauter » un certain nombre d'instructions sans les exécuter, ou de « revenir en arrière » pour répéter des instructions déjà déroulées (le texte du programme n'est pas modifié, mais est modifié l'ordre dans lequel il est « lu »).

Point fondamental, un ordinateur conforme au modèle de von Neumann exécute une instruction, et une seule, à la fois (principe d'exécution séquentielle). En ce début de vingt-et-unième siècle, pratiquement tous les ordinateurs se conforment extérieurement à ce modèle, à quelques perfectionnements de réalisation technique près qui améliorent les performances mais ne modifient ni le modèle d'exécution ni la sémantique du traitement de l'information (nous donnons une brève description de ces techniques au chapitre 9).

Comment indique-t-on à l'unité de contrôle le « moment voulu » pour déclencher telle ou telle action ? C'est écrit dans le texte d'un programme. Où est le programme ? Dans la mémoire.

La mémoire est constituée d'éléments susceptibles de prendre des états. Un élément de base de la mémoire peut prendre deux états distincts et peut servir à représenter une information élémentaire, ou bit (binary digit, chiffre binaire). Cette représentation d'une information par un élément de mémoire s'appelle un code. Une mémoire avec beaucoup de bits permet le codage d'informations complexes, dans la limite de la taille de la mémoire.

Comme les constituants élémentaires de la mémoire ont deux états, il est commode d'utiliser la numération binaire pour les représenter et pour effectuer des calculs à leur sujet. À l'époque de la scolarité de l'auteur, les systèmes de numération étaient introduits en classe de cinquième, mais je me suis laissé dire que cette introduction n'était plus systématique. L'annexe A en donne les rudiments.

Si les constructeurs des premiers ordinateurs avaient imaginé des constituants élémentaires à trois états, l'informatique aurait-elle été ternaire plutôt que binaire ? En fait tout laisse supposer que l'extraordinaire développement de l'informatique doit beaucoup à la grande simplicité de la numération binaire. Gottfried Wilhelm von Leibniz déjà l'avait conçu. Les nombreuses tentatives pour développer des machines décimales ont été décevantes, sauf pour les calculettes. Et même si la technique fournissait aujourd'hui des composants ternaires économiquement intéressants, il y a fort à parier que l'informatique resterait binaire pour profiter de la simplicité, de l'uniformité et de la régularité, en un mot de l'élégance, des modèles formels qui lui donnent sa charpente.

Comme le bit est une unité d'information trop élémentaire pour la plupart des usages, on manipule ordinairement des mots de mémoire, constitués d'un nombre donné de bits (32 ou 64 usuellement). La taille du mot est une caractéristique importante de l'architecture d'un ordinateur. On peut se représenter ces mots comme rangés dans un grand tableau de cases numérotées. Le numéro de chaque case est l'adresse du mot qu'elle contient.

Le chemin par lequel unité centrale, mémoire et organes d'entrée-sortie communiquent s'appelle de façon générique un « bus ». De façon un peu formelle, un bus est un graphe connexe complet, ce qui veut dire en langage courant que tous les éléments connectés au bus peuvent communiquer entre eux.

Quel fut le premier ordinateur ?

Comme suggéré par le titre de son rapport, First Draft of a Report on the EDVAC [50], les principes qu'y exposait von Neumann étaient destinés à s'appliquer à la construction d'une machine nommée EDVAC qui aurait été la première réalisation de l'architecture dite depuis de von Neumann. Il en fut autrement.

Comment von Neumann, mathématicien réputé à la position scientifique bien établie dans plusieurs domaines, de la théorie des ensembles au calcul des probabilités, en était-il venu à s'intéresser au calcul automatique ? D'abord, il avait fréquenté Alan Turing à l'IAS (Institute for Advanced Studies) de Princeton de 1936 à 1938 et il connaissait ses travaux. Plus tard, Herman H. Goldstine a raconté dans son livre [26] comment, en 1943, alors qu'il était « scientifique du contingent » dans l'U.S. Navy et qu'il travaillait au projet de calculateur ENIAC destiné aux calculs balistiques des canons de marine, il avait aperçu von Neumann sur le quai de la gare d'Aberdeen (Maryland), avait osé l'aborder et lui avait parlé de son travail. Von Neumann avait été immédiatement passionné et s'était joint au projet.

Le projet ENIAC (pour Electronic Numerical Integrator and Computer) devait produire une grande machine à calculer et il avait été mis en route à l'Université de Pennsylvanie en 1943 sous la direction de J. Presper Eckert et de John W. Mauchly. Une fois réalisé (à la fin de 1945), l'ENIAC serait le plus grand calculateur de son temps. Mais l'ENIAC ne répondait pas à la définition que nous avons donnée de l'ordinateur : une machine programmable, automatique et universelle. La réalisation d'un calcul avec l'ENIAC demandait des interventions manuelles pour adapter la configuration de la machine, ce qui va à l'encontre de l'exigence d'être automatique et programmable. En fait la programmation était réalisée essentiellement au moyen d'interrupteurs et de tableaux de connexions, comme sur les machines mécanographiques. C'est en pensant aux moyens d'améliorer ce fonctionnement que von Neumann a conçu son architecture.

Plus tard, Eckert et Mauchly ont accusé von Neumann d'avoir pillé leurs idées, mais cette thèse ne résiste pas à la simple lecture du First Draft of a Report on the EDVAC. Il est légitime de dire qu'entre l'EDVAC et l'ENIAC il y a une différence du même ordre qu'entre la lunette de Galilée et les lunettes réalisées auparavant par un Hollandais anonyme : Galilée a certes bénéficié de l'exemple de son prédécesseur, mais, comme l'a souligné Alexandre Koyré, sa lunette est la réalisation d'une théorie scientifique, alors que l'instrument de son prédécesseur était le fruit d'une démarche empirique. Le texte de von Neumann est un des fondements (avec la machine de Turing) d'une science nouvelle. La construction de l'EDVAC prendra du retard, et la première machine de von Neumann sera britannique.

En 1995 de grandes manifestations ont été organisées aux États-Unis pour célébrer le cinquantenaire de l'ENIAC comme celui du premier ordinateur, mais c'était abusif. L'ENIAC représente sans doute l'apogée des calculateurs pré-informatiques.

En fait les premiers ordinateurs véritables furent le MARK 1 de l'Université de Manchester, réalisé sous la direction de Max Newman, opérationnel en 1948, et l'EDSAC, construit à l'Université de Cambridge sous la direction de Maurice Wilkes en 1949. Les querelles d'antériorité entre ces deux machines ne sont et ne seront sans doute pas tranchées, mais le fait que cela se joue entre elles n'est guère remis en cause. Les principes à la base de ces deux machines avaient incontestablement été élaborés par John von Neumann aux États-Unis, la théorie sous-jacente était celle du Britannique Alan Turing, mais les réalisation étaient britanniques, d'où sans doute la tentation d'une usurpation commémoratrice américaine...

Cette question de primauté ou pas de l'ENIAC est loin d'être un détail. Selon la réponse qu'on lui donne :

l'ordinateur a été inventé par Eckert et Mauchly, ou par von Neumann ;
la première réalisation est américaine, ou britannique ;
l'informatique est née de l'évolution technique normale des machines mécanographiques, ou d'une rupture épistémologique dont la source se trouve dans la recherche fondamentale en mathématiques ;
l'informatique est un bricolage d'ingénieur astucieux, ou une percée intellectuelle de première importance.

2.2 La machine de Turing

Le but de Turing lorsqu'il a imaginé sa machine (toute abstraite et théorique, il va sans dire) était de donner une chair à la notion abstraite de procédure effective. Une procédure effective, c'est un procédé pour effectuer un calcul, par exemple la démarche à suivre pour faire une multiplication, telle qu'elle vous a été enseignée à l'école.

Le modèle formel d'une procédure effective (pour décrire un algorithme) doit posséder certaines propriétés. Premièrement, chaque procédure doit recevoir une définition finie. Deuxièmement, la procédure doit être composée d'étapes distinctes, dont chacune doit pouvoir être accomplie mécaniquement. Dans sa simplicité, la machine de Turing déterministe composée des éléments suivants répond à ce programme :

une mémoire infinie représentée par un ruban divisé en cases. Chaque case du ruban peut recevoir un symbole de l'alphabet défini pour la machine ;
une tête de lecture capable de parcourir le ruban dans les deux sens ;
un ensemble fini d'états parmi lesquels on distingue un état initial et les autres états, dits accepteurs ;
une fonction de transition qui, pour chaque état de la machine et chaque symbole figurant sous la tête de lecture, précise :
- l'état suivant ;
- le caractère qui sera écrit sur le ruban à la place de celui qui se trouvait sous la tête de lecture ;
- le sens du prochain déplacement de la tête de lecture.

La configuration d'une machine de Turing peut être représentée par un triplet (q, m, u) où q est l'état de la machine, m le mot qui apparaît sur le ruban avant la position de la tête de lecture, u le mot figurant sur le ruban entre la position de la tête de lecture et le dernier caractère non blanc.

Un arc du graphe de la fonction de transition peut être représenté par un quintuplet (qi, si, sj, x, qj) où :

q_i est l'état de départ ;
s_i est le symbole pointé avant l'exécution du cycle ;
s_j est le symbole qui doit remplacer s_i ;
x est un élément de {G, D, w} (G pour gauche, D pour droite, w pour un déplacement nul) ;
q_j est l'état de fin de cycle.

Pour se donner une intuition de la chose, imaginons une M.T. (machine de Turing) avec un alphabet {0, 1, <espace>} ; nous conviendrons d'utiliser le système de numération unaire (celui que vous utilisez pour marquer les points au ping-pong, autrement dit « les bâtons ») et de séparer les nombres par des 0. Pouvons-nous additionner deux nombres ?

Figure 2.2 : Un modèle théorique

Le ruban mentionne successivement les nombres 4 et 3. Pour les additionner il suffit que la tête de lecture lise successivement les quatre chiffres unaires qui constituent le nombre 4, dont la fin sera indiquée par l'occurrence du signe zéro. Il faudra alors supprimer le zéro et récrire d'une case à droite les chiffres du nombre 3, jusqu'à la rencontre d'un signe zéro, qui subira le même traitement, pour obtenir 7. L'écriture de la table des transitions constituera pour le lecteur un exercice amusant.

On peut doter sa Machine de Turing de l'alphabet fini de son choix. Son ruban peut être infini dans les deux sens ou dans un seul. Elle peut même avoir plusieurs rubans. On montre (Turing a montré) que ces diverses machines sont équivalentes. Tous les langages de programmation modernes sont équivalents à la Machine de Turing.

1: La figure et les deux alinéas qui suivent sont empruntés à mon livre Initiation à la programmation avec Scheme, publié en 2001 par les Éditions Technip, avec l'aimable autorisation de l'éditeur.
2: Une traduction plus exacte de l'anglais control unit serait « unité de commande ». L'usage a entériné l'impropriété.