El algoritmo de Béládyeditar
El algoritmo de almacenamiento en caché más eficiente sería descartar siempre la información que no se necesitará durante más tiempo en el futuro. Este resultado óptimo se conoce como algoritmo óptimo de Bélády/política de reemplazo simplemente óptima o algoritmo clarividente. Dado que en general es imposible predecir en qué medida se necesitará información en el futuro, en general esto no se puede aplicar en la práctica. El mínimo práctico se puede calcular solo después de la experimentación, y se puede comparar la efectividad del algoritmo de caché realmente elegido.
En el momento en que se produce un error de página, un conjunto de páginas está en memoria. En el ejemplo, la secuencia de ‘5’, ‘0’, ‘1’ se accede por el Fotograma 1, el Fotograma 2 y el Fotograma 3, respectivamente. Luego, cuando se accede a ‘2’, reemplaza el valor’ 5′, que está en el fotograma 1, ya que predice que no se accederá al valor’ 5 ‘ en un futuro cercano. Debido a que un sistema operativo de propósito general de la vida real no puede predecir cuándo se accederá a ‘5’, el algoritmo de Bélády no se puede implementar en un sistema de este tipo.
Primera entrada, primera salida (FIFO) Editar
Usando este algoritmo, la caché se comporta de la misma manera que una cola FIFO. La caché desaloja los bloques en el orden en que se agregaron, sin tener en cuenta la frecuencia o la cantidad de veces que se accedió a ellos antes.
Last in first out (LIFO) o First in last out (FILO)Edit
Usando este algoritmo, la caché se comporta de la misma manera que una pila y exactamente de manera opuesta a una cola FIFO. La caché desaloja el bloque agregado más recientemente primero sin tener en cuenta la frecuencia o la cantidad de veces que se accedió antes.
Editar
Primero descarta los elementos menos utilizados recientemente. Este algoritmo requiere llevar un registro de lo que se usó y cuándo, lo cual es costoso si uno quiere asegurarse de que el algoritmo siempre descarta el elemento menos utilizado recientemente. Las implementaciones generales de esta técnica requieren mantener «bits de antigüedad» para las líneas de caché y rastrear la línea de caché «Menos Utilizada recientemente» basada en bits de antigüedad. En tal implementación, cada vez que se usa una línea de caché, cambia la antigüedad de todas las demás líneas de caché. LRU es en realidad una familia de algoritmos de almacenamiento en caché con miembros que incluyen 2Q de Theodore Johnson y Dennis Shasha, y LRU / K de Pat O’Neil, Betty O’Neil y Gerhard Weikum.
La secuencia de acceso para el siguiente ejemplo es A B C D E D F.
En el ejemplo anterior, una vez que se instala un B C D en los bloques con números de secuencia (Incremento 1 para cada nuevo Acceso) y cuando se accede a E, es un error y debe instalarse en uno de los bloques. De acuerdo con el Algoritmo LRU, dado que A tiene el rango más bajo(A(0)), E reemplazará a A.
En el penúltimo paso se accede a D y, por lo tanto, se actualiza el número de secuencia.
LRU, al igual que muchas otras políticas de reemplazo, se puede caracterizar utilizando un campo de transición de estado en un espacio vectorial, que decide los cambios de estado de caché dinámico similares a cómo un campo electromagnético determina el movimiento de una partícula cargada colocada en él.
Time aware least recently used (TLRU)Editar
Time aware Least Recently Used (TLRU) es una variante de LRU diseñada para la situación en la que el contenido almacenado en 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 nuevo término: TTU (Tiempo de uso). TTU es una marca de tiempo de un contenido / página que estipula el tiempo de usabilidad para el contenido basado en la localidad del contenido y el anuncio del editor de contenido. Debido a esta marca de tiempo basada en la localidad, TTU proporciona más control al administrador local para regular el almacenamiento en red.En el algoritmo TLRU, cuando llega una pieza de contenido, un nodo de caché calcula el valor de TTU local en función del valor de TTU asignado por el editor de contenido. El valor local de TTU se calcula utilizando una función definida localmente. Una vez que se calcula el valor de TTU local, la sustitución del contenido se realiza en un subconjunto del contenido total almacenado en el nodo de caché. La TLRU garantiza que el contenido de vida menos popular y pequeño se sustituya por el contenido entrante.
Último uso (MRU)Editar
Descarta, a diferencia de LRU, los elementos más utilizados primero. En los hallazgos presentados en la 11a conferencia de VLDB, Chou y DeWitt señalaron que «Cuando un archivo se escanea repetidamente en un patrón de referencia, la MRU es el mejor algoritmo de reemplazo.»Posteriormente, otros investigadores que se presentaron en la 22a conferencia VLDB señalaron que para patrones de acceso aleatorio y escaneos repetidos en grandes conjuntos de datos (a veces conocidos como patrones de acceso cíclico) los algoritmos de caché MRU tienen más visitas que LRU debido a su tendencia a retener datos más antiguos. Los algoritmos de MRU son más útiles en situaciones en las que cuanto más antiguo es un elemento, más probable es que se acceda a él.
La secuencia de acceso para el siguiente ejemplo es A B C D E C D B.
Aquí, A B C D se colocan en la caché ya que todavía hay espacio disponible. En el quinto acceso E, vemos que el bloque que contenía D ahora se reemplaza por E, ya que este bloque se usó más recientemente. Otro acceso a C y en el siguiente acceso a D, C se reemplaza como era el bloque al que se accedió justo antes de D y así sucesivamente.
Pseudo-LRU (PLRU)Editar
Para cachés de CPU con gran asociatividad (generalmente > 4 formas), el costo de implementación de LRU se vuelve prohibitivo. En muchos cachés de CPU, un esquema que casi siempre descarta uno de los elementos menos utilizados recientemente es suficiente, por lo que muchos diseñadores de CPU eligen un algoritmo PLRU que solo necesita un bit por elemento de caché para funcionar.Por lo general, la PLRU tiene una relación de fallas ligeramente peor, tiene una latencia ligeramente mejor, usa un poco menos de energía que la LRU y menos gastos generales en comparación con la LRU.
El siguiente ejemplo muestra cómo funcionan los Bits como un árbol binario de punteros de 1 bit que apuntan al subárbol menos utilizado recientemente. Siguiendo la cadena de puntero al nodo hoja se identifica al candidato de reemplazo. Al acceder, todos los punteros de 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 vía a la que se accede.
La secuencia de acceso es B C D E.
El principio aquí es fácil de entender si solo miramos los punteros de flecha. Cuando hay un acceso a un valor, por ejemplo ‘A’, y no podemos encontrarlo en la caché, lo cargamos de la memoria y lo colocamos en el bloque donde apuntan las flechas, yendo de arriba a abajo. Después de haber colocado ese bloque, volteamos las mismas flechas para que apunten en dirección opuesta. En el ejemplo anterior vemos cómo se colocó ‘A’, seguido de’ B’, ‘C’y ‘ D’. Luego, a medida que el caché se llenaba, la ‘E’ reemplazó a la ‘A’ porque ahí era donde apuntaban las flechas en ese momento, y las flechas que conducían a la ‘A’ se volteaban para apuntar en la dirección opuesta. Las flechas luego llevaron a ‘B’, que será el bloque reemplazado en la próxima falla de caché.
Edición de reemplazo aleatorio (RR)
Selecciona aleatoriamente un elemento candidato y lo descarta para hacer espacio cuando sea necesario. Este algoritmo no requiere mantener ninguna información sobre el historial de acceso. Por su simplicidad, se ha utilizado en procesadores ARM. Admite simulación estocástica eficiente.
La secuencia de acceso para el siguiente ejemplo es un B C D E B D F
Segmented LRU (SLRU)Edit
La caché SLRU se divide en dos segmentos, un segmento de prueba y un segmento protegido. Las líneas de cada segmento se ordenan de la más a la menos recientemente accedida. Los datos de errores se agregan a la caché al final del segmento de prueba al que se ha accedido más recientemente. Las visitas se eliminan del lugar en el que residen actualmente y se añaden al extremo del segmento protegido al que se ha accedido más recientemente. Por lo tanto, se ha accedido al menos dos veces a las líneas del segmento protegido. El segmento protegido es finito, por lo que 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 más recientemente utilizado (MRU) del segmento de prueba, dando a esta línea otra oportunidad de ser accedida antes de ser reemplazada. El límite de tamaño en el segmento protegido es un parámetro SLRU que varía de acuerdo con los patrones de carga de trabajo de E/S. Siempre que los datos deben ser descartados de la caché, las líneas se obtienen del extremo de la LRU del segmento de prueba.
Edición de uso menos frecuente (LFU)
De uso menos frecuente Cuenta la frecuencia con la que se necesita un elemento. Los que se usan con menos frecuencia se descartan primero. Esto funciona muy similar a LRU, excepto que en lugar de almacenar el valor de la fecha en que se accedió a un bloque, almacenamos el valor de cuántas veces se accedió a él. Así que, por supuesto, mientras ejecutamos una secuencia de acceso, reemplazaremos un bloque que se usó menos veces de nuestra caché. Por ejemplo, si A se usó (accedió) 5 veces y B se usó 3 veces y otros C y D se usaron 10 veces cada uno, reemplazaremos B.
El esquema de reemplazo de caché de uso reciente menos frecuente (LFRU)combina los beneficios de los esquemas LFU y LRU. LFRU es adecuado para aplicaciones de caché «en red», como redes centradas en la información (ICN), Redes de Distribución de Contenido (CDN) y redes distribuidas en general. En LFRU, la caché se divide en dos particiones llamadas particiones privilegiadas y no privilegiadas. La partición privilegiada se puede definir como una partición protegida. Si el contenido es muy popular, se introduce en la partición privilegiada. La sustitución de la partición privilegiada se realiza de la siguiente manera: LFRU desaloja el contenido de la partición sin privilegios, empuja el contenido de la partición privilegiada a la partición sin privilegios y, finalmente, inserta nuevo contenido en la partición privilegiada. En el procedimiento anterior, la LRU se usa para la partición privilegiada y un esquema de LFU aproximado (ALFU) se usa para la partición no privilegiada, de ahí la abreviatura LFRU.
La idea básica es filtrar el contenido localmente popular con el esquema ALFU y empujar el contenido popular a una de las particiones privilegiadas.
LFU con envejecimiento dinámico (LFUDA)Editar
Una variante llamada LFU con envejecimiento dinámico (LFUDA) que utiliza el envejecimiento dinámico para adaptarse a los cambios en el conjunto de objetos populares. Agrega un factor de antigüedad de caché al recuento de referencias cuando se agrega un nuevo objeto a la caché o cuando se vuelve a referenciar un objeto existente. LFUDA incrementa la antigüedad de la caché al desalojar bloques configurándola con el valor de clave del objeto desalojado. Por lo tanto, la antigüedad de la caché siempre es menor o igual al valor de clave mínimo en la caché. Supongamos que cuando se accedía con frecuencia a un objeto en el pasado y ahora se vuelve impopular, permanecerá en la caché durante mucho tiempo, evitando que los objetos nuevos o menos populares lo reemplacen. Por lo tanto, este envejecimiento dinámico se introduce para reducir el recuento de tales objetos, lo que los hace elegibles para su reemplazo. La ventaja de LFUDA es que reduce la contaminación de caché causada por LFU cuando los tamaños de caché son muy pequeños. Cuando los tamaños de caché son grandes, pocas decisiones de reemplazo son suficientes y la contaminación de la caché no será un problema.
Conjunto de recencia de baja referencia (LIRS)Editar
LIRS es un algoritmo de reemplazo de página con un rendimiento mejorado sobre LRU y muchos otros algoritmos de reemplazo más nuevos. Esto se logra utilizando la distancia de reutilización como métrica para clasificar dinámicamente las páginas a las que se accede para tomar una decisión de reemplazo. Los LIR abordan efectivamente los límites de la LRU mediante el uso de la recencia para evaluar la Recencia entre referencias (TIR) para tomar una decisión de reemplazo.
En la figura anterior,» x » representa que se accede a un bloque en el tiempo t. Supongamos que si se accede al bloque A1 en el momento 1, la Recencia se convertirá en 0, ya que este es el primer bloque al que se accede, y la TIR será 1, ya que predice que se volverá a acceder a A1 en el tiempo 3. En el tiempo 2 desde que se accede a A4, la recencia se convertirá en 0 para A4 y 1 para A1 porque A4 es el objeto al que se ha accedido más recientemente y la TIR se convertirá en 4 y continuará. En el momento 10, el algoritmo LIRS tendrá dos conjuntos LIR set = {A1, A2} y HIR set = {A3, A4, A5}. Ahora, en el momento 10, si hay acceso a A4, se produce una falla. El algoritmo LIRS ahora desalojará a A5 en lugar de A2 debido a su mayor actualidad.
CLOCK-ProEdit
El algoritmo LRU no se puede implementar directamente en la ruta crítica de los sistemas informáticos, como los sistemas operativos, debido a su alta sobrecarga. Una aproximación de LRU, llamada RELOJ, se usa comúnmente para la implementación. Del mismo modo, CLOCK-Pro es una aproximación de LIRS para una implementación de bajo costo en sistemas. CLOCK-Pro está bajo el marco de RELOJ básico, pero tiene tres méritos distintos principales. En primer lugar, CLOCK-Pro tiene tres «manecillas de reloj» en contraste con una estructura simple de RELOJ donde solo se usa una «manecilla». Con las tres agujas, CLOCK-Pro es capaz de medir la distancia de reutilización de los accesos a los datos de forma aproximada. En segundo lugar, se mantienen todos los méritos de los LIRS, como desalojar rápidamente elementos de datos de acceso único o de baja localidad. En tercer lugar, la complejidad del CLOCK-Pro es la misma que la del CLOCK, por lo que es fácil de implementar a bajo costo. La implementación de reemplazo de caché de búfer en la versión actual de Linux es una combinación de LRU y CLOCK-Pro.
Edición de caché de reemplazo adaptable (ARC)
equilibra constantemente entre LRU y LFU, para mejorar el resultado combinado. ARC mejora la SLRU mediante el uso de información sobre elementos de caché recientemente desalojados para ajustar dinámicamente el tamaño del segmento protegido y el segmento de prueba para aprovechar al máximo el espacio de caché disponible. El algoritmo de reemplazo adaptativo se explica con el ejemplo.
AdaptiveClimb (AC)Edit
Utiliza el golpe / error reciente para ajustar el salto, donde en ascenso cualquier golpe cambia la posición de una ranura a la parte superior, y en LRU hit cambia la posición del golpe a la parte superior. Por lo tanto, se beneficia de la optimalidad de climb cuando el programa está en un alcance fijo, y de la rápida adaptación a un nuevo alcance, como lo hace LRU. También admite el uso compartido de caché entre núcleos liberando extras cuando las referencias son a la parte superior de la caché.
Reloj con reemplazo adaptativo (CAR)Editar
Combina las ventajas de la Caché de Reemplazo Adaptativo (ARC) y el RELOJ. El coche tiene un rendimiento comparable al de ARC, y supera sustancialmente a LRU y CLOCK. Al igual que ARC, CAR es autoajustable y no requiere parámetros mágicos especificados por el usuario. Utiliza 4 listas doblemente vinculadas: dos relojes T1 y T2 y dos listas simples de LRU B1 y B2. El reloj T1 almacena páginas basadas en «actualidad » o» utilidad a corto plazo», mientras que el reloj T2 almacena páginas con» frecuencia «o»utilidad a largo plazo». T1 y T2 contienen las páginas que están en la caché, mientras que B1 y B2 contienen páginas que han sido desalojadas recientemente de T1 y T2, respectivamente. El algoritmo intenta mantener el tamaño de estas listas B1≈T2 y B2≈T1. Se insertan nuevas páginas en T1 o T2. Si hay un golpe en el tamaño B1 de T1 se incrementa y de manera similar si hay un golpe en el tamaño B2 de T1 se disminuye. La regla de adaptación utilizada tiene el mismo principio que en ARC, invertir más en listas que darán más visitas cuando se agreguen más páginas.
Edición de múltiples colas (MQ)
El algoritmo de múltiples colas o MQ se desarrolló para mejorar el rendimiento de la caché de búfer de segundo nivel para, por ejemplo, una caché de búfer de servidor. La caché MQ contiene un número m de colas LRU: Q0, Q1,…, Qm-1. Aquí, el valor de m representa una jerarquía basada en la vida útil de todos los bloques en esa cola en particular. Por ejemplo, si j> i, los bloques en Qj tendrán una vida útil más larga que los de Qi. Además de estos hay otro búfer de historial Qout, una cola que mantiene una lista de todos los Identificadores de Bloque junto con sus frecuencias de acceso. Cuando Qout está lleno, se desaloja el identificador más antiguo. Los bloques permanecen en las colas de la LRU durante una vida útil determinada, que el algoritmo MQ define dinámicamente como la distancia temporal máxima entre dos accesos al mismo archivo o el número de bloques de caché, el que sea mayor. Si un bloque no ha sido referenciado durante su vida útil, es degradado de Qi a Qi−1 o desalojado de la caché si está en Q0. Cada cola también tiene un número máximo de accesos; si se accede a un bloque en la cola Qi más de 2i veces, este bloque se promociona a Qi+1 hasta que se accede más de 2i+1 veces o su vida útil expira. Dentro de una cola dada, los bloques se clasifican según la actualidad del acceso, de acuerdo con LRU.
podemos ver en la Fig. cómo se colocan las colas de m LRU en la caché. Véase también la Fig. cómo almacena el Qout los identificadores de bloque y sus frecuencias de acceso correspondientes. a se colocó en Q0, ya que solo se accedió una vez recientemente y podemos comprobar en Qout cómo b y c se colocaron en Q1 y Q2 respectivamente, ya que sus frecuencias de acceso son 2 y 4. La cola en la que se coloca un bloque depende de la frecuencia de acceso(f) como log2(f). Cuando la caché está llena, el primer bloque que se desalojará será el encabezado de Q0 en este caso a. Si se accede una vez más a a, se moverá a Q1 debajo de b.
Alforja: Algoritmo de almacenamiento en caché basado en contenedores para objetos compuestoseditar
Alforja es un mecanismo de almacenamiento en caché flash basado en contenedores que identifica contenedores divergentes (heterogéneos) donde los bloques contenidos en ellos tienen patrones de acceso muy variables. Pannier utiliza una estructura de cola de supervivencia basada en colas de prioridad para clasificar los contenedores en función de su tiempo de supervivencia, que es proporcional a los datos en tiempo real del contenedor. La alforja se construye en base a LRU segmentada (S2LRU), que segrega los datos calientes y fríos. La alforja también utiliza un controlador de retroalimentación de varios pasos para acelerar las escrituras de flash para garantizar la vida útil del flash.