La fonction de mémorisation - Architecture des Machines et des Systemes Informatiques - page 192

Le principe de fonctionnement est décrit par l'algorithme :
si répertoire contient étiquette
alors
information trouvée;
charger le processeur;
sinon
si répertoire plein
alors
algorithme de remplacement de ligne;
remplir la ligne choisie;
charger le processeur;
sinon
remplir une ligne libre;
charger le processeur;
finsi
finsi
Cette gestion est plus complexe que dans le cas du cache direct. Dans le cas d'un
échec une ligne de mémoire doit être chargée dans le cache mais contrairement au
cache direct on ne connaît pas le numéro de la ligne du cache dans laquelle l'infor-
mation doit être placée. Il faut donc vérifier si le cache est plein, et dans ce cas il faut
exécuter un algorithme permettant de choisir la ligne à remplacer. C'est le cas le plus
défavorable et les performances de l'algorithme sont critiques pour que le cache soit
efficace : ainsi il ne faut pas que l'on remplace la ligne qui va être utilisée immédia-
tement après son remplacement.
Algorithmes de remplacement de lignes
Il existe différents algorithmes de remplacement de lignes. Les principaux sont :
-FIFO ( First In, First Out ) : dans ce cas, la ligne remplacée est la ligne la plus
anciennement chargée ;
-LRU ( Least Recently Used ) : dans ce cas, la ligne remplacée est la ligne la moins
récemment accédée. Cette politique est meilleure que la précédente car elle tient
compte des accès effectués par le processeur au cache, mais elle est coûteuse car
nécessite de maintenir l'ordre des accès réalisés;
-NMRU ( Not MostRecently Used ) : la ligne remplacée n'est pas la plus récem-
ment utilisée. Dans cette politique, la ligne remplacée est une ligne choisie au
hasard dans l'ensemble des lignes du cache, hormis la ligne la plus récemment
accédée.
La dernière politique offre de bonnes performances et est couramment mise en
œuvre dans les caches associatifs.
➤ Cache mixte
Le cache mixte (figure 8.18), utilisé dans certains de nos micro-ordinateurs, utilise
les techniques des deux caches précédents. Le cache est divisé en blocs gérés comme