Espaces d’adressage et traduction des adresses

Un programme en cours d’exécution travaille avec un espace d’adressage : sa propre vue de la mémoire, dont les emplacements d’octets sont numérotés. Le système d’exploitation place la mémoire du programme dans la machine et fait en sorte que ses adresses atteignent les bons octets physiques. L’organisation que voit le programme et celle du matériel sont deux choses différentes.

Pourquoi plusieurs programmes restent en mémoire

Les premiers systèmes pouvaient conserver un programme à côté du système d’exploitation. Par exemple, le système d’exploitation pouvait occuper les 64 premiers Ko et le programme le reste de la mémoire. La multiprogrammation gardait plusieurs processus prêts, afin que le processeur puisse travailler pendant qu’un autre processus attendait une entrée ou une sortie. Le partage du temps faisait passer le processeur d’un processus à l’autre assez souvent pour servir les utilisateurs interactifs.

Enregistrer toute la mémoire d’un processus sur disque à chaque changement rendrait la commutation beaucoup trop lente. Conserver plusieurs processus en mémoire physique évite cette copie, mais pose un problème de protection. Une adresse produite par un processus ne doit pas lui permettre d’écraser le système d’exploitation ou un processus voisin.

Les tailles de mémoire suivent ici la convention binaire utilisée dans ces modèles : 1 Ko vaut 1 024 octets, aussi noté 1 Kio ; 1 Mo vaut 1 024 Ko. Un espace d’adressage de 16 Ko possède 16 384 emplacements d’octets, numérotés de 0 à 16 383. Le nombre 16 384 est la borne de fin, pas une adresse d’octet valide.

Code, données, tas et pile

Dans l’organisation classique utilisée pour enseigner un espace de 16 Ko, le code utilise les adresses basses, de 0 jusqu’à la borne de 1 Ko. Le tas commence au-dessus du code et croît vers le haut. La pile commence à la borne supérieure et croît vers le bas. L’espace libre qui les sépare permet aux deux zones de grandir. Les organisations réelles diffèrent ; par exemple, chaque fil d’exécution possède sa propre pile. Les rôles des zones restent utiles même lorsque leurs emplacements changent.

Suivre un pointeur jusqu’à la bonne mémoire

Une adresse virtuelle désigne un octet dans l’espace d’adressage d’un processus. Une adresse physique désigne un octet dans la mémoire matérielle de la machine. Lorsque le code C affiche printf("%p", (void *) &x), il affiche une adresse virtuelle. Le pointeur affiché ne révèle pas l’octet physique qui stocke x.

Supposons que deux processus utilisent tous deux l’adresse virtuelle 1 000. Chaque adresse est interprétée dans l’espace d’adressage de son processus, de sorte que les accès peuvent atteindre des octets physiques différents. De même, du code à l’adresse virtuelle 0 n’occupe pas nécessairement l’adresse physique 0. Le système d’exploitation peut le placer ailleurs et configurer la traduction matérielle pour y accéder.

Le processeur traduit les recherches d’instructions, les lectures et les écritures. Le système d’exploitation choisit et gère les correspondances, notamment en changeant les emplacements physiques tout en conservant les adresses virtuelles du programme.

Un système de gestion mémoire doit faire plus que traduire correctement un nombre. Il doit permettre aux programmes ordinaires de s’exécuter sans gérer leur emplacement physique, maintenir un faible coût de traduction et faire respecter les limites qui rendent le partage sûr. Ces exigences sont la transparence, l’efficacité et la protection.

Préserver la vue du programme

La transparence signifie qu’un programme s’exécute comme s’il disposait d’une mémoire privée. Il utilise ses propres adresses pour le code et les données sans avoir à suivre les autres processus présents ni l’emplacement de leurs octets. Le système d’exploitation et le matériel préservent cette vue en arrière-plan. Le déplacement d’un processus en mémoire physique ne devrait pas obliger le processus à réécrire ses pointeurs.

Cette illusion n’exige pas une copie physique distincte de chaque octet pour chaque processus. Par exemple, du code protégé en lecture seule peut être partagé. L’essentiel est que le partage préserve le comportement et les droits d’accès que chaque processus est en droit d’observer.

Prendre en compte les deux types de coût

Chaque recherche d’instruction, lecture et écriture nécessite une traduction. Exécuter une fonction du système d’exploitation à chaque accès rendrait l’exécution ordinaire trop lente. Le matériel effectue les opérations fréquentes ; le code du système d’exploitation gère la configuration, les changements et les défauts.

L’efficacité en espace compte également. Un mécanisme de traduction petit et rapide peut tout de même gaspiller beaucoup de mémoire. Une zone unique régie par une base et une limite réserve l’espace inutilisé entre le tas et la pile. La segmentation évite d’associer de la mémoire physique à cet espace, mais introduit des zones physiques de tailles variables et des trous entre elles. Les métadonnées, l’espace réservé inutilisé et les trous influent tous sur la quantité de travail utile que la mémoire peut accueillir.

Arrêter un accès interdit à la limite

Sans protection, un pointeur mal orienté dans un éditeur de texte pourrait écraser un autre processus ou le noyau. Les dégâts pourraient apparaître bien plus tard dans du code sans rapport. Lorsque les limites sont imposées, le matériel rejette un accès hors de la zone autorisée et déclenche une exception. Le système d’exploitation traite l’exception et termine généralement le processus fautif, en signalant souvent une erreur de segmentation.

La protection isole les processus les uns des autres. Elle ne garantit pas que l’utilisation de la mémoire en C soit sûre à l’intérieur d’une zone de tas autorisée. Une écriture au-delà d’un bloc alloué peut tout de même atteindre un autre bloc appartenant au même processus. Les limites des processus et celles des blocs de l’allocateur sont distinctes.

