Algoritmo de reemplazo de páginas

En un sistema operativo que utiliza paginación para la gestión de memoria virtual , los algoritmos de reemplazo de páginas deciden qué páginas de memoria se deben transferir (a veces denominadas intercambio) o escribir en el disco cuando se necesita asignar una página de memoria. El reemplazo de páginas ocurre cuando la página solicitada no se encuentra en la memoria ( fallo de página ) y no se puede utilizar una página libre para satisfacer la asignación, ya sea porque no hay ninguna disponible o porque el número de páginas libres es inferior a un umbral determinado.

Cuando se vuelve a acceder a la página seleccionada para su reemplazo y paginada, es necesario cargarla (leerla desde el disco), lo que implica esperar a que finalice la operación de entrada/salida. Esto determina la calidad del algoritmo de reemplazo de páginas: cuanto menor sea el tiempo de espera para la carga de páginas, mejor será el algoritmo. Un algoritmo de reemplazo de páginas analiza la información limitada sobre los accesos a las páginas que proporciona el hardware e intenta adivinar qué páginas deben reemplazarse para minimizar el número total de fallos de página, equilibrando esto con los costos (almacenamiento primario y tiempo de procesador) del propio algoritmo.

El problema de la sustitución de páginas es un problema típico en línea desde la perspectiva del análisis competitivo, en el sentido de que se conoce el algoritmo determinista óptimo.

Historia

Los algoritmos de reemplazo de páginas fueron un tema candente de investigación y debate en las décadas de 1960 y 1970. Esto concluyó en gran medida con el desarrollo de aproximaciones LRU (menos usadas recientemente) sofisticadas y algoritmos de conjunto de trabajo . Desde entonces, algunas suposiciones básicas de los algoritmos tradicionales de reemplazo de páginas quedaron invalidadas, lo que dio lugar a un resurgimiento de la investigación. En particular, las siguientes tendencias en el comportamiento del hardware subyacente y del software de nivel de usuario han afectado el rendimiento de los algoritmos de reemplazo de páginas:

El tamaño del almacenamiento primario ha aumentado en varios órdenes de magnitud. Con varios gigabytes de memoria primaria, los algoritmos que requieren una comprobación periódica de cada marco de memoria son cada vez menos prácticos.
Las jerarquías de memoria se han vuelto más complejas. El coste de un fallo de caché de la CPU es mucho mayor. Esto agrava el problema anterior.
La localidad de referencia del software de usuario se ha debilitado. Esto se atribuye principalmente a la difusión de técnicas de programación orientada a objetos que favorecen un gran número de funciones pequeñas, al uso de estructuras de datos sofisticadas como árboles y tablas hash que tienden a generar patrones de referencia de memoria caóticos, y a la aparición de la recolección de basura que cambió drásticamente el comportamiento de acceso a la memoria de las aplicaciones.

Los requisitos para los algoritmos de reemplazo de páginas han cambiado debido a las diferencias en las arquitecturas del núcleo del sistema operativo . En particular, la mayoría de los núcleos de los sistemas operativos modernos tienen memoria virtual y cachés del sistema de archivos unificadas , lo que requiere que el algoritmo de reemplazo de páginas seleccione una página entre las páginas de los espacios de direcciones virtuales de los programas de usuario y los archivos en caché. Estas últimas páginas tienen propiedades específicas. Por ejemplo, pueden estar bloqueadas o tener requisitos de orden de escritura impuestos por el registro de transacciones . Además, como el objetivo del reemplazo de páginas es minimizar el tiempo total de espera de memoria, debe tener en cuenta los requisitos de memoria impuestos por otros subsistemas del núcleo que asignan memoria. Como resultado, el reemplazo de páginas en los núcleos modernos ( Linux , FreeBSD y Solaris ) tiende a funcionar a nivel de un asignador de memoria del núcleo de propósito general, en lugar de a nivel superior, como en un subsistema de memoria virtual.

Sustitución local frente a sustitución global

Los algoritmos de reemplazo pueden ser locales o globales.

Cuando un proceso sufre un fallo de página, un algoritmo local de reemplazo de páginas selecciona para su reemplazo una página que pertenece a ese mismo proceso (o a un grupo de procesos que comparten una partición de memoria ). Un algoritmo de reemplazo global puede seleccionar cualquier página en la memoria.

La sustitución local de páginas presupone algún tipo de particionamiento de memoria que determina cuántas páginas se asignarán a un proceso o grupo de procesos. Las formas más comunes de particionamiento son el particionamiento fijo y los algoritmos de conjunto balanceado basados en el modelo de conjunto de trabajo . La ventaja de la sustitución local de páginas radica en su escalabilidad: cada proceso puede gestionar sus fallos de página de forma independiente, lo que se traduce en un rendimiento más consistente para dicho proceso. Sin embargo, la sustitución global de páginas es más eficiente a nivel de sistema general. ^{[ 1 ]}

Detectar qué páginas se referencian y modifican

Las computadoras modernas de propósito general y algunos procesadores integrados admiten memoria virtual . En la mayoría de ellas, cada proceso tiene su propio espacio de direcciones virtuales . Una tabla de páginas asigna un subconjunto de las direcciones virtuales del proceso a direcciones físicas. Además, en la mayoría de las arquitecturas, la tabla de páginas contiene un bit de "acceso" y un bit de "modificación" para cada página. La CPU establece el bit de acceso cuando el proceso lee o escribe en la memoria de esa página. La CPU establece el bit de modificación cuando el proceso escribe en la memoria de esa página. El sistema operativo puede modificar los bits de acceso y modificación. El sistema operativo puede detectar accesos a la memoria y a los archivos mediante los siguientes medios:

Al borrar el bit de acceso en las páginas presentes en la tabla de páginas del proceso, el sistema operativo recorre la tabla buscando aquellas páginas cuyo bit de acceso fue activado por la CPU. Este proceso es rápido porque la CPU activa automáticamente el bit de acceso, pero impreciso porque el sistema operativo no recibe notificación inmediata del acceso ni dispone de información sobre el orden en que el proceso accedió a dichas páginas.
Al eliminar páginas de la tabla de páginas del proceso sin eliminarlas necesariamente de la memoria física, el siguiente acceso a esa página se detecta inmediatamente porque provoca un fallo de página . Esto es lento porque un fallo de página implica un cambio de contexto al sistema operativo, una búsqueda por software de la dirección física correspondiente , la modificación de la tabla de páginas y un cambio de contexto de vuelta al proceso, pero preciso porque el acceso se detecta inmediatamente después de que se produce.
Directamente cuando el proceso realiza llamadas al sistema que potencialmente acceden a la caché de páginas como ready writeen POSIX .

