¿Cómo funciona el caché LRU?

Las instrucciones y / o cachés de datos totalmente asociativos reales son raros, a veces ocultos como búfer de bucle, combinando buffers de escritura ...

Lo que es común es tener de 2 a 16 formas de cachés asociativas con conjuntos. Hasta 4 formas, la verdadera LRU es posible, más allá de eso, generalmente se usa la pseudo-LRU.

Hay pocas ventajas de ir más allá de las 4-8 formas para una caché de CPU L1 / L2. Se pueden necesitar más formas en los cachés L2-L3 compartidos entre varias CPU.

Para 4 LRU verdaderas, hay 24 combinaciones posibles: 1-2-3-4, 1-2-4-3, 1-3-2-4 ... etc. Puede almacenarse como un 5 Código de bits que indica directamente la forma menos recientemente utilizada.

Creo que necesitas una estructura de datos "de pila". Esto le dará o (log n) o o (1) rendimiento para insertar una nueva referencia de página (dependiendo de la implementación) y le dará o (log n) tiempo para eliminar la página más antigua. El tiempo para encontrar la página más antigua es o (1) (siempre está en la parte superior del montón).

enlace

Una forma directa de hacer esto es mantener las líneas de caché en una lista circular con doble enlace. Esto permitiría mover una línea a la cabecera de la lista (utilizada más recientemente) y encontrar la cola de la lista (usada menos recientemente) como operaciones O (1).

Lamentablemente, mover una línea al encabezado de la lista, asumiendo que los enlaces se mantienen en memorias de bloque de algún tipo, requiere un mínimo de aproximadamente 4 ciclos de reloj (una lectura y tres escrituras), lo que podría ralentizar los accesos a su caché. a menos que encuentre una manera de desacoplar esta actividad de la actividad de la CPU.