Gestion mémoire

Programmation modulaire

Le chargement des programmes est l'assemblage de modules (programme, bibliothèques). Le calcul des adresses mémoire se fait de deux façons :

• le chargement absolu, où les adresses sont fixées par le programmeur, le compilateur ou l'assembleur ;
• le chargement dynamique, où des adresses relatives sont résolues au chargement ou à l'exécution.

Pour cela, on utilise l'édition de liens, c'est-à-dire l'utilisation de "symboles" pour référencer des adresses inconnues. Les références non résolues provoquent le chargement d'autres modules. Cela permet de mettre à jour des modules sans recompiler.

Comment stocker les adresses si on peut charger à différents endroits ? Les adresses absolues sont simples à gérer mais imposent un emplacement du code en mémoire, et donc un seul programme en mémoire ou une mémoire virtuelle. Les adresses relatives sont ajustées plus tard, au chargement ou à l'exécution (édition de liens entre modules, fixer les adresses à l'intérieur des modules).

Dans le code indépendant de la position (PIC), on utilise uniquement des adresses relatives : il est facile à charger, sans besoin de modifier le code, et peu coûteux en temps.

Mémoire virtuelle

Nous souhaitons que chaque processus voie un espace linéaire. Cependant, cet espace n'est pas forcément contigu physiquement et n'est pas forcément utilisé intégralement. Nous souhaitons aussi que sa taille ne soit pas limitée par la mémoire physique, et pouvoir protéger et partager la mémoire.

L'intérêt de la mémoire virtuelle est de nous offrir plus de mémoire que la mémoire physique disponible. Le code et les données non utilisés peuvent donc rester sur le disque (chargés par l'OS quand ils deviennent nécessaires). Elle permet aussi de faire cohabiter de nombreux processus, mais surtout d'isoler les processus, puisque l'espace virtuel des autres processus est inaccessible.

Cette abstraction n'entraîne pas de contraintes pour le programmeur, puisqu'elle offre une vue linéaire et uniforme, indépendante du stockage physique.

En revanche, la mémoire virtuelle possède des inconvénients de performance : on consomme de l'espace mémoire pour stocker les tables de pages, et du temps pour consulter la table des pages.

Pagination

La pagination permet une forte non-contiguïté de l'espace virtuel en mémoire physique. La mémoire physique est divisée en blocs de taille fixe, et l'espace virtuel en blocs de même taille. Chaque cadre virtuel nécessite l'allocation d'une page physique.

L'association entre les pages et les cadres est gérée par l'OS (table de pages), il n'y a pas de contrainte sur le choix des pages (les espaces virtuels sont dispersés dans l'espace physique). Sauf partage explicite, aucune adresse virtuelle ne pointe sur les pages des autres processus.

Une adresse virtuelle se décompose en un numéro de cadre virtuel et un décalage dans la page. Ce numéro est l'index dans la table des pages et permet de récupérer le numéro de page physique. L'adresse physique est alors obtenue en concaténant le PFN (page frame number) et le décalage (soit PFN × taille de page + décalage).

Chaque cadre virtuel dispose de bits de protection : un bit permet de dire si la page est valide ou non (seg fault), un bit permet de dire si la page est présente ou non (défauts de page, swap ...). En fonction de l'architecture il peut y avoir des bits de lecture seule, lecture-écriture, exécution, etc.

Les avantages de la pagination sont multiples : l'allocation de pages est facile, le swap de morceaux de programmes aussi (tous les cadres virtuels ont la même taille, un bit de présence est utilisé pour savoir si swappé ou non). Le partage et la protection des pages est facile.

En revanche, cela implique une fragmentation interne (au plus une page par zone allouée), un surcoût en temps (2 références mémoire par accès sans TLB) et une consommation de mémoire importante pour les tables.

Segmentation

Cela consiste à partitionner la mémoire en unités logiques (code, tas, pile). L'espace d'adressage est alors défini par l'ensemble des segments indépendants. Les adresses virtuelles sont alors composées du sélecteur de segment plus du décalage dans ce segment. Cela permet de mettre en place une protection par segment et un partage à forte granularité. Cependant, l'allocation est difficile (segments de taille variable, fragmentation externe) et le swap est plus lourd qu'avec la pagination.

Approches hybrides : Segments paginés

Nous utilisons des segments pour distinguer des unités logiques (code, tas, pile) et une pagination interne à chaque segment (allocation, swap à granularité fine). La traduction d'une adresse virtuelle en adresse physique se fait en deux temps :

• Sélecteur de segment et décalage traduits via la table des segments en une adresse linéaire
• Traduction de l'adresse linéaire en adresse physique via la table des pages.

