Sistemas operativos modernos

El algoritmo no usada recientemente (NRU; not recently used) desaloja al azar una pági­ na de la clase de número más bajo que no esté vacía. Este algoritmo se basa en la suposición implícita de que es mejor desalojar una página modificada a la que no se ha hecho referencia en por lo menos un tic del reloj (que típicamente es de 20 ms), en vez de una página limpia que se está usando mucho. El principal atractivo de NRU es que es fácil de entender, tiene una im­ plementación moderadamente eficiente y produce un desempeño que, si bien de ninguna ma­ nera es óptimo, podría ser aceptable. 4.4.3 El algoritmo de reemplazo de páginas de primero en entrar, primero en salir Otro algoritmo de paginación con bajo gasto adicional es el de primero en entrar, primero en salir first-in, first-out). Para ilustrar su funcionamiento, consideremos un supermercado que tiene suficientes anaqueles para exhibir exactamente k productos distintos. Un día, cierta com­ pañía introduce un nuevo tipo de comestible: yoghurt orgánico en polvo instantáneo que puede re­ constituirse en un homo de microondas. El producto es un éxito inmediato, así que nuestro supermercado finito tiene que deshacerse de un producto viejo para tener el nuevo en existencia. Una posibilidad es hallar el producto que el supermercado ha tenido en existencia más tiempo (por ejemplo, algo que comenzó a vender hace 120 años) y deshacerse de él alegando que ya no le interesa a nadie. En efecto, el supermercado mantiene una lista enlazada de todos los productos que vende, en el orden en que se introdujeron. El nuevo se coloca al final de la lista; el que está al principio, se abandona. Como algoritmo de reemplazo de páginas, puede aplicarse la misma idea. El sistema ope­ rativo mantiene una lista de todas las páginas que están actualmente en la memoria, con la más antigua al principio de la lista y la más nueva al final. Al presentarse un fallo de página, se de­ saloja la página que está al principio de la lista y la nueva se anexa al final. En el caso de una tienda, PIFO podría eliminar la cera para bigote, pero también podría eliminar harina, sal o mantequilla. En el caso de las computadoras surge el mismo problema; por ello, casi nunca se usa FIFO en su forma pura. 4.4.4 El algoritmo de reemplazo de páginas de segunda oportunidad Una modificación sencilla de FIFO que evita el problema de desalojar una página que se usa mucho consiste en examinar el bit R de la página más antigua. Si es O, quiere decir que la pá­ gina no sólo es antigua, sino que tampoco se usa mucho. Por lo tanto, es reemplazada de inme­ diato. Si el bit R es 1, se apaga, la página se coloca al final de la lista de páginas y su tiempo de carga se actualiza como si acabara de llegar a la memoria. Luego continúa la búsqueda. El funcionamiento de este algoritmo, llamado de segunda oportunidad, se muestra en la figura 4-16. En la figura 4-16a se muestra que las páginas A a / / se mantienen en una lista enlazada, ordenadas según la hora a la que llegaron a la memoria. Supongamos que hay un fallo de página en el tiempo 20. La página más antigua es A, que lle­ gó en el tiempo O, cuando se inició el proceso. Si el bit /? de A está apagado, se le desaloja de la memoria, escribiéndola en disco (si está modificada) o simplemente abandonándola (si está lim-