No usada recientemente (Not Recently Used, NRU)

Este algoritmo favorece a las páginas que fueron usadas recientemente. Funciona de la siguiente manera: cuando una página es referenciada, fija el bit de referencia para esa página. Similarmente, cuando una página es modificada, fija 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 en 0 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 1: no referenciada, no modificada
  • Categoría 2: no referenciada, modificada ( Categoria sin logica alguna)
  • Categoría 3: referenciada, no modificada
  • Categoría 4: referenciada, modificada

Las mejores páginas para cambiar son las que se encuentran en la categoría 0, mientras que las peores son las de la categoría 3. Se desaloja al azar una página de la categoría más baja que no esté vacía. Este algoritmo se basa en la suposición de que es mejor desalojar una página modificada a la que no se ha hecho referencia en al menos un tic de reloj, en vez de una página limpia que se está usando mucho.

Primera en entrar, primera en salir (FIFO, First In, First Out)

En este método el sistema operativo sólo tiene que guardar en qué orden las páginas fueron cargadas, de modo que al necesitar hacer espacio pueda fácilmente elegir la primera página cargada. Se usa una cola, al cargar una página nueva se ingresa en el último lugar. Aunque las colas FIFO son simples e intuitivas, no se comportan de manera aceptable en la aplicación práctica, por lo que es raro su uso en su forma simple. Uno de los problemas que presentan es la llamada Anomalía FIFO o Anomalía de Belady. Belady encontró ejemplos en los que un sistema con un número de marcos de páginas igual a tres tenía menos fallos de páginas que un sistema con cuatro marcos de páginas. El problema consiste en que podemos quitar de memoria una página de memoria muy usada, sólo porque es la más antigua.

FIFO Y ANOMALÍA DE BELADY M

TRES PAGINAS
PAGINAS
SOLICITUD RESIDENTES FALLA
A A F
B A,B F
C A,B,C F
D B,C,D F
A C,D,A F
B D,B,A F
E B,A,E F
A B,A,E
B B,A,E

 

CUATRO PAGINAS
PAGINAS
SOLICITUD RESIDENTES FALLA
A A F
B A,B F
C A,B,C F
D A,B,C,D F
A A,B,C,D
B A,B,C,D
E B,C,D,E F
A C,D,E,A F
B D,E,A,B F

Reloj, Segunda oportunidad

Es una pequeña modificación al algoritmo FIFO, que funciona bastante mejor que el FIFO. En este caso cuando una página debe ser sacada se toma la primera en la cola, y en vez de sacarla, consulta el valor de un bit de referencia. En caso de estar fijado (en 1) se cambia el bit a 0 y se lo coloca al final de la obstrucción, autorizando su tiempo de carga como si recién hubiera llegado al procesador. De esta forma, se le da una segunda oportunidad. Si el bit se encuentra sin fijar(en 0), la página se saca de memoria. Cada vez que la MMU accede a una página, fija su bit de referencia a 1. Para esto es necesario soporte para bit de referencia por hardware.

Existe una variante de este algoritmo que sobre la misma idea presenta una mejora en la implementación. Es el algoritmo del reloj, que lo que hace es tener una lista circular, de forma que al llegar al último elemento de la lista, pasa automáticamente al primero. Los elementos no se mueven al final de la cola cuando son accedidos, simplemente se pone su bit de referencia a 1. Esto nos evita tener que hacer movimientos de punteros en el caso de implementarlo con una lista enlazada. De hecho, se puede implementar con un array perfectamente, ahorrando así memoria.

Menos usada recientemente (Least Recently UsedLRU)

Este algoritmo difiere del de ‘No usada recientemente’ en el hecho de que aquel sólo se fija en el intervalo de tiempo desde que se pusieron en 0 los bits de referencia de las páginas, mientras que el algoritmo de ‘Menos usada recientemente’ intenta proveer un comportamiento casi óptimo mediante la observación de las páginas que menos fueron usadas recientemente. Este tipo de páginas, estadísticamente son las que tienen menor probabilidad de ser usadas nuevamente.

Aunque este algoritmo provee un buen comportamiento en teoría, es caro de implementar, en cuanto a recursos consumidos. Hay varias implementaciones que intentan mantener bajo el costo y lograr un rendimiento considerable. Un método consiste en tener una lista enlazada y ordenada de todas las páginas en memoria. En el final de la lista está la página menos usada recientemente, y al principio la más usada recientemente. El costo alto de este método es porque cada vez que se referencia una página debe ser movida en la lista, algo que consume mucho tiempo. Otra forma, que requiere soporte de hardware, consiste en tener un contador que es incrementado en cada instrucción del CPU. Cada vez que una página es accedida, gana el número del contador en ese momento. Cuando una página debe ser retirada de memoria, simplemente hay que buscar cuál es la que tiene el menor número, que es la que fue usada hace más tiempo. En el presente no existen contadores tan grandes para permitir esto. Debido al alto costo del LRU, se proponen algoritmos similares, pero que permiten implementaciones menos costosas, como los que siguen.

