Scribd
Importer
85 vues7 pages

Algorithmes de Remplacement Cache

Le document traite des algorithmes de remplacement des lignes de cache, nécessaires lors des défauts de page pour gérer l'espace mémoire. Il présente différentes catégories d'algorithmes, notamment l'Optimal et LRU (Least Recently Used), en expliquant leur fonctionnement et leurs principes. L'algorithme LRU, qui remplace la ligne la moins récemment utilisée, est détaillé avec un exemple illustratif de son application dans un cache de 4 lignes.

Transféré par

lorraineanjarasoa
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
85 vues7 pages

Algorithmes de Remplacement Cache

Le document traite des algorithmes de remplacement des lignes de cache, nécessaires lors des défauts de page pour gérer l'espace mémoire. Il présente différentes catégories d'algorithmes, notamment l'Optimal et LRU (Least Recently Used), en expliquant leur fonctionnement et leurs principes. L'algorithme LRU, qui remplace la ligne la moins récemment utilisée, est détaillé avec un exemple illustratif de son application dans un cache de 4 lignes.

Transféré par

lorraineanjarasoa
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithmes de remplacement des

lignes de cache
Lorsqu'un défaut de page se produit, il faut
amener la page manquante en mémoire
centrale. S'il y a de la place pour elle, il
suffit de la charger. S'il n'y a pas de place, il
faut en libérer une, et le choix de la victime
est réalisé par l‘un des algorithmes de
remplacement
Il existe différents types de mémoire cache, dont l'organisation
amène des situations où une ligne de la mémoire principale est
mappée sur un ensemble de lignes de mémoire cache remplie. Il faut
donc choisir la ligne de mémoire cache qui sera remplacée par la
nouvelle ligne. Cette sélection est réalisée par les algorithmes de
remplacement de lignes de cache. Le principe de fonctionnement de
la majorité de ces algorithmes repose sur le principe de localité. Ces
algorithmes sont en général divisés en deux grandes catégories :
 les algorithmes dépendants de l'utilisation des données: LRU, etc.
 les algorithmes indépendants de l'utilisation des
données : aléatoire, FIFO.
Algorithme optimal
Cet algorithme, formalisé par L.A. Belady, utilise la mémoire
cache de manière optimale : il remplace la ligne de mémoire
cache qui ne sera pas utilisée pour la plus grande période de
temps. Par conséquent, cet algorithme doit connaître les
accès futurs afin de désigner la ligne à évincer. Cela est donc
impossible à réaliser dans un système réel mais constitue
néanmoins un excellent moyen afin de mesurer l'efficacité
d'un algorithme de remplacement en fournissant une
référence.
LRU (Least Recently Used)
Cet algorithme remplace la ligne utilisée le moins
récemment. L'idée sous-jacente est de garder les
données récemment utilisées, conformément
au principe de localité. Tous les accès aux différentes
lignes de la mémoire cache sont enregistrés ; ce qui
explique que cet algorithme coûte cher en termes
d'opérations de traitement de liste. De plus, ce coût, qui
est un élément vital des systèmes
embarqués notamment, augmente exponentiellement
avec le nombre de voies de la mémoire cache.
Principes
La gestion du remplacement des lignes dans les caches passe par l’utilisation
d’une pile. Dans cette pile figurant les numéros des lignes classés suivant la date
de leur dernière utilisation.
En sommet de pile se trouve le numéro de la ligne la plus récemment utilisée (Most
Recently Used) et en fond de pile la moins récemment utilisée (Least Recently
Used).
Lorsqu’on fait référence à une ligne, son numéro est rangé en sommet de pile.

Algorithme LRU
Cette première méthode, intuitivement la plus naturelle, consiste :
• Lors d’un Miss:
• À remplacer le contenu de la ligne la plus anciennement référencée par celle lue en mémoire
• À mettre en sommet de pile le N° de cette ligne et décaler tous les autres;
• Lors d’un Hit, à amener le N° de ligne référencée au sommet de pile.
Exemple :
Considérons :
• Un cache constitué de 4 lignes notées 1,2,3 et 4
• Et a, b, c, d,…. Les étiquettes des adresses référencées

La pile de gestion d’ancienneté est représentée verticalement et les


lignes du cache horizontalement. On s’intéresse au comportement
de ce cache après qu’il ait reçu la séquence initiale (a, b, c, d).
Supposons que les références qui vont se succéder forme la
séquence (b, c, e).

Vous aimerez peut-être aussi