2.2. L'algorithme LRU
Concernant l'algorithme LRU, on expulse la page dont
l'utilisation est la plus reculée dans le temps. Pour cela, le SE indexe
chaque page par le temps écoulé depuis sa dernière
référence et il constitue une liste chaînée des
pages par ordre décroissant de temps depuis la dernière
référence.
L'algorithme est stable. Mais il nécessite une gestion
coûteuse de la liste qui est modifiée à chaque accès
à une page. Il s'agit cependant d'un algorithme souvent utilisé
car très satisfaisant par ses résultats.
Comme solution d'implémentation de cet algorithme nous
avons :
Ø L'utilisation des compteurs: à chaque
entrée de la table des pages, on ajoute un compteur de temps qui est mis
à jour à chaque accès à la page. Il faut rechercher
sur l'ensemble de la table la victime. De plus, ces temps doivent être
mis à jour quand on change de table de page (celle d'un autre processus
...). On ne peut utiliser le temps réel ... Dans le cadre de SIGEMEC,
nous avons utilisé une matrice de taille n x m où n
représente le nombre de cadres mémoire et m la taille de la
séquence d'appel et à chaque accès à une page,
on modifie les entrées de la matrice correspondantes ;
Ø L'utilisation d'une pile: à chaque fois que
l'on accède à une page, la page est placée en sommet de
pile. Le dessus est toujours la page la plus récemment utilisée
et le fond de la pile la moins récemment utilisée.
Ø L'utilisation des masques : On utilise un octet
associé à chaque page. Le système positionne à 1 le
bit de poids fort à chaque accès à la page. Toutes les N
millisecondes (click d'horloge) le système fait un décalage
à droite de l'octet associé à chaque page. On obtient
ainsi un historique de l'utilisation de la page. L'octet à 00000000
indique que la page n'a pas 'été utilisée depuis 8 cycles,
11111111 indique que la page a été utilisée pendant les 8
cycles. La page de masque 11000100 a été utilisée plus
récemment que 01110111. Si l'on interprète ces octets comme des
entiers non-signés, c'est la page ayant le plus petit octet qui a
été utilisée le moins récemment (l'unicité
des numéros n'étant pas assurée, la sélection entre
numéros identiques se fait avec l'ordre FIFO).
| 