Distinguer l’opération du choix

Un mécanisme est la manière dont une opération est effectuée. Ajouter la valeur d’un registre de base et vérifier un registre limite sont des mécanismes. Une politique choisit parmi les actions possibles : où placer un processus, quel trou libre utiliser ou quand déplacer un segment.

Cette séparation permet au système d’exploitation de changer sa stratégie de placement tout en conservant la même traduction matérielle. La virtualisation de la mémoire commence par cette vue privée et protégée ; elle ne se définit pas par l’utilisation du disque comme mémoire supplémentaire.

Une variable pointeur et la mémoire vers laquelle elle pointe sont des objets distincts. Comprendre leurs durées de vie est le point de départ de l’API de gestion mémoire en C. Les variables locales ordinaires utilisent généralement le stockage automatique de la pile, les blocs du tas durent jusqu’à leur libération et les variables globales et locales static disposent d’un stockage pendant toute l’exécution du programme.

Suivre l’allocation, pas seulement le pointeur

void f(void) {
    int x;
    int *p = malloc(sizeof(int));
}

Dans l’organisation habituelle de la pile, x et p appartiennent à cet appel de f. L’entier demandé appartient au tas. Le retour de la fonction supprime la variable pointeur locale ; il ne libère pas le bloc du tas. S’il ne reste aucune copie de l’adresse, le programme a perdu l’accès à un bloc toujours alloué : c’est une fuite de mémoire.

malloc(size) demande au moins ce nombre d’octets et renvoie un pointeur, ou NULL si la demande ne peut pas être satisfaite. Ses octets ne sont pas initialisés pour le programme. Pour 10 entiers, utilise malloc(10 * sizeof(int)) ; là où un entier occupe 4 octets, la demande porte sur 40 octets. Pour une chaîne, réserve de la place pour ses caractères et un octet pour le caractère nul de fin : malloc(strlen(s) + 1).

sizeof(a) mesure l’objet nommé a. Si a est un pointeur, il donne la taille du pointeur, pas celle du bloc alloué. Un pointeur de 8 octets peut désigner un bloc de 40 octets.

Connaître le rôle de chaque opération de bibliothèque

free prend le pointeur renvoyé, sans argument de taille. L’allocateur conserve des métadonnées de taille, généralement dans un en-tête avant le bloc. Transmets le pointeur renvoyé pour un bloc actuellement alloué ; un pointeur vers l’intérieur du bloc ne peut pas le remplacer. free(NULL) est valide et ne fait rien. Ces fonctions appartiennent à la bibliothèque C : ce ne sont pas des appels système.

Reconnaître l’erreur liée à la durée de vie ou à la limite

Un pointeur sans allocation valide ne peut pas être utilisé comme s’il pointait déjà vers une zone de stockage. Lire des octets nouvellement alloués avant de les initialiser est une lecture de données non initialisées. Écrire au-delà de la fin du bloc alloué est un débordement de tampon ; omettre l’octet de fin d’une chaîne peut en provoquer un.

Après free, les anciens pointeurs vers le bloc sont pendants. Accéder au bloc par l’un d’eux est un accès après libération (use-after-free). Libérer de nouveau le bloc est une double libération. Libérer une adresse que l’allocateur n’a pas renvoyée pour un bloc encore alloué est une libération invalide. Une fuite de bloc est différente : le bloc reste alloué, mais le programme ne le libère plus lorsqu’il le devrait.

Comprendre ce que le matériel peut vérifier

La compilation peut réussir malgré toutes ces erreurs. Le matériel vérifie normalement les zones et les permissions du processus, pas chaque allocation de la bibliothèque. Franchir la limite d’un bloc tout en restant dans le tas autorisé du processus peut entraîner un comportement indéfini sans défaut immédiat. Le programme peut corrompre des données, planter plus tard, lire des valeurs sans signification ou sembler fonctionner. Valgrind et AddressSanitizer peuvent détecter beaucoup de ces erreurs pendant l’exécution.

La bibliothèque C et le système d’exploitation gèrent la mémoire à des échelles différentes. Le système d’exploitation établit des zones dans l’espace d’adressage d’un processus et leur fournit de la mémoire physique. L’allocateur divise la mémoire disponible du tas en blocs, répertorie les blocs libres et les réutilise d’un appel à l’autre.

Déplacer la limite du segment de données

La limite du segment de données est l’adresse située juste après la fin du tas traditionnel. brk fixe cette limite à une adresse choisie. sbrk(n) la déplace d’un nombre donné d’octets et, en cas de succès, renvoie l’ancienne limite. sbrk(0) indique la limite actuelle sans la déplacer.

Supposons que la limite soit à 40 960 et que l’allocateur appelle sbrk(8192) avec succès. La valeur renvoyée est 40 960. La nouvelle limite est :

Les octets ajoutés occupent les adresses virtuelles de 40 960 à 49 151. La nouvelle limite, 49 152, se trouve juste après la zone ajoutée. Confondre la valeur renvoyée avec la nouvelle limite décale tous les calculs de placement ultérieurs.

Les applications utilisent la bibliothèque d’allocation au lieu de déplacer directement la limite. La bibliothèque suit les parties de sa zone qu’elle possède. Des modifications indépendantes de cette limite peuvent invalider ses informations de gestion.

Obtenir une projection distincte

mmap peut créer une zone anonyme : une mémoire non liée à un fichier, initialement remplie d’octets nuls. munmap supprime une projection. Un allocateur peut utiliser des projections distinctes pour les allocations importantes et les rendre au système d’exploitation lorsqu’elles sont libérées.

