Mémoire virtuelle et pagination

Chaque adresse qu’utilise un programme est un mensonge. Quand les chapitres précédents ont montré deux processus lisant des valeurs différentes à la même adresse, ou main atterrissant ailleurs à chaque lancement, il s’agissait d’adresses virtuelles : des nombres qui n’ont de sens qu’à l’intérieur d’un processus. Entre le CPU et les puces mémoire, un circuit traduit chacune d’elles, à chaque lecture, écriture et chargement d’instruction, en adresse physique, l’emplacement réel dans la RAM. Cette traduction, mise en place par le système d’exploitation et effectuée par le matériel, c’est la mémoire virtuelle.

Tout commence dans les années 1950 : les programmeurs découpaient leurs programmes à la main en recouvrements (overlays) chargés l’un après l’autre dans une mémoire minuscule. En 1961, une équipe de Manchester proposa de le faire automatiquement, et au début des années 1970 la plupart des ordinateurs en disposaient. La motivation a changé depuis (les machines ont désormais beaucoup de RAM), mais la mémoire virtuelle est restée, parce qu’elle donne à chaque processus un espace d’adressage privé et protégé, permet au système de partager et de copier la mémoire à peu de frais, et de n’allouer la mémoire que lorsqu’elle sert vraiment.

Pages, cadres et MMU

La correspondance n’est pas tenue octet par octet. L’espace d’adressage virtuel est découpé en pages de taille fixe, la mémoire physique en cadres de page (page frames) de même taille, et une table des pages indique, pour chaque page virtuelle, quel cadre la contient, ou qu’aucun ne la contient. Le circuit qui la consulte est la MMU (memory management unit), présente dans chaque cœur.

Comme la taille de page est une puissance de deux, une adresse se coupe proprement en deux : les bits de poids fort forment le numéro de page virtuelle, les bits de poids faible le décalage dans la page. Seul le numéro de page est traduit ; le décalage passe tel quel. Avec des pages de 4 Kio, le décalage occupe les 12 bits de poids faible, soit les trois derniers chiffres hexadécimaux :

Il affiche 40401c page 404 offset 1c pour la globale, 406010 page 406 offset 10 pour le bloc du tas et 7fffffc4 page 7ffff offset fc4 pour la variable locale. Le simulateur ne traduit pas les adresses (son espace d’adressage est l’espace physique), mais les vraies machines les découpent exactement ainsi. Le même programme sur le Mac où ce chapitre a été écrit, dont les pages font 16 Kio, garde 14 bits de décalage : sa variable de pile, en 0x16b11e794, est au décalage 0x2794 de la page 0x5ac47.

Des tables de pages à plusieurs niveaux

Une table unique et plate ne convient pas aux espaces d’adressage 64 bits. x86-64 et ARM64 utilisent des adresses virtuelles de 48 bits ; avec des pages de 4 Kio, cela fait 2³⁶ pages, et une entrée de 8 octets pour chacune occuperait 512 Gio par processus. L’essentiel d’un espace d’adressage est vide : on fait donc de la table un arbre. Le numéro de page est découpé en plusieurs index, chacun choisissant une entrée à un niveau, qui pointe vers la table du niveau suivant. Seules les parties de l’arbre qui couvrent de la mémoire utilisée existent.

Sur x86-64, et sur ARM64 avec des pages de 4 Kio, chaque table est une page de 4 Kio contenant 512 entrées de huit octets ; chaque niveau consomme donc 9 bits de l’adresse : 9 + 9 + 9 + 9 + 12 = 48. Prenons l’adresse de pile 0xffffec4f579c d’un processus Linux ARM 64 bits :

bits 47–39  → level 0 index 511
bits 38–30  → level 1 index 511
bits 29–21  → level 2 index 354
bits 20–12  → level 3 index 245   → frame number
bits 11–0   → offset 0x79c        (copied unchanged)

Quatre lectures en mémoire pour traduire une adresse : c’est le parcours de la table (page walk), effectué par la MMU elle-même sur x86, ARM et RISC-V. Chaque processus a son propre arbre, et changer de processus revient à désigner une autre racine à la MMU : le registre CR3 sur x86, TTBR0_EL1 sur ARM64.

48 bits donnent 256 Tio d’adresses virtuelles, que Linux coupe en deux sur x86-64 : 128 Tio pour l’utilisateur, 128 Tio pour le noyau. Intel a ajouté un cinquième niveau, à partir de ses processeurs Ice Lake, pour les serveurs dotés d’énormes mémoires : la pagination à 5 niveaux porte les adresses à 57 bits, soit 128 Pio, et Linux la prend en charge.

ARM64 laisse le système choisir la taille de page, appelée granule de traduction, et la forme de l’arbre en découle :