Partage mémoire

Plusieurs zones virtuelles peuvent pointer sur les mêmes pages physiques avec des protections différentes. Il existe un compteur de références dans les pages, la page est libre quand la dernière référence est relâchée. On peut alors la réutiliser.

Tables de pages

La table des pages est définie par l'ensemble des associations entre les cadres virtuels et leurs informations de validité, de localisation et de protection. Elle est accédée quasiment uniquement par adresse virtuelle. La table des pages complète prend beaucoup de place en mémoire (4 Mo pour un espace de 32 bits avec des pages de 4 Ko et des entrées de 4 octets).

Une grande part de l'espace d'adressage n'est pas utilisée, car elle n'est pas valide ou valide mais actuellement inutilisée. Doit-on vraiment décrire toutes ces pages virtuelles inutiles individuellement ?

L'idée est d'utiliser des tables hiérarchiques à plusieurs niveaux, chaque niveau est un tableau d'indirection vers des sous-tableaux. Cela permet de supprimer les tableaux inutiles (au lieu d'allouer un tableau d'entrées invalides, on marque le pointeur du père comme invalide).

Si un processus n'utilise qu'un seul cadre virtuel alors on alloue une seule page par niveau. Si un processus utilise toute la mémoire virtuelle alors le dernier niveau fait exactement la même taille qu'une table linéaire à 1 seul niveau (le surcoût des niveaux supérieurs est négligeable, de l'ordre de 1 / nombre de pointeurs par niveau).

Les processeurs supportent de 2 à 5 niveaux (4 ou 5 sur x86-64), et l'OS les utilise comme il veut.

