# Les systèmes d'exploitation/Version imprimable

* Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
* Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
* Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.
Une version à jour et éditable de ce livre est disponible sur Wikilivres, une bibliothèque de livres pédagogiques, à l'URL : https://fr.wikibooks.org/wiki/Les_syst%C3%A8mes_d%27exploitation

# Le noyau d'un système d'exploitation

Au tout début de l'informatique, le logiciel assurait lui-même la gestion du matériel. Chaque application gérait elle-même la mémoire, la communication avec les périphériques et bien d'autres choses. Le logiciel pouvait être démarré directement à l'allumage de l'ordinateur, sans charger de système d'exploitation. En conséquence, les logiciels n'étaient pas compatibles sur une large gamme de matériel et supportaient assez mal un changement de configuration.
Mais avec le temps, les informaticiens ont inventé des techniques d'abstraction matérielle qui permettent à un programme de s'exécuter sur des ordinateurs avec des matériels très différents. Rendre les programmes indépendants du matériel a demandé de revoir l'organisation des logiciels, qui ont dû être découpés en plusieurs programmes séparés :
* les programmes systèmes gèrent la mémoire et les périphériques ;
* les programmes applicatifs ou applications délèguent la gestion de la mémoire et des périphériques aux programmes systèmes.
Pour simplifier, l'ensemble des programmes système porte le nom de système d'exploitation. Le rôle du système d'exploitation est d'être un intermédiaire entre les logiciels et le matériel. Après, cette définition est assez sommaire et les systèmes d'exploitation sont très variés et ont évolué avec le temps. Mais les programmes systèmes sont clairement le cœur de tout système d'exploitation, un cœur autour duquel s'articulent tout un écosystème de programmes applicatifs plus ou moins développé.

## Les niveaux de privilège

L'OS doit garantir que seuls les programmes systèmes ont accès aux périphériques ou aux registres de gestion de la mémoire virtuelle. Pour cela, les systèmes d'exploitation actuels incorporent des niveaux de privilège, aussi appelée anneaux mémoires. Dans chaque niveau de privilège, certaines manipulations du matériel sont impossibles et certaines opérations sont interdites. Plus le niveau de privilège est bas, moins il y a d'interdiction et plus on peut faire d'opérations risquées.
S'il a existé des systèmes d’exploitation avec quatre, sept ou huit niveaux de privilège, tous les processeurs des PC modernes (x86 64 bits) gèrent seulement deux niveaux de privilèges : un mode noyau pour le système d'exploitation et un mode utilisateur pour les applications. En mode noyau, tout est autorisé ou presque, alors que les accès aux périphériques sont interdits en mode utilisateur, de même que l'accès à certaines portions de la mémoire. Un programme en mode utilisateur ne peut pas accéder aux périphériques, lire ou écrire sur le disque dur, gérer certaines portions protégées de la mémoire, etc. Seul le noyau du système d'exploitation en est capable. C'est un mécanisme qui force à déléguer la gestion du matériel au système d'exploitation.
Sur certains processeurs, on trouve des niveaux de privilèges intermédiaires entre l'espace noyau et l'espace utilisateur. Les processeurs x86 des PC 32 bits contiennent 4 niveaux de privilèges. Le système Honeywell 6180 en possédait 8. À l'origine, ceux-ci ont été inventés pour faciliter la programmation des pilotes de périphériques. Certains d'entre eux peuvent en effet gagner à avoir des niveaux de privilèges intermédiaires entre celui d'une simple application et celui d'un OS. Mais force est de constater que ceux-ci ne sont pas vraiment utilisés, seuls les espaces noyau et utilisateur étant pertinents. Il en est de même pour beaucoup de méthodes de protection mémoire. Une des raisons à cet état de fait est tout simplement la compatibilité entre architectures matérielles différentes. Par exemple, les premières versions de Windows NT n'utilisaient que deux anneaux de privilèges sur les processeurs x86, en partie parce que d'autres jeux d'instructions supportés par Windows n'avaient que deux niveaux de privilèges. Ce n'est pas la seule raison, la facilité de programmation de l'OS devant aussi être prise en compte.
Les anneaux mémoire/niveaux de privilèges étaient au tout début gérés uniquement par le système d'exploitation par des mécanismes purement logiciels, les processeurs actuels gèrent directement les anneaux de protection. En général, le processeur contient un registre qui précise le niveau de privilège, si le programme en cours est en espace noyau ou en espace utilisateur. À chaque accès mémoire ou exécution d'instruction, le processeur vérifie si le niveau de privilège permet l'opération demandée. Lorsqu'un programme effectue une instruction interdite en mode utilisateur, une exception matérielle est levée. Généralement, le programme est arrêté sauvagement et un message d'erreur est affiché.

## Les appels systèmes