Dans glibc, le seuil initial par défaut pour cette méthode est de 128 Ko, soit 131 072 octets, et il peut être relevé. Une allocation suffisamment grande fait généralement l’objet d’une projection distincte si elle ne peut pas être satisfaite à partir de l’espace libre existant. C’est une politique de bibliothèque, pas une limite universelle du langage C.

Libérer au niveau de la bibliothèque ou du système d’exploitation

Un appel à free remet généralement un petit bloc dans la réserve de la bibliothèque. Le processus peut donc ensuite afficher la même empreinte mémoire. La mémoire peut être réutilisée sans nouvelle demande au système d’exploitation.

La fin d’un processus permet de récupérer même les blocs que le programme a laissés fuir. Pendant la durée de vie d’un serveur de longue durée, des fuites répétées continuent toutefois de consommer sa mémoire disponible. La récupération à la fin du processus n’empêche pas cette pression pendant son exécution.

Relier la croissance du tas à la traduction

Dans le modèle de segmentation, le tas est un segment physique contigu. Pour l’agrandir, il faut des octets physiques libres immédiatement au-dessus. Si ces octets sont occupés, le système d’exploitation peut déplacer le segment vers un trou plus grand et mettre à jour son état de traduction. Si aucune zone adaptée n’est disponible, l’agrandissement échoue. Si l’allocateur ne peut pas obtenir assez d’espace, malloc renvoie NULL.

Le relogement dynamique traduit les adresses pendant l’exécution d’un programme. Dans le modèle de base et de limite, un processus occupe une zone physique contiguë. Commençons par des espaces d’adressage de même taille qui tiennent en mémoire physique ; une paire de registres décrit alors la zone du processus en cours d’exécution.

Vérifier d’abord l’adresse virtuelle

Le registre de base contient l’adresse physique du premier octet de la zone. Le registre limite contient la taille de la zone en octets. Pour une adresse virtuelle positive ou nulle, la règle est :

Si la vérification réussit :

Sinon, le matériel déclenche une exception. Une taille est un nombre d’octets : l’adresse égale à la limite est donc déjà en dehors de la zone. Les adresses virtuelles négatives sont également invalides.

Examiner les limites des octets

Prenons un espace d’adressage de 8 Ko avec une base de 20 480 et une limite de 8 192. Ses octets virtuels vont de 0 à 8 191. L’adresse virtuelle 1 000 réussit la vérification et atteint l’octet physique 21 480. Le dernier octet virtuel autorisé, 8 191, atteint 28 671. L’adresse 9 000 échoue car elle est supérieure ou égale à 8 192 ; le matériel doit la rejeter avant de lancer l’accès physique.

Les recherches d’instructions utilisent la même traduction que les données. Si une instruction à l’adresse virtuelle 128 charge une valeur depuis l’adresse virtuelle 3 000, la recherche atteint l’adresse physique 20 608 et la lecture atteint 23 480. Il s’agit de deux accès à la mémoire avec deux adresses traduites, pas d’une seule traduction pour toute l’instruction.

Bien distinguer les conventions de limite

La même zone de 8 Ko a pour borne physique de fin 28 672. Les deux conventions autorisent exactement les octets de 20 480 à 28 671. Comparer l’adresse physique 21 480 à la taille 8 192 mélange les deux conventions et rejette à tort un accès autorisé.

Déplacer la mémoire sans changer les pointeurs

La MMU, ou unité de gestion mémoire, effectue les vérifications et l’addition. Le système d’exploitation peut mettre un processus en pause, copier sa zone ailleurs et modifier la base. Le processus continue d’utiliser les mêmes adresses virtuelles : c’est pourquoi le relogement est dynamique.

Avec le relogement statique, un chargeur réécrit les adresses intégrées lors du chargement du code. Réécrire une référence de 1 000 en 21 480 inscrit un emplacement physique dans le programme. Un déplacement ultérieur nécessite de nouvelles réécritures, et la seule réécriture n’empêche pas un programme de construire une adresse hors de sa zone.

N’ajoute la base qu’à une adresse virtuelle. L’ajouter à une adresse physique déjà traduite décale l’emplacement une deuxième fois et détruit la correspondance.

Le matériel contient les registres de traduction du processus qui s’exécute sur un processeur. Le système d’exploitation conserve l’état sauvegardé des processus en attente. La protection dépend du fait que seul le code privilégié du système d’exploitation peut modifier cet état.

Fournir les opérations matérielles

Le processeur a besoin des modes utilisateur et noyau, d’une paire de registres de base et de limite dans sa MMU, et de circuits pour la vérification et l’addition. Il lui faut aussi des opérations privilégiées pour modifier la paire et installer les gestionnaires d’exception. Les adresses interdites et les tentatives d’exécution d’instructions privilégiées en mode utilisateur doivent déclencher des exceptions.

Si un programme utilisateur pouvait modifier sa base, il pourrait diriger ses adresses vers le noyau ou un autre processus. Les vérifications de limite protégeraient alors la mauvaise zone. Restreindre les modifications fait donc partie du mécanisme de protection et ne relève pas seulement de la commodité administrative.

Créer et exécuter un processus

Au démarrage, le système d’exploitation installe ses gestionnaires de déroutement et d’exception, démarre l’horloge d’interruption et prépare ses informations sur la mémoire libre. Lorsqu’un processus démarre, le système d’exploitation trouve un emplacement physique pour son espace d’adressage. Si les emplacements ont la même taille, une liste des blocs libres peut simplement indiquer quels emplacements sont inutilisés.

Le système d’exploitation marque l’emplacement choisi comme occupé, enregistre la base et la limite du processus, charge les registres et passe en mode utilisateur. Le processus s’exécute alors directement sur le processeur. Le matériel traduit les accès ordinaires sans appeler le système d’exploitation pour chaque octet.

Restaurer la bonne paire lors d’une commutation de contexte

