Algoritmo de reemplazo de página

En un sistema operativo de computadora que utiliza paginación para la administración de la memoria virtual, los algoritmos de reemplazo de páginas deciden qué páginas de memoria paginar, a veces llamado intercambio o escritura en el disco, cuando una página de memoria necesita para ser asignado. El reemplazo de página ocurre cuando una página solicitada no está en la memoria (fallo de página) y no se puede usar una página libre para satisfacer la asignación, ya sea porque no hay ninguna o porque la cantidad de páginas libres es inferior a cierto umbral.

Cuando se vuelve a hacer referencia a la página que se seleccionó para reemplazo y paginada, se debe paginar (leer desde el disco), y esto implica esperar a que se complete la E/S. Esto determina la calidad del algoritmo de reemplazo de páginas: cuanto menos tiempo se espere para las entradas 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 proporcionada por el hardware e intenta adivinar qué páginas deben reemplazarse para minimizar el número total de páginas perdidas, mientras equilibra esto con los costos (almacenamiento primario y tiempo de procesador) de el algoritmo en sí.

El problema de reemplazo 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 terminó en su mayor parte con el desarrollo de aproximaciones sofisticadas LRU (utilizadas menos recientemente) y algoritmos de conjuntos de trabajo. Desde entonces, algunas suposiciones básicas hechas por los algoritmos tradicionales de reemplazo de páginas quedaron invalidadas, lo que resultó en un resurgimiento de la investigación. En particular, las siguientes tendencias en el comportamiento del hardware subyacente y del software a nivel de usuario han afectado el rendimiento de los algoritmos de reemplazo de páginas:

• El tamaño del almacenamiento primario ha aumentado por múltiples órdenes de magnitud. Con varios gigabytes de memoria primaria, algoritmos que requieren un cheque periódico de cada uno de los marcos de memoria se están volviendo cada vez menos prácticos.
• Las jerarquías de memoria han crecido más alto. El costo de una falta de caché de CPU es mucho más caro. Esto exacerba el problema anterior.
• Localidad de referencia del software del usuario se ha debilitado. Esto se atribuye principalmente a la difusión de técnicas de programación orientadas al objeto que favorecen un gran número de funciones pequeñas, el uso de estructuras de datos sofisticadas como árboles y tablas de hash que tienden a resultar en patrones de referencia de memoria caótica, y el advenimiento de la colección de basura que cambió drásticamente el comportamiento del acceso a la memoria de las aplicaciones.

Los requisitos para los algoritmos de reemplazo de páginas han cambiado debido a diferencias en las arquitecturas del kernel del sistema operativo. En particular, la mayoría de los kernels de sistemas operativos modernos tienen memoria virtual unificada y cachés del sistema de archivos, lo que requiere que el algoritmo de reemplazo de página seleccione una página entre las páginas de los espacios de direcciones virtuales del programa de usuario y los archivos almacenados en caché. Las últimas páginas tienen propiedades específicas. Por ejemplo, pueden estar bloqueados o pueden tener requisitos de orden de escritura impuestos mediante el registro en diario. Además, como el objetivo del reemplazo de páginas es minimizar el tiempo total de espera de memoria, se deben 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 kernels modernos (Linux, FreeBSD y Solaris) tiende a funcionar en el nivel de un asignador de memoria del kernel de propósito general, en lugar de en el nivel superior de un subsistema de memoria virtual.

Reemplazo local versus global

Los algoritmos de reemplazo pueden ser locales o globales.

Cuando un proceso sufre un error de página, un algoritmo de reemplazo de página local selecciona para reemplazar alguna 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 es gratuito para seleccionar cualquier página en la memoria.

El reemplazo de páginas locales supone alguna forma de partición de memoria que determina cuántas páginas se asignarán a un proceso determinado o a un grupo de procesos. Las formas más populares de partición son los algoritmos de partición fija y de conjunto equilibrado basados en el modelo de conjunto de trabajo. La ventaja del reemplazo de páginas local es su escalabilidad: cada proceso puede manejar sus errores de página de forma independiente, lo que genera un rendimiento más consistente para ese proceso. Sin embargo, el reemplazo global de páginas es más eficiente en todo el sistema.

Detectar qué páginas son referenciadas y modificadas

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