Une adresse virtuelle est la concaténation des index de chaque niveau (les premiers bits donnent l'entrée dans la table du premier niveau, etc.) et du décalage. L'OS choisit le nombre de bits en faisant tenir la table et chaque sous-table dans une page exactement. La traduction des adresses virtuelles en adresses physiques se fait via le parcours de la table de haut en bas.

Concernant les tables de pages hachées, on réalise le hachage de l'adresse virtuelle, puis le parcours d'une liste pour localiser la PTE (Page Table Entry). Cela est efficace pour les espaces d'adressage très dispersés, lent pour les espaces remplis.

Bilan

• Table linéaire originale : très simple, bon temps d'accès, très mauvais en espace mémoire
• Table hiérarchique : assez simple, bon temps d'accès, très bon en espace mémoire
• Table hachée : relativement simple, temps d'accès bon en moyenne, très très bon en espace mémoire

Pagination à la demande et défauts de page

L'OS peut souvent être paresseux (ne pas charger une page en mémoire tant qu'elle n'est pas accédée) : cela implique un défaut de page lors du premier accès, qui entraîne l'allocation et le remplissage de la page (reprise sur erreur).

On utilise aussi la pagination à la demande (demand paging) puisque la mémoire n'est qu'un cache des données manipulées par le processus. Initialement, tout est sur le disque ; ensuite, on charge ce qui est accédé quand c'est nécessaire.

Un défaut de page est un accès qui ne peut être réalisé par le matériel (le processeur ne peut pas le faire) et demande l'aide de l'OS (adresse virtuelle invalide, adresse valide mais page absente en mémoire physique, adresse valide mais écriture interdite).

L'OS a défini un traitant pour l'exception "défaut de page". Le traitant va alors identifier le problème, le réparer si cela est possible (chargement d'une page depuis le disque) sinon le processus ne peut pas continuer.

L'allocation de pages se fait via l'OS, il dispose d'une liste de pages libres. Si la liste est vide, il faut libérer une page (sinon il y a une erreur).

Pour charger une page lors d'un défaut nous allons d'une part récupérer une page libre et d'autre part localiser les données à charger. Il suffit ensuite de soumettre l'I/O de lecture depuis le disque. Lorsque l'I/O termine il suffit d'adapter le statut de la page et reprendre le processus.

La pagination à la demande est efficace grâce aux propriétés suivantes :

• Localité temporelle : une page accédée récemment le sera sûrement à nouveau dans le futur proche
• Localité spatiale : les zones mémoire voisines seront sûrement accédées dans le futur proche
• Une page chargée va être réutilisée plusieurs fois
• En moyenne, on utilise beaucoup les choses déjà chargées
• Ne pas charger trop de choses inutilement

En revanche certaines applications ne respectent pas vraiment la localité spatiale ou temporelle, les politiques de chargement et remplacement doivent être bonnes.

Projection de fichiers

Sous Unix, « tout est fichier » : l'OS manipule essentiellement des pages de fichiers. Nous pouvons réaliser une projection publique (partagée, MAP_SHARED), où les modifications effectuées en mémoire sont répercutées dans le fichier, ou une projection privée (MAP_PRIVATE), où les modifications sont faites sur une copie propre au processus (éventuellement placée dans le swap) et sont perdues à la fin du processus.

La projection anonyme est une projection sans fichier de support. Elle sert pour la pile et le tas, et malloc l'utilise pour les grosses allocations en dehors du tas. Elle peut être privée ou publique.

Copy-on-Write

Les copies mémoire coûtent cher, il faut éviter de dupliquer inutilement et retarder la duplication au maximum, jusqu'à la première modification (par exemple après un fork()). Pour détecter cette modification, la page partagée est mise en lecture seule dans le matériel, et une écriture provoque un défaut de page. Le traitant alloue une page, copie le contenu dedans et la donne au processus.

Le swap

Le swap est une extension de la mémoire physique sur disque. Il est plus lent, n'a pas besoin d'être adressable par le processeur et est entièrement géré par l'OS.

Historiquement on swappait des processus entiers ce qui provoque la suspension complète de l'exécution. La pagination permet la granularité de la page. Un processus gigantesque peut continuer à s'exécuter en résidant essentiellement dans le swap.

Les PTE valides mais non présentes peuvent pointer vers un bloc du swap. Un accès provoque un défaut de page et le chargement du bloc en mémoire. L'OS décide de quelles pages envoyer sur le disque (selon le principe de localité).

Le swap sert uniquement quand il faut libérer de la mémoire physique. Seules les pages privées et/ou anonymes vont dans le swap (la libération des pages de projections publiques les renvoie dans le fichier correspondant).

Heuristiques de gestion mémoire

Le chargement des pages se fait quand elles sont accédées lors du défaut de page. Le prepaging et le prefaulting permettent de charger à l'avance des pages suivantes (principe de localité). Le chargement s'effectue généralement dans n'importe quelle page physique. Lorsque l'on utilise une architecture NUMA on privilégie généralement l'utilisation de mémoire proche.

Les pages modifiées sont sauvegardées dans les fichiers correspondants ou dans le swap. Les pages projetées sont difficiles à gérer, car il n'y a pas d'appel explicite à l'OS lors des modifications : le matériel positionne alors un bit Dirty, et l'on ne sauvegarde que les pages Dirty.

Concernant le swap, l'idéal serait d'évincer la page qui sera utilisée le plus tard (algorithme optimal de Belady), ce qui est irréalisable puisqu'il faut connaître le futur : on l'approche avec la politique LRU (Least Recently Used) ou LFU (Least Frequently Used). Le swap se produit soit au dernier moment, soit quand la mémoire disponible passe en dessous d'un seuil.

On conserve en mémoire le plus de choses possibles car elle est rapide au cas où cela serve plus tard. On effectue des sauvegardes régulières des modifications sans forcément libérer les pages. En régime permanent, un OS utilise toute la mémoire, au cas où. Les pages publiques sont gardées en mémoire si un processus les réutilise et les pages privées jusqu'à la fin du processus courant.

Si une allocation mémoire échoue le système doit tout de même survivre. L'utilisateur doit pouvoir continuer à utiliser le système (tuer un processus pour libérer de la mémoire). Pour déterminer qui tuer plusieurs politiques existent, tuer ceux qui essaient d'allouer, ceux qui allouent beaucoup ou les processus les moins importants.

Support matériel

Le code manipule uniquement des adresses virtuelles mais le processeur doit les traduire en adresse physique. Il faut que la table des pages soit accessible au matériel (soit directement par une MMU, soit indirectement par l'OS via une exception).

La MMU (Memory Management Unit) est un circuit dédié du processeur pour traduire les adresses virtuelles. Cependant, la traduction des adresses virtuelles peut être lente : il est donc nécessaire de mettre en cache les traductions dans le TLB (Translation Lookaside Buffer). En cas d'échec dans le TLB :

• si le parcours de la table est matériel, la MMU parcourt la table des pages (x86) ;
• si le TLB est géré par logiciel (par exemple MIPS), une exception est levée et gérée par l'OS.

Mémoire du noyau

L'espace d'adressage utilisé par le noyau se divise en deux parties. D'une part, il existe un espace virtuel spécifique au noyau accessible uniquement en mode privilégié ; d'autre part, l'espace virtuel utilisateur du processus courant utilisé pendant un appel système ou une interruption.

Le noyau est un contexte d'exécution et a potentiellement le droit d'accéder à tout ce qui possède une adresse virtuelle. Cependant, il n'a réellement besoin que de son propre code et de ses données propres pour fonctionner (10-100 Mo). Le noyau ne mappe rien par défaut à part le strict minimum.