Limpieza previa

La mayoría de los algoritmos de reemplazo simplemente devuelven la página de destino como resultado. Esto significa que si la página de destino está sucia (es decir, contiene datos que deben escribirse en la memoria persistente antes de que la página pueda recuperarse), se debe iniciar una operación de E/S para enviar esa página a la memoria persistente (para limpiarla ). En los inicios de la memoria virtual, el tiempo dedicado a la limpieza no era una preocupación importante, ya que la memoria virtual se implementó por primera vez en sistemas con canales dúplex completos hacia la memoria persistente, y la limpieza solía superponerse con la paginación. En cambio, el hardware comercial actual no admite transferencias dúplex completas, y la limpieza de las páginas de destino se convierte en un problema.

Para abordar esta situación, se implementan diversas políticas de prelimpieza . La prelimpieza es el mecanismo que inicia las operaciones de entrada/salida (E/S) en las páginas modificadas que probablemente se reemplazarán pronto. La idea es que, para cuando la página prelimpiada se seleccione para su reemplazo, las operaciones de E/S se hayan completado y la página esté limpia. La prelimpieza parte de la base de que es posible identificar las páginas que se reemplazarán a continuación . Una prelimpieza demasiado proactiva puede desperdiciar ancho de banda de E/S al escribir páginas que se vuelven a modificar antes de ser seleccionadas para su reemplazo.

El problema de paginación (h,k)

El problema de paginación (h,k) es una generalización del modelo del problema de paginación: Sean h,k enteros positivos tales que $h\leq k$ . Medimos el rendimiento de un algoritmo con caché de tamaño $h\leq k$ en relación con el algoritmo de reemplazo de páginas teóricamente óptimo . Si $h<k$ Proporcionamos el algoritmo óptimo de reemplazo de páginas con un consumo de recursos estrictamente menor.

El problema de paginación (h,k) es una forma de medir el rendimiento de un algoritmo en línea comparándolo con el rendimiento del algoritmo óptimo, específicamente, parametrizando por separado el tamaño de la caché del algoritmo en línea y del algoritmo óptimo.

Algoritmos de marcado

Los algoritmos de marcado constituyen una clase general de algoritmos de paginación. A cada página se le asocia un bit denominado marca. Inicialmente, todas las páginas se establecen como no marcadas. Durante una etapa (un período de operación o una secuencia de solicitudes) de solicitudes de página, se marca una página cuando se solicita por primera vez en dicha etapa. Un algoritmo de marcado es aquel que nunca desplaza una página marcada.

Si ALG es un algoritmo de marcado con una caché de tamaño k, y OPT es el algoritmo óptimo con una caché de tamaño h, donde $h\leq k$ , entonces ALG es ${\tfrac {k}{k-h+1}}$ -competitivo. Por lo tanto, cada algoritmo de calificación alcanza el ${\tfrac {k}{k-h+1}}$ -índice de competitividad.

LRU es un algoritmo de marcado, mientras que FIFO no lo es.

Algoritmos conservadores

Un algoritmo es conservador si, en cualquier secuencia de solicitudes consecutivas que contenga k o menos referencias de página distintas, el algoritmo incurrirá en k o menos fallos de página.

Si ALG es un algoritmo conservador con una caché de tamaño k, y OPT es el algoritmo óptimo con una caché de $h\leq k$ , entonces ALG es ${\tfrac {k}{k-h+1}}$ -competitivo. Por lo tanto, cada algoritmo conservador alcanza el ${\tfrac {k}{k-h+1}}$ -índice de competitividad.

LRU, FIFO y CLOCK son algoritmos conservadores.

Algoritmos de reemplazo de páginas

Hay una variedad de algoritmos de reemplazo de páginas: ^{[ 2 ]}

El algoritmo de reemplazo de páginas teóricamente óptimo

El algoritmo de reemplazo de páginas teóricamente óptimo (también conocido como OPT, algoritmo de reemplazo clarividente o política de reemplazo de páginas óptima de Bélády ) ^{[ 3 ]}^{[ 4 ]}^{[ 2 ]} es un algoritmo que funciona de la siguiente manera: cuando se necesita intercambiar una página, el sistema operativo reemplaza la página cuyo próximo uso ocurrirá más en el futuro. Por ejemplo, una página que no se utilizará durante los próximos 6 segundos se reemplazará por una página que se utilizará dentro de los próximos 0,4 segundos.

Este algoritmo no puede implementarse en un sistema operativo de propósito general porque es imposible calcular de forma fiable cuánto tiempo falta para que se utilice una página, salvo que todo el software que se ejecutará en el sistema se conozca de antemano y sea susceptible de análisis estático de sus patrones de referencia de memoria, o que solo exista una clase de aplicaciones que permitan el análisis en tiempo de ejecución. A pesar de esta limitación, existen algoritmos ^{[ 5 ]} que pueden ofrecer un rendimiento casi óptimo: el sistema operativo realiza un seguimiento de todas las páginas a las que hace referencia el programa y utiliza esos datos para decidir qué páginas intercambiar en ejecuciones posteriores. Este algoritmo puede ofrecer un rendimiento casi óptimo, pero no en la primera ejecución de un programa, y solo si el patrón de referencia de memoria del programa es relativamente consistente en cada ejecución.

El análisis del problema de paginación también se ha realizado en el campo de los algoritmos en línea . La eficiencia de los algoritmos aleatorios en línea para el problema de paginación se mide mediante análisis amortizado .

No se ha usado recientemente

El algoritmo de reemplazo de páginas no usadas recientemente (NRU) prioriza el mantenimiento en memoria de las páginas que se han usado recientemente. Este algoritmo funciona según el siguiente principio: cuando se hace referencia a una página, se activa un bit de referencia para marcarla como tal. De forma similar, cuando se modifica (se escribe) en una página, se activa un bit de modificación. La activación de estos bits suele realizarse mediante hardware, aunque también es posible hacerlo a nivel de software.

En un intervalo de tiempo fijo, se activa una interrupción del temporizador que borra el bit de referencia de todas las páginas, de modo que solo las páginas referenciadas dentro del intervalo actual del temporizador se marcan con dicho bit. Cuando es necesario reemplazar una página, el sistema operativo la divide en cuatro clases:

3. Referenciado, modificado

2. Referenciado, no modificado

1. No referenciado, modificado

0. No referenciado, no modificado