• Limpiando el bit de acceso en las páginas presentes en la tabla de página del proceso. Después de algún tiempo, el sistema operativo escanea la tabla de página buscando páginas que tenían el bit de acceso fijado por la CPU. Esto es rápido porque el bit de acceso es fijado automáticamente por la CPU e inexacto porque el sistema operativo no recibe inmediatamente aviso del acceso ni tiene información sobre el orden en que el proceso accedió a estas páginas.
• Eliminando páginas de la tabla de página del proceso sin eliminarlas necesariamente de la memoria física. El próximo acceso a esa página se detecta inmediatamente porque causa una falla de página. Esto es lento porque una falla de página implica un cambio de contexto en el sistema operativo, búsqueda de software para la dirección física correspondiente, modificación de la tabla de página y un cambio de contexto de nuevo al proceso y exacto porque el acceso se detecta inmediatamente después de que ocurra.
• Directamente cuando el proceso hace llamadas del sistema que potencialmente acceden a la caché de la página como read y write en 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 el almacenamiento estable antes de que se pueda recuperar la página), se debe iniciar E/S para enviar esa página al almacenamiento estable (para limpiar la página). En los primeros días de la memoria virtual, el tiempo dedicado a la limpieza no era una gran preocupación, porque la memoria virtual se implementó por primera vez en sistemas con canales dúplex completos hacia el almacenamiento estable, y la limpieza generalmente se superponía con la paginación. El hardware básico contemporáneo, por otro lado, no admite transferencias dúplex y la limpieza de las páginas de destino se convierte en un problema.

Para hacer frente a esta situación, se implementan diversas políticas de prelimpieza. La limpieza previa es el mecanismo que inicia la E/S en páginas sucias que (probablemente) serán reemplazadas pronto. La idea es que cuando la página previamente limpiada se seleccione para el reemplazo, la E/S se completará y la página estará limpia. La limpieza previa supone que es posible identificar las páginas que serán reemplazadas a continuación. Una limpieza previa demasiado intensa puede desperdiciar ancho de banda de E/S al escribir páginas que logran volver a ensuciarse antes de ser seleccionadas para ser reemplazadas.

El problema de la paginación (h,k)

El problema (h,k)-paging es una generalización del modelo de problema de paging: Let h,k ser enteros positivos tal que ${displaystyle hleq k}$. Medimos el rendimiento de un algoritmo con caché de tamaño ${displaystyle hleq k}$ relativo al algoritmo de reemplazo de página teóricamente óptimo. Si ${displaystyle hierek}$, proporcionamos el algoritmo de reemplazo óptimo de página con estrictamente menos recurso.

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 caché del algoritmo en línea y del algoritmo óptimo.

Algoritmos de marcado

Los algoritmos de marcado son una clase general de algoritmos de paginación. Para cada página, la asociamos con un bit llamado marca. Inicialmente, configuramos todas las páginas como sin marcar. Durante una etapa (un período de operación o una secuencia de solicitudes) de solicitudes de páginas, marcamos una página cuando se solicita por primera vez en esta etapa. Un algoritmo de marcado es un algoritmo que nunca elimina una página marcada.

Si ALG es un algoritmo de marcación con un caché de tamaño k, y OPT es el algoritmo óptimo con un caché de tamaño h, donde ${displaystyle hleq k}$, entonces ALG es ${fnMicroc} {k}{k-h+1}}$- competitivo. Así que cada algoritmo de marcación alcanza el ${fnMicroc} {k}{k-h+1}}$- ratio competitiva.

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

Algoritmos conservadores

Un algoritmo es conservador, si en cualquier secuencia de solicitud consecutiva que contenga k o menos referencias de páginas distintas, el algoritmo incurrirá en k o menos errores de página.

Si ALG es un algoritmo conservador con un caché de tamaño k, y OPT es el algoritmo óptimo con un caché de ${displaystyle hleq k}$, entonces ALG es ${fnMicroc} {k}{k-h+1}}$- competitivo. Así que cada algoritmo conservador alcanza el ${fnMicroc} {k}{k-h+1}}$- ratio competitiva.

LRU, FIFO y CLOCK son algoritmos conservadores.

Algoritmos de sustitución de páginas

Existe una variedad de algoritmos de reemplazo de páginas:

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

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

Este algoritmo no se puede implementar en un sistema operativo de propósito general porque es imposible calcular de manera confiable cuánto tiempo pasará antes de que se utilice una página, excepto cuando todo el software que se ejecutará en un sistema se conoce de antemano y es susceptible de análisis estático de sus patrones de referencia de memoria, o solo una clase de aplicaciones que permiten el análisis en tiempo de ejecución. A pesar de esta limitación, existen algoritmos 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 entrar y salir en ejecuciones posteriores. Este algoritmo puede ofrecer un rendimiento casi óptimo, pero no en la primera ejecución de un programa, y sólo si el patrón de referencia de memoria del programa es relativamente consistente cada vez que se ejecuta.

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 en línea aleatorios para el problema de paginación se mide mediante un análisis amortizado.