Tous les programmes systèmes sont des routines d'interruptions, fournies par l'OS ou les pilotes, qui permettent d'exploiter les périphériques. Les applications peuvent appeler à la demande ces routines via une interruption logicielle : ils effectuent ce qu'on appelle un appel système. Tout OS fournit un ensemble d'appels systèmes de base, qui servent à manipuler la mémoire, gérer des fichiers, etc. Par exemple, linux fournit les appels systèmes open, read, write et close pour manipuler des fichiers, les appels brk, sbrk, pour allouer et désallouer de la mémoire, etc. Évidemment, ceux-ci ne sont pas les seuls : linux fournit environ 380 appels systèmes distincts. Ceux-ci sont souvent encapsulés dans des librairies et peuvent s'utiliser comme de simples fonctions.
L'appel système se charge automatiquement de basculer le processeur dans l'espace noyau. Cette commutation n'est cependant pas gratuite, de même que l'interruption qui lui est associée. Ainsi, les appels systèmes sont généralement considérés comme lents, très lents. Divers processeurs incorporent des techniques pour rendre ces commutations plus rapides, via des instructions spécialisées (SYSCALL/SYSRET et SYSENTER/SYSEXIT d'AMD et Intel), ou d'autres techniques (call gate d’Intel, Supervisor Call instruction des IBM 360, etc.).
Sur les PC anciens, le BIOS fournissait les routines de base et le système d'exploitation se contentait d’exécuter les routines fournies par le BIOS. Mais de nos jours, le système d'exploitation fournit ses propres routines et contourne le BIOS en modifiant le vecteur d'interruption avec les adresses de ses routines. On dit qu'il détourne l'interruption.

## Le noyau du système d'exploitation

La portion du système d'exploitation placée dans l'espace noyau est ce qu'on appelle le noyau du système d’exploitation, le reste de l'OS étant composé d'applications qui servent, par exemple, à afficher une interface graphique ou une ligne de commande. Reste que beaucoup de programmes de l'OS peuvent être placés indifféremment dans le noyau ou dans l'espace utilisateur. Mais cela a un coût : exécuter un appel système est très lent, changer de niveau de privilège étant assez couteux. Conserver de bonnes performances impose de diminuer la quantité d'appels systèmes, et donc de placer un maximum de choses en espace noyau. Mais cela se fait au prix de la sécurité, toute erreur de programmation dans le noyau entrainant un écran bleu.

### Les types de noyaux : monolithique, micro-noyaux, hybrides

On peut classer les noyaux en plusieurs types, selon l'accent mit sur les performances ou la sécurité. Dans les grandes lignes, les deux types principaux correspondent à deux visions extrêmes de ce qu'est un noyau :
* Les noyaux monolithiques placent un maximum de programmes systèmes dans l'espace noyau.
* Les micro-noyaux préfèrent au contraire placer le plus de choses dans l'espace utilisateur.
Entre ces deux types, on trouve un grand nombre d'intermédiaires appelés des noyaux hybrides. Pour information, les systèmes Unix et Linux sont basés sur des noyaux monolithiques, tandis que les systèmes Windows et Mac OS utilisent des noyaux hybrides qui reprennent les avantages des noyaux monolithiques et des micro-noyaux.
Certaines versions relativement extrêmes de noyaux monolithiques, où tout l'OS est placé dans l'espace noyau, portent le nom de noyaux mégalithiques. De même, on trouve des versions extrêmes de micro-noyaux, où tout l'OS est composé de bibliothèques logicielles exécutées en espace utilisateur, à l'exception du minimum vital. On parle alors d'exokernel ou de nanokernel.
| Noyau monolithique modulaire. | Micro noyau hybride simplifié. | Micro noyau simplifié. |

### Les avantages et inconvénients de chaque type de noyau

Chaque type de noyau a ses avantages et ses inconvénients, mais on fait la différence surtout entre les deux extrêmes que sont les micro-noyaux et les noyaux monolithiques. Micro-noyaux et noyau monolithiques sont chacun l'opposé de l'autre du point de vue des performances et de la sécurité.
* Les micro-noyaux sont très fiables, avec peu d'écrans bleus, mais avec des performances moins que les noyaux hybrides ou monolithiques. La raison tient à ce que la plupart des bogues et erreurs graves sont dans l'espace utilisateur, ce qui réduit le nombre d'écrans bleus. Avec eux, la majorité des erreurs de programmation n'entrainant pas un crash, mais simplement l'affichage d'un message d'erreur. Mais le nombre d'appels système est plus important que pour les noyaux monolithiques, ce qui est source de performances relativement faibles.
* Les noyaux monolithiques sont peu fiables, mais performants. Leurs performances excellentes viennent du fait que les appels systèmes à faire sont peu nombreux. Par contre, leur fiabilité est plutôt faible, la majorité des erreurs de programmation de l'OS se trouvant dans le noyau, source de beaucoup d'écrans bleus.
* Noyau monolithique
* Micro-noyau - appels système et services

# La multiprogrammation

Les tout premiers OS datent des années 1950, et ceux-ci ont commencé à devenir de plus en plus utilisés à partir des années 60-70. Évidemment, ces OS étaient simples, au point de ne pas pouvoir exécuter plusieurs programmes en même temps. Il était ainsi impossible de démarrer à la fois un navigateur internet, tout en écoutant de la musique. Dit autrement, ces systèmes d'exploitation ne permettaient de ne démarrer qu'un seul programme à la fois. On appelait ces OS des OS mono-programmés ou mono-tâche.
Mais cette approche avait un problème. Lors de l'accès à un périphérique, le processeur doit attendre que le transfert avec le périphérique ait cessé avant de pouvoir faire quoique ce soit d'autre. Durant toute la durée de la communication avec le périphérique, le processeur est inutilisé. Pour certains programmes qui accèdent beaucoup aux périphériques, il est possible que le processeur ne soit utilisé que 20% du temps, voire moins. Une solution possible est d’exécuter un autre programme pendant que le programme principal accède aux périphériques. Un OS qui permet cela est un OS multi-programmé. Le nombre de programmes pouvant être chargés en mémoire simultanément est appelé le taux de multiprogrammation. Plus celui-ci est élevé, plus l'OS utilisera le processeur à ses capacités maximales.
Les OS actuels vont plus loin et permettent d’exécuter plusieurs programmes "simultanément", même si aucun programme n'accède aux périphériques. Les OS de ce genre sont des OS multi-tâche. L'apparition de la multiprogrammation a posé de nombreux problèmes, notamment au niveau du partage de la mémoire et du processeur. Dans ce qui va suivre, nous allons voir comment ces OS gèrent la mémoire et les commutations entre programmes (appelés processus sur ces OS).
    Dans ce qui va suivre, nous utiliserons le terme processus pour parler d'un programme, quelqu'il soit. En réalité, les deux termes ne sont pas synonymes, comme nous le verrons vers la fin du chapitre. Mais nous ferons la confusion pour le moment.

## L'allocation du processeur

Le système d'exploitation utilise une technique très simple pour permettre la multiprogrammation sur les ordinateurs à un seul processeur : l'ordonnancement. Cela consiste à constamment alterner entre les différents programmes à exécuter : en alternant assez vite, on peut donner l'illusion que plusieurs processus s'exécutent en même temps.
Avec cette technique, chaque processus peut être dans (au moins) trois états :
* Élu : un processus en état élu est en train de s'exécuter sur le processeur.
* Prêt : celui-ci a besoin de s'exécuter sur le processeur et attend son tour.
* Bloqué : celui-ci n'a pas besoin de s'exécuter (par exemple, parce qu'il attend une donnée en provenance d'une entrée-sortie).
Suivant le système d'exploitation, d'autres états sont possibles, comme un état terminé (le programme a fini de s’exécuter), un état "en cours d'initialisation", et bien d'autres.
Les processus en état prêt sont placés dans une file d'attente, le nombre de programme dans cette liste a une limite fixée par le système d'exploitation. Lorsque l'OS décide de changer de processus, il choisit un processus dans la file d'attente et le lance sur le processeur. Pour comprendre comment faire, il faut se souvenir qu'un processus manipule un ensemble de registres processeur, aussi appelé contexte d'exécution du processus. Pour qu'un processus puisse reprendre où il en était, il faut que son contexte d’exécution redevienne ce qu'il était. Pour cela, le contexte d’exécution est sauvegardé quand le processus est interrompu et restauré lors de son redémarrage. On appelle cela une commutation de contexte. Le système d'exploitation doit évidemment mémoriser tous les contextes des processus dans une liste appelée table des processus, elle-même très liée à la file d'attente.

### L'ordonnancement sur un seul processeur

Reste que pour utiliser le processeur au mieux, il faut faire en sorte que tous les processus aient leur part du gâteau. C'est ce qu'on appelle l'ordonnancement. Il existe deux grandes formes d'ordonnancement : l'ordonnancement collaboratif, et l'ordonnancement préemptif. Dans le premier cas, c'est le processus lui-même qui décide de passer de l'état élu à l'état bloqué ou prêt, par l'intermédiaire d'un appel système. Dans le second, c'est le système d’exploitation qui stoppe l’exécution d'un processus. L'avantage du dernier cas est que les processus ne peuvent plus monopoliser le processeur.

#### L'ordonnancement collaboratif

Tout d'abord, on va commencer par un système d'exploitation qui exécute des programmes qui s’exécutent les uns après les autres. Ces programmes sont exécutés jusqu’à ce qu'ils finissent leur travail ou décident eux-mêmes de stopper leur exécution, soit pour accéder à un périphérique, soit pour laisser la place à un autre programme.
Avec l'algorithme First Input First Output (FIFO), les programmes à exécuter sont ajoutés dans la file d'attente quand on les démarre. Ceux-ci sont alors stockés dans la file d'attente dans l'ordre dans lesquels on les a fait démarrer. L'ordonnanceur décide alors d’exécuter le programme entré dans la file d'attente avant tous les autres en premier. En clair, les programmes sont exécutés dans l'ordre dans lequel ils sont rentrés dans la file d'attente.
Avec l'algorithme Last Input First Output (LIFO), les programmes à exécuter sont ajoutés dans la file d'attente quand on les démarre. Ceux-ci sont alors stockés dans la file d'attente dans l'ordre dans lesquels on les a fait démarrer. Mais contrairement à l'algorithme FIFO, l'ordonnanceur exécute le programme entré en dernier dans la file d'attente, et non le premier. Si vous ajoutez un programme dans une file d'attente contenant déjà des programmes en attente, ce sera lui le prochain à être exécuté, vu qu'il a été ajouté en dernier. Cet algorithme peut souffrir d'un phénomène assez particulier : dans certains cas, un programme peut très bien mettre énormément de temps avant d'être exécuté. Si vous exécutez beaucoup de programme, ceux-ci seront rentrés dans la file d'attente avant les tout premiers programmes exécutés en premier. Ceux-ci doivent alors attendre la fin de l’exécution de tous les programmes rentrés après eux.
L'algorithme Shortest Job First est basé sur une logique simple. Les programmes à exécuter sont placés dans la file d'attente et l’ordonnanceur va alors décider d’exécuter d'abord les processus qui se termineront le plus rapidement. Pour appliquer cet algorithme, on suppose que les temps d’exécution des différents programmes sont connus à l'avance et sont parfaitement bornés. Cette contrainte peut sembler absurde, mais elle a un sens dans certains cas assez rares dans lesquels on connait à l'avance le temps mit par un programme pour s’exécuter. Dans ce cas, l'algorithme est simple : on exécute le programme qui met le moins de temps à s’exécuter en premier. Une fois celui-ci terminé, on le retire de la file d'attente et on recommence.

#### L'ordonnancement préemptif

L'ordonnancement préemptif se base souvent sur la technique du quantum de temps : chaque programme s’exécute durant un temps fixé une bonne fois pour toutes. En clair, toutes les « x » millisecondes, le programme en cours d’exécution est interrompu et l'ordonnanceur exécuté. Ainsi, il est presque impossible qu'un processus un peu trop égoïste puisse monopoliser le processeur aux dépens des autres processus. La durée du quantum de temps doit être grande devant le temps mis pour changer de programme. En même temps, on doit avoir un temps suffisamment petit pour le cas où un grand nombre de programmes s'exécutent simultanément. Généralement, selon la rapidité du matériel, un quantum de temps entre 10 et 100 millisecondes donne de bons résultats. Pour information, Windows utilise un quantum de 15ms, et Linux un quantum de 10ms.
Voyons maintenant les algorithmes préemptifs qui permettent de choisir quel programme faire passer de l'état prêt à l'état élu. Pour faire simple, nous allons en voir quelques-uns, relativement importants et très proches de ceux utilisés dans les OS actuels.
L'algorithme Shortest Remaining Time Next est une variante préemptive de l'algorithme Shortest Job First vu au-dessus. Dans cette version, si un programme est ajouté dans la file d'attente, on regarde le temps que ce nouveau venu mettrait à s’exécuter, et on compare avec le temps qu'il reste au processus en cours d’exécution avant que celui-ci finisse son travail. Si le temps mit par le nouveau programme est plus faible que le temps d’exécution du programme en train de s’exécuter, on change et on exécute le nouveau venu à la place.
L'algorithme du tourniquet exécute chaque programme l'un après l'autre, dans l'ordre. Cet algorithme est redoutablement efficace et des OS comme Windows ou Linux l'ont utilisé durant longtemps. Mais cet algorithme a un défaut : le choix du quantum de temps doit être calibré au mieux et n'être ni trop court, ni trop long.
L'algorithme des files d'attentes multiple niveau donne la priorité aux programmes rapides ou qui accèdent souvent aux périphériques. Cet algorithme utilise plusieurs files d'attentes, auxquelles on donne des quantums de temps différents. Tout programme démarre dans la file d'attente avec le plus petit quantum de temps, et change de file d'attente suivant son utilisation du quantum. Si un programme utilise la totalité de son quantum de temps, c'est le signe qu'il a besoin d'un quantum plus gros et doit donc changer de file. La seule façon pour lui de remonter d'un niveau est de ne plus utiliser complètement son quantum de temps. Ainsi, un programme va se stabiliser dans la file dont le quantum de temps est optimal (ou presque).
L'ordonnancement par loterie repose sur un ordonnancement aléatoire. Chaque processus se voit attribuer des tickets de loterie : pour chaque ticket, le processus a droit à un quantum de temps. À chaque fois que le processeur change de processus, il tire un ticket de loterie et le programme qui a ce ticket est alors élu. Évidemment, certains processus peuvent être prioritaires sur les autres : ils disposent alors de plus de tickets de loterie que les autres. Dans le même genre, des processus qui collaborent entre eux peuvent échanger des tickets. Comme quoi, il y a même moyen de tricher avec de l'aléatoire…

### L’ordonnancement sur plusieurs processeurs

Les algorithmes ci-dessus marchent quand plusieurs processus doivent s’exécuter un seul processeur. Mais les ordinateurs actuels sont très complexes et beaucoup n'ont pas qu'un seul processeur. Soit ils ont effectivement plusieurs processeurs connectés à la carte mère, soit ils ont un processeur dit multicœurs. Pour rappel, les processeurs multicœurs peuvent être vus comme un regroupement de plusieurs processeurs sur la même puce de silicium. Pour être plus précis, ils contiennent plusieurs cœurs, chaque cœur pouvant exécuter un programme tout seul. Chaque cœur dispose de toute la machinerie électronique pour exécuter un programme, que ce soit un séquenceur d'instruction, des registres, une unité de calcul. Par contre, certains circuits d'un processeur ne sont présents qu'en un seul exemplaire dans un processeur multicœurs, comme les circuits de communication avec la mémoire ou les circuits d’interfaçage avec la carte mère.
    Dans ce qui suit, nous utiliserons le terme cœurs pour désigner soit les cœurs d'un processeur multicœurs, soit les différents processeurs d'un système multiprocesseur.
Pour profiter de plusieurs cœurs, les algorithmes d'ordonnancement doivent être revus, ou tout du moins adaptés à la présence de plusieurs cœurs. Le point principal est que le système d'exploitation doit décider de répartir les programmes sur les différents cœurs, sans compter qu'il doit le faire de manière optimale. Le cas le plus simple est celui où il y a autant de cœurs que de processus, mais ce cas est rare en pratique. Il arrive souvent qu'il y aie plus de processus à exécuter que de cœurs, ce qui fait qu'il faut alors ordonnancer plusieurs programmes sur un même cœur.
Globalement, il existe deux méthodes pures pour l'ordonnancement multicœurs : soit on gère les deux problèmes précédents séparément, soit on les gère avec un seul algorithme. Le premier cas consiste à répartir les programmes sur les différents cœurs, avant d'appliquer les algorithmes de la section précédente dans le cas où il y a plusieurs programmes sur un seul cœur. L'autre solution consiste à utiliser un seul algorithme qui résout les deux problèmes en même temps. On parle alors d'ordonnancement partitionné dans le premier cas, et d'ordonnancement global dans le second. Il existe aussi des méthodes hybride, qui font un peu des deux.
L'avantage de l'ordonnancement partitionné est sa simplicité et sa facilité de programmation. Les algorithmes précédents peuvent être réutilisés sans problème et il suffit de rajouter un algorithme de répartition des programmes sur les différents cœurs. Mais l'inconvénient est que les performances sont généralement mauvaises. La raison est qu'un processus est attribué à un cœur sans pouvoir en changer. Imaginez par exemple que je lance 6 processus différents : deux cœurs recevront un processus, les deux autres en recevront deux. Maintenant, imaginons que le ferme les deux processus sur les deux premiers cœurs : on aura alors deux cœurs inutilisés et deux cœurs qui exécutent chacun deux processus. Alors que la solution idéale est de migrer des processus pour remplir les deux cœurs inutilisés. De plus, les algorithmes pour répartir les programmes sur les différents cœurs peuvent être assez complexe. L'ordonnancement global n'a pas ce problème, car il permet de migrer des processus d'un cœur à un autre. La migration en elle-même a des couts, mais le gain en vaut très souvent la peine.
Notons que l'ordonnancement, peu importe qu'il soit partitionné ou global ou hybride, est très compliqué sur les processeurs multicœurs dits asymétriques, c'est-à-dire quand les différents cœurs ne sont pas identiques, à savoir que certains sont plus puissants que d'autres, ou que certains cœurs disposent de fonctionnalités que les autres n'ont pas. Certaines applications bénéficient à s’exécuter sur un type de cœur plutôt qu'un autre, que ce soit car elles demandent plus de puissance ou sont programmées pour utiliser les fonctionnalités de certains cœurs. Dans ce cas, la répartition est diablement complexe et les algorithmes conçus pour ce genre d'architectures sont particulièrement compliqués à programmer.

## La création et destruction de processus

Les processus peuvent naître et mourir. La plupart des processus démarrent quand l'utilisateur demande l’exécution d'un programme, n'importe quel double-clic sur une icône d’exécutable en est un bon exemple. Mais, le démarrage de la machine en est un autre exemple. En effet, il faut bien lancer le système d'exploitation, ce qui demande de démarrer un certain nombre de processus. Après tout, vous avez toujours un certain nombre de services qui se lancent avec le système d'exploitation et qui tournent en arrière-plan. À l'exception du premier processus, lancé par le noyau, les processus sont toujours créés par un autre processus. On dit que le processus qui les a créés est le processus parent. Les processus créés par le parent sont appelés processus enfants. On parle aussi de père et de fils. Certains systèmes d'exploitation conservent des informations sur qui a démarré quoi et mémorisent ainsi qui est le père ou le fils pour chaque processus. L'ensemble forme alors une hiérarchie de processus.
Sur la majorité des systèmes d'exploitation, un appel système suffit pour créer un processus. Mais certains systèmes d'exploitation (les dérivés d’Unix, notamment) ne fonctionnent pas comme cela. Sur ces systèmes, la création d'un nouveau processus est indirecte : on doit d'abord copier un processus existant avant de remplacer son code par celui d'un autre programme. Ces deux étapes correspondent à deux appels systèmes différents. Dans la réalité, le système d'exploitation ne copie pas vraiment le processus, mais utilise des optimisations pour faire comme si tout se passait ainsi.
Si les processus peuvent être créés, il est aussi possible de les détruire quand ils ont terminé leur travail ou s'ils commettent une erreur/faute lors de leur exécution. Dans tous les cas, le processus père est informé de la terminaison du processus fils par le système d'exploitation. Le processus fils passe alors dans un mode appelé mode zombie : il attend que son père prenne connaissance de sa terminaison. Lorsque le processus se termine, le système récupère tout ce qu'il a attribué au processus (PCB, espaces mémoire, etc.), mais garde une trace du processus dans sa table des processus. C'est seulement lorsque le père prend connaissance de la mort de son fils qu'il supprime l'entrée du fils dans la table des processus. Si un processus père est terminé avant son fils, le processus qui est le père de tous qui « adopte » le processus qui a perdu son père et qui se chargera alors de le « tuer ».

## La communication inter-processus

Les processus sont chargés dans des espaces mémoire dédiés où seuls eux peuvent écrire. On parle d'isolation des processus. Il faut cependant noter que tous les systèmes d'exploitation n'implémentent pas cette isolation des processus, MS-DOS en étant un exemple. Faire communiquer des processus entre eux demande d'utiliser des mécanismes de communication inter-processus. Les méthodes les plus simples consistent soit à partager un bout de mémoire entre processus, soit à communiquer par l’intermédiaire d'un fichier partagé. Mais ces méthodes rudimentaires ne sont pas très pratiques et il existe d'autres méthodes plus élaborées, que nous allons aborder maintenant.

### L'échange de messages

La première méthode de communication inter-processus est appelée l'échange de messages. Il permet aux processus de s'échanger des messages, des blocs de données de taille variable ou fixe selon l'implémentation. Mais le contenu n'est pas standardisé et chaque processus peut mettre ce qu'il veut dans un message. Le tout est que le processus qui reçoit le message sache l’interpréter. Pour cela, le format des données, le type du message, ainsi que la taille totale du message, est souvent envoyé en même temps que le message.
Dans le cas le plus simple, il n'y a pas de mise en attente des messages dans un espace de stockage partagé entre processus. On parle alors de passage de message. Cela fonctionne bien quand les deux processus ne sont pas sur le même ordinateur et communiquent entre eux via un réseau local ou par Internet. Mais certains OS permettent de mettre en attente les messages envoyés d'un processus à un autre, le processus récepteur pouvant consulter les messages en attente quand celui-ci est disponible. Les messages sont alors mis en attente dans diverses structures de mémoire partagée. Celles-ci sont appelées, suivant leur fonctionnement, des tubes ou des files de messages. Ces structures stockent les messages dans l'ordre dans lequel ils ont été envoyés (fonctionnement en file ou FIFO). La différence entre les deux est que les tubes sont partagés entre deux processus, un pouvant lire et un autre écrire, alors qu'une file de message peut être partagée entre plusieurs processus qui peuvent aussi bien lire qu'écrire.

### Les threads et fibers

Une autre méthode est de regrouper plusieurs programmes dans un seul processus, afin qu'ils partagent le même morceau de mémoire. Les programmes portent alors le nom de threads. Les threads d'un même processus partagent le même espace d'adressage. Ils partagent généralement certains segments : ils se partagent le code, le tas et les données statiques. Par contre, chaque thread dispose de sa propre pile d'appel.
Ces threads doivent aussi être ordonnancés. On fait ainsi la distinction entre threads proprement dits, gérés par un ordonnancement préemptif, et les fibers, gérés par un ordonnancement collaboratif. Le changement de contexte entre deux threads est beaucoup plus rapide que pour les processus, vu que cela évite de devoir faire certaines manipulations obligatoires avec les processus. Par exemple, on n'est pas obligé de vider le contenu des mémoires caches sur certains processeurs.
Les threads utilisateurs sont des threads qui ne sont pas liés au système d'exploitation. Ceux-ci sont gérés à l'intérieur d'un processus, par une bibliothèque logicielle. Celle-ci s'occupe de la création et la suppression des threads, ainsi que de leur ordonnancement. Le système d'exploitation ne peut pas les ordonnancer et n'a donc pas besoin de mémoriser les informations des threads. Par contre, chaque thread doit se partager le temps alloué au processus lors de l'ordonnancement : c'est dans un quantum de temps que ces threads peuvent s'exécuter.
Les threads noyaux sont gérés par le système d'exploitation, qui peut les créer, les détruire ou les ordonnancer. L'ordonnancement est donc plus efficace, vu que chaque thread est ordonnancé tel quel. Il est donc nécessaire de disposer d'une table des threads pour mémoriser les contextes d'exécution et les informations de chaque thread.
| Threads utilisateurs | Threads noyaux |

# La gestion de la mémoire

Dans le chapitre précédent, on a vu comment plusieurs programmes peuvent se partager le processeur. Mais ceux-ci doivent aussi se partager la mémoire physique : chaque programme doit avoir sa propre mémoire, sans marcher sur la mémoire des autres. Si un programme pouvait modifier les données d'un autre programme, on se retrouverait rapidement avec une situation non prévue par le programmeur, avec des conséquences allant de comiques à catastrophiques.
Il faut donc introduire des mécanismes de partage de la mémoire, ce qui implique plusieurs choses : chaque programme doit avoir son ou ses propres blocs de mémoire, et il doit être le seul à pouvoir y accéder. Ces problèmes peuvent être réglés directement au niveau du matériel par des techniques de mémoire virtuelle, mais nous n'aborderons pas ce sujet (le cours Fonctionnement d'un ordinateur vous renseignera sur le sujet). Mais le système d'exploitation a aussi un grand rôle à jouer sur les architectures sans mémoire virtuelle. Dans ce chapitre, nous allons voir comment le système d'exploitation fait pour gérer le partage de la mémoire physique entre programmes, quand la mémoire virtuelle n'est pas utilisée.

## L'espace d'adressage unique sans multiprogrammation

