Políticas de reemplazo de caché

En informática, las políticas de reemplazo de caché (también conocidas como algoritmos de reemplazo de caché o algoritmos de caché) son instrucciones o algoritmos de optimización que un programa de computadora o hardware- La estructura mantenida puede utilizarse para gestionar un caché de información. El almacenamiento en caché mejora el rendimiento al mantener elementos de datos recientes o de uso frecuente en ubicaciones de memoria cuyo acceso es más rápido o computacionalmente más económico que los almacenes de memoria normales. Cuando el caché está lleno, el algoritmo debe elegir qué elementos descartar para dejar espacio para nuevos datos.

Descripción general

El tiempo promedio de referencia de la memoria es

${\displaystyle T=m\times T_{m}+T_{h}+E}$

dónde

${\displaystyle m}$ = ratio de faltas = 1 - (proporción de la partida)

${\displaystyle T_{m}$ = tiempo para hacer acceso a la memoria principal cuando hay una falta (o, con un caché multinivel, tiempo promedio de referencia de memoria para el caché más bajo)

${\displaystyle T_{h}$= latencia: tiempo para hacer referencia al caché (debe ser el mismo para golpes y faltas)

${\displaystyle E}$ = efectos secundarios, como los efectos en los sistemas multiprocesadores

Un caché tiene dos factores principales de mérito: latencia y tasa de aciertos. Varios factores secundarios también afectan el rendimiento de la caché.

La tasa de aciertos de un caché describe la frecuencia con la que se encuentra un elemento buscado. Las políticas de reemplazo más eficientes rastrean más información de uso para mejorar la tasa de aciertos para un tamaño de caché determinado. La latencia de un caché describe cuánto tiempo después de solicitar un elemento deseado, el caché puede devolver ese elemento cuando hay un resultado. Las estrategias de reemplazo más rápidas generalmente rastrean menos información de uso (o, con una caché asignada directamente, ninguna información) para reducir el tiempo necesario para actualizar la información. Cada estrategia de reemplazo es un compromiso entre la tasa de aciertos y la latencia.

Las mediciones de la tasa de aciertos generalmente se realizan en aplicaciones de referencia y la tasa de aciertos varía según la aplicación. Las aplicaciones de transmisión de video y audio a menudo tienen una tasa de aciertos cercana a cero, porque cada bit de datos en la transmisión se lee una vez (un error obligatorio), se usa y luego nunca se lee ni se escribe nuevamente. Muchos algoritmos de caché (particularmente LRU) permiten que la transmisión de datos llene el caché, eliminando información que pronto se volverá a utilizar (contaminación del caché). Otros factores pueden ser el tamaño, el tiempo de obtención y el vencimiento. Dependiendo del tamaño de la caché, es posible que no sea necesario ningún algoritmo de almacenamiento en caché adicional para descartar elementos. Los algoritmos también mantienen la coherencia de la caché cuando se utilizan varias cachés para los mismos datos, como cuando varios servidores de bases de datos actualizan un archivo de datos compartido.

Políticas

Anomalía de Bélády en los algoritmos de reemplazo de páginas

El algoritmo de almacenamiento en caché más eficiente sería descartar información que no sería necesaria durante mucho tiempo; esto se conoce como algoritmo óptimo de Bélády, política de reemplazo óptima o algoritmo clarividente. Dado que generalmente es imposible predecir hasta qué punto en el futuro se necesitará información, esto es inviable en la práctica. El mínimo práctico se puede calcular después de la experimentación y se puede comparar la efectividad de un algoritmo de caché elegido.

Cuando ocurre un error de página, hay un conjunto de páginas en la memoria. En el ejemplo, el cuadro 1, el cuadro 2 y el cuadro 3 acceden a la secuencia de 5, 0, 1 respectivamente. Cuando se accede a 2, reemplaza el valor 5 (que está en el cuadro 1, prediciendo que no se accederá al valor 5 en un futuro próximo. Debido a que un sistema operativo de propósito general no puede predecir cuándo se accederá a 5, el algoritmo de Bélády no se puede implementar allí.

Reemplazo aleatorio (RR)

El reemplazo aleatorio selecciona un elemento y lo descarta para hacer espacio cuando sea necesario. Este algoritmo no requiere mantener ningún historial de acceso. Se ha utilizado en procesadores ARM debido a su simplicidad y permite una simulación estocástica eficiente.

Políticas simples basadas en colas

Primero en entrar, primero en salir (FIFO)

Con este algoritmo, la caché se comporta como una cola FIFO; desaloja los bloques en el orden en que se agregaron, independientemente de la frecuencia o cuántas veces se accedió a ellos antes.

Último en entrar, primero en salir (LIFO) o Primero en entrar, último en salir (FILO)

La caché se comporta como una pila y a diferencia de una cola FIFO. El caché desaloja primero el bloque agregado más recientemente, independientemente de la frecuencia o cuántas veces se accedió a él antes.

TAMIZ

SIEVE es un algoritmo de desalojo simple diseñado específicamente para cachés web, como cachés de valores clave y redes de entrega de contenido. Utiliza la idea de ascenso lento y descenso rápido. Por lo tanto, SIEVE no actualiza la estructura de datos global en los accesos al caché y retrasa la actualización hasta el momento del desalojo; mientras tanto, desaloja rápidamente los objetos recién insertados porque las cargas de trabajo de la caché tienden a mostrar altas proporciones de un solo acierto y no vale la pena mantener la mayoría de los objetos nuevos en la caché. SIEVE utiliza una única cola FIFO y utiliza una mano en movimiento para seleccionar objetos para desalojar. Los objetos en el caché tienen un bit de metadatos que indica si el objeto ha sido solicitado después de ser admitido en el caché. La mano de desalojo apunta al final de la cola al principio y se mueve hacia la cabeza con el tiempo. En comparación con el algoritmo de desalojo CLOCK, los objetos retenidos en SIEVE permanecen en la posición anterior. Por lo tanto, los objetos nuevos siempre están a la cabeza y los objetos antiguos siempre a la cola. A medida que la mano se mueve hacia la cabeza, los nuevos objetos son rápidamente desalojados (degradación rápida), que es la clave para la alta eficiencia del algoritmo de desalojo SIEVE. SIEVE es más simple que LRU, pero logra índices de fallos sorprendentemente más bajos que LRU a la par con algoritmos de desalojo de última generación. Además, en cargas de trabajo estacionarias sesgadas, SIEVE es mejor que los algoritmos conocidos existentes, incluido LFU.

Políticas simples basadas en la actualidad

Menos utilizado recientemente (LRU)

Primero descarta los elementos usados menos recientemente. Este algoritmo requiere realizar un seguimiento de qué se utilizó y cuándo, lo cual es engorroso. Requiere "bits de edad" para líneas de caché y rastrea la línea de caché utilizada menos recientemente en función de ellas. Cuando se utiliza una línea de caché, la antigüedad de las otras líneas de caché cambia. LRU es una familia de algoritmos de almacenamiento en caché, que incluye 2Q de Theodore Johnson y Dennis Shasha y LRU/K de Pat O'Neil, Betty O'Neil y Gerhard Weikum. El acceso bb para el ejemplo es A B C D E D F:

Cuando se instala A B C D en los bloques con números de secuencia (incremento 1 por cada nuevo acceso) y se accede a E, es un error y debe instalarse en un bloque. Con el algoritmo LRU, E reemplazará a A porque A tiene el rango más bajo (A(0)). En el penúltimo paso, se accede a D y se actualiza el número de secuencia. Luego se accede a F, reemplazando a B, que tenía el rango más bajo, (B(1)).

Consciente del tiempo, usado menos recientemente

TLRU (con reconocimiento de tiempo y uso menos reciente) es una variante de LRU diseñada para cuando el contenido de una caché tiene una vida útil válida. El algoritmo es adecuado para aplicaciones de caché de red, como redes centradas en la información (ICN), redes de entrega de contenido (CDN) y redes distribuidas en general. TLRU introduce un término: TTU (tiempo de uso), una marca de tiempo del contenido (o una página) que estipula el tiempo de usabilidad del contenido en función de su localidad y el editor del contenido. TTU proporciona más control a un administrador local en la regulación del almacenamiento en red.

Cuando llega contenido sujeto a TLRU, un nodo de caché calcula la TTU local en función de la TTU asignada por el editor de contenido. El valor TTU local se calcula con una función definida localmente. Cuando se calcula el valor de TTU local, el reemplazo de contenido se realiza en un subconjunto del contenido total del nodo de caché. TLRU garantiza que el contenido menos popular y de corta duración sea reemplazado por contenido entrante.

Utilizada más recientemente (MRU)

A diferencia de LRU, MRU descarta primero los elementos usados más recientemente. En la undécima conferencia de VLDB, Chou y DeWitt dijeron: "Cuando un archivo se escanea repetidamente en un patrón de referencia [en bucle secuencial], MRU es el mejor algoritmo de reemplazo". Los investigadores que presentaron en la 22ª conferencia VLDB señalaron que para patrones de acceso aleatorio y escaneos repetidos en grandes conjuntos de datos (también conocidos como patrones de acceso cíclico), los algoritmos de caché MRU tienen más aciertos que LRU debido a su tendencia a retener datos más antiguos. Los algoritmos MRU son más útiles en situaciones en las que cuanto más antiguo es un elemento, es más probable que se acceda a él. La secuencia de acceso para el ejemplo es A B C D E C D B:

A B C D se colocan en el caché, ya que hay espacio disponible. En el quinto acceso (E), el bloque que contenía D se reemplaza por E, ya que este bloque se usó por última vez. En el siguiente acceso (a D), se reemplaza C ya que era el bloque al que se accedió justo antes de D.

LRU segmentada (SLRU)

Una caché SLRU se divide en dos segmentos: de prueba y protegida. Las líneas de cada segmento están ordenadas de mayor a menor acceso reciente. Los datos de los errores se agregan al caché en el extremo del segmento de prueba al que se accedió más recientemente. Las visitas se eliminan de donde residen y se agregan al extremo del segmento protegido al que se accedió más recientemente; Se ha accedido a las líneas del segmento protegido al menos dos veces. El segmento protegido es finito; La migración de una línea del segmento de prueba al segmento protegido puede forzar la migración de la línea LRU en el segmento protegido al extremo utilizado más recientemente del segmento de prueba, dando a esta línea otra oportunidad de acceder antes de ser reemplazada. El límite de tamaño del segmento protegido es un parámetro SLRU que varía según los patrones de carga de trabajo de E/S. Cuando se deben descartar datos de la caché, las líneas se obtienen del extremo LRU del segmento de prueba.

Aproximaciones LRU

LRU puede resultar costoso en cachés con mayor asociatividad. El hardware práctico suele emplear una aproximación para lograr un rendimiento similar a un costo de hardware menor.

Pseudo-LRU (PLRU)

Para cachés de CPU con gran asociatividad (generalmente > cuatro formas), el costo de implementación de LRU se vuelve prohibitivo. En muchas cachés de CPU, es suficiente un algoritmo que casi siempre descarta uno de los elementos utilizados menos recientemente; Muchos diseñadores de CPU eligen un algoritmo PLRU, que sólo necesita un bit por elemento de caché para funcionar. PLRU generalmente tiene una tasa de fallos ligeramente peor, una latencia ligeramente mejor, usa un poco menos de energía que LRU y tiene una sobrecarga menor que LRU.

Los bits funcionan como un árbol binario de punteros de un bit que apuntan a un subárbol utilizado menos recientemente. Seguir la cadena de puntero hasta el nodo hoja identifica al candidato de reemplazo. Con un acceso, todos los punteros en la cadena desde el nodo hoja de la vía a la que se accede hasta el nodo raíz se configuran para apuntar a un subárbol que no contiene la ruta a la que se accede. La secuencia de acceso en el ejemplo es A B C D E:

Cuando hay acceso a un valor (como A) y no está en el caché, se carga desde la memoria y se coloca en el bloque hacia donde apuntan las flechas en el ejemplo. Una vez colocado ese bloque, las flechas se invierten para que apunten en la dirección opuesta. Se colocan A, B, C y D; E reemplaza A a medida que el caché se llena porque ahí era donde apuntaban las flechas, y las flechas que conducían a A giran para apuntar en la dirección opuesta (a B, el bloque que será reemplazado en el próximo caché falla).

Reloj-Pro

El algoritmo LRU no se puede implementar en la ruta crítica de los sistemas informáticos, como los sistemas operativos, debido a su gran sobrecarga; En su lugar, se suele utilizar reloj, una aproximación de LRU. Clock-Pro es una aproximación de LIRS para implementación de bajo costo en sistemas. Clock-Pro tiene el marco Clock básico, con tres ventajas. Tiene tres "manecillas de reloj" (a diferencia de la única "manecilla" del reloj) y puede medir aproximadamente la distancia de reutilización de los accesos a datos. Al igual que LIRS, puede desalojar rápidamente elementos de datos de baja localidad o de acceso único. Clock-Pro es tan complejo como Clock y fácil de implementar a bajo costo. La implementación de reemplazo de caché de búfer en la versión 2017 de Linux combina LRU y Clock-Pro.

Políticas simples basadas en frecuencia

Menos utilizada frecuentemente (LFU)

El algoritmo LFU cuenta con qué frecuencia se necesita un artículo; los que se usan con menos frecuencia se descartan primero. Esto es similar a LRU, excepto que se almacena cuántas veces se accedió a un bloque en lugar de cuán recientemente. Mientras se ejecuta una secuencia de acceso, el bloque que se usó la menor cantidad de veces se eliminará del caché.

Uso reciente menos frecuente (LFRU)

El algoritmo menos frecuente utilizado recientemente (LFRU) combina los beneficios de LFU y LRU. LFRU es adecuado para aplicaciones de caché de red como ICN, CDN y redes distribuidas en general. En LFRU, el caché se divide en dos particiones: privilegiada y sin privilegios. La partición privilegiada está protegida y, si el contenido es popular, se inserta en la partición privilegiada. Al reemplazar la partición privilegiada, LFRU desaloja el contenido de la partición sin privilegios; empuja el contenido de la partición privilegiada a la no privilegiada e inserta contenido nuevo en la partición privilegiada. LRU se utiliza para la partición privilegiada y un algoritmo LFU (ALFU) aproximado para la partición sin privilegios.

LFU con envejecimiento dinámico (LFUDA)

Una variante, LFU con envejecimiento dinámico (LFUDA), utiliza el envejecimiento dinámico para adaptarse a los cambios en un conjunto de objetos populares; agrega un factor de antigüedad de la caché al recuento de referencias cuando se agrega un nuevo objeto a la caché o se vuelve a hacer referencia a un objeto existente. LFUDA incrementa la antigüedad de la caché al desalojar bloques configurándola en el valor clave del objeto desalojado, y la antigüedad de la caché siempre es menor o igual que el valor de clave mínimo en la caché. Si se accedió con frecuencia a un objeto en el pasado y se vuelve impopular, permanecerá en la caché durante mucho tiempo (evitando que objetos nuevos o menos populares lo reemplacen). El envejecimiento dinámico reduce la cantidad de dichos objetos, haciéndolos elegibles para reemplazo, y LFUDA reduce la contaminación de la caché causada por LFU cuando una caché es pequeña.

S3-FIFO

Este es un nuevo algoritmo de desalojo diseñado en 2023. En comparación con los algoritmos existentes, que en su mayoría se basan en LRU (menos utilizado recientemente), S3-FIFO solo usa tres colas FIFO: una cola pequeña que ocupa el 10% del espacio de caché, una cola principal que utiliza el 90% del espacio de caché y una cola fantasma que solo almacena metadatos de objetos. La cola pequeña se utiliza para filtrar las maravillas de un solo golpe (objetos a los que sólo se accede una vez en un período de tiempo corto); la cola principal se usa para almacenar objetos populares y usa la reinserción para mantenerlos en el caché; y la cola fantasma se utiliza para capturar objetos potencialmente populares que son desalojados de la cola pequeña. Los objetos se insertan primero en la cola pequeña (si no se encuentran en la cola fantasma, de lo contrario se insertan en la cola principal); tras el desalojo de la cola pequeña, si se ha solicitado un objeto, se reinserta en la cola principal; de lo contrario, se desaloja y los metadatos se rastrean en la cola fantasma.

S3-FIFO demuestra que las colas FIFO son suficientes para diseñar algoritmos de desalojo eficientes y escalables. En comparación con LRU y los algoritmos basados en LRU, S3-FIFO puede lograr un rendimiento 6 veces mayor. Además, en cargas de trabajo de caché web, S3-FIFO logra el índice de errores más bajo entre los 11 algoritmos de última generación que compararon los autores.

Políticas estilo RRIP

Las políticas de estilo RRIP son la base de otras políticas de reemplazo de caché, incluido Hawkeye.

Predicción del intervalo de referencia (RRIP)

RRIP es una política flexible, propuesta por Intel, que intenta proporcionar una buena resistencia al escaneo y al mismo tiempo permite desalojar las líneas de caché más antiguas que no se han reutilizado. Todas las líneas de caché tienen un valor de predicción, el RRPV (valor de predicción de referencia), que debe correlacionarse con el momento en que se espera que se reutilice la línea. El RRPV suele ser alto en el momento de la inserción; Si una línea no se reutiliza pronto, será expulsada para evitar que los escaneos (grandes cantidades de datos utilizados solo una vez) llenen el caché. Cuando se reutiliza una línea de caché, el RRPV se establece en cero, lo que indica que la línea se ha reutilizado una vez y es probable que se reutilice nuevamente.

En caso de fallo de caché, la línea con un RRPV igual al máximo RRPV posible es expulsada; con valores de 3 bits, se desaloja una línea con un RRPV de 2³ - 1 = 7. Si ninguna línea tiene este valor, todos los RRPV del conjunto se incrementan en 1 hasta que uno lo alcance. Se necesita un desempate y, por lo general, es la primera línea de la izquierda. El aumento es necesario para garantizar que las líneas más antiguas envejezcan adecuadamente y serán desalojadas si no se reutilizan.

RRIP estático (SRRIP)

SRRIP inserta líneas con un valor RRPV de maxRRPV; una línea que acaba de insertarse será la que tendrá más probabilidades de ser expulsada si se pierde el caché.

RRIP bimodal (BRRIP)

SRRIP funciona bien normalmente, pero sufre cuando el conjunto de trabajo es mucho mayor que el tamaño de la caché y provoca una destrucción de la caché. Esto se soluciona insertando líneas con un valor RRPV de maxRRPV la mayor parte del tiempo e insertando líneas con un valor RRPV de maxRRPV - 1 aleatoriamente con una probabilidad baja. Esto hace que algunas líneas se "peguen" en el caché y ayuda a prevenir la paliza. BRRIP, sin embargo, degrada el rendimiento en accesos que no son de destrucción. SRRIP funciona mejor cuando el conjunto de trabajo es más pequeño que el caché y BRRIP funciona mejor cuando el conjunto de trabajo es más grande que el caché.

RRIP dinámico (DRRIP)

DRRIP utiliza duelo de conjuntos para seleccionar si se usa SRRIP o BRRIP. Dedica algunos conjuntos (normalmente 32) para usar SRRIP y otros pocos para usar BRRIP, y utiliza un contador de políticas que monitorea el rendimiento del conjunto para determinar qué política será utilizada por el resto de la caché.

Políticas que se aproximan al algoritmo de Bélády

El algoritmo de Bélády es la política óptima de reemplazo de caché, pero requiere conocimiento del futuro para desalojar las líneas que se reutilizarán en mayor medida en el futuro. Se han propuesto varias políticas de reemplazo que intentan predecir distancias de reutilización futuras a partir de patrones de acceso pasados, permitiéndoles aproximarse a la política de reemplazo óptima. Algunas de las políticas de reemplazo de caché de mejor rendimiento intentan imitar el algoritmo de Bélády.

Ojo de halcón

Hawkeye intenta emular el algoritmo de Bélády mediante el uso de accesos pasados por un PC para predecir si los accesos que produce generan accesos cache-friendly (utilizados más tarde) o cache-averse (no utilizados más adelante). Muestra una serie de conjuntos de caché no alineados, utiliza una historia de longitud ${\displaystyle 8\times {\text{the cache size}}$ y emula el algoritmo de Bélády en estos accesos. Esto permite que la política determine qué líneas deberían haber sido cachés y cuáles no deberían, prediciendo si una instrucción es cache-friendly o cache-averse. Estos datos se introducen en un RRIP; los accesos de instrucciones amigables con caché tienen un valor de RRPV más bajo (de ser desalojados más adelante), y los accesos de las instrucciones cache-averse tienen un valor de RRPV más alto (de igual manera ser desalojados antes). El backend RRIP toma las decisiones de desalojo. El generador de caché y OPT muestra el valor inicial de RRPV de las líneas de caché insertadas. Hawkeye ganó el campeonato de caché CRC2 en 2017, y Harmony es una extensión de Hawkeye que mejora el rendimiento de prefetching.

Sinsajo

Sinsajo intenta mejorar a Hawkeye de varias maneras. Elimina la predicción binaria, lo que le permite tomar decisiones más detalladas sobre qué líneas de caché desalojar y deja la decisión sobre qué línea de caché desalojar para cuando haya más información disponible.

Mockingjay mantiene un caché de accesos únicos, los PC que los produjeron, y sus timetamps. Cuando una línea en el caché muestrado se accede de nuevo, la diferencia de tiempo se enviará al predictor de distancia de reutilización. El RDP utiliza el aprendizaje de diferencia temporal, donde el nuevo valor RDP será aumentado o reducido por un pequeño número para compensar los outliers; el número se calcula como ${\displaystyle w=\min \left(1,{\frac {\text{timestamp difference}{16}\right)}$. Si el valor no se ha inicializado, la distancia de reutilización observada se inserta directamente. Si el caché muestrado está lleno y una línea necesita ser descartada, el RDP es instruido que el PC que accedió por última vez produce accesos de streaming.

En un acceso o inserción, el tiempo estimado de reutilización (ETR) para esta línea se actualiza para reflejar la distancia de reutilización prevista. En caso de error de caché, se desaloja la línea con el valor ETR más alto. Mockingjay tiene resultados cercanos al algoritmo óptimo de Bélády.

Políticas de aprendizaje automático

Varias políticas han intentado utilizar perceptrones, cadenas de Markov u otros tipos de aprendizaje automático para predecir qué línea desalojar. También existen algoritmos de aprendizaje aumentado para el reemplazo de caché.

Otras políticas

Conjunto de actualidad baja entre referencias (LIRS)

LIRS es un algoritmo de reemplazo de páginas con mejor rendimiento que LRU y otros algoritmos de reemplazo más nuevos. La distancia de reutilización es una métrica para clasificar dinámicamente las páginas visitadas para tomar una decisión de reemplazo. LIRS aborda los límites de LRU mediante el uso de la actualidad para evaluar la actualidad entre referencias (TIR) para tomar una decisión de reemplazo.

En el diagrama, X indica que se accede a un bloque en un momento determinado. Si se accede al bloque A1 en el momento 1, su actualidad será 0; este es el bloque al que se accede por primera vez y la TIR será 1, ya que predice que se accederá nuevamente a A1 en el tiempo 3. En el tiempo 2, dado que se accede a A4, la actualidad será 0 para A4 y 1 para A1; A4 es el objeto al que se accedió más recientemente y la TIR será 4. En el momento 10, el algoritmo LIRS tendrá dos conjuntos: un conjunto LIR = {A1, A2} y un conjunto HIR = {A3, A4, A5}. En el momento 10, si hay acceso a A4 se produce un fallo; LIRS desalojará a A5 en lugar de A2 debido a su mayor actualidad.

Caché de reemplazo adaptable

La caché de reemplazo adaptativa (ARC) equilibra constantemente entre LRU y LFU para mejorar el resultado combinado. Mejora SLRU al utilizar información sobre elementos de caché desalojados recientemente para ajustar el tamaño de los segmentos protegidos y de prueba para aprovechar al máximo el espacio de caché disponible.

Reloj con reemplazo adaptativo

Reloj con reemplazo adaptativo (CAR) combina las ventajas de ARC y Reloj. CAR tiene un rendimiento comparable al de ARC y supera a LRU y Clock. Al igual que ARC, CAR se autoajusta y no requiere parámetros especificados por el usuario.

Cola múltiple

El algoritmo de reemplazo de colas múltiples (MQ) se desarrolló para mejorar el rendimiento de una caché de búfer de segundo nivel, como la caché de búfer de un servidor, y fue presentado en un artículo por Zhou, Philbin y Li. La caché MQ contiene un número m de colas LRU: Q₀, Q₁,..., Q_{m -1}. El valor de m representa una jerarquía basada en la vida útil de todos los bloques en esa cola.

Alforja

Pannier es un mecanismo de almacenamiento en caché flash basado en contenedores que identifica contenedores cuyos bloques tienen patrones de acceso variables. Pannier tiene una estructura de cola de supervivencia basada en colas de prioridad para clasificar los contenedores según su tiempo de supervivencia, que es proporcional a los datos activos en el contenedor.

Análisis estático

El análisis estático determina qué accesos son aciertos o errores de caché para indicar el peor tiempo de ejecución de un programa. Un enfoque para analizar las propiedades de los cachés LRU es darle a cada bloque del caché una edad de "edad" (0 para el utilizado más recientemente) y calcular intervalos para edades posibles. Este análisis se puede refinar para distinguir casos en los que se puede acceder al mismo punto del programa mediante rutas que resultan en errores o aciertos. Se puede obtener un análisis eficiente abstrayendo conjuntos de estados de caché mediante anticadenas que están representadas por diagramas de decisión binarios compactos.

El análisis estático de LRU no se extiende a las políticas pseudo-LRU. Según la teoría de la complejidad computacional, los problemas de análisis estático planteados por pseudo-LRU y FIFO se encuentran en clases de complejidad más altas que los de LRU.