Aunque parezca imposible que una página se modifique sin estar referenciada, esto ocurre cuando el bit de referencia de una página de clase 3 se borra mediante la interrupción del temporizador. El algoritmo NRU selecciona una página aleatoria de la categoría más baja para su eliminación. Por lo tanto, de las cuatro categorías de páginas mencionadas, el algoritmo NRU reemplazará una página no referenciada y no modificada si existe. Cabe destacar que este algoritmo implica que una página modificada pero no referenciada (dentro del último intervalo del temporizador) es menos importante que una página no modificada que se referencia con frecuencia.

NRU es un algoritmo de marcado, por lo tanto es ${\tfrac {k}{k-h+1}}$ -competitivo.

Primero en entrar, primero en salir

El algoritmo de reemplazo de páginas más simple es el algoritmo FIFO. El algoritmo de reemplazo de páginas primero en entrar, primero en salir (FIFO) es un algoritmo de bajo consumo de recursos que requiere poca gestión por parte del sistema operativo . La idea es obvia por su nombre: el sistema operativo mantiene un registro de todas las páginas en memoria en una cola, con la llegada más reciente al final y la llegada más antigua al principio. Cuando se necesita reemplazar una página, se selecciona la página que está al principio de la cola (la página más antigua). Si bien FIFO es económico e intuitivo, su rendimiento en la práctica es deficiente. Por lo tanto, rara vez se utiliza en su forma original. Este algoritmo experimenta la anomalía de Bélády . En pocas palabras, en caso de fallo de página, se reemplaza el marco que ha estado en memoria durante más tiempo.

El sistema operativo OpenVMS utiliza el algoritmo de reemplazo de páginas FIFO , con algunas modificaciones. ^{[ 6 ]} Se proporciona una segunda oportunidad parcial omitiendo un número limitado de entradas con referencias válidas a la tabla de traducción, ^{[ 7 ]} y, además, las páginas se desplazan del conjunto de trabajo del proceso a un grupo de todo el sistema desde el cual se pueden recuperar si no se han reutilizado ya.

FIFO es un algoritmo conservador, por lo que es ${\tfrac {k}{k-h+1}}$ -competitivo.

Segunda oportunidad

Una forma modificada del algoritmo de reemplazo de páginas FIFO, conocida como algoritmo de reemplazo de páginas de segunda oportunidad, funciona relativamente mejor que FIFO con poco costo para la mejora. Funciona examinando el inicio de la cola como lo hace FIFO, pero en lugar de paginar esa página inmediatamente, verifica si su bit de referencia está activado. Si no lo está, la página se intercambia. De lo contrario, el bit de referencia se desactiva, la página se inserta al final de la cola (como si fuera una página nueva) y este proceso se repite. Esto también puede considerarse como una cola circular. Si todas las páginas tienen su bit de referencia activado, en el segundo encuentro con la primera página de la lista, esa página se intercambiará, ya que ahora tiene su bit de referencia desactivado. Si todas las páginas tienen su bit de referencia desactivado, el algoritmo de segunda oportunidad degenera en FIFO puro.

Como su nombre indica, Second-chance le da a cada página una "segunda oportunidad": una página antigua que ya ha sido referenciada probablemente esté en uso y no debería reemplazarse por una página nueva que no haya sido referenciada.

Reloj

El algoritmo Clock es una versión más eficiente de FIFO que Second-Chance porque las páginas no tienen que ser constantemente desplazadas al final de la lista, pero realiza la misma función general que Second-Chance. El algoritmo Clock mantiene una lista circular de páginas en memoria, con la "manecilla" (iterador) apuntando al último marco de página examinado en la lista. Cuando ocurre un fallo de página y no existen marcos vacíos, se inspecciona el bit R (referenciado) en la posición de la manecilla. Si R es 0, la nueva página se coloca en lugar de la página a la que apunta la "manecilla" y esta avanza una posición. De lo contrario, el bit R se borra, la manecilla del Clock se incrementa y el proceso se repite hasta que se reemplaza una página. ^{[ 8 ]} Este algoritmo fue descrito por primera vez en 1969 por Fernando J. Corbató . ^{[ 9 ]}

Variantes del reloj

GCLOCK: Algoritmo generalizado de reemplazo de páginas de reloj. ^{[ 10 ]}
Clock-Pro mantiene una lista circular de información sobre las páginas referenciadas recientemente, incluyendo todas las M páginas en memoria, así como las M páginas más recientes que se han paginado. Esta información adicional sobre las páginas paginadas, al igual que la información similar que mantiene ARC , le permite funcionar mejor que LRU en bucles grandes y escaneos únicos. ^{[ 11 ]}
WSclock. ^{[ 12 ]} Al combinar el algoritmo Clock con el concepto de conjunto de trabajo (es decir, el conjunto de páginas que se espera que utilice ese proceso durante un intervalo de tiempo determinado), se puede mejorar el rendimiento del algoritmo. En la práctica, el algoritmo de "envejecimiento" y el algoritmo "WSClock" son probablemente los algoritmos de reemplazo de páginas más importantes. ^{[ 13 ]}^{[ 14 ]}
El algoritmo de reemplazo de páginas Clock with Adaptive Replacement (CAR) tiene un rendimiento comparable al de ARC y supera sustancialmente a LRU y CLOCK. ^{[ 15 ]} El algoritmo CAR se autoajusta y no requiere parámetros mágicos especificados por el usuario.

CLOCK es un algoritmo conservador, por lo que es ${\tfrac {k}{k-h+1}}$ -competitivo.

Menos usado recientemente

El algoritmo de reemplazo de páginas menos usadas recientemente (LRU), aunque similar en nombre a NRU, se diferencia en que LRU realiza un seguimiento del uso de las páginas durante un período corto de tiempo, mientras que NRU solo considera el uso en el último intervalo de reloj. LRU se basa en la idea de que las páginas que se han usado más en las últimas instrucciones tienen más probabilidades de usarse también en las siguientes. Si bien LRU puede proporcionar un rendimiento casi óptimo en teoría (casi tan bueno como la caché de reemplazo adaptativa ), su implementación en la práctica es bastante costosa. Existen algunos métodos de implementación para este algoritmo que intentan reducir el costo manteniendo el mayor rendimiento posible.

El método más costoso es el de lista enlazada , que utiliza una lista que contiene todas las páginas de memoria. Al final de la lista se encuentra la página menos utilizada y al principio la más utilizada. El costo de esta implementación radica en que los elementos de la lista deben moverse en cada acceso a la memoria, lo cual es un proceso que consume mucho tiempo.

