En un sistema operativo de computadora que utiliza paginación para la administración de memoria virtual , los algoritmos de reemplazo de páginas deciden qué páginas de memoria se deben paginar, a veces llamado intercambio, o escribir en el disco, cuando se necesita asignar una página de memoria. El reemplazo de páginas ocurre cuando una página solicitada no está en la memoria ( error 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 menor que un umbral determinado.
Cuando se vuelve a hacer referencia a la página que se seleccionó para reemplazar y se envió a la página de salida, se debe enviar a la página de entrada (leer desde el disco), y esto implica esperar a que se complete la operación de E/S. Esto determina la calidad del algoritmo de reemplazo de páginas: cuanto menos tiempo se espere para recibir 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 se deben reemplazar para minimizar la cantidad total de páginas perdidas, al mismo tiempo que se equilibra esto con los costos (almacenamiento primario y tiempo de procesador) del algoritmo en sí.
El problema de reemplazo de páginas es un problema en línea típico 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 de gran interés en la investigación y el debate en las décadas de 1960 y 1970. Esto terminó en gran parte con el desarrollo de aproximaciones LRU (menos utilizadas recientemente) y algoritmos de conjuntos de trabajo sofisticados . Desde entonces, algunas suposiciones básicas hechas por los algoritmos tradicionales de reemplazo de páginas se invalidaron, lo que resultó en un resurgimiento de la investigación. En particular, las siguientes tendencias en el comportamiento del hardware subyacente y el 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 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 unificada y cachés del sistema de archivos, lo que requiere que el algoritmo de reemplazo de páginas seleccione una página de entre las páginas de los espacios de direcciones virtuales del programa de usuario y los archivos en caché. Las últimas páginas tienen propiedades específicas. Por ejemplo, pueden estar bloqueadas o pueden tener requisitos de orden de escritura impuestos por el registro en diario . Además, como el objetivo del reemplazo de páginas es minimizar el tiempo total de espera de la 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 en el nivel de un asignador de memoria del núcleo 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 incurre en 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 tiene la libertad de seleccionar cualquier página en la memoria.
El reemplazo de páginas local supone algún tipo 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 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 fallos de página de forma independiente, lo que conduce a un rendimiento más consistente para ese proceso. Sin embargo, el reemplazo de páginas global es más eficiente a nivel de sistema general. [1]
Las computadoras modernas de propósito 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 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 "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 sucio. El sistema operativo puede detectar accesos a la memoria y a los archivos a través de los siguientes medios:
ready writeen 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 la 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ó primero en sistemas con canales dúplex completos al almacenamiento estable y la limpieza se superponía habitualmente con la paginación. El hardware actual, por otro lado, no admite transferencias dúplex completas y la limpieza de las páginas de destino se convierte en un problema.
Para lidiar con esta situación, se implementan varias políticas de prelimpieza . La prelimpieza es el mecanismo que inicia la E/S en páginas sucias que (probablemente) se reemplazarán pronto. La idea es que para cuando la página prelimpiada sea realmente seleccionada para el reemplazo, la E/S se completará y la página estará limpia. La prelimpieza supone que es posible identificar las páginas que serán reemplazadas a continuación . Una prelimpieza demasiado ansiosa puede desperdiciar ancho de banda de E/S al escribir páginas que logran volver a ensuciarse antes de ser seleccionadas para el reemplazo.
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 caché de tamaño relativo al algoritmo de reemplazo de páginas teóricamente óptimo. Si , proporcionamos el algoritmo de reemplazo de páginas ó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 no marcadas. 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 pagina una página marcada.
Si ALG es un algoritmo de marcado con un caché de tamaño k y OPT es el algoritmo óptimo con un caché de tamaño h, donde , entonces ALG es -competitivo. Por lo tanto, todo 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 fallos 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 lo tanto, todo algoritmo conservador alcanza la relación -competitiva.
LRU, FIFO y CLOCK son algoritmos conservadores.
Existen diversos 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 óptima de reemplazo de página de Bélády ) [3] [4] [2] es un algoritmo que funciona de la siguiente manera: cuando es necesario reemplazar una página, el sistema operativo reemplaza la página cuyo próximo uso ocurrirá en el futuro más lejano. Por ejemplo, una página que no se va a utilizar durante los próximos 6 segundos se reemplazará por una página que se va a utilizar dentro de 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 use 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 [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 ingresar y eliminar 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 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 utilizando el análisis amortizado .
El algoritmo de reemplazo de páginas no utilizadas recientemente (NRU) es un algoritmo que favorece el mantenimiento en memoria de 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 una página (se escribe en ella), 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 intervalo de tiempo fijo, se activa una interrupción del temporizador y se 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 de tiempo actual se marcan con un bit de referencia. Cuando es necesario reemplazar una página, el sistema operativo divide las páginas en cuatro clases:
Aunque no parece posible que una página se modifique pero no se haga 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 elige una página aleatoria de la categoría más baja para eliminarla. Por lo tanto, 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 no referenciada (dentro del último intervalo del temporizador) es menos importante que una página no modificada pero referenciada intensamente.
NRU es un algoritmo de calificación, por lo tanto es competitivo.
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 costo que requiere poca contabilidad por parte del sistema operativo . La idea es obvia desde 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 llegada más antigua al frente. Cuando es necesario reemplazar una página, se selecciona la página al frente de la cola (la página más antigua). Si bien FIFO es económico e intuitivo, su rendimiento en la aplicación práctica es deficiente. Por lo tanto, rara vez se usa en su forma sin modificar. Este algoritmo experimenta la anomalía de Bélády . En palabras simples, en caso de falla de página, se reemplaza el marco que ha estado en la 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 aún no se han reutilizado.
FIFO es un algoritmo conservador, por lo tanto es competitivo.
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 a un bajo costo de mejora. Funciona mirando el frente de la cola como lo hace FIFO, pero en lugar de paginar inmediatamente esa página, verifica si su bit de referencia está configurado. Si no está configurado, la página se intercambia. De lo contrario, el bit de referencia se borra, 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 configurado, en el segundo encuentro de la primera página en la lista, esa página se intercambiará, ya que ahora tiene su bit de referencia 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-chance 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 debería reemplazarse 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 ser empujadas constantemente 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, entonces el bit R (referenciado) se inspecciona en la ubicació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 la manecilla avanza una posición. De lo contrario, el bit R se borra, luego la manecilla del reloj 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]
CLOCK es un algoritmo conservador, por lo que es competitivo.
El algoritmo de reemplazo de páginas menos utilizado recientemente (LRU), aunque tiene un nombre similar al NRU, se diferencia en que LRU realiza un seguimiento del uso de las páginas durante un corto período de tiempo, mientras que NRU solo observa el uso en el último intervalo de reloj. LRU funciona sobre la idea de que las páginas que se han utilizado con mayor frecuencia en las últimas instrucciones tienen más probabilidades de utilizarse también con mayor frecuencia en las próximas instrucciones. Si bien LRU puede proporcionar un rendimiento casi óptimo en teoría (casi tan bueno como el caché de reemplazo adaptativo ), es bastante costoso de implementar en la práctica. Hay algunos métodos de implementación para este algoritmo que intentan reducir el costo y, al mismo tiempo, mantener la mayor parte posible del rendimiento.
El método más costoso es el de lista enlazada, que utiliza una lista enlazada que contiene todas las páginas en memoria. Al final de esta lista se encuentra la página menos utilizada recientemente y al frente, la más utilizada 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 que 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 en cada instrucción. Siempre que se accede a una página, adquiere el valor igual al del contador en el momento del acceso a la página. Siempre que se necesita reemplazar una página, el sistema operativo selecciona la página con el contador más bajo y la reemplaza.
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 analizar estadísticamente en su totalidad. Se ha demostrado, por ejemplo, que el algoritmo 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 del grupo administrado.
Por otro lado, la debilidad de LRU es que su rendimiento tiende a degenerar bajo muchos patrones de referencia bastante comunes. Por ejemplo, si hay N páginas en el grupo de 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 invertido mucho esfuerzo en modificar LRU para que funcione mejor en tales situaciones. Muchas de las modificaciones propuestas de LRU intentan detectar patrones de referencia de bucle y cambiar a un algoritmo de reemplazo adecuado, como Most Recently Used (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 el costo adicional de rastrear referencias de página. 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 usa una aproximación LRU global y vuelve al reemplazo aleatorio cuando el rendimiento de LRU degenera, y el procesador Intel i860 usó una política de reemplazo aleatorio (Rhodehamel 1989 [20] ).
El algoritmo de reemplazo de páginas que no se usan con frecuencia (NFU) requiere un contador, y cada página tiene su propio contador que inicialmente se establece en 0. En cada intervalo de reloj, todas las páginas a las que se hizo referencia dentro de ese intervalo tendrán su contador incrementado en 1. En efecto, los contadores registran la frecuencia con la que se ha usado una página. Por lo tanto, la página con el contador más bajo se puede cambiar cuando sea necesario.
El principal problema con NFU es que lleva un registro de la frecuencia de uso sin tener en cuenta el lapso de tiempo 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 se necesitan en la segunda, tendrán preferencia sobre las páginas que se usan comparativamente poco en la segunda pasada, ya que tienen contadores de frecuencia más altos. Esto da como resultado un rendimiento deficiente. Existen otros escenarios comunes en los que NFU tendrá un rendimiento similar, como el arranque del sistema operativo. Afortunadamente, existe un algoritmo similar y mejor, y su descripción se incluye a continuación.
El algoritmo de reemplazo de página no utilizado con frecuencia genera menos errores de página que el algoritmo de reemplazo de página utilizado menos recientemente cuando la tabla de páginas contiene valores de puntero nulo.
El algoritmo de envejecimiento es un descendiente del algoritmo NFU, con modificaciones para que tenga en cuenta el lapso de tiempo de uso. En lugar de simplemente incrementar los contadores de las páginas referenciadas, poniendo el mismo énfasis en las referencias de página independientemente del tiempo, el contador de referencia de una página primero se desplaza a 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 ticks de reloj, su contador de referencia se verá así en orden cronológico: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Las referencias de página más cercanas al tiempo presente tienen más impacto que las referencias de página de hace mucho tiempo. Esto garantiza que las páginas referenciadas más recientemente, aunque menos frecuentemente, tendrán mayor prioridad sobre las páginas referenciadas con mayor frecuencia en el pasado. De esta forma, 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 se actualiza como se describe anteriormente a través de , utilizando operadores de desplazamiento aritmético .
de colecciones.abc importar secuenciadef simular_envejecimiento ( Rs : Secuencia , k : int ) -> Ninguno : # Simular envejecimiento print ( "t | R-bits (0- {length} ) | Contadores para páginas 0- {length} " . format ( length = 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}" .format ( V , k ) para V en Vs ]))) En el ejemplo dado de R-bits para 6 páginas durante 5 ticks de reloj, la función imprime la siguiente salida, que enumera los R-bits para cada tick 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 ] ] >>> k = 8 >>> simular_envejecimiento ( 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 la última16/32 (dependiendo del tamaño de bits de los enteros del procesador). En consecuencia, dos páginas pueden tener contadores referenciados 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 dentro de los últimos 16 intervalos es suficiente para tomar una buena decisión sobre qué página reemplazar. Por lo 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 que se utiliza en LRU, pero la diferencia es 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 que esté junto a la página actual en rotación contraria al reloj. [ cita requerida ]
Muchas de las técnicas que se han analizado anteriormente presuponen la presencia de un bit de referencia asociado a cada página. Algunos equipos no tienen dicho 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 se ha modificado una página, pero no necesariamente si se ha leído. Su enfoque se conoce como almacenamiento en caché de páginas secundarias. Las páginas eliminadas de los conjuntos de trabajo (memoria privada del proceso, generalmente) se colocan en listas de propósito especial mientras 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 almacenamiento de respaldo aún es válido (cuyo contenido no está sucio o no necesita conservarse de otro modo) se coloca al final de la lista de páginas libres. Una página que requiere escritura en el almacenamiento de respaldo 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 se pueden seleccionar para su eliminación en el conjunto de trabajo de una manera esencialmente 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 a la que se haga referencia de esta manera se eliminará de la lista de páginas libres o modificadas y se colocará nuevamente en un conjunto de trabajo de proceso. La lista de páginas modificadas proporciona además una oportunidad para 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 se pueden colocar luego en la lista de páginas libres. La secuencia de páginas que avanza hasta el comienzo 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 de hardware se compensa proporcionando dos tablas de páginas: las tablas de páginas nativas del procesador, sin bits referenciados ni bits sucios , y las tablas de páginas mantenidas por software con los bits necesarios presentes. Los bits emulados en la tabla mantenida por software se establecen mediante errores de página. Para obtener los errores 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 que se implementa modificando la tabla nativa.
Linux utiliza un caché de página unificado para
mmaped anónimas. Esto incluye el montón y la pila de programas del espacio de usuario . Está escrito para intercambiarse cuando se pagina.mmap. Si están presentes en la memoria y no se modifican 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 soportado 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 LRU de páginas. En el caso básico, cuando un programa de espacio de usuario accede a una página, 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 paginarse 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 /proc/meminfoen los campos "Activo", "Inactivo", "Activo(anónimo)", "Inactivo(anónimo)", "Activo(archivo)" e "Inactivo(archivo)".
El conjunto de trabajo de un proceso es el conjunto de páginas que se espera que utilice ese proceso durante un intervalo de tiempo determinado.
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 de mediano plazo ) [ aclaración necesaria ]