Pagination et mémoire virtuelle

Un programme utilise des adresses virtuelles. La mémoire physique contient les octets dans des cadres. La pagination divise l’espace d’adressage virtuel en pages de taille égale et la mémoire physique en cadres de même taille. Le système d’exploitation peut placer n’importe quelle page dans n’importe quel cadre libre. La page 0 peut occuper le cadre 12 et la page 1 le cadre 3 ; le programme voit toujours des adresses virtuelles consécutives.

Cela supprime la fragmentation externe pour les allocations de pages individuelles. Avec des segments de taille variable, une demande peut échouer parce que l’espace libre est divisé en trous trop petits. Avec la pagination, un cadre libre peut toujours contenir une page. Un espace d’adressage creux peut laisser un grand espace entre le tas et la pile sans réserver de cadres physiques pour cet espace.

Mesurer l’espace inutilisé dans les pages

La pagination présente néanmoins une fragmentation interne. Une zone doit occuper un nombre entier de pages, même lorsque sa dernière page est partiellement vide. Une zone de 9 000 octets nécessite trois pages de 4 KiB : deux pages contiennent 8 192 octets, laissant 808 octets pour la troisième. L’allocation occupe 12 288 octets, dont 3 288 sont inutilisés. KiB signifie 1 024 octets ; MiB signifie 1 048 576 octets. Certains ouvrages utilisent KB et MB pour ces quantités binaires.

Découper l’adresse en champs

Une adresse désigne à la fois une page et un octet à l’intérieur de celle-ci. Pour une taille de page de $2^k$ octets, les $k$ bits de poids faible constituent le déplacement. Les bits de poids fort restants constituent le numéro de page virtuelle, ou VPN. Une adresse de 32 bits avec des pages de 4 KiB comporte 12 bits de déplacement et 20 bits de VPN. Cet espace d’adressage compte $2^{20}$ pages virtuelles possibles.

Pour 0x00403A7C, les trois derniers chiffres hexadécimaux donnent le déplacement 0xA7C, car chaque chiffre hexadécimal représente quatre bits. Les cinq premiers chiffres donnent le VPN 0x00403. Ce raccourci fonctionne ici parce que la frontière entre les champs tombe entre deux chiffres hexadécimaux. Pour une autre taille de page, compte les bits avant de découper la valeur hexadécimale écrite.

Le calcul décimal donne le même résultat :

Ici, $P$ est la taille de page en octets. Avec des pages de 1 024 octets, l’adresse virtuelle 5 000 a pour VPN 4 et pour déplacement 904. Quatre pages complètes représentent 4 096 octets ; les 904 octets restants situent l’adresse dans la page 4. Les déplacements commencent à zéro : ceux de cette page vont donc de 0 à 1 023.

La traduction remplace le VPN par un numéro de cadre physique. Elle recopie le déplacement sans changement : l’octet 904 d’une page virtuelle est l’octet 904 de son cadre. Le numéro de page seul n’est pas une adresse d’octet. Multiplie un numéro de cadre par la taille de page pour trouver l’adresse de début du cadre, puis ajoute le déplacement.

Choisir une taille de page

Des pages plus grandes réduisent le nombre de correspondances et permettent à chaque traduction en cache de couvrir davantage d’octets. Elles gaspillent aussi plus d’espace dans les pages partiellement utilisées et déplacent davantage de données lors du chargement d’une page. Une taille de page de base courante est de 4 KiB ; d’autres systèmes utilisent 16 KiB ou 64 KiB. x86-64 prend aussi en charge des projections de grande taille, comme les pages de 2 MiB.

Une table des pages répertorie les correspondances d’un processus. Dans une table des pages linéaire, le VPN indexe un tableau : l’entrée 4 décrit la page virtuelle 4. Chaque processus possède sa propre table : une même adresse virtuelle peut donc désigner des octets physiques différents selon le processus. Lors d’une commutation de contexte, le système d’exploitation sélectionne la table du nouveau processus au moyen d’un registre de base de table des pages.

Lire l’état et les permissions d’une entrée

Une entrée de table des pages, ou PTE, contient un numéro de cadre physique (PFN) et des informations de contrôle. Dans le modèle pédagogique, un bit de validité indique que la page appartient à l’espace d’adressage ; un bit de présence indique que son contenu se trouve en mémoire physique. Les bits de protection contrôlent les lectures, les écritures, l’exécution et les accès en mode utilisateur. Un bit de modification enregistre les écritures effectuées depuis sa dernière remise à zéro. Un bit d’accès enregistre les utilisations depuis sa dernière remise à zéro ; il est aussi appelé bit de référence ou d’utilisation.

Ce sont des rôles conceptuels, et non la garantie d’une organisation matérielle identique partout. Sur x86, une PTE ne possède pas de bit de validité distinct. Lorsque le bit de présence est à zéro, le système d’exploitation consulte ses propres informations pour distinguer une adresse inutilisée d’une page valide stockée ailleurs. Sur x86, le matériel positionne les bits d’accès et de modification ; le système d’exploitation les gère et les remet à zéro.

Localiser l’entrée et l’octet

Pour traduire une adresse avec une table linéaire :

1. Découpe l’adresse virtuelle en VPN et déplacement.
2. Localise son entrée à l’adresse $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}+\mathrm{V}\mathrm{P}\mathrm{N}\times \mathrm{P}\mathrm{T}\mathrm{E}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}$.
3. Vérifie que la correspondance existe, que la page est présente et que l’accès est autorisé.
4. Forme l’adresse physique avec $\mathrm{P}\mathrm{F}\mathrm{N}\times \mathrm{p}\mathrm{a}\mathrm{g}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}+\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}\mathrm{t}$.
5. Lis ou écris l’octet à cette adresse physique.

Avec des pages de 1 024 octets, l’adresse virtuelle 5 000 donne le VPN 4 et le déplacement 904. Supposons que la PTE 4 indique que la page est présente, autorise la lecture demandée et contienne le PFN 9. Le cadre 9 commence à 9 216 : l’adresse physique de l’octet est donc 10 120. L’adresse de la table elle-même relève d’un calcul distinct : si les entrées occupent 4 octets, la PTE 4 se trouve 16 octets après la base de la table.

Pour un exemple hexadécimal, des pages de 4 KiB découpent 0x00403A7C en VPN 0x403 et déplacement 0xA7C. Si la correspondance autorisée contient le PFN 0x1F2B5, l’adresse physique est 0x1F2B5A7C. La PTE se trouve à base + 0x403 × 4 = base + 0x100C. La concaténation du déplacement forme une adresse de données ; la multiplication du VPN par la taille d’une entrée localise la PTE. Ces deux adresses servent à des usages différents.

Une vérification qui échoue déclenche une exception. Le système d’exploitation peut charger une page valide absente de la mémoire, fournir une mémoire remplie de zéros ou corriger une autre correspondance légitime. Une adresse invalide ou un accès interdit provoque généralement une erreur de segmentation. Une page présente peut tout de même refuser une écriture si sa protection l’interdit.

