Gestion de la mémoire

Un programme compilé contient des adresses. Si ces adresses étaient celles de la mémoire physique, deux programmes ne pourraient pas coexister sans se piétiner, il faudrait recompiler un programme pour le charger ailleurs, et rien n'empêcherait l'un de lire les données de l'autre.

Le système résout les trois problèmes d'un coup en interposant une traduction : le programme manipule des adresses logiques, le matériel les convertit en adresses physiques. C'est le sujet de ce chapitre, et c'est aussi son point difficile — la conversion d'une adresse logique en adresse physique se travaille par des exercices systématiques, pas par la lecture d'un schéma. Prévoyez d'en faire beaucoup.

Allocation contiguë et fragmentation

La première idée est de donner à chaque processus un bloc de mémoire d'un seul tenant. Le matériel n'a alors besoin que de deux registres, chargés au changement de contexte : un registre de base, ajouté à chaque adresse logique, et un registre de limite, qui provoque une exception si l'adresse la dépasse. Relocation et protection en deux additions.

Le problème arrive avec les départs. Les processus se terminent en laissant des trous ; les trous ne sont pas au bon endroit. On peut avoir 500 Mio libres au total et être incapable de loger un processus de 100 Mio parce que le plus grand trou en fait 80. C'est la fragmentation externe.

Trois stratégies de placement se disputent le choix du trou, et leur classement est contre-intuitif. Le premier ajustement prend le premier trou assez grand : rapide, et en pratique le meilleur. Le meilleur ajustement prend le plus petit trou suffisant : plus lent, et il produit une poussière de trous minuscules inutilisables. Le pire ajustement prend le plus grand : il laisse des restes exploitables mais détruit vite les grands trous.

On peut compacter — déplacer les processus pour réunir les trous — mais c'est coûteux et impossible si le programme contient des adresses physiques déjà calculées. La vraie solution est ailleurs : cesser d'exiger que la mémoire d'un processus soit d'un seul tenant.

La pagination

On découpe la mémoire logique en pages et la mémoire physique en cadres, tous de la même taille — typiquement 4 Kio. Une page quelconque peut aller dans un cadre quelconque, et une table des pages, propre à chaque processus, note où chacune se trouve.

La fragmentation externe disparaît : tout trou est un cadre, donc utilisable. Il reste une fragmentation interne, la partie inutilisée de la dernière page — en moyenne une demi-page par processus, soit 2 Kio, un prix dérisoire.

Le découpage de l'adresse

C'est ici qu'il faut ralentir. Une adresse logique n'est pas un couple à calculer : c'est un simple nombre, que le matériel lit en deux morceaux.

1Adresse logique sur 32 bits, pages de 4 Kio (2¹² octets)2 3 31                                   12 11                    04┌───────────────────────────────────────┬───────────────────────┐5│        numéro de page   (20 bits)     │  déplacement (12 bits)│6└───────────────────────────────────────┴───────────────────────┘

La taille de page fixe le découpage, et rien d'autre : $4\,\text{Kio} = 2^{12}$, donc 12 bits de déplacement, et les 20 bits restants numérotent $2^{20}$ pages.

La traduction se fait en trois gestes :

11. numéro de page  = adresse ÷ taille_page        (les bits de poids fort)22. déplacement     = adresse mod taille_page      (les bits de poids faible)33. adresse physique = table[numéro] × taille_page + déplacement

Le point que tout le monde manque au premier essai : le déplacement n'est jamais traduit. Il traverse la conversion inchangé, parce qu'une page et un cadre ont la même taille — le $k$-ième octet d'une page est le $k$-ième octet de son cadre. Seul le numéro change.

Déroulons un exemple complet, avec des pages de 4 Kio et une table qui dit que la page 2 est dans le cadre 7 :

1adresse logique   900029000 ÷ 4096 = 2   reste 8083                  ↳ page 2, déplacement 8084 5table[2] = cadre 76 7adresse physique  7 × 4096 + 808 = 29 480

Un contrôle qui évite bien des erreurs : le déplacement doit toujours être strictement inférieur à la taille de page. S'il ne l'est pas, la division a été faite avec la mauvaise taille.

