Algoritmos de
Remplazamiento de Paginas
Miguel Covarrubias
Algoritmos de Remplazamiento de
Paginas


Cuando un error de pagina ocurre, se
forza a una pagina a salir de memoria y se
actualizan sus contenidos.
Si se remplaza una una pagina poco
usada, se mejora el desempeño del
sistema.
El Algoritmo Optimo de
Remplazamiento de Paginas



Etiqueta a cada pagina con el numero de
instrucciones que se van a ejecutar antes
de que esta pagina sea referenciada.
El algoritmo saca la pagina con la mayor
etiqueta.
Se puede implementar en una segunda
corrida corriendo un progama en una
primer corrida en un simulador y usando
la informacion de las paginas
referenciadas.
El Algoritmo Optimo de
Remplazamiento de Paginas


Se pueden comparar otros algoritmos
contra este algoritmo optimo y saber
cuanto se pueden mejorar los algoritmos.
Este algoritmo solo sirve para evaluar el
desempeño de otros algoritmos y no tiene
uso practico porque el algoritmo es
especifico para la primera corrida.
Algoritmo de la Pagina no Usada
Recientemente


Cada pagina tiene asociado un bit R que
se prende cuando la pagina es
referenciada (lectura o escritura) y un bit
M que se prende cuando se modifica la
pagina.
Si el hardware no tiene estos bits, se
puede simular asignando el modo de la
pagina a lectura solamente cuando R esta
prendido y el modo lectura/escitura
cuando R y M estan prendidos.
Algoritmo de la Pagina no Usada
Recientemente

En cada interrupcion del reloj, los bits R se
apagan y se dividen las paginas en:





Clase
Clase
Clase
Clase
0:
1:
2:
3:
no referenciada, no modificada
no referenciada, modificada
referenciada, no modificada
referenciada, modificada
Las paginas de la clase 1 ocurren cuando
a una pagina de la clase 3 se le apaga el
bit R.
Algoritmo de la Pagina no Usada
Recientemente

El algoritmo NRU (Not Recently Used)
saca una pagina al azar de la clase no
vacia con el menor numero.
Algoritmo FIFO



Supongamos que un supermercado puede
mostrar solo k articulos diferentes.
El Algoritmo FIFO (First-In, First-Out) saca
el articulo que se introdujo con mas
tiempo para meter un nuevo articulo.
Puede remover articulos muy usados que
se han usado desde el hace mucho tiempo
y por eso es usado raramente.
Algoritmo de Remplazamiento de
Paginas de la Segunda Oportunidad


Se modifica el FIFO para que se saque la
pagina mas vieja si su bit R esta apagado,
sino apagamos su bit R y mandamos la
pagina al final de la cola.
Esta operacion se llama segunda
oportunidad.
Algoritmo de Remplazamiento de
Paginas de la Segunda Oportunidad

Si todas las paginas tienen el bit R
prendido, el algoritmo se degenera en un
FIFO.
Algoritmo de Remplazamiento de
Paginas del Reloj


El algoritmo de la segunda oportunidad es
ineficiente por mover las paginas a lo
largo de su lista y se puede mejorar
usando una lista circular.
El algoritmo del reloj mantiene un
apuntador a la pagina mas vieja y es otra
forma de implementar la segunda
oportunidad.
Algoritmo de Remplazamiento de
Paginas del Reloj
Algoritmo de Remplazamiento de
Paginas LRU



El algoritmo LRU (Least Recently Used)
supone que paginas que se han usado
recientemente mucho/poco se seguiran
usando mucho/poco.
Se implementa con una lista ligada
moviendo cada pagina al inicio de la lista
cuando se referencia la pagina.
Tambien se puede implementar con un
arreglo que guarda el tiempo del ultimo
acceso a cada pagina.
Algoritmo de Remplazamiento de
Paginas LRU
Algoritmo de Remplazamiento de
Paginas LRU

En una matrix de n x n inicialmente vacia
se prende la fila k y luego se apaga la
columna k al referenciar la pagina k, la fila
con menor numero binario es la pagina
menos usada recientemente.
Simulando LRU en Software


El algoritmo NFU (Not Frequently Used)
cuenta con los bits R el numero de veces
que se ha referenciada cada pagina y saca
la pagina menos refenciada.
El problema es que no olvida las
referencias.
Simulando LRU en Software
Simulando LRU en Software


Podemos simular bien el LRU modificando
el NFU (envejecimento) recorriendo los
bits de los contadores y sumando R a la
izquierda.
Cuando un error de pagina sucede se saca
la pagina con el menor contador.
Simulando LRU en Software


Cuando dos paginas no se han referenciado en
el mismo tiempo, el algoritmo de envejecimiento
saca el que tenga el menor numero de los bits
que quedan a la derecha de los ceros a la
izquierda en comun.
El algoritmo de envejecimeinto usa 8 bits para
los contadores para un tick de reloj de 20 ms.
Descargar

PageReplacementAlgorithms