Gestion mémoire

Programmation modulaire

Le chargement des programmes est l'assemblage de modules (programme, bibliothèques). Le calcul des adresses mémoires se fait via deux moyens :

• le chargement absolu par le programmeur, le compilateur ou l'assembleur
• le chargement dynamique qui sont des adresses relatives calculées à l'exécution

Pour cela on utilse de 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 des 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 impose un seul programme ou 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).

Le code est indépendant de la position, on utilise uniquement des adresses relatives (facile à charger, pas besoin de modifier le code, peu coûteux en temps)

Mémoire virtuelle

Nous souhaitons que chaque processus voit un espace linéaire. Cependant il n'est pas forcément linéaire physiquement et n'est pas forcément utilisé intégralement. Nous souhaitons aussi que la taille ne soit pas limité par la mémoire physique ainsi que 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 de mémoire physique disponible. Les codes et données non-utilisées peuvent donc rester sur le disque (chargés par l'OS quand ils deviennent nécessaires). Elle permet aussi de faire cohabiter de nombreux processsus mais surtout d'isoler des processus puisque l'espace virtuel des autres processsus est inaccessible.

Cette abstraction n'entraine pas de contraintes pour le programmeur puisque l'abstraction est linéaire et uniforme du stockage physique.

En revanche la mémoire virtuelle possède des inconvénients, en effet le premier est un inconvénient de performance puisque l'on consomme de l'espace mémoire pour stocker des tables de pages mais aussi de la consommation en temps pour consulter la table des pages.

Pagination

Permet une forte non-contiguité de l'espace virtuel en mémoire physique. Il y a une division de la mémoire physique en bloc de taille fixe et la division de l'espace virtuel en blocs de tailles fixes. 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 dispersés dans l'espace physique). Aucune adresse virtuelle ne pointe sur les pages de autres processus.

La traduction des adresses virtuelles équivaut au numéro du cadre virtuel plus le décalage. Ce numéro est l'index dans le table de page et permet de récupérer le numéro de page physique. L'adresse physique est alors égale au PFN (page frame number) plus le décalage.

Chaque cadre virtuel dispose de bits de protections, 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 read-only, read-write etc

Les avantages de la pagination sont multiples, l'allocation de pages est faciles, 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 (de l'ordre de la taille d'une page), cela est coûteux (2 références par accès mémoire) et implique une consommation de mémoire importante.

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é 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 et le swap est plus lourd que lors de 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 est en deux temps

• Décalage d'index dans la table de pages via la table des segments : 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 de page est défini par l'ensemble des associations entre les cadres virtuels et la validité, la localisation et la protection. Elle est accédé quasiquement uniquement par adresse virtuelle. La table des pages complète prend beaucoup de place en mémoire (4MB pour un espace 32 bits avec pages de 4Ko).

Une grande part de l'espace d'adressage n'est pas utilisé car il n'est pas valide ou valide mais inutilisé actuellement. Ainsi 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 (surcoût des niveaux supérieurs est négligeable de l'ordre de 1/ nombre de pointeurs par niveau).

Les processeurs supportent 2 à 4 niveaux et l'OS les utilise comme il veut.

Les adresses virtuelles sont égales à l'agréagation d'index pour chaque niveau. (premiers bits est l'entrée dans la table du premier niveau etc). 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 physique se fait via le parcours de la table de haut en bas.

Concernant les tables de pages hachées, on réalise l'hachage de l'adresse virtuelle puis un parcours d'une liste pour localise la PTE. 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 fainéant (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, entre temps, 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 par 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 possède les avantages suivants :

• 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

Dans un OS tout est fichier. L'OS ne fait que manipuler des pages de fichiers. Nous pouvons réaliser une projection publique où les modifications effectuées en mémoire sont répercutées dans le fichier. Ou une projection privée où les modifications sont sauvées dans le swap et sont perdues à la fin du processus.

La projection anonyme est une projection sans fichier de support. Il utilise la pile ou le tas et est utilisé par malloc pour les allocations en dehors du tas. Il peut être privé ou public.

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 concurrente. Pour détecter une modification concurrent la page est mise en lecture seule dans le matériel et provoquer 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. Elle est plus lente et n'a pas besoin d'être déréférencable 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érations des pages de mappings publics les renvoit sur le disque contenant 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 prefaulting permet 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 modifications sont sauvées sur les pages modifiées dans des fichiers correspondants ou dans le swap. Les pages mappées sont difficiles à gérer, il n'y a pas dappel explicite à l'OS lors des modifications. Le matériel ajoute alors un bit Dirty et l'on sauve uniquement les pages Dirty.

Concernant le swap nous allons swaper les pages non-utilisées à l'avenir (algorithme de Belady) en utilisant la politique LRU (Least Recentyle 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ère 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 essaie 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 cricuit dédié du processeur pour traduire les adresses virtuelles. Cependant la traduction des adresses virtuelles peut être lente. Il est de plus nécessaire de cacher les traductions (Translation Lookaside Buffer). Si le TLB cache miss :

• Si MMU, la MMU parcourt la table des pages
• Si pas de MMU, exception gérée par l'OS.

Mémoire du noyau

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

Le noyau est un contexte d'exécution et à potentiellement le droit d'accéder à tout ce qui possède une adresse virtuelle. Cependant il est réellement besoin 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.