Le coût, et la TLB

La table des pages est en mémoire. Chaque accès du programme en demande donc deux : un pour lire la table, un pour l'octet voulu. La mémoire est deux fois plus lente, ce qui est inacceptable.

D'où le tampon de traduction (TLB), petit cache totalement associatif — au sens du chapitre 7 d'architecture — qui garde les traductions récentes. Grâce à la localité, quelques dizaines d'entrées suffisent à obtenir plus de 98 % de succès : la quasi-totalité des accès se traduisent sans toucher la table.

Le TLB est vidé à chaque changement de contexte, puisque les traductions appartiennent au processus sortant. C'est un coût caché du chapitre 4, qui s'ajoute à la sauvegarde des registres — et l'une des raisons pour lesquelles un quantum trop court est ruineux.

Enfin, la table elle-même est un problème : $2^{20}$ entrées par processus, à 4 octets, font 4 Mio de table pour un programme qui n'utilise peut-être que quelques pages. On la découpe donc en plusieurs niveaux, ce qui permet de ne matérialiser que les branches réellement employées.

Segmentation

La pagination découpe selon une taille arbitraire, qui ne correspond à rien dans le programme. La segmentation découpe selon la structure logique : un segment pour le code, un pour les données, un pour la pile, un par bibliothèque partagée. Une adresse y est un couple (numéro de segment, déplacement), et chaque segment porte sa propre longueur et ses propres droits.

L'avantage est la protection fine et le partage naturel : marquer le segment de code en lecture seule, ou le rendre visible à plusieurs processus, devient trivial. Le défaut est que les segments sont de tailles différentes — donc la fragmentation externe revient.

D'où la combinaison retenue par les architectures réelles : segmenter puis paginer. Le programme voit des segments, chacun est découpé en pages, et les pages vont dans des cadres quelconques. On garde la protection du premier et l'absence de fragmentation du second.

Mémoire virtuelle

Dernier étage, et le plus rentable. Rien n'oblige à ce que toutes les pages d'un processus soient en mémoire. Chaque entrée de la table porte un bit de présence ; les pages absentes sont sur le disque.

Toucher une page absente déclenche un défaut de page, qui est une exception matérielle, pas une erreur du programme. Le système la traite : il choisit un cadre libre — ou en libère un —, lit la page depuis le disque, met à jour la table, et réexécute l'instruction fautive, qui réussit cette fois. Le processus n'a rien vu, sinon qu'il a été bloqué au sens du chapitre 3 pendant plusieurs millisecondes.

Trois bénéfices, considérables. Un programme peut être plus grand que la mémoire physique. Le chargement à la demande ne lit que ce qui sert réellement, donc le démarrage est immédiat. Et plusieurs processus partagent les cadres du même code en lecture seule — les trois éditeurs du chapitre 3 ne coûtent qu'une copie.

Le coût est brutal, et c'est le chiffre à retenir : un accès mémoire prend 60 ns, un défaut de page 10 ms sur un disque magnétique, soit cent mille fois plus. Un taux de défaut de un pour mille suffit à doubler le temps moyen d'accès. C'est pourquoi la mémoire virtuelle n'est viable que si les défauts sont rarissimes — ce que la localité du chapitre 7 d'architecture rend possible.

Quand elle ne l'est plus, le système s'écroule (thrashing). Trop de processus, pas assez de cadres : chacun passe son temps à provoquer des défauts, le disque sature, l'utilisation du processeur s'effondre. Le piège est que l'ordonnanceur, voyant le processeur inoccupé, admet davantage de processus — et aggrave exactement le problème. La parade est la notion d'ensemble de travail : l'ensemble des pages qu'un processus utilise réellement dans une fenêtre de temps récente. Tant que la somme des ensembles de travail tient en mémoire, tout va bien ; dès qu'elle déborde, il faut suspendre un processus entier plutôt que d'en admettre un de plus.

Choisir la victime

Reste la question la plus concrète : quelle page évincer ? La même qu'au chapitre 7 d'architecture pour le cache, mais avec un enjeu cent mille fois supérieur.