Avant d'aller plus loin, nous devons parler de la notion d'espace d'adressage. Un espace d'adressage est l'ensemble des adresses mémoire gérées par le processeur. Par exemple, si je prends un processeur 16 bits, il peut adresser en tout 2^16 = 65536 adresses, l'ensemble de ces adresses forme son espace d'adressage. Toutes les adresses ne sont pas forcément occupées par de la mémoire RAM. Il se peut qu'il n'y ait pas assez de RAM installée, par exemple, ce qui laisse des adresses inutilisées. Un partie de l'espace d'adressable est alors vide. Ce qui fait que l'espace d'adressage ne correspond par à la mémoire réellement installée.
De plus, sur la plupart des systèmes, l'espace d'adressage ne contient pas que la RAM, mais adresse aussi d'autres composants : des périphériques, des mémoires ROM, etc. Concrètement, des adresses censées être disponibles pour la RAM sont détournées vers la ROM ou les périphériques. On dit alors que la ROM et les périphériques sont mappés en mémoire. Et ce qui est fait avec des périphériques, l'est aussi avec des mémoires ROM, des mémoires RAM de périphériques ou d'autres composants. Mapper des périphériques ou une ROM dans la mémoire permet au processeur d'y avoir accès facilement. De plus, cela permet de remplir les vides de l'espace d'adressage, si jamais trop peu de RAM est installé. Il est d'usage de trouver une mémoire ROM au sommet de l'espace d'adressage, suivie par les adresses dédiées aux périphériques. En général, les adresses basses sont réservées pour la mémoire RAM, la mémoire ROM est dans les adresses hautes, les périphériques sont en-dessous de la ROM.

### Le découpage de l'espace d'adressage

Avec un espace d'adressage unique, le système d'exploitation réserve une portion de l'espace d'adressage au système d'exploitation, alors que le reste est utilisé pour le programme à exécuter. D'ordinaire, le système d'exploitation est est en mémoire RAM, comme le programme à lancer. Il faut alors copier le système d'exploitation dans la RAM, depuis une mémoire de masse. Il est alors placé dans les premières adresses, les adresses basses, celles-ci étant généralement réservées pour la RAM.
Sur certains systèmes, le système d'exploitation est placé dans une mémoire ROM. C'est le cas si le système d'exploitation prend très peu de mémoire, comme c'est le cas sur les systèmes les plus anciens, ou encore sur certains systèmes embarqués rudimentaires. Les deux cas font généralement un usage différent de l'espace d'adressage. Si le système d'exploitation est copié en mémoire RAM, il est généralement placé dans les premières adresses, les adresses basses. A l'inverse, un OS en mémoire ROM est généralement placé à la fin de la mémoire, dans les adresses hautes. Mais tout cela n'est qu'une convention, et les exceptions sont monnaie courantes. Il existe aussi une organisation intermédiaire, où le système d'exploitation est chargé en RAM, mais utilise des mémoires ROM annexes, qui servent souvent pour accéder aux périphériques. On a alors un mélange des deux techniques précédentes : l'OS est situé au début de la mémoire, alors que les périphériques sont à la fin, et les programmes au milieu.
Le premier modèle est celui des anciens mainframes et des stations de travail. Le second modèle est très courant dans les systèmes embarqués actuels, de par sa simplicité. Enfin, le troisième modèle était celui des ordinateurs PC un peu anciens, où le système d'exploitation déléguait la gestion des périphériques à des BIOS dédiés. Chaque périphérique incorporait un BIOS, qui contenait de quoi communiquer avec. On avait ainsi un BIOS pour la carte vidéo, un autre pour la carte son, etc.
A l'époque, les processeurs x86 avaient des adresses de 20 bits, ce qui fait 1 mébioctet de mémoire adressable. Le premier mébioctet de mémoire est décomposé en deux portions de mémoire : les premiers 640 kibioctets sont ce qu'on appelle la mémoire conventionnelle, alors que les octets restants forment la mémoire haute. Tout le reste de la mémoire, au-delà du premier mébioctet, est ce qu'on appelle la mémoire étendue et elle est apparue quand les processeurs x86 32 bits sont apparus. La distinction entre mémoire conventionnelle et haute est restée pour des raisons de compatibilité.
* Les deux premiers kibioctets de la mémoire conventionnelle sont réservés au BIOS, le reste est utilisé par le système d'exploitation (MS-DOS, avant sa version 5.0) et le programme en cours d’exécution. Pour être plus précis, les premiers octets contiennent le BIOS, qui est suivi par la BIOS Data Area utilisée par le BIOS pour stocker des données diverses, qui commence à l'adresse 0040:0000h, a une taille de 255 octets, et est initialisée lors du démarrage de l'ordinateur.
* La mémoire haute est réservée pour communiquer avec les périphériques. On y trouve aussi le BIOS de la carte vidéo (s'il existe) et les BIOS des différents périphériques, qui sont nécessaires pour les initialiser et parfois pour communiquer avec eux. De plus, on y trouve la mémoire de la carte vidéo, et éventuellement la mémoire d'autres périphériques comme la carte son.

### Le chargement d'un programme

Le démarrage d'un programme est le rôle d'un morceau du système d'exploitation appelé le chargeur de programme (loader en anglais). Celui-ci rapatrie le fichier exécutable en RAM et l’exécute avec un branchement vers la première instruction du programme démarré. Avec une telle allocation mémoire, cette tâche est relativement simple : l'adresse du début du programme est toujours la même. Les loaders de ces systèmes d'exploitation n'ont donc pas à faire grand-chose et n'ont notamment pas besoin de décider où placer le programme en mémoire. La place d'un programme en mémoire est toujours la même, elle est absolue, d'où leur nom de loaders absolus qu'on donne au chargeur de programme de ce type. Les fichiers objets/exécutables de tels systèmes d'exploitation ne contenaient que le code machine : on appelle ces fichiers des Flat Binary. On peut citer l'exemple des fichiers .COM, utilisés par le système d'exploitation MS-DOS (le système d'exploitation des PC avant que Windows ne prenne la relève).
Il faut noter qu'il est possible de lancer/exécuter plusieurs programmes en même temps avec un seul espace d'adressage. Le tout est que les programmes se partagent l'espace d'adressage à tour de rôle. Régulièrement, le programme en cours d’exécution est arrêté, pour laisser la place au suivant, et ainsi de suite. Le défaut majeur de cette méthode est qu'elle doit sauvegarder le programme en cours avant de l'arrêter, pour qu'il puisse reprendre là où il en était. Cette sauvegarde consiste à copier la totalité de la RAM et l'état du processeur sur le disque dur. Et cette copie est longue, très longue. Autant dire que cette méthode n'est pas pratique.

### La protection mémoire

Protéger les données de l'OS contre une erreur ou malveillance d'un programme utilisateur est nécessaire. Dans le cas où le système d'exploitation est placé dans une mémoire ROM, au sommet de l'espace d'adressage, il n'y a pas besoin de faire quoique ce soit. Le programme peut parfaitement lire les données de l'OS sans problèmes, et c'est même nécessaire pour certaines opérations courantes (comme les appels systèmes). Il est impossible pour le programme d'écrire dans la portion mémoire du système d'exploitation, vu que celui-ci est en ROM (une mémoire par définition inaccessible en écriture). Cette solution est de toute façon utilisée sur des systèmes très simples où la protection mémoire n'est pas très importante, de toute façon. Mais dans le cas où le système d'exploitation est chargé en RAM, tout change. il devient possible pour un programme d'aller écrire dans la portion réservée à l'OS et d'écraser le code de l'OS. Chose qu'il faut absolument empêcher.
La solution la plus courante est d'interdire les écritures d'un programme de dépasser une certaine limite, en-dessous ou au-dessus de laquelle se trouve le système d’exploitation. Pour cela, le processeur incorpore un registre limite, qui contient l'adresse limite au-delà de laquelle un programme peut pas aller. Quand un programme applicatif accède à la mémoire, l'adresse à laquelle il accède est comparée au contenu du registre limite. Si cette adresse est inférieure/supérieure au registre limite, le programme cherche à accéder à une donnée placée dans la mémoire réservée au système : l’accès mémoire est interdit, une exception matérielle est levée et l'OS affiche un message d'erreur. Dans le cas contraire, l'accès mémoire est autorisé et notre programme s’exécute normalement.

## L'espace d'adressage unique avec multiprogrammation

Il est possible de charger plusieurs programmes dans un espace d'adressage unique. Pour cela, le système d'exploitation attribue un bloc de RAM pour chaque programme, sa partition mémoire. L'usage de partitions mémoire est un sacré avantage pour la multiprogrammation. Certes, la multiprogrammation est possible sur les systèmes sans partitions mémoires, mais elles facilitent grandement son implémentation. Sans elle, on ne peut charger qu'un seul programme en RAM à la fois. Changer de programme à exécuter demande de faire des va-et-vient entre RAM et mémoire de masse.

### La relocation

Avec l'usage de partitions mémoires basiques, une partition ne peut pas être placée n'importe où en mémoire physique. Les programmes sont généralement chargés les uns à la suite des autres. On charge le premier programme au début de la mémoire, puis on charge le second, etc. Par contre, cela signifie qu'un programme n'a pas d'adresse fixée en mémoire physique. Tout dépend de l'ordre de chargement des programmes et du nombre de programmes chargés. Ainsi, les adresses de destination des branchements et les adresses des données ne sont jamais les mêmes. Il faut donc trouver un moyen pour que les programmes puissent fonctionner avec des adresses qui changent d'une exécution à l'autre. Ce besoin est appelé la relocalisation.
Pour résoudre ce problème, le compilateur considère que le programme commence à l'adresse zéro et laisse l'OS corriger les adresses du programme. La correction en elle-même n'est pas très compliquée, il faut juste considérer que les adresses fournies par le compilateur donnent la position de la donnée dans la partition mémoire. Si on sait où commence le programme en mémoire, à savoir sa première adresse, l'adresse de sa base, la correction d'adresse est triviale. Il suffit d'ajouter la position dans la partition mémoire à l'adresse de la base. Si on utilise un espace d'adressage unique, les adresses doivent être corrigées par l'OS une par une. Le chargeur de programme s'occupe de la correction des adresses.
    Le position-independant code (PIC) ou code indépendant de la position est une autre solution qui consiste à créer des programmes dont le contenu est indépendant de l'adresse de base et qui peuvent être lancés sans relocation. Mais cette méthode demande d'utiliser des techniques logicielles, aujourd'hui incorporées dans les compilateurs et les éditeurs de lien. Mais je passe ce genre de détails sous silence, nous en reparlerons d'ici quelques chapitres.

### La protection mémoire des partitions mémoires

Un programme ne doit idéalement n'avoir accès qu'à la partition qui lui est dédiée et pas aux autres, sauf dans quelques rares exceptions. Toute tentative d'accès à une autre partition doit déclencher une exception matérielle, qui entraîne souvent l'apparition d'un message d'erreur. Tout cela est pris en charge par le système d'exploitation, par l'intermédiaire de mécanismes de protection mémoire, que nous allons maintenant aborder.
Les premiers IBM 360 disposaient d'un autre mécanisme pour éviter les conflits d'accès à la mémoire. Ce mécanisme de protection attribue à chaque programme une clé de protection, qui consiste en un nombre unique de 4 bits (chaque programme a donc une clé différente de ses collègues). La mémoire est fragmentée en blocs de même taille, de 2 kibioctets. Le processeur mémorise, pour chacun de ses blocs, la clé de protection du programme qui a réservé ce bloc. À chaque accès mémoire, le processeur compare la clé de protection du programme en cours d’exécution et celle du bloc de mémoire de destination. Si les deux clés sont différentes, alors un programme a effectué un accès hors des clous et il se fait sauvagement arrêter.

### L'allocation mémoire

Si on exécute plusieurs programmes en même temps, il arrive que la mémoire ne pas à tous les contenir. Dans ce cas, la gestion de la mémoire s'effectue processus par processus. Si un programme veut s’exécuter, mais qu'il n'y a pas assez de RAM, un autre programme quitte la RAM et lui laisse sa place. Comme auparavant, le programme qui quitte la RAM est sauvegardé sur le disque dur, intégralement. On sauvegarde l'état du processeur, ses registres, la partition mémoire du programme. Le programme doit pouvoir reprendre où il en était. Ce processus de swapping est assez lourd, mais il marche très bien. Typiquement, le programme qui quitte la mémoire est choisit par le système d'exploitation.
Utiliser des partitions mémoire permet d'implémenter ce que l'on appelle l'allocation mémoire : le programme peut demander à l'OS d'agrandir ou rétrécir sa partition mémoire suivant les besoins. Si un programme a besoin de plus de mémoire, il peut en demander à l'OS. Et quand il n'a plus besoin d'une portion de mémoire, il peut la libérer. Dans les deux cas, le système d'exploitation fournit des appels système pour agrandir ou rétrécir la partition mémoire. Cela pose toutefois quelques problèmes. Prenons par exemple le cas suivant : deux programmes sont lancés et sont stockés dans deux partitions mémoire consécutives, adjacentes. Il arrive alors parfois qu'il n'y ait pas de mémoire libre à la suite du programme n° 1. Pour le résoudre, notre système d’exploitation va devoir déplacer au moins un programme et réorganiser la façon dont ceux-ci sont répartis en mémoire. Ce qui signifie qu'au moins un des deux programme sera déplacé.
Le swapping et l'allocation mémoire sont prises en charge par le système d'exploitation, mais les deux demandent de gérer la mémoire libre de l’ordinateur. Quand un programme quitte la mémoire pour être swappé sur le disque dur, il laisse derrière lui de la mémoire RAM de libre. La même chose se produit quand un programme se termine : il libère partition la mémoire qu'il occupait, qui devient de la mémoire libre. Même chose quand un programme libère de la mémoire. Voyons comment le système d'exploitation gère cette mémoire libre.

### La fragmentation externe et la compaction de la mémoire

Il arrive, généralement après beaucoup d'allocations mémoires, que l'on ait des vides dans la mémoire qui sont séparés les uns des autres. La mémoire libre est donc fragmentée en pleins de petit morceaux de mémoire libre. Et si on veut lancer un nouveau programme ou en recharger un depuis le disque dur, il se peut que ces morceaux sont tous trop petits pour l’accueillir, alors que leur somme serait suffisante. Par exemple, il se peut que l'on veuille recharge un programme depuis le disque dur, qui a besoin de 50 mégaoctets de RAM, avec 100 mégaoctets de mémoire libre mais que la mémoire libre soit fragmentée en fragments qui font tous entre 5 et 10 mégaoctets. C'est ce qui s'appelle la fragmentation externe : on dispose de suffisamment de mémoire libre, mais celle-ci est dispersée dans beaucoup de partitions qui sont trop petites.
Dans ce cas, la seule solution crédible est de compacter la mémoire, c'est à dire rassembler toutes les partitions mémoire dans les adresses basses. Cette défragmentation de la RAM, aussi appelée compaction de la mémoire RAM, garantit que l'espace libre est compacté en un seul bloc au sommet de la mémoire. Mais c'est une opération très couteuse, qui est réalisée en dernier recours.

### La gestion des partitions libres

