De nombreuses instructions ou fonctionnalités d'un programme nécessitent de connaitre une adresse dès la compilation (les branchements par exemple). Sur la plupart des OS actuels, l'adresse à laquelle on charge un programme en mémoire n'est presque jamais la même d'une exécution à l'autre. Ainsi, les adresses de destination des branchements et les adresses des données ne sont jamais les mêmes. Il nous faut donc trouver un moyen pour faire en sorte que nos programmes puissent fonctionner avec des adresses qui changent d'une exécution à l'autre. Ce besoin est appelé la relocation.
De plus, un autre problème se pose : un programme peut être exécuté sur des ordinateurs ayant des capacités mémoires diverses et variées et dans des conditions très différentes. Par exemple, un programme doit pouvoir fonctionner sur des ordinateur ayant peu de mémoire sans poser de problèmes. Après tout, quand on conçoit un programme, on ne sait pas toujours quelle sera la quantité mémoire que notre ordinateur contiendra et encore moins comment celle-ci sera partagée entre nos différents programmes en cours d’exécution : s'affranchir de limitations sur la quantité de mémoire disponible est un plus vraiment appréciable. Ce besoin est appelé l'abstraction matérielle de la mémoire.
Généralement, plusieurs programmes sont présents en même temps dans notre ordinateur et doivent se partager la mémoire physique. 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. Cela a des conséquences qui vont de comiques à catastrophiques et cela fini très souvent par un joli plantage. Il faut donc introduire des mécanismes de protection mémoire.
Pour éviter cela, chaque programme a accès à des portions de la mémoire dans lesquelles lui seul peut écrire ou lire. Le reste de la mémoire est inaccessible en lecture et en écriture, à part pour la mémoire partagée entre différents programmes. Ces droits sont différents pour chaque programme et peuvent être différents pour la lecture et l'écriture : on peut mettre certaines portion de mémoire en lecture seule, en écriture seule, etc. Toute tentative d'accès à une partie de la mémoire non-autorisée déclenchera une exception matérielle (rappelez-vous le chapitre sur les interruptions) qui devra être traitée par une routine du système d'exploitation. Généralement, le programme fautif est sauvagement arrêté et un message d'erreur est affiché à l'écran.
Ces détails concernant l'organisation et la gestion de la mémoire sont assez compliqués à gérer et faire en sorte que les programmes applicatifs n'aient pas à s'en soucier est des plus agréable. Ce genre de problème a eu des solutions purement logicielles : on peut citer par exemple l'overlaying. Mais d'autres techniques règlent ces problèmes directement au niveau du matériel : on parle de mémoire virtuelle.
Mono-programmation
Sur les ordinateurs mono-programmés, capables d’exécuter un seul programme à la fois, la technique la plus souvent utilisée est la technique du moniteur résident. Cela consiste à découper la mémoire en deux parties :
- une portion de taille fixe et constante qui sera réservée au système d'exploitation ainsi qu'à quelques autres machins (par exemple la gestion des périphériques) ;
- et le reste de la mémoire qui sera réservé au programme à exécuter.
Chargement d'un programme
Au démarrage d'un programme, un morceau du système d'exploitation, le chargeur de programme (loader en anglais), rapatrie le fichier exécutable en RAM et l’exécute. 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 à 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).
Protection mémoire
Protéger les données de l'OS contre une erreur ou malveillance d'un programme utilisateur est nécessaire. La solution la plus courante est d'interdire les écritures d'un programme utilisateur aux adresses inférieures à la limite basse du programme applicatif (la limite haute de l'OS, en terme d'adresses). Pour cela, on va implanter un registre limite dans le processeur : ce registre contient l'adresse à partir de laquelle un programme applicatif est stocké en mémoire.
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 au contenu du 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.
Multi-programmation
Vous avez sûrement déjà remarqué que vous pouvez parfaitement lancer plusieurs programmes en même temps sur votre ordinateur. Par exemple, vous pouvez télécharger quelque chose grâce à Firefox et regarder une vidéo en même temps sans que cela pose problème. C'est parce que votre système d'exploitation peut exécuter plusieurs programmes en même temps sur le même ordinateur. On dit qu'il est multitâches.
Permettre à plusieurs programmes de s’exécuter « en même temps » sur un ordinateur porte un nom : la multiprogrammation. Au départ, la multiprogrammation a été inventée pour masquer la lenteur des périphériques. Si un programme doit attendre une donnée en provenance d'un périphérique, on peut exécuter un autre programme durant ce temps d'attente.
Mais l'apparition de la multiprogrammation a posé de nombreux problèmes, notamment au niveau du partage de la mémoire, car sur les premiers OS qui utilisaient la multiprogrammation, les différents programmes devaient se partager la mémoire physique. Chaque programme recevait donc un bloc de mémoire RAM pour lui tout seul (dans ce qui va suivre, nous allons appeler ces blocs des partitions mémoire).
Gestion 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 savoir quelles sont les portions de la mémoire inutilisées. Et cela peut se faire de deux manières.
Table de bits
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. Cela prend à peine un bit par bloc : 0 pour un bloc occupé et 1 pour un bloc libre. L'ensemble des bits associé à chaque bloc 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. Mais la recherche d'un segment libre demande de parcourir le tableau de bit du début à la fin (en s’arrêtant quand on trouve un segment suffisant), or il s'agit d'une opération très lente.
Liste des partitions libres
Une autre méthode consiste à conserver une liste chainée des partitions mémoire. 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.
Il est aussi possible d'utiliser deux listes séparées pour les trous et les programmes, mais cela complexifie fortement le programme utilisé pour gérer ces listes. On peut aussi en profiter pour trier 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, certains algorithmes de sélection du segment seront alors plus rapides.
Choix de la partition
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é.
Si on choisit mal la partition, on peut obtenir un phénomène de fragmentation externe, c'est-à-dire que l'on dispose de suffisamment de mémoire libre, mais que celle-ci est dispersée dans beaucoup de petits segments vides qui peuvent difficilement stocker une partition à eux tous seuls. Si aucun bloc de mémoire vide n'est suffisamment gros pour combler une demande d'un programme, le système d'exploitation va devoir déplacer les partitions pour les compacter et créer des espaces vides plus gros. En clair, il va devoir déplacer des segments entiers dans la mémoire, ce qui prend beaucoup de temps inutilement.
Algorithme de la première zone libre
La solution la plus simple est de placer le programme dans la première partition capable de l’accueillir. Si le programme n'utilise pas tout le segment, on découpe la partition de manière à en créer une pour la zone non-occupée par le programme lancé.
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.
Algorithme du meilleur ajustement
On pourrait penser que quitte à choisir un bloc, autant prendre celui qui contient juste ce qu'il faut de mémoire. Cette méthode demande de parcourir toute la liste avant de faire un choix, ce qui rend la recherche plus longue. Avec une liste de trous triée par taille, cet algorithme est particulièrement rapide. Mais bizarrement, cette méthode laisse beaucoup de partition trop petites pour être utilisables. En effet, il est rare que les programmes utilisent toute la partition attribuée et laissent souvent du « rab » ce qui fait que la fragmentation externe devient alors importante.
Algorithme du plus grand segment
Pour éviter le problème décrit plus haut, on peut procéder de manière à ce que les partitions laissée lors de l'allocation soient les plus grosses possibles pour augmenter leurs possibilités de réutilisation. L'algorithme utilisé consiste donc à choisir le plus grand segment libre capable d’accueillir le programme lancé. Avec une liste de partitions triée par taille, cet algorithme est particulièrement rapide.
Protection mémoire
Second problème : comment éviter qu'un programme aille modifier les données d'un autre programme ? Pour cela, l'OS doit vérifier que les accès mémoire d'un programme restent bien dans sa partition. Pour cela, il faut vérifier les débordements par le haut et par le bas, ce qui peut être fait de deux manières.
Registres de base et limite
La première solution utilise deux registres :
- un registre de base ;
- et un registre limite.
Le registre de base stocke l'adresse à laquelle commence la partition et le registre limite conserve l'adresse à laquelle elle se termine. Une implémentation naïve de la protection mémoire consiste à vérifier pour chaque accès mémoire que l'adresse à laquelle le programme veut lire est bien située dans l'intervalle délimité par le registre de base et le registre limite.
Protection keys
Toutefois, il existe une autre solution : attribuer à chaque programme une clé de protection, qui consiste en un nombre unique (chaque programme a donc une clé différente de ses collègues). La mémoire est fragmentée en blocs de même taille, généralement de 4 kibioctets et 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.
Relocation
Chaque partition n'a pas une adresse de base fixe, celle-ci dépendant des allocations précédentes. Or, chaque accès à une donnée, chaque branchement, chaque instruction est localisée en mémoire et vouloir y accéder signifie accéder à la bonne adresse. Un programme doit donc connaitre celle-ci dès sa conception. Pour cela, le compilateur considère que le programme commence à l'adresse zéro et laisse l'OS corriger les adresses du programme en fonction de la première adresse de sa partition : il suffit d’additionner cette adresse de début aux adresses manipulées par le programme. Il existe deux grandes méthodes pour faire cette simple addition : la relocation et le position indépendant code.
Relocation
Avec la relocation, la correction est réalisée au lancement du programme par l'OS. Dans d'autres cas, la relocation peut être réalisée automatiquement par le processeur : il suffit d'additionner l'adresse à lire ou écrire avec le registre de base, pour obtenir l'adresse réelle de la donnée ou de l'instruction dans la mémoire.
Position indépendant code
Le position indépendant code 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 linkers. Mais je passe ce genre de détails sous silence, nous sommes dans un tutoriel sur les OS et non dans un tutoriel sur les linkers et les assembleurs.
Allocation mémoire
Utiliser des partitions mémoire permet d'implémenter ce que l'on appelle l'allocation mémoire : le programme pourra demander à l'OS d'agrandir ou rétrécir sa partition mémoire suivant les besoins. Si notre 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 libérer celle-ci et la rendre à l'OS. 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 en mémoire. Ces programmes vont alors régulièrement avoir besoin de mémoire et vont prendre de la mémoire. Imaginez qu'un programme ait tellement grossit qu'on en arrive à la situation suivante :
Imaginez maintenant que le programme n° 1 ait besoin de plus de mémoire, que se passe-il ?
Je suppose que vous voyez bien qu'il y a un problème : il n'y a 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é.
Mémoire virtuelle
Avec la mémoire virtuelle, tout se passe comme si notre programme était seul au monde et pouvait lire et écrire à toutes les adresses disponibles à partir de l'adresse zéro. Chaque programme a accès à autant d'adresses que ce que le processeur peut gérer. Dès lors, on se moque du fait que des adresses sont réservées aux périphériques, de la quantité de mémoire réellement installée sur l'ordinateur ou de la mémoire prise par d'autres programmes en cours d’exécution. Pour éviter que ce surplus de fausse mémoire pose problème, on utilise une partie des mémoires de masse (disque durs) d'un ordinateur en remplacement de la mémoire physique manquante.
Bien sûr, les adresses de cette fausse mémoire vue par le programme sont des adresses fictives qui devront être traduites en adresses mémoire réelles pour être utilisées. Les fausses adresses sont ce qu'on appelle des adresses logiques qui seront les adresses manipulées par notre programme. Par contre, les adresses réelles seront ce qu'on appelle des adresses physiques.
Pour implémenter cette technique, il faut rajouter un circuit qui traduit les adresses logiques en adresses physiques : ce circuit est appelé la Memory Management Unit. Il faut préciser qu'il existe différentes méthodes pour gérer ces adresses logiques et les transformer en adresses physiques : les principales sont la segmentation et la pagination. La suite du tutoriel va détailler ces deux techniques et quelques autres.
Segmentation
La segmentation consiste à découper la mémoire virtuelle (la fausse mémoire vue par un programme) en blocs de mémoire de taille variable qu'on appelle segments. Pour donner un aperçu de la technique de segmentation, je vais prendre l'exemple de la segmentation sur les processeurs x86. La mémoire virtuelle est découpée en $2^{16}$ segments de $2^{32}$ bits, les adresses font 48 bits. Pour identifier un segment, seuls les 16 bits de poids forts de l'adresse 48 bits sont utiles : ils forment ce qu'on appelle un sélecteur de segment. Les 32 bits servent à identifier la position de la donnée dans un segment et sont appelés l'offset.
Relocation
Chaque segment peut être placé n'importe où en mémoire physique.
Effectuer la relocation demande de connaitre l'adresse de base de chaque segment. Cette correspondance segment-adresse de base est stockée dans une table de correspondance en mémoire RAM ou dans des registres du processeur.
Cette table de correspondance est unique pour chaque programme : la même adresse logique ne donnera pas la même adresse physique selon le programme. Vu que les tables des segments sont différentes pour chaque programme, il faut pouvoir mettre à jour le contenu des registres qui mémorisent la table des segments. Cette opération est réalisée lors d'un changement de contexte par l'OS.
Mais il y a moyen de faire plus simple. Quand on accède à un segment, on peut être sur que notre processeur va effectuer un grand nombre d'accès dans ce segment avant d'en changer : on peut éviter d'avoir à préciser le sélecteur à chaque fois. Au lieu d'utiliser une table de correspondance, on mémorise l'adresse physique du segment en cours de traitement dans un registre, le registre de base. Tous les accès mémoire suivants utiliseront cette adresse et n'auront pas à préciser le sélecteur de segment.
Protection mémoire
La segmentation permet aussi d'interdire certaines manipulations dangereuses sur la mémoire et de garantir la protection mémoire. La première méthode consiste à tester les accès hors-segment : si jamais l'accès mémoire se fait à une adresse en-dehors du segment en cours de traitement, le processeur lève alors une exception matérielle qui est traitée par le système d'exploitation de l'ordinateur.
Pour effectuer cette vérification, la MMU doit comparer l'adresse de fin du segment et l'adresse à laquelle on veut accéder. Une autre solution demande de comparer l'offset avec la longueur du segment. Pour cela, la MMU doit se souvenir de l'adresse de fin de chaque segment ou de sa longueur, cette information étant placée dans la table des segments.
Vient ensuite la gestion des droits d'accès : chaque segment se voit attribuer un certain nombre d'autorisations d'accès qui indiquent si l'on peut lire ou écrire dans un segment, si celui-ci contient des données ou des instructions, etc. Ces informations sont rassemblées, avec les adresses et d'autres informations sur les segments, dans ce qu'on appelle un descripteur de segment. Pour se simplifier la tâche, les concepteurs de processeurs et de systèmes d'exploitation ont décidé de regrouper ces descripteurs dans une portion de la mémoire, spécialement réservée pour l'occasion : la table des descripteurs de segment.
Pagination
De nos jours, la segmentation est obsolète et n'est plus utilisée. À la place, les OS et processeurs utilisent la pagination. Avec la pagination, la mémoire virtuelle et la mémoire physique sont découpées en blocs de taille fixe (contrairement aux segments de tailles variables) : ces blocs sont appelés des pages mémoires. Toute page de la mémoire virtuelle peut être placée dans n'importe quelle page de la mémoire physique : une page en mémoire physique correspond à une page en mémoire virtuelle. La taille des pages varie suivant le processeur et le système d'exploitation et tourne souvent autour de 4 kibioctets.
Translation d'adresse
Par contre, le contenu d'une page en mémoire fictive est rigoureusement le même que le contenu de la page correspondante en mémoire physique : on peut ainsi localiser une donnée par sa position dans la page. Une adresse (logique ou physique) se décompose donc en deux parties : un numéro de page qui identifie la page et une autre permettant de localiser la donnée dans la page. Traduire l'adresse logique en adresse physique demande juste de remplacer le numéro de la page logique en un numéro de page physique.
Pour faire cette traduction, il faut se souvenir des correspondances entre numéro de page et adresse de la page en mémoire fictive. Dans le cas le plus simple, ces correspondances sont stockées dans une sorte de table, nommée la table des pages. Ainsi, pour chaque numéro (ou chaque adresse) de page logique, on stocke l'adresse de base de la page correspondante en mémoire physique. La table des pages est unique pour chaque programme vu que les correspondances entre adresses physiques et logiques ne sont pas les mêmes. Cette table des pages est souvent stockée dans la mémoire RAM, à un endroit bien précis connu du processeur.
Mais la technique précédente a un léger défaut : la table des pages bouffe beaucoup de mémoire. Pour éviter cela, les concepteurs de processeurs et de systèmes d'exploitation ont remarqué que les adresses les plus hautes et/ou les plus basses sont les plus utilisées, alors que les adresses situées au milieu de l'espace d'adressage sont peu utilisées en raison du fonctionnement de la pile et du tas. Ainsi, les concepteurs d'OS ont décidés de découper l'espace d'adressage en plusieurs sous-espace d'adressage de taille identique qui ont tous leur propre table des pages. Si un sous-espace d'adressage n'est pas utilisé, il n'y a pas besoin d'utiliser de la mémoire pour stocker sa table des pages associée .
Sur certains systèmes, la taille d'une table des pages serait beaucoup trop grande en utilisant les techniques vues au-dessus. Pour éviter cela, on a inventé les tables des pages inversées. Elles se basent sur le fait que la mémoire physique réellement présente sur l'ordinateur est souvent plus petite que la mémoire virtuelle. Pour faciliter le processus de recherche dans la table, les concepteurs de système d'exploitation peuvent stocker celle-ci avec ce que l'on appelle une table de hachage.
Remplacement des pages mémoires
La mémoire physique contient moins de pages que la mémoire fictive et il faut trouver un moyen pour que cela ne pose pas de problème. La solution consiste à utiliser des mémoires de stockage comme mémoire d'appoint. Si on a besoin de plus de pages mémoire que la mémoire physique n'en contient, certaines pages mémoire vont être déplacées sur le disque dur pour faire de la place.
Les pages localisées sur le disque dur doivent néanmoins être chargées en RAM avant d'être utilisables. Lorsque l'on veut traduire l'adresse logique d'une page mémoire déplacée sur le disque dur, la MMU ne va pas pouvoir associer l'adresse logique à une adresse en mémoire RAM. Elle va alors lever une exception matérielle dont la routine rapatriera la page en mémoire RAM.
Charger une page en RAM ne pose aucun problème tant qu'il existe de la RAM disponible : on peut charger la donnée dans une page inoccupée. Mais si toute la RAM est pleine, il faut déplacer une page mémoire en RAM sur le disque dur pour faire de la place. Tout cela est effectué par la fameuse routine du système d'exploitation dont j'ai parlé plus haut.
Il existe différents algorithmes qui permettent de décider quelle page supprimer de la RAM. Ces algorithmes ont une importance capitale en terme de performance : si on supprime une donnée dont on aura besoin dans le futur, il faudra recharger celle-ci, ce qui prend du temps. Pour éviter cela, le choix de la page doit être fait avec le plus grand soin.
Voici une liste non exhaustive de ces algorithmes :
- Aléatoire : on choisit la page au hasard.
- FIFO : on supprime la donnée qui a été chargée dans la mémoire avant toute les autres.
- LRU : on supprime la donnée qui été lue ou écrite pour la dernière fois avant toute les autres.
- LFU : on vire la page qui est lue ou écrite le moins souvent comparé aux autres.
- etc.
Ces algorithmes ont chacun deux variantes : une locale et une globale. Avec la version locale, la page qui va être rapatriée sur le disque dur est une page réservée au programme qui est la cause du manque de pages libres. Avec la version globale, le système d'exploitation va choisir la page à virer parmi toutes les pages présentes en mémoire vive.
Sur la majorité des systèmes d'exploitation, il est possible d'interdire le déplacement de certaines pages sur le disque dur. Ces pages restent alors en mémoire RAM durant un temps plus ou moins long, parfois en permanence. Cette possibilité simplifie la vie des programmeurs qui conçoivent des systèmes d'exploitation : essayez donc d'exécuter une interruption alors que la page contenant son code est placée sur le disque dur. 
Protection mémoire
Avec la pagination, chaque page a des droits d'accès : on peut autoriser ou interdire la lecture ou l'écriture, voir l’exécution du contenu d'une page. Pour cela, il suffit de rajouter des bits dans la table des pages pour mémoriser ces autorisations. Suivant la valeur de ces bits, la page sera accessible ou non.
De plus, chaque page est attribuée à un programme en particulier puisqu'un programme n'a pas besoin d’accéder aux données d'une page réservée à un autre. Autant limiter les erreurs potentielles en spécifiant à quel programme appartient une page. Pour cela, des bits permettant d’identifier le programme possesseur de la page sont ajoutés en plus des adresses et des bits de gestion des droits d'accès en lecture/écriture dans la table des pages.