Remplacement de pages : FIFO, LRU et la politique optimale

La mémoire dispose de quelques cadres, chacun pouvant contenir une page. Le programme demande les pages dans l’ordre de la chaîne de références. Si la page est déjà dans un cadre, l’accès réussit. Sinon, il y a un défaut de page. Lorsque tous les cadres sont occupés, il faut retirer une page : FIFO choisit celle qui a été chargée en premier, LRU celle dont la dernière utilisation est la plus ancienne, et OPT celle dont la prochaine utilisation est la plus lointaine.

Exemple résolu — Remplacement de pages : FIFO, LRU et la politique optimale

Références	12

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Remplacement de pages : FIFO, LRU et la politique optimale

La mémoire est divisée en cadres de même taille, et les données du programme en pages de cette même taille. Chaque page peut donc occuper n’importe quel cadre. La chaîne de références est la suite des pages auxquelles le programme accède. Un accès à une page absente de la mémoire provoque un défaut de page : la page est chargée et, si aucun cadre n’est libre, une politique de remplacement choisit la page à retirer. Une politique présente l’anomalie de Bélády sur une chaîne lorsqu’elle provoque davantage de défauts avec F + 1 cadres qu’avec F cadres.

Ce que signifie chaque symbole

F: le nombre de cadres
n: le nombre de pages de la boucle (exercice résolu)
r: le nombre de parcours de la boucle

Suppose: On utilise la pagination à la demande : une page n’est chargée que lorsqu’elle est demandée. La mémoire est vide au départ ; le premier accès à chaque page provoque donc un défaut, quelle que soit la politique. Si plusieurs pages ne seront plus utilisées, OPT retire ici celle dont le numéro est le plus petit. Chaque référence porte sur une seule page. On ne distingue pas les lectures des écritures, et retirer une page ne coûte rien. Une mise en œuvre exacte de LRU exige de connaître la date de chaque accès à la mémoire. Cet enregistrement étant trop coûteux, les noyaux utilisent des approximations fondées sur un bit de référence par page ; l’algorithme de l’horloge est le plus connu.

Un cadre de plus, un défaut de plus 🖖

Cliquez sur FIFO, 3 cadres, puis sur FIFO, 4 cadres. Pour la chaîne 1 2 3 4 1 2 5 1 2 3 4 5, la mémoire la plus grande subit davantage de défauts : 10 contre 9. Faites avancer les deux simulations jusqu’à l’étape 7, où arrive la page 5. Avec trois cadres, les pages 1 et 2 ont déjà été retirées, puis rechargées. Ce sont donc les plus récemment chargées, et FIFO retire la page 4. Avec quatre cadres, les pages 1 et 2 sont restées en mémoire. La page 1 est alors celle dont le chargement est le plus ancien : FIFO la retire juste avant que le programme ne la demande. Bélády, Nelson et Shedler ont décrit ce phénomène en 1969. Il est rare. Nous avons appliqué FIFO à toutes les chaînes de moins de douze références, quel que soit le nombre de pages : aucune ne présente cette anomalie. Parmi les 4 213 597 chaînes de longueur exactement douze, en comptant comme une seule deux chaînes qui ne diffèrent que par les noms des pages, huit la présentent. Elles commencent toutes par 1 2 3 4 1 2 5 1 et provoquent toutes un seul défaut supplémentaire lorsqu’on passe de trois cadres à quatre. Celle-ci est la seule des huit à ne comporter que cinq pages.

Avec LRU et OPT, ajouter de la mémoire n’augmente jamais le nombre de défauts 🖖

Cliquez sur LRU, 4 cadres : la même chaîne provoque 8 défauts, contre 10 avec trois cadres. Avec F cadres, LRU conserve les F pages utilisées le plus récemment ; avec F + 1 cadres, il conserve ces mêmes pages et une page supplémentaire. À chaque étape, toutes les pages de la petite mémoire sont donc présentes dans la grande. Un accès qui réussit avec trois cadres réussit aussi avec quatre. FIFO conserve les pages chargées le plus récemment. Or le nombre de cadres modifie l’historique des chargements : après l’étape 7, les trois cadres contiennent 1, 2 et 5, tandis que les quatre cadres contiennent 2, 3, 4 et 5. OPT possède la même propriété d’inclusion que LRU. Les politiques qui la vérifient sont appelées algorithmes à pile. Pour elles, le nombre de défauts indiqué dans le tableau sous les résultats n’augmente jamais avec le nombre de cadres. Pour FIFO, il peut augmenter ; la cellule correspondante est alors signalée.

