Sistemas operativos modernos

Si se desaloja una página muy utilizada, lo más seguro es que pronto tenga que volverse a traer a la memoria, con el consiguiente gasto extra. Se ha trabajado mucho sobre el tema de los al­ goritmos de reemplazo de páginas, tanto desde el punto de vista teórico como experimental. A continuación describiremos algunos de los algoritmos más importantes. Vale la pena señalar que el problema de “reemplazo de páginas” también se da en otras áreas del diseño de computadoras. Por ejemplo, casi todas las computadoras tienen uno o más cachés en memoria que contienen bloques de memoria de 32 o 64 bytes recién usados. Cuando se llena el caché, hay que escoger el bloque desalojar. Este problema es idéntico al de reemplazo de pá­ ginas, sólo que se efectúa en una escala de tiempo más corta (se tiene que efectuar en unos cuan­ tos nanosegundos, no en milisegundos como el reemplazo de páginas). La escala de tiempo es corta porque los fallos de bloque en caché se satisfacen colocando un bloque de la memoria prin­ cipal, que no tiene tiempo de desplazamiento de la cabeza lectora ni latencia rotacional. Un segundo ejemplo es un servidor Web. Este puede mantener en su caché de memoria cierto número de páginas Web muy utilizadas. Sin embargo, si el caché se llena y se hace re­ ferencia a una página nueva, habrá que decidir cuál página Web desalojar. Las consideraciones son similares al caso de páginas de memoria virtual, salvo por el hecho de que las páginas Web nunca se modifican en el caché, así que la copia en disco siempre está actualizada. En un sis­ tema de memoria virtual, las páginas que están en la memoria principal podrían estar modifi­ cadas o sin modificación. 4.4.1 El algoritmo óptimo de reemplazo de páginas El mejor algoritmo de reemplazo de páginas posible es fácil de describir pero imposible de im­ plementar. En el momento en que se presenta un fallo de página, cierto conjunto de páginas es­ tá en la memoria. En la siguiente instrucción se hará referencia a una de esas páginas (la página que contiene a la instrucción). Puede ser que no se haga referencia a otras de las páginas sino hasta 10, 100 o quizá 1000 instrucciones después. Cada página puede rotularse con el número de instrucciones que se ejecutarán antes de que se haga la primera referencia a esa página. El algoritmo de página óptima simplemente dice que debe desalojarse la página con el ró­ tulo más grande. Si faltan ocho millones de instrucciones para que se use cierta página y fal­ tan seis millones de instrucciones para que se use otra, el desalojo de la primera aplaza lo más posible el fallo de página que volverá a traer una página a la memoria. Las computadoras, igual que las personas, tratan de aplazar lo más posible los sucesos desagradables. El único problema con este algoritmo es que no puede ponerse en práctica. En el momen­ to en que se presenta el fallo de página, el sistema operativo no tiene forma de saber cuándo se volverá a hacer referencia a cualquiera de las páginas. (Vimos una situación similar con el al­ goritmo de calendarización del trabajo más corto primero: ¿cómo sabe el sistema cuál trabajo es el más corto?) No obstante, si se ejecuta un programa en un simulador y se lleva la cuenta de todas las referencias a páginas, será posible implementar el reemplazo de páginas óptimo en la segunda ejecución, utilizando la información de referencias a páginas recabada durante la primera ejecución. De este modo, es posible comparar el desempeño de algoritmos factibles con el mejor po­ sible. Si un sistema operativo logra un desempeño, digamos, sólo 1% menos bueno que el del