FIFO évince la plus anciennement chargée. Simple, et mauvais : l'ancienneté du chargement ne dit rien de l'utilité, et une page chargée tôt mais utilisée en permanence sera sacrifiée.

Optimal évince celle dont la prochaine utilisation est la plus lointaine. Il est démontrablement le meilleur, et irréalisable — il faudrait connaître l'avenir. Il sert d'étalon : un algorithme réel se juge à son écart avec lui.

LRU évince la moins récemment utilisée. C'est le pari sur la localité temporelle, et il approche l'optimal de près. Sa version exacte coûte cher — il faudrait horodater chaque accès —, donc on l'approche : le matériel maintient un simple bit de référence par page, mis à 1 à chaque accès, et l'algorithme dit de la seconde chance parcourt les pages en cercle, remet à 0 les bits qu'il trouve à 1, et évince la première page dont le bit était déjà à 0.

Enfin, une bizarrerie de FIFO qui achève de le disqualifier : l'anomalie de Belady. Sur certaines suites de références, augmenter le nombre de cadres augmente le nombre de défauts. La suite 1 2 3 4 1 2 5 1 2 3 4 5 produit 9 défauts sur trois cadres et 10 sur quatre. LRU et l'optimal n'ont pas ce défaut.

À vous

L'exercice attaque le point qui coince de front. Première partie : la traduction d'adresses, avec une table donnée, sur une série de cas dont certains doivent produire une exception — déplacement hors bornes, page absente, page en lecture seule écrite.

Seconde partie : les trois algorithmes de remplacement sur la même suite de références, avec le comptage des défauts. Puis la vérification de l'anomalie de Belady, en faisant varier le nombre de cadres de 3 à 5 — et en constatant que la courbe de FIFO n'est pas monotone, alors que celle de LRU l'est.

// ── 1. Traduction d'adresses ──────────────────────────────────────────────
const TAILLE_PAGE = 1024;            // 1 Kio, donc 10 bits de déplacement

// Une entrée de table : le cadre, la présence, les droits.
const TABLE = [
  { cadre: 5, present: true,  ecriture: false },   // page 0 : code, lecture seule
  { cadre: 9, present: true,  ecriture: true  },   // page 1 : données
  { cadre: 2, present: false, ecriture: true  },   // page 2 : sur le disque
  { cadre: 7, present: true,  ecriture: true  },   // page 3
];

function traduire(adresseLogique, ecrit = false) {
  const page = 0;          // ← à écrire
  const deplacement = 0;   // ← à écrire

  if (page >= TABLE.length) return { erreur: "hors de l'espace d'adressage" };
  const e = TABLE[page];
  if (!e.present) return { erreur: "DÉFAUT DE PAGE sur la page " + page };
  if (ecrit && !e.ecriture) return { erreur: "violation : écriture en lecture seule" };

  return { page, deplacement, cadre: e.cadre, physique: 0 };   // ← à écrire
}

const CAS = [
  { a: 3500, ecrit: false },   // page 3, déplacement 428 -> 7 x 1024 + 428
  { a: 0,    ecrit: false },
  { a: 1023, ecrit: false },   // dernier octet de la page 0
  { a: 1024, ecrit: false },   // premier octet de la page 1
  { a: 500,  ecrit: true  },   // écriture en lecture seule
  { a: 2100, ecrit: false },   // page absente
  { a: 9000, ecrit: false },   // au-delà de la table
];

for (const c of CAS) {
  const r = traduire(c.a, c.ecrit);
  console.log(String(c.a).padStart(5) + (c.ecrit ? " (écriture)" : "           ") + " -> " +
    (r.erreur ?? "page " + r.page + ", dépl. " + String(r.deplacement).padStart(4) +
                 ", cadre " + r.cadre + "  =>  physique " + r.physique));
}

// ── 2. Remplacement de pages ──────────────────────────────────────────────
const SUITE = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];