L'OS sait quelles sont les portions de la mémoire inutilisées d’une manière ou d'une autre. Et cela peut se faire de deux manières : l'une utilise un tableau de bit, l'autre une liste chainée.
La première solution consiste à découper la mémoire en blocs de quelques kibioctets. Pour chaque bloc, l'OS retient si ce bloc est occupé ou libre en utilisant un bit par bloc : 0 pour un bloc occupé et 1 pour un bloc libre. L'ensemble de ces bits est mémorisé dans un tableau de bits. Cette technique ne gaspille pas beaucoup de mémoire si l'on choisit bien la taille des blocs. Globalement, plus les blocs sont gros, plus le tableau de bits est petit. Mais la recherche d'un bloc de mémoire libre suffisamment grand demande de parcourir le tableau de bit du début jusqu'à trouver un segment suffisant. Si on veut trouver une partition de K blocs, il faut parcourir le tableau jusqu'à trouver k bits consécutifs à 0. Or il s'agit d'une opération très lente, d'autant plus lente que le tableau de bits est gros. Le choix de la taille des blocs est généralement une histoire de compromis : un gros tableau ralentit la recherche d'une partition vide, utilise plus de mémoire, mais réduit quelque peu la fragmentation ; un petit tableau a les avantages inverses.
Une autre méthode consiste à conserver une liste chaînée des partitions mémoire. Par partition, on veut aussi bien parler des partitions mémoires associées à un processus, que les zones vides de la mémoire. L'avantage est que le parcours de la liste chainée est plus rapide qu'avec un tableau de bits, car on saute directement d'une partition à la suivante. Cette liste est généralement triée suivant les adresses des partitions/blocs libres : des partitions qui se suivent dans la mémoire se suivront dans la liste. Cela permet de faciliter la fusion des blocs libres : si un programme libère un bloc, ce bloc peut être fusionné avec d'éventuels blocs libres adjacents pour donner un seul gros bloc. Divers optimisations permettent d'accélérer la recherche de partitions mémoire suffisamment grandes pour accueillir un programme à charger.
* Par exemple, il est possible d'utiliser deux listes séparées pour les vides et les programmes, ce qui permet de rechercher uniquement dans les vides. Mais cela complexifie fortement le programme utilisé pour gérer ces listes.
* Une autre méthode trie les listes non par adresse, mais par taille : les plus gros ou plus petits trous seront alors disponibles en premier dans la liste. Cela permet de choisir rapidement les blocs les plus gros ou les plus petits capables d’accueillir un programme.

### Le choix des partitions libres

Lorsqu'on démarre un programme, l'OS doit trouver un bloc de mémoire vide pour accueillir le programme exécuté. Pour cela, l'OS doit trouver une partition vide suffisamment grande pour accueillir le programme démarré. Si le programme n'utilise pas tout le segment, on découpe la partition de manière à créer une partition pour la zone non-occupée par le programme lancé. Lors de la recherche d'un segment de mémoire capable d'accueillir un programme, on tombe souvent sur plusieurs résultats, autrement dit plusieurs segments peuvent recevoir le programme démarré. Mais si on choisit mal la partition, de multiples allocations entraînent un phénomène de fragmentation externe : on dispose de suffisamment de mémoire libre, mais celle-ci est dispersée dans beaucoup de segments qui sont trop petits.
La solution la plus simple est de placer le programme dans le premier vide capable de l’accueillir. C'est l'algorithme de la première zone libre. Si le programme n'utilise pas tout le segment, on découpe le vide en deux : une zone pour le processus, une autre zone vide pour ce qui reste. Le temps de recherche est alors minimal, car on s'arrête au premier vide convenable. Une variante permet de diminuer le temps de recherche d'un segment adéquat. L'idée est que quand on trouve un segment libre, les segments précédents ont de fortes chances d'être occupés ou trop petits pour contenir un programme. Dans ces conditions, mieux vaut commencer les recherches futures à partir du segment libre. Pour cela, lors de chaque recherche d'un segment libre, l'OS mémorise là où il s'est arrêté et il reprend la recherche à partir de celui-ci. Cet algorithme s'appelle l'algorithme de la zone libre suivante.
Une autre méthode consiste à prendre le vide le plus proche de la taille du programme à charger, celui qui contient juste ce qu'il faut de mémoire. C'est ce qu'on appelle l'algorithme du meilleur ajustement. Le défaut principal de cette méthode est qu'elle laisse beaucoup de partitions trop petites pour être utilisables. En effet, il est rare que les programmes utilisent toute la partition attribuée et laissent souvent du « rab ». Une fois la partition allouée, ce rab devient un petit espace vide très difficile à réutiliser, ce qui fait que la fragmentation externe devient alors importante. Pour éviter ce problème, on peut choisir non pas le vide le plus adapté, mais le vide le plus gros possible. C'est l'algorithme du plus grande résidu. Les résultats en matière de fragmentation mémoire sont paradoxalement assez mauvais. Pour ces deux algorithmes, on doit parcourir toute la liste avant de faire un choix, ce qui rend la recherche assez longue avec un tableau de bit ou une liste chainée triée par adresse. Cependant, avec une liste de trous triée par taille, et non par adresse, cet algorithme est particulièrement rapide. De plus, l'usage de deux listes séparées pour les trous et les processus les accélère encore plus.

# Les systèmes de fichiers

Le système de fichiers est la portion du système d'exploitation qui s'occupe de la gestion des mémoires de masse. Il prend en charge le stockage des fichiers sur le disque dur, le rangement de ceux-ci dans des répertoires, l'ouverture ou la fermeture de fichiers/répertoires, et bien d'autres choses encore.
    La gestion des partitions n'implique pas du tout le système de fichier. Le partitionnement est en réalité réalisé avant même toute implication du système d'exploitation, par le BIOS ou l'UEFI.

## Les fichiers

Les données sont organisées sur le disque dur sous la forme de fichiers. Ce sont généralement de simples morceaux d'une mémoire de masse, sur lesquels un programme peut écrire ce qu'il veut. Le système de fichiers attribuent plusieurs caractéristiques à chaque fichier.
* Chaque fichier reçoit un nom de fichier, qui permet de l'identifier et de ne pas confondre les fichiers entre eux. L'utilisateur peut évidemment renommer les fichiers, choisir le nom des fichiers, et d'autres choses dans le genre.
* En plus du nom, le système d'exploitation peut mémoriser des informations supplémentaires sur le fichier : la date de création, la quantité de mémoire occupée par le fichier, et d'autres choses encore. Ces informations en plus sont appelées des attributs de fichier.
* Il existe des normes qui décrivent comment les données doivent être rangées dans un fichier, suivant le type de données à stocker : ce sont les formats de fichiers. Le format d'un fichier est indiqué à la fin du nom du fichier par une extension de fichier. Généralement, cette extension de nom commence par un ".", suivi d'une abréviation. Par exemple, le .JPEG, le .WAV, le .MP3 ou le .TXT sont des formats de fichiers. Ces formats de fichiers ne sont pas gérés par le système d'exploitation. Tout ce que peut faire l'OS, c'est d'attribuer un format de fichier à une application : il sait qu'un .PDF doit s'ouvrir avec un lecteur de fichiers .PDF, par exemple.

### Les clusters

Pour rappel, toutes les mémoires de masse sont découpées en secteurs de taille fixe, qui possèdent tous une adresse. Les systèmes de fichiers actuels ne travaillent pas toujours sur la base des secteurs, mais utilisent des clusters, des groupes de plusieurs secteurs consécutifs. L'adresse d'un cluster est celle de son premier secteur. La taille d'un cluster dépend du système de fichiers utilisé, et peut parfois être configuré. Par exemple, Windows permet d'utiliser des tailles de clusters comprises entre 512 octets et 64 kilooctets.
La taille idéale des clusters dépend du nombre de fichiers à stocker et de leur taille. Pour de petits fichiers, il est préférable d'utiliser une taille de cluster faible, alors que les gros fichiers ne voient pas d'inconvénients à utiliser des clusters de grande taille. En effet, un fichier doit utiliser un nombre entier de clusters. Illustrons la raison par un exemple. Si un fichier fait 500 octets, il utilisera un cluster complet : seuls les 500 premiers octets seront utilisés, les autres étant tout simplement inutilisés tant que le fichier ne grossit pas. Si le cluster a une taille de 512 octets, seuls 12 octets seront gâchés. Mais avec une taille de cluster de 4 kilooctets, la grosse majorité du cluster sera inoccupé. La même chose a lieu quand les fichiers prennent un faible nombre de clusters. Par exemple, un fichier de 9 kilooctets n'utilisera pas d'espace inutile avec des clusters de 512 octets : le fichier utilisera 18 clusters au complet. Mais avec une taille de clusters de 4 Ko, trois secteurs seront utilisés, dont le dernier ne contiendra qu'1 Ko de données utiles, 3 Ko étant gâchés.
En comparaison, le débit en lecture et écriture sera nettement amélioré avec des clusters suffisamment gros. Pour comprendre pourquoi, il faut savoir que le débit d'un disque dur est le produit de deux facteurs : la taille d'une unité d'allocation (ici, un cluster) multiplié par le nombre d'opérations disque par secondes. Ces opérations disque correspondent à une lecture ou écriture de cluster. Chaque opération d'entrée-sortie utilise un peu de processeur, vu qu'il s'agit d'un appel système. Cela peut se résumer par la formule suivante, avec D le débit du HDD, IOPS le nombre d'opérations disque par secondes, et $T_{cluster}$ la taille d'un cluster : $D=IOPS\times T_{cluster}$. Pour un débit constant, augmenter la taille d'un cluster diminue le nombre d’opérations disque nécessaires. Le débit maximal est donc plus stable, beaucoup de disques durs ayant une limite au nombre d’opérations disque qu'ils peuvent gérer en une seconde. Expérimentalement, on constate que le débit en lecture ou écriture est meilleur avec une grande taille de cluster, du moins pour des accès à de gros fichiers, dont la lecture/écriture demande d’accéder à des secteurs/cluster consécutifs.

### L'allocation des secteurs

