Algoritmos de Reemplazo de Páginas en Sistemas Operativos
Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 3,77 KB
Algoritmo Óptimo (OPT)
Este algoritmo tiene como finalidad retirar la página que vaya a ser referenciada más tarde. Por ejemplo, si hay una página A que será usada dentro de 10000 instrucciones, y una página B que será usada dentro de 2800 instrucciones, se debería eliminar de la memoria la página A. Como se puede deducir, para esto el sistema operativo debería ver en cuánto tiempo será usada cada página en memoria y elegir la que está más distante. El problema de este método es que necesita conocimiento del futuro, por lo que es imposible su implementación. Es un algoritmo teórico y se utiliza a efectos comparativos con los algoritmos factibles de implementar.
Algoritmo Primero en Entrar, Primero en Salir (FIFO)
En este método, el sistema operativo solo tiene que guardar el orden en que las páginas fueron cargadas, de modo que al necesitar liberar espacio, pueda elegir fácilmente la primera página cargada. Se usa una cola: al cargar una página nueva, se ingresa al final. Aunque las colas FIFO son simples e intuitivas, no se comportan de manera aceptable en la práctica, por lo que es raro su uso en su forma más simple. Uno de los problemas que presentan es la llamada Anomalía de Belady (o Anomalía FIFO). Belady encontró ejemplos en los que un sistema con un número de páginas igual a tres tenía menos fallos de página que un sistema con cuatro páginas. El mayor problema consiste en que podemos quitar de la memoria una página muy usada, solo porque es la más antigua.
Algoritmo No Usada Recientemente (NRU)
Este algoritmo favorece a las páginas que fueron usadas recientemente. Funciona de la siguiente manera: cuando una página es referenciada, establece el bit de referencia para esa página. Similarmente, cuando una página es modificada, establece su bit de modificación. Usualmente, estas operaciones son realizadas por el hardware, aunque puede hacerse también por software. En un tiempo fijo, el sistema operativo pone a cero los bits de referencia de todas las páginas, de modo que las páginas con su bit de referencia en 1 son las que fueron referenciadas dentro del último intervalo de reloj.
Cuando una página debe ser reemplazada, el sistema operativo divide las páginas en cuatro categorías:
- Categoría 0: no referenciada, no modificada
- Categoría 1: no referenciada, modificada
- Categoría 2: referenciada, no modificada
- Categoría 3: referenciada, modificada
Las mejores páginas para reemplazar son las que se encuentran en la categoría 0, mientras que las peores son las de la categoría 3. Dentro de las páginas en categoría 0, se elige una página al azar para ser intercambiada.
Algoritmo del Reloj (Clock Algorithm)
Aunque el algoritmo anterior es razonable, un mejor enfoque es mantener las páginas en una lista circular con la forma de un reloj. Una manecilla apunta hacia la página más antigua. Al ocurrir un fallo de página, se inspecciona la página a la que apunta la manecilla: si su bit R es 0, se retira de la memoria, se inserta la nueva página en su lugar en el reloj y la manecilla avanza una posición. Si R es 1, la manecilla avanza una posición y el bit se limpia. Esto continúa hasta encontrar una página con R=0.
Algoritmo de Segunda Oportunidad
Una modificación simple del FIFO que evita deshacerse de una página de uso frecuente. Inspecciona el bit R de la página más antigua y busca una página antigua sin referencias durante el intervalo de tiempo anterior.