function fifo(suite, cadres) {
  const memoire = [];
  let defauts = 0;
  for (const page of suite) {
    if (memoire.includes(page)) continue;
    defauts++;
    if (memoire.length === cadres) memoire.shift();   // le plus ancien CHARGÉ
    memoire.push(page);
  }
  return defauts;
}

function lru(suite, cadres) { return 0; }        // ← à écrire
function optimal(suite, cadres) { return 0; }    // ← à écrire

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Complétez traduire() : numéro de page, déplacement, adresse physique.
// 2. Écrivez lru (évincer la moins récemment UTILISÉE) et optimal (évincer
//    celle dont la prochaine utilisation est la plus lointaine).
// 3. Faites varier le nombre de cadres de 3 à 5 et cherchez l'anomalie de
//    Belady : chez qui la courbe n'est-elle pas décroissante ?

for (const c of [3, 4, 5]) console.log(c + " cadres : FIFO " + fifo(SUITE, c) + " défauts");

const TAILLE_PAGE = 1024;

const TABLE = [
  { cadre: 5, present: true,  ecriture: false },
  { cadre: 9, present: true,  ecriture: true  },
  { cadre: 2, present: false, ecriture: true  },
  { cadre: 7, present: true,  ecriture: true  },
];

function traduire(adresseLogique, ecrit = false) {
  // Les bits de poids fort numérotent la page, ceux de poids faible donnent
  // le déplacement. Avec une taille de page en puissance de 2, division et
  // modulo sont un simple découpage de bits — c'est pourquoi la taille de
  // page EST une puissance de 2.
  const page = Math.floor(adresseLogique / TAILLE_PAGE);
  const deplacement = adresseLogique % TAILLE_PAGE;

  if (page >= TABLE.length) return { erreur: "hors de l'espace d'adressage" };
  const e = TABLE[page];
  if (!e.present) return { erreur: "DÉFAUT DE PAGE sur la page " + page };
  if (ecrit && !e.ecriture) return { erreur: "violation : écriture en lecture seule" };

  // Le déplacement traverse INCHANGÉ : page et cadre ont la même taille.
  return { page, deplacement, cadre: e.cadre, physique: e.cadre * TAILLE_PAGE + deplacement };
}

const CAS = [
  { a: 3500, ecrit: false }, { a: 0, ecrit: false }, { a: 1023, ecrit: false },
  { a: 1024, ecrit: false }, { a: 500, ecrit: true }, { a: 2100, ecrit: false },
  { a: 9000, ecrit: false },
];

for (const c of CAS) {
  const r = traduire(c.a, c.ecrit);
  console.log(String(c.a).padStart(5) + (c.ecrit ? " (écriture)" : "           ") + " -> " +
    (r.erreur ?? "page " + r.page + ", dépl. " + String(r.deplacement).padStart(4) +
                 ", cadre " + r.cadre + "  =>  physique " + r.physique));
}

const SUITE = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];

function fifo(suite, cadres) {
  const memoire = [];
  let defauts = 0;
  for (const page of suite) {
    if (memoire.includes(page)) continue;
    defauts++;
    if (memoire.length === cadres) memoire.shift();
    memoire.push(page);
  }
  return defauts;
}

function lru(suite, cadres) {
  const memoire = [];   // du moins récemment utilisé au plus récent
  let defauts = 0;
  for (const page of suite) {
    const i = memoire.indexOf(page);
    if (i !== -1) {
      // Un SUCCÈS met à jour l'ordre : c'est toute la différence avec FIFO,
      // qui ne regarde que l'instant du chargement.
      memoire.splice(i, 1);
      memoire.push(page);
      continue;
    }
    defauts++;
    if (memoire.length === cadres) memoire.shift();
    memoire.push(page);
  }
  return defauts;
}

function optimal(suite, cadres) {
  const memoire = [];
  let defauts = 0;
  for (let t = 0; t < suite.length; t++) {
    const page = suite[t];
    if (memoire.includes(page)) continue;
    defauts++;
    if (memoire.length === cadres) {
      // On regarde l'AVENIR : la victime est celle dont la prochaine
      // utilisation est la plus lointaine, ou qui ne reviendra jamais.
      let victime = 0, plusLoin = -1;
      for (let i = 0; i < memoire.length; i++) {
        let prochain = suite.indexOf(memoire[i], t + 1);
        if (prochain === -1) { victime = i; break; }
        if (prochain > plusLoin) { plusLoin = prochain; victime = i; }
      }
      memoire.splice(victime, 1);
    }
    memoire.push(page);
  }
  return defauts;
}