Une interruption d’horloge transfère le contrôle au système d’exploitation. Celui-ci sauvegarde les registres de l’ancien processus, y compris la base et la limite, dans son bloc de contrôle de processus, puis restaure les valeurs du processus suivant avant de revenir en mode utilisateur.

Supposons que la base de A soit 20 480 et celle de B 40 960, tous deux ayant une limite de 8 192. L’adresse virtuelle 1 000 de A atteint 21 480. Après le passage à B, la même valeur virtuelle atteint 41 960. Restaurer les registres du processeur sans restaurer l’état de traduction ferait accéder B à la zone de A avec les pointeurs de B.

Le processeur possède la paire active ; chaque processus possède sa propre paire sauvegardée. Ne te représente pas une seule paire permanente pour toute la machine et ne suppose pas que les paires de tous les processus sont actives simultanément sur un même processeur.

Déplacer, traiter un défaut et terminer

Pour déplacer A à l’adresse physique 49 152, le système d’exploitation interrompt son exécution, copie sa zone de 8 Ko et met à jour la base sauvegardée de A. Une fois que A reprend avec cette base installée, l’adresse virtuelle 1 000 atteint 50 152. Les valeurs de ses pointeurs virtuels n’ont pas besoin d’être modifiées.

En cas d’accès invalide, le matériel déclenche une exception et transfère l’exécution en mode noyau au gestionnaire enregistré. Le système d’exploitation termine généralement le processus fautif. À sa terminaison, il rend l’emplacement à la liste des blocs libres et libère les informations du processus.

Le mécanisme de base et de limite atteint deux objectifs à faible coût : la traduction est transparente et chaque adresse est vérifiée par rapport à la zone allouée. Son principal point faible tient au rapport entre cette zone et les octets que le processus utilise réellement.

Réserver toute l’étendue

Pour les opérations fréquentes, le matériel n’a besoin que d’une addition et d’une comparaison. Un allocateur d’emplacements de taille fixe peut aussi choisir rapidement un emplacement libre. Aucun de ces avantages ne signifie que l’emplacement est rempli de données utiles.

Dans l’organisation classique, le code et le tas se trouvent près d’une extrémité et la pile près de l’autre. Une paire de registres de base et de limite traduit tout l’intervalle. L’espace inutilisé entre le tas et la pile occupe de la mémoire physique tout comme les parties utiles.

Pour un espace d’adressage de 16 Ko utilisant 1 Ko de code, 2 Ko de tas et 1 Ko de pile :

Ce gaspillage est une fragmentation interne : des octets inutilisés à l’intérieur d’une zone déjà allouée à un processus. Il ne vient pas d’un mauvais choix de bloc par l’allocateur du tas. Même un tas de 2 Ko parfaitement rempli laisse le grand espace central réservé.

Distinguer trois questions de taille

L’étendue de l’espace d’adressage, les octets actuellement utilisés et la mémoire physique disponible sont des quantités différentes. Un espace adressé par octet sur 32 bits s’étend sur $2^{32}$ octets, soit 4 Go. Le réserver sous la forme d’un seul bloc physique exige les 4 Go entiers, même si le processus n’utilise actuellement que quelques mégaoctets.

Donner des tailles variables aux emplacements supprime la contrainte de taille identique, mais pas le besoin d’un trou contigu. Cela crée aussi un problème de placement : le système d’exploitation doit choisir parmi des trous libres de tailles différentes. Réduire un emplacement ne peut pas préserver à la fois les adresses basses du code et l’adresse haute éloignée de la pile si toute l’étendue doit rester valide dans la même correspondance simple.

Reloger les zones séparément

Le code, le tas et la pile n’ont pas besoin d’être voisins en mémoire physique pour préserver la vue du programme. Donner à chacun sa propre base et sa propre limite permet au système d’exploitation de n’allouer que leurs étendues utilisées et de laisser l’espace virtuel intermédiaire sans mémoire physique associée. C’est la segmentation, qui généralise une paire de registres de relogement à plusieurs zones logiques.

Pour l’organisation de 16 Ko ci-dessus, les trois zones utilisées ne nécessitent au total que 4 Ko avant leur propre surcoût de gestion. L’économie d’espace vient du changement de ce qui est relogé comme une unité, pas d’une addition plus rapide du registre de base.

Un segment est une zone contiguë d’un espace d’adressage qui a une fonction précise. Dans le modèle classique, le code, le tas et la pile reçoivent chacun une paire de registres de base et de taille. Leurs zones physiques peuvent être placées indépendamment, même si le processus conserve son organisation virtuelle habituelle.

Associer de la mémoire physique aux seules étendues utilisées

Prenons un espace d’adressage de 16 Ko avec les placements suivants. Les tailles utilisent le Ko binaire, ou Kio.

Le code et le tas croissent vers les adresses plus élevées ; la traduction de la pile utilise sa borne supérieure et un déplacement négatif. Les trois zones physiques n’utilisent au total que 7 Ko. Les espaces virtuels vides entre elles ne nécessitent aucun stockage physique. Chaque segment reste contigu ; ce sont les segments qui n’ont plus besoin d’être adjacents entre eux.

Traduire une adresse d’un segment qui croît vers le haut

Identifie d’abord le segment. Calcule ensuite le déplacement depuis son début virtuel. Vérifie que le déplacement est positif ou nul et inférieur à la taille actuelle du segment, puis ajoute-le à la base physique :

Pour l’adresse virtuelle 500, le déplacement dans le code est de 500. Il est inférieur à 2 048 : l’accès atteint donc l’adresse physique 41 460.

Pour l’adresse virtuelle 5 000, le déplacement dans le tas est :

La vérification de la taille réussit car 904 est inférieur à 3 072. Le résultat est :

