# Fiche de lecture :

## 1 - Présentation des personnages

### 1.1 Mondanité des systèmes

Dans les chapitres suivants :
- nature
- naissance
- et histoire des SE

Rôle des SE dans notre société
Apparition assez tardive dans l’évolution de l’informatique
Invasion de nos activités par les systèmes d’exploitation

### 1.2 Quelques définitions

**Système d'exploitation** : logiciel facilite utilisation ordinateur

**Ordinateur :** matériel composé de fils, circuits, etc., inutilisable sans le logiciel constitué de programmes. Automate capable d’effectuer des actions dites primitives , de les enchaîner dans l’ordre voulu, de les répéter et surtout de choisir, en fonction du résultat des actions précédentes, la prochaine action à effectuer entre deux ou plusieurs possibilités connues à l’avance.
Un ordinateur est un automate à états fini.

**Jeu d'instructions :** Ensemble des primitives d’un ordinateur

Chaque instruction est un objet physique, en l’occurence un circuit électronique, partie du processeur qui anime l’ordinateur.

**Programme :** texte qui énumère, dans le bon ordre, les primitives de l’ordinateur dont l’exécution mènera à la production du résultat recherché. Texte du programme qui pilote la séquence des actions effectuées par l’ordinateur.

**Rédiger un programme pour un ordinateur :** décrire la séquence de ses états successifs qui vont permettre d’obtenir le résultat voulu.

**Une procédure effective :** Enchaînement d’opérations élémentaires qui permettront d’exécuter les calculs nécessaires à la solution de problèmes pour lesquels existent des solutions calculables.

**Programmer :** Traduire ces opérations élémentaires en termes d’actions primitives d’un ordinateur.

### 1.3 La couche visible du système

Système d’exploitation intermédiaire entre l’utilisateur et l’ordinateur.

**Interface** : Gestionnaire de fenêtres (partie la plus tournée vers l’utilisateur directement accessible à la perception )

Interface de haut niveau VS interface de bas niveau

### 1.4 Une représentation : le modèle en couches

**Noyau** : programmes qui interagissent directement avec les éléments matériels de l’ordinateur.

**Architecture en couches** : modèle destiné à se représenter intellectuellement les choses par des abstractions.

Couches basses VS couches hautes

**Interface** : Les règles et les conventions qui régissent les échanges entre 2 couches


Soit un système dont les communications avec d’autres systèmes sont représentées par un modèle à n couches numérotées de 1 à n.

### 1.5 L’informatique est (aussi) une science

Discipline de l'informatique :


Les ellipses -> noms des grands paradigmes qui donnent les clés de l’informatique.

Chacun l’imagine selon les applications qui en sont faites dans son domaine.
Ex : physicien a tendance à la réduire au calcul, tant cette activité est pour lui associée à l’informatique.

### 1.6 Architectures

Parallèle avec la préocupation première d'un architecte : les moyens de circuler

Comment l’information circule-t-elle entre le disque dur et la mémoire centrale, de celle-ci au processeur ?
Comment les différents programmes d’un logiciel partagent-ils des données, ou au contraire en garantissent-ils l’accès exclusif ?

Le système d’exploitation est le grand aiguilleur et régulateur.

### 1.7 Enjeux d’une histoire

Histoire de l’informatique peut être considérée sous différents angles :

- histoire de la pensée scientifique
- histoire des techniques de calcul automatique
- histoire des ordinateurs

Poursuite du rêve de construire un être mécanique pensant

Engagement dans cette voie de philosophes et savants parmi les plus éminents :

- Blaise Pascal
- Gottfried Wilhelm Leibniz
- John von Neumann

Von Neumann est plus respecté pour la théorie des jeux ou ses travaux de mathématiques pures que pour son invention de l’ordinateur, la plus importante du XXe siècle.

Vision de l'histoire de l'informatique du point de vue mécanique et éléctronique tronquée.

## 2 - Principe de fonctionnement de l’ordinateur

Système d'exploitation permet à un ordinateur de faire plusieurs choses à la fois.

### 2.1 Modèle de l’ordinateur

John von Neumann, dans "First Draft of a Report on the EDVAC" (1945) a proposé l’architecture suivante :


Processeur de l'ordinateur (unité centrale) :
- unité de contrôle
- unité arithmétique
- unité d’entrée–sortie

Instruction peut consulter le contenu de la mémoire ou modifier le contenu de la mémoire.

Actions :
- consulter ou à modifier l’état de la mémoire ou d’un des registres 3 A ou R
- déclencher une opération d’entrée-sortie
- modifier la séquence des instructions formulées par le programme en commandant de « sauter » un certain nombre d’instructions sans les exécuter
- « revenir en arrière » pour répéter des instructions déjà déroulées

Un ordinateur style von Neumann exécute une instruction à la fois.

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.

Cette représentation d’une information par un élément de mémoire s’appelle un code.

Mémoire avec beaucoup de bits permet codage d’informations complexes, dans la limite de la taille de la mémoire.

Constituants élémentaires de la mémoire ont deux états donc on utilise la numération binaire pour les représenter et pour effectuer des calculs à leur sujet.

Extraordinaire développement de l’informatique doit à la simplicité de la numération binaire.

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.

La taille du mot est une caractéristique importante de l’architecture d’un ordinateur.

Le chemin par lequel unité centrale, mémoire et organes d’entréesortie communiquent s’appelle de façon générique un « bus ».

Bus : graphe connexe complet, veut dire que tous les éléments connectés au bus peuvent communiquer entre eux.

### 2.2 Traitement de l’information

L’être humain et l’ordinateur ne sont pas aptes aux mêmes actions primitives.
L’être humain est capable d’inventer à tout moment de nouvelles primitives, et d’en oublier d’autres.

Le traitement des données doit être effectif (doit aboutir pratiquement au résultat).

Exemple: D = Ensemble des numéros d’immatriculation des voitures immatriculées en France.

Les règles de formation des numéros d’immatriculation sont la syntaxe du langage.

La correspondance qui, à tout numéro d’immatriculation bien formé, fait correspondre le département d’immatriculation de la voiture qui le porte est un traitement de D, on sait comment le réaliser.

Algorithme : Description (pour un exécutant) d’une méthode de résolution d’un problème (suite d’opérations qui fournissent le résultat cherché).