No utilizada recientemente

El algoritmo de reemplazo de páginas no utilizadas recientemente (NRU) es un algoritmo que favorece mantener en la memoria las páginas que se han utilizado recientemente. Este algoritmo funciona según el siguiente principio: cuando se hace referencia a una página, se establece un bit de referencia para esa página, marcándola como referenciada. De manera similar, cuando se modifica (escribe) una página, se establece un bit de modificación. La configuración de los bits normalmente la realiza el hardware, aunque también es posible hacerlo a nivel de software.

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

3. referencia, modificada

2. referencias, no modificadas

1. not referenced, modified

0. no referenciado, no modificado

Aunque no parece posible modificar una página sin hacer referencia a ella, esto sucede cuando la interrupción del temporizador borra el bit de referencia de una página de clase 3. El algoritmo NRU selecciona una página aleatoria de la categoría más baja para eliminarla. Entonces, de las cuatro categorías de páginas anteriores, el algoritmo NRU reemplazará una página no referenciada ni modificada, si dicha página existe. Tenga en cuenta que este algoritmo implica que una página modificada pero a la que no se hace referencia (dentro del último intervalo de tiempo) es menos importante que una página no modificada a la que se hace referencia intensamente.

NRU es un algoritmo de marcación, así que es ${fnMicroc} {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ágina primero en entrar, primero en salir (FIFO) es un algoritmo de baja sobrecarga que requiere poca contabilidad por parte del sistema operativo. La idea es obvia por el nombre: el sistema operativo realiza un seguimiento de todas las páginas en la memoria en una cola, con la llegada más reciente al final y la más antigua al frente. Cuando es necesario reemplazar una página, se selecciona la página al principio de la cola (la página más antigua). Si bien FIFO es barato e intuitivo, su rendimiento es deficiente en la aplicación práctica. Por lo tanto, rara vez se utiliza en su forma no modificada. Este algoritmo experimenta la anomalía de Bélády. En palabras simples, ante un fallo de página se reemplaza el fotograma que lleva más tiempo en la memoria.

El sistema operativo OpenVMS utiliza el algoritmo de reemplazo de páginas FIFO, con algunas modificaciones. Se proporciona una segunda oportunidad parcial al omitir un número limitado de entradas con referencias de tablas de traducción válidas 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 aún no se reutilizan.

FIFO es un algoritmo conservador, así que es ${fnMicroc} {k}{k-h+1}}$- competitivo.

Segunda oportunidad

Una forma modificada del algoritmo de reemplazo de páginas FIFO, conocido como algoritmo de reemplazo de páginas de segunda oportunidad, funciona relativamente mejor que FIFO a un bajo costo de mejora. Funciona mirando al frente de la cola como lo hace FIFO, pero en lugar de paginar inmediatamente esa página, verifica si su bit de referencia está establecido. Si no está configurado, la página se cambia. De lo contrario, se borra el bit referenciado, la página se inserta al final de la cola (como si fuera una página nueva) y se repite este proceso. Esto también se puede considerar como una cola circular. Si todas las páginas tienen su bit de referencia configurado, en el segundo encuentro de la primera página de la lista, esa página se intercambiará, ya que ahora su bit de referencia se ha borrado. Si todas las páginas tienen su bit de referencia borrado, entonces el algoritmo de segunda oportunidad degenera en FIFO puro.

Como sugiere su nombre, Second-Channel le da a cada página una "segunda oportunidad" – una página antigua a la que se ha hecho referencia probablemente esté en uso y no debe cambiarse por una página nueva a la que no se ha hecho referencia.

Reloj

Clock es una versión más eficiente de FIFO que Second-Chance porque las páginas no tienen que estar constantemente al final de la lista, pero realiza la misma función general que Second-Chance. El algoritmo del reloj mantiene una lista circular de páginas en la memoria, con la "manecilla" (iterador) que apunta al último marco de página examinado en la lista. Cuando se produce un error de página y no existen marcos vacíos, se inspecciona el bit R (referenciado) en la ubicación de la mano. Si R es 0, la nueva página se coloca en lugar de la página que contiene la "mano" señala y la mano avanza una posición. De lo contrario, se borra el bit R, luego se incrementa la manecilla del reloj y se repite el proceso hasta que se reemplaza una página. Este algoritmo fue descrito por primera vez en 1969 por Fernando J. Corbató.