Le système d'exploitation doit mémoriser pour chaque fichier, quels sont les secteurs du HDD qui correspondent (leur adresse). Cette liste de secteurs est stockée dans une table de correspondance, située au tout début d'une partition : la Master File Table. Celle-ci contient, pour chaque fichier, son nom, ses attributs, ainsi que la liste de ses clusters. Avec un système de fichiers de ce type, chaque partition est décomposée en quatre portions :
* le secteur de boot proprement dit, qui contient le chargeur de système d'exploitation ;
* la Master File Table, qui contient la liste des fichiers et leurs clusters ;
* et enfin, les fichiers et répertoires contenus dans le répertoire racine.
Reste que lors de la création ou de l'agrandissement d'un fichier, l'O.S doit lui allouer un certain nombre de secteurs. Pour cela, il existe diverses méthodes d'allocation.
La première méthode est celle de l'allocation contiguë. Elle consiste à trouver un bloc de secteurs consécutifs capable d'accepter l'ensemble du fichier. Repérer un fichier sur le disque dur demande simplement de mémoriser le premier secteur, et le nombre de secteurs utilisés. Cette méthode a de nombreux avantages, notamment pour les performances des lectures et des écritures à l'intérieur d'un fichier. C'est l'ailleurs la voie royale pour le stockage de fichiers sur les CD-ROM ou les DVD, où les fichiers sont impossible à supprimer. Mais sur les disques durs, les choses changent. À force de supprimer ou d'ajouter des fichiers de taille différentes, on se retrouve avec des blocs de secteurs vides, coincés entre deux fichiers proches. Ces secteurs sont inutilisables, vu que les fichiers à stocker sont trop gros pour rentrer dedans. Une telle situation est ce qu'on appelle de la fragmentation. Le seul moyen pour récupérer ces blocs est de compacter les fichiers, pour récupérer l’espace libre : c'est l'opération de défragmentation.
Sur d'autres systèmes de fichiers, les clusters d'un fichier ne sont donc pas forcément consécutifs sur le disque dur. Le système d'exploitation doit garder, pour chaque fichier, la liste des clusters qui correspondent à ce fichier. Cette liste est ce qu'on appelle une liste chaînée : chaque cluster indique quel est le cluster suivant (plus précisément, l'adresse du cluster suivant). L'accès à un fichier se fait cluster par cluster. L'accès à un cluster bien précis demande de parcourir le fichier depuis le début, jusqu'à tomber sur le cluster demandé. Avec cette méthode, la défragmentation reste utile sur les HDD, vu que l'accès à des secteurs consécutifs est plus rapide. On parle d'allocation par liste chaînée.
On peut améliorer la méthode précédente, en regroupant toutes les correspondances (cluster -> cluster suivant) dans une table en mémoire RAM. Cette table est appelée la FAT, pour File Allocation Table. Avec cette méthode, l'accès aléatoire est plus rapide : parcourir cette table en mémoire RAM, est plus rapide que de parcourir le disque dur. Malheureusement, cette table a une taille assez imposante pour des disques durs de grande capacité : pour un disque dur de 200 gibioctets, la taille de la FAT est de plus de 600 mébioctets. On parle d'allocation indexée, ou allocation par FAT.
Une autre méthode consiste à ne pas stocker les correspondances (cluster -> cluster suivant), mais simplement les adresses des clusters les unes à la suite des autres : on obtient ainsi un i-nœud. C'est cette méthode qui est utilisée dans les systèmes d'exploitation UNIX et leurs dérivés (Linux, notamment). Sous Linux, la table des adresses de cluster a cependant une taille limitée. Pour gérer des fichiers de taille arbitraire, il est possible d'utiliser plusieurs tables d'i-nœuds par fichier. Ces tables sont reliées sous la forme d'une liste chaînée, chaque table d'i-nœud indiquant la suivante. Dans certains cas extrêmes, cette organisation en liste chaînée disparaît au profit d'une organisation partiellement arborescente, certaines tables contenant plusieurs pointeurs vers les tables suivantes (tables doublement indirectes).

## Les répertoires

Sur les premiers systèmes d'exploitation, on ne pouvait pas ranger les fichiers : tous les fichiers étaient placés sur le disque dur sans organisation. De nos jours, tous les systèmes d'exploitation gèrent des répertoires. Ceux-ci sont représentés sur le disque dur par des fichiers, qui contiennent des liens vers les fichiers contenus dans le répertoire. Le fichier répertoire mémorise aussi toutes les informations concernant les fichiers : leur nom, leur extension, leur taille, leurs attributs, etc. Ces informations sont rarement stockées dans le fichier lui-même. Ainsi, quand vous ouvrez un répertoire ou que vous consultez les propriétés d'un fichier, ce fichier n'est jamais ouvert : ces informations sont récupérées dans le répertoire.

### Le codage des répertoires

Un répertoire contient une liste de fichier. Pour chaque fichier, il mémorise son nom, ses attributs, ainsi que la liste des clusters qui lui sont attribués. Les attributs sont stockés dans une structure de taille fixe, le nombre des attributs par fichier étant connu à l'avance. Mais la liste des clusters et les noms des fichiers n'ont pas de taille fixée à l'avance. Cela ne pose pas de problème pour la liste des clusters, contrairement à ce qu'on a pour les noms. Généralement, les répertoires mémorisent les noms des fichiers qu'ils contiennent, avec leurs attributs. Ceux-ci sont donc placées dans un bloc de taille fixe, un en-tête.
La gestion des noms de fichiers peut se faire de plusieurs manières. Avec la première méthode, on limite la taille des noms de fichiers. On peut alors réserver une taille suffisante dans le fichier répertoire pour stocker ce nom. Par exemple, sur les premiers systèmes de fichiers FAT, les noms de fichiers étaient limités à 8 caractères (plus 3 pour l'extension de fichier). Le répertoire allouait 8 octets pour chaque nom de fichier, plus 3 octets pour l'extension. La taille utilisée était alors limitée. Cette méthode, bien que simple d'utilisation, a tendance à gâcher de la mémoire si de grands noms de fichiers sont utilisés. Et si de petits noms de fichier, l'espace utilisé sera faible, mais les utilisateurs pourront se sentir limités par la taille maximale des noms de fichier.
On peut aussi utiliser des noms de fichiers de taille variable. La solution la plus simple consiste à placer ceux-ci à la suite de l'en-tête (qui contient les attributs). Cette méthode a cependant un désavantage lors de la suppression du fichier : elle génère de la fragmentation assez facilement. Pour éviter cela, on peut placer les noms de fichier de taille variable à la fin du fichier répertoire, chaque en-tête pointant vers le nom de fichier adéquat (Linux).

### La hiérarchie de répertoires

Sur les premiers systèmes d'exploitation, tous les fichiers étaient placés dans un seul et unique répertoire. Quand le nombre de fichier était relativement faible, cela ne posait pas trop de problèmes. L'avantage de cette méthode était que le système d'exploitation était plus simple et qu'il n'avait pas à gérer une arborescence de répertoire sur le disque dur. Mais l'inconvénient se faisait sentir quand les fichiers devenaient de plus en plus nombreux. Cette organisation est encore utilisée sur les baladeurs et appareils photo numériques.
De nos jours, les répertoires sont organisés en une hiérarchie de répertoire : un répertoire peut contenir d'autres répertoires, et ainsi de suite. Évidemment, cette hiérarchie commence par un répertoire maître, tout en haut de cette hiérarchie : ce répertoire est appelé la racine. Sous Windows, on trouve une seule et unique racine par partition ou disque dur : on en a une sur C : , une autre sur D : , etc. Sous Linux, il n'existe qu'une seule racine, chaque partition étant un répertoire accessible depuis la racine : ces répertoires sont appelés des points de montage. Sur Windows, ce répertoire est noté : soit \, soit nom_lecteur : \ (C:\, D:\). Sous Linux, il est noté : / .
Reste que savoir où se trouve un fichier demande de préciser quel est le chemin qu'il faut suivre en partant du répertoire maître : on doit préciser qu'il faut ouvrir tel répertoire, puis tel autre, et ainsi de suite jusqu’au fichier. Ce chemin, qui reprendre le chemin de la racine jusqu’au fichier, est appelé le chemin d'accès absolu. Sous Windows, les noms de répertoires sont séparés par un \ : C:\Program Files\Internet Explorer. Sous Linux, les noms de répertoires sont séparés par un / : /usr/ast/courrier. Les chemins d'accès relatifs sont similaires, sauf qu'ils ne partent pas de la racine : ils partent d'un répertoire choisit par l'utilisateur, nommé répertoire courant. Dans les grandes lignes, l'utilisateur ou un programme choisissent un répertoire et lui attribuent le titre de répertoire courant. Généralement, chaque processus a son propre répertoire de travail, qu'il peut changer à loisir. Pour cela, le programme doit utiliser un appel système, chdir sous Linux.
Linux a une particularité : il normalise la place de certains répertoires bien précis du système d'exploitation. L'arborescence des répertoires est en effet standardisé par le Filesystem Hierarchy Standard, la dernière version datant de juin 2015.

# Le démarrage de l'ordinateur

Le démarrage de l'ordinateur implique à la fois le matériel de l'ordinateur et le système d'exploitation. Sur les machines les plus simples, généralement des systèmes embarqués, le système d'exploitation est placé dans une petite mémoire ROM et est lancé automatiquement au démarrage de l'ordinateur. Mais sur les ordinateurs personnels actuels, le système d'exploitation est placé sur une mémoire de masse, comme un disque dur ou une clé USB. Le processus de démarrage est alors plus compliqué. Aucun ordinateur ne boote directement depuis le disque dur ou une clé USB, ce qui fait qu'il y a forcément une mémoire ROM dans un ordinateur moderne. Elle sert lors du démarrage de l'ordinateur pour le configurer à l'allumage et démarrer son système d'exploitation. Cette mémoire ROM est appelée le firmware, et ce n'est autre que le BIOS sur les ordinateurs anciens, l'UEFI sur les ordinateurs récents.
Sur les ordinateurs modernes, le démarrage est un processus qui demande de nombreuses étapes, la majorité se passant avant le lancement du système d’exploitation. Le démarrage commence quand l'utilisateur appuie sur le bouton d’alimentation. Le courant passe alors dans les différents circuits de l'ordinateur, qui s'allument. Le processeur est conçu pour démarrer l’exécution d'un programme à une adresse bien précise, adresse à laquelle se trouve le firmware. Le firmware s’exécute alors et commence son travail. Il effectue beaucoup de choses, mais la première est de tester le bon fonctionnement du processeur, de la mémoire et des périphériques cruciaux. Cette étape de test est appelée le power self-on test. Si une erreur est rencontrée, le démarrage stoppe et le BIOS émet une suite de bips caractéristique. Mais si aucune erreur n'est rencontrée, le firmware poursuit le démarrage et accède alors au disque dur. Précisément, il lit le premier secteur du disque dur et lance un programme de démarrage spécialisé, appelé le bootloader, dont le but est de lancer le système d'exploitation.
    Dans ce wikilivre sur les systèmes d'exploitation, nous n'allons pas nous intéresser à ce que fait le firmware avant de lire le disque dur. Il s'agit là d'une procédure réalisée entièrement en matériel, par le firmware, qui a plus sa place dans un cours d'architecture des ordinateurs. La procédure de démarrage du BIOS est d'ailleurs abordé dans mon wikilivre "Fonctionnement d'un ordinateur", dans le chapitre sur la carte mère, accessible via ce lien : La carte mère, chipset et BIOS. Dans ce qui suit, nous partons du principe que le firmware a fait son travail de test et d'initialisation du matériel, et s’apprête à passer la main au système d'exploitation.

## Le bootloader et les partitions

Le firmware accède en premier au disque dur, avant de laisser la main au système d'exploitation. Diverses informations sont placés dans les premiers secteurs du disque dur, pour déterminer quels sont les systèmes d'exploitations installés, comment est partitionné le disque dur, comment lancer le système d'exploitation, etc. Suivant que l'on parle du BIOS ou de l'UEFI ou de leur équivalent sur les MAC et autres architectures, ces informations ne sont pas stockées de la même manière. Mais on peut quand même donner quelques généralités sur ces informations de démarrage.

### Le chargeur d’amorçage

En premier lieu, il faut parler du chargeur d'amorçage (bootloader), un morceau de logiciel qui démarre le système d'exploitation. Il le copie en mémoire, démarre le noyau et les services en espace utilisateur, et bien d'autres choses. Il existe de nombreux chargeur d'amorçage, certains sont des logiciels libres, d'autres des logiciels propriétaires. Tous les systèmes d’exploitation modernes fournissent leur propre chargeur d'amorçage. Sur les systèmes Microsoft, le chargeur d'amorçage utilisait le BIOS et correspondait à deux fichiers : le NTLDR (NT LoaDeR ou Chargeur d'amorçage de Windows NT) et un fichier de configuration boot.ini. Depuis Vista, le chargeur d'amorçage est winload.exe et sa configuration est stockée dans le registre. Apple a son propre chargeur d'amorçage appelé Bootcamp. Les chargeurs d'amorçage open Source sont eux plus nombreux, mais les plus connus sont de loin GRUB, Coreboot, et LILO/eLILO.
Il faut noter que certains bootloaders permettent de lancer plusieurs systèmes d'exploitation différents. Attention, je ne veux pas dire que l'on peut lancer plusieurs systèmes d’exploitation en même temps, comme c'est le cas avec les techniques de virtualisation. Je veux dire que l'on peut lancer au choix Windows, Linux, ou un autre OS. Il est possible d'installer plusieurs systèmes d'exploitation sur un ordinateur et de décider lequel lancer au démarrage.

### La table des partitions

Un autre point important pour le démarrage est que les partitions du disque dur sont gérées avant même le lancement du système d'exploitation. Pour rappel, partitionner un disque dur signifie le diviser en plusieurs morceaux, qui seront considérés par le système d'exploitation comme autant de disques durs séparés. Les informations sur les partitions sont mémorisées dans une table des partitions, qui stocke la taille et le premier secteur de chaque partition, ainsi que quelques informations complémentaires.

## Le démarrage sur les ordinateurs personnels de type PC

Sur les ordinateurs de type PC, au jeu d'instruction x86, il existe deux standards pour les firmware : le BIOS pour les ordinateurs anciens, et l'UEFI, pour les ordinateurs récents. Le processus de démarrage est différent pour les deux. Notamment, les informations de démarrage sur le disque dur ne sont pas organisées de la même manière. Le BIOS n'utilise que le premier secteur du disque dur, alors que l'UEFI prend plus de place. La table des partitions n'est pas la même suivant que l'on parle d'un ordinateur avec un BIOS ou utilisant l'UEFI.

### Le Master Boot Record et le BIOS

Sur les PC avec un BIOS, les informations de démarrage sont stockées dans le Master Boot Record (MBR), le premier secteur du disque dur, qui joue un rôle important lors du démarrage de l'ordinateur. Le BIOS est conçu pour lire MBR, récupérer le bootloader dans le MBR, puis lancer le noyau et le reste du système d'exploitation.
Le MBR est structuré comme illustré ci-dessous, en trois grandes parties aux usages différents.
* Les premiers octets du MBR sont remplis par le bootloader. Il existe parfois une portion du code exécutable qui contient les messages d'erreur à afficher dans le cas où le lancement du système d'exploitation échouerait. Sur les BIOS récents, cette portion se termine par quelques octets de signature et d'anticopie.
* La table des partitions contient des informations sur les différentes partitions installées sur le disque dur : leur « nom », leur taille, et leur localisation sur le disque dur (adresse LBA). On ne peut créer que quatre lignes dans cette table, on se trouve donc limité à quatre partitions principales. Il faut dire que cette table ne fait que 64 octets (elle a été conçue comme cela).
* Les deux derniers octets du MBR doivent avoir une valeur bien précise pour que le BIOS autorise l'exécution. Cette valeur, appelée le nombre magique, vaut 0xAA55, ce qui correspond à 43 605 en décimal. Mais le résultat est encore plus joli en binaire : 1010 1010 0101 0101.

#### La table des partitions

Les informations de chaque partition sont codées sur 16 octets, de la manière indiquée ci-dessous. La partition correspond évidemment à un bloc de secteurs consécutifs. Vu que la taille d'une partition est codée sur 32 bits, la taille d'une partition ne peut pas dépasser les 4 Giga-secteurs. Sur les mémoires de masse qui ont des secteurs de 512 Kio, cela correspond à une capacité totale de 2,2 Téraoctets.
| Flag qui indique si la partition est bootable ou non | Adresse CHS du début de la partition | Type de la partition | Adresse CHS de la fin de partition | Adresse LBA du début de la partition | Taille de la partition en nombre de secteurs |
| 1 octet | 3 octets | 1 octet | 3 octets | 4 octets | 4 octets |
Afin de dépasser la limite de 4 partitions, il est possible de subdiviser une partition en sous-partitions, appelées partitions logiques. Pour cela, la partition subdivisée doit être définie comme une partition dite étendue dans le MBR (le type de la partition doit avoir une valeur bien précise). Les informations sur une partition logique sont mémorisées dans un secteur situé au début de la partition logique, dans une structure appelée Extended Boot Record. Celui-ci a une structure similaire au MBR, à quelques détails près. Premièrement, seules les deux premières entrées de la table des partitions sont censées être utilisées. La première indique l'adresse de la prochaine partition logique (ce qui fait que les EBR forment une liste chaînée), tandis que la seconde sert pour les informations de la partition logique proprement dite. De plus, la place normalement réservée au chargement de système d'exploitation est remplie de zéros.

#### Le bootloader

Le bootloader du MBR est très petit, trop petit pour contenir le moindre code substantiel. Il ne peut pas à lui seul démarrer le système d'exploitation, charger le noyau et autre. Sa réelle utilité est de charger un second bootloader, plus consistent, depuis le disque dur. On distingue ainsi le bootloader de première étape, localisé dans le MBR, et le bootloader de seconde étape situé sur le disque dur. Le premier lit la table des partitions, détecte quelles sont les partitions actives (celles bootables) et décide depuis laquelle charge le second bootloader. Le second bootloader démarre le noyau, les drivers, puis lance les logiciels en espace utilisateur. Les bootloaders de première étape les plus connus sont coreboot et Libreboot pour les logiciels open source, mais les systèmes d'exploitations usuels fournissent aussi leurs propres bootloaders. Les bootloaders de seconde étape les plus connus sont GNU GRUB, rEFInd, BOOTMGR, Syslinux, NTLDR (Windows uniquement) et iBoot (mac).

### Les tables GUID et l'UEFI

Afin de faire face aux limitations de ce système, le MBR est progressivement remplacé par des table de partitionnement GUID. Avec elle, la table des partitions peut contenir 32 partitions différentes. La table des partitions contient donc 32 entrées, une pour stocker les informations sur chaque partition. Ces entrées sont précédées par un en-tête, qui contient des informations générales permettant au système de fonctionner. Cet en-tête est lui-même précédé par un MBR tout ce qu'il y a de plus normal, pour des raisons de compatibilité.
Les adresses de chaque partition sont des adresses LBA codées sur 8 octets (64 bits), ce qui permet de gérer des partitions plus grandes qu'avec le MBR, allant jusqu’à 2,2 téraoctets. Voici à quoi ressemble une entrée de la table des partitions.
| Type de la partition | Identifiant GUID | Première adresse LBA | Dernière adresse LBA | Attributs de la partition | Nom de la partition |
| 16 octets | 16 octets | 8 octets | 8 octets | 8 octets | 72 octets |
L'UEFI utilise les tables de partition GUID pour faire son travail, mais il dispose d'un mode de compatibilité avec le MBR au cas où. Les PC avec des BIOS ne sont pas censés utiliser les partitions GUID, car cela fait partie du standard UEFI, mais quelques BIOS en sont cependant capables.

# Virtualisation et machines virtuelles

Grâce aux différentes technologies de virtualisation, il est possible de lancer plusieurs systèmes d'exploitation en même temps sur le même ordinateur. Il est ainsi possible de passer d'un O.S à un autre relativement rapidement, suivant les besoins, avec un simple raccourci clavier. Vous avez certainement déjà eu l'occasion d'utiliser VMWARE ou un autre logiciel de virtualisation. Ces technologies sont aussi beaucoup utilisées sur les serveurs, entre autres.

## Les machines virtuelles

Les logiciels de virtualisation implémentent ce qu'on appelle des machines virtuelles. Il s'agit d'une sorte de faux matériel, simulé par un logiciel. Un logiciel qui s’exécute dans une machine virtuelle aura l'impression de s’exécuter sur un matériel et/ou un O.S différent du matériel sur lequel il est en train de s’exécuter. Dans ce qui suit, nous parlerons de V.M (virtual machine), pour parler des machines virtuelles.
Les machines virtuelles sont aussi utilisées sur ce qu'on appelle les émulateurs, des logiciels qui permettent de simuler le fonctionnement d'anciens ordinateurs ou consoles de jeux. Les techniques de virtualisation fonctionnent un peu différemment de l'émulation de consoles de jeux. Un émulateur a besoin d'émuler le processeur, qui est généralement totalement différent entre le matériel émulé et le matériel sur lequel s’exécute la V.M. La différence principale est une différence de jeu d'instruction, ce qui fait que l'émulation implique généralement de traduire les instructions à exécuter dans la V.M par des instructions exécutables par le processeur. Ce n'est pas le cas avec la virtualisation, le jeu d'instruction étant le même.
Le logiciel de virtualisation est généralement limité à un logiciel appelé hyperviseur. Celui-ci gère plusieurs machines virtuelles, une par O.S lancé sur l'ordinateur. Il existe différents types d'hyperviseurs, qui sont généralement appelées sous les noms techniques de virtualisation de type 1 et 2. Dans le premier cas, l'hyperviseur s’exécute directement, sans avoir besoin d'un O.S sous-jacent. Dans le second cas, l'hyperviseur est un logiciel applicatif comme un autre, qui s’exécute sur un O.S bien précis. Les émulateurs utilisent systématiquement un hyperviseur de type 2 amélioré, capable de simuler le jeu d'instruction du processeur émulé.
| Hyperviseur de type 1 | Hyperviseur de type 2 |
Une méthode annexe à la virtualisation de type 2 consiste à modifier l'O.S à virtualiser de manière à ce qu'il puisse communiquer directement avec l'hyperviseur. On parle alors de paravirtualisation. Avec cette méthode, les appels systèmes des O.S sont remplacés par des appels systèmes implémentés par l'hyperviseur.

## Fonctionnement/implémentation

On peut se demander comment les technologies de virtualisation et les émulateurs font pour simuler une machine virtuelle. Pour être considéré comme un logiciel de virtualisation, un logiciel doit remplir trois critères :
* L'équivalence : l'O.S virtualisé et les applications qui s’exécutent doivent se comporter comme s'ils étaient exécutés sur le matériel de base, sans virtualisation.
* L'efficacité : La grande partie des instructions machines doit s’exécuter directement sur le processeur, afin de garder des performances correctes. Ce critère n'est pas respecté par les émulateurs matériels, qui doivent simuler le jeu d'instruction du processeur émulé.
* Le contrôle des ressources : tout accès au matériel par l'O.S virtualisé doit être intercepté par la machine virtuelle et intégralement pris en charge par l'hyperviseur.
Remplir ces trois critères est possible sous certaines conditions, établies par la théorie de la virtualisation de Popek et Goldberg. Ceux-ci ont réussit à établir plusieurs théorèmes sur la possibilité de créer un hyperviseur pour une architecture matérielle quelconque. Ces théorèmes se basent sur la présence de différents types d'instructions machines. Pour faire simple, on peut distinguer les instructions systèmes, qui agissent sur le matériel. Il s'agit d'instructions d'accès aux entrées-sorties, aussi appelées instructions sensibles à la configuration, et d'instructions qui reconfigurent le processeur, aussi appelées instructions sensibles au comportement.
Une autre distinction est la distinction entre instruction privilégiées ou non. Certaines instructions sont exécutables uniquement si le processeur est en mode noyau. Si ce n'est pas le cas, le processeur considère qu'une erreur a eu lieu et lance une exception matérielle. Ces instructions sont appelées des instructions privilégiées. On peut considérer qu'il s'agit d'instructions que seul l'O.S peut utiliser. À côté, on trouve des instructions non-privilégiées qui peuvent s’exécuter aussi bien en mode noyau qu'en mode utilisateur.
La théorie de Popek et Goldberg dit qu'il est possible de virtualiser un O.S à une condition : que les instructions systèmes soient toutes des instructions privilégiées. Si c'est le cas, virtualiser un O.S signifie simplement le démarrer en mode utilisateur. Quand l'O.S exécutera un accès au matériel, il le fera via une instruction privilégiée. Ce faisant, celle-ci déclenchera une exception matérielle, qui sera traitée par une routine d'interruption spéciale. L'hyperviseur n'est ni plus ni moins qu'un ensemble de routines d'interruptions, chaque routine simulant le fonctionnement du matériel émulé. Par exemple, un accès au disque dur sera émulé par une routine d'interruption, qui utilisera les appels systèmes fournit par l'OS pour accéder au disque dur réellement présent dans l'ordinateur. Cette méthode est souvent appelé la méthode trap-and-emulate.
Mais le critère précédent n'est pas respecté par beaucoup de jeux d'instructions. Par exemple, ce n'est pas le cas sur les processeurs x86, qu'ils soient 32 bits. Diverses instructions systèmes ne sont pas des instructions privilégiées. La solution est simplement de traduire à la volée les instructions systèmes (privilégiées ou non-privilégiées) en appels systèmes équivalents. Cette technique est appelée la réécriture de code.
Certains processeurs disposent de technologies matérielles d'accélération de la virtualisation. Sur les processeurs x86, on peut citer l'Intel Vtx ou l'AMD-V.

# Assembleur et édition des liens

La majorité des programmes actuels sont écrits dans des langages de haut niveau, comme le C, le Java, le C++, l'Erlang, le PHP, etc. Mais ces langages ne sont pas compréhensibles par le processeur, qui ne comprend que le langage machine. Les codes sources écrits dans des langages de haut niveau doivent donc être traduit en langage machine par la chaîne de compilation. À l'heure actuelle, la majorité des compilateurs ne traduit pas directement un langage de haut niveau en langage machine, mais passe par un langage intermédiaire : l'assembleur. Cet assembleur est un langage de programmation, utilisé autrefois par les programmeurs, assez proche du langage du langage machine. Il va de soit que cet assembleur doit être traduit en langage machine pour être exécuté par le processeur. Tout ce qui se passe entre la compilation et l'exécution du programme est pris en charge par trois programmes qui forment ce qu'on appelle la chaîne d'assemblage. Cette chaîne d'assemblage commence par le logiciel d'assemblage qui traduit le code assembleur en code machine. Ce code machine est alors mémorisé dans un fichier objet. Ensuite, l'éditeur de liens, ou linker, qui combine plusieurs fichiers objets en un fichier exécutable. Enfin, le chargeur de programme, aussi appelé loader, charge les programmes en mémoire. L'ensemble regroupant compilateur et chaîne d'assemblage, avec éventuellement des interpréteurs, est appelé la chaîne de compilation.
* La chaine de compilation
* Un programme écrit dans un langage de haut niveau (le C, en l’occurrence).
* Le code assembleur.
* Le programme en langage machine.
Traduire les l'assembleur en instructions-machine est la première tâche du logiciel d'assemblage, mais ce n'est pas la seule. Il s'occupe aussi de la résolution des symboles, à savoir qu'il transforme les labels (et autres symboles) en adresses mémoires (l'adresse de l'instruction cible d'un branchement, ou adresse d'une variable). Pour détailler plus, il faut faire la différence entre les symboles locaux, utilisés uniquement dans le module où ils sont définis (ils servent à fabriquer des fonctions, variables statiques et structures de contrôle), des symboles globaux, référencés dans d'autres fichiers (ils servent pour nommer les fonctions accessibles à l'extérieur du module, et les variables globales). De plus, la chaîne d’assemblage doit s'occuper en partie de la relocation, même si cela dépend fortement du processeur. Les contraintes d'alignement mémoire, la taille variable des instructions, et les modes d'adressages utilisés vont devoir être pris en compte lors du processus de relocation. Évidemment, les logiciels de la chaîne d'assemblage peuvent aussi optimiser le code assembleur généré, de manière à le rendre plus rapide. Mais nous passerons cette fonctionnalité sous silence dans ce qui suit.

## Le logiciel d'assemblage

L'assembleur permet, comme le langage machine, d'utiliser directement le instructions du jeu d'instruction, mais dans une version nettement plus facile pour les êtres humains. Au lieu d'écrire ces instructions sous la forme de suites de bits, la programmation en assembleur décrit chaque instruction en utilisant du texte. Ainsi, les opérandes peuvent être écrites en décimal, au lieu de devoir être écrites en binaires. De plus, les opcodes sont remplacées par un mot : la mnémonique. Pour donner un exemple, l’instruction d'addition aura pour mnémonique ADD, ce qui est plus facile à taper que le code binaire correspondant. Il existe aussi des mnémoniques pour les registres, qui portent le nom de noms de registres. Par exemple, l'assembleur x86 nomme les registres avec les mnémoniques EAX, EBX, ECX, EDX, etc. Les modes d'adressages sont pris en charge via des syntaxes spéciales. Il est aussi possible de nommer une ligne de code (une instruction, donc) en lui attribuant un label, qui est remplacé par l'adresse de l'instruction lors de la traduction en langage machine. Ces labels sont utiles pour remplacer l'adresse de destination des branchements, ce qui permet de ne pas écrire ces adresses en dur.
Certains assembleurs permettent aussi de créer des macros, des ancêtres des fonctions. Ces macros sont simplement des suites d'instructions qui sont nommées. Il est possible d'insérer ces macros n'importe où dans le code, en mettant leur nom à cet endroit en utilisant une syntaxe spéciale. La suite d'instruction sera alors recopiée à l'endroit où le nom de la macro a été inséré, lors de la traduction en langage machine. Cela évite d'avoir à faire des copier-coller.
Le logiciel d'assemblage traduit chaque ligne de code l'une après l'autre. Cela demande de :
* remplacer la mnémonique par l'opcode correspondant ;
* remplacer les opérandes par la suite de bits correspondante ;
* remplacer les labels par l'adresse qui correspond ;
* remplacer les macros par leur contenu ;
* ne rien faire sur les commentaires.
Il faut cependant noter que les langages assembleurs ne sont pas forcément rudimentaires. Il existe notamment des assembleurs de haut-niveau, qui gèrent structures de contrôle, fonctions, procédures, types de données composites (structures et unions), voire la programmation orientée objet par classes. Ceux-ci demandent d'ajouter une phase de compilation en assembleur « pur » à un logiciel d'assemblage plus rudimentaire.

### Macros

La première opération que va faire le logiciel d'assemblage est le remplacement [appel de macro → corps de la macro]. Ces macros sont sauvegardées dans une table de hachage qui associe un nom de macro à son corps : la table des macros. Cependant, les choses deviennent beaucoup plus compliquées quand les macros contiennent des arguments/paramètres, ou quand le logiciel d'assemblage utilise des macros imbriquées ou récursives. Pour effectuer ce remplacement, le logiciel d'assemblage peut procéder en une ou deux étapes, la situation la plus simple à comprendre étant celle à deux étapes.
Un assembleur à deux étapes (on peut aussi dire : à deux passes) procède comme suit : la première étape parcourt le code assembleur pour détecter les macros, alors que la seconde effectue le remplacement. L'algorithme de la première passe lit le fichier source ligne par ligne. Si une ligne est une macro, il crée une entrée dans la table des macros et copie les lignes de code suivantes dans celle-ci. Il continue ainsi jusqu'à tomber sur le mot-clé qui indique la fin du corps de la macro. C'est aussi lors de cette passe que sont gérées les directives. Par la suite, le logiciel d'assemblage va effectuer le remplacement, qui ne peut pas se faire « en place » : le logiciel d'assemblage doit copier le fichier source dans un nouveau fichier.
Certains assembleurs forcent la déclaration des macros en début de fichier, juste avant le code principal. Dans ce cas, les macros sont toutes déclarées avant leur utilisation, ce qui permet de fusionner ces deux passes en une seule : c'est la passe 0.
* Lire une ligne de code dans le fichier source ;
* Si cette ligne est un nom de macro, créer une entrée dans la table des macros, et copier les lignes de code suivantes dans celle-ci jusqu'à tomber sur le mot-clé qui indique la fin du corps de la macro : à ce moment-là, on retourne à l'étape 1 ;
* Si cette ligne est une directive qui peut être gérée lors de la passe 0, l'exécuter, puis retourner à l'étape 1 ;
* Si cette ligne est une instruction-machine, copier celle-ci dans le nouveau fichier source (sauf s'il s'agit de la ligne qui indique la fin du programme) ;
* Sinon, accéder à la table des macros et copier le corps de la macro ligne par ligne dans le nouveau fichier.
* Si cette ligne indique la fin du code source, arrêter là.

### Mnémoniques

Pour traduire les mnémoniques en opcode, le logiciel d'assemblage contient une table de hachage mnémonique → opcode : la table des opcodes. Cette table associe à chaque mnémonique l'opcode qui correspond, éventuellement la taille de l'opcode pour les architectures à instructions de taille variable ou d'autres informations. Il se peut qu'une mnémonique corresponde à plusieurs instructions-machine, suivant le mode d'adressage. Dans ce cas, chaque entrée de la table des mnémoniques contient plusieurs opcodes, le choix de l'opcode étant fait selon le mode d'adressage. Identifier le mode d'adressage est relativement simple : une simple expression régulière sur la ligne de code suffit. Certaines mnémoniques sont des cas particuliers d'instructions-machine plus générales : on parle de pseudo-instructions. Par exemple, sur les processeurs assez anciens qui utilisent le jeu d'instruction MIPS, l'instruction MOV r1 → r2 est synthétisée à partir de l'instruction suivante : add r1, r0, r2. Dans ces conditions, la table des mnémoniques ne contient pas l'opcode de l'instruction, mais littéralement une bonne partie de la représentation binaire de l'instruction, avec des opérandes (ici, des noms de registres) déjà spécifiés. Un champ pseudo-instruction est ajouté dans la table des opcodes pour savoir si seul l'opcode doit être remplacé ou non.

### Symboles locaux

Pour traduire les symboles locaux, le logiciel d'assemblage utilise une table des symboles, qui mémorise les correspondances entre un symbole (un label le plus souvent) et sa valeur/adresse. Pour chaque symbole, cette table mémorise diverses informations, dont le nom du symbole, sa valeur et son type. La table des symboles est sauvegardée dans le fichier objet, vu qu'elle servira par la suite pour la relocation au niveau du linker et du loader. Pour remplir la table des symboles, le logiciel d'assemblage doit savoir quelle est l'adresse de l'instruction qu'il est en train de traduire. Pour cela, il suffit de profiter du fait que le logiciel d'assemblage traduit une ligne de code à la fois : le logiciel d'assemblage utilise un simple compteur, mis à zéro avant le démarrage de la traduction, qui est incrémenté de la taille de l'instruction après chaque traduction.
Il se peut que la valeur d'un symbole soit définie quelques lignes plus bas. Le cas le plus classique est celui des branchements vers une ligne de code située plus loin dans le programme. Toute instruction qui utilise un tel label ne peut être totalement traduite qu'une fois la valeur du label connue. Pour résoudre ce problème, il existe deux méthodes : la première correspond à celle des logiciels d'assemblage à deux passes, et l'autre à celle des logiciels d'assemblage à une passe.
Les assembleurs à deux passes sont les plus simples à comprendre : le logiciel d'assemblage parcourt une première fois le code ASM pour remplir la table des symboles et repasse une seconde fois pour traduire les instructions. Ces assembleurs font face à un léger problème sur les processeurs dont les instructions sont de taille variable : lors de la première passe, le logiciel d'assemblage doit déterminer la taille des instructions qu'il ne traduit pas, afin de mettre à jour le compteur d'adresse. Et cela demande d'analyser les opérandes et de déterminer le mode d'adressage de l'instruction.
Les assembleurs à une passe fonctionnent autrement : ceux-ci vont passer une seule fois sur le code source. La table des symboles de ces assembleurs contient, en plus des correspondances nom-valeur, un bit qui indique si la valeur du symbole est connue et une liste d'attente, qui contient les adresses des instructions déjà rencontrées qui ont besoin de la valeur en question. Quand ils rencontrent une référence dont la valeur n'est pas connue, ils ajoutent le symbole à la table des symboles et l'adresse de l'instruction dans la liste d'attente, et poursuivent le parcours du code source. S'ils rencontrent une instruction qui utilise ce symbole à valeur inconnue, l'adresse de l'instruction est ajoutée à la liste d'attente. Quand la valeur est enfin connue, le bit de la table de symboles est mis à 0 (pour indiquer que la valeur est connue), et le logiciel d'assemblage met à jour les instructions mémorisées dans la liste d'attente. Cette méthode pose cependant quelques problèmes sur les processeurs dont les instructions sont de taille variable.

### Noms de registres et autres constantes

On pourrait penser qu'il existe une table de correspondance pour les noms de registres, comme la table de mnémoniques pour les mnémoniques, mais on peut ruser en considérant les noms de registres comme des symboles comme les autres : il suffit de remplir la table des symboles avec les correspondances nom de registre → représentation binaire, et le tour est joué. On peut utiliser le même principe pour gérer les préfixes des instructions, comme sur le jeu d'instruction x86.

### Optimisation

Il n'est pas rare que le code assembleur soit optimisé avant d'être traduit en langage machine. D'autres assembleur optimisent directement le code objet crée. Ces optimisations sont relativement rudimentaires. Il s'agit le plus souvent de remplacement d'instructions lentes par des instructions équivalentes mais plus rapides. Par exemple, il est possible de remplacer des multiplications ou divisions par une puissance de deux par des décalages, plus rapides. Le logiciel d'assemblage peut aussi modifier l'ordre des instructions pour profiter au mieux du pipeline. Dans tous les cas, ces optimisations sont prises en charge à part, soit dans une passe d'optimisation du code assembleur, soit par un logiciel annexe au logiciel d'assemblage, qui optimise directement le code objet.

## L'édition des liens

De nos jours, les programmes actuels sont composés de plusieurs modules ou classes, qui sont traduits chacun de leur côté en fichier objet. Les symboles globaux, qui référencent une entité déclarée dans un autre fichier objet, ne sont pas traduits en adresses par le logiciel d'assemblage. Pour obtenir un fichier exécutable, il faut combiner plusieurs fichiers objets en un seul fichier exécutable, et traduire les symboles globaux en adresses : c'est le but de la phase d'édition des liens, effectuée par un éditeur de liens, ou linker.
En l'absence de segmentation mémoire (une forme de mémoire virtuelle), le linker concatène les fichiers objets. Avec la segmentation, chaque fichier objet a ses propres segments de code et de données, qui doivent être fusionnés. Pour faire son travail, le linker doit savoir où commence chaque segment dans le fichier objet, son type (code, données, etc.), et sa taille. Ces informations sont mémorisées dans le fichier objet, dans une table de segments, créée par le logiciel d'assemblage. De plus, le linker doit rajouter des vides dans l'exécutable pour des raisons d'alignement au niveau des pages mémoire.
* Édition des liens sans segmentation.
* Édition des liens avec segmentation.

### Relocation

Combiner plusieurs fichiers objets en exécutable va poser un problème similaire à celui obtenu lors du lancement d'un programme en mémoire : les adresses calculées en supposant que le fichier objet commence à l'adresse 0 sont fausses. Pour corriger celles-ci, le linker doit effectuer une relocation, et considère que le début du fichier exécutable est à l'adresse 0. Pour cela, le linker doit connaître l'emplacement des adresses dans le fichier objet, informations qui sont mémorisées dans la table des symboles sauvegardée dans le fichier objet.

### Résolution des symboles globaux

De plus, le linker s'occupe de la résolution des symboles globaux. En effet, quand on fait appel à une fonction ou variable localisée dans un autre fichier objet, la position de celle-ci dans le fichier exécutable (et donc son adresse) n'est pas définie avant son placement dans le fichier exécutable : la table des symboles contient des vides. Une fois la fusion des fichiers objets opérée, on connaît les adresses de ces symboles globaux, qui peuvent être traduits : le linker doit donc mettre à jour ces adresses dans le code machine (c'est pour cela qu'on parle d'édition des liens).

## Les chargeurs de programme

Au démarrage d'un programme, un morceau du système d'exploitation, le chargeur de programme ou loader, rapatrie le fichier exécutable en RAM et l'exécute. Sur les systèmes sans mémoire virtuelle, le loader vérifie s'il y a suffisamment de mémoire pour charger le programme. Pour cela, il a besoin de savoir quelle est la taille du code machine et de la mémoire statique, ces informations étant mémorisées dans l'exécutable par le linker.

### Loaders absolus

Sur les systèmes d'exploitation mono-programmés, il était impossible d'exécuter plusieurs programmes en même temps. Ces systèmes d'exploitation découpaient la mémoire en deux parties : une portion de taille fixe réservée au système d'exploitation et le reste de la mémoire, réservé au programme à exécuter. Avec cette technique, l'adresse du début du programme est toujours la même : les loaders de ces systèmes d'exploitation n'ont pas à gérer la relocation, d'où leur nom de loaders absolus. Les fichiers objets/exécutables de tels systèmes d'exploitation ne contenaient que le code machine : on appelle ces fichiers des Flat Binary. On peut citer l'exemple des fichiers .COM, utilisés par le système d'exploitation MS-DOS (le système d'exploitation des PC avant que Windows ne prenne la relève).
Quand les programmes consistaient en un seul fichier assembleur de plusieurs milliers de lignes de code, il était possible de les traduire en langage machine et de les lancer directement. Le logiciel d'assemblage était un assemble-go loader, un assembleur à une passe qui écrivait le code machine directement en RAM. Il n'y avait alors pas besoin d'édition des liens et le loader était fusionné avec le logiciel d'assemblage.

### Loaders à relocation

Avec le temps, les systèmes d'exploitation sont devenus capables de faire résider plusieurs programmes en même temps dans la RAM de l'ordinateur, ce qui demanda au loader de s'occuper de la relocation. Le loader doit donc savoir où sont les adresses dans le fichier exécutable, histoire de les « relocaliser ». Pour cela, il se base sur une table de relocalisation qui indique la localisation des adresses dans le fichier exécutable. Cette table est généralement une copie de la table des symboles, à quelques différences près : pour chaque label, on a ajouté un bit qui indique si l'adresse correspondante doit être relocalisée. Les assembleurs à deux passes peuvent produire une telle table sans aucune modification, ce qui n'est pas le cas des assembleurs habituels à une seule passe.
Avec la multiprogrammation, il est devenu possible de démarrer plusieurs copies d'un même programme simultanément. Dans ce cas, il est possible de partager certains segments du code machine entre les différentes copies du programme. Pour cela, le loader doit savoir où se situent le code machine et les données statiques dans le fichier exécutable, ce qui demande de sauvegarder ces informations dans le fichier exécutable. Ces informations sont mémorisées dans un en-tête, qui mémorise la position et la taille des autres segments dans le fichier (avec souvent d'autres informations).
Sur certains processeurs, la relocation est totalement gérée en matériel, à l'intérieur du processeur. C'est notamment le cas pour les ordinateurs qui utilisent la mémoire virtuelle. Sur ces ordinateurs, les loaders ne font que modifier la table des pages pour faire croire que le fichier exécutable est « swappé » sur le disque dur : le chargement du programme se fera à la demande, quand un chargement d'instruction déclenchera un défaut de page (page miss). Certains processeurs ont tenté d'être encore plus novateurs, en se payant le luxe de supprimer aussi l'étape d'édition des liens. Sur ces processeurs, l'attribution d'une adresse à un objet est déterminée au cours de l'exécution du programme, directement au niveau matériel. Mais ces architectures, dites à arithmétique à zéro adresse (Zero address arithmetic), sont cependant très rares.

### Loaders à édition des liens dynamique

Les librairies partagées sont des librairies mises en commun entre plusieurs programmes : il n'existe qu'une seule copie en mémoire, que les programmes peuvent utiliser au besoin. Les librairies statiques ont toujours la même place en mémoire physique : pas besoin de relocation ou de résoudre les labels qui pointent vers cette librairie. Avec les librairies dynamiques, la position de la librairie en mémoire varie à chaque démarrage de la machine : il faut faire la relocation, et résoudre les labels/symboles de la librairie.
Dans certains cas, l'édition des liens s'effectue dès le démarrage du programme, qui doit indiquer les librairies dont il a besoin. Mais dans d'autres cas, le programme charge les librairies à la demande, en appelant le loader via une interruption spéciale : il faut alors passer le nom de la librairie à exécuter en paramètre de l'interruption.

## Pour aller plus loin

* Livre Assemblers and loaders, disponible gratuitement via le lien suivant : Assemblers and loaders ;
* Livre Linkers and Loaders de John R. Levine, publié par by Morgan-Kauffman, (ISBN 1-55860-496-0).

# La base de registre de Windows

Vous avez peut-être entendu parler de la fameuse base de registre de Windows, sans trop savoir ce que c'est ni à quoi cela peut bien servir. Beaucoup de sites web racontent n'importe quoi à son propos et la plupart préconisent des manipulations inutiles, voire dangereuses, de celle-ci. Certaines manipulations du registre permettraient ainsi de gagner en performance, de débloquer des fonctionnalités cachées, ou de résoudre divers problèmes techniques (spoiler : non). Nettoyer celle-ci permettrait de gagner en performance (spoiler : non plus), de même que la défragmenter.
Dans les grandes lignes, la base de registre est juste une base de données. Il s'agit d'un ensemble de fichiers, qui mémorise les options de configuration des logiciels ou du système d'exploitation. Elle y stocke les associations de fichier (quel programme permet d'ouvrir tel type de fichier), les paramètres configurables dans le panneau de configuration, les programmes lancés au démarrage, etc. Toutes les options du matériel, des pilotes de périphérique, du système d'exploitation, ou des différents programmes sont ainsi mémorisées dans le registre (à quelques exceptions près).