Une boucle qui dépasse la mémoire d’une page met LRU en échec à chaque accès 🖖

Cliquez sur Boucle, LRU : cinq pages sont lues dans l’ordre, trois fois de suite, avec quatre cadres. Chacune des 15 références provoque un défaut, car la page dont la dernière utilisation est la plus ancienne est toujours celle que la boucle demande ensuite. FIFO se comporte exactement de la même façon. Cliquez sur Boucle, OPT : le nombre de défauts tombe à 7. OPT retire la page dont la prochaine utilisation est la plus lointaine. Aux étapes 5 et 9, c’est celle qui vient d’être lue. Pour faire ce choix, OPT doit connaître toute la suite des références. Aucun système d’exploitation ne dispose de cette information. OPT sert donc de référence : il donne le plus petit nombre de défauts qu’une politique puisse atteindre sur cette chaîne. Ajoutez un cinquième cadre à la boucle : les trois politiques provoquent alors 5 défauts, un par page.

Problème entièrement résolu

Quand chaque référence provoque un défaut avec LRU 5 étapes
Cliquez sur Boucle, OPT et repérez les étapes de ses 7 défauts. Considérez ensuite un programme qui calcule la somme des éléments d’un tableau occupant 100 pages, qu’il parcourt 1 000 fois, avec 99 cadres. Combien de défauts LRU provoque-t-il ? Et OPT ? Que se passe-t-il avec un 100ᵉ cadre ?

Ouvrez ce problème dans l'outil
1. Dans la simulation, les cinq premières références provoquent un défaut : quatre remplissent les cadres vides, et la cinquième entraîne le retrait d’une page. Les défauts suivants surviennent aux étapes 9 et 13, espacés de quatre références : 5 + 2 = 7.
  
  $5 + 2 = 7 faults: steps 1 - 5, 9, 13$
2. Avec n − 1 cadres pour une boucle de n pages, une seule page de la boucle est absente de la mémoire. Lors d’un défaut, la page dont la prochaine utilisation est la plus lointaine est celle qui vient d’être lue : elle sera demandée de nouveau après n − 1 références. Au dernier parcours, certaines pages ne seront plus utilisées ; OPT peut alors retirer l’une d’elles. En retirant la page qui vient d’être lue, on conserve en mémoire les pages des n − 2 références suivantes. Le prochain défaut survient donc n − 1 références plus tard.
  
  $n - 1 frames : one fault every n - 1 references$
3. LRU avec 99 cadres : lorsqu’un accès à la page p provoque un défaut, toutes les autres pages sont dans les cadres. Celle dont la dernière utilisation est la plus ancienne est p + 1, précisément celle que la boucle demande ensuite. Chacune des 100 × 1 000 = 100 000 références provoque donc un défaut, comme dans la simulation où les 15 références en provoquaient un. FIFO retire les mêmes pages.
  
  $LRU : 100 \times 1000 = 100000$
4. OPT : les 99 premières références remplissent les cadres. À partir de la 100ᵉ, un défaut survient toutes les 99 références, aux références 100, 199, 298, … Il y en a donc 1 + ⌊(100 000 − 100) / 99⌋ = 1 + 1 009 = 1 010. Le total est de 99 + 1 010 = 1 109, soit n + ⌊n(r − 1)/(n − 1)⌋ avec n = 100 et r = 1 000.
  
  $OPT : 99 + (1 + ⌊ \frac{100 000 - 100}{99} ⌋) = 99 + 1010 = 1109 = n + ⌊ \frac{n ( r - 1 )}{n - 1} ⌋$
5. Avec un 100ᵉ cadre, le tableau tient entièrement en mémoire : chacune des trois politiques provoque 100 défauts, un par page, puis aucun après le premier parcours.
  
  $F = 100 : 100 faults$
Réponse

LRU : 100 000 défauts ; OPT : 1 109 ; avec un cadre supplémentaire : 100. Une boucle qui dépasse la mémoire d’une page est le pire cas pour LRU. Le cadre qui manquait suffit ici à diviser le nombre de défauts par mille.

$LRU 100000, OPT 1109, 100 with one frame more$

Parcours

Ce qu’une structure de données rend peu coûteux

Références (1)

The first insight's date and attribution: the anomaly, and its formal treatment for FIFO: L. A. Belady, R. A. Nelson and G. S. Shedler, "An anomaly in space-time characteristics of certain programs running in a paging machine," Communications of the ACM 12(6), 349–353, June 1969.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.