Variantes de reloj

• GCLOCK: algoritmo de sustitución de página de reloj generalizado.
• Clock-Pro mantiene una lista circular de información sobre páginas de referencia recientemente, incluyendo todas las páginas M en memoria, así como las páginas M más recientes que han sido publicadas. Esta información extra en páginas desplegadas, como la información similar mantenida por ARC, le ayuda a trabajar mejor que LRU en grandes lazos y escaneos de una sola vez.
• WSclock. Al combinar el algoritmo del reloj con el concepto de un conjunto de trabajo (es decir, el conjunto de páginas espera ser utilizado por ese proceso durante algún intervalo de tiempo), 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ágina más importantes.
• Reloj con Reemplazo Adaptable (CAR) es un algoritmo de reemplazo de página que tiene un rendimiento comparable a ARC, y supera sustancialmente tanto LRU como CLOCK. El algoritmo CAR es automático y no requiere parámetros mágicos especificados por el usuario.

CLOCK es un algoritmo conservador, así que es ${fnMicroc} {k}{k-h+1}}$- competitivo.

Menos utilizada recientemente

El algoritmo de reemplazo de páginas utilizado menos recientemente (LRU), aunque similar en nombre a NRU, difiere en el hecho de que LRU realiza un seguimiento del uso de la página durante un corto período de tiempo, mientras que NRU solo analiza el uso en el último reloj. intervalo. LRU trabaja con la idea de que las páginas que se han utilizado más en las últimas instrucciones probablemente también se utilizarán mucho en las siguientes instrucciones. Si bien LRU puede proporcionar un rendimiento casi óptimo en teoría (casi tan bueno como el caché de reemplazo adaptativo), 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 y al mismo tiempo mantener el mayor rendimiento posible.

El método más caro es el método de lista enlazada, que utiliza una lista enlazada que contiene todas las páginas en la memoria. Al final de esta lista se encuentra la página utilizada menos recientemente y al frente está la página utilizada más recientemente. El costo de esta implementación radica en el hecho de que los elementos de la lista deberán moverse en cada referencia de memoria, lo cual es un proceso que requiere 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, adquiere el valor igual al contador en el momento del acceso a la página. Siempre que es necesario reemplazar una página, el sistema operativo selecciona la página con el contador más bajo y la intercambia.

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

Una ventaja importante del algoritmo LRU es que se puede realizar un análisis estadístico completo. Se ha demostrado, por ejemplo, que LRU nunca puede generar más de N veces más errores 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 es que su desempeño tiende a degenerar bajo muchos patrones de referencia bastante comunes. Por ejemplo, si hay N páginas en el grupo LRU, una aplicación que ejecute un bucle sobre una matriz de N + 1 páginas provocará un error de página en todos y cada uno de los accesos. Como los bucles sobre matrices grandes son comunes, se ha puesto mucho esfuerzo en modificar LRU para que funcione mejor en tales situaciones. Muchas de las modificaciones de LRU propuestas intentan detectar patrones de referencia en bucle y cambiar a un algoritmo de reemplazo adecuado, como el utilizado más recientemente (MRU).

Variantes de LRU

1. LRU-K desaloja la página cuyo acceso K-th más reciente es más lejano en el pasado. Por ejemplo, LRU-1 es simplemente LRU mientras que LRU-2 desaloja páginas según el tiempo de su acceso penúltimo. LRU-K mejora mucho en LRU con respecto a la localidad a tiempo.
2. El algoritmo ARC extiende LRU manteniendo una historia de páginas recientemente desalojadas y utiliza esto para cambiar la preferencia al acceso reciente o frecuente. Es particularmente resistente a los escaneos secuenciales.
3. El algoritmo 2Q mejora sobre el algoritmo LRU y LRU/2. Al tener dos colas, una para artículos de calentar y la otra para artículos de ralentización, los artículos se colocan primero en la cola de ralentización y después de un segundo acceso de los elementos colocados en los puntos de calentar. Debido a que las referencias a elementos añadidos son más largas que en el algoritmo LRU y LRU/2, tiene una cola mejor que mejora la tasa de éxito de la caché.

Puede encontrar una comparación de ARC con otros algoritmos (LRU, MQ, 2Q, LRU-2, LRFU, LIRS) en Megiddo & Modha 2004.

LRU es un algoritmo de marcación, así que es ${fnMicroc} {k}{k-h+1}}$- competitivo.