## Pourquoi une base de registre ?

On peut se demander pourquoi Windows utilise une base de registre relativement centralisée, contrairement à ce que font d'autres systèmes d'exploitation. Par exemple, les distributions Linux regroupent leurs fichiers de configuration dans un répertoire nommé /etc. Eh bien il faut savoir que Windows n'a pas toujours procédé ainsi. Les premières versions de Windows se passaient totalement de base de registre, celle-ci n'ayant été ajoutée qu'à partir de la version 3.1.

### Avant la base de registre

À l'époque du MS-DOS, seuls deux fichiers étaient utilisés en lieu et place de la base de registre :
* config.sys contenait des informations de configuration du DOS ;
* autoexec.bat démarrait une série de commandes au démarrage de l'OS.
Puis vinrent les premières versions de Windows. Avant Windows 3.1, Windows utilisait des fichiers .ini pour mémoriser les options de l'OS, d'un programme ou d'un pilote de périphérique. Ces fichiers étaient des fichiers textes, découpés en sections qui pouvaient contenir plusieurs déclarations de données. Chaque donnée était déclarée par un nom de variable, suivi par un signe égal, lui-même suivi par la valeur de la variable. Les noms des sections étaient indiqués entre crochets et tout ce qui suivait ce nom appartenait à la section.
Les programmes décidaient où placer leurs fichiers .ini sur le disque dur, le plus souvent dans le répertoire du pilote ou du programme. En faisant ainsi, chaque programme avait accès seulement à ses options de configuration et ne pouvait pas récupérer les options du système d'exploitation directement.
Seuls quelques fichiers étaient utilisés par le système d'exploitation :
* win.ini pour les paramètres de l'utilisateur ;
* system.ini pour tout ce qui a trait au matériel ;
* et reg.dat pour les associations de fichier.
Si vous regardez sur votre disque dur, vous verrez que les deux premiers fichiers existent toujours. Évidemment, ceux-ci ne contiennent pas le registre de Windows. Ils ne sont là que pour conserver la compatibilité avec les anciennes versions de Windows, au cas où vous tenteriez d'utiliser un programme conçu pour Windows 3.1 sur votre ordinateur. Une grande part du mode de compatibilité des programmes de Windows se base sur ce fichier.