Ajouter l’adresse virtuelle entière à la base du tas produirait 31 624. Cette erreur introduit la position virtuelle de début du tas dans un calcul qui ne nécessite que la distance à l’intérieur du segment.

Vérifier le segment, pas seulement l’étendue de l’espace d’adressage

L’adresse virtuelle 7 500 tient toujours sur 14 bits, mais cela ne la rend pas autorisée. Son déplacement dans le tas est de 3 404, au-delà de l’étendue actuelle de 3 072 octets. Le matériel déclenche une exception. Une adresse peut donc se trouver dans l’étendue globale de l’espace d’adressage tout en étant hors de toute zone valide.

Le terme erreur de segmentation vient des accès invalides en mémoire segmentée et reste utilisé pour les accès interdits sur des systèmes employant d’autres mécanismes de traduction. Le seul nom de l’erreur ne permet pas de déterminer le mécanisme de traduction de la machine.

Avant de pouvoir utiliser la base et la taille d’un segment, le matériel doit déterminer quel segment un accès désigne. Dans une conception explicite, ce choix figure dans les bits de l’adresse. Dans une conception implicite, il découle de la manière dont le processeur a formé l’adresse.

Découper une adresse de 14 bits

Attribue les deux bits de poids fort au numéro de segment et les douze bits de poids faible au déplacement. Le champ de deux bits possède quatre valeurs possibles. Utilise 00 pour le code, 01 pour le tas et 11 pour la pile ; laisse 10 inutilisé.

Le champ de déplacement peut représenter 4 096 valeurs différentes, de 0 à 4 095. La plage virtuelle maximale de chaque segment est donc de 4 Ko, même lorsque son étendue valide actuelle est plus petite. La capacité maximale et la taille actuelle sont deux limites différentes.

Pour l’adresse virtuelle 5 000, la représentation sur 14 bits est :

01 0011 1000 1000

Les premiers bits 01 sélectionnent le tas. Les bits restants 0011 1000 1000 valent 904 en décimal. Avec une taille de tas de 3 072 et une base physique de 26 624, le déplacement réussit la vérification de taille et atteint l’adresse physique 27 528.

Utiliser un masque et un décalage

Le même découpage peut être exprimé en code :

segment = (va & 0x3000) >> 12;
offset = va & 0x0FFF;

Le masque 0x3000 conserve les deux bits du sélecteur ; un décalage de douze les amène aux positions de poids faible pour donner le numéro de segment. Le masque 0x0FFF efface ces bits du sélecteur et conserve le déplacement. Pour va = 0x1388, les résultats sont le segment 1 et le déplacement 0x388, soit 904.

N’ajoute pas 0x1388 directement à la base du tas. Cette valeur comprend à la fois le sélecteur de segment et le déplacement. Le sélecteur choisit les registres ; seul le déplacement participe à la traduction à l’intérieur du segment. L’adresse physique obtenue n’a pas besoin de conserver la configuration des bits du sélecteur.

Reconnaître le coût du découpage

Un sélecteur de deux bits crée quatre plages. Laisser 10 inutilisé rend indisponible un quart de l’étendue virtuelle de 16 Ko. Aucun segment ne peut dépasser sa plage de 4 Ko simplement parce que davantage de mémoire physique se libère. D’autres conceptions peuvent utiliser un découpage différent ; réunir le code et le tas dans un segment permet à un seul bit de sélection de le distinguer de la pile.

Laisser plutôt le type d’accès choisir

Dans une conception implicite, les recherches d’instructions utilisent le segment de code car leur adresse vient du compteur ordinal. Les références fondées sur le pointeur de pile ou le pointeur de cadre utilisent le segment de pile. Les autres accès utilisent le segment du tas dans ce modèle simplifié.

La pile croît vers les adresses plus basses. Sa traduction nécessite un bit de sens en plus d’une base et d’une taille. Dans ce modèle, 1 indique une croissance vers le haut et 0 une croissance vers le bas. Les permissions d’accès ajoutent une autre vérification indépendante : un octet peut être dans les limites tout en interdisant l’opération demandée.

Considérer la base de la pile comme une borne supérieure

Pour un segment qui croît vers le haut, la base désigne son premier octet physique. Pour un segment qui croît vers le bas, la base désigne la borne située juste au-dessus de son octet physique le plus élevé. Dans l’organisation de l’exemple, la base de pile 53 248 et la taille 2 048 couvrent les octets physiques de 51 200 à 53 247.

Pour la plage de pile de 4 Ko sélectionnée par 11, convertis le champ de déplacement de douze bits en déplacement négatif :

Le champ va de 0 à 4 095, donc ce déplacement est toujours négatif. Il est valide lorsque sa valeur absolue ne dépasse pas la taille actuelle de la pile. Ajoute ensuite le déplacement signé à la base.

Étudier un accès autorisé à la pile

L’adresse virtuelle 15 500 sélectionne la pile. Sa plage commence à l’adresse virtuelle 12 288, donc son champ de déplacement est 3 212. Convertis le champ :

La profondeur 884 est comprise dans la taille de 2 048. La traduction donne :

Ajouter la valeur positive 3 212 à la base pointerait au-dessus de la pile. Le champ n’est pas encore le déplacement requis pour un segment qui croît vers le bas.

L’adresse virtuelle 13 000 donne quant à elle un champ de 712 et un déplacement de −3 384. Sa profondeur dépasse 2 048, donc le matériel déclenche un défaut. Si le système d’exploitation agrandit la pile, l’augmentation de sa taille peut rendre valides davantage d’adresses basses.

Inclure la borne inférieure