TRES PAGINAS
PAGINAS
SOLICITUD RESIDENTES FALLA
A A F
B A,B F
C A,B,C F
D B,C,D F
A C,D,A F
B D,B,A F
E B,A,E F
A B,E,A
B E,A,B

Algoritmo del conjunto de trabajo 

  • Conjunto de trabajo (working set) es el numero de paginas mínimo que un programa necesita para ejecutarse
  • El algoritmo debe garantizar en un espacio de tiempo el conjunto de páginas requeridas este presente.
  • Se utiliza un bit de referencia y una estampa de tiempo
    • Se mira en todas las páginas el bit de referencia
    • Coloco en el tiempo actual el último tiempo
    • Se saca a la pagina que no está referenciada

Reloj mejorado

Existe una variante de este algoritmo que sobre la misma idea presenta una mejora en la implementación. Es el algoritmo del reloj, que lo que hace es tener una lista circular, de forma que al llegar al último elemento de la lista, pasa automáticamente al primero. Los elementos no se mueven al final de la cola cuando son accedidos, simplemente se pone su bit de referencia a 1. Esto nos evita tener que hacer movimientos de punteros en el caso de implementarlo con una lista enlazada. De hecho, se puede implementar con un array perfectamente, ahorrando así memoria.

windows XP

  • utiliza paginacion por demanda por clustering. el agrupamiento trae las paginas alrededor de la pagina fallada.
  • a los proceso se les asigna un working set minimum y un working set maximum
  • el conjunto de trabajo minimo es el numero de paginas que se le garantiza a un proceso tener en memoria
  • a un proceso se le pueden asignar tantas paginas

solaris

  • mantiene una lista de paginas libres para asignarle a los procesos con faltas de pagina.
  • lostfree parámetro umbral (cantidad de memoria) para empezar a paginar.
  • desfree parámetro umbral para incrementar la paginacion
  • minfree parámetro umbral para empezar el intercambio
  • la paginacion es realizada por el proceso pageout
  • pageout busca las paginas utilizando el algoritmo del reloj modificado
  • scanrate es la velocidad con la cual las paginas son buscadas. Varia de solwscan.

reemplazo de paginas en linux

  • linux utiliza una variante del algoritmo del reloj para aproximarse a la estrategia de reemplazo de paginas LRU.
  • el administrador de memoria utiliza dos listas enlazadas.
    • la lista activa
      • contiene las paginas activas

 

ALMACENAMIENTO SECUNDARIO

 

Planificación del Disco

  • El SO es responsable por el uso eficiente del HW para los discos duros, esto significa tener un tiempo de acceso más rápido y un mayor ancho de banda para el disco
  • El tiempo de acceso tiene dos componentes principales:
    • El tiempo de búsqueda es el tiempo en el que el disco debe mover las cabezas hasta el cilindro que contiene el sector deseado
    • Latencia rotacional es el tiempo adicional de espera para que el disco rote sus cabezas hasta el sector deseado.
  • Minimizando el tiempo de búsqueda
  • El ancho de banda del disco es el número total de bytes transferidos dividido por el tiempo total entre la primera solicitud del servicio y el completado de la transferencia.
  • Existen diversos algoritmos para planificar el servicio de las solicitudes de entrada y salida del disco

FCFS( first come first serve)

cola de solicitudes= 98, 183, 37, 122, 14, 124, 65, 67 la cabeza inicia en 53.

la ilustración muestra el movimiento total de la cabeza de 640 cilindros

SSTF (Shortest seek time first)

  • elige la solicitud con el mínimo de tiempo de búsqueda desde la actual posición de la cabeza
  • la planificación SSTF es una forma de la planificación SJF

la ilustración muestra el movimiento total de la cabeza de 236 cilindros

SCAN – N PASOS

el brazo del disco empieza en uno de los extremos del disco, y se mueve hacia el otro extremo, sirviendo las solicitudas hasta que llega al otro extremo, donde el movimiento se invierte el servicio continua.

C-Scan

C-look

  • versión de C-scan
  • el brazo solo va tan lejos como este la ultima solicitud en cada dirección, entonces se devuelve sin ir al extreselección de algoritmos de planificacion de disco

RESUMEN

 

 

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 )

w

Conectando a %s