Sistemas operativos modernos

4.5.1 Anomalía de Belady De manera intuitiva, podríamos pensar que entre más marcos de página tenga la memoria, me­ nos fallos de página experimentará un programa. Aunque parezca sorprendente, no siempre su­ cede así. Belady et al. (1969) descubrieron un contraejemplo en el que FIFO causaba más fallos de página con cuatro marcos de página que con tres. Esta extraña situación se conoce co­ mo anomalía de Belady, y se ilustra en la figura 4-24 para un programa con cinco páginas vir­ tuales, numeradas del Oal 4. Las páginas se solicitan en el orden 0 1 2 3 0 1 4 0 1 2 3 4 En la figura 4-24a se muestra que con tres marcos de página, se generan nueve fallos de pági­ na en total. En la figura 4-24b se generan 10 fallos de página con cuatro marcos de página. Página más reciente Página más antigua / Todos los marcos están inicialmeníe vacíos 0 1 2 3 0 1 4 0 1 2 3 4 0 1 2 3 0 1 4 4 4 2 3 3 0 1 2 3 0 1 1 1 4 2 2 0 2 3 0 0 0 1 4 4 P P P P P P P P P 9 Fallos de página 0 1 2 3 0 1 4 0 1 2 3 4 Página más reciente 0 1 2 3 3 3 4 0 1 2 3 4 0 1 2 2 2 3 4 0 1 2 3 Página más antigua 0 1 1 1 2 3 4 0 1 2 0 0 0 1 2 3 4 0 1 P P P P P P P P P P (b) Figura 4-24. Anomalía de Belady. a) FIFO con tres marcos de página, b) FIFO con cuatro marcos de página. Las P indican las referencias que causan fallos de página. 4.5.2 Algoritmos de pila Muchos investigadores en ciencias de la computación quedaron intrigados ante la anomalía de Belady y comenzaron a investigarla. Estos trabajos condujeron al desarrollo de toda una teoría sobre los algoritmos de reemplazo de páginas y sus propiedades. Aunque en su mayor parte ta­ les trabajos rebasan el alcance del presente libro, a continuación presentaremos una breve in­ troducción. Si desea más detalle consulte Maekawa et al. (1987). Todos estos trabajos parten de la observación de que un proceso genera una serie de refe­ rencias a la memoria conforme se ejecuta. Cada referencia a la memoria corresponde a una pá-