Algoritmo LRU en algoritmo de reemplazo de página

Tres algoritmos comunes de reemplazo de páginas: primero en entrar, primero en salir, LFU y LRU.

Referencia:

Algoritmo de almacenamiento en caché (algoritmo de reemplazo de página)-LRU LFU FIFO

El algoritmo LRU (menos utilizado recientemente) elimina datos según los registros de acceso históricos de los datos. La idea central es que si no se ha accedido a un dato recientemente, es poco probable que se acceda a él en el futuro. Es decir, cuando el espacio limitado se llena con datos, se deben eliminar aquellos a los que no se ha accedido durante más tiempo.

Supongamos que la secuencia es 4 3 4 2 3 1 4 2.

Hay tres bloques físicos.

Primera ronda 4 llamadas a la memoria 4

Ronda secundaria 3 llamadas a la memoria 3 4

Luego 4 llamadas a la memoria 4 3

Luego 2 llama a la memoria 2 4 3

Después de eso, 3 llama a la memoria 3 2 4

Luego transfiere 1 a la memoria 1 3 2 (4 se descarta porque es el que menos se usa).

Después de eso, se transferirá a la memoria 4 1 3 (el principio es el mismo que el anterior).

Finalmente, 2 se transfiere a la memoria 2 4 1.

Si diseñamos una estructura de datos para el caché LRU, debería admitir dos operaciones:

Una es usar una matriz para almacenar cada elemento de datos y luego asociar una marca de tiempo con cada clave. están asociados y se mantiene una marca de tiempo máxima en la caché. Los puntos de diseño son los siguientes:

El otro es la estructura de datos que usa hashmap + lista doblemente enlazada, y los puntos de diseño son los siguientes:

Comparando las dos ideas de diseño anteriores En la sección, no es difícil encontrar que 1 El diseño requiere mantener una marca de tiempo para cada clave, y la complejidad temporal de las operaciones de configuración y obtención es O (n). Obviamente, a medida que aumenta la cantidad de datos, las operaciones de configuración y obtención se vuelven cada vez más lentas. En el Diseño 2, al usar hashmap + lista vinculada, la complejidad temporal de las operaciones establecer y obtener es solo O (1). La implementación específica del Diseño 2 es la siguiente.

Los resultados de ejecución son los siguientes:

Referencia:

Caché LRU

Principio de LRU e implementación de Redis: preguntas de la entrevista de Toutiao

p>