Algoritmos de reemplazo de páginas

Arquitectura y Sistemas Operativos

Algoritmos de reemplazo de páginas

Cuando ocurre un fallo de página, el sistema operativo tiene que elegir una página para desalojarla (eliminarla de memoria) y hacer espacio para la página entrante.

empezar_

Algoritmos de reemplazo de páginas

Óptimo

Reloj

Primera en entrar, primera en salir (FIFO)

No usadas recientemente(NRU)

Menos Usada Recientemente(LRU)

Finalizar

Algoritmos de reemplazo de páginas

óptimo

- Cuando ocurre un fallo de página, hay cierto conjunto de páginas en memoria y una de éstas se referenciará en la siguiente instrucción; otras páginas tal vez no se referencien sino hasta 10, 100 o tal vez 1000 instrucciones después. Cada página se puede etiquetar con el número de instrucciones que se ejecutarán antes de que se haga referencia por primera vez a esa página. - El algoritmo óptimo de reemplazo de páginas establece que la página con la etiqueta más alta debe eliminarse. - Si una página no se va a utilizar durante 8 millones de instrucciones y otra no se va a utilizar durante 6 millones de instrucciones, al eliminar la primera se enviará el fallo de página que la obtendrá de vuelta lo más lejos posible en el futuro.

info

Algoritmos de reemplazo de páginas

Nru

Cuando se inicia un proceso, ambos bits de página(RyM) se establecen en 0. El bit R se borra en forma periódica para diferenciar las páginas a las que no se ha hecho referencia recientemente de las que si. Cuando ocurre un fallo de página, el sistema operativo inspecciona todas las páginas y las divide en 4 categorías segun los valores actuales de sus bits R y M: clase 0: no ha sido referenciada, no ha sido modificada, clase 1: no ha sido referenciada, ha sido modificada, clase 2: ha sido referenciada, no ha sido modificada, clase 3: ha sido referenciada, ha sido modificada. El algoritmo NRU elimina una página al azar de la clase de menor numeración que no esté vacía.

info

Algoritmos de reemplazo de páginas

fifo

El sistema operativo mantiene una lista de todas las páginas actualmente en memoria, en donde la llegada más reciente está en la parte final y la menos reciente en la parte frontal. En un fallo de página, se elimina la página que está en la parte frontal y la nueva página se agrega a la parte final de la lista.

info

Algoritmos de reemplazo de páginas

Reloj

Este algoritmo mantiene todos los marcos de página en una lista circular en forma de reloj. La manecilla apunta a la página más antigua. Cuando ocurre un fallo de página, la página a la que apunta la manecilla se inspecciona. Si el bit R es 0, la página se desaloja, se inserta la nueva página en el reloj en su lugar y la manecilla se avanza una posición. Si R es 1, se borra y la manecilla se avanza a la siguiente página. Este proceso se repite hasta encontrar una página con R = 0.

info

Algoritmos de reemplazo de páginas

lru

Las páginas que no se hayan utilizado por mucho tiempo probablemente seguirán sin utilizarse por mucho tiempo más. Esta idea sugiere un algoritmo factible cuando ocurra un fallo de página, hay que descartar la página que no se haya utilizado durante la mayor longitud de tiempo.

info

Gracias

Grupo: Candela Puerta - Alvaro Rubina - Diego Cárdenas - Diego Canales - Benjamin Buchaillot - Florencia Gimenez