Les systèmes d'exploitation/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.

IO mappées en mémoire

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.

Gestion de la mémoire sur les OS monoprogrammés.

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.

Méthodes d'allocation de la mémoire avec un espace d'adressage unique

Organisation Mémoire des vieux PC, à l'époque du DOS.

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.

Protection mémoire avec un registre limite.

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.

Partitions mémoire

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.

Segmentation et relocation.

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.

Fragmentation externe.

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.