Otro método que requiere soporte de hardware es el siguiente: supongamos que el hardware tiene un contador de 64 bits que se incrementa con cada instrucción. Cada vez que se accede a una página, esta adquiere el valor del contador en ese momento. Cuando es necesario reemplazar una página, el sistema operativo selecciona la página con el contador más bajo y la sustituye.

Debido a los costes de implementación, se pueden considerar algoritmos (como los que se describen a continuación) que son similares a LRU, pero que ofrecen implementaciones más económicas.

Una ventaja importante del algoritmo LRU es que se presta a un análisis estadístico completo. Se ha demostrado, por ejemplo, que LRU nunca produce más de N veces más fallos de página que el algoritmo OPT, donde N es proporcional al número de páginas en el grupo administrado.

Por otro lado, la debilidad de LRU radica en que su rendimiento tiende a degradarse bajo muchos patrones de referencia bastante comunes. Por ejemplo, si hay N páginas en el grupo LRU, una aplicación que ejecuta un bucle sobre un array de N + 1 páginas provocará un fallo de página en cada acceso. Dado que los bucles sobre arrays grandes son frecuentes, se ha dedicado mucho esfuerzo a modificar LRU para que funcione mejor en tales situaciones. Muchas de las modificaciones propuestas para LRU intentan detectar patrones de referencia en bucle y cambiar a un algoritmo de reemplazo adecuado, como el de Uso Más Recientemente Usado (MRU).

Variantes de LRU

LRU-K ^{[ 16 ]} elimina la página cuyo k-ésimo acceso más reciente se encuentra más alejado en el pasado. Por ejemplo, LRU-1 es simplemente LRU, mientras que LRU-2 elimina las páginas según el tiempo de su penúltimo acceso. LRU-K mejora considerablemente a LRU en lo que respecta a la localidad temporal.
El algoritmo ARC ^{[ 17 ]} extiende LRU al mantener un historial de páginas recientemente desalojadas y lo utiliza para cambiar la preferencia hacia el acceso reciente o frecuente. Es particularmente resistente a los escaneos secuenciales.
El algoritmo 2Q ^{[ 18 ]} mejora los algoritmos LRU y LRU/2. Al tener dos colas, una para elementos de ruta crítica y otra para elementos de ruta lenta, los elementos se colocan primero en la cola de ruta lenta y, tras un segundo acceso, se colocan en la cola de ruta crítica. Dado que las referencias a los elementos añadidos se mantienen durante más tiempo que en los algoritmos LRU y LRU/2, la cola de ruta crítica es más eficiente, lo que mejora la tasa de aciertos de la caché.

Una comparación de ARC con otros algoritmos (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) se puede encontrar en Megiddo y Modha 2004. ^{[ 19 ]}

LRU es un algoritmo de marcado, por lo que es ${\tfrac {k}{k-h+1}}$ -competitivo.

Aleatorio

El algoritmo de reemplazo aleatorio reemplaza una página aleatoria en la memoria. Esto elimina el costo adicional del seguimiento de referencias de página. Generalmente funciona mejor que FIFO, y para referencias de memoria en bucle es mejor que LRU, aunque en la práctica LRU suele tener un mejor rendimiento. OS/390 utiliza una aproximación LRU global y recurre al reemplazo aleatorio cuando el rendimiento de LRU se degrada, y el procesador Intel i860 utilizaba una política de reemplazo aleatorio (Rhodehamel 1989 ^{[ 20 ]} ).

No se usa con frecuencia (NFU)

El algoritmo de reemplazo de páginas no utilizadas con frecuencia (NFU, por sus siglas en inglés) requiere un contador, y cada página tiene su propio contador, que inicialmente se establece en 0. En cada intervalo de reloj, el contador de todas las páginas que se hayan consultado durante ese intervalo se incrementará en 1. En efecto, los contadores registran la frecuencia de uso de cada página. De esta forma, la página con el contador más bajo puede reemplazarse cuando sea necesario.

El principal problema de NFU es que registra la frecuencia de uso sin tener en cuenta el intervalo de tiempo. Por lo tanto, en un compilador de múltiples pasadas , las páginas que se usaron mucho durante la primera pasada, pero que no se necesitan en la segunda, tendrán prioridad sobre las páginas que se usan relativamente poco en la segunda pasada, ya que tienen contadores de frecuencia más altos. Esto resulta en un rendimiento deficiente. Existen otros escenarios comunes donde NFU se comporta de manera similar, como el arranque del sistema operativo. Afortunadamente, existe un algoritmo similar y mejor, cuya descripción se presenta a continuación.

El algoritmo de reemplazo de páginas menos utilizado genera menos fallos de página que el algoritmo de reemplazo de páginas menos utilizado recientemente cuando la tabla de páginas contiene valores de puntero nulo .

Envejecimiento

El algoritmo de envejecimiento es descendiente del algoritmo NFU, con modificaciones para que tenga en cuenta el intervalo de tiempo de uso. En lugar de simplemente incrementar los contadores de las páginas referenciadas, dando la misma importancia a las referencias de página independientemente del tiempo, el contador de referencias de una página se desplaza primero a la derecha (dividido por 2), antes de añadir el bit referenciado a la izquierda de ese número binario. Por ejemplo, si una página ha referenciado los bits 1, 0, 0, 1, 1, 0 en los últimos 6 ciclos de reloj, su contador de referencias se verá así en orden cronológico: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Las referencias de página más cercanas al presente tienen mayor impacto que las referencias de páginas antiguas. Esto garantiza que las páginas referenciadas más recientemente, aunque se referencien con menos frecuencia, tendrán mayor prioridad que las páginas referenciadas con mayor frecuencia en el pasado. Por lo tanto, cuando sea necesario reemplazar una página, se elegirá la página con el contador más bajo.

El siguiente código Python simula el algoritmo de envejecimiento. Contadores $V_{i}$ se inicializan con0 y actualizado como se describe anteriormente a través de $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ , utilizando operadores de desplazamiento aritmético .

from collections.abc import Sequencedef simulate_aging ( Rs : Sequence , k : int ) -> None : """Simular envejecimiento""" print ( " t | R-bits (0- {length} ) | Contadores para las páginas 0- {length} " . format ( length = len ( Rs ))) Vs = [ 0 ] * len ( Rs [ 0 ]) for t , R in enumerate ( Rs ): Vs [:] = [ R [ i ] << ( k - 1 ) | V >> 1 for i , V in enumerate ( Vs )] print ( " {:02d}  | {}  | [ {} ]" . format ( t , R , ", " . join ([ "{:0 {} b}" . format ( V , k ) for V in Vs ])))

