Algoritmos de reemplazo de pagina

POLITICAS DE RECUPERACION

– politica de recuperacion:
   – determina cuando una pagina se deberia traer a la memoria principal
   – con paginacion bajo demanda (demand paging), una pagina se trae a memoria solo cuando se hace referencia a una posicion en dicha pagina
las faltas de pagina forzan el cambio
 – que pagina debe ser removida
– establecer espacio para la pagina que entra
  • Establecer espacio para la página que entra.
  • Las páginas modificadas deben ser guardadas las otras pueden sobreescribirse
  • Es aconsejable no reemplazar una página usada con frecuencia, seguramente la necesitaremos.
ALGOTIMOS DE REEMPLAZO DE PAGINA

Algoritmo óptimo de reemplazo de página

  • Reemplaza la página que se requerirá en el punto más lejano.
    • Optimo pero no lograble.
  • La estimación se basa en el registro de uso de las corridas anteriores de los procesos.
  • Sigue siendo poco práctico.

Algoritmo de página no recientemente usada (NRU)

  • Cada página tiene un bit de referencia, un bit de modificación.
  • Las páginas se clasifican
    1. No referenciadas, no modificadas.
    2. No referenciadas, modificadas.
    3. Referenciadas, no modificadas.
    4. Referenciadas, modificadas.
  • NRU remueve las páginas aleatoriamente desde el número más bajo en clases no vacías.

FIFO (First-in,First-out)

  • Conserva una lista encadenada de todas las páginas en el orden en que llegaron a memoria.
    • Trata los marcos de página ocupados como si se tratase de un buffer circular.
    • Las páginas se reemplazan mediante una estrategia cíclica de tipo round-robin.
    • Es una de las políticas de reemplazo más sencillas de implementar.
    • Se reemplaza la página que lleva en memoria más tiempo.
    • Estas páginas podrían necesitarse de nuevo muy pronto.
  • Se reemplazan las páginas al principio de la lista.
  • Desventaja
    • Las páginas que más estén en la memoria no necesariamente son las más usadas.

FIFO.png

anomalida de belady M : que sistema tenga memoria no garantiza que el sistema funcione mejor

ALGORITMO DE RELOJ O SEGUNDA OPORTUNIDAD
si la pagina señalada tiene el bit de referencia en 1 dejela funcionar, en caso contrario poner su bit de referencia en 0 y darle la oportunidad, si en la siguiente vuelta aun no esta referenciada sacarla
sin-tc3adtul8.png
ALGORITMO LRU (menos recientemente refernciadas)
  • Asume que las páginas recientemente usadas serán usadas de nuevo, elimina las páginas que no han sido usadas por mucho tiempo.
  • Reemplaza la página que no se haya referenciado desde hace más tiempo.
  • Por el principio de proximidad referenciada, esta página sería la que tiene menos probabilidad de volver a tener referencias en un futuro próximo.
  • Debe conservar una lista de páginas enlazadas
    • Las páginas usadas recientemente de primeras y las menos usadas de últimas.
    • Actualiza estos enlaces en cada referencia de memoria.
  • De forma alternativa puede llevar un contador en cada entrada de la tabla de páginas, seleccionando la página con el menor valor.
    • Cada página podría etiquetarse con el instante de tiempo de su última referencia. Esto podría suponer una gran sobrecarga.

sin-tc3adtulo9.png

ALGORITMO DEL CONJUNTO DE TRABAJO (11)

1327736_orig.jpg
ALGORITMO DE PAGINA NO RECIENTEMENTE USADA (NRU)

Reloj mejorado

Se toma el algoritmo del reloj pero con los 2 bit, el de referencia y el de modificación:

0,0 No referenciadas, no modificadas.

0,1 No referencidas, modificadas.

1,0 Referenciadas, no modificadas.

1,1 Referenciadas, modificadas.

Se reemplaza el de la clase más baja (Macintosh).

Otros algoritmos de reemplazo de páginas

  • Aleatorio (Random): Reemplaza las páginas de forma aleatoria, se trabaja en el OS/360 cuando se degenera el LRU, también se utilizó en extinto i860 de intel (risc).
  • No frecuentemente usada (NFU): Cada página tiene un contador, en cada intervalo de reloj se incrementa en 1 el contador de las páginas referenciadas, así cuando se requiere intercambio se saca la de menor contador.
  • Envejecimiento (Aging): Similar al anterior pero tiene en cuenta el tiempo, primero se desplaza a la derecha antes de incrementar. Con lo cual se compensan las páginas más recientemente usadas.
  • La menos usada frecuentemente (LFU): Reemplaza la página que menos intensivamente ha sido referenciada, se basa en la heurística de que una página no referenciada con frecuencia es probable que no sea referenciada en el futuro.
  • Reemplazo de página más lejana FPR (Far Page Replacement): Crea un grafo de acceso que caracteriza los patrones de referencia de un proceso. Reemplaza la página no referenciada que esté más lejana de cualquier página referenciada en el grafo de acceso. Es compleja de manejar sin soporte en hardware, no ha sido implementada en sistemas comerciales.
Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s