Aleatorio

El algoritmo de reemplazo aleatorio reemplaza una página aleatoria en la memoria. Esto elimina los costos generales de rastrear las referencias de las páginas. Por lo general, funciona mejor que FIFO y para referencias de memoria en bucle es mejor que LRU, aunque generalmente LRU funciona mejor en la práctica. OS/390 utiliza una aproximación LRU global y recurre al reemplazo aleatorio cuando el rendimiento de LRU degenera, y el procesador Intel i860 utilizó una política de reemplazo aleatorio (Rhodehamel 1989).

No utilizada con frecuencia (NFU)

El algoritmo de reemplazo de páginas no utilizado con frecuencia (NFU) requiere un contador, y cada página tiene un contador propio que inicialmente se establece en 0. En cada intervalo de reloj, todas las páginas a las que se ha hecho referencia dentro de ese intervalo tendrán su contador incrementado en 1. De hecho, los contadores realizan un seguimiento de la frecuencia con la que se ha utilizado una página. Por lo tanto, la página con el contador más bajo se puede cambiar cuando sea necesario.

El principal problema de NFU es que realiza un seguimiento de la frecuencia de uso sin tener en cuenta el período de uso. Por lo tanto, en un compilador de múltiples pasadas, las páginas que se usaron mucho durante la primera pasada, pero que no son necesarias en la segunda pasada, serán favorecidas sobre las páginas que se usan relativamente poco en la segunda pasada, ya que tienen contadores de frecuencia más altos. Estos resultados son pobres en rendimiento. Existen otros escenarios comunes en los que NFU funcionará de manera similar, como el inicio del sistema operativo. Afortunadamente, existe un algoritmo similar y mejor, y su descripción se encuentra a continuación.

El algoritmo de reemplazo de páginas que no se usa con frecuencia genera menos errores de página que el algoritmo de reemplazo de páginas usado menos recientemente cuando la tabla de páginas contiene valores de puntero nulos.

Envejecimiento

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

El siguiente código Python simula el algoritmo de envejecimiento. Contratistas ${displaystyle V_{i}$ se inicializan con 0 actualizada como se describe anteriormente ${displaystyle V_{i}leftarrow (R_{i}ll (k-1) 1)}$, usando operadores de cambio aritméticos.

desde collections.abc importación Secuenciadef simular_aging()Rs: Secuencia, k: int) - No. Ninguno: # Simular el envejecimiento impresión()" t peru R-bits (0-{length}) Contratistas para páginas 0-{length}".formato()longitud=Len()Rs)) Vs = [0] * Len()Rs[0]) para t, R dentro enumerado()Rs): Vs[:] = [R[i] c) c) ()k - 1) Silencio V " 1 para i, V dentro enumerado()Vs) impresión()"{:02d} Silencio {} Silencio{}].formato()t, R, ", ".Únase([2]"{:0{}b).formato()V, k) para V dentro Vs])