Apple a choisi des pages de 16 Kio pour ses Mac ARM et ses iPhone : sysctl hw.pagesize répond 16384 sur ce M2. La machine virtuelle Linux qui tourne sur la même puce utilise 4 Kio (getconf PAGESIZE affiche 4096), parce que son noyau a été compilé ainsi. La taille de page n’est donc pas une propriété du CPU mais un choix du système parmi ce que le CPU permet, et un choix qui évolue lentement, car les logiciels la supposent sans le dire : Android n’a commencé à gérer les pages de 16 Kio qu’avec Android 15, et depuis novembre 2025 Google Play exige que les nouvelles applications et mises à jour qui le ciblent fonctionnent avec elles.

Les anciennes conceptions 32 bits utilisaient deux niveaux : le x86 en mode 32 bits découpait une adresse en 10 + 10 + 12 bits avec des pages de 4 Ko, et l’ARM 32 bits proposait des pages de 4 Ko à 16 Mo. Le principe est identique ; les machines 64 bits ont simplement besoin de deux ou trois niveaux de plus. Et les tailles de page, autrefois de 512 octets à 64 Ko, sont aujourd’hui de 4, 16 ou 64 Kio, avec de grandes pages en plus.

Ce que contient une entrée de table

Une entrée de table des pages (PTE) x86-64 fait 64 bits : le numéro du cadre physique, et des indicateurs que la MMU vérifie à chaque accès :

• P (present) : la correspondance est valide. S’il est à 0, tout accès provoque un défaut de page, et les 63 autres bits sont libres pour que le système y note, par exemple, où la page est partie sur le disque.
• R/W : écriture autorisée.
• U/S : le mode utilisateur peut accéder à la page. Les pages du noyau l’ont à 0 : c’est le mécanisme matériel derrière l’isolation du chapitre sur les appels système.
• NX (no-execute, bit 63) : les octets de la page ne peuvent pas être exécutés comme des instructions. Avec R/W, il donne les droits W^X visibles dans /proc/self/maps : code en r-x, données en rw-.
• A (accessed) et D (dirty) : positionnés par le matériel quand la page est lue et quand elle est écrite. Le système s’en sert pour choisir quoi évincer, et pour savoir si une page évincée doit être réécrite : les pages « propres » et « sales ».

Les entrées ARM64 portent les mêmes informations sous d’autres noms (droits d’accès, UXN/PXN pour l’interdiction d’exécuter, un indicateur d’accès, un mécanisme de bit sale). Chaque protection que le système offre à un processus (code en lecture seule, pile non exécutable, page de garde sous la pile, page NULL qui fait planter) est l’un de ces bits.

Le TLB : un cache des traductions

Quatre lectures mémoire de plus par accès rendraient chaque programme plusieurs fois plus lent. Chaque cœur garde donc les traductions récentes dans un petit cache rapide, le TLB (translation lookaside buffer) : numéro de page virtuelle en entrée, numéro de cadre et droits en sortie, dans le même cycle que la consultation du cache. Ce n’est qu’en cas d’échec TLB (TLB miss) que la MMU parcourt l’arbre, et même alors les niveaux supérieurs de l’arbre sont généralement dans les caches de données ordinaires.

C’est le TLB qui rend la forme des accès importante à l’échelle de la page, et pas seulement de la ligne de cache. Cette expérience suit une chaîne de pointeurs à travers 4 096 lignes de cache dans un ordre aléatoire : 512 Kio de données dans les deux cas. Dans une disposition, les lignes sont serrées les unes contre les autres ; dans l’autre, chacune est seule dans sa page, si bien que la chaîne touche 4 096 pages différentes :

Mêmes données, même comportement du cache, et trois à cinq fois plus lent : la différence, ce sont les échecs TLB et les parcours de table. Avec 1 024 lignes, qui tiennent dans le cache L1, la chaîne serrée prend 0,9 ns par lecture et la chaîne à une ligne par page de 3 à 8 ns. Les pages de 16 Kio de macOS couvrent quatre fois plus de mémoire par entrée de TLB que les pages de 4 Kio, et les grandes pages (huge pages) de 2 Mio 512 fois plus, assez pour ramener le cas dispersé presque au niveau du cas serré. (Les chiffres Linux incluent un coût de virtualisation : dans une machine virtuelle, un échec TLB parcourt les tables de l’invité et celles de l’hyperviseur, comme l’explique le chapitre sur la virtualisation matérielle.)

Un changement de contexte change de tables de pages, ce qui rendrait fausse chaque entrée du TLB. Les anciens processeurs x86 vidaient tout le TLB à chaque changement. Les actuels étiquettent les entrées avec un numéro d’espace d’adressage (PCID sur x86, ASID sur ARM), si bien que les entrées de plusieurs processus cohabitent et survivent au changement.

Défauts de page et pagination à la demande