En el ejemplo dado de R-bits para 6 páginas en 5 ciclos de reloj, la función imprime la siguiente salida, que enumera los R-bits para cada ciclo de reloj $t$ y los valores individuales del contador. $V_{i}$ para cada página en representación binaria . ^{[ 21 ]}

>>> Rs = [[ 1 , 0 , 1 , 0 , 1 , 1 ], [ 1 , 1 , 0 , 0 , 1 , 0 ], [ 1 , 1 , 0 , 1 , 0 , 1 ], [ 1 , 0 , 0 , 0 , 1 , 0 ], [ 0 , 1 , 1 , 0 , 0 , 0 ]] >>> k = 8 >>> simulate_aging ( Rs , k ) t | R-bits (0-5) | Contadores para las páginas 0-5 00 | [1, 0, 1, 0, 1, 1] | [10000000, 00000000, 10000000, 00000000, 10000000, 10000000] 01 | [1, 1, 0, 0, 1, 0] | [11000000, 10000000, 01000000, 00000000, 11000000, 01000000] 02 | [1, 1, 0, 1, 0, 1] | [11100000, 11000000, 00100000, 10000000, 01100000, 10100000] 03 | [1, 0, 0, 0, 1, 0] | [11110000, 01100000, 00010000, 01000000, 10110000, 01010000] 04 | [0, 1, 1, 0, 0, 0] | [01111000, 10110000, 10001000, 00100000, 01011000, 00101000]

Tenga en cuenta que el envejecimiento difiere de LRU en el sentido de que el envejecimiento solo puede realizar un seguimiento de las referencias en el últimoIntervalos de tiempo de 16/32 (dependiendo del tamaño de bits de los enteros del procesador). Por consiguiente, dos páginas pueden tener contadores referenciados de 00000000, aunque una página se haya referenciado hace 9 intervalos y la otra hace 1000. En general, conocer el uso durante los últimos 16 intervalos es suficiente para decidir qué página reemplazar. De este modo, el envejecimiento puede ofrecer un rendimiento casi óptimo a un precio moderado.

Algoritmo de reemplazo de páginas por distancia más larga primero (LDF).

La idea básica de este algoritmo es la localidad de referencia, similar a la utilizada en LRU, pero con la diferencia de que en LDF la localidad se basa en la distancia, no en las referencias utilizadas. En LDF, se reemplaza la página que se encuentra a mayor distancia de la página actual. Si dos páginas están a la misma distancia, se reemplazará la página siguiente a la actual en sentido antihorario.

Detalles de implementación

Técnicas para hardware sin bit de referencia

Muchas de las técnicas descritas anteriormente presuponen la presencia de un bit de referencia asociado a cada página. Algunos dispositivos no disponen de dicho bit, por lo que su uso eficiente requiere técnicas que funcionen correctamente sin él.

Un ejemplo notable es el hardware VAX que ejecuta OpenVMS . Este sistema sabe si una página ha sido modificada, pero no necesariamente si ha sido leída. Su enfoque se conoce como almacenamiento en caché de páginas secundario. Las páginas eliminadas de los conjuntos de trabajo (memoria privada del proceso, generalmente) se colocan en listas especiales mientras permanecen en la memoria física durante un tiempo. Eliminar una página de un conjunto de trabajo no es técnicamente una operación de reemplazo de página, pero efectivamente identifica esa página como candidata. Una página cuyo almacenamiento subyacente aún es válido (cuyo contenido no está modificado o no necesita conservarse) se coloca al final de la lista de páginas libres. Una página que requiere escritura en el almacenamiento subyacente se colocará en la lista de páginas modificadas. Estas acciones generalmente se activan cuando el tamaño de la lista de páginas libres cae por debajo de un umbral ajustable.

Las páginas pueden seleccionarse para su eliminación del conjunto de trabajo de forma prácticamente aleatoria, con la expectativa de que, si se realiza una mala elección, una referencia futura pueda recuperar esa página de la lista de Páginas Libres o Modificadas antes de que se elimine de la memoria física. Una página referenciada de esta manera se eliminará de la lista de Páginas Libres o Modificadas y se volverá a colocar en el conjunto de trabajo de un proceso. La Lista de Páginas Modificadas también ofrece la oportunidad de escribir páginas en la memoria de respaldo en grupos de más de una página, lo que aumenta la eficiencia. Estas páginas pueden luego colocarse en la Lista de Páginas Libres. La secuencia de páginas que avanza hacia el inicio de la Lista de Páginas Libres se asemeja a los resultados de un mecanismo LRU o NRU, y el efecto general tiene similitudes con el algoritmo de Segunda Oportunidad descrito anteriormente.

Otro ejemplo lo proporciona el kernel de Linux en ARM . La falta de funcionalidad de hardware se compensa con dos tablas de páginas: las tablas de páginas nativas del procesador, sin bits referenciados ni modificados , y las tablas de páginas mantenidas por software, que sí contienen los bits necesarios. Los bits emulados en la tabla mantenida por software se establecen mediante fallos de página. Para obtener fallos de página, al borrar los bits emulados en la segunda tabla se revocan algunos de los derechos de acceso a la página correspondiente, lo cual se implementa modificando la tabla nativa.

Caché de páginas en Linux

Linux utiliza una caché de páginas unificada para

brky regiones mmaped anónimas . Esto incluye el montón y la pila de los programas del espacio de usuario . Está escrito para intercambiarse cuando se pagina.
mmapRegiones no anónimas (respaldadas por archivos) . Si está presente en la memoria y no se modifica de forma privada, la página física se comparte con la caché de archivos o el búfer.
Memoria compartida adquirida a través de shm_open.
El sistema de archivos en memoria tmpfs ; se escribe en la memoria de intercambio cuando se pagina.
La caché de archivos incluye: escritura en el almacenamiento de bloques subyacente (posiblemente pasando por el búfer, ver más abajo) cuando se pagina.
La caché de dispositivos de bloques , denominada "búfer" por Linux (que no debe confundirse con otras estructuras también llamadas búferes, como las que se utilizan para tuberías y búferes utilizados internamente en Linux); se escribe en el almacenamiento subyacente cuando se pagina.

