En un sistema operativo de computadora que usa la paginación para la administración de la memoria virtual , los algoritmos de reemplazo de página deciden qué páginas de memoria se deben paginar , lo que a veces se denomina 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 ( error de página ) y una página libre no puede usarse para satisfacer la asignación, ya sea porque no hay ninguna o porque el número de páginas libres es menor que algún umbral.
Cuando se vuelve a hacer referencia a la página que se seleccionó para el reemplazo y se paginó, 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ágina: cuanto menos tiempo de espera para las entradas de página, mejor es el algoritmo. Un algoritmo de reemplazo de página 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 sustitución de páginas es un problema online típico 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ágina fueron un tema candente de investigación y debate en las décadas de 1960 y 1970. Eso terminó principalmente con el desarrollo de aproximaciones sofisticadas de LRU (menos utilizadas recientemente) y algoritmos de conjuntos de trabajo . Desde entonces, se invalidaron algunas suposiciones básicas hechas por los algoritmos tradicionales de reemplazo de página, 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:
- El tamaño del almacenamiento primario ha aumentado en varios órdenes de magnitud. Con varios gigabytes de memoria primaria, los algoritmos que requieren una verificación periódica de todos y cada uno de los marcos de memoria son cada vez menos prácticos.
- Las jerarquías de la memoria se han vuelto más altas. El costo de una falla en la memoria caché de la CPU es mucho más caro. 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 orientadas a objetos que favorecen un gran número de funciones pequeñas, el uso de estructuras de datos sofisticadas como árboles y tablas hash que tienden a dar como resultado patrones de referencia de memoria caóticos y el advenimiento de la recolección de basura que cambió drásticamente 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 kernel del sistema operativo . En particular, la mayoría de los núcleos de sistemas operativos modernos tienen memorias virtuales unificadas 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 en caché. Las últimas páginas tienen propiedades específicas. Por ejemplo, pueden estar bloqueados o pueden tener requisitos de orden de escritura impuestos por el diario . 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 kernel que asignan memoria. Como resultado, el reemplazo de páginas en los núcleos modernos ( Linux , FreeBSD y Solaris ) tiende a funcionar al nivel de un asignador de memoria del núcleo de propósito general, en lugar del nivel superior de un subsistema de memoria virtual.
Reemplazo local versus global
Los algoritmos de reemplazo pueden ser locales o globales.
Cuando un proceso incurre en una falla de página, un algoritmo de reemplazo de página local selecciona para reemplazar alguna página que pertenece a ese mismo proceso (o un grupo de procesos que comparten una partición de memoria ). Un algoritmo de reemplazo global es libre de seleccionar cualquier página en la memoria.
El reemplazo de página local asume alguna forma de partición de memoria que determina cuántas páginas se asignarán a un proceso dado o un grupo de procesos. Las formas más populares de particionamiento son el particionamiento fijo y los algoritmos de conjuntos equilibrados basados en el modelo del conjunto de trabajo . La ventaja del reemplazo de página local es su escalabilidad: cada proceso puede manejar sus fallas de página de forma independiente, lo que lleva a un rendimiento más consistente para ese proceso. Sin embargo, el reemplazo de página global es más eficiente en el sistema global. [1]
Detectando qué páginas son referenciadas y modificadas
Las computadoras modernas de propósito general y algunos procesadores integrados tienen soporte para 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 de "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 el acceso y los bits sucios. El sistema operativo puede detectar accesos a memoria y archivos a través de los siguientes medios:
- Borrando el bit de acceso en las páginas presentes en la tabla de páginas del proceso. Después de un tiempo, el sistema operativo escanea la tabla de páginas en busca de páginas que tengan el bit de acceso establecido por la CPU. Esto es rápido porque el bit de acceso lo establece automáticamente la CPU y es inexacto porque el sistema operativo no recibe notificación inmediata del acceso ni tiene información sobre el orden en el que el proceso accedió a estas páginas.
- Eliminando 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 error de página . Esto es lento porque una falla de página implica un cambio de contexto al 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 al proceso y es preciso porque el acceso se detecta inmediatamente después de que ocurre.
- Directamente cuando el proceso realiza llamadas al sistema que potencialmente acceden a la caché de la página como
read
ywrite
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 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 motivo de gran preocupación, porque la memoria virtual se implementó por primera vez en sistemas con canales dúplex completos para el almacenamiento estable, y la limpieza solía superponerse con la paginación. El hardware básico actual, por otro lado, no admite transferencias full duplex 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 limpieza previa . La limpieza previa 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 previamente limpiada esté seleccionada para el reemplazo, la E / S se completará y la página estará limpia. La limpieza previa asume que es posible identificar las páginas que serán reemplazadas a continuación . Una limpieza previa que es demasiado ansiosa puede desperdiciar el ancho de banda de E / S al escribir páginas que logran volver a ensuciarse antes de ser seleccionadas para su reemplazo.
Paginación anticipada
Algunos sistemas utilizan la paginación por demanda, esperando hasta que se solicite una página antes de cargarla en la RAM.
Otros sistemas intentan reducir la latencia adivinando qué páginas que no están en la RAM probablemente se necesitarán pronto y precargando dichas páginas en la RAM, antes de que se solicite esa página. (Esto a menudo se combina con la limpieza previa, que adivina qué páginas actualmente en la RAM no se necesitarán pronto y las escribe previamente en el almacenamiento).
Cuando ocurre una falla de página, los sistemas de "paginación anticipada" no solo traerán la página referenciada, sino también las siguientes páginas consecutivas (análoga a una cola de entrada de captación previa en una CPU).
El mecanismo de recuperación previa de intercambio va aún más lejos en la carga de páginas (incluso si no son consecutivas) que probablemente se necesitarán pronto.
El problema de la paginación (h, k)
El problema de paginación (h, k) es una generalización del modelo de problema de paginación: sean h, k enteros positivos tales que . Medimos el rendimiento de un algoritmo con caché de tamañoen relación con el algoritmo de sustitución de página teóricamente óptimo . Si, proporcionamos el algoritmo de reemplazo de página óptimo con estrictamente menos recursos.
El problema de la 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 el algoritmo óptimo.
Algoritmos de marcado
Los algoritmos de marcado son una clase general de algoritmos de paginación. Para cada página, lo asociamos con un bit llamado su marca. Inicialmente, configuramos todas las páginas como sin marcar. Durante una etapa de solicitudes de página, 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 una caché de tamaño k, y OPT es el algoritmo óptimo con una caché de tamaño h, donde , entonces ALG es -competitivo. Entonces, cada algoritmo de marcado alcanza el-relación 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ágina distintas, el algoritmo incurrirá en k fallas de página o menos.
Si ALG es un algoritmo conservador con una caché de tamaño k, y OPT es el algoritmo óptimo con una caché de , entonces ALG es -competitivo. Entonces, cada algoritmo conservador alcanza el-relación competitiva.
LRU, FIFO y CLOCK son algoritmos conservadores.
Algoritmos de reemplazo de página
Hay una variedad de algoritmos de reemplazo de página: [2]
El algoritmo de reemplazo de página 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 de reemplazo de página óptima de Bélády ) [3] [4] [2] es un algoritmo que funciona de la siguiente manera: cuando una página necesita ser intercambiada, el 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 cambiará 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 use una página, excepto cuando todo el software que se ejecutará en un sistema se conoce de antemano y es susceptible de ser utilizado. 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 [ cita requerida ] 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 usa esos datos para decidir qué páginas intercambiar dentro y fuera 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 la paginación también se ha realizado en el campo de los algoritmos en línea . La eficiencia de los algoritmos en línea aleatorizados para el problema de la paginación se mide mediante un análisis amortizado .
No utilizado recientemente
El algoritmo de sustitución de páginas no utilizado recientemente (NRU) es un algoritmo que favorece el mantenimiento de las páginas en memoria 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 (se escribe en) una página, se establece un bit modificado. El ajuste de los bits normalmente lo realiza el hardware, aunque también es posible hacerlo a nivel del software.
En un cierto intervalo de tiempo fijo, una interrupción del temporizador activa y borra el bit referenciado de todas las páginas, por lo que solo las páginas referenciadas dentro del intervalo del temporizador actual se marcan con un bit referenciado. Cuando es necesario reemplazar una página, el sistema operativo divide las páginas en cuatro clases:
- 3. referenciado, modificado
- 2. referenciado, no modificado
- 1. no referenciado, modificado
- 0. no referenciado, no modificado
Aunque no parece posible que se modifique una página 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 su eliminación. Por lo tanto, de las cuatro categorías de páginas anteriores, el algoritmo NRU reemplazará una página no referenciada ni modificada si 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 a la que se hace referencia intensamente.
NRU es un algoritmo de marcado, por lo que es -competitivo.
Primero en entrar primero en salir
El algoritmo de reemplazo de página más simple es un 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 llegada 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 económico e intuitivo, tiene un rendimiento deficiente en la aplicación práctica. Por lo tanto, rara vez se usa en su forma no modificada. Este algoritmo experimenta la anomalía de Bélády . En palabras simples, en un error de página, se reemplaza el marco que ha estado más tiempo en la memoria.
El sistema operativo VAX / VMS utiliza el algoritmo de reemplazo de página FIFO , con algunas modificaciones. [5] Se proporciona una segunda oportunidad parcial al omitir un número limitado de entradas con referencias de tabla de traducción válidas, [6] y, además, las páginas se desplazan del conjunto de trabajo del proceso a un conjunto de todo el sistema desde el que se pueden recuperar si no se han reutilizado .
FIFO es un algoritmo conservador, por lo que es -competitivo.
Segunda oportunidad
Una forma modificada del algoritmo de reemplazo de página FIFO, conocido como el algoritmo de reemplazo de página de segunda oportunidad, tiene un precio relativamente mejor que el de FIFO a un costo bajo para la mejora. Funciona mirando al principio de la cola como lo hace FIFO, pero en lugar de paginar inmediatamente esa página, comprueba si su bit de referencia está establecido. Si no está configurado, la página se intercambia. De lo contrario, se borra el bit referenciado, la página se inserta al final de la cola (como si fuera una nueva página) 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 establecido, en el segundo encuentro de la primera página de la lista, esa página se intercambiará, ya que ahora tiene borrado su bit de referencia. Si se borra el bit de referencia de todas las páginas, 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 se debe cambiar por una nueva página 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 "mano" (iterador) apuntando 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 el lugar de la página a la que apunta la "mano" y la mano 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. [7] Este algoritmo fue descrito por primera vez en 1969 por FJ Corbató . [8]
Variantes de reloj
- GCLOCK: algoritmo de reemplazo de página de reloj generalizado. [9]
- Clock-Pro mantiene una lista circular de información sobre las páginas referenciadas recientemente, incluidas todas las páginas M en la memoria, así como las páginas M más recientes que se han paginado. Esta información adicional en las páginas paginadas, como la información similar mantenida por ARC , ayuda a que funcione mejor que LRU en bucles grandes y escaneos únicos. [10]
- WSclock. [11] Combinando el algoritmo Clock con el concepto de un conjunto de trabajo (es decir, el conjunto de páginas que se espera que utilice 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 sustitución de páginas más importantes. [12] [13]
- Clock with Adaptive Replacement (CAR) es un algoritmo de reemplazo de página que tiene un rendimiento comparable al ARC y supera sustancialmente tanto a LRU como a CLOCK. [14] El algoritmo CAR se ajusta automáticamente y no requiere parámetros mágicos especificados por el usuario.
CLOCK es un algoritmo conservador, por lo que es -competitivo.
Menos usado recientemente
El algoritmo de reemplazo de página utilizado menos recientemente (LRU), aunque similar en nombre a NRU, se diferencia 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 observa el uso en el último intervalo de reloj. LRU trabaja con 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 en las próximas instrucciones. Si bien LRU puede proporcionar un rendimiento casi óptimo en teoría (casi tan bueno como la memoria caché de reemplazo adaptativa ), su implementación en la práctica es bastante costosa. Hay algunos métodos de implementación para este algoritmo que intentan reducir el costo y mantener tanto rendimiento como sea 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 que se ha utilizado menos recientemente y, al principio, la página que se ha utilizado 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 que es un proceso que requiere mucho tiempo.
Otro método que requiere soporte de hardware es el siguiente: suponga 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 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 baratas.
Una ventaja importante del algoritmo LRU es que es susceptible de análisis estadístico completo. Se ha demostrado, por ejemplo, que LRU nunca puede generar más de N veces más fallas 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 ejecuta 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 en arreglos grandes son comunes, se ha realizado un gran esfuerzo para 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
- LRU-K [15] desaloja la página cuyo K-ésimo acceso más reciente es el más lejano en el pasado. Por ejemplo, LRU-1 es simplemente LRU mientras que LRU-2 desaloja páginas según el momento de su penúltimo acceso. LRU-K mejora mucho en LRU con respecto a la localidad en el tiempo.
- El algoritmo ARC [16] extiende LRU al mantener un historial de páginas recientemente desalojadas y lo usa para cambiar la preferencia al acceso reciente o frecuente. Es particularmente resistente a exploraciones secuenciales.
Se puede encontrar una comparación de ARC con otros algoritmos (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) en Megiddo & Modha 2004. [17]
LRU es un algoritmo de marcado, por lo que es -competitivo.
Aleatorio
El algoritmo de reemplazo aleatorio reemplaza una página aleatoria en la memoria. Esto elimina los gastos generales de seguimiento de las referencias a las páginas. Por lo general, le va mejor que FIFO, y para las referencias de memoria en bucle es mejor que LRU, aunque generalmente LRU funciona mejor en la práctica. OS / 390 utiliza una aproximación global de LRU 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 [18] ).
No se usa con frecuencia (NFU)
El algoritmo de reemplazo de página que no se usa con frecuencia (NFU) requiere un contador, y cada página tiene un contador propio que se establece inicialmente 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. En efecto, 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 con NFU es que realiza un seguimiento 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 son necesarias en la segunda, se verán favorecidas sobre las páginas que se usan de manera comparable 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 arranque del sistema operativo. Afortunadamente, existe un algoritmo similar y mejor, y su descripción sigue.
El algoritmo de reemplazo de página que no se usa con frecuencia genera menos fallas de página que el algoritmo de reemplazo de página usado menos recientemente cuando la tabla de página contiene valores de puntero nulos.
Envejecimiento
El algoritmo de envejecimiento es un descendiente del algoritmo NFU, con modificaciones para que sea consciente del lapso de tiempo de uso. En lugar de simplemente incrementar los contadores de páginas referenciadas, poniendo el mismo énfasis en las referencias de página independientemente del tiempo, el contador de referencia en una página se desplaza primero 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 tiene bits de referencia 1,0,0,1,1,0 en los últimos 6 tics de reloj, su contador de referencia se verá así: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Referencias de página más cerca hasta la actualidad tienen más impacto que las referencias a páginas de hace mucho tiempo. Esto asegura 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 de Python simula el algoritmo de envejecimiento. Contadores se inicializan con 0 y actualizado como se describe arriba a través de, utilizando operadores de desplazamiento aritméticos .
de la secuencia de importación de collections.abcdef simulate_aging ( Rs : Sequence , k : int ) -> None : "" "Simular envejecimiento." "" print ( 't | R-bits (0- {length} ) | Contadores para páginas 0- {length} ' . 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 enumerate ( 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 sobre 5 tics de reloj, la función imprime la siguiente salida, que enumera los bits R para cada tick de reloj t y los valores de contador individualespara cada página en representación binaria . [19]
>>> 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 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 del LRU en el sentido de que el envejecimiento solo puede realizar un seguimiento de las referencias en los últimos 16/32 (dependiendo del tamaño de bits de los enteros del procesador) intervalos de tiempo. En consecuencia, dos páginas pueden tener contadores de referencia de 00000000, aunque una página fue 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 en cuanto a qué página cambiar. Por lo tanto, el envejecimiento puede ofrecer un rendimiento casi óptimo a un precio moderado.
Algoritmo de reemplazo de página de mayor distancia primero (LDF)
La idea básica detrás de este algoritmo es 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 la 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 anti-reloj. [20]
Detalles de implementacion
Técnicas para hardware sin bit de referencia
Muchas de las técnicas discutidas anteriormente asumen la presencia de un bit de referencia asociado con cada página. Algunos hardware no tienen tal bit, por lo que su uso eficiente requiere técnicas que funcionen bien sin uno.
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 una página. Su enfoque se conoce como almacenamiento en caché de página secundaria. Las páginas eliminadas de los conjuntos de trabajo (memoria privada de proceso, en general) se colocan en listas de propósito especial mientras permanecen en la memoria física durante algún tiempo. La eliminación de 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 sigue siendo válido (cuyo contenido no está sucio o no necesita conservarse) se coloca al final de la Lista de páginas gratuitas. Una página que requiere escritura en la tienda de respaldo se colocará en la Lista de páginas modificadas. Por lo general, estas acciones se activan cuando el tamaño de la lista de páginas gratuitas cae por debajo de un umbral ajustable.
Las páginas pueden seleccionarse para la eliminación del conjunto de trabajo de una manera 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 hace 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 se pueden colocar en la Lista de páginas gratuitas. La secuencia de páginas que se abre camino hacia el encabezado de la Lista de páginas gratuitas se asemeja a los resultados de un mecanismo LRU o NRU y el efecto general tiene similitudes con el algoritmo Second-Chance descrito anteriormente.
Otro ejemplo lo utiliza el kernel de Linux en ARM . La falta de funcionalidad de hardware se compensa proporcionando dos tablas de página: las tablas de página nativas del procesador, sin bits referenciados ni bits sucios , y tablas de página mantenidas por software con los bits requeridos presentes. Los bits emulados en la tabla mantenida por software se establecen mediante fallas de página. Para obtener las fallas de la página, borrar los bits emulados en la segunda tabla revoca algunos de los derechos de acceso a la página correspondiente, que se implementa mediante la alteración de la tabla nativa.
Caché de página en Linux
Linux usa una caché de página unificada para
- brky regiones mmaped anónimas. Esto incluye el montón y la pila de programas de espacio de usuario . Está escrito para intercambiar cuando se pagina.
mmap
Regiones ed 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é de archivos o el búfer.- Memoria compartida adquirida a través de shm_open.
- El sistema de archivos en memoria tmpfs ; escrito para intercambiar cuando se pagina.
- El caché de archivos que incluye; escrito en el almacenamiento de bloques subyacente (posiblemente pasando por el búfer, ver más abajo) cuando se paginó.
- El caché de dispositivos de bloque , llamado "búfer" por Linux (que no debe confundirse con otras estructuras también llamadas búferes como las que se usan para tuberías y búferes que se usan internamente en Linux); escrito en el almacenamiento subyacente cuando se paginó.
La caché de página 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 de 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, se coloca en el encabezado del conjunto inactivo. Cuando se accede a él 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 que se agote la memoria física. [21] [22] Cuando se quita una página del conjunto inactivo, se pagina sin 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 (luego)".
Conjunto de trabajo
El conjunto de trabajo de un proceso es el conjunto de páginas que se espera que utilice ese proceso durante algún intervalo de tiempo.
El "modelo de conjunto de trabajo" no es un algoritmo de reemplazo de página en sentido estricto (en realidad es una especie de programador a mediano plazo ) [ aclaración necesaria ]
Referencias
- ^ Bell, John. "Notas del curso de sistemas operativos: memoria virtual" . Universidad de Illinois en la Facultad de Ingeniería de Chicago . Archivado desde el original el 23 de septiembre de 2018 . Consultado el 21 de julio de 2017 .
- ^ a b Jones, Douglas W. "22C: 116 Lecture Notes" . Departamento de Ciencias de la Computación de la Universidad de Iowa . Archivado desde el original el 30 de junio de 2012 . Consultado el 18 de marzo de 2008 .
- ^ Torrez, Paul; et al. "CS111 Lecture 11 notes" . Departamento de Ciencias de la Computación de UCLA . Archivado desde el original el 9 de enero de 2009.
- ^ Bahn, Hyokyung; Noh, Sam H. (12 a 14 de febrero de 2003). Caracterización del comportamiento de referencia web revisada: evidencia para la administración de caché dicotomizada . Conferencia Internacional sobre Redes de Información 2003 . Jeju, Corea del Sur: Springer-Verlag. págs. 1018–1027. doi : 10.1007 / 978-3-540-45235-5_100 . ISBN 978-3-540-40827-7.
- ^ Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (14 de diciembre de 2004). Conceptos del sistema operativo (7ª ed.). Hoboken, Nueva Jersey, EE.UU .: John Wiley & Sons. pag. 339. ISBN 0-47169-466-5. OCLC 56913661 .
- ^ Ayuda de VMS - Parámetros del sistema, TBSKIPWSL
- ^ Tanenbaum, Andrew S. (2001). Sistemas operativos modernos (2ª ed.). Upper Saddle River, Nueva Jersey, EE.UU .: Prentice-Hall. pag. 218 (4,4,5) . ISBN 978-0-13-031358-4. LCCN 00051666 . OCLC 45284637 . OL 24214243M .
- ^ Corbató, Fernando J. (1969). "Un experimento de localización con el sistema Multics" (PDF) . Festschrift: En honor a PM Morse . Prensa del MIT . págs. 217–228.
- ^ Smith, Alan Jay (septiembre de 1978). "Secuencialidad y captación previa en sistemas de bases de datos". Transacciones ACM en sistemas de bases de datos . Nueva York, NY, EE.UU .: ACM. 3 (3): 223–247. doi : 10.1145 / 320263.320276 . S2CID 11611563 .
- ^ Jiang, Song; Chen, Feng; Zhang, Xiaodong (10 a 15 de abril de 2005). CLOCK-Pro: una mejora eficaz del reemplazo de CLOCK (PDF) . 2005 Conferencia Técnica Anual de USENIX . Anaheim, CA, EE.UU .: Asociación USENIX. pag. 35. Archivado (PDF) desde el original el 12 de junio de 2019 . Consultado el 24 de marzo de 2009 .
- ^ Carr, Richard W .; Hennessy, John L. (14 a 16 de diciembre de 1981). WSCLOCK: un algoritmo simple y eficaz para la gestión de la memoria virtual (PDF comprimido con gzip) . Octavo simposio 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-1. Archivado desde el original el 10 de junio de 2007.
- ^ Gottlieb, Allan. "WSClock" . Departamento de Informática de la Universidad de Nueva York . Archivado desde el original el 30 de julio de 2012 . Consultado el 12 de junio de 2019 .
- ^ Tanenbaum, Andrew S. "Algoritmos de reemplazo de página" . InformIT . Archivado desde el original el 10 de septiembre de 2012 . Consultado el 12 de junio de 2019 .
- ^ Bansal, Sorav & Modha, Dharmendra S. (31 de marzo a 2 de abril de 2004). COCHE: Reloj con reemplazo adaptable (PDF) . 3er Congreso USENIX sobre Tecnologías de Archivo y Almacenamiento (FAST '04) . San Francisco, CA, EE.UU .: Asociación USENIX. págs. 187-200. CiteSeerX 10.1.1.105.6057 . Archivado (PDF) desde el original el 31 de julio de 2004.
- ^ O'Neil, Elizabeth J .; et al. (25 a 28 de mayo de 1993). El algoritmo de reemplazo de páginas LRU-K para almacenamiento en búfer de disco de base de datos (PDF) . 1993 Conferencia internacional ACM SIGMOD sobre Gestión de datos . Washington, DC, Estados Unidos: ACM. págs. 297-306. CiteSeerX 10.1.1.18.1434 . doi : 10.1145 / 170035.170081 . ISBN 0-89791-592-5. Archivado (PDF) desde el original el 6 de septiembre de 2019.
- ^ Megiddo, Nimrod & Modha, Dharmendra S. (31 de marzo - 2 de abril de 2003). ARC: una caché de reemplazo de autoajuste y baja sobrecarga (PDF) . 2ª Conferencia USENIX sobre Tecnologías de Archivo y Almacenamiento (FAST '03) . San Francisco, CA, EE.UU .: Asociación USENIX. págs. 115-130. Archivado (PDF) desde el original el 8 de febrero de 2010.
- ^ Megiddo, Nimrod y Modha, Dharmendra S. (2004). "Superar a LRU con un algoritmo de caché de reemplazo adaptable" (PDF) . Computadora . Sociedad de Informática IEEE. 37 (4): 58. CiteSeerX 10.1.1.231.498 . doi : 10.1109 / MC.2004.1297303 . S2CID 5507282 . Archivado (PDF) desde el original el 21 de octubre de 2012 . Consultado el 20 de septiembre de 2013 .
- ^ Rhodehamel, Michael W. (2 a 4 de octubre de 1989). La interfaz de bus y las unidades de megafonía del microprocesador i860 . 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors . Cambridge, MA, EE.UU .: IEEE. págs. 380–384. doi : 10.1109 / ICCD.1989.63392 . ISBN 0-8186-1971-6. Número de acceso INSPEC 3719504.
- ^ Tanenbaum, Andrew S .; Bos, Herbert (2015). Sistemas operativos modernos (4ª ed.). Boston, MA, EE.UU .: Pearson. pag. 215. ISBN 978-0-13-359162-0. OL 25620855M .
- ^ Kumar, Gyanendra; Tomar, Parul (septiembre de 2017). "Un nuevo algoritmo de reemplazo de primera página de mayor distancia" . Revista India de Ciencia y Tecnología . 10 (30): 1–6. doi : 10.17485 / ijst / 2017 / v10i30 / 115500 . ISSN 0974-6846 . Archivado desde el original el 7 de septiembre de 2017.
- ^ Consulte la explicación al principio de/mm/workingset.cen la fuente de Linux
- ^ Corbet, Jonathan Corbet (2 de mayo de 2012). "Mejor equilibrio de lista activo / inactivo" . LWN.net .
Otras lecturas
- Wong, Kin-Yeung (23 de enero de 2006). "Políticas de reemplazo de caché web: un enfoque pragmático". Red IEEE . IEEE. 20 (1): 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 de página óptimo". Revista de la ACM . Nueva York, NY, EE.UU .: ACM. 18 (1): 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, Nueva Jersey, 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, Nueva Jersey, EE.UU .: Prentice-Hall. ISBN 978-0-13-031358-4. LCCN 00051666 . OCLC 45284637 . OL 24214243M .Extracto en línea de los algoritmos de reemplazo de páginas: Algoritmos de reemplazo de páginas .
- Johnson, Theodore; Shasha, Dennis (12 a 15 de septiembre de 1994). 2Q: Algoritmo de reemplazo de gestión de búfer de alto rendimiento y baja sobrecarga (PDF) . XX Congreso Internacional sobre Bases de Datos Muy Grandes . Santiago de Chile, Chile: Morgan Kaufmann. págs. 439–450. ISBN 1-55860-153-8. Archivado (PDF) desde el original el 17 de marzo de 2020 . Consultado el 31 de julio de 2005 .
- Vidrio, Gedeón; Cao, Pei (15 a 18 de junio de 1997). Reemplazo de página adaptable basado en el comportamiento de referencia de memoria . 1997 Conferencia internacional ACM SIGMETRICS sobre Medición y modelado de sistemas informáticos . Seattle, WA, Estados Unidos: ACM. págs. 115-126. doi : 10.1145 / 258612.258681 . ISBN 0-89791-909-2. También disponible en forma extendida como "Informe técnico 1338" . Departamento de Ciencias de la Computación, Universidad de Winconsin-Madison .
- Kim, Jong Min; et al. (17 a 21 de octubre de 2000). Un esquema de administración de búfer unificado de alto rendimiento y bajo costo que aprovecha las referencias secuenciales y en bucle (PDF) . IV Simposio Usenix sobre Diseño e Implementación de Sistemas Operativos (OSDI'2000) . 4 . San Diego, CA, EE.UU .: Asociación USENIX. Archivado (PDF) desde el original el 18 de septiembre de 2004.
- Smaragdakis, Yannis; Kaplan, Scott; Wilson, Paul (1º a 4 de mayo de 1999). EELRU: reemplazo de página adaptable simple y efectivo (PDF) . 1999 Conferencia internacional ACM SIGMETRICS sobre Medición y modelado de sistemas informáticos . Atlanta, GA, Estados Unidos: ACM. págs. 122-133. doi : 10.1145 / 301453.301486 . ISBN 1-58113-083-X. Archivado (PDF) desde el original el 4 de marzo de 2016.
- Jiang, Song; Zhang, Xiaodong (15 a 19 de junio de 2002). LIRS: un reemplazo de conjunto de antigüedad de interreferencia baja (PDF) . 2002 Conferencia internacional ACM SIGMETRICS 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-9. Archivado (PDF) desde el original el 12 de junio de 2019.
- Lee, Donghee; et al. (1º a 4 de septiembre de 1997). Implementación y Evaluación de Desempeño de la Política de Reemplazo de LRFU . 23ª Conferencia Euromicro Nuevas Fronteras de las Tecnologías de la Información . Budapest, Hungría: IEEE Computer Society. págs. 106-111. doi : 10.1109 / EMSCNT.1997.658446 . ISBN 0-8186-8215-9. Número de acceso INSPEC 5856800.
- Zhou, Yuanyuan; Philbin, James; Li, Kai (25 a 30 de junio de 2001). El algoritmo de reemplazo de múltiples colas para cachés de búfer de segundo nivel (PDF) . 2001 Conferencia técnica anual de USENIX . Boston, MA, EE.UU .: Asociación USENIX. págs. 91-104. ISBN 1-880446-09-X. Archivado (PDF) desde el original el 24 de noviembre de 2005.