Compter l’espace des tables et les lectures mémoire

Les tables linéaires sont coûteuses même pour les petits processus. Avec des adresses virtuelles de 32 bits et des pages de 4 KiB, chaque table nécessite 1 048 576 entrées. À raison de 4 octets chacune, cela représente 4 MiB par processus, y compris les entrées des pages virtuelles inutilisées. Cent processus ont besoin de 400 MiB rien que pour ces tables.

Elles ajoutent aussi une recherche à chaque référence mémoire. Dans un modèle simple sans cache de traduction, le processeur lit une PTE puis les données demandées : deux accès mémoire. Le partage reste possible : deux processus peuvent volontairement associer leurs pages virtuelles distinctes au même PFN, comme pour du code de programme en lecture seule.

Un tampon de traduction, ou TLB, est un petit cache matériel de traductions d’adresses situé dans l’unité de gestion mémoire (MMU). Il contient des correspondances récentes entre VPN et PFN ainsi que des informations d’accès. Il met en cache des traductions, tandis qu’un cache de données contient les octets du programme. Une recherche peut échouer dans un cache et réussir dans l’autre.

Suivre les succès et les échecs

Lors d’une recherche réussie dans le TLB, la MMU obtient le PFN de l’entrée en cache, vérifie les permissions d’accès et combine le PFN avec le déplacement inchangé. Elle n’a pas besoin de lire la table des pages. Un succès ne dispense jamais de faire respecter la protection. Le bit de validité du TLB indique qu’une entrée en cache est utilisable ; il n’indique pas si une page virtuelle appartient à l’espace d’adressage du processus.

En cas d’échec de recherche dans le TLB, le système doit rechercher la traduction dans la table des pages. Si la page est présente et que l’accès est autorisé, il installe la traduction et termine ou réessaie la référence. Aucune lecture sur le stockage n’est nécessaire. Si, au contraire, la table indique une correspondance absente ou un accès interdit, un défaut de page nécessite l’intervention du système d’exploitation. Un échec de recherche dans le TLB ne constitue pas à lui seul un défaut de page.

Prédire la réutilisation grâce à la localité

Les TLB peuvent contenir bien moins d’entrées qu’il n’existe de pages virtuelles, mais ils fonctionnent bien parce que les programmes présentent une localité. La localité spatiale signifie que des adresses voisines sont utilisées à des instants proches. Dès qu’une traduction est en cache, de nombreuses adresses de cette page peuvent l’utiliser. La localité temporelle signifie que les adresses utilisées récemment seront probablement réutilisées, comme pour les instructions d’une boucle.

Considère 16 384 entiers de quatre octets stockés consécutivement dans un tableau aligné sur une frontière de page. Avec des pages de 4 KiB, chaque page contient 1 024 entiers : le tableau occupe donc 16 pages. En partant d’un TLB vide et sans autres traductions qui interfèrent, le premier entier de chaque page provoque un échec. Les 1 023 suivants sur cette page donnent des succès. Il y a en tout 16 échecs et 16 368 succès, soit un taux de succès d’environ 99,9 %.

L’ordre des accès modifie ce résultat. En C, int a[1024][1024] stocke les lignes consécutivement. Supposons des entiers de quatre octets, un alignement sur une frontière de page, des pages de 4 KiB et un TLB LRU de 64 entrées. Chaque ligne occupe une page. Un parcours ligne par ligne produit un échec par ligne, soit 1 024 échecs. Un parcours colonne par colonne visite 1 024 pages différentes avant de revenir à la première. Sa traduction a déjà été évacuée : les 1 048 576 références au tableau donnent donc toutes lieu à un échec. La taille du tableau n’a pas changé ; c’est la distance entre deux utilisations qui change.

Calculer le coût moyen des succès et des échecs

Le modèle de durée doit préciser le coût d’un succès et celui d’un échec. Supposons qu’un accès mémoire prenne 100 ns, que la recherche dans le TLB n’ajoute aucun temps et qu’un échec avec une table linéaire ajoute une lecture mémoire. Un succès coûte 100 ns et un échec dont la traduction est trouvée coûte 200 ns. Avec un taux de succès de 98 % :

Cette moyenne comprend l’accès final aux données dans les deux cas. Ne compter que la lecture supplémentaire de la PTE comme coût total de l’échec sous-estimerait ce coût. Avec des tables multiniveau, un échec peut nécessiter plusieurs lectures de tables : la localité compte donc encore davantage.

Un échec de recherche dans le TLB nécessite une recherche de traduction, mais les architectures répartissent ce travail différemment. Avec un TLB géré par le matériel, comme sur x86 et ARM, la MMU parcourt la table des pages à partir de la racine sélectionnée. Le matériel définit le format qu’il peut parcourir. Si la correspondance est utilisable, il remplit le cache de traduction sans appeler de gestionnaire du système d’exploitation pour cet échec ordinaire.

Un TLB géré par logiciel, utilisé dans les architectures classiques MIPS et SPARC, déclenche une exception en cas d’échec. Un gestionnaire du système d’exploitation trouve la correspondance et l’insère à l’aide d’instructions privilégiées. Cela donne au système d’exploitation davantage de liberté quant à la structure de sa table. Le retour de cette exception relance l’instruction dont la recherche a échoué ; le retour d’un appel système poursuit normalement après l’appel.

Garder le gestionnaire de remplissage accessible

Le gestionnaire d’échecs doit pouvoir accéder de manière fiable à ses propres instructions et données. Si le traitement d’un échec déclenche immédiatement, dans le gestionnaire, le même type d’échec non résolu, le système peut ne plus progresser. Les architectures évitent cela grâce à une mémoire non traduite ou à des traductions permanentes pour le code et les données indispensables du gestionnaire.

Sélectionner le bon espace d’adressage

Les commutations de contexte introduisent un autre problème. Le processus A peut associer le VPN 7 au cadre 20, tandis que le processus B associe le VPN 7 au cadre 90. Conserver l’entrée de A sans identifiant après le passage à B enverrait B vers le mauvais cadre. Charger la racine de la table des pages de B ne suffit pas à rendre sûre une correspondance en cache dépourvue d’identifiant.

Une solution consiste à invalider les entrées concernées du TLB lors d’une commutation. Leurs bits de validité sont remis à zéro, ce qui oblige le nouveau processus à les remplir de nouveau. Une autre solution associe aux entrées un identifiant d’espace d’adressage (ASID). La recherche vérifie alors à la fois la page virtuelle et son identifiant d’espace d’adressage. x86 appelle son identifiant un identifiant de contexte de processus, ou PCID. Les entrées de plusieurs espaces d’adressage peuvent rester en cache tandis que le matériel ne sélectionne que celles qui appartiennent au contexte courant. La réutilisation des identifiants doit néanmoins être gérée afin qu’une ancienne entrée ne soit pas prise pour celle d’un nouvel espace d’adressage.