### L'apparition de la base de registre

Sous Windows 3.1, la base de registre avait un rôle extrêmement limité comparé à celui qui prévaut de nos jours. Le registre de 3.1 servait uniquement pour les associations de fichiers. Il mémorisait que tel fichier s'ouvre avec tel programme. Ce n'est qu'avec les Windows suivants que le rôle de la base de registre s'est complexifié et qu'elle a commencé à mémoriser des informations de plus en plus disparates.
Si le registre a été inventé, c'est pour limiter le nombre de fichiers de configuration et organiser un petit peu les informations de configuration. Centraliser le tout dans une base de registre a clairement facilité la tâche des développeurs de logiciels, notamment pour la création des installeurs et désinstalleurs. Aujourd'hui, le registre n'utilise que quelques fichiers sur le disque dur qui sont appelés des ruches. On est bien loin de l'orgie de fichiers de configuration des premiers temps.

## Le contenu de la base de registre

Les informations sont mémorisées dans le registre sous la forme d'attributs auxquels on affecte un nom, une valeur et un type. Les types autorisés sont les suivants :
* des données binaires (REG_BINARY) ;
* des nombres entiers, (REG_DWORD pour les entiers 32 bits, REG_QWORD pour les 64 bits) ;
* des chaines de caractères (REG_SZ pour les chaines simples, REG_EXPAND_SZ pour les chaines qui contiennent des variables d'environnement et REG_MULTI_SZ pour des listes de chaines) ;
* des données non-typées (NONE) ;
* et un type spécifique au registre, que je ne détaillerai pas : REG_LINK.

### Les clés de registre

L'ensemble des attributs est mémorisé dans une arborescence qui ressemble beaucoup à celle d'un système de fichier. On peut voir le registre comme une sorte d'arborescence de répertoires qui contiennent soit des attributs, soit d'autres répertoires. Les clés de registres étant au registre ce que les répertoires sont aux systèmes de fichiers.
Certaines clés de registres sont partagées par tous les utilisateurs de l’ordinateur. Les différents comptes administrateurs, invités et utilisateur y ont donc accès. Mais certaines clés sont spécifiques à un utilisateur bien précis. Un utilisateur a notamment accès à ses clés HKEY_USERS, mais n'a pas accès aux clés de registres des autres utilisateurs. Pour cela, chaque clé de registre se voit attribuer une liste de contrôle d'accès. Cette liste mémorise, pour chaque clé, quels sont les utilisateurs qui peuvent y accéder et quels sont les droits de chaque utilisateur. Les droits prévus pour chaque clé sont les suivants :
* lire la clé ;
* modifier la clé ;
* supprimer la clé
* être prévenu des changements sur cette clé ;
* créer un lien vers cette clé (réservé au système d'exploitation) ;
* créer une sous-clé ;
* récupérer la liste des sous-clés ;
* modifier la liste des contrôles d'accès ;
* récupérer la liste des contrôles d'accès.
L'administrateur de l'ordinateur peut ainsi empêcher la modification de certaines clés de registre, afin d’éviter certaines manipulations dangereuses. Ce blocage des clés peut être fait poste par poste ou via des outils de gestion de parc informatique. L'administrateur peut ainsi établir une politique de groupe, à savoir faire en sorte que certains types de comptes n'aient pas certains droits ou ni puissent pas faire telle ou telle manipulation.

### Les clés primaires

Lorsqu’on ouvre le registre, on voit clairement qu'il existe cinq clés principales :
* HKEY_CLASSES_ROOT, qui contient les associations de fichiers ;
* HKEY_CURRENT_USER, qui contient les informations sur l'utilisateur (celui qui a ouvert la session) ;
* HKEY_LOCAL_MACHINE, qui contient les informations liées au matériel (pilotes notamment) ;
* HKEY_USERS, qui contient les paramètres de chaque utilisateur (tout ce qui est modifiable dans le panneau de configuration et même un peu plus) ;
* HKEY_CURRENT_CONFIG, qui contient les informations de la configuration matérielle.
En réalité, il existe deux clés primaires, les trois autres clés principales étant des sous-clés des deux autres. Ces deux clés primaires sont HKEY_LOCAL_MACHINE et HKEY_USERS. Ainsi, HKEY_CURRENT_USER est un alias qui pointe vers HKEY_USERS\Current_user. De même, HKEY_CURRENT_CONFIG est juste un lien vers la sous-clé HKEY_Local_Machine\System\ControllSet001\Hardware Profiles. Enfin, HKEY_CLASSES_ROOT est une sorte de fusion entre HKEY_LOCAL_MACHINE\Software\Classes et HKEY_CURRENT_USER\Software\Classes keys.

#### HKEY_LOCAL_MACHINE

La clé HKEY_LOCAL_MACHINE contient plusieurs sous-clés :
* HARDWARE ;
* SYSTEM ;
* SOFTWARE ;
* SECURITY ;
* SAM.
| Sous-clé | Description |
| HARDWARE | Cette clé est recréée à chaque démarrage et mémorise toutes les informations sur la configuration matérielle : processeur, quantité de RAM, périphériques installés et ainsi de suite. |
| SYSTEM | Elle contient les options des pilotes de périphériques et divers informations sur la RAM et les pilotes. |
| SOFTWARE | Elle contient toutes les informations de configuration des logiciels, leurs emplacements sur le disque dur, la position des installeur/désinstalleurs, etc. Elle est souvent structurée de manière à ce que chaque éditeur de logiciel ait sa propre sous-clé, sous-clé qui contient des clés pour chaque programme de l'éditeur installé sur l'ordinateur. Cette organisation en éditeur/programme n'est cependant pas toujours respectée. |
| SECURITY / SAM | Les deux mémorisent les informations des différents comptes utilisateurs : leur noms, leurs mots de passe, leurs options de sécurité, etc. C'est notamment dans cette clé que se situent tous les mots de passe du système. Mais des protections logicielles font que cette clé est inaccessible pour la plupart des utilisateurs (elles paraissent vides). |
Détaillons un petit peu les clés SECURITY et SAM. La SAM, ou Secure Account Manager, est la base de données des comptes utilisateurs, qui contient les noms et mots de passe des comptes. Avant Windows 2000, toute la gestion des comptes utilisateurs se basait sur cette SAM et divers outils permettraient de sécuriser et de gérer la SAM. Cette SAM est localisée dans le fichier Windows\system32\Config\SAM.
Il y a de cela quelques années, Windows ne chiffrait pas les mots de passe mémorisés dans ce fichier. Le fichier était cependant protégé et seuls les comptes administrateurs avec certains droits d'accès pouvaient y accéder. Mais, un attaquant pouvait quand même lire le contenu de ce fichier avec une petite ruse. Il lui suffisait de faire démarrer l'ordinateur sur une clé USB, un CD-ROM ou tout autre mémoire externe sur laquelle on a installé un système d'exploitation. Ainsi, l'attaquant pouvait lire le contenu du disque dur sous Linux, sans que les sécurités de Windows n'y change quoi que ce soit. Il pouvait donc lire le fichier et accéder aux comptes utilisateur comme bon lui semble.
Mais depuis Windows 2000, tous les mots de passe sont chiffrés et la gestion des mots de passe ne passe plus par la base de registre, mais par une technologie nommée Active Directory.

#### HKEY_USERS

La clé HKEY_USERS contient divers paramètres, généralement ceux modifiables dans le panneau de configuration :
* les paramètres d'apparence de Windows ;
* les réglages d'accessibilité ;
* les paramètres d'impression ;
* et bien d'autres encore.
On y trouve plusieurs clés : une par utilisateur de la machine, plus une clé DEFAULT qui contient les réglages par défaut. Chaque clé contient :
* AppEvents, pour les sons associés aux événements Windows ;
* Console, pour gérer la ligne de commande ;
* Control Panel, qui regroupe tous les paramètres réglables dans le panneau de configuration ;
* Identities pour les réglages d'Outlook Express/Windows Mail ;
* Keyboard pour les réglages du clavier ;
* Printers pour les réglages des imprimantes installées ;
* Session Information contient des informations sur la session Windows actuelle ;
* Software contient certains paramètres des logiciels installés.

#### HKEY_CLASSES_ROOT

Pour rappel, la clé HKEY_CLASSES_ROOT n'est qu'une sorte de fusion entre HKEY_LOCAL_MACHINE\Software\Classes et HKEY_CURRENT_USER\Software\Classes keys. Si l'on regarde la clé HKEY_CLASSES_ROOT, on s’aperçoit que celle-ci contient une clé pour chaque extension de fichier connue. On peut dire que c'est un descendant du fameux fichier REG.DAT des premiers Windows, qui mémorisait ces associations de fichiers.

## L'organisation sur le disque dur de la base de registre

Comme dit plus haut, le registre est mémorisé dans divers fichiers répartis sur le disque dur, généralement dans des répertoires différents. Ces fichiers sont appelés des ruches. Il s'agit évidemment de fichiers cachés, afin que l'utilisateur lambda ne puisse pas modifier leur contenu par inadvertance. Il faut dire que vu l'importance du registre et de son contenu, les concepteurs de Windows préfèrent éviter que n'importe qui puisse y toucher.
Sur le disque dur, une ruche correspond en fait à deux fichiers :
* un fichier primaire, sans extension de fichier, qui contient les données de la ruche ;
* un fichier .LOG, qui sert juste à enregistrer les modifications faites dans le fichier primaire.
Le fichier primaire a toujours une taille qui augmente ou diminue par pas de 256 kibioctets, pour éviter la fragmentation.

### Le format de fichier de registre

Un fichier de registre peut être décomposé en plusieurs sections :
* un en-tête de 4 kibioctets ;
* suivi de plusieurs bins, de taille multiple de 4 kibioctets, eux-même composés :
** d'un entête HBIN de 32 octets ;
** suivi de cellules, qui mémorisent un attribut ou une clé.
Ce système permet de faciliter la gestion des données dans le fichier. Cela permet notamment de réserver de l'espace disque à l'avance pour y enregistrer des données (des cellules), de faciliter la mise à jour des cellules et ainsi de suite. Il se peut que des bins vides, sans données, soient entourés par des bins occupés.
Évidemment, un tel format de fichier n'est pas conçu pour économiser de l'espace disque, mais plus pour améliorer les performances et la gestion du contenu des fichiers. Il faut dire que les fichiers du registre n'ont que rarement des tailles importantes et que leur taille reste très souvent faible. Dans ces conditions, mieux vaut garder de bonnes performances ou faciliter la gestion des fichiers. Nous en reparlerons dans la partie sur la défragmentation du registre.

#### Les cellules

Chaque cellule contient :
* soit un attribut ;
* soit une clé ;
* soit une liste de sous-clés ;
* soit une liste d'attributs ;
* soit un descripteur de sécurité.
Le type de données présent dans la cellule est indiqué au début de celle-ci, dans un en-tête spécial. Une cellule peut contenir des données de taille variable, mais dont la taille sera toujours un multiple de 8 octets. Si jamais la donnée ne respecte pas cette contrainte, on ajoutera des données inutiles pour atteindre le multiple de 8 octets immédiatement supérieur. La cellule commence par un nombre entier qui indique le nombre d'octets occupé par la cellule. Si cet entier est positif, la cellule est vide. S'il est négatif, alors la taille est égale à l'opposé de ce nombre.
Chaque cellule peut faire référence à une autre. Par exemple, les cellules de valeur font référence à une valeur qui est enregistrée dans le fichier. Les cellules de clés peuvent indiquer où se situent les sous-clés associées dans le fichier. Dit autrement, toute la hiérarchie, l'arborescence du registre est mémorisée dans le fichier via des liens, des références vers d'autres morceaux du fichier.
Localiser une cellule ou une valeur dans le fichier se fait avec l'index de la donnée, à savoir la distance qui sépare celle-ci depuis le premier HBIN du fichier. Pour les cellules qui ne sont pas enregistrées sur le disque dur, les clés volatiles, le bit de poids fort de cet index est mis à 1. Il est à 0 dans le cas contraire (clés non-volatiles).

#### Les Bins

Lorsqu'on ajoute des clés dans un fichier, celles-ci sont ajoutées dans des bins. Certains bins ne sont pas pleins : on peut alors leur ajouter des clés. Quand on ajoute des clés dans un bin plein, sa taille augmente brusquement de 4 kibioctets. La part des 4 kibioctets non-utilisée par les clés ajoutées est considéré comme de l'espace libre utilisable pour de futures clés.

### La localisation des fichiers sur le disque dur

Sous Windows 9x le registre est stocké dans les fichiers USER.DAT et SYSTEM.DAT du répertoire \WINDOWS. On devine rapidement que USER.DAT contient la clé HKEY_USERS, et que SYSTEM.DAT contient la clé HKEY_LOCAL_MACHINE (rappelez-vous que les trois autres sont des sous-clés des deux précédentes). Windows Me possède un fichiers de plus : CLASSES.DAT.
Sur les Windows plus récent, toutes les clés sont mémorisées dans le répertoire Windows\System32\Config, à l'exception de HKEY_USERS. La clé HKEY_USERS est mémorisée dans Windows\Profiles\Username. Mais il ne faut pas croire qu'à chaque clé principale correspond une ruche, c'est-à-dire un fichier sur le disque dur. En réalité, voici plus ou moins l'organisation en fichier de ces clés.
| Hive Registry Path | Hive File Path |
| HKEY_LOCAL_MACHINE \SYSTEM | %SystemRoot%1\system32\config\system |
| HKEY_LOCAL_MACHINE \SAM | %SystemRoot%\system32\config\sam |
| HKEY_LOCAL_MACHINE \SECURITY | %SystemRoot%\system32\config\security |
| HKEY_LOCAL_MACHINE \SOFTWARE | %SystemRoot%\system32\config\software |
| HKEY_LOCAL_MACHINE \HARDWARE | Pas de fichier |
| HKEY_USERS \UserProfile | Profile, souvent le répertoire \profiles\user |
| HKEY_USERS.DEFAULT | %SystemRoot%\system32\config\default |
Dans le tableau plus haut, vous avez vu que certaines clés n'ont pas de fichier associé. C'est tout à fait normal, dans le sens où elles sont reconstruites à chaque démarrage de l'ordinateur. Elles ne sont jamais enregistrées sur le disque dur et n'ont pas de fichiers associés. Ces clés sont appelées des clés volatiles. Toute modification de ces clés ou des valeurs/clés qu'elles contiennent ne peut donc pas être sauvegardé. Les clés suivantes sont des clés volatiles :
* HKEY_LOCAL_MACHINE\System\CurrentControlSet ;
* HKEY_CURRENT_USER ;
* HKEY_LOCAL_MACHINE\Hardware.
Les fichiers du registre ne sont pas lus ou écrits depuis le disque dur à chaque fois qu'on en a besoin. À la place, le système d'exploitation copie le registre en mémoire RAM au démarrage du système d'exploitation. Cela prend un peu de mémoire, mais pas beaucoup. Évidemment, le système d'exploitation utilise de nombreuses techniques d'optimisation pour faciliter la recherche d'une informations dans le registre. Une partie de celles-ci sont décrites dans les documents suivants : Inside registry internals, The Internal Structure of the Windows Registry.

## Manipuler le registre

Aussi bien le système d'exploitation que les programmes installés peuvent manipuler le registre. L'utilisateur peut aussi aller trifouiller dans le registre de lui-même, s'il sait comment faire. Dans ce qui va suivre, nous allons voir quelles sont les manipulations habituelles sur le registre, à savoir :
* la modification ;
* la sauvegarde ;
* et les opérations comme le nettoyage ou la défragmentation.

### La modification du registre

Modifier le registre peut se faire à la main. Windows est fourni avec un éditeur de registre, regedit.exe, qui permet de lire le contenu du registre et de le modifier. Cela peut servir aux utilisateurs expérimentés qui souhaitent modifier des options sans avoir à passer par le panneau de configuration.
Mais, dans la plupart des cas, le registre est modifié directement par les programmes, essentiellement des installeurs ou des désinstalleurs. C'est généralement lors de l'installation d'un programme que le registre est modifié et que les clés liées au programme installé sont créées. Une fois la clé créée, il se peut que l'ordinateur doive redémarrer pour que les clés soient prises en compte. Cela vient du fait que beaucoup de clés ne sont vérifiées que lors du démarrage de l'ordinateur (c'est le cas des clés liées aux pilotes ou aux services de Windows). Dans ces conditions, un redémarrage est obligatoire pour que leur nouvelle valeur soit prise en compte.
Pour modifier le registre, Windows fournit diverses API, c'est-à-dire des bibliothèques de fonctions qui manipulent le registre. Il s'agit notamment des APIs Win32 Registry, qu'on trouve dans la DLL nommée ADVAPI32.DLL. Cette bibliothèque fournit plusieurs fonctions qui travaillent sur les clés ou les attributs.

### La sauvegarde du registre

Toutes les modifications du registre sont loin d'être heureuses. Par exemple, de nombreux logiciels espions ou adwares modifient le registre afin de commettre leurs méfaits. De plus, il est possible que des installeurs ou désinstalleurs bogués oublient d'effacer des clés de registre inutiles. Pire : certains logiciels qui prétendent nettoyer le registre de données soit-disant inutiles peuvent littéralement casser le registre en supprimant des clés importantes. Il est cependant possible de revenir sur des modifications assez simplement. Windows fournit divers outils pour sauvegarder le registre et son contenu.
La première méthode pour sauvegarder le registre passe par une copie de celui-ci. On pourrait croire que l'on peut faire cette copie à la main, mais c'est oublier que de nombreux fichiers du registre ne sont pas accessibles via l'explorateur de fichiers, sans compter que Windows interdit la copie de certains. On est donc obligé d'utiliser une autre méthode. Cette méthode passe par regedit : celui-ci permet d'exporter tout ou partie des clés du registre.
Une autre méthode est celle des fameux points de restauration de Windows. Ces points de restauration ne sont ni plus ni moins que des copies, des sauvegardes du registre. Ils permettent de restaurer le registre à un état antérieur, quand tout allait bien. Il faut cependant préciser que tout le registre n'est pas forcément sauvegardé. Premièrement, seule une portion importante du registre l'est. Ensuite, la sauvegarde ne prend en compte que ce qui a changé depuis la dernière sauvegarde.

### Le nettoyage et défragmentation du registre

Si vous avez déjà trainé sur divers sites de téléchargement d’utilitaires, vous connaissez certainement les logiciels de nettoyage ou de défragmentation du registre. Le nettoyage du registre sert surtout à supprimer des clés de registre devenues inutiles. Par exemple, de nombreux logiciels laissent des clés de registres une fois désinstallés (la clé de registre n'est pas effacée lors de la désinstallation). Quand on installe beaucoup de logiciels, il se peut que le registre contienne quelques clés inutiles.
Dans les faits, nettoyer le registre est souvent une mauvaise idée. Déjà, le gain en performance et en espace disque est nul, ou du moins trop faible pour valoir le coup. Effacer les clés inutiles ne diminue pas de beaucoup l'espace disque libre, en raison de l'organisation des fichiers sur le disque. On se retrouve juste avec des bins partiellement vides ou complètement vides. Les défragmenteurs et compacteurs de registre compactent les données dispersées dans plusieurs bins, histoire d'obtenir des bins totalement pleins. Ils en profitent pour supprimer les bins vides obtenus à la fin du fichier (ou entre les bins remplis). Mais vu qu'un fichier du registre grandit ou diminue par blocs de 256 kibioctets, cela ne sert généralement à rien : on ne récupère pas assez d'espace pour franchir la barre des 256 kibioctets.
De même, on voit mal d'où pourraient provenir les gains de performances du nettoyage, vu que la recherche d'une information dans le registre est très rapide. Le seul moment où le registre est massivement utilisé est au démarrage du système d'exploitation, quand le registre est copié dans la mémoire RAM. Le compacter ou le défragmenter peu alors rendre sa copie plus rapide et le démarrage marginalement plus rapide (on gagne tout au plus quelques secondes).
Nettoyer le registre peut cependant avoir des conséquences assez fâcheuses si une clé utile est effacée. Et sachant que beaucoup de nettoyeurs ne savent pas vraiment faire la différence entre ce qui est utile et ce qui ne l'est pas… Bref, vous avez bien compris que les nettoyeurs et compacteurs/défragmenteurs de registre sont tout au plus inutiles, au pire nuisibles.