operating system - usadas - No puedo entender la anomalía de Belady
explique cómo funciona el método de sustitución de páginas llamado de segunda oportunidad (5)
Por lo tanto, la anomalía de Belady indica que al usar una política de reemplazo de página FIFO, al agregar más espacio de página tendremos más fallos de página.
Mi intuición dice que deberíamos tener menos o, a lo sumo, el mismo número de errores de página a medida que agregamos más espacio de página.
Si pensamos en una cola FIFO como una canalización, agregar más espacio de página es como hacer que la tubería sea más grande:
____
O____O size 4
________
O________O size 8
Entonces, ¿por qué obtienes más fallos de página? Mi intuición dice que con un conducto más largo, tomaría un poco más de tiempo para comenzar a tener fallos de página (por lo tanto, con un conducto infinito no tendría fallos de página) y luego tendría tantos fallos de página como A menudo como con un tubo más pequeño.
¿Qué está mal con mi razonamiento?
En resumen, sobre la Anomalía de Belady podemos decir "Agregar más marcos puede provocar más fallos de página".
Esta declaración es incorrecta porque está sobregeneralizada :
La anomalía de Belady indica que al usar una política de reemplazo de página FIFO, al agregar más espacio de página tendremos más fallos de página
Esta es una versión corregida:
"La anomalía de Belady indica que al usar una política de reemplazo de página FIFO, al agregar más espacio de página, algunos patrones de acceso a la memoria en realidad resultarán en más fallas de página".
En otras palabras ... si la anomalía se observa depende del patrón de acceso a la memoria real.
La anomalía de Belady ocurre en un esquema FIFO solo cuando la página que se está refiriendo actualmente es la última que se eliminó de la memoria principal. solo en este caso, aunque aumente el espacio de la página, tendrá más errores de página.
La anomalía de Belady se produce en el algoritmo de reemplazo de página, no sigue el algoritmo de pila. Es decir, las páginas en las que los fotogramas eran menos, deberían ser un subconjunto de las páginas cuando hay más fotogramas. puede ocurrir en FIFO a veces, incluso el reemplazo de página al azar pero no LRU u óptimo.
La razón por la que al usar FIFO, aumentar el número de páginas puede aumentar la tasa de fallas en algunos patrones de acceso, es porque cuando tiene más páginas, las páginas solicitadas recientemente pueden permanecer en la parte inferior de la cola FIFO por más tiempo.
Considere la tercera vez que se solicita "3" en el ejemplo de wikipedia aquí: http://en.wikipedia.org/wiki/Belady%27s_anomaly
Las faltas de página están marcadas con una "f".
1:
Page Requests 3 2 1 0 3 2 4 3 2 1 0 4
Newest Page 3f 2f 1f 0f 3f 2f 4f 4 4 1f 0f 0
3 2 1 0 3 2 2 2 4 1 1
Oldest Page 3 2 1 0 3 3 3 2 4 4
2:
Page Requests 3 2 1 0 3 2 4 3 2 1 0 4
Newest Page 3f 2f 1f 0f 0 0 4f 3f 2f 1f 0f 4f
3 2 1 1 1 0 4 3 2 1 0
3 2 2 2 1 0 4 3 2 1
Oldest Page 3 3 3 2 1 0 4 3 2
En el primer ejemplo (con menos páginas), hay 9 fallas de página.
En el segundo ejemplo (con más páginas), hay 10 fallas de página.
Cuando se utiliza FIFO, al aumentar el tamaño de la memoria caché cambia el orden en que se eliminan los elementos. Lo que en algunos casos, puede aumentar la tasa de falla.
La anomalía de Belady no indica nada sobre la tendencia general de las tasas de fallas con respecto al tamaño de la memoria caché. Entonces, su razonamiento (acerca de ver el caché como una tubería), en el caso general no es incorrecto.
En resumen: la Anomalía de Belady señala que es posible explotar el hecho de que los tamaños de caché más grandes pueden hacer que los elementos de la caché se suban en la cola FIFO más tarde que los tamaños de caché más pequeños, con el fin de que los tamaños de caché más grandes tengan una falla mayor Tasa bajo un patrón de acceso particular (y posiblemente raro).