Invalider les correspondances modifiées

La modification d’une PTE rend aussi périmée une traduction en cache. Supposons que le système d’exploitation retire la permission d’écriture en mémoire mais laisse une entrée du TLB autorisant l’écriture. Le processeur pourrait continuer à autoriser les écritures par cette ancienne entrée. Le système d’exploitation doit invalider les traductions concernées. Sur une machine à plusieurs cœurs, chaque cœur susceptible de conserver la correspondance en cache doit participer. Cette coordination s’appelle une invalidation interprocesseur du TLB.

Calculer la couverture des traductions

La capacité compte autant que la validité. La couverture du TLB est la quantité de mémoire représentée par les traductions en cache :

Un TLB de 64 entrées couvre 256 KiB avec des pages de 4 KiB et 128 MiB avec des pages de 2 MiB. La couverture décrit l’étendue des correspondances, et non la capacité de la mémoire physique. Les processeurs existants peuvent avoir des capacités de TLB distinctes selon la taille des pages : ce calcul compare donc un nombre fixe d’entrées.

Lorsqu’un TLB est plein, il remplace une traduction. LRU favorise les entrées récemment utilisées ; le remplacement aléatoire choisit sans suivre la date de dernière utilisation. Parcourir en boucle une page de plus que le TLB ne peut en contenir met LRU en échec, car chaque traduction est évacuée juste avant d’être nécessaire à nouveau.

Une table des pages linéaire réserve une entrée pour chaque page virtuelle possible. La plupart des processus n’utilisent qu’une petite partie de leur espace d’adressage : le code et le tas se trouvent près d’une extrémité, la pile près de l’autre, et un grand espace les sépare. Une table comportant des millions d’entrées invalides consomme tout de même de la mémoire. Réduire ce coût implique de modifier la taille des pages, l’organisation de la table ou les deux.

Réduire le nombre de pages

Des pages plus grandes réduisent le nombre de VPN. Avec un espace d’adressage de 32 bits et des pages de 16 KiB, 14 bits forment le déplacement et 18 bits forment le VPN. Une table linéaire nécessite alors 262 144 entrées. À raison de 4 octets chacune, elle occupe 1 MiB, contre 4 MiB pour des pages de 4 KiB. Cela économise de l’espace pour la table, même si le processus peut toujours adresser 4 GiB d’octets virtuels.

Le coût se déplace ailleurs. Une petite allocation peut gaspiller davantage de sa dernière page, et le chargement d’une page en mémoire transfère davantage d’octets. Augmenter la taille des pages ne distingue pas une partie de l’espace d’adressage très utilisée d’un espace inutilisé ; cela réduit simplement le nombre d’entrées pour les deux.

Omettre les espaces vides avec des tables de segments distinctes

La segmentation paginée donne au code, au tas et à la pile leurs propres tables des pages. Chaque segment possède une base de table et une borne pour ses numéros de page. L’espace entre les segments ne nécessite aucune entrée. La traduction sélectionne d’abord le segment, vérifie sa borne, puis recherche la page dans ce segment.

Cette approche dépend d’un découpage pertinent en segments. Ses tables peuvent avoir des longueurs différentes et nécessiter de l’espace physique contigu, ce qui réintroduit la fragmentation externe pour les tables elles-mêmes. Les pages de données du processus restent de taille fixe ; les objets fragmentés sont désormais les tables des pages de taille variable.

Indexer les cadres physiques

Une table des pages inversée change ce que décrit une entrée. Elle comporte une entrée par cadre physique pour toute la machine, indiquant le processus et le VPN qui l’occupent. Avec 16 GiB de mémoire physique et des cadres de 4 KiB, elle nécessite 4 194 304 entrées, quel que soit le nombre de processus possédant de grands espaces d’adressage virtuels. Il faut encore connaître la taille d’une entrée pour convertir ce nombre en un total d’octets.

Une table ordinaire utilise le VPN comme indice direct dans un tableau. Une table inversée recherche à la place la paire constituée de l’identité de l’espace d’adressage et du VPN. Une structure de hachage peut rendre cette recherche efficace, mais les collisions peuvent nécessiter des recherches supplémentaires. Les cadres partagés nécessitent aussi un traitement supplémentaire, car un cadre peut avoir plusieurs noms virtuels. Les tables des pages hachées, comme celles utilisées dans les systèmes PowerPC, reposent sur des principes de recherche apparentés ; une table hachée n’est pas nécessairement une table inversée comportant strictement une entrée par cadre.

Allouer les tables par zone utilisée

Les tables des pages multiniveau conservent la recherche indexée tout en n’allouant des pages de table de niveau inférieur que là où des correspondances sont nécessaires. Une entrée de niveau supérieur peut marquer toute une plage inutilisée sans allouer sa table de niveau inférieur. C’est la solution courante sur les systèmes modernes. L’économie est maximale pour les espaces d’adressage creux, tandis qu’un échec de recherche dans le TLB nécessite davantage d’étapes de recherche.

Pour comparer les solutions, demande-toi ce qui détermine leur taille. Une table linéaire grandit avec le nombre de pages virtuelles par processus. Une table inversée grandit avec le nombre de cadres physiques du système. Une hiérarchie grandit avec les branches de tables nécessaires aux correspondances. Aucun de ces nombres n’est le nombre d’octets de données du programme actuellement présents en mémoire.

Une table des pages à deux niveaux divise une grande table linéaire en morceaux de la taille d’une page. Un répertoire de pages pointe vers ces morceaux. Le répertoire est alloué, mais une page de table des pages de niveau inférieur ne l’est que lorsque sa zone nécessite des correspondances. Une entrée de répertoire absente peut représenter toute une plage inutilisée.

Déduire le découpage 10/10/12

Prends une adresse virtuelle de 32 bits, des pages de 4 KiB et des entrées de 4 octets. Chaque page de table des pages contient 1 024 entrées : un indice de 10 bits sélectionne donc une entrée. L’adresse se découpe en 10 bits de répertoire, 10 bits de table et 12 bits de déplacement. Chaque table de niveau inférieur associe 1 024 pages à des cadres, couvrant 4 MiB d’adresses virtuelles. Le répertoire comporte lui aussi 1 024 entrées et occupe une page de 4 KiB.

Suivre les entrées de répertoire et de table

Le parcours suit des pointeurs physiques :

1. Ajoute $\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ à la base physique du répertoire. Lis cette entrée de répertoire de pages (PDE).
2. Si elle pointe vers une page de table, multiplie son PFN par 4 096 pour obtenir la base physique de cette table.
3. Ajoute $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ et lis la PTE.
4. Vérifie la correspondance de dernier niveau et combine son PFN avec le déplacement.

