Sunday, October 29, 2006
Simulador de Memoria Paginada
Primero para implementar los algoritmos use las sugerencias que salen en el libro de Tanenbaum,.
FIFO
Para este Algoritmo uso un arreglo para guardar el orden en que las paginas fueron ingresadas, y una cola para irlas reemplazando.
Second Chance
Es una pequeña modificación al algoritmo FIFO, que funciona bastante mejor que aquel. 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 cola. De esta forma, se le da una segunda oportunidad. Si el bit se encuentra sin fijar, la página se saca de memoria.
NRU (Not Recently Used)
Este algoritmo es el analogo de LFU, ya que en los libros asi se le llama. 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. Se utilizan las siguientes categorias con respecto al reemplazo.
- 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 cambiar 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.
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 recientemente usada, y al principio la más recientemente usada. 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 el momento 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.
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. Se utiliza a los efectos comparativos con los algoritmos factibles de ser implementados.
En nuestro caso que conocemos el "futuro" que es las siguientes reservaciones de memoria, entonces ordene el arreglo, usando quicksort que tiene un tiempo O(nlogn), y asi se ordena el archivo de manera que queden las que se usaran con mas frecuencia primero.
Preguntas Finales
1) ¿Qué estrategia de reemplazo de páginas escogería usted y por qué? Debe considerar los resultados obtenidos y el esfuerzo que le llevó implementar cada estrategia. Discuta lo que sus resultados muestran acerca de los méritos relativos de FIFO, LRU, LFU, Second Chance (CLOCK) y OPT para cada una de las diferentes combinaciones de parámetros.?
La que utilizaria seria LRU ya que en las simulaciones fue el que menos cambios tiene que hacer y mantiene una buena aproximacion con respecto al Optimo.
2) ¿Qué aspectos de la administración de memoria encontró que fue más difícil implementar?
La parte mas dificil de implementar fue la memoria paginada, ya que los algoritmos con ese manejar de bits de referencia se me hicieron dificil de manejar, que algunas cosas las tuve que hacer de otra manera para poder salir con eso, la verdad es que es demasiado ambiguo ciertas cosas.
3) ¿Qué aspectos de la administración de la memoria encontró más fácil implementar?
El de memoria continua, ya que se me hizo muy familiar a un proyecto de estructuras de Datos.
4) ¿Qué cambiaría en su diseño actual?
La verdad que le cambiaria, la manera de manejar el archivo de memorias, para motivos de la simulacion, (memoria paginada), no utilizaria hexadecimales, me parece que para efectos demostrativos, generaria numeros aleatorios, me parece mas facil.
Monday, October 09, 2006
Inicio de la Clase