Un déplacement de −2 048 atteint l’octet le plus bas de la pile, 51 200, et est autorisé. Un déplacement de −2 049 est en dehors. La vérification pour la croissance vers le bas inclut donc la valeur absolue égale à la taille. Cela correspond au nombre d’octets de la règle pour la croissance vers le haut, même si cette règle exclut un déplacement égal à la taille : la base pour la croissance vers le haut est un octet, tandis que celle pour la croissance vers le bas est une borne de fin.

Vérifier l’opération demandée

Les bits de protection enregistrent les permissions de lecture, d’écriture et d’exécution. Le code est généralement accessible en lecture et en exécution ; le tas et la pile sont généralement accessibles en lecture et en écriture. Une écriture dans du code autorisé en lecture et en exécution provoque un défaut même si son déplacement est valide. L’exécution de données provoque aussi un défaut lorsque la permission d’exécution est absente.

Le code en lecture seule peut être partagé. Le système d’exploitation peut faire pointer les segments de code de deux processus vers la même zone physique et interdire les écritures dans les deux. Les octets d’instruction occupent une seule copie physique, tandis que chaque processus conserve un tas et une pile distincts.

La segmentation remplace une grande zone par plusieurs zones plus petites. Cela évite d’associer de la mémoire physique aux espaces virtuels vides, mais le système d’exploitation doit désormais placer et agrandir des zones de tailles différentes tout en préservant l’état de traduction de chaque processus.

Sauvegarder chaque partie de la correspondance

Lors d’une commutation de contexte, la base et la taille ne suffisent plus. Le système d’exploitation sauvegarde et restaure la base, la taille, le sens de croissance et les permissions de chaque segment. Restaurer une pile avec le mauvais sens ou du code avec les mauvaises permissions changerait la signification d’adresses par ailleurs identiques.

Lorsqu’un allocateur a besoin de plus d’espace sur le tas, le système d’exploitation doit étendre le segment physique du tas. Des octets libres immédiatement au-dessus permettent une croissance directe. Sinon, le système d’exploitation peut le déplacer vers un trou plus grand adapté et mettre à jour sa base. S’il ne peut pas obtenir une zone adaptée, l’agrandissement échoue.

Choisir la granularité

Multics utilisait la segmentation à grain fin. Davantage de segments permettent un contrôle par unités plus petites, mais nécessitent davantage de métadonnées de traduction et de gestion.

Trouver un trou suffisamment grand

Les segments physiques de tailles variables laissent des trous libres de tailles variables lorsque les processus démarrent, grandissent et se terminent. Il y a fragmentation externe lorsque le nombre total d’octets libres est suffisant, mais qu’aucun trou ne peut contenir à lui seul le segment demandé.

Supposons que les trous libres mesurent 8 Ko, 6 Ko et 10 Ko. Leur total est de 24 Ko. Un segment de tas de 12 Ko ne peut toujours pas y tenir : le plus grand trou disponible ne mesure que 10 Ko. Réunir les trous sur le papier ne rend pas leurs adresses physiques adjacentes.

Le compactage peut corriger cette organisation. Le système d’exploitation met les processus en pause, copie les segments côte à côte et met leurs bases à jour. Les adresses virtuelles continuent de fonctionner car la traduction masque les déplacements physiques. Il en résulte une grande zone libre contiguë, mais la copie est coûteuse et de nouvelles allocations peuvent fragmenter à nouveau la mémoire.

Des politiques de placement comme le premier ajustement et le meilleur ajustement cherchent à limiter les fragments inutilisables sans effectuer de copie. Aucune politique de placement à tailles variables ne supprime la fragmentation externe pour toutes les séquences de demandes. Un seul grand segment peut aussi gaspiller de l’espace à l’intérieur de sa propre étendue lorsque seules des parties dispersées sont utilisées.

Reconnaître le modèle dans les systèmes modernes

La pagination divise la mémoire en morceaux de taille fixe et évite d’exiger que chaque zone logique occupe un seul trou physique. Le modèle de segmentation reste utile pour comprendre les zones, la protection et le partage. En mode 64 bits de x86-64, les bases de segmentation ordinaires du code, des données et de la pile se comportent comme si elles valaient zéro et leurs limites ne sont pas vérifiées ; FS et GS conservent des bases utiles pour les données propres à chaque fil d’exécution ou à chaque processeur. Un message d’accès interdit appelé erreur de segmentation ne signifie pas que le modèle classique à trois segments est actif.

La gestion de l’espace libre répertorie la mémoire disponible et choisit l’emplacement de chaque demande. Des demandes de même taille peuvent utiliser une liste de blocs interchangeables. Les tailles variables sont plus difficiles à gérer : un allocateur de tas comme un système d’exploitation qui place des segments doit trouver un bloc contigu assez grand pour la demande suivante.

Localiser la fragmentation externe

Considérons une zone de 60 octets avec les octets libres de 0 à 19, un bloc alloué de 20 à 39 et les octets libres de 40 à 59. Quarante octets sont libres, mais aucun des deux trous ne peut satisfaire une demande de 25 octets. Le bloc encore alloué au milieu empêche de traiter ces trous comme une seule zone.

C’est une fragmentation externe : de l’espace est libre en dehors des blocs alloués, mais sa disposition le rend inutilisable pour une demande contiguë particulière. Les octets libres n’ont pas disparu. Ils peuvent encore servir à de plus petites demandes ou devenir utiles lorsque les blocs qui les séparent sont libérés.

Localiser la fragmentation interne

Un allocateur qui arrondit les demandes aux multiples de 16 donne à une demande de 20 octets un bloc de 32 octets. Les 12 octets supplémentaires se trouvent à l’intérieur d’un bloc déjà alloué. Ce gaspillage est une fragmentation interne.

L’espace inutilisé entre le tas et la pile dans un emplacement régi par une base et une limite est un autre exemple. L’allocation par compagnons introduit le même type de gaspillage lorsqu’elle arrondit aux puissances de deux. Le niveau de gestion diffère, mais c’est l’emplacement de l’espace inutilisé qui définit le type de fragmentation.