La PDE pointe vers une table, tandis que la PTE pointe vers la page de données demandée. Confondre ces rôles dirige une référence vers la mémoire des tables des pages au lieu des données du programme.

Pour l’adresse virtuelle 0x00803ABC, l’indice de répertoire est 2, l’indice de table est 3 et le déplacement est 0xABC. Supposons que l’entrée de répertoire 2 pointe vers le cadre 0xA1. Sa table commence à 0xA1000. L’entrée 3 se trouve à 12 octets du début de cette table, à l’adresse 0xA100C. Si la PTE indique que la page est présente, autorise l’accès et contient le PFN 0x2F3C4, l’adresse des données est 0x2F3C4ABC.

Remarque les deux multiplicateurs différents. Un indice de table compte des entrées : multiplie-le donc par la taille d’une entrée. Un PFN compte des cadres : multiplie-le donc par la taille de page. Le déplacement compte des octets dans la page finale et ne nécessite aucun de ces multiplicateurs. La base du répertoire et les pointeurs utilisés pendant le parcours sont des adresses physiques ; utiliser des pointeurs virtuels nécessiterait une autre traduction pour effectuer cette traduction.

Compter les tables et les lectures de recherche

L’espace dépend de la répartition des correspondances. Supposons qu’un processus utilise les 8 MiB du bas de son espace de 4 GiB et les 4 MiB du haut, les deux zones étant alignées sur des frontières de répertoire. La zone basse nécessite deux pages de table et la zone haute une. Avec le répertoire, cela donne quatre pages, soit 16 KiB, au lieu d’une table linéaire de 4 MiB. Répartir le même nombre de pages de données de façon éparse dans de nombreuses zones de répertoire pourrait nécessiter davantage de pages de table.

Dans le schéma pédagogique de base, une PDE invalide signifie qu’aucune des pages de sa zone de 4 MiB n’appartient à l’espace d’adressage. Le parcours s’arrête sans lire de PTE. Les systèmes d’exploitation complets peuvent aussi utiliser des entrées absentes pour l’allocation différée : leurs informations logicielles déterminent donc la signification d’une entrée que le matériel considère comme absente.

La hiérarchie économise de l’espace en ajoutant du travail lors d’un échec de recherche dans le TLB. Un parcours à deux niveaux sans cache lit une PDE et une PTE avant d’accéder aux données : trois lectures mémoire au total, contre deux pour une table linéaire. Une recherche réussie dans le TLB évite ces lectures de tables. Un taux de succès élevé devient donc particulièrement précieux à mesure que la hiérarchie s’approfondit.

Le nombre de niveaux de tables découle de trois valeurs : le nombre de bits d’adresse virtuelle effectivement pris en charge, la taille de page et la taille d’une entrée. Calcule d’abord le nombre de bits du déplacement. Calcule ensuite combien d’entrées tiennent dans une page de table et combien de bits sélectionnent une entrée. Enfin, divise les bits restants du VPN en champs d’indice, en arrondissant si nécessaire le nombre de niveaux à l’entier supérieur.

Déduire les quatre niveaux

Pour la pagination x86-64 à quatre niveaux, le nombre de bits d’adresse virtuelle pris en charge est de 48. Une page de 4 KiB fournit 12 bits de déplacement. Une entrée de 8 octets donne 512 entrées par page de table, sélectionnées par 9 bits. Le VPN comporte 36 bits : quatre indices de 9 bits sont donc nécessaires. Un parcours réussi sans cache suit quatre entrées puis accède aux données.

Les niveaux sont la PML4, la table des pointeurs de répertoires de pages, le répertoire de pages et la table des pages. Leurs indices occupent les bits 47 à 39, 38 à 30, 29 à 21 et 20 à 12. CR3 indique la racine physique. Linux nomme les niveaux correspondants PGD, PUD, PMD et PTE ; sa hiérarchie générique comprend un niveau P4D, qui est fusionné lorsque l’architecture n’utilise que quatre niveaux.

Distinguer le nombre de bits d’adresse de la mémoire vive

Un espace d’adressage prenant en charge 48 bits contient 256 TiB d’octets adressables. Les adresses sont néanmoins conservées dans des valeurs de 64 bits : dans la forme canonique ordinaire, les bits au-dessus du bit 47 répètent ce bit. Les plages basse et haute valides sont séparées par un espace non canonique. Parler d’un espace d’adressage de 48 bits ne signifie pas que toutes les configurations de 64 bits sont utilisables ni qu’un processus reçoit 256 TiB de mémoire vive.

Une table linéaire serait énorme. Il existe $2^{36}$ pages virtuelles ; en multipliant par des entrées de 8 octets, on obtient $2^{39}$ octets, soit 512 GiB par processus. Une hiérarchie représente les plages inutilisées par des branches absentes au lieu de réserver toutes ces entrées.

Les processeurs prenant en charge la pagination à cinq niveaux peuvent utiliser 57 bits d’adresse virtuelle lorsque ce mode est activé. Un indice supplémentaire de 9 bits est ajouté au-dessus de la PML4, ce qui donne 128 PiB d’octets adressables et une lecture de table possible supplémentaire. Les bits supérieurs d’une adresse canonique répètent alors le bit 56. Les fonctions prises en charge par le processeur et le mode de pagination activé déterminent le nombre de bits applicable.

Arrêter le parcours à une page de grande taille

Les pages de grande taille arrêtent le parcours plus tôt. Sur x86-64, une entrée au niveau du répertoire de pages peut associer directement une page de 2 MiB à un cadre, en laissant 21 bits de déplacement. Une entrée de la table des pointeurs de répertoires de pages peut associer une page de 1 GiB à un cadre, en laissant 30 bits de déplacement. Les bits de poids plus faible qui sélectionnent autrement des entrées de niveau inférieur sélectionnent alors des octets dans cette page de grande taille.

Cela réduit à la fois la longueur du parcours et le nombre de traductions nécessaires pour une zone donnée. La couverture du TLB augmente, ce qui peut aider les bases de données et d’autres charges de travail importantes. La correspondance physique nécessite une zone contiguë de cadres correctement alignée, et une page de grande taille partiellement utilisée peut gaspiller beaucoup plus de mémoire. Linux prend en charge l’allocation explicite de pages géantes et les pages géantes transparentes ; les tailles prises en charge dépendent de l’architecture.

Le décompte simple des coûts suppose qu’aucune entrée de table n’est en cache. Les processeurs existants mettent en cache les structures de pagination et les lectures de tables peuvent réussir dans les caches ordinaires. Quatre niveaux ne signifient donc pas nécessairement quatre attentes dues à la mémoire principale à chaque échec de recherche dans le TLB. Ils décrivent la chaîne de dépendances et son coût sans cache.

