Anomalía de Belady en los algoritmos de reemplazo de página – Part 1

Requisito previo: algoritmos de reemplazo de página 
En el sistema operativo, los datos de proceso se cargan en fragmentos de tamaño fijo y cada fragmento se denomina página. El procesador carga estas páginas en fragmentos de memoria de tamaño fijo llamados marcos. Normalmente, el tamaño de cada página siempre es igual al tamaño del marco. 

Una falla de página ocurre cuando una página no se encuentra en la memoria y necesita cargarse desde el disco. Si se produce un error de página y ya se han asignado todos los marcos de memoria, se requiere el reemplazo de una página en la memoria cuando se solicita una nueva página. Esto se conoce como demanda-paginación. La elección de qué página reemplazar se especifica mediante algoritmos de reemplazo de página. Los algoritmos de reemplazo de página comúnmente utilizados son FIFO, LRU, algoritmos de reemplazo de página óptimos, etc. 

Generalmente, al aumentar el número de cuadros en la memoria virtual de un proceso, su ejecución se vuelve más rápida al ocurrir menos fallas de página. A veces ocurre lo contrario, es decir, se producen más fallos de página cuando se asignan más marcos a un proceso. Este resultado tan inesperado se denomina Anomalía de Belady . 

La anomalía de Bélády es el nombre que se le da al fenómeno en el que el aumento del número de marcos de página da como resultado un aumento del número de fallas de página para un patrón de acceso a la memoria dado. 

Este fenómeno se experimenta comúnmente en los siguientes algoritmos de reemplazo de página: 

1. Primero en entrar, primero en salir (FIFO) 
2. Algoritmo de segunda oportunidad 
3. Algoritmo de reemplazo de página aleatoria 

Motivo de la anomalía de Belady: 
los otros dos algoritmos de reemplazo de página comúnmente utilizados son Óptimo y LRU, pero la anomalía de Belady nunca puede ocurrir en estos algoritmos para ninguna string de referencia, ya que pertenecen a una clase de algoritmos de reemplazo de página basados ​​en pilas. 

Un algoritmo basado en pila es aquel en el que se puede demostrar que el conjunto de páginas en memoria para N fotogramas es siempre un subconjunto del conjunto de páginas que estarían en memoria con N + 1 fotogramas. Para el reemplazo de LRU, el conjunto de páginas en la memoria serían las n páginas a las que se hizo referencia más recientemente. Si el número de fotogramas aumenta, estas n páginas seguirán siendo las referenciadas más recientemente y, por lo tanto, seguirán estando en la memoria. Mientras que en FIFO, si una página llamada b entró en la memoria física antes que una página, entonces la prioridad de reemplazo de b es mayor que la de a, pero esto no es independiente de la cantidad de marcos de página y, por lo tanto, FIFO no sigue una política de reemplazo de páginas de pila y, por lo tanto, sufre la Anomalía de Belady. 

Ejemplo: Considere el siguiente diagrama para comprender el comportamiento de un algoritmo de reemplazo de página basado en pila 

El diagrama ilustra que dado el conjunto de páginas, es decir, {0, 1, 2} en 3 marcos de memoria, no es un subconjunto de las páginas en memoria: {0, 1, 4, 5} con 4 marcos y es una violación en la propiedad de los algoritmos basados ​​en pilas. Esta situación se puede ver con frecuencia en el algoritmo FIFO. 

Anomalía de Belady en FIFO: 
suponiendo un sistema que no tiene páginas cargadas en la memoria y utiliza el algoritmo de reemplazo de página FIFO. Considere la siguiente string de referencia: 

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 

Caso 1: si el sistema tiene 3 marcos, la string de referencia dada que usa el algoritmo de reemplazo de página FIFO produce un total de 9 fallas de página. El siguiente diagrama ilustra el patrón de las fallas de página que ocurren en el ejemplo. 

Caso 2: si el sistema tiene 4 marcos, la string de referencia dada usando el algoritmo de reemplazo de página FIFO produce un total de 10 fallas de página. El siguiente diagrama ilustra el patrón de las fallas de página que ocurren en el ejemplo. 

Se puede ver en el ejemplo anterior que al aumentar la cantidad de marcos mientras se usa el algoritmo de reemplazo de página FIFO, la cantidad de fallas de página aumentó de 9 a 10. 

Nota: no es necesario que cada patrón de referencia de string cause una anomalía de Belady en FIFO, pero hay ciertos tipos de referencias de string que empeoran el rendimiento de FIFO al aumentar la cantidad de cuadros. 

Por qué los algoritmos basados ​​en pilas no sufren anomalías: 
todos los algoritmos basados ​​en pilas nunca sufren anomalías Belady porque este tipo de algoritmos asigna una prioridad a una página (para reemplazo) que es independiente de la cantidad de marcos de página. Ejemplos de tales políticas son Optimal, LRU y LFU. Además, estos algoritmos también tienen una buena propiedad para la simulación, es decir, la proporción de errores (o aciertos) se puede calcular para cualquier número de marcos de página con un solo paso a través de la string de referencia. 

En el algoritmo LRU, cada vez que se hace referencia a una página, se mueve a la parte superior de la pila, por lo que las n primeras páginas de la pila son las n páginas utilizadas más recientemente. Incluso si el número de fotogramas se incrementa a n+1 , la parte superior de la pila tendrá n+1 páginas usadas más recientemente. 

Se puede usar un ejemplo similar para calcular el número de fallas de página en el algoritmo LRU. Suponiendo un sistema que no tiene páginas cargadas en la memoria y utiliza el algoritmo de sustitución de páginas LRU. Considere la siguiente string de referencia: 

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5  

Caso 1: si el sistema tiene 3 marcos, la string de referencia dada usando el algoritmo de reemplazo de página LRU produce un total de 10 fallas de página. El siguiente diagrama ilustra el patrón de las fallas de página que ocurren en el ejemplo. 

Caso 2: si el sistema tiene 4 marcos, la string de referencia dada al usar el algoritmo de reemplazo de página LRU, entonces se producen un total de 8 fallas de página. El diagrama muestra el patrón de los errores de página en el ejemplo. 

Conclusión: 
varios factores afectan sustancialmente la cantidad de fallas de página, como la longitud de la string de referencia y la cantidad de marcos de página libres disponibles. También se producen anomalías debido al pequeño tamaño de la memoria caché, así como a la imprudente tasa de cambio del contenido de la memoria caché. Además, la situación de un número fijo de fallos de página incluso después de aumentar el número de marcos también puede verse como una anomalía. A menudo, los algoritmos como el algoritmo de reemplazo de página aleatorio también son susceptibles a la anomalía de Belady, porque puede comportarse como el algoritmo de reemplazo de página primero en entrar, primero en salir (FIFO) . Pero los algoritmos basados ​​en Stack generalmente son inmunes a todas esas situaciones, ya que garantizan mejores visitas a la página cuando se incrementan los marcos. 

Preguntas de GATE CS Corner: 
practicar las siguientes preguntas lo ayudará a evaluar su conocimiento. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques. 

1. PUERTA-CS-2001 | Pregunta 21
2. PUERTA-CS-2009 | Pregunta 8
3. CS ISRO 2011 | Pregunta 73
4. GATE-CS-2016 (Conjunto 2) | Pregunta 30
5. CS ISRO 2016 | Pregunta 48
6. PUERTA CS Simulacro 2018 | Pregunta 63