Politique de remplacement de cache qui évince la donnée inutilisée depuis le plus longtemps. Elle exploite bien la localité temporelle, mais une gestion exacte est difficile avec de nombreuses voies, d'où l'usage d'approximations.
Nom japonais: LRU(Least Recently Used)
« LRU (Least Recently Used) » apparaît dans 6 questions d'entraînement réparties sur 2 thèmes, dont Hiérarchie mémoire, Système d'exploitation et matériel.
Domaine: Hiérarchie mémoire
Réponse : B. 5
En suivant l’ordre : A (défaut, [A]), B (défaut, [A,B]), A (succès, A devient le plus récent), C (défaut, éviction de B, le plus ancien, [A,C]), B (défaut, éviction de A, le plus ancien, [C,B]), A (défaut, éviction de C, le plus ancien, [B,A]) ; on obtient 5 défauts. Le résultat 4 provient par exemple de l’hypothèse erronée que A est évincé à l’insertion de C ; en LRU, il est essentiel que A, ayant fait l’objet d’un succès, soit devenu le plus récent. Le résultat 6 néglige le succès du troisième accès à A.
Réponse : B. Elle est irréalisable, mais sert de référence en donnant la borne inférieure du nombre de défauts des autres politiques
Le remplacement optimal (OPT de Belady) suppose connu l’ordre des accès futurs et évince la donnée dont la prochaine utilisation est la plus lointaine ; le nombre de défauts est alors théoriquement minimal. Le matériel réel ne pouvant connaître les accès futurs, cette politique est irréalisable ; on l’applique à des séquences d’accès enregistrées pour évaluer à quel point LRU ou d’autres politiques approchent l’optimum. Les données évincées différant de celles de LRU, le nombre de défauts est en général différent.
Le résultat 4 provient par exemple de l’hypothèse erronée que A est évincé à l’insertion de C ; en LRU, il est essentiel que A, ayant fait l’objet d’un succès, soit devenu le plus récent.
Un cache totalement associatif de 2 lignes avec remplacemen…Le matériel réel ne pouvant connaître les accès futurs, cette politique est irréalisable ; on l’applique à des séquences d’accès enregistrées pour évaluer à quel point LRU ou d’autres politiques approchent l’optimum.
Par opposition à LRU, qui évince l’élément inutilisé depuis…Un LRU exact exige de mettre à jour l’ordre à chaque accès, ce qui est coûteux avec beaucoup de pages.
Dans l’algorithme de remplacement de page de l’horloge (sec…Elle ne se produit pas avec des algorithmes comme LRU, où l’ensemble des pages conservées avec plus de pages contient toujours l’ensemble précédent (algorithmes à pile).
Avec le remplacement de page FIFO, augmenter le nombre de p…La validité d’une ligne est indiquée par le bit de validité, et l’ordre des accès est géré par les informations de remplacement telles que LRU.
Dans un cache à écriture différée, quel est le rôle du bit …Écroulement (thrashing) Copie sur écriture (copy-on-write) Ligne de cache Allocation en écriture (write allocate) Blocage de boucle (loop blocking) Cache associatif par ensembles Cache entièrement associatif Cache non bloquant Correspondance directe (direct-mapped) Défaut de capacité (capacity miss)