Les espaces d’adressage virtuels peuvent ensemble dépasser la mémoire physique, car toutes les pages n’ont pas besoin d’y rester présentes. L’espace d’échange stocke le contenu des pages déplacées sur un disque ou un SSD. Linux peut utiliser une partition ou un fichier d’échange ; Windows utilise un fichier d’échange. La mémoire physique contient le sous-ensemble des pages actuellement présentes.

La pagination déplace des pages individuelles. Une sortie vers le stockage de sauvegarde y écrit une page avant la réutilisation de son cadre ; une entrée la relit. Historiquement, l’échange désignait aussi le déplacement d’un processus entier. Dans les discussions actuelles, le terme désigne souvent le déplacement de pages : identifie donc l’objet déplacé.

Interpréter la correspondance manquante

Le bit de présence d’une PTE indique au matériel si une correspondance vers une page présente en mémoire est disponible. Si une page valide a été transférée dans l’espace d’échange, le système d’exploitation enregistre l’emplacement de son contenu, soit dans des bits de l’entrée définis par le logiciel, soit dans des métadonnées distinctes. Un bit de présence à zéro ne désigne pas à lui seul l’espace d’échange : il peut aussi correspondre à une mémoire non allouée ou dont l’allocation est différée.

Un défaut de page est une exception provoquée par un accès qui ne peut pas aboutir avec la correspondance actuelle. Il peut indiquer une absence ou une violation de protection. Le gestionnaire décide si l’accès est légitime et comment le traiter. Un traitement réussi peut charger des octets stockés, fournir une mémoire remplie de zéros, associer la page à un cadre déjà présent en mémoire ou créer une copie privée. Un accès réellement invalide entraîne généralement une erreur de segmentation.

Restaurer une page sauvegardée

Suis la lecture d’une page présente dans l’espace d’échange avec des pages de 1 024 octets :

1. L’adresse virtuelle 5 000 donne le VPN 4 et le déplacement 904.
2. Le TLB ne possède aucune traduction utilisable. Le parcours de la table des pages trouve la page valide mais absente ; les informations logicielles indiquent le bloc 37 de l’espace d’échange.
3. Le gestionnaire obtient le cadre 9. Si aucun cadre n’est libre, la récupération de mémoire doit d’abord faire de la place.
4. Le système d’exploitation lit le bloc 37 dans le cadre 9. Le processus ayant provoqué le défaut attend ; un autre processus prêt peut utiliser le processeur.
5. À la fin de la lecture, le système d’exploitation inscrit le PFN 9, indique que la page est présente et remet le processus à l’état prêt.
6. L’instruction est relancée. La traduction atteint maintenant l’adresse physique 10 120.

L’instruction reprend l’opération prévue une fois les octets disponibles. Passer à l’instruction suivante après l’échec ferait perdre un chargement ou un stockage. Le processus peut subir une attente, mais son adresse virtuelle n’a pas changé.

Classer le défaut et prévoir la demande

Un défaut majeur nécessite une lecture sur le stockage. Un défaut mineur est résolu sans cette entrée-sortie, par exemple en fournissant un cadre rempli de zéros ou en associant la page à un cadre déjà présent en mémoire. Un grand nombre de défauts mineurs n’implique donc pas le même trafic sur le périphérique qu’un nombre égal de défauts majeurs. Sous Linux, /usr/bin/time -v indique les deux nombres pour une commande.

La pagination à la demande attend le premier accès à une page avant de la fournir. Un programme peut ainsi commencer sans charger tout son contenu. Le préchargement charge les pages dont on prévoit qu’elles seront bientôt nécessaires. De bonnes prévisions évitent des attentes ultérieures ; de mauvaises prévisions consomment de la bande passante et de la mémoire pour des pages jamais utilisées.

Distingue les événements. Un échec de recherche dans le TLB nécessite une recherche de traduction. Un défaut de page demande au système d’exploitation de traiter un problème de correspondance. Une erreur de segmentation est une issue habituelle pour un accès interdit. Une page présente et accessible peut provoquer un échec de recherche dans le TLB sans provoquer aucun des deux autres événements.

Une lecture rare sur le stockage peut dominer le temps d’accès moyen à la mémoire. Soit $p$ la probabilité qu’une référence provoque un défaut majeur, $M$ le temps d’accès ordinaire et $F$ le temps total de traitement d’une référence qui provoque un défaut. Un modèle simple à deux cas donne :

Ici, $F$ comprend la lecture sur le stockage, le travail du système d’exploitation et toute réécriture nécessaire d’une page victime modifiée. C’est le temps total en cas de défaut, et non simplement un petit surcoût de recherche d’une PTE.

Calculer l’effet de défauts rares

Supposons qu’un accès ordinaire prenne 100 ns et qu’un défaut majeur prenne 8 ms au total. Convertis 8 ms en 8 000 000 ns avant de calculer la moyenne. Avec un défaut pour 1 000 références :

Cela représente environ 81 fois le temps d’accès ordinaire. Un taux de défauts de 0,1 % paraît faible, mais un défaut coûte autant que plusieurs milliers de références mémoire.

Pour un ralentissement inférieur à 10 %, la moyenne doit être inférieure à 110 ns. En réorganisant l’expression, on obtient :

Cela représente moins d’un défaut majeur pour environ 800 000 références. La probabilité admissible dépend du temps de traitement supposé. Pour un temps de traitement de 0,1 ms sur un SSD, donné à titre d’exemple, l’attente est plus courte, mais elle est encore de 100 000 ns : mille accès de 100 ns.

Garder des cadres disponibles

Le système d’exploitation essaie de préparer des cadres avant qu’un défaut n’en nécessite un. Un démon de pagination en arrière-plan, comme kswapd sous Linux, récupère de la mémoire lorsque le nombre de cadres libres passe sous un seuil bas. Dans le modèle élémentaire à seuils, il poursuit son travail jusqu’à un seuil haut. Cela évite d’attendre la sélection et la préparation d’une victime à chaque défaut.

Préserver les modifications avant la réutilisation

Une page modifiée contient des changements effectués depuis la dernière remise à zéro de l’état de modification. Avant la réutilisation de son cadre, ces changements doivent être préservés si la page fait toujours partie de la mémoire d’un processus. Sa réécriture peut avoir lieu en arrière-plan. Après une réécriture réussie, la page présente en mémoire peut être marquée comme non modifiée ; une écriture ultérieure la rend à nouveau modifiée.

Une page non modifiée ne peut être écartée sans nouvelle écriture que si son contenu peut être récupéré ou recréé. Le code de programme non modifié peut être relu depuis l’exécutable. Une page dont une copie à jour existe dans l’espace d’échange peut être relue depuis cet espace. Une page anonyme non modifiée sans copie récupérable ne peut pas simplement être oubliée. Le bit de modification ne prouve pas à lui seul qu’une copie existe sur un stockage de sauvegarde.

