6.6.3 Política LRU

De acuerdo al principio de localidad temporal en las referencias (es más probable la
referencia a una página cuanto más recientemente se haya referenciado), se
selecciona como página víctima la  menos recientemente referenciada. Nótese que ello
implica modificar en cada referencia la información acerca de las páginas cargadas, a
diferencia del algoritmo FIFO, que sólo requiere hacerlo en la carga de cada página.
Esta característica hace de LRU un  algoritmo de pila. Los algoritmos de pila
presentan la propiedad de que, dada una secuencia de referencias, una memoria con
más marcos de página, tras un número determinado de referencias, mantiene el
conjunto de páginas que contendría con un tamaño menor en la misma referencia. En
otras palabras, la tasa de fallos nunca aumenta si  se incrementa el tamaño de
memoria. Los algoritmos de pila evitan la anomalía de Belady.
La implementación hardware de la política LRU es compleja. Hay dos mecanismos:
(a) Mantener una lista encadenada de páginas ordenadas por el tiempo de su
última referencia.
(b) Mantener un contador de referencias y un registro (de al menos 64 bits)
asociado a cada marco de página, que se actualiza en una referencia con el
valor del contador.
En ambos casos la implementación es muy costosa, por lo que, como alternativa al
algoritmo LRU puro se utilizan aproximaciones. Un mecanismo de aproximación
consiste en almacenar el tick de reloj en el que se produce la referencia en vez de la
propia referencia, para lo que se requiere un bit de referencia asociado a cada marco
en base al cual la rutina de atención al reloj puede determinar si la página ha sido referenciada desde el tick anterior y actualizar el registro de ticks de última


referencia a la página, que puede implementarse por software. Con esta
aproximación se pierde precisión, al convertir la relación de orden total entre las
referencias en una relación de orden parcial (las referencias dentro de un mismo tick
no están ordenadas).
Algunos de los siguientes algoritmos también son aproximaciones a LRU.