Algoritmo LRU(Least-Recently-Used)

Gráficas comparativas Ver un algoritmo paso a paso Realización de ejercicios
Se saca la página que hace más tiempo que no ha sido referenciada. Se fundamenta en el hecho de que las referencias que están próximas en el tiempo también lo están en el espacio.

Es un algorimo de los llamados de "Pila", que cumple que el número de páginas que hay en memoria para n celdas es siempre un subconjunto de las páginas que estarían en memoria con n+1 celdas.

Se implementa con una lista enlazada con la página que hace más que no se referencia al final. Si una página se referencia se vuelve a colocar arriba de la lista. También se puede implementar con registros de envejecimiento, contadores, etc.

Ventajas

Es uno de los mejores y, al contrario que el FIFO, no tiene la Anomalía de Belady.

Inconvenientes

Es muy difícil de implementar, y necesita hardware especial, ya que el coste de realizarlo por software es excesivo: requiere una actualización de la lista por cada referencia a memoria.

Ejemplo:


Gráficas comparativas Ver un algoritmo paso a paso Realización de ejercicios