Un même allocateur peut subir les deux. Arrondir une demande peut gaspiller des octets dans son bloc tandis que d’autres blocs libres restent séparés ailleurs.

Fusionner les blocs libres voisins sans déplacer les données encore utilisées

La fusion des blocs libres réunit les blocs libres physiquement adjacents. Si le bloc central de la zone de 60 octets est libéré, les trois parties peuvent former un seul trou de 60 octets. Si le bloc central reste alloué, la fusion ne peut pas le franchir. La fusion réduit la fragmentation externe, mais ne garantit pas un trou assez grand pour chaque demande.

Ajouter de la mémoire à un tas peut réduire la pression, mais ne change pas les adresses des blocs existants encore alloués. Leur placement peut toujours laisser de petits espaces inutilisables.

Expliquer pourquoi le système d’exploitation peut compacter les segments

Le système d’exploitation peut copier les segments physiques et mettre leurs bases à jour. Les programmes conservent des adresses virtuelles, de sorte que la correspondance peut masquer ces déplacements. Un allocateur général de tas en C ne dispose pas d’une couche de traduction entre les pointeurs renvoyés et les emplacements dans le tas. Un programme peut avoir copié un pointeur dans de nombreux objets et l’allocateur ne peut pas découvrir et réécrire chaque copie.

Déplacer seul un bloc du tas encore alloué laisserait ces pointeurs dirigés vers son ancien emplacement. Par conséquent, la gestion ordinaire par malloc conserve les blocs alloués aux adresses renvoyées jusqu’à leur libération. Elle doit gérer la fragmentation par le placement, la réutilisation, la scission et la fusion de l’espace libre.

Une liste des blocs libres répertorie les blocs libres par adresse et par taille. L’allocation scinde un bloc ou le retire de la liste ; la libération rend un bloc et peut le fusionner avec ses voisins. La convention de taille compte : une taille enregistrée peut désigner la charge utile utilisable ou le bloc entier, métadonnées comprises.

Scinder et fusionner des plages simples

Ignorons d’abord les en-têtes. Dans une zone de 60 octets avec les entrées libres (0, 20) et (40, 20), une demande de 8 octets placée au début renvoie l’adresse 0. Les entrées restantes sont (8, 12) et (40, 20).

En repartant de l’organisation initiale, libère les octets alloués du milieu, de 20 à 39. Sans fusion, trois entrées de 20 octets ne peuvent toujours pas satisfaire individuellement une demande de 30 octets. La fusion des plages adjacentes produit (0, 60), qui le peut. L’ordre des adresses aide l’allocateur à reconnaître les voisins ; le voisinage dans la liste ne suffit pas à lui seul si leurs plages physiques ne se touchent pas.

Retrouver l’en-tête à partir du pointeur utilisateur

free(ptr) ne reçoit aucune taille. Un allocateur simple stocke un en-tête de taille juste avant la charge utile, parfois accompagné d’une valeur de contrôle ou d’un nombre magique. Soustraire la longueur de l’en-tête permet de trouver les métadonnées.

Avec un en-tête de 16 octets, une demande de 96 octets occupe 112 octets au total. Le programme reçoit un pointeur situé 16 octets après le début du bloc. Sa libération rend toute l’étendue de 112 octets, en-tête compris, pour la gestion future. L’alignement peut entraîner un arrondi ; les tailles de cet exemple respectent déjà un alignement sur 16 octets.

Suivre une liste des blocs libres intégrée

Supposons qu’un tas de 4 096 octets commence à 32 768. Un nœud libre utilise 16 octets et indique les octets utilisables après le nœud. Au départ, il indique 4 080 octets utilisables.

Trois demandes de 96 octets consomment chacune 112 octets :

Le nœud libre restant commence à 33 104. Sa taille utilisable est de 3 744 octets. Le décompte est :

Libérer le bloc pointé par 32 896 permet de trouver l’en-tête à 32 880. Ce bloc devient un nœud libre de 96 octets utilisables. Il ne peut pas rejoindre le dernier nœud à 33 104 car la troisième allocation se trouve entre eux. Lorsque les trois blocs alloués sont libérés et fusionnés, un seul nœud décrit de nouveau 4 080 octets utilisables. L’absorption des anciens en-têtes intérieurs rend leurs octets disponibles dans l’étendue fusionnée.

Conserver les informations de gestion dans la zone gérée

Les nœuds de liste intégrés se trouvent dans la mémoire libre elle-même : la gestion de la liste ne nécessite donc pas une allocation distincte pour chaque entrée. Le nœud contient une taille et un lien vers le bloc libre suivant. Si aucun bloc ne convient, l’allocateur peut demander davantage de mémoire avec sbrk ou mmap ; s’il ne peut pas en obtenir assez, le résultat est NULL.

Un débordement peut écraser un en-tête ou un nœud voisin. Cela explique pourquoi la défaillance visible peut se produire lors d’un appel ultérieur à malloc ou free, après l’écriture qui a endommagé la liste.

Une politique de placement choisit parmi les blocs assez grands pour une demande. Des choix différents laissent des trous différents pour les demandes futures. Le temps de recherche compte autant que la fragmentation et aucune politique ne l’emporte pour toutes les charges de travail.

Comparer les règles de recherche

Pour le meilleur et le pire ajustement, une liste simple non triée nécessite un parcours complet. D’autres structures peuvent trouver plus rapidement des tailles adaptées. Le premier ajustement désigne le premier bloc dans l’ordre choisi pour la liste, ce qui ne signifie pas nécessairement la plus petite adresse, sauf si la liste est triée par adresse.

Suivre la première demande