Quand la MMU ne trouve pas de correspondance valide, elle déclenche un défaut de page (page fault), l’exception redémarrable du chapitre sur les déroutements. Le noyau cherche ce qui devrait se trouver à cette adresse. Si l’accès est illégal, le processus reçoit SIGSEGV. S’il est légal mais que la page n’est pas encore là, le noyau trouve un cadre, le remplit, écrit la PTE et revient à l’instruction fautive, qui s’exécute à nouveau et réussit. Le programme ne s’aperçoit de rien.

C’est ce qui rend possible la pagination à la demande : rien n’est chargé avant d’être touché. malloc(1 Gio) ou mmap ne fait qu’enregistrer une région ; aucun cadre n’est alloué. La première écriture dans chaque page provoque un défaut, le noyau fournit un cadre rempli de zéros, et c’est seulement alors que la page compte dans la mémoire du processus. Mesure : réserver 1 Gio, écrire un octet par page, puis recommencer :

Chaque page du premier passage a provoqué un défaut, et chaque défaut a coûté de 500 à 900 ns, surtout pour remettre le nouveau cadre à zéro, plus le déroutement. Le second passage n’a provoqué aucun défaut. Avec les grandes pages, un seul défaut projette 2 Mio d’un coup, et le nombre de défauts est divisé par 512. Ensuite, le /proc/self/status de Linux affichait VmRSS: 1049836 kB (le gigaoctet, désormais résident) et VmPTE: 2100 kB : les tables de pages elles-mêmes, 262 144 entrées de 8 octets plus les niveaux supérieurs.

Ce sont des défauts mineurs : aucun disque en jeu. Un défaut majeur doit lire la page sur le disque : dans le fichier exécutable pour le code, dans la zone d’échange (swap) pour les données évincées. Le même mécanisme réalise la copie sur écriture : après fork, parent et enfant partagent des cadres marqués en lecture seule, et la première écriture provoque un défaut, copie la page et recommence. Il permet aussi à Linux la surallocation (overcommit) : il distribue plus de mémoire virtuelle qu’il n’a de RAM et d’espace d’échange, en pariant que la plus grande partie ne sera jamais touchée.

Quand la mémoire manque

Quand il faut un cadre et qu’aucun n’est libre, le noyau doit évincer une page : la jeter si elle est propre et adossée à un fichier, l’écrire d’abord dans l’espace d’échange si elle est sale. Laquelle ? L’idéal serait celle dont on aura besoin le plus tard, ce que personne ne sait. LRU (least recently used, la moins récemment utilisée) s’en approche, mais suivre l’ordre exact de chaque accès coûterait trop cher. Les vrais noyaux approchent LRU avec le bit d’accès du matériel : l’algorithme de l’horloge (clock) balaie les cadres en remettant les bits d’accès à zéro, et évince une page dont le bit est encore à zéro au passage suivant. Linux tient des listes active et inactive, et propose depuis la version 6.1 (2022) un LRU à plusieurs générations ; macOS et Windows utilisent leurs propres variantes de la même idée.

LRU échoue lourdement quand une boucle parcourt une page de plus que ce qui tient en mémoire : chaque accès évince exactement la page dont on aura besoin ensuite. Plus généralement, chaque programme a un ensemble de travail (working set), le terme de Denning pour les pages qu’il utilise activement. Si les ensembles de travail des programmes en cours tiennent en RAM, les défauts sont rares. Sinon, le système s’écroule (thrashing) : il passe son temps à faire entrer et sortir des pages. Voici un conteneur limité à 256 Mio de RAM, avec espace d’échange autorisé, qui touche chaque page d’un tampon quatre fois de suite :

Trois à cinq mille fois plus lent, pour un tampon seulement deux fois plus grand. Chaque passage évince les pages dont le suivant a besoin en premier : c’est la pathologie de LRU, pour de vrai. Chacun des 25 600 défauts majeurs a lu quatre pages d’un coup dans l’espace d’échange ; la durée d’un passage divisée par le nombre de défauts majeurs donne environ 100 µs par défaut sur ce disque virtuel. Un accès à un disque dur coûte environ 10 ms de positionnement et de rotation ; les SSD ont divisé ce chiffre par cent, mais une page lue dans l’espace d’échange coûte encore environ dix mille fois plus qu’une page déjà en RAM.

Les systèmes modernes essaient d’éviter complètement l’échange sur disque en compressant la mémoire. macOS le fait depuis 2013 : les pages qui seraient échangées sont d’abord compressées en RAM. Sur ce Mac, vm_stat indiquait 2 462 121 pages stockées dans le compresseur, soit 37,6 Gio de données, occupant 587 094 pages, soit 9,0 Gio : un rapport d’environ 4 pour 1. Windows 10 a ajouté une réserve compressée semblable ; Linux propose zswap et zram.