En el ejemplo dado de R-bits para 6 páginas más de 5 relojes, la función imprime la siguiente salida, que lista los R-bits para cada reloj marca t y los valores opuestos individuales ${displaystyle V_{i}$ para cada página en representación binaria.

, titulado Rs = [[2]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]], titulado k = 8, titulado simular_aging()Rs, k) t ← R-bits (0-5) Silenciosos para páginas 0-500 Silencio [1, 0, 1, 0, 1, 1] Silencio [10000000, 00000000, 10000000, 00000000000, 10000000000, 10000000, 10000000000000]01 Silencio [1, 1, 0, 0, 1, 0] Silencioso [11000000, 10000000, 01000000, 00000000, 11000000, 01000000000]02 Silenciosos [1, 1, 0, 1, 0, 1] Silenciosos [11100000, 11000000, 00100000, 10000000, 01100000, 10100000]03 Silencio [1, 0, 0, 0, 1, 0] Silencioso [11110000, 01100000, 00010000, 01000000, 10110000, 01010000]04 Silencio [0, 1, 1, 0, 0, 0] Silencioso [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 último 16 /32 (dependiendo del tamaño de bits de los enteros del procesador) intervalos de tiempo. En consecuencia, es posible que dos páginas hayan hecho referencia a contadores de 00000000, aunque una página haya sido referenciada hace 9 intervalos y la otra hace 1000 intervalos. En términos generales, conocer el uso en los últimos 16 intervalos es suficiente para tomar una buena decisión sobre qué página cambiar. Por tanto, el envejecimiento puede ofrecer un rendimiento casi óptimo por un precio moderado.

Algoritmo de reemplazo de página de mayor distancia primero (LDF)

La idea básica detrás de este algoritmo es la Localidad de Referencia como se usa en LRU, pero la diferencia es que en LDF, la localidad se basa en la distancia, no en las referencias utilizadas. En el LDF, reemplace 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 que está al lado de la página actual en rotación antirreloj.

Detalles de implementación

Técnicas para hardware sin broca de referencia

Muchas de las técnicas analizadas anteriormente suponen la presencia de un bit de referencia asociado con cada página. Algunos hardware no tienen ese bit, por lo que su uso eficiente requiere técnicas que funcionen bien 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 secundarias. Las páginas eliminadas de los conjuntos de trabajo (memoria privada de proceso, generalmente) se colocan en listas de propósitos especiales y permanecen en la memoria física durante algún tiempo. Eliminar una página de un conjunto de trabajo no es técnicamente una operación de reemplazo de página, pero identifica efectivamente esa página como candidata. Una página cuyo almacén de respaldo aún es válido (cuyo contenido no está sucio o no necesita ser preservado) se coloca al final de la Lista de páginas gratuitas. Una página que requiera escritura en la tienda de respaldo se colocará en la Lista de páginas modificadas. Estas acciones normalmente se activan cuando el tamaño de la lista de páginas libres cae por debajo de un umbral ajustable.

Las páginas se pueden seleccionar para eliminar el conjunto de trabajo de forma esencialmente aleatoria, con la expectativa de que si se hace una mala elección, una referencia futura pueda recuperar esa página de la lista Libre o Modificada antes de que se elimine de la memoria física. Una página a la que se haga referencia de esta manera se eliminará de la lista Libre o Modificada y se volverá a colocar en un conjunto de trabajo de proceso. La lista de páginas modificadas también brinda la oportunidad de escribir páginas en la tienda de respaldo en grupos de más de una página, lo que aumenta la eficiencia. Estas páginas luego se pueden colocar en la Lista de páginas gratuitas. La secuencia de páginas que llega hasta el encabezado 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 es el que utiliza el kernel de Linux en ARM. La falta de funcionalidad del hardware se compensa proporcionando dos tablas de páginas: las tablas de páginas nativas del procesador, sin bits referenciados ni bits sucios, y tablas de páginas mantenidas por software con los bits requeridos presentes. Los bits emulados en la tabla mantenida por software se configuran mediante errores de página. Para eliminar los errores de página, borrar los bits emulados en la segunda tabla revoca algunos de los derechos de acceso a la página correspondiente, lo que se implementa alterando la tabla nativa.

Caché de página en Linux

Linux utiliza una caché de páginas unificada para

• brk and anonymous mmaped-regions. Esto incluye el montón y la pila de programas del espacio-usuario. Está escrito para cambiar cuando se escribe.
• Non-anonymous (file-backed) mmapRegiones de Ed. Si está presente en la memoria y no modificado privadamente la página física se comparte con el archivo cache o buffer.
• Memoria compartida adquirida a través de shm_open.
• Los tmpfs in-memory filesystem; escrito para cambiar cuando se envía a cabo.
• El caché de archivo incluyendo; escrito al almacenamiento de bloques subyacentes (posiblemente pasando por el búfer, ver abajo) cuando se envía a cabo.
• El caché de los dispositivos de bloques, llamado el "buffer" de Linux (para no confundirse con otras estructuras también llamadas búferes como los utilizados para tuberías y búferes utilizados internamente en Linux); escrito al almacenamiento subyacente cuando se envía a cabo.

La caché de páginas unificada funciona 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 siguiente tamaño mayor (2 MiB en x86-64) llamadas &# 34;páginas enormes" por Linux. Las páginas en la caché de páginas se dividen en una categoría "activa" establecido y un "inactivo" colocar. Ambos conjuntos mantienen una lista de páginas LRU. En el caso básico, cuando un programa de espacio de usuario accede a una página, ésta se coloca en la cabecera del conjunto inactivo. Cuando se accede 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 de cualquier espacio de direcciones de proceso, sin ser paginada fuera de la memoria física. Cuando se elimina una página del conjunto inactivo, se elimina de la memoria física. El tamaño del archivo "activo" y "inactivo" La lista se puede consultar desde /proc/meminfo en los campos "Activo", "Inactivo", "Activo(anon)", "Inactivo(anon)", "Activo(archivo)" y "Inactivo(archivo)".

Conjunto de trabajo

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

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