Prenons des blocs libres de 30, 12, 50 et 20 octets par ordre d’adresse. Ignorons les en-têtes et supposons que la scission puisse conserver chaque reste. Une demande de 18 octets modifie la liste comme suit :

• Le meilleur ajustement utilise 20 et laisse 30, 12, 50, 2.
• Le pire ajustement utilise 50 et laisse 30, 12, 32, 20.
• Le premier ajustement utilise 30 et laisse 12, 12, 50, 20.
• L’ajustement suivant, en commençant au quatrième bloc, utilise 20 et laisse 30, 12, 50, 2.

L’ajustement suivant a besoin d’une position de départ pour déterminer son choix. Son nom seul n’implique pas la première entrée de la liste. Le suivi doit conserver cet état de recherche entre les demandes.

Comprendre pourquoi la demande suivante change le verdict

Une demande ultérieure porte sur 45 octets. Le meilleur ajustement et le premier ajustement ont tous deux préservé le bloc de 50 octets : ils réussissent donc tous les deux. Le plus grand bloc restant avec le pire ajustement mesure 32 octets : la demande échoue donc malgré les 94 octets libres au total :

Cet échec est dû à la fragmentation externe. La décision précédente a divisé le seul trou suffisamment grand. À l’inverse, le meilleur ajustement a laissé un fragment de 2 octets qui peut être trop petit pour des demandes futures utiles. Un petit reste immédiat ne prouve pas qu’une politique utilisera bien l’espace sur l’ensemble de la séquence de demandes.

Mettre en balance la politique et la structure de données

Parcourir des milliers d’entrées peut être coûteux même si chaque placement est bon. Les allocateurs utilisés en pratique regroupent les blocs par taille ou utilisent des structures de recherche comme des arbres équilibrés. Une liste triée par adresse facilite aussi la fusion en aidant à trouver les voisins physiques.

Le mécanisme d’allocation (trouver, scinder, mettre à jour les métadonnées) peut rester le même lorsque la politique change. Pour comparer équitablement les politiques, suis les mêmes demandes et libérations, garde les mêmes règles de surcoût et tiens compte à la fois des trous obtenus et du travail de recherche.

La recherche générale dans une liste des blocs libres est souple, mais peut être coûteuse. Les allocateurs spécialisés rendent les demandes courantes prévisibles en regroupant les tailles, en conservant des objets réutilisables ou en limitant les tailles des blocs aux puissances de deux.

Réutiliser les tailles courantes et les objets initialisés

Les listes séparées par taille conservent des listes de blocs libres distinctes pour les tailles courantes, avec un allocateur général pour les autres demandes. Une demande de taille courante peut être satisfaite en prenant directement un bloc dans sa liste. Les blocs de même taille ne créent pas de fragmentation externe entre eux, mais la répartition de la capacité entre les listes est un choix de politique : les blocs disponibles d’une taille peuvent ne pas convenir à une autre taille.

Un allocateur slab conserve un cache d’objets pour un type d’objet du noyau utilisé de façon récurrente, comme un inode, un verrou ou un descripteur de processus. Un bloc slab est divisé en objets de ce type. Le cache obtient davantage de blocs slab au besoin et peut rendre un bloc entièrement libre à un allocateur général. Jeff Bonwick a conçu cette approche pour Solaris.

Le cache conserve les objets libérés dans un état initialisé, ce qui évite de répéter leur préparation et leur destruction. Cela fait gagner du temps au-delà de la recherche elle-même.

Diviser une zone en blocs compagnons

Un allocateur binaire par compagnons part d’une zone dont la taille est une puissance de deux et arrondit chaque demande à une taille de bloc égale à une puissance de deux. Il divise successivement un bloc libre en deux moitiés égales jusqu’à ce qu’une moitié soit juste assez grande. Les deux moitiés issues d’une division sont des blocs compagnons.

Pour une demande de 5 Ko dans une zone de 64 Ko, arrondis 5 Ko à 8 Ko. Divise les 64 Ko en deux blocs de 32 Ko, puis les 32 Ko choisis en deux blocs de 16 Ko, puis les 16 Ko choisis en deux blocs de 8 Ko. Renvoyer le premier bloc de 8 Ko laisse des blocs compagnons libres aux déplacements 8 Ko, 16 Ko et 32 Ko, de tailles respectives 8 Ko, 16 Ko et 32 Ko.

L’allocation gaspille 3 Ko à l’intérieur de son bloc de 8 Ko. C’est une fragmentation interne, acceptée en échange de scissions et de fusions régulières.

Trouver l’unique partenaire de fusion autorisé

En utilisant les déplacements mesurés depuis le début de la zone gérée :

Le ou exclusif inverse le bit correspondant à la taille du bloc. Pour un bloc de 8 Ko au déplacement 0, son compagnon se trouve au déplacement 8 192. Pour un bloc de 16 Ko au déplacement 16 384, son compagnon se trouve à 0.

Lorsque le premier bloc de 8 Ko est libéré, il fusionne avec son compagnon libre de 8 Ko. Le bloc de 16 Ko obtenu peut fusionner avec son compagnon libre, puis le bloc de 32 Ko obtenu peut à nouveau fusionner. La fusion s’arrête si le compagnon requis de même taille est utilisé. Être adjacents et libres ne suffit pas si les deux blocs ne sont pas des compagnons issus de la même division.

Une demande de 20 Ko reçoit 32 Ko, ce qui gaspille 12 Ko, soit 37,5 % du bloc. Linux associe l’allocation de mémoire physique par compagnons à des caches d’objets de type slab. Les allocateurs multithreadés utilisent aussi des caches locaux ou plusieurs arènes pour réduire l’attente d’un verrou d’allocation partagé ; glibc, jemalloc et tcmalloc utilisent des variantes de ces idées.