Si un défaut doit évacuer une page modifiée de façon synchrone, il peut nécessiter l’écriture de la victime suivie de la lecture demandée. Préférer une victime non modifiée et récupérable évite cette écriture pendant le traitement bloquant du défaut. Le regroupement des transferts combine plusieurs écritures en transferts plus importants, ce qui est particulièrement utile sur les disques.

Les défauts de page sont des points de contrôle utiles pour différer du travail. Une correspondance peut appartenir à un processus avant que le système d’exploitation ne lui attribue un cadre privé. Avec la mise à zéro à la demande, le premier accès obtient une mémoire remplie de zéros. Cela évite d’allouer et de mettre à zéro toutes les pages réservées dès le départ. La mise à zéro empêche aussi un processus de voir les données laissées par un autre.

Le défaut ne nécessite aucune lecture sur disque, car le contenu requis est constitué de zéros et non d’octets sauvegardés. C’est un défaut mineur. Un système peut optimiser l’implémentation, mais le résultat visible reste une mémoire nouvellement fournie contenant les zéros requis.

Partager du code en lecture seule

Des tables des pages distinctes n’imposent pas de copies distinctes de chaque page. Deux PTE peuvent contenir le même PFN, même à des adresses virtuelles différentes. Les processus exécutant le même programme peuvent partager du code en lecture seule. Cinquante processus utilisant un éditeur peuvent faire référence à une seule copie présente en mémoire de chaque page de code partagée. La protection en lecture seule empêche un processus de modifier ces instructions pour tous les autres.

Créer un contenu privé lors d’une écriture

La copie sur écriture (COW) permet le partage initial de pages qui pourront ensuite nécessiter un contenu privé. Après fork(), le processus père et le processus fils ont des espaces d’adressage distincts, mais peuvent partager leurs cadres de données privées ordinaires. Le système d’exploitation marque leurs correspondances privées accessibles en écriture comme étant en lecture seule et enregistre qu’il s’agit de correspondances à copie sur écriture. Les lectures réussissent sans copie.

Lorsque l’un des deux processus écrit pour la première fois dans une page partagée à copie sur écriture, l’écriture enfreint sa protection actuelle et provoque un défaut de page. Le gestionnaire reconnaît ce cas légitime, alloue un cadre privé, copie la page, installe une correspondance accessible en écriture pour le processus qui a écrit et relance l’instruction. L’autre processus conserve le contenu d’origine. Le système d’exploitation doit aussi mettre les traductions en cache en accord avec les correspondances modifiées.

Pour un processus ayant 400 MiB de données privées présentes en mémoire, supposons que son processus fils écrive dans trois pages distinctes de 4 KiB avant d’appeler exec(). Les données copiées à cause de ces écritures représentent au total 12 288 octets. Des écritures répétées dans une page déjà privée ne provoquent pas à chaque fois une nouvelle copie de toute la page. La création des tables des pages et les autres tâches de gestion du processus ont toujours un coût ; la copie sur écriture évite de copier immédiatement les 400 MiB de données.

C’est particulièrement utile lorsque fork() est rapidement suivi de exec(), qui remplace l’espace d’adressage du processus fils. Copier immédiatement toutes les anciennes données effectuerait un travail que le processus fils pourrait ne jamais utiliser. Les correspondances volontairement partagées et accessibles en écriture ont une sémantique différente : la copie sur écriture concerne les correspondances privées qui doivent diverger lors d’une écriture.

Une PTE en lecture seule ne suffit pas à établir qu’il s’agit d’une copie sur écriture. Une écriture dans du code de programme réellement en lecture seule est une erreur ; une écriture dans une page de données protégée pour la copie sur écriture peut être prise en charge. Les informations logicielles distinguent ces cas : la même exception matérielle de protection peut donc aboutir à une nouvelle tentative réussie ou à une erreur de segmentation.

Protéger les projections du noyau

Les projections mémoire du noyau utilisent aussi la protection. Une conception traditionnelle projette la mémoire du noyau dans l’espace d’adressage de chaque processus avec un accès réservé au superviseur, ce qui permet d’entrer dans le noyau sans sélectionner une correspondance entièrement différente. Le code en mode utilisateur ne peut pas accéder à ces pages simplement parce qu’elles ont des adresses. L’isolation des tables de pages du noyau, introduite sur les systèmes concernés après la révélation de Meltdown en 2018, supprime la plupart des projections du noyau pendant l’exécution du code utilisateur et change les correspondances à l’entrée dans le noyau.

Une politique de remplacement choisit une page présente en mémoire à évacuer lorsqu’aucun cadre n’est libre pour une page nécessaire. La mémoire physique sert de cache pour le contenu des pages. La politique tente de conserver les pages dont l’utilisation future évitera des défauts coûteux. Un défaut dans le modèle de remplacement indique simplement que la page n’est pas présente ; la nécessité d’une entrée-sortie dépend de la provenance du contenu manquant.

Consigner les succès et les défauts

Compare les politiques avec la même chaîne de références, le même nombre de cadres et le même état initial. Une chaîne de références énumère les numéros de pages dans l’ordre des accès. Pour chaque référence, demande-toi d’abord si la page est présente en mémoire. Si oui, consigne un succès. Sinon, consigne un défaut, charge la page et n’évacue une victime que si la mémoire est déjà pleine.

Les premières références provoquent des défauts même lorsqu’il reste des cadres libres. Ces défauts obligatoires ne peuvent pas être évités en choisissant une autre victime. Les défauts ultérieurs dus à une capacité insuffisante sont des défauts de capacité. Le remplacement des pages ne présente pas de conflit de placement : une page peut occuper n’importe quel cadre. Les défauts de conflit concernent les caches à placement restreint, et non ce modèle de cadres entièrement souple.

Choisir l’utilisation future la plus éloignée

La politique optimale, OPT ou MIN, choisit la page dont la prochaine utilisation est la plus éloignée dans le futur. Une page qui ne sera plus jamais utilisée est une victime idéale. Cette politique produit le plus petit nombre de défauts pour une chaîne de références connue, mais un système d’exploitation en cours d’exécution ne peut pas connaître des références futures quelconques. OPT sert de référence pour les politiques utilisables en pratique.

Utilise trois cadres initialement vides et la chaîne 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. Les trois premières références remplissent la mémoire et provoquent des défauts. La référence suivante à 1 donne un succès. À la référence 5, la page 4 arrive : les pages 1, 2 et 3 présentes en mémoire seront de nouveau utilisées aux rangs 6, 8 et 11. Évacue 3, dont la prochaine utilisation est la plus éloignée.

Après le succès sur 1, la page 5 arrive au rang 7. Les pages 1, 2 et 4 présentes en mémoire seront de nouveau utilisées aux rangs 9, 8 et 10 ; OPT évacue donc 4. Les références suivantes à 2 et à 1 donnent des succès. La page 4 provoque un défaut au rang 10 ; 2 ou 5 peut être évacuée, car aucune des deux n’est réutilisée. La page 3 provoque ensuite un défaut et évacue une autre page qui ne sera plus utilisée. La dernière référence à 1 donne un succès.

