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 en el número de fallos 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ágina FIFO (primero en entrar, primero en salir ) . En FIFO, el fallo de página puede o no aumentar 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 fallo de página disminuye. László Bélády demostró esto en 1969. [1]
En la gestión de memoria informática habitual , la información se carga en fragmentos de tamaño específico. Cada fragmento se denomina página . La memoria principal solo puede contener una cantidad limitada de páginas a la vez. Requiere un marco por cada página que puede cargar. Se produce un error de página 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 el FIFO: se borra la página que haya estado en los marcos durante más tiempo. 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 o menos de errores de página.
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. [ cita requerida ]
En 2010, Fornai e Iványi demostraron que la anomalía en realidad no tiene límites y que se puede construir una cadena de referencia para cualquier proporción arbitraria de errores de página. [ cita requerida ]