console.log("");
console.log("cadres |  FIFO |  LRU  | optimal");
for (const c of [3, 4, 5, 6]) {
  console.log(String(c).padStart(6) + " | " +
    String(fifo(SUITE, c)).padStart(5) + " | " +
    String(lru(SUITE, c)).padStart(5) + " | " +
    String(optimal(SUITE, c)).padStart(7));
}
// Regardez la colonne FIFO entre 3 et 4 cadres : 9 puis 10. Ajouter de la
// mémoire a AUGMENTÉ le nombre de défauts. C'est l'anomalie de Belady, et
// elle vient de ce que FIFO ne garantit pas l'inclusion : l'ensemble des
// pages présentes avec 4 cadres n'est pas un sur-ensemble de celui à 3.
// LRU et l'optimal ont cette propriété d'inclusion, donc leur courbe est
// toujours décroissante.

En travaux pratiques

terminal 1 : &compteur = 0x55d3e8a04010, valeur 42
terminal 2 : &compteur = 0x55d3e8a04010, valeur 7

même adresse VIRTUELLE, deux adresses PHYSIQUES différentes

cat /proc/self/maps

55d3e8a01000-55d3e8a02000 r-xp   /usr/bin/monprog     ← code, exécutable
55d3e8a03000-55d3e8a04000 r--p   /usr/bin/monprog     ← constantes
55d3e8a04000-55d3e8a05000 rw-p   /usr/bin/monprog     ← données globales
55d3e9c1f000-55d3e9c40000 rw-p   [heap]               ← le tas, malloc
7f2c4a000000-7f2c4a028000 r-xp   /lib/libc.so.6
7ffd3c5e0000-7ffd3c601000 rw-p   [stack]              ← la pile

malloc(1 Go)                → mémoire résidente : 1,3 Mo
puis 1 octet toutes les 4 Ko → mémoire résidente : 1,0 Go

/* malloc ne fait que réserver un intervalle d'adresses.
 La page physique est allouée au PREMIER ACCÈS,
 par un défaut de page. */

défaut MINEUR : la page existe en mémoire, il manque juste
              l'entrée dans la table → ~1 µs
défaut MAJEUR : la page doit être lue sur le DISQUE → ~5 ms

/usr/bin/time -v ./monprog
Minor page faults: 262 144
Major page faults: 3

mémoire libre décroissante, tout va bien… puis :

si  in   out          cpu
0  0     0      95 % utilisateur
0  0     0      93 %
128 4 096 12 288  8 % utilisateur, 91 % en attente d'E/S
                ← le système ne calcule plus, il pagine

l'effondrement n'est pas progressif : il est brutal

read  : 0,84 s   (copie noyau → tampon utilisateur)
mmap  : 0,31 s   (pas de copie : le fichier EST la mémoire)

après fork :
père : &x = 0x7ffd… valeur 42
fils : &x = 0x7ffd… valeur 42      ← même adresse, MÊME page physique
fils modifie x = 99
père : 42   |   fils : 99          ← la page a été DUPLIQUÉE à l'écriture

Ce que la suite en fait

Le bloc V descend d'un cran. La mémoire virtuelle de ce chapitre suppose un disque où ranger les pages absentes ; le chapitre 7 explique comment ce disque est organisé, et le chapitre 8 comment on lui parle.

Le lien est plus étroit qu'il n'y paraît. Le fichier projeté en mémoire, que le chapitre 7 présentera, applique la mécanique de la pagination à un fichier ordinaire : on l'ouvre, on obtient une plage d'adresses, et les lectures disque se font toutes seules par défaut de page. Le système de fichiers et la mémoire virtuelle sont deux visages du même mécanisme.

À retenir