Comparer les totaux et les charges de travail

La simulation compte 7 défauts et 5 succès. En comptant les 12 références, le taux de succès est de 5/12, soit environ 41,7 %. Il y a cinq pages distinctes, donc cinq défauts obligatoires. Si le taux indiqué exclut ces défauts, il devient 5/7, soit environ 71,4 %. Les deux taux peuvent décrire la même simulation : précise donc toujours le dénominateur.

Pour ne pas perdre le fil, distingue la référence courante de la suite des références futures. OPT compare la prochaine utilisation de chaque page présente en mémoire après le rang courant ; il ne choisit pas la page dont le numéro est le plus grand ou qui a été chargée en premier. Si deux pages ne sont plus jamais utilisées, l’un ou l’autre choix reste optimal.

Les charges de travail influent sur l’importance de la politique. Lorsque les références ont la même probabilité pour toutes les pages, les utilisations passées donnent peu d’indications. Avec de la localité, un petit ensemble de pages fréquemment utilisées reçoit de nombreuses références, et le conserver améliore le taux de succès. L’écart entre le nombre de défauts d’une politique utilisable en pratique et celui d’OPT mesure l’amélioration possible pour cette charge de travail.

FIFO évacue la page chargée en premier parmi celles actuellement présentes en mémoire. Une file suit l’ordre d’arrivée. Un succès ne déplace pas la page en fin de file. FIFO est donc facile à gérer, mais peut évacuer une page encore fréquemment utilisée simplement parce qu’elle est arrivée il y a longtemps.

Suivre la dernière utilisation plutôt que l’arrivée

LRU, qui remplace la page la moins récemment utilisée, suit l’utilisation la plus récente de chaque page présente en mémoire. En cas de succès, cette page devient la plus récemment utilisée ; en cas de défaut alors que la mémoire est pleine, la page dont la dernière utilisation est la plus ancienne est évacuée. Cette politique suit la localité temporelle : une utilisation récente prédit souvent une utilisation dans un futur proche. La date d’arrivée et celle de la dernière utilisation sont deux historiques différents.

Le remplacement aléatoire choisit au hasard une victime présente en mémoire sans suivre l’ordre des utilisations récentes. Son résultat varie d’une exécution à l’autre. Il peut éviter le comportement d’échec déterministe de LRU sur une charge de travail cyclique, mais peut tout de même faire de mauvais choix. LFU, qui remplace la page la moins fréquemment utilisée, suit des nombres d’utilisations plutôt que leur date. Sans vieillissement, il peut conserver une page très utilisée dans une phase antérieure du programme mais désormais inutilisée.

Simuler les politiques sur la même chaîne

Compare les politiques avec trois cadres vides sur 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. Les pages 1, 2 et 3 remplissent d’abord la mémoire. Le succès sur 1 laisse l’ordre de FIFO inchangé : l’arrivée de 4 évacue donc 1. LRU considère au contraire que 1 est récente et évacue 2. La référence suivante à 1 provoque donc un défaut avec FIFO et un succès avec LRU.

Pour LRU, les défauts ultérieurs évacuent 3 pour la page 5, 4 pour la page 2, 5 pour la page 4 et 2 pour la page 3. Le total est de 8 défauts et 4 succès. FIFO produit 10 défauts et 2 succès. OPT produit 7 défauts sur la même chaîne. LRU fait ici mieux que FIFO, mais n’atteint pas l’optimum qui tient compte du futur.

Expliquer l’anomalie de Belady

Davantage de cadres n’améliorent pas toutes les politiques sur toutes les chaînes. L’anomalie de Belady est une augmentation du nombre de défauts lorsque FIFO reçoit plus de cadres. Pour 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, FIFO produit 9 défauts avec trois cadres et 10 avec quatre. La capacité supplémentaire change les victimes choisies ensuite dans la file : les ensembles de pages présentes ne sont donc pas nécessairement inclus les uns dans les autres.

LRU et OPT sont des algorithmes à pile : lorsque les égalités sont traitées de façon cohérente, l’ensemble des pages présentes pour un nombre de cadres plus petit est inclus dans celui obtenu avec un nombre plus grand. Augmenter la capacité ne peut donc pas transformer un succès avec moins de mémoire en défaut avec plus de mémoire. Sur la chaîne de l’anomalie, LRU produit 10 défauts avec trois cadres et 8 avec quatre.

Reconnaître les charges de travail défavorables à LRU

Certaines charges de travail restent défavorables à LRU. Parcours trois fois en boucle les pages 1, 2, 3, 4 avec trois cadres. Chaque nouvelle page évacue celle qui sera nécessaire ensuite, ce qui produit 12 défauts. OPT en nécessite 6. Le remplacement aléatoire peut conserver des pages utiles d’un tour à l’autre et obtient ici de meilleurs résultats en moyenne. Un parcours unique peut de même évincer d’un cache LRU un ensemble utile de pages fréquemment utilisées.

Une comparaison de politiques doit préciser la charge de travail et le nombre de cadres. La localité rend le suivi des utilisations récentes utile dans de nombreux programmes, ce qui motive les approximations de LRU dans les systèmes existants. Une boucle périodique dépassant juste la capacité favorise un autre choix ; un avantage observé sur une courte simulation ne permet pas d’établir un classement universel.

LRU exact nécessite du travail à chaque référence mémoire. Avec des horodatages, chaque référence met à jour un horodatage et la sélection d’une victime recherche le plus ancien. Avec une liste ordonnée, la victime est disponible en fin de liste, mais chaque référence doit déplacer sa page en tête. Mettre à jour cette structure par logiciel à chaque chargement et stockage serait trop coûteux.

Lire le bit de référence

Le matériel fournit un indice moins coûteux : le bit de référence, aussi appelé bit d’accès ou d’utilisation. Le matériel le positionne lorsqu’une page est lue ou écrite. Le système d’exploitation le remet à zéro pour commencer une nouvelle période d’observation. Un bit positionné signifie qu’il y a eu au moins une utilisation depuis la dernière remise à zéro ; ce n’est pas un décompte de fréquence et il ne révèle pas l’ordre exact des dernières utilisations.

Rechercher une victime

L’algorithme de l’horloge place les cadres en cercle et maintient une aiguille pointant vers le prochain candidat. Lors d’un remplacement, il examine le bit de référence du candidat. Si le bit vaut 1, l’aiguille le remet à zéro et avance. Si le bit vaut 0, ce cadre est la victime. La nouvelle page entre avec son bit de référence positionné et l’aiguille avance au-delà. Un succès positionne le bit de la page référencée sans déplacer l’aiguille.

