La anomalía de Bélády

En el almacenamiento informático, la anomalía de Bélády es el fenómeno en el que el aumento del número de marcos de página da como resultado un aumento del número de errores de página para ciertos patrones de acceso a la memoria. Este fenómeno se experimenta comúnmente cuando se utiliza el algoritmo de reemplazo de páginas primero en entrar, primero en salir (FIFO). En FIFO, el error de página puede aumentar o no a medida que aumentan los marcos de página, pero en algoritmos óptimos y basados en pila como LRU, a medida que aumentan los marcos de página, el error de página disminuye. László Bélády lo demostró en 1969.

Fondo

En la gestión común de la memoria de las computadoras, la información se carga en fragmentos de tamaño específico. Cada fragmento se denomina página. La memoria principal sólo puede contener un número limitado de páginas a la vez. Requiere un marco para cada página que puede cargar. Un error de página ocurre cuando no se encuentra una página y es posible que sea necesario cargarla desde el disco a la memoria.

Cuando se produce un error de página y todos los marcos están en uso, se debe borrar uno para dejar espacio para la nueva página. Un algoritmo simple es FIFO: la página que haya estado más tiempo en los marcos es la que se borra. Hasta que se demostró la anomalía de Bélády, se creía que un aumento en el número de marcos de página siempre daría como resultado el mismo número de errores de página o menos.

La anomalía de Bélády no tiene límites

Bélády, Nelson y Shedler construyeron cadenas de referencia para las cuales el algoritmo de reemplazo de páginas FIFO produjo casi el doble de errores de página en una memoria más grande que en una más pequeña y formularon la conjetura de que 2 es un límite general.

En 2010, Fornai e Iványi demostraron que la anomalía es, de hecho, ilimitada y que se puede construir una cadena de referencia para cualquier proporción arbitraria de errores de página.