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 es necesario asignar una página de memoria. 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 el número de páginas libres es inferior a cierto umbral.
Cuando se hace referencia nuevamente 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ágina, 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 mismo.
El problema de 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.
Los algoritmos de reemplazo de páginas fueron un tema candente de investigación y debate en las décadas de 1960 y 1970. En su mayor parte, eso terminó 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:
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.
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 la partición fija y los algoritmos de conjuntos equilibrados 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. [1]
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 contiene un bit de "acceso" y un bit "sucio" 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:
read
y write
en POSIX.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 afrontar 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 paginación (h,k) es una generalización del modelo del problema de paginación: Sean h,k números enteros positivos tales que . Medimos el rendimiento de un algoritmo con tamaño de caché en relación con el algoritmo de reemplazo de página teóricamente óptimo. Si es así , proporcionamos el algoritmo de reemplazo de página óptimo con estrictamente menos recursos.
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.
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 marcado con una caché de tamaño k y OPT es el algoritmo óptimo con una caché de tamaño h, donde , entonces ALG es competitivo. Por tanto, cada algoritmo de marcado alcanza la relación competitiva.
LRU es un algoritmo de marcado, mientras que FIFO no es un algoritmo de marcado.
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 , entonces ALG es competitivo. Por tanto, todo algoritmo conservador alcanza la relación competitiva.
LRU, FIFO y CLOCK son algoritmos conservadores.
Hay una variedad de algoritmos de reemplazo de páginas: [2]
El algoritmo de reemplazo de página teóricamente óptimo (también conocido como OPT, algoritmo de reemplazo clarividente o política de reemplazo de página óptima de Bélády ) [3] [4] [2] es un algoritmo que funciona de la siguiente manera: cuando es necesario intercambiar una página, la El sistema operativo cambia 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 ser implementado. 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 [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 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 aleatorios en línea para el problema de paginación se mide mediante un análisis amortizado .
El algoritmo de reemplazo de páginas no utilizadas recientemente (NRU) es un algoritmo que favorece mantener en 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, de modo 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:
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 marcado, por lo que es competitivo.
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. [6] Se proporciona una segunda oportunidad parcial al omitir un número limitado de entradas con referencias de tablas de traducción válidas, [7] y, además, las páginas se desplazan del conjunto de trabajo del proceso a un conjunto de todo el sistema desde el cual se pueden recuperar si aún no se reutilizan. .
FIFO es un algoritmo conservador, por lo que es competitivo.
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 con 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, Segunda oportunidad 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 intercambiarse por una página nueva a la que no se ha hecho referencia.
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 de reloj mantiene una lista circular de páginas en la memoria, con la "mano" (iterador) apuntando al último marco de página examinado en la lista. Cuando ocurre un error de página y no existen marcos vacíos, entonces 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 a la que apunta la "mano" 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. [8] Este algoritmo fue descrito por primera vez en 1969 por Fernando J. Corbató . [9]
CLOCK es un algoritmo conservador, por lo que es competitivo.
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 intervalo de reloj. 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).
Se puede encontrar una comparación de ARC con otros algoritmos (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) en Megiddo & Modha 2004. [19]
LRU es un algoritmo de marcado, por lo que es competitivo.
El algoritmo de reemplazo aleatorio reemplaza una página aleatoria en la memoria. Esto elimina los costos generales del seguimiento de 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 [20] ).
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, se incrementará el contador de todas las páginas a las que se haya hecho referencia dentro de ese intervalo. 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.
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. Los contadores se inicializan con0 y actualizado como se describe anteriormente mediante , utilizando operadores de desplazamiento aritméticos .
de colecciones.abc importar secuenciadef simular_envejecimiento ( Rs : Secuencia , k : int ) -> Ninguno : # Simular envejecimiento print ( "t | R-bits (0- {longitud} ) | Contadores para páginas 0- {longitud} " . formato ( longitud = len ( Rs ))) Vs = [ 0 ] * len ( Rs [ 0 ]) para t , R en enumerar ( Rs ): Vs [:] = [ R [ i ] << ( k - 1 ) | V >> 1 para i , V en enumerar ( Vs )] print ( " {:02d} | {} | [ {} ]" . format ( t , R , ", " . join ([ "{:0 {} b}" . formato ( V , k ) para V en Vs ])))
En el ejemplo dado de bits R para 6 páginas en 5 ciclos de reloj, la función imprime el siguiente resultado, que enumera los bits R para cada ciclo de reloj t y los valores de contador individuales 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 >>> simular_envejecimiento ( Rs , k ) t | Bits R (0-5) | Contadores para 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 las últimasIntervalos de tiempo de 16/32 (dependiendo del tamaño de bits de los números enteros del procesador). 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.
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. [ cita necesaria ]
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 conservado) 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 al 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 lo 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.
Linux utiliza un caché de página unificado para
mmap
educativas anónimas . Esto incluye el montón y la pila de programas del espacio de usuario . Está escrito para intercambiarse cuando se pagina.mmap
Regiones de edición 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 el caché o el búfer de archivos.shm_open
.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 siguiente tamaño más grande (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 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. [22] [23] Cuando se elimina una página del conjunto inactivo, se elimina de la memoria física. El tamaño de la lista "activo" e "inactivo" se puede consultar /proc/meminfo
en los campos "Activo", "Inactivo", "Activo(anon)", "Inactivo(anon)", "Activo(archivo)" e "Inactivo (archivo)".
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 ) [ se necesita aclaración ]