Supposons que le cercle contienne A avec un bit à 1, B avec un bit à 0 et C avec un bit à 1, et que l’aiguille pointe vers A. Un défaut sur D remet le bit de A à zéro et fait avancer l’aiguille vers B. Le bit de B vaut déjà 0 : D remplace donc B avec un bit à 1 et l’aiguille termine sur C. Si la référence suivante provoque un défaut sur E, l’aiguille remet le bit de C à zéro, puis trouve celui de A à 0 et remplace A. Si A avait été consultée entre ces défauts, son bit vaudrait 1 et elle recevrait une autre chance.

Si tous les bits valent 1 et qu’aucun nouvel accès n’intervient, un tour les remet tous à zéro. L’aiguille évacue alors sa page de départ lorsqu’elle y revient. Cette sélection particulière ressemble à la prochaine victime selon l’ordre d’arrivée de FIFO, mais l’horloge suit généralement l’historique des utilisations et la position de l’aiguille ; elle n’équivaut pas toujours à FIFO.

Une simulation complète de l’horloge nécessite une convention d’initialisation. Ici, les cadres vides sont remplis dans l’ordre avec un bit à 1 ; l’aiguille reste sur le cadre 0 jusqu’au premier remplacement. Les succès positionnent les bits. Chaque remplacement fait avancer l’aiguille. Selon cette convention, trois cadres sur 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1 produisent 10 défauts. Une courte chaîne peut masquer l’intérêt d’une approximation fondée sur les utilisations récentes ; l’horloge suit souvent bien la localité sur des exécutions plus longues.

Tenir compte du coût d’écriture et des variantes existantes

L’état de modification ajoute le coût de préservation d’une victime. Une préférence de l’algorithme de l’horloge amélioré classe les paires (référence, modification) dans l’ordre (0 ; 0), (0 ; 1), (1 ; 0), puis (1 ; 1). Cela favorise une page qui n’a pas été utilisée récemment et ne contient pas de modifications non sauvegardées. Les implémentations diffèrent dans leur manière de remettre les bits à zéro pendant le parcours et de planifier les écritures. Une réécriture en arrière-plan peut rendre une page candidate non modifiée avant que le remplacement n’en ait besoin.

Les systèmes existants utilisent des variantes plus élaborées. VAX/VMS plaçait les pages retirées dans des listes de pages non modifiées ou modifiées afin qu’un processus puisse en récupérer une avant la réutilisation de son cadre. Linux a utilisé des listes actives et inactives et propose un LRU multigénérationnel, qui regroupe les pages selon la date d’utilisation observée. Ces systèmes utilisent les informations du matériel pour guider les décisions du système d’exploitation ; le bit de référence matériel ne choisit pas lui-même une victime.

L’écroulement se produit lorsque les processus passent la majeure partie de leur temps à charger en mémoire des pages à la suite de défauts et à évacuer des pages qui seront bientôt nécessaires à nouveau. Le périphérique de stockage reste occupé tandis que le taux d’utilisation du processeur baisse, alors que les programmes ont encore du travail à effectuer. Une faible charge du processeur ne suffit pas à identifier un écroulement ; c’est l’association d’une pagination intense et d’une faible progression qui constitue l’indice.

La cause est une demande de mémoire supérieure au nombre de cadres disponibles. Un processus a besoin qu’un ensemble utile de pages soit présent en mémoire pour terminer sa phase courante. Si les ensembles actifs de plusieurs processus ne tiennent pas ensemble, leurs défauts déplacent sans cesse des pages utiles. Lancer encore davantage de processus peut aggraver cette pression, même si le processeur semble sous-utilisé.

Estimer la demande courante de pages

L’ensemble de travail, noté $W(t,\mathrm{\Delta })$, estime les besoins courants d’un processus. Dans le modèle à fenêtre de références, c’est l’ensemble des pages distinctes figurant dans les $\mathrm{\Delta }$ dernières références se terminant à l’instant $t$. Compte chaque page une seule fois, même si elle apparaît plusieurs fois dans la fenêtre. La taille de l’ensemble de travail est un nombre de pages, et non un nombre de références.

Avec une fenêtre de 5 et la chaîne 1, 2, 1, 3, 2, 1, 4, 5, 4, 5, 4, 6, 5, 4, examine l’état après la référence 6. Les cinq dernières références sont 2, 1, 3, 2, 1, ce qui donne {1, 2, 3}, de taille 3. Après la référence 8, la fenêtre est 3, 2, 1, 4, 5, ce qui donne une taille de 5. Après la référence 11, elle est 4, 5, 4, 5, 4, ce qui donne une taille de 2. La demande atteint temporairement un maximum lorsque l’ancienne et la nouvelle phase se chevauchent.

Contrôler la demande active et l’allocation

Une fenêtre courte peut omettre des pages encore nécessaires ; une fenêtre trop longue peut inclure des pages d’une phase terminée. Le modèle de l’ensemble de travail de Peter Denning relie ces besoins changeants à l’allocation. Une politique fondée sur l’ensemble de travail n’exécute les processus que lorsque leurs ensembles de travail réunis tiennent en mémoire. Si ce n’est pas le cas, elle suspend un ou plusieurs processus et libère leurs cadres. C’est le contrôle d’admission.

Le contrôle de la fréquence des défauts de page (PFF) utilise les taux de défauts mesurés. Au-dessus d’un seuil supérieur, un processus a besoin de plus de cadres. En dessous d’un seuil inférieur, certains cadres peuvent être réattribués. Si un processus a besoin de cadres et qu’aucun n’est disponible, il peut être nécessaire de suspendre un processus. Deux seuils réduisent les ajustements continuels autour d’une seule limite.

Avec le remplacement global, un défaut peut évacuer une page d’un autre processus. Cela s’adapte avec souplesse aux changements de demande, mais permet à un processus d’augmenter les défauts d’un autre. Avec le remplacement local, les victimes proviennent uniquement des cadres alloués au processus ayant provoqué le défaut. Cela limite les interférences, mais ne peut pas aider un processus auquel trop peu de cadres ont été attribués sans modifier son allocation.

Choisir des remèdes à la pression sur la mémoire

Les remèdes utiles réduisent la demande ou augmentent la capacité : exécuter moins de programmes, ajouter de la mémoire physique ou améliorer la localité, par exemple en parcourant les tableaux dans leur ordre de stockage. Un espace d’échange plus rapide réduit le coût de chaque défaut majeur ; il ne permet pas à un ensemble actif trop grand de tenir en mémoire. Remplacer un disque par un SSD peut améliorer la progression sans supprimer la cause.

Sous une pression extrême, le tueur de processus en cas de manque de mémoire de Linux peut terminer un processus sélectionné lorsque la récupération et l’échange ne peuvent pas libérer assez de mémoire. La sélection utilise un score tenant compte de la mémoire et des ajustements liés à la politique, et ne se limite pas à identifier le plus gros processus. La mémoire devient récupérable lorsque le processus se termine et son travail est perdu. C’est une libération de ressources en dernier recours, distincte de la suspension d’un processus qui pourra reprendre plus tard.