Choisir une taille de page

Le compromis reste valable. Les petites pages gaspillent moins de mémoire : en moyenne, la moitié de la dernière page d’une région reste inutilisée, c’est la fragmentation interne. Les grandes pages demandent moins d’entrées de table, moins de défauts et moins d’entrées de TLB, comme on l’a mesuré. La tendance va vers le grand : les pages de 4 Kio ont été la norme pendant des décennies, 16 Kio est le choix d’Apple, et au-dessus de la taille de base, x86-64 propose des pages de 2 Mio et 1 Gio, ARM64 des blocs de 2 Mio, 32 Mio, 512 Mio ou 1 Gio selon le granule.

Linux utilise les grandes pages de deux façons. Les grandes pages transparentes (THP, transparent huge pages) laissent le noyau adosser automatiquement la mémoire anonyme qui s’y prête à des pages de 2 Mio ; la VM Linux utilisée ici a THP réglé sur always, et c’est pourquoi les expériences précédentes ont dû s’en exclure avec madvise(MADV_NOHUGEPAGE) pour observer le comportement à 4 Kio. Et hugetlbfs réserve explicitement des grandes pages, pour les bases de données et les machines virtuelles qui veulent des garanties.

La segmentation, un détour historique

Les systèmes plus anciens utilisaient la segmentation : au lieu d’un seul espace d’adressage linéaire, un programme dispose de plusieurs segments (code, pile, table des symboles), chacun commençant à 0 et capable de grandir indépendamment. Le x86 32 bits en avait toute la machinerie : sélecteurs dans CS, DS et SS, descripteurs dans la GDT et la LDT avec une base et une limite, pagination appliquée par-dessus, le tout calqué sur MULTICS ; et quatre anneaux de protection reliés par des portes d’appel (call gates).

Cela décrit le x86 32 bits. En mode 64 bits, celui qu’utilisent tous les systèmes x86 actuels, la segmentation a pratiquement disparu : les bases de CS, DS, ES et SS sont considérées comme nulles et leurs limites ne sont pas vérifiées. Seuls FS et GS gardent une base, qui ne sert qu’à une chose : pointer vers des données propres à chaque thread (Linux place le stockage local aux threads derrière FS, Windows son bloc d’informations de thread derrière GS). Les anneaux 1 et 2 restent inutilisés, et les appels système passent par syscall plutôt que par des portes d’appel. ARM64 et RISC-V n’ont jamais eu de segments. La pagination seule l’a emporté : chaque espace d’adressage est une plage plate unique, et les régions de /proc/self/maps jouent le rôle que les segments devaient jouer, sans second type d’adresse.

Mémoire virtuelle et caches

Une remarque est à retenir : mémoire virtuelle et cache sont la même idée à deux niveaux de la hiérarchie. Un cache garde certaines lignes de la mémoire en SRAM rapide, et un échec est traité par le matériel en quelques nanosecondes ; la mémoire virtuelle garde certaines pages de l’espace d’adressage en RAM, et un échec est traité par le système en microsecondes, ou en millisecondes depuis le disque. Les deux reposent sur la localité. Les deux évincent avec des approximations de LRU. Et le TLB est un cache de la table des pages elle-même, placé sur le chemin de chaque accès mémoire.

À retenir

• Les programmes utilisent des adresses virtuelles ; la MMU les traduit en adresses physiques à chaque accès, page par page. Le décalage dans la page passe sans changement.
• Les tables de pages sont des arbres : 4 niveaux de 9 bits sur x86-64 et sur ARM64 avec des pages de 4 Kio (adresses de 48 bits), 5 niveaux pour 57 bits. ARM64 permet aussi des granules de 16 et 64 Kio ; Apple utilise 16 Kio.
• Une entrée de table contient le numéro de cadre et les bits de protection (présent, modifiable, utilisateur, non exécutable), plus les bits d’accès et sale dont le système se sert pour évincer.
• Le TLB met les traductions en cache. Toucher beaucoup de pages coûte du temps : 6 ns par lecture pour des lignes serrées, 30 ns avec une ligne par page de 4 Kio, 8 ns avec des grandes pages de 2 Mio, mesurés ici.
• La pagination à la demande alloue les cadres au premier accès : environ 500 à 900 ns par défaut de page ici. Le même mécanisme donne la copie sur écriture et la surallocation.
• Quand la RAM manque, le système évince des pages choisies par des approximations de LRU comme l’horloge. Si l’ensemble de travail ne tient pas, le système s’écroule : des milliers de fois plus lent dans l’expérience du conteneur. La compression mémoire (4 pour 1 sur ce Mac) retarde le passage par le disque.
• La segmentation appartient au passé sur le x86 64 bits : seuls FS et GS survivent, pour les données propres aux threads.