La caché de páginas unificada opera en unidades del tamaño de página más pequeño admitido por la CPU (4 KiB en ARMv8 , x86 y x86-64 ) con algunas páginas del tamaño inmediatamente superior (2 MiB en x86-64 ) llamadas "páginas enormes" por Linux. Las páginas en la caché de páginas se dividen en un conjunto "activo" y un conjunto "inactivo". Ambos conjuntos mantienen una lista LRU de páginas. En el caso básico, cuando un programa en el espacio de usuario accede a una página, esta se coloca al principio del conjunto inactivo. Cuando se accede a ella repetidamente, se mueve a la lista activa. Linux mueve las páginas del conjunto activo al conjunto inactivo según sea necesario para que el conjunto activo sea más pequeño que el conjunto inactivo. Cuando una página se mueve al conjunto inactivo, se elimina de la tabla de páginas del espacio de direcciones de cualquier proceso, sin ser paginada fuera de la memoria física. ^{[ 22 ]}^{[ 23 ]} Cuando una página se elimina del conjunto inactivo, se pagina fuera de la memoria física. El tamaño de la lista "activa" e "inactiva" se puede consultar en /proc/meminfolos campos "Active", "Inactive", "Active(anon)", "Inactive(anon)", "Active(file)" e "Inactive(file)".

Conjunto de trabajo

El conjunto de trabajo de un proceso es el conjunto de páginas que se espera que ese proceso utilice durante un intervalo de tiempo determinado.

El "modelo de conjunto de trabajo" no es un algoritmo de reemplazo de páginas en el sentido estricto (en realidad es una especie de planificador a medio plazo ).

Referencias

