Sistemas operativos modernos

marco de página, el tamaño de la memoria y volvemos a ejecutar el proceso, en todos los pun­ tos durante la ejecución todas las páginas que estaban presentes en la primera ocasión también lo estarán en la segunda, junto con una página adicional. Si examinamos la figura 4-25 y pensamos un poco en cómo funciona, deberá quedar cla­ ro que LRU tiene esta propiedad. Algunos otros algoritmos (por ejemplo, el reemplazo óptimo de páginas) también la tienen, pero FIFO no. Llamamos algoritmos de pila a los que tienen esta propiedad. Éstos no presentan la anomalía de Belady y por ello los adoran los teóricos de la memoria virtual. 4.5.3 La cadena de distancias En el caso de los algoritmos de pila, resulta conveniente representar la cadena de referencias de una forma más abstracta que con los números de página reales. En adelante, denotaremos una referencia a una página con la distancia desde la parte superior de la pila donde se colocó la página. Por ejemplo, la referencia a la página 1 en la última columna de la figura 4-25 es una referencia a una página que está a una distancia 3 de la parte superior de la pila (porque la pá­ gina 1 estaba en tercer lugar antes de la referencia). Decimos que las páginas que todavía no se han solicitado y, por lo tanto, todavía no están en la pila (es decir, no están en M) están a una distancia ®o. Cabe señalar que la cadena de distancias no sólo depende de la cadena de referencias, si­ no también del algoritmo de paginación. Con la misma cadena de referencias original, un al­ goritmo distinto tomaría decisiones diferentes respecto a cuáles páginas desalojar. Por ello, se produce una sucesión de pilas distinta. Las propiedades estadísticas de la cadena de distancias tienen un impacto importante en el desempeño del algoritmo. En la figura 4-26a vemos la función de densidad de probabilidad pa­ ra los elementos de una cadena de distancias (ficticia) d. Casi todos los elementos de la cade­ na están entre 1 y /t. Con una memoria de k marcos de página, habrá pocos fallos de página. P(d) (a) d (b) Figura 4-26. Funciones de densidad de probabilidad para dos cadenas de distancias hipotéticas. En contraste, en la figura 4-26b las referencias están tan dispersas que la única manera de evitar un gran número de fallos de página es dar al programa tantos marcos de página como páginas virtuales tenga. Tener un programa así es simplemente mala suerte.