Description de la méthode doit être adaptée à l’exécutant.
Exécutant sait effectuer des primitives. (nombre fini d'actions)
Algorithme doit être constitué d’une combinaison de primitives.

Corrado Böhm et Giuseppe Jacopini ont démontré dans « Flow diagrams, Turing machines and languages with only two formation rules », CACM mai 1966.

Pour construire toutes les combinaisons possibles de primitives il suffisait de savoir réaliser l’enchaînement de deux primitives, la répétition d’une primitive donnée et le choix, pendant l’exécution d’un traitement, entre deux primitives selon le résultat d’un test.

Algorithme -> exécutant -> primitives

### 2.3 Mémoire et action, données et programme

Programme réside dans la mémoire, c’est l’innovation principale du modèle de von
Neumann.
Cette invention porte le nom de « machine à programme enregistré ».

Un programme c’est de l’information.
De l’information sur le traitement à appliquer à l’information, de la méta-information.
A l’époque de von Neumann le concept de programme était beaucoup moins bien formé qu’aujourd’hui.

L’idée de von Neumann consiste à dire que programme et données seront enregistrés dans la même mémoire.

Chaque case de mémoire peut contenir un mot, ce mot peut représenter soit une instruction, soit un élément de donnée.

### 2.4 À quoi ressemble le langage machine ?

#### 2.4.1 Premier programme

Instruction d'ordinateur en langage humain :

1. charge dans le registre A (aussi appelé accumulateur) le nombre qui
est dans la case mémoire numéro 20 ;
2. teste le contenu de A : s’il vaut zéro passe directement à l’instruction
6 ; sinon ne fais rien, c’est à dire continue en séquence ;
3. additionne au contenu du registre A le nombre qui est dans la case
mémoire numéro 21 (le résultat effacera l’ancien contenu du registre
A et prendra sa place) ;
4. copie le contenu du registre A dans la case mémoire numéro 22 (le
résultat effacera l’ancien contenu de la case mémoire numéro 22 et
prendra sa place) ;
5. imprime le contenu de la case mémoire numéro 22 ;
6. fin.

Dans la mémoire, ces textes sont codés sous forme d’un certain nombre de bits selon un format fixe.

L’unité de contrôle va chercher ces instructions l’une après l’autre et déclencher leur exécution.

Le décodage par l’unité de contrôle du code opération permet d’activer le circuit logique qui correspond à l’instruction désirée.

#### 2.4.2 Questions sur le programme (A revoir)

- Que signifie la valeur d’adresse décimal ?
- Pourquoi nos instructions ont-elles deux champs « registre » alors qu’elles utilisent un ou zéro registre ?
- Pourquoi les instructions numéro 5 et 6, qui ne font référence à aucun des deux registres A et R, ont-elles une valeur dans chaque champ registre, en l’occurrence 1 qui désigne A et 0 qui désigne R ?

Et l’instruction « test registre et branchement » ordonne, si le test est positif, que le déroulement du programme soit modifié pour se continuer par l’exécution de l’instruction qui se trouve à cette adresse .

Adresse = numéro de case mémoire.

Parce que le format des instructions de notre ordinateur fictif est fixe, et qu’il est prévisible qu’il aura besoin d’instructions qui concernent deux registres, par exemple une addition registre à registre.

#### 2.5 Mot d’état de programme (PSW)
PSW = Program Status Word
PC = Program Counter
IP = Instruction Pointer

Le processeur détient l’adresse de la prochaine instruction à exécuter dans le compteur de programme.

Au démarrage de l’ordinateur :
- le PC est chargé avec l’adresse de la première instruction à exécuter
- lors de l’exécution de chaque instruction le processeur place dans le PC l’adresse de l’instruction suivante

Un saut, ou branchement = placer dans le PC l’adresse de l’emplacement dans le texte du programme où est située l’instruction désirée.

### 2.6 Premier métalangage

#### 2.6.1 Vers un langage symbolique

BZ 1, FIN

0010 1100 0000 0101


BZ = 0010 1
1 = ?
FIN = ?

Il faudra calculer l’adresse qui correspond à FIN dans la sixième instruction, ce qui revient à compter combien il y a de mots entre la première et
la sixième instruction.
On dit que FIN est un nom symbolique qui désigne l’instruction d’adresse 5


Comment les symboles vont-ils être transformés en adresses ?

#### 2.6.2 Adresses absolues, adresses relatives

Symboles FIN, VAL1, VAL2, RESULT désignent des cases dans la mémoire.

Désigner chaque case par son numéro = adresse absolu

Programme symbolique =
- valeurs numériques des adresses par des noms symboliques
- codes opération binaires par des noms mnémoniques
- valeurs binaires par des nombres décimaux

Outil de traduction du programme symbolique en langage machine

#### 2.6.3 Assembleur, table des symboles

Assembleur = Programme qui traduit du langage symbolique en texte binaire exécutable

table des symboles

Pour traduire les symboles en adresse, Assembleur :
1 - dresse la liste de tous les symboles qu’il rencontre
2 - calcule la distance (en nombre de cases mémoire) entre le début du texte du programme et l’emplacement où le symbole est défini (cette distance est l’adresse relative désignée par ce symbole par rapport au début du programme, et où sa valeur est placée dans la table.)

Assembleur représente par rapport au langage machine un métalangage, plus loin de la réalité concrète de l’ordinateur.

#### 2.6.4 Traduction de langages

Böhm et Jacopini qui donne du même coup la voie d’une telle preuve et son équivalence avec le modèle de la machine de Turing. Un langage qui satisfait à toutes ces conditions est dit Turing-équivalent. Un programme qui traduit un langage de programmation dans un autre, généralement de plus bas niveau, s’appelle un compilateur. Un métalangage de l’assembleur est appelé un langage évolué.

Fortran fut en 1954 le premier langage évolué.

### 2.7 Comment cela démarre-t-il ?

Depuis les années 1990 c’est en général de la mémoire Flash, analogue à celle des clés USB et des disques SSD, ce qui permet de le modifier. Son action consiste à aller chercher sur une mémoire externe préparée à cet effet un autre programme un peu moins petit, à le recopier en mémoire centrale et à en déclencher l’exécution. Le programme que le circuit de démarrage va chercher sur la mémoire externe s’appelle programme de boot.

Plus précisément, la partie du système qui est lancée après l’amorçage, et qui en est l’âme, est appelée noyau du système.

### 2.8 Quel est le rôle de la mémoire ?

Nous avons introduit la notion de mémoire en disant qu’une action du processeur consistait à consulter ou à modifier l’état de la mémoire. La mathématique ignore cette notion d’état, qui introduirait dans son univers d’abstraction un aspect physique totalement incongru. Un mot de mémoire peut donc être utilisé pour emmagasiner un état du calcul.

Le modèle théorique qui rend compte de ce que nous venons de dire de la mémoire est la machine de Turing.

### 2.9 La machine de Turing

Le but de Turing lorsqu’il a imaginé sa machine était de donner une chair à la notion abstraite de procédure effective. Le modèle formel d’une procédure effective doit posséder certaines propriétés. Deuxièmement, la procédure doit être composée d’étapes distinctes, dont chacune doit pouvoir être accomplie mécaniquement.
* 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ù :
* qi est l’état de départ ;
* si est le symbole pointé avant l’exécution du cycle ;
* sj est le symbole qui doit remplacer si;
* x est un élément de {G,D,w} (G pour gauche, D pour droite, w pour un déplacement nul) ;
* qj est l’état de fin de cycle.

Pour se donner une intuition de la chose, imaginons une M.T. avec un alphabet {0,1,} ; nous conviendrons d’utiliser le système de numération unaire et de séparer les nombres par des 0. 42. Notre M.T. fonctionnera selon un cycle qui consiste à passer successivement par les trois phases suivantes, puis à recommencer :

**Phase de lecture** - La machine lit le contenu de la case courante et le
transmet comme paramètre d’entrée à la fonction de transition.
**Phase de calcul** - La valeur de la fonction de transition est calculée
en fonction de l’état courant et de la valeur contenue dans la case
courante.
**Phase d’action** - L’action déterminée par la fonction de transition est
effectuée ; elle comporte (éventuellement) une modification de la
valeur contenue dans la case courante et un déplacement de la tête
de lecture ; cette phase d’action est donc capable de produire des
symboles.


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.


On peut doter sa Machine de Turing de l’alphabet fini de son choix.
Elle peut même avoir plusieurs rubans. Tous les langages de programmation modernes sont équivalents à la Machine de Turing.

## 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. 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.

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 1. 704, avec sa mémoire de 4096 mots de 36 bits qui semblait énorme à l’époque , 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 . 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 beaucoup plus rapide qu’une imprimante, puis en les imprimant plus tard, pendant que l’unité centrale effectuerait d’autres calculs. 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étaprogramme », 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é.

### 3.2 Simultanéité et multiprogrammation

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 un milliard d’instructions par seconde, valeur banale en cette année 2018, nous voyons qu’il nous reste énormément de marge, puisqu’en 0,25 seconde il peut exécuter 250 millions d’instructions élémentaires, et en 0,02 seconde, 20 millions.
* Le système d’exploitation va donc permettre l’exécution « pseudosimultané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 020 seconde, ce qui laisse pendant les opérations manuelles (ou plus exactement digitales) un temps inoccupé de 0,249 980 seconde, disponible pour l’exécution de 249 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 19 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

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. Le processus, c’est la suite d’actions effectives qui va mener à la réalisation d’un gâteau concret.

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 œufs, le sucre et la farine de gâteau 1 sont bien entendus distincts de ceux de gâteau 2. 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. En procédant ainsi, le pâtissier réalise deux gâteaux en « pseudosimultanéité », ce qui permettra à ses deux clients d’être servis à temps pour le dessert.

1 au moment où on va l’abandonner pour s’occuper de gâteau 2, on note quelque-part la valeur du PC. Nous poursuivrons l’étude de cette notion centrale qu’est le processus à la section 3.7 p.

### 3.4 Réification du calcul

Nous avons vu à la section 2.3 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. 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 , une mémoire centrale , 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. 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é.

Alonzo Church réunit ces idées en un formalisme qui aujourd’hui encore satisfait théoriciens et praticiens de la programmation, le -calcul. En 1956 John MacCarthy élabore à partir du -calcul un langage de programmation, LISP, pour lequel il implémente à partir de 1958 un traducteur sur l’IBM 704. Le -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 -termes dans des -expressions. 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 , et il faut organiser ce volume d’information pour que les humains qui l’écrivent et le modifient puissent s’y retrouver. Quand un programme appelle un sous-programme 5 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.
Au moment de l’édition de liens, soit ils sont inclus dans le fichier exécutable , soit l’éditeur de liens place dans le fichier exécutable une référence vers leur emplacement dans une bibliothèque partageable 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.

### 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.

### 3.7 Vision dynamique du programme : le processus

Le programme vu sous cet angle est appelé un processus , process en anglais . Ainsi, si à un instant donné quinze personnes utilisent l’éditeur de texte Emacs 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 . Le système d’exploitation 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 œuvre 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.

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. Nous étudierons dans ce chapitre le processus au sens classique. L’étude des threads nécessite l’examen préalable des différents types de ressources à partager, elle trouvera sa place au chapitre 10 page 342.

### 3.8 Attributs du système d’exploitation

Quelles doivent être les caractéristiques d’un système d’exploitation, propres à mettre en œuvre 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 à 2018 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é de styles de réalisation et d’interfaces personne–ordinateur.

#### 3.8.1 Mode d’exécution privilégié

Certaines opérations ne sont accessibles qu’au mode privilégié. 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.

#### 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.

#### 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. 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.

##### 3.8.4.1 Étreinte fatale

Un groupe de processus P1, P2, ... 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.

#### 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.


#### 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.
Ainsi est assuré le maintien de la cohérence entre les multiples opérations, et évitée l’occurrence d’étreintes fatales. Comme conséquence de ce monopole des entréesorties, 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. 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.

### 3.9 Notion d’appel système

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.

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.

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. 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 été décrits p.

Nous prendrons l’exemple d’Unix, qui crée des processus avec l’appel système fork. init lance par l’appel système fork divers processus système utilitaires, puis 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 7. 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.

#### 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. 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 , 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.

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. 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. Tandis qu’une série de commandes du shell, cela s’envoie par courrier électronique de façon sûre. 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 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.

#### 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. – Le système exécute un programme spécial, dit pilote de périphérique, 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 diagramme des opérations est décrit par la figure 3.1.

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 . En effet un programme qui s’est arrêté ne pourra pas se remettre en action spontanément. Dans notre cas l’appel système 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. – 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

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. – 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. Le contrôleur sait accéder à la mémoire et sélectionner la bonne adresse.

À 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.

– La première chose que fait le superviseur d’interruption est de déterminer la nature de l’interruption. Il se débranche donc à la section appropriée, le superviseur d’interruption d’entrée-sorties. 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. – Une fois le contrôle transféré au superviseur d’interruption d’entréesortie, 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.

### 3.12 Ordonnancement de processus

Les systèmes que nous envisageons permettent la multiprogrammation, 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 12. 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 . L’ordonnanceur reçoit la main à un moment où tous les processus sont dans l’état d’attente.

Le rôle de l’ordonnanceur est de sélectionner parmi les processus prêts celui qui va être activé. 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. 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 , risquerait de bloquer tous les autres parce qu’il ne rendrait jamais la main.

#### 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 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.

#### 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.

#### 3.12.3 Préemption

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 pour l’exécution , comme déjà dit.

Les interruptions sont les seules circonstances à l’occasion desquelles un processus peut passer d’un état à 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. 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 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 , 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. 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.

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 donc, il n’est par construction pas préemptible par un processus en mode utilisateur . 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.

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.

##### 3.12.4.1 Atomicité des opérations

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 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 multiprocesseur. Il faut donc que la section critique soit composée d’une instruction unique sur un cycle unique.

– le système est cohérent à l’issue de l’opération. Cette instruction est généralement nommée TAS . 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 et atomic_inc_and_test.

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.

##### 3.12.4.2 Masquage des interruptions

Tous les processeurs courants possèdent un dispositif de masquage des interruptions. 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é. 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...

##### 3.12.4.3 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. 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. 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.

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. 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. 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 . 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 . 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 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. 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.

### 3.13 Chronologie des premiers systèmes d’exploitation

1956 - GM-NAA I/O
1957 - Atlas Supervisor
1960 - IBSYS
1960 - MCP (Master Control Program)
1961 - CTSS fut le premier système de temps partagé
1964 - OS/360 d’IBM
1965 - Multics
1969 - Unix

Aujourd’hui ne survivent pratiquement que trois souches :
- **z/OS**
- **Windows**
- **Unix**

Unix { Linux, macOS, iOS, Android, FreeBSD, NetBSD, OpenBSD, ... }

## 4. Mémoire

### 4.1 Les problèmes à résoudre

La mémoire, terme d’un anthropomorphisme abusif hérité des « cerveaux artificiels » et auquel les Anglo-Saxons ont raison de souvent préférer storage, est un élément essentiel de l’architecture de von Neumann.
Lorsqu’un calcul est effectué par un ordinateur, ses phases successives sont représentées par différents états de la mémoire, ce qui est la réalisation technique du ruban de la machine de Turing. Dès que le calcul se complique, l’organisation de la mémoire joue un rôle important dans l’efficacité et l’intelligibilité du programme.
En outre, dès qu’un système d’exploitation permet la présence simultanée en mémoire de plusieurs programmes il faut partager entre eux la mémoire disponible et veiller à éviter que l’un n’empiète sur la zone réservée à l’autre.

### 4.2 La mémoire du programme

Gödel, Alan Turing et Alonzo Church, conduit à des notations d’une rigueur implacable mais d’un maniement délicat, qui réserverait la programmation des ordinateurs à une élite triée sur le volet de la mathématique.

#### 4.2.1 Les mots de mémoire

Dès von Neumann la mémoire est structurée, nous l’avons vu, en mots qui regroupent un certain nombre de bits. Si l’on considère chaque bit comme un chiffre binaire et un mot de taille n comme un nombre binaire de n chiffres, nous avons l’élément de base d’une arithmétique. Nous avons vu que nous devons aussi représenter en mémoire bien d’autres choses que des nombres. D’abord et malgré qu’en aient les physiciens et les numériciens, toutes les données ne sont pas des nombres, il y a aussi des chaînes de caractères, du texte, des images et des sons représentés de façon codée.

#### 4.2.2 Les adresses

Il faut allouer à chacun de ces objets un ou plusieurs mots de mémoire, et ensuite pouvoir les y retrouver. Ceci suppose un système d’identification et de repérage des mots individuels, un système d’adresses. Les adresses, nous l’avons vu en 2.4.1, sont manipulées par les instructions, c’est-à-dire qu’elles doivent tenir dans les registres 2. La taille d’un registre en bits est la borne supérieure du nombre de chiffres binaires d’une adresse.

Si le registre a n bits, la plus grande adresse vaudra 2 n − 1, et donc aucun ordinateur conforme à cette architecture ne pourra avoir une capacité mémoire supérieure à 2 n octets. Cette valeur de n intervient partout dans l’architecture et dans les programmes, si on l’a prévue trop petite au départ c’est irréparable.

32 octets, un peu plus de 4 milliards. À l’époque cette valeur semblait énorme, et les ingénieurs limitèrent la taille des adresses à 24 bits donnant accès à une mémoire de 16 millions d’octets. Lorsqu’à la fin des années 1970 la limite de 16 millions d’octets se révéla une contrainte insupportable, les systèmes d’exploitation développés par IBM soi-même pour l’architecture 360 utilisaient régulièrement les huit bits de poids fort des mots d’adresse pour toutes sortes d’usages, et la conversion à l’architecture XA imposa un remaniement complet de milliers de modules de logiciel, au prix d’années de travail et de millions de dollars 3.

#### 4.2.3 Noms et variables

En langage machine ou assembleur les noms sont des adresses, mais dans des langages de plus haut niveau les noms sont des lexèmes plus abstraits, en fait plus similaires à ce que nous appelons nom dans la grammaire des langages humains. De tels noms seront généralement appelés des identifiants. Mais pour être exécuté le programme en langage de haut niveau sera traduit en langage assembleur, puis en langage machine, et ses noms se résoudront en adresses qui permettront d’accéder physiquement à la donnée. En langage machine ou assembleur même, la donnée traitée n’est pas toujours désignée directement par une adresse simple.

R1 sera appelé registre de base et R2 registre index du tableau. Dans un langage évolué, en général, on a envie de conserver des résultats intermédiaires, ou des valeurs significatives d’un calcul ou d’un traitement de quelque sorte. Ces valeurs, de quelque type , occupent un ou plusieurs mots qui constituent un objet élémentaire. Bref, on souhaite pouvoir retrouver, à la demande, la valeur d’un objet du langage.

La solution retenue consiste souvent à associer à la valeur un nom de telle sorte que l’évocation ultérieure de ce nom procure un accès à la valeur. L’identifiant sera le nom de l’objet. L’objet le plus habituel des langages de programmation évolués est la variable.

Il est possible par le langage de modifier la valeur de la variable. L’opération de modification de la valeur d’une variable s’appelle l’affectation . Le nom n’est qu’un objet du langage, un objet symbolique destiné à disparaître au cours du processus de traduction de langage évolué en langage machine. Nous avons ainsi une chaîne de noms, depuis l’identifiant du langage évolué jusqu’à l’adresse mémoire physique en passant par d’éventuelles adresses indirectes ou indexées, qui tous mènent à la même donnée.

Revenons un instant sur l’affectation, qui est la propriété numéro 6 de ce que nous avons appelé variable. Si nous en étions restés aux trois propriétés précédentes, ce que nous appelons variable serait grosso modo la même chose que ce que les mathématiciens appellent variable.

#### 4.2.4 Protection de la mémoire

Dès que les systèmes se compliquèrent, et surtout dès qu’il y eut plusieurs programmes en mémoire, des accidents arrivèrent. Si l’on a en mémoire le petit programme en langage machine de la section 2.4.1, il est clair qu’une erreur de programmation très banale peut envoyer une donnée à une mauvaise adresse, et écraser une donnée ou une instruction qui ne devrait pas l’être, ce qui perturbera radicalement les traitements ultérieurs. Les premiers systèmes de multiprogrammation abordaient ce problème par le côté du matériel. L’architecture 360 découpe la mémoire en groupes de 2 048 octets qui constituent l’unité non partageable d’allocation à un processus donné. Lors de tout accès mémoire, le processeur vérifie que la clé de la zone concernée est bien égale à la clé du processus courant, sinon le processeur provoque une erreur fatale et le processus concerné est interrompu.

### 4.3 Partage de mémoire en multiprogrammation

Les sections 3.2 et 3.8 ont décrit les principes de la multiprogrammation et ses conséquences dans le domaine de la mémoire ; il faut maintenant préciser comment se fait l’attribution de la mémoire à chacun des
programmes concomitants pseudo-simultanés.

#### 4.3.1 Exemple : l’OS/360

Les premiers systèmes d’exploitation destinés à l’architecture IBM

– Avec l’OS/MFT , la mémoire était découpée en partitions fixes au démarrage du système. Les travaux étaient répartis en classes et chaque classe était éligible pour une ou plusieurs partitions, principalement en fonction de la taille mémoire nécessaire à l’exécution des travaux de la classe. Tout ceci entraîne un risque de mauvaise utilisation de la mémoire. – La version plus perfectionnée, OS/MVT , abolit le découpage rigide de la mémoire.

Chaque programme annonce la taille de la région de mémoire nécessaire à son exécution et dès qu’elle est disponible elle lui est attribuée, toujours une fois pour toutes et jusqu’à la fin de son exécution. Lorsqu’un programme se termine il libère une région de mémoire qui laisse un trou à une adresse arbitraire au milieu de la mémoire. Il peut ainsi se créer un effet « fromage de gruyère », où plusieurs trous de mémoire atteignent une taille cumulée suffisante pour les travaux en attente, mais comme chacun est trop petit, la file d’attente est bloquée. Ce défaut de la gestion de mémoire de l’OS/360 sera corrigé par l’introduction de la mémoire virtuelle que nous étudierons à la section suivante, mais auparavant il nous faut compléter ce qui vient d’être dit en expliquant la translation des programmes, sans quoi nous ne pourrions avoir plusieurs programmes en mémoire simultanément.

#### 4.3.2 Translation des programmes

Oui il s’agit bien de translation, puisqu’aujourd’hui il faut préciser en employant ce mot que l’on n’est pas en train de faire une erreur de traduction de l’anglais translation qui signifie traduction en français 4. Nous avons donc parlé plus haut de la traduction des programmes, ici c’est de leur translation qu’il s’agit. Lors de nos essais en langage machine nos programmes comportaient des adresses qui désignaient sans ambiguïté un mot de mémoire bien déterminé où devait se trouver une instruction ou une donnée indispensable au bon déroulement des opérations. Si maintenant on nous dit que le programme va être chargé à une adresse qui ne sera plus l’adresse 0, mais une position quelconque et imprévue en plein milieu de la mémoire, tout le texte va être décalé, et chaque objet désigné par le programme aura une adresse qui ne sera plus l’adresse absolue à partir de 0 que nous avions écrite, mais cette adresse additionnée de l’adresse de chargement du programme.

Lorsqu’on programme en assembleur, on écrit rarement des adresses absolues. Les assembleurs allègent la tâche du programmeur en lui permettant de désigner la position d’un octet dans le texte du programme par un nom symbolique, que l’assembleur se chargera de traduire en adresse. FIN, qui désignait l’instruction située à l’adresse absolue 5. Un tel symbole peut de la même façon désigner le premier octet d’une zone de mémoire qui contient une donnée.

Nous voulons maintenant que ce symbole ne désigne plus l’adresse absolue 5, mais une adresse relative par rapport au début du programme, lequel ne serait plus nécessairement à l’adresse 0. Au moment de l’exécution, il recevra l’adresse du point de chargement du programme en mémoire, et ainsi nos adresses exprimées sous la forme base + déplacement seront juste. Enfin, n’oublions pas que lorsque que nous disons programmeur il faut la plupart du temps entendre compilateur, parce que c’est lui qui va traduire en assembleur les programmes écrits en langage évolué par des humains qui n’auront pas eu à se soucier de ces contingences techniques pourtant passionnantes. Ce perfectionnement de l’assembleur n’est pas très spectaculaire, mais sans lui la multiprogrammation serait plus complexe à réaliser.

La translation des programmes est parfois aussi nommée réimplantation.

### 4.4 Mémoire virtuelle

#### 4.4.1 Insuffisance de la mémoire statique

Nous avons vu ci-dessus que l’allocation à un programme de la zone mémoire dont il avait besoin, de façon fixe une fois pour toutes au début de son exécution, avait un inconvénient qui était la fragmentation de la mémoire au fur et à mesure du lancement à des instants aléatoires de programmes de tailles hétérogènes. Certains systèmes des années 1960 palliaient cette inefficacité en réorganisant périodiquement la mémoire pour « tasser » les zones utilisées les unes contre les autres. La voici.

#### 4.4.2 Organisation générale

L’organisation de mémoire virtuelle que nous allons décrire est inspirée de celle des systèmes IBM 370 et suivants, mais les autres réalisations sont assez comparables. La mémoire virtuelle est celle que les programmes utilisent, mais elle n’existe pas vraiment. La mémoire virtuelle répond à deux préoccupations. La première vise à éviter le gaspillage de fragments de mémoire en permettant à la mémoire linéaire vue par le programme d’être physiquement constituée de fragments disjoints, ce qui supprime l’inconvénient de la fragmentation de la mémoire, au prix d’un mécanisme que nous allons étudier pour rétablir la fiction de la linéarité 5.

Si nous observons, cycle par cycle, le déroulement d’un programme dont la taille mémoire est par exemple de un million d’octets, nous constaterons que pendant une tranche de temps donnée, brève par rapport au temps d’exécution total, il ne fait référence qu’à un petit nombre d’adresses proches les unes des autres. Ceci veut dire qu’à chaque instant le programme a besoin de beaucoup moins de mémoire qu’il ne lui en faut au total, et que le contenu de la mémoire inutile à un instant donné pourrait être stocké provisoirement dans un endroit moins coûteux, par exemple sur disque. Lorsque le système d’exploitation lance l’exécution d’un programme, il lui alloue un espace de mémoire virtuelle. Comme cette mémoire est virtuelle, donc gratuite ou presque, l’espace alloué est aussi vaste que l’on veut, dans les limites de l’adressage possible avec la taille de mot disponible.

Cet espace de mémoire virtuelle est découpé en pages de taille fixe et décrit par une table des pages. Les emplacements en mémoire virtuelle sont désignés par des adresses virtuelles, qui ressemblent comme des sœurs aux adresses réelles que nous avons vues jusqu’alors.

#### 4.4.3 Pagination

Les programmes ne connaissent que la mémoire virtuelle, et des adresses virtuelles. Chaque fois qu’une instruction fait référence à une donnée, cette référence est une adresse virtuelle. Avec les autres fonctions de gestion de la mémoire virtuelle que nous allons décrire il constitue la MMU . Les 5 bits de poids le plus fort sont un numéro de segment, index dans la table de segments du processus, qui permet de trouver la table des pages du segment.

Les 7 bits de poids intermédiaire sont un numéro de page, index dans la table des pages qui permet de trouver la page concernée. La partition des 12 bits de poids fort en numéro de segment et numéro de page n’est qu’un artifice pour hiérarchiser la table des pages, ils peuvent être considérés globalement comme le numéro de page. Le DAT consulte la table des pages pour y chercher l’entrée correspondant au numéro de page virtuelle voulu. – Dans le cas 1 de la liste ci-dessus la page existe et possède une incarnation en mémoire réelle.

Le circuit de traduction d’adresse trouve dans la table des pages l’adresse du cadre de page qui contient la page virtuelle. Cette adresse est additionnée au déplacement dans la page, ce qui donne l’adresse réelle à laquelle le programme doit accéder. Cette situation peut se produire au lancement d’un programme, ou après l’allocation d’une zone de mémoire dynamique vierge, par exemple. Il va falloir obtenir du système une page réelle « neuve » et placer son adresse dans la table des pages, ainsi nous serons ramenés au problème précédent, après la consommation d’un nombre non négligeable de cycles de processeur.

La MMU génère une exception dite de défaut de page , et le gestionnaire de défaut de page va être chargé d’obtenir une page réelle neuve. Le système gère une table des cadres de pages en mémoire réelle, cette table garde pour chaque cadre de page un certain nombre d’informations, et notamment s’il est libre. Si le parcours de la table des cadres de pages révèle un cadre libre il est alloué à la page vierge, son adresse est placée dans la table des pages et le programme peut poursuivre son exécution. S’il n’y a aucun cadre de page libre, il faut en libérer un.

L’estampille de plus faible valeur désigne le cadre de la page la moins récemment utilisée. La table des pages est mise à jour et le programme continue comme dans le cas précédent. Une fois le cadre de page obtenu, le contenu de la page virtuelle qui était en mémoire auxiliaire est recopié dans ce cadre, la table des pages est mise à jour et l’exécution du programme peut continuer.


#### 4.4.4 Espaces adresse

Les premiers systèmes à mémoire virtuelle allouaient pour l’ensemble du système un espace unique de mémoire virtuelle dont la taille était fixée par la valeur maximum d’une adresse. Cet espace virtuel était partagé entre les programmes selon les mêmes principes que dans les anciens systèmes sans mémoire virtuelle, tels que nous les avons exposés au début de ce chapitre. Ceci présentait l’avantage que l’adjonction de la mémoire virtuelle modifiait assez peu le système d’exploitation.

IBM le système MVS en 1974, chez Digital

Equipment VMS en 1977, chez Data General AOS/VS... Une mémoire virtuelle à espaces adresse multiples est illustrée par la figure 4.2. Il est de ce fait impossible à un programme de faire référence à une adresse qui appartient à une page de mémoire virtuelle d’un autre programme. La mémoire virtuelle à espaces adresse multiples améliore la sécurité des données. Maintenant que chaque programme a son espace privé, rien n’interdit de le charger toujours à la même adresse, et d’avoir une carte de la mémoire identique d’une exécution à l’autre.

« Ce procédé permet de limiter les effets des attaques de type dépassement de zone mémoire par exemple 6. » Cette technique se nomme « distribution aléatoire de l’espace d’adressage » .

Simultanéité dans le même espace adresse . Que chaque programme s’exécute dans son espace privé inaccessible aux autres parce que tout simplement aucun nom n’est disponible pour en désigner les emplacements, très bien, mais il y a quand même des choses à partager. Notamment le système d’exploitation, qui après tout est lui aussi un programme, avec des sous-programmes qui doivent pouvoir être appelés par les programmes ordinaires. Le système d’exploitation comporte aussi de nombreuses tables qui contiennent des informations relatives à l’état de l’ordinateur et du système, comme par exemple le fuseau horaire de référence, des moyens d’accès aux données sur disque ou au réseau, etc. Comment y accéder ?.


31 octets qui constituent la première moitié de cet espace sont dévolus au programme et à ses données.

#### 4.4.5 Registres associatifs (Translation Lookaside Buffer, TLB)

En fait, un système de mémoire tel que celui décrit jusqu’ici serait d’une lenteur exécrable. Il serait donc judicieux de garder sous la main, c’est-à-dire dans quelques registres implantés sur le circuit du processeur, et de ce fait d’un accès beaucoup plus rapide que la mémoire, le résultat des traductions les plus récentes, soit une table de correspondance numéro de page virtuelle – numéro de cadre de page pour ces quelques pages utilisées. Si la consultation du TLB réussit, le DAT beaucoup plus lent est arrêté. Si elle échoue le DAT poursuit la traduction jusqu’à son terme et en place le résultat dans le TLB pour la prochaine fois.

Où le DAT va-t-il placer le résultat de la traduction qu’il vient d’effectuer ? À la place d’une autre entrée. Généralement, les systèmes à espaces adresse multiples évoqués à la section précédent 4.4. 4 mettent le TLB en échec, et chaque commutation de contexte, qui entraîne un changement d’espace adresse, nécessite la remise à zéro du TLB. Le plus surprenant est que le TLB reste néanmoins efficace.

Signalons que certains processeurs, tel le MIPS R4000, utilisent un TLB étiqueté , c’est-à-dire que chaque entrée de TLB comporte l’identifiant de l’espace adresse auquel elle appartient, ce qui évite la pénalité que nous venons d’évoquer. Ce dispositif est si efficace et résout une si grande proportion des traductions d’adresses que certains concepteurs se sont dit que le DAT servait très rarement et qu’il suffisait de le réaliser en logiciel, ce qui est beaucoup plus lent mais plus simple et moins coûteux, et libère des nanomètres–carrés précieux sur le circuit. Sur ces processeurs le seul matériel spécialisé pour la mémoire virtuelle est le TLB et sa logique de consultation. C’est notamment sur ce principe que reposent les dispositifs de cache, qui constituent la hiérarchie de mémoire, et que nous verrons bientôt.

#### 4.4.6 Tables de pages inverses

64 octets, il nous faudrait des tables de pages avec 2

Une solution, retenue sur les premières versions de l’Alpha et de l’Itanium, est de réduire arbitrairement mais radicalement la taille mémoire adressable en limitant le nombre de lignes du bus d’adresses, mais ce n’est guère satisfaisant. L’avantage de la table des cadres de pages, c’est qu’elle est beaucoup plus petite, et par définition dans un rapport de taille avec la mémoire réelle de l’ordre de un pour mille. Des méthodes telles que les tables associatives sont de nature à diminuer la pénalité qui en résulte.

#### 4.4.7 Mémoire virtuelle segmentée

Les systèmes de mémoire virtuelle que nous avons décrits jusqu’ici utilisent des espaces adresse uniformes, c’est-à-dire découpés en pages de tailles identiques, elles-mêmes regoupées par simple raison de commodité de manipulation en segments de tailles identiques. D’autres architectures de mémoire virtuelle ont été imaginées, avec des segments de tailles variables, adaptés à des régions particulières du programme, par exemple un segment pour le code du programme, un segment pour les données initialisées au lancement du programme, un segment pour les données non initialisées, un segment de données non modifiables, un segment pour les structures de données créées par le système pour ce processus, etc. De tels systèmes conservent en général une taille de page fixe, mais le nombre de pages d’un segment est arbitraire. L’archétype de ces systèmes à mémoire virtuelle segmentée est Multics.

#### 4.4.8 Petite chronologie de la mémoire virtuelle

La première réalisation de mémoire virtuelle avec pagination date de 1961 et figure à l’actif de l’Université de Manchester, qui développait en collaboration avec le constructeur le système de l’ordinateur ATLAS de Ferranti.

– système écrit en langage évolué .
1961 vit les débuts du projet MAC dirigé par Fernando Corbató au MIT, et dans ce cadre la réalisation du système CTSS , ancêtre de Multics, sur ordinateur IBM 709 puis 7094. CTSS comportait un système de swap, qui recopiait sur mémoire auxiliaire les programmes mis en attente par le système au profit de programmes réactivés et rechargés depuis la mémoire auxiliaire vers la mémoire vive. Ce système de swap, qui peut être considéré comme la mémoire virtuelle du pauvre, se retrouve sur le PDP-1 de Digital mis au point en 1962 pour BBN , un nom que nous retouverons au chapitre consacré aux réseaux, puis sur beaucoup de machines de la gamme PDP.

### 4.5 Hiérarchie de mémoire

#### 4.5.1 Position du problème

Dès que cette table devient longue il faut trouver une solution plus subtile. C’est l’idée de la hiérarchie de mémoires, une mémoire petite et rapide en avant–plan d’une mémoire vaste, plus lente mais complète. Il nous faudra disposer d’un algorithme de remplacement des informations vieillies par de nouvelles vedettes. Remarquons que cette idée de working set se marie bien avec la constatation notée plus haut de la localité des traitements.

### 4.6 La technique du cache

Le mot cache, curieux retour au français d’un emprunt anglais, suggère ici l’idée de cacher dans un coin pour l’avoir sous la main une chose que l’on ne veut pas avoir à aller chercher à la cave ou au grenier, pour gagner du temps.

#### 4.6.1 Cache mémoire

Les processeurs modernes utilisent la technique de cache pour accélérer l'accès à la mémoire en mettant en place plusieurs niveaux de mémoire de différentes tailles et vitesses d'accès. Le niveau le plus rapide est le cache L1, qui est directement intégré au processeur et a un temps d'accès très rapide. Le niveau suivant est le cache L2, qui est moins rapide mais plus grand que le L1. Le processeur peut également avoir un cache L3 externe qui est encore plus lent mais plus grand. L'accès à la mémoire principale se fait à un débit moins élevé que les caches. La taille des caches a évolué de manière moins spectaculaire que les performances des processeurs en raison de la localité des traitements, ce qui signifie qu'augmenter trop la taille des caches n'apporte que peu de gains de performance.

#### 4.6.2 Hiérarchie de mémoire : données numériques

Jeffrey Dean, un architecte système chez Google, a présenté un tableau des temps d'accès comparés aux différents niveaux de mémoire lors d'une conférence sur les systèmes distribués à grande échelle et le middleware en 2009. Ce tableau a été mis à jour en 2018. Depuis au moins 2010, la vitesse des processeurs n'a plus augmenté en raison d'un "accord d'armistice" entre les industriels, probablement en raison de problèmes de dissipation thermique liés à la concurrence dans ce domaine.


#### 4.6.3 Mise en œuvre du cache

Les caches sont utilisés pour accélérer les traitements en chargeant les zones de mémoire fréquemment utilisées dans le cache. L'algorithme de gestion du cache consiste à charger la zone de mémoire demandée par le processeur à la place de la zone la moins récemment utilisée dans le cache, en supposant que cette zone sera souvent demandée dans les instants qui suivent. La partie complexe de l'algorithme consiste à maintenir la cohérence entre les caches et la mémoire principale en réécrivant les zones modifiées dans le cache. La technique du cache permet d'obtenir des améliorations de performance spectaculaires, mais aucun modèle général de son fonctionnement n'a été proposé à ce jour.

### 4.7 Langage et mémoire

Le système d'exploitation alloue l'espace de mémoire nécessaire à l'exécution d'un programme. La façon dont cet espace est présenté au programme dépend du langage de programmation utilisé et du traducteur. Cependant, il peut être utile de se rappeler les informations précédemment présentées sur la notion de sous-programme, qui permet de découper un grand programme en parties plus gérables.

#### 4.7.1 Langages à mémoire statique

Les langages de programmation à gestion de mémoire statique, tels que Fortran, allouent la mémoire une seule fois au lancement du programme. Les variables et le texte du programme en langage machine sont à des emplacements fixes et ne peuvent pas être étendues. Le compilateur crée une image binaire du programme traduit et de ses zones de données, qui est assemblée avec les différents sous-programmes et les sous-programmes de bibliothèque pour en faire un fichier binaire exécutable. Cette technique a l'inconvénient de ne pas permettre l'extension de la mémoire pendant l'exécution, d'empêcher la récursion et la création d'objets dynamiques à l'exécution, mais elle a l'avantage de rendre les programmes écrits dans ces langages rapides et à l'abri de l'échec de mémoire en cours d'exécution.

#### 4.7.2 Vecteur d’état d’un programme

Un sous-programme s'exécute dans un contexte qui comprend l'adresse de la liste des arguments fournis par le programme appelant, l'adresse de retour vers laquelle il doit effectuer un branchement une fois terminé, l'adresse où déposer le résultat de son exécution, ainsi que les variables internes (locales) au sous-programme. Ces éléments de contexte forment ce que l'on appelle le vecteur d'état du programme, qui est une collection de mots.

#### 4.7.3 Langages à mémoire dynamique

Il existe deux grandes catégories de méthodes pour allouer de la mémoire supplémentaire dynamiquement à un programme pendant son exécution: sur la pile et dans le tas. La plupart des langages modernes utilisent les deux. La pile est généralement utilisée pour les données qui tiennent dans un mot ou peu de mots, qui doivent être traitées rapidement et qui n'ont pas besoin de survie au-delà de la fin de l'exécution du sous-programme en cours. Le tas est utilisé pour les données de taille quelconque et éventuellement variable, ainsi que pour les données qui doivent survivre au sous-programme en cours. Cependant, il est important de noter que l'allocation de mémoire se fait toujours à partir de l'espace d'adresses du processus, et que si cet espace est plein, les tentatives d'allocation déclencheront des erreurs.

##### 4.7.3.1 Allocation de mémoire sur la pile

Dans un langage à gestion de mémoire dynamique, le système, pour chaque appel de sous-programme, crée un vecteur d’état , et le détruit lorsque la procédure se termine. En général, le résultat renvoyé par un sous-programme qui se termine aura été placé dans la pile, à un endroit convenu du vecteur d’état du programme appelant, c’est-àdire « en dessous » du vecteur courant.

Différentes activations d’un sous-programme peuvent coexister, avec chacune son vecteur d’état distinct, ce qui permet notamment à un sous-programme d’être récursif, c’est-à-dire de s’appeler lui-même. Les valeurs, associées aux noms locaux, contenues dans le vecteur d’état stocké sur la pile, sont détruites à la fin de l’activation, ce qui élimine une cause d’erreur de programmation. Le vecteur d’état d’un sous-programme appelé ne peut plus exister après la terminaison de l’appelant.

##### 4.7.3.2 Allocation de mémoire sur le tas

Les systèmes d'exploitation ont souvent une fonction qui permet aux programmes de demander de l'espace mémoire de n'importe quelle taille. Cette mémoire est généralement prise dans une zone appelée "tas" de l'espace d'adressage du processus et est gérée par des fonctions comme "malloc" ou "brk". Les langages de haut niveau gèrent souvent cette allocation de mémoire de manière transparente pour le programmeur, tandis que les langages de bas niveau comme C et C++ requièrent que l'allocation soit explicitement gérée par des fonctions comme "malloc". Si l'allocation de mémoire est explicitement gérée, il est également nécessaire de libérer explicitement cette mémoire lorsqu'elle n'est plus utilisée en utilisant une fonction comme "free". Cependant, dans un programme complexe, il peut être difficile de savoir quand il est approprié de libérer une zone de mémoire car plusieurs sous-programmes peuvent faire référence à la même zone de mémoire allouée à différents moments. Des algorithmes heuristiques ont été développés pour résoudre ce problème difficile de gestion de la mémoire.

##### 4.7.3.3 Gestion de la mémoire dynamique

Il existe deux types de langages de programmation modernes: les langages à gestion de mémoire explicite, tels que C, C++, Pascal, où le programmeur doit gérer l'allocation et la libération de la mémoire obtenue dynamiquement, et les langages à gestion de mémoire automatique, tels que Lisp, Smalltalk, Scheme, Caml ou Java, où la mémoire est allouée implicitement lorsqu'un objet est créé. Les langages de la seconde catégorie utilisent un algorithme heuristique appelé "ramasse-miettes" ou "garbage collector" (GC) pour libérer la mémoire allouée et inutilisée. Ada est un langage qui était censé avoir un GC, mais qui a trouvé son public dans la communauté du temps réel et dont les utilisateurs ont été réticents à l'idée de déclencher le GC de manière asynchrone. Les versions récentes d'Ada autorisent l'utilisation d'un GC qui peut être désactivé, et autorisent également la publication de compilateurs sans GC. Les langages à gestion de mémoire explicite sont adaptés pour écrire des systèmes d'exploitation, des pilotes de périphérique et des programmes fortement liés au matériel, mais peuvent être moins adaptés pour écrire des programmes de haut niveau. Les langages à GC sont plus abstraits et permettent une expression et une simplicité accrues, mais sont moins adaptés pour écrire des programmes nécessitant une réactivité en temps réel et une utilisation efficace de la mémoire.

#### 4.7.4 Mémoire d’un programme en cours d’exécution

Les compilateurs modernes créent souvent des programmes exécutables qui sont structurés en plusieurs sections en fonction de l'utilisation des données qui y sont placées. Ces sections incluent une section de code pour les instructions du programme, qui est protégée contre la modification afin d'éviter les failles de sécurité, une section de données statiques pour les données de taille fixe et non initialisées, une section de la pile qui contient la pile et est organisée et gérée de manière à suivre les principes décrits précédemment, et une section du tas qui contient le tas. Un programme peut avoir plusieurs autres sections, par exemple une section par sous-programme.

## 5 Persistance

### 5.1 Mémoire auxiliaire

La mémoire centrale d'un ordinateur utilise actuellement des semi-conducteurs pour stocker des données, mais cela n'a pas toujours été le cas. Avant les années 1970, la technologie de mémoire dominante utilisait des tores de ferrite magnétisés et un champ magnétique pour stocker des données. Cependant, ce type de mémoire était petite et sujette aux perturbations, ce qui rendait difficile la conservation des données lorsque l'alimentation électrique était interrompue ou lorsque le processus se terminait. Pour stocker de grandes quantités de données de manière permanente, il est nécessaire d'utiliser d'autres dispositifs de mémoire appelés mémoire auxiliaire, comme les disques magnétiques ou les SSD. Les disques magnétiques sont en train d'être remplacés par les SSD, qui sont plus rapides, mais les disques magnétiques ont encore quelques avantages par rapport à eux.

### 5.2 Système de fichiers

Les fichiers dans les systèmes Unix ou Linux sont une série de caractères qui peuvent être lus par un programme comme un flux. Ils sont stockés sur le disque dur en plusieurs secteurs de 512 caractères chacun. Un système de répertoire est utilisé pour associer un nom à un emplacement sur le disque pour chaque fichier. Les secteurs peuvent être alloués en blocs de plusieurs secteurs pour éviter un morcellement excessif.

### 5.3 Systèmes de fichiers en réseau : NFS, SANs et NAS

Pour un centre de calcul d’une certaine importance, il y a trois modèles
de solutions possibles pour stocker les bases de données :
1. disques connectés directement aux serveurs par des attachements
IDE, SATA, SCSI (Small Computer Systems Interface), SAS, etc.
(ou NVMe (Non-Volatile Memory express) pour les disques SSD) ;
2. disques organisés selon la technologie SAN (Storage Area Network) ;
3. disques organisés selon la technologie NAS (Network Attached
Storage).
Nous allons examiner successivement ces trois solutions. Pour en
savoir plus sur SCSI, SAN et NAS on consultera avec profit le livre de
W. Curtis Preston.

## 6 Réseaux

De surcroît, des systèmes sont apparus qui mettent à profit le réseau pour regrouper plusieurs ordinateurs et les considérer comme un seul multi-ordinateur, ou système distribué. Bref, s’il est de bonne méthode de distinguer l’architecture des ordinateurs, qui traite de l’organisation des éléments matériels des machines, l’architecture des systèmes d’exploitation, qui envisage la couche logiciel d’interface entre le matériel et les programmes de l’utilisateur, et l’architecture des réseaux, consacrée aux moyens de communication entre ordinateurs distants, il est clair qu’aucun de ces domaines ne pourra être traité sérieusement sans qu’il soit fait appel aux deux autres. Le problème de base à résoudre pour concevoir et réaliser un réseau d’ordinateurs consiste à établir un échange de données entre deux ordinateurs distants. La position de ce problème remonte au moins à Aristote, qui a envisagé la communication d’information entre deux personnes en termes de message et de code.

Incidemment, ce modèle est beaucoup mieux adapté à la communication entre ordinateurs qu’à la communication entre êtres humains, qui est extraordinairement compliquée par tout un contexte et par des éléments non verbaux qui rendent ce modèle, dans ce cas, assez inapproprié. Bref, pour les ordinateurs le modèle aristotélicien convient bien. L’invention du téléphone a conduit à le formaliser sous le nom de « communication sur un canal bruité ». En effet il y a du bruit, c’est-à-dire qu’aucun canal de communication n’est parfait, certains éléments du message sont altérés ou perdus.

Il va sans dire que pour transmettre de l’information codée sous forme numérique, les altérations des messages sont beaucoup moins tolérables. Nous allons dire quelques mots très sommaires de la théorie de l’information. Le transfert d’information dans un système de communication s’effectue par messages. Un message est une suite de signes tirés d’un alphabet.

## 7 Protection et sécurité

La protection consiste à empêcher qu’un utilisateur puisse altérer un fichier qui ne lui appartient pas et dont le propriétaire ne lui en a pas donné l’autorisation, ou encore à empêcher qu’un processus en cours d’exécution ne modifie une zone mémoire attribuée à un autre processus sans l’autorisation de celui-ci, par exemple.

Un objet est, sous réserve d’inventaire, soit un fichier, soit un processus, soit une structure de données éphémère créée en mémoire par un processus, mais nous avons vu à la section 5.4 que pour Multics tous ces objets sont en fin de compte des segments ou sont contenus dans des segments de mémoire virtuelle.

– droit de blocage, par exemple pour un processus en cours d’exécution ou éligible pour l’exécution. – Avant toute tentative d’accès à un objet par un utilisateur, l’identité de cet utilisateur doit être authentifiée. – Pour qu’un utilisateur ait le droit d’exécuter une action sur un objet, et dans un système informatique cette action est perpétrée par l’entremise d’un processus, il faut en outre que le processus en question possède le pouvoir voulu. Le pouvoir est un attribut d’un processus, il peut prendre des valeurs qui confèrent à ce processus des privilèges plus ou moins étendus.

– La valeur du pouvoir d’un processus peut changer au cours de son exécution. Ainsi un processus qui se déroule dans un mode utilisateur peut faire une demande d’entrée-sortie, ce qui nécessite le mode superviseur. Ceci sera résolu, sous Unix par exemple, par le mécanisme de l’appel système, qui transfère le contrôle, pour le compte du processus utilisateur, à une procédure du noyau qui va travailler en mode superviseur. – Nous définirons la notion de domaine de protection dans lequel s’exécute un processus comme l’ensemble des objets auxquels ce processus a accès et des opérations qu’il a le droit d’effectuer sur ces objets.

Lorsqu’un processus change de valeur de pouvoir, il change par là même de domaine de protection. Il faut protéger les données et les processus d’un utilisateur contre les processus des autres utilisateurs, protéger le fonctionnement du système contre les processus des utilisateurs et vice-versa, enfin protéger l’un de l’autre les processus d’un même utilisateur. Cette réflexion de simple bon sens suffit à refuser le qualificatif « sûr » à tel système d’exploitation qui comporte un système perfectionné de listes d’accès réalisé... en mode utilisateur, et pour lequel de surcroît l’identification des utilisateurs est facultative.

## 8 De Multics à Unix et au logiciel libre

Comme nous l’avons déjà mentionné à la section 3.10.1, Multics est né en 1964 au MIT (Massachusetts Institute of Technology) dans le cadre d’un projet de recherche nommé MAC, sous la direction de Fernando Corbató.

La même équipe avait déjà créé le système CTSS. Multics était destiné aux ordinateurs General Electric de la famille GE 635, pour lesquels le constructeur fournissait de son côté un système d’exploitation plus conventionnel. L’objectif du projet était la réalisation d’un grand système informatique capable de fournir des services interactifs en temps partagé à un millier d’utilisateurs simultanés. Le système d’exploitation était écrit en langage évolué , voie ouverte par les systèmes Burroughs écrits en Algol, mais encore peu fréquentée.

L’institut de statistique qui employait à l’époque l’auteur de ces lignes en avait acquis un, fruit de la fusion CII-Honeywell-Bull, et ses experts en informatique démographique avaient essayé d’imaginer les moyens de traiter avec cet engin les recensements de la population, mais ils avaient fini par regarder ce drôle de système un peu de l’œil de la poule qui a couvé un œuf de cane. Si changer de langage ou de système ne rend pas plus intelligent, il y a des systèmes et des langages qui incitent à la réflexion, et d’autres moins. Multics, sous cet angle comme sous certains autres, était un précurseur d’Unix, système qui considère ses utilisateurs comme des personnes intelligentes, mais aussi suffisamment intéressées par le système lui-même pour lui consacrer un temps non négligeable dont les employeurs ne comprennent pas toujours la fécondité. C’est ainsi que des industriels ont inventé pour Unix une interface utilisateur nommée CDE dont le principe est de plaquer sur le système une sorte de super-Windows dont le paramétrage, réservé à des administrateurs, est ensuite propagé à la masse des utilisateurs.

## 9 Au-delà du modèle de von Neumann

La recherche de performances a inspiré des tentatives pour contourner la loi d’airain de l’architecture de von Neumann : une seule instruction à la fois. Ces tentatives se classent en deux catégories : radicales et pragmatiques. Le présent chapitre en fait un bref tour d’horizon. Les architectures qui remettent fortement en cause le principe de von Neumann n’existent aujourd’hui que dans quelques laboratoires (même si elles sont sans doute promises à un avenir meilleur et si certaines d’entre elles ont un passé respectable), et celles qui sont des extensions pratiques de ce principe ne remettent pas en cause la sémantique du modèle de calcul, même si elles en compliquent considérablement la mise en œuvre technique pour le bénéfice d’une amélioration non moins considérable des performances.

Les tentatives radicales visent à créer de nouveaux modèles de calcul en imaginant des ordinateurs capables d’exécuter un grand nombre d’instructions simultanément. Ces modèles révolutionnaires se classent selon diverses catégories :

* SIMD (Single Instruction Multiple Data)
* Architectures cellulaires et systoliques
* MIMD (Multiple Instructions Multiple Data)

Ce rapide tour d’horizon des architectures non von Neumann illustre leur échec général dû à la difficulté de leur programmation. À leur apparition elles ont souvent énormément séduit, mais la nécessité de recourir à des méthodes et à des langages de programmation peu répandus et maîtrisés par peu d’ingénieurs a vite découragé industriels et clients. D’où le succès, en revanche, de contournements du principe de von Neumann par des voies moins radicales, qui recherchaient le même résultat tout en conservant la sémantique classique et que nous allons examiner maintenant.

La réforme la plus importante apportée à l'architecture de von Neumann pour améliorer les performances tout en conservant un comportement extérieur apparent identique est la substitution d'une hiérarchie de mémoires de temps d'accès décroissants à la mémoire centrale unique. L'exécution des instructions successives dans cette architecture se déroule en plusieurs étapes : lecture de l'instruction suivante en mémoire grâce au compteur de programme (PC), décodage de l'instruction, exécution de l'opération, et mise à jour du PC. L'utilisation de pipelines et de processeurs super-scalaires permet d'améliorer les performances en parallélisant ces étapes.

## 10 Machines virtuelles et micro-noyaux

Les chapitres qui précèdent ont montré à plusieurs reprises que la conception d’une architecture informatique consistait le plus souvent en grande partie à organiser des niveaux d’abstraction différents afin de donner une intelligibilité supérieure à un mécanisme, ou au contraire pour le dissimuler aux yeux de l’utilisateur. Nous pouvons subsumer certains de ces artefacts sous la notion de machine virtuelle. L’interpréteur se présente à son utilisateur comme un ordinateur dont le langage machine serait le langage qu’en fait il traduit à la volée. Il est une machine virtuelle du langage considéré.

Basic, Scheme, Python, le shell Unix sont des langages interprétés, par opposition aux langages compilés comme C, Scheme , Ada, pour lesquels il faut d’abord écrire le texte du programme jusqu’au bout, puis le soumettre à un traducteur appelé compilateur qui le traduit en langage machine. On peut dire que le système d’exploitation exhibe une machine virtuelle qui représente de façon stylisée et elliptique la machine réelle, dont les aspects les plus sordides sont ainsi dissimulés. Des émulateurs d’Unix sur VAX sous VMS ont existé, ainsi que des émulateurs de VMS sous Unix. Apple et d’autres sociétés ont produit des logiciels qui émulent un PC sous Windows sur un Macintosh.

Tous les accès de Windows au matériel sont interceptés de telle sorte que le système hébergé ne puisse pas faire la distinction entre un périphérique réel et l’abstraction présentée par la machine virtuelle. L’émulateur peut d’ailleurs accueillir simultanément plusieurs machines virtuelles tournant sous des systèmes différents.

## 11 Micro-informatique

La micro-informatique a connu un grand succès depuis les années 1970 grâce aux efforts pour rendre les ordinateurs techniquement et économiquement accessibles aux particuliers. Aujourd'hui, la plupart des ordinateurs sont destinés à un usage individuel et sont appelés micro-ordinateurs. Depuis 2007, avec l'arrivée de l'iPhone et d'Android, cela est également vrai pour les téléphones. La révolution de la micro-informatique a principalement porté sur l'interface homme-machine, avec l'apparition d'interfaces graphiques et de périphériques adaptés à un usage individuel. Elle a également eu un impact économique et social important, rendant l'ordinateur accessible à toutes les couches de la société. La révolution a commencé avec la création de la société Digital Equipment en 1960 et la mise en vente du premier PDP-1, un ordinateur individuel relativement abordable pour l'époque. Les gammes PDP suivantes ont permis de nombreuses innovations, notamment dans les systèmes de contrôle informatique de processus industriels et le développement de Unix.

En 1971, Intel a créé le premier microprocesseur, le 4004, qui a permis la naissance de la micro-informatique en regroupant de nombreux circuits électroniques sur une seule puce, fabriquée de manière automatisée. En 1972, les Français André Truong Trong Thi et François Gernelle ont créé le micro-ordinateur Micral avec l'Intel 8008 et en 1975, MITS (Model Instrumentation Telemetry Systems) a lancé l'Altair 8800, un micro-ordinateur basé sur l'Intel 8080 et vendu en kit. Steve Wozniak et Steve Jobs ont créé Apple en 1976 et ont lancé la carte Apple I et l'Apple II l'année suivante, qui a introduit une mémoire vidéo directement commandée par le processeur et reliée à un moniteur. D'autres constructeurs ont également lancé des micros, tels que Commodore, Oric, Atari et Acorn, et Tandy Radio Shack a utilisé le Zilog Z80 pour son TRS-80. En parallèle, le système d'exploitation CP/M (Control Program/Microcomputers) a été développé en 1973 et peut être utilisé sur plusieurs types de micros.

## 12 Le micrologiciel

Le micrologiciel (ou firmware) est un composant essentiel du fonctionnement d'un ordinateur, qui comprend le BIOS (Basic Input/Output System) et, depuis 2008, l'Intel Management Engine et sa composante Intel Active Management Technology (AMT). Ces dispositifs supervisent le fonctionnement de l'ordinateur et gèrent notamment la sécurité. Le BIOS est un programme enregistré dans une mémoire non-volatile qui s'exécute au démarrage de l'ordinateur et charge le noyau du système d'exploitation en mémoire. Le bootloader est un autre programme chargé par le BIOS qui permet de sélectionner le système d'exploitation à démarrer. Le micrologiciel a également la responsabilité de configurer le matériel de l'ordinateur et de fournir des fonctions de base pour communiquer avec lui.

L'UEFI (Unified Extensible Firmware Interface) est un système de démarrage de l'ordinateur qui remplace le BIOS traditionnel et vise à éliminer certaines limitations du démarrage du système d'exploitation. L'UEFI est accompagnée du système de partitionnement GPT (GUID Partition Table), capable de gérer des disques de grande capacité. Secure Boot est un autre dispositif associé à l'UEFI qui vise à empêcher le démarrage sur l'ordinateur de systèmes non signés par une autorité d'accréditation, comme Microsoft. Cette élévation de Microsoft au rang d'autorité universelle a suscité des protestations de la communauté du logiciel libre, mais certaines distributions GNU/Linux, comme Ubuntu, RedHat et Fedora, ont accepté de payer un certificat de 99 dollars pour être signées par Microsoft. Il est possible de désactiver Secure Boot et de lancer d'autres systèmes d'exploitation, comme GNU/Linux, sur un ordinateur équipé de Windows en configurant le disque de démarrage de manière adéquate et en utilisant le logiciel d'amorçage GRUB.