↑ Bell, John. "Apuntes del curso de Sistemas Operativos: Memoria Virtual" . Facultad de Ingeniería de la Universidad de Illinois en Chicago . Archivado del original el 23 de septiembre de 2018. Consultado el 21 de julio de 2017 .
1 2 Jones, Douglas W. "22C:116 Notas de clase" . Departamento de Ciencias de la Computación de la Universidad de Iowa . Recuperado el 18 de marzo de 2008 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
↑ Torrez, Paul; et al. "Apuntes de la clase 11 de CS111" . Departamento de Ciencias de la Computación de UCLA . Archivado del original el 9 de enero de 2009.
↑ Bahn, Hyokyung; Noh, Sam H. (12–14 de febrero de 2003). Caracterización del comportamiento de referencia web revisitada: Evidencia de gestión de caché dicotómica . Conferencia Internacional sobre Redes de Información 2003. Jeju, Corea del Sur: Springer-Verlag. pp. 1018–1027 . doi : 10.1007/978-3-540-45235-5_100 . ISBN 978-3-540-40827-7.
↑ Jain, Akanksha; Lin, Calvin (2016). Regreso al futuro: aprovechando el algoritmo de Belady para mejorar el reemplazo de caché (PDF) . Simposio Internacional sobre Arquitectura de Computadoras (ISCA). Seúl, Corea del Sur: IEEE. doi : 10.1109/ISCA.2016.17 .
↑ Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (14 de diciembre de 2004). Conceptos de sistemas operativos (7.ª ed.). Hoboken, NJ, EE. UU.: John Wiley & Sons. pág. 339. ISBN 0-47169-466-5OCLC 56913661
↑ Ayuda de VMS — Parámetros del sistema, TBSKIPWSL
↑ Tanenbaum, Andrew S. (2001). Sistemas operativos modernos (2.ª ed.). Upper Saddle River, NJ, EE. UU.: Prentice-Hall. pág. 218 (4.4.5) . ISBN 978-0-13-031358-4. LCCN 00051666 . OCLC 45284637 . OL 24214243M .
↑ Corbató, Fernando J. (1969). "Un experimento de paginación con el sistema Multics" (PDF) . Festschrift: En honor a PM Morse . MIT Press . pp. 217–228 .
↑ Smith, Alan Jay (septiembre de 1978). "Secuencialidad y precarga en sistemas de bases de datos" . ACM Transactions on Database Systems . 3 (3). Nueva York, NY, EE. UU.: ACM: 223–247 . doi : 10.1145/320263.320276 . S2CID 11611563 .
↑ Jiang, Song; Chen, Feng; Zhang, Xiaodong (10–15 de abril de 2005). CLOCK-Pro: una mejora efectiva del reemplazo de CLOCK (PDF) . Conferencia Técnica Anual USENIX 2005. Anaheim, CA, EE. UU.: Asociación USENIX. pág. 35. Archivado (PDF) del original el 12 de junio de 2019. Recuperado el 24 de marzo de 2009 .
↑ Carr, Richard W.; Hennessy, John L. (14–16 de diciembre de 1981). WSCLOCK: un algoritmo simple y eficaz para la gestión de memoria virtual (PDF comprimido) . Octavo simposio de la ACM sobre principios de sistemas operativos . Pacific Grove, CA, EE. UU.: ACM. págs. 87–95 . doi : 10.1145/800216.806596 . ISBN 0-89791-062-1Archivado del original el 10 de junio de 2007 .
↑ Gottlieb, Allan. "WSClock" . Departamento de Ciencias de la Computación de la Universidad de Nueva York . Consultado el 12 de junio de 2019 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
↑ Tanenbaum, Andrew S. "Algoritmos de reemplazo de páginas" . InformIT . Consultado el 12 de junio de 2019 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
↑ Bansal, Sorav y Modha, Dharmendra S. (31 de marzo - 2 de abril de 2004). CAR: Reloj con reemplazo adaptativo (PDF) . 3.ª Conferencia USENIX sobre tecnologías de archivos y almacenamiento (FAST '04) . San Francisco, CA, EE. UU.: Asociación USENIX. págs. 187-200 . CiteSeerX 10.1.1.105.6057 . Archivado (PDF) del original el 31 de julio de 2004.
↑ O'Neil, Elizabeth J.; et al. (25–28 de mayo de 1993). El algoritmo de reemplazo de páginas LRU-K para el almacenamiento en búfer de disco de bases de datos (PDF) . Conferencia internacional ACM SIGMOD de 1993 sobre gestión de datos . Washington, DC, EE. UU.: ACM. págs. 297–306 . CiteSeerX 10.1.1.18.1434 . doi : 10.1145/170035.170081 . ISBN 0-89791-592-5Archivado (PDF) del original el 6 de septiembre de 2019 .
↑ Megiddo, Nimrod y Modha, Dharmendra S. (31 de marzo - 2 de abril de 2003). ARC: una caché de reemplazo autoajustable y de baja sobrecarga (PDF) . 2.ª Conferencia USENIX sobre Tecnologías de Archivos y Almacenamiento (FAST '03) . San Francisco, CA, EE. UU.: Asociación USENIX. págs. 115-130 . Archivado (PDF) del original el 8 de febrero de 2010.
↑ Johnson, Theodore; Shasha, Dennis (12–15 de septiembre de 1994). 2Q: Un algoritmo de reemplazo de gestión de búferes de alto rendimiento y baja sobrecarga (PDF) . XX Conferencia Internacional sobre Bases de Datos Muy Grandes . Santiago de Chile, Chile: Morgan Kaufmann. págs. 439–450 . ISBN 1-55860-153-8. Archivado (PDF) del original el 17 de marzo de 2020. Recuperado el 31 de julio de 2005 .
↑ Megiddo, Nimrod y Modha, Dharmendra S. (2004). "Superando a LRU con un algoritmo de caché de reemplazo adaptativo" ( PDF) . Computer . 37 (4). IEEE Computer Society: 58. CiteSeerX 10.1.1.231.498 . doi : 10.1109/MC.2004.1297303 . S2CID 5507282. Archivado (PDF) del original el 21 de octubre de 2012. Recuperado el 20 de septiembre de 2013 .
↑ Rhodehamel, Michael W. (2–4 de octubre de 1989). La interfaz de bus y las unidades de paginación del microprocesador i860 . Conferencia Internacional IEEE de 1989 sobre Diseño de Computadoras: VLSI en Computadoras y Procesadores . Cambridge, MA, EE. UU.: IEEE. págs. 380–384 . doi : 10.1109/ICCD.1989.63392 . ISBN 0-8186-1971-6Número de acceso INSPEC 3719504.
^ Tanenbaum, Andrew S.; Bos, Herbert (2015). Sistemas operativos modernos (4ª ed.). Boston, MA, Estados Unidos: Pearson. pag. 215.ISBN 978-0-13-359162-0. OL 25620855M .
↑ Ver explicación al inicio del/mm/workingset.ccódigo fuente de Linux
↑ Corbet, Jonathan Corbet (2 de mayo de 2012). "Mejor equilibrio de listas activas/inactivas" . LWN.net .

Lecturas adicionales

Wong, Kin-Yeung (23 de enero de 2006). "Políticas de reemplazo de caché web: un enfoque pragmático". IEEE Network . 20 (1). IEEE: 28–34 . doi : 10.1109/MNET.2006.1580916 . ISSN 0890-8044 . S2CID 17969287. Número de acceso INSPEC 8964134.
Aho, Alfred V.; Denning, Peter J.; Ullman, Jeffrey D. (enero de 1971). "Principios de reemplazo óptimo de páginas" . Journal of the ACM . 18 (1). Nueva York, NY, EE. UU.: ACM: 80–93 . doi : 10.1145/321623.321632 . S2CID 3154537 .
Tanenbaum, Andrew S. (1997). Sistemas operativos: diseño e implementación (2.ª ed.). Upper Saddle River, NJ, EE. UU.: Prentice-Hall. ISBN 0-13-638677-6. LCCN 96037153 . OL 998396M .
Tanenbaum, Andrew S. (2001). Sistemas operativos modernos (2.ª ed.). Upper Saddle River, NJ, EE. UU.: Prentice-Hall. ISBN 978-0-13-031358-4. LCCN 00051666 . OCLC 45284637 . OL 24214243M . Extracto en línea sobre algoritmos de reemplazo de páginas: Algoritmos de reemplazo de páginas .
Glass, Gideon; Cao, Pei (15-18 de junio de 1997). Reemplazo adaptativo de páginas basado en el comportamiento de referencia de memoria . Conferencia internacional ACM SIGMETRICS de 1997 sobre medición y modelado de sistemas informáticos . Seattle, WA, EE. UU.: ACM. págs. 115-126 . doi : 10.1145/258612.258681 . ISBN 0-89791-909-2.También disponible en forma extendida como Glass, Gideon; Cao, Pei (1997). "Informe técnico 1338" . Departamento de Ciencias de la Computación, Universidad de Wisconsin-Madison .
Kim, Jong Min; et al. (17–21 de octubre de 2000). Un esquema de gestión de búfer unificado de alto rendimiento y baja sobrecarga que aprovecha las referencias secuenciales y en bucle (PDF) . 4.º Simposio Usenix sobre Diseño e Implementación de Sistemas Operativos (OSDI'2000) . Vol. 4. San Diego, CA, EE. UU.: USENIX Association. Archivado (PDF) del original el 18 de septiembre de 2004.
Smaragdakis, Yannis; Kaplan, Scott; Wilson, Paul (1–4 de mayo de 1999). EELRU: reemplazo de página adaptativo simple y efectivo (PDF) . Conferencia internacional ACM SIGMETRICS de 1999 sobre medición y modelado de sistemas informáticos . Atlanta, GA, EE. UU.: ACM. págs. 122–133 . doi : 10.1145/301453.301486 . ISBN 1-58113-083-XArchivado (PDF) del original el 4 de marzo de 2016 .
Jiang, Song; Zhang, Xiaodong (15–19 de junio de 2002). LIRS: un reemplazo de conjunto de recencia de baja interreferencia (PDF) . Conferencia internacional ACM SIGMETRICS 2002 sobre medición y modelado de sistemas informáticos . Marina Del Rey, CA, EE. UU.: ACM. págs. 31–42 . doi : 10.1145/511334.511340 . ISBN 1-58113-531-9Archivado (PDF) del original el 12 de junio de 2019 .
Lee, Donghee; et al. (1–4 de septiembre de 1997). Implementación y evaluación del rendimiento de la política de reemplazo de LRFU . 23.ª Conferencia Euromicro: Nuevas Fronteras de la Tecnología de la Información . Budapest, Hungría: IEEE Computer Society. pp. 106–111 . doi : 10.1109/EMSCNT.1997.658446 . ISBN 0-8186-8215-9Número de acceso INSPEC 5856800.
Zhou, Yuanyuan; Philbin, James; Li, Kai (25–30 de junio de 2001). El algoritmo de reemplazo de múltiples colas para cachés de búfer de segundo nivel (PDF) . Conferencia Técnica Anual USENIX 2001. Boston, MA, EE. UU.: Asociación USENIX. págs. 91–104 . ISBN 1-880446-09-XArchivado (PDF) del original el 24 de noviembre de 2005 .

[1] Bell, John. "Apuntes del curso de Sistemas Operativos: Memoria Virtual" . Facultad de Ingeniería de la Universidad de Illinois en Chicago . Archivado del original el 23 de septiembre de 2018. Consultado el 21 de julio de 2017 .

[lecture_notes_jones-2] 1 2 Jones, Douglas W. "22C:116 Notas de clase" . Departamento de Ciencias de la Computación de la Universidad de Iowa . Recuperado el 18 de marzo de 2008 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )

[3] Torrez, Paul; et al. "Apuntes de la clase 11 de CS111" . Departamento de Ciencias de la Computación de UCLA . Archivado del original el 9 de enero de 2009.

[4] Bahn, Hyokyung; Noh, Sam H. (12–14 de febrero de 2003). Caracterización del comportamiento de referencia web revisitada: Evidencia de gestión de caché dicotómica . Conferencia Internacional sobre Redes de Información 2003. Jeju, Corea del Sur: Springer-Verlag. pp. 1018–1027 . doi : 10.1007/978-3-540-45235-5_100 . ISBN 978-3-540-40827-7.

[5] Jain, Akanksha; Lin, Calvin (2016). Regreso al futuro: aprovechando el algoritmo de Belady para mejorar el reemplazo de caché (PDF) . Simposio Internacional sobre Arquitectura de Computadoras (ISCA). Seúl, Corea del Sur: IEEE. doi : 10.1109/ISCA.2016.17 .

[Silber-6] Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (14 de diciembre de 2004). Conceptos de sistemas operativos (7.ª ed.). Hoboken, NJ, EE. UU.: John Wiley & Sons. pág. 339. ISBN 0-47169-466-5OCLC 56913661

[7] Ayuda de VMS — Parámetros del sistema, TBSKIPWSL

[Tanenbaum-8] Tanenbaum, Andrew S. (2001). Sistemas operativos modernos (2.ª ed.). Upper Saddle River, NJ, EE. UU.: Prentice-Hall. pág. 218 (4.4.5) . ISBN 978-0-13-031358-4. LCCN 00051666 . OCLC 45284637 . OL 24214243M .

[9] Corbató, Fernando J. (1969). "Un experimento de paginación con el sistema Multics" (PDF) . Festschrift: En honor a PM Morse . MIT Press . pp. 217–228 .

[10] Smith, Alan Jay (septiembre de 1978). "Secuencialidad y precarga en sistemas de bases de datos" . ACM Transactions on Database Systems . 3 (3). Nueva York, NY, EE. UU.: ACM: 223–247 . doi : 10.1145/320263.320276 . S2CID 11611563 .

[11] Jiang, Song; Chen, Feng; Zhang, Xiaodong (10–15 de abril de 2005). CLOCK-Pro: una mejora efectiva del reemplazo de CLOCK (PDF) . Conferencia Técnica Anual USENIX 2005. Anaheim, CA, EE. UU.: Asociación USENIX. pág. 35. Archivado (PDF) del original el 12 de junio de 2019. Recuperado el 24 de marzo de 2009 .

[12] Carr, Richard W.; Hennessy, John L. (14–16 de diciembre de 1981). WSCLOCK: un algoritmo simple y eficaz para la gestión de memoria virtual (PDF comprimido) . Octavo simposio de la ACM sobre principios de sistemas operativos . Pacific Grove, CA, EE. UU.: ACM. págs. 87–95 . doi : 10.1145/800216.806596 . ISBN 0-89791-062-1Archivado del original el 10 de junio de 2007 .

[13] Gottlieb, Allan. "WSClock" . Departamento de Ciencias de la Computación de la Universidad de Nueva York . Consultado el 12 de junio de 2019 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )

[14] Tanenbaum, Andrew S. "Algoritmos de reemplazo de páginas" . InformIT . Consultado el 12 de junio de 2019 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )

[15] Bansal, Sorav y Modha, Dharmendra S. (31 de marzo - 2 de abril de 2004). CAR: Reloj con reemplazo adaptativo (PDF) . 3.ª Conferencia USENIX sobre tecnologías de archivos y almacenamiento (FAST '04) . San Francisco, CA, EE. UU.: Asociación USENIX. págs. 187-200 . CiteSeerX 10.1.1.105.6057 . Archivado (PDF) del original el 31 de julio de 2004.

[16] O'Neil, Elizabeth J.; et al. (25–28 de mayo de 1993). El algoritmo de reemplazo de páginas LRU-K para el almacenamiento en búfer de disco de bases de datos (PDF) . Conferencia internacional ACM SIGMOD de 1993 sobre gestión de datos . Washington, DC, EE. UU.: ACM. págs. 297–306 . CiteSeerX 10.1.1.18.1434 . doi : 10.1145/170035.170081 . ISBN 0-89791-592-5Archivado (PDF) del original el 6 de septiembre de 2019 .

[17] Megiddo, Nimrod y Modha, Dharmendra S. (31 de marzo - 2 de abril de 2003). ARC: una caché de reemplazo autoajustable y de baja sobrecarga (PDF) . 2.ª Conferencia USENIX sobre Tecnologías de Archivos y Almacenamiento (FAST '03) . San Francisco, CA, EE. UU.: Asociación USENIX. págs. 115-130 . Archivado (PDF) del original el 8 de febrero de 2010.

[18] Johnson, Theodore; Shasha, Dennis (12–15 de septiembre de 1994). 2Q: Un algoritmo de reemplazo de gestión de búferes de alto rendimiento y baja sobrecarga (PDF) . XX Conferencia Internacional sobre Bases de Datos Muy Grandes . Santiago de Chile, Chile: Morgan Kaufmann. págs. 439–450 . ISBN 1-55860-153-8. Archivado (PDF) del original el 17 de marzo de 2020. Recuperado el 31 de julio de 2005 .

[19] Megiddo, Nimrod y Modha, Dharmendra S. (2004). "Superando a LRU con un algoritmo de caché de reemplazo adaptativo" ( PDF) . Computer . 37 (4). IEEE Computer Society: 58. CiteSeerX 10.1.1.231.498 . doi : 10.1109/MC.2004.1297303 . S2CID 5507282. Archivado (PDF) del original el 21 de octubre de 2012. Recuperado el 20 de septiembre de 2013 .

[20] Rhodehamel, Michael W. (2–4 de octubre de 1989). La interfaz de bus y las unidades de paginación del microprocesador i860 . Conferencia Internacional IEEE de 1989 sobre Diseño de Computadoras: VLSI en Computadoras y Procesadores . Cambridge, MA, EE. UU.: IEEE. págs. 380–384 . doi : 10.1109/ICCD.1989.63392 . ISBN 0-8186-1971-6Número de acceso INSPEC 3719504.

[21] Tanenbaum, Andrew S.; Bos, Herbert (2015). Sistemas operativos modernos (4ª ed.). Boston, MA, Estados Unidos: Pearson. pag. 215.ISBN 978-0-13-359162-0. OL 25620855M .

[22] Ver explicación al inicio del/mm/workingset.ccódigo fuente de Linux

[23] Corbet, Jonathan Corbet (2 de mayo de 2012). "Mejor equilibrio de listas activas/inactivas" . LWN.net .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]