www.es-minix.org

[gerardo_ofc]

Ya habia posteado mis respuestas de la documentacion en un nuevo Topico afuera de este (el domingo 29 de Octubre). Pero vuelvo a adjuntarlas aqui por si acaso...

Estas son las respuestas a las preguntas: (la documentacion la he enviado al correo efutch@gmail.com y esta subida a la UV de la clase, ya que son muchas paginas e incluye imágenes). NOTA: TODO ESTO FUE HECHO EL DOMINGO 29 DE OCTUBRE 2006 (EL ENVIO DE LA DOCUMENTACION, DEL PROYECTO, ETC.)

7. Preguntas

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 estrategia que yo elegiría para reemplazo de páginas sería LRU, ya que es la que obtuvo los mejores resultados, independientemente de los parámetros (después del algoritmo OPT claramente). A pesar de que su implementación sea algo difícil, el algoritmo de LRU sólo utiliza un contador más, o una pila para llevar cuenta de qué páginas llevan más tiempo sin ser utilizadas. No obstante, el hardware para este algoritmo debería ser desarrollado y así tener computadoras más eficientes. Los resultados fueron generosos para este algoritmo, ya que muestran que varias veces se generaba el mismo número de Fallos de Página que el Óptimo.

Según los resultados con los diferentes parámetros, el algoritmo que siempre resultó teniendo el mayor número de Fallos de Página fue el algoritmo LFU (Least Frequently Used), seguido por el algoritmo de Second Chance (o Reloj). Estos dos algoritmos siempre mostraban ser ineficientes con las diferentes combinaciones de parámetros. Quizás si el algoritmo de Reloj fuera avanzado (que utilizara dos bits – uno de validez y uno de modificación - como explica el libro), resultaría más eficiente.

El algoritmo FIFO nunca pareció haber mostrado señales de la anomalía de Belady, ya que siempre a medida que el número de marcos aumentaba, el número de fallos de página disminuía. Quizás se podría apreciar esto mejor utilizando menos líneas de referencia.

Aparentemente, si la probabilidad S (que la próxima referencia sea en la misma página) es mayor, habrá una menor incidencia de Fallos de Página. Una probabilidad O alta causa mayor número de Fallos de Página.

2) ¿Qué aspectos de la administración de memoria encontró que fue más difícil implementar?

Lo más difícil de implementar en la administración de memoria, basándome en este proyecto, fue el manejo de las estructuras (más que todo orientación a objetos) para poder realizar los diferentes algoritmos de reemplazo y paginación. Aproximadamente el 60% del tiempo fue tomado desarrollando y pensando en las estructuras que utilizaría, y cómo las iba a utilizar. Estas estructuras incluyen la simulación de la memoria RAM, las listas enlazadas de agujeros y procesos, la tabla de páginas y la tabla de marcos.

Otro aspecto difícil fue poder otorgarle al usuario una interfaz amigable y lo suficientemente dinámica y flexible como para poder apreciar todos los algoritmos con una gran variedad de parámetros. Por ejemplo, el usuario puede ingresar el número de pausas que desea para apreciar las estadísticas del módulo 2, así como puede elegir cualquier valor entre 0 y 100 para las probabilidades S y O en la generación del archivo de referencias.

3) ¿Qué aspectos de la administración de la memoria encontró más fácil implementar?

Lo más fácil de implementar en la administración de la memoria quizás fueron los algoritmos de reemplazo de páginas, ya que después de hacer uno, los otros eran muy parecidos y solo requerían algunos cambios de implementación y a lo más 2 nuevas variables/estructuras de datos.

4) ¿Qué cambiaría en su diseño actual?

Lo que cambiaría de mi diseño actual sería permitirle al usuario elegir el tamaño de la memoria principal en el módulo 2 (que no solo se mantenga en 256 K).

[ivanordonez]

IVAN ADOLFO ORDOÑEZ MONCADA
10411030


Descripción

Este proyecto debería consistir en un simulador programado en VB.NET para investigar las diferencias relativas de los algoritmos de asignación de memoria y las politicas de reemplazo de páginas.

Sin embargo solo he realizado el primer modulo (generar un archivoconteniendo con 10000 strings de referencia a memoria, basado en el formato dinero), y el segundo modulo ( manejador de memoria contigua que simula la asignación de memoria en sistemas operativos no paginados)


Funcionamiento

Modulo 1: en general el modulo 1 genera cada string de referencia dependiendo de una ¨probabilidad ¨ s de q caiga en la misma página de la referencia anterior, una ¨probabilidad ¨ o de q caiga en la página anterior o siguiente de la referencia anterior, y de perdida generar cualquier referencia al ¨azar¨.

La 1ra ref y la de ¨perdida¨ tienen la forma para generar la dir :

dir = CInt(Int(1048576 * Rnd()))

si se cumple s ó o:

dir = ((pag_act + #) * 1024) + CInt(Int(1024 * Rnd()))

donde # es:
0 con prob s
+1 ó -1 con prob o

Luego se completa el string, con el char 0 o 1 (para cumplir con el formato dinero).

Modulo 2: es capaz de simular la asignación de memoria continua por medio de First-Fit o Best-Fit dependiendo de lo que el usuario desea (expresado a travez de radiobuttons).

Existen dos estructuras principales:

- arr_proc: arreglo que almacena cada uno de los process en potencia del sistema. Cada entrada está compuesto de tres campos: dir_inic (primer byte que ocupa), esp_asignado (bytes reservados para el proceso), esp_utilizado (bytes reales que utiliza el proceso).

- arr_hold: arreglo que almacena cada uno de los agujeros en potencia del sistema. Cada entrada está compuesto de dos campos: dir_inic (primer byte que ocupa), esp_asignado (bytes disponibles para un proceso).

Las estructuras se basan el concepto de conteo, es decir que no existe una entrada por cada byte de la memoria, sino que la entrada de cada proceso o agugero (hold) guarda cuantos bytes a partir de ese punto pertenecen al proceso o agujero, respectivamente.

Para implementar el First-Fit lo que se hace es ordenar la estructura arr_hold de manera que los holds con byte inicial más cercano a cero queden en el inicio de la misma (orden descendente); en cambio en el Best-Fit se ordena la estructura arr_hold de manera que los holds con menos cantidad de bytes queden en el inicio de la misma (orden descendente).

Ahora, en este proyecto he utilizado para el ordenamiento el algoritmo de burbuja mejorado (por mayor facilidad), sin embargo para sistema con capacidad de manejar mucha memoria y procesos, resultaría más conveniente otro algoritmo (p.e. quick sort).
También se podrían utilizar otras estructuras, p.e. árbol B.

Para el momento de unir holds (por cierto fue lo que más me costó), verifíco si el espacio liberado por el proceso es contiguo a algun hold, primero por debajo y luego por arriba; en el primer caso sum los bytes disponibles a los del hold, en el segundo caso ,además, asigno como primer byte del hold el primer byte del proceso saliente. Luego reviso de forma similar, si han quedado dos holds contiguos para unirlos (idem).

En cuanto a la compactación ordeno la estructura arr_proc en orden descendente basado en el valor del primer byte de cada proceso. Luego hago que el primer byte del proceso i+1 sea la suma del primer byte del proceso i + la cantidad de bytes asignados a el proceso i.



Compilación y Uso:

Para correr el programa se debe contar con .NET FRAMEWORK (fue programado sobre la version 2003).
Para utilizarlo el usuario solo debe dar click sobre el botón que dice ¨Modulo 1¨ y listo, podrá observar en un cuadro de texto el contenido del archivo generado; o dar click en Modulo 2 para ver los resultados de la simulacion de la asignacion de la memoria continua.


Procedimientos

show_file: muestra en un objeto tipo RichTextBox el contenido del archivo generado.
crear_str_ref: crea el string de referencia con el formato dinero.
to_dec: convierte strings en integer decimal.

Comentarios de Implementación

De verdad q este proyecto resultó ser mas complejo de lo q pensé. En el modúlo 2 por ejemplo por cada problema que resolvía me ganaba otros tres. La estructura cada vez se hacía más compleja, y casi ¨imposible¨ de manejar. Igual, en el intento aprendí bastante.
Es evidente que otras estructuras (árboles talvez) y algoritmos de ordenamiento y busqueda más complejos daría mayor eficiencia al proyecto, pero creo que lo utilizado aqui (para este caso particular) tiene un buen desempeño.


Preguntas:


1) ¿Qué estrategia de reemplazo de páginas escogería usted y por qué?
Esta pregunta no la contesto xq no hice el tercer modulo (así q no estaría bien).

2) ¿Qué aspectos de la administración de memoria encontró que fue más difícil implementar?
Fue el hecho de unir holds al momento de desasignar memoria que pertenecia a un proceso. No me salía, parecía que iba a ser más sencillo, la verdad es que al final es "sencillo", lo complicado es encontrar ese método "sencillo". Por ejemplo uno de mis errores lógicos fue en el caso de que el nuevo hold estuviera entre otros dos: ya que unia el nuevo hold con el de arriba y luego con el de abajo, generando asi una traslapación.

3) ¿Qué aspectos de la administración de la memoria encontró más fácil implementar?
Creo que se escucha raro, no se si realmente es lo más facil pero fue lo que más rápido me salió: la compactación, practicamente a la primera me salió.

4) ¿Qué cambiaría en su diseño actual?
Bueno, primero el algoritmo de ordenamiento, utilicé el buble sort (es sencillo, pero está bien para está aplicación particular) pero sobre todo si el sistema maneja mucha memoria y procesos, esto será muy lento.
Segundo, la estructura utilizada fue arreglos, claro en vb.net estos pueden ser dinámicos, pero segun me dicen es mejor si uno utiliza árboles (es más complejo, pero más eficiente).

[damaya]

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.
No hice la tercera parte del proyecto pero para mi la mejor estrategia seria LFU, Esto porque se tiene un mejor control de que pagina se ha usado menos y aunque la implementacion es mas trabajada, el mejor rendimiento del sistema lo valdrá.


2) ¿Qué aspectos de la administración de memoria encontró que fue más difícil implementar?
Desde mi forma de implementacion usando arboles (y sus nodos representan agujeros) First fit y Best fit resultan casi igualmente complejas, con un poco mas de trabajo Best fit porque se debo subdividir el arbol en dos partes para encontrar cual es el mejor Agujero para la requisicion de memoria.

3) ¿Qué aspectos de la administración de la memoria encontró más fácil implementar?
El First fit, ya que leo la raiz de albol para ver que cantidad de memoria disponible tiene, si necesito mas memoria que esa elimino la raiz y leo la nueva raiz hasta encontrar un tamaño mayor al que necesito.

4) ¿Qué cambiaría en su diseño actual?
Uso demasaidas estructuras de datos:

• 2 arboles, uno de ellos tiene listas enlazadas dentro de sus nodos.
  
• 1 tabla Hash para informacion de los procesos activos

Trataria de disminuir este numero de estructuras sin bajar el rendimiento


FELIZ NAVIDAD A TODOS (JO JO JO JOO)!

pd: Ingeniero, Esperamos pueda darnos Compiladores el segundo semestre del proximo año!

[lmelgars]

Luis Alfredo Megar Sánchez
10411182

Preguntas Indicadas

2) ¿Qué aspectos de la administración de memoria encontró que fue más difícil implementar?
R// Hasta donde pude desarrollar el proyecto una de las cosas que percate fue el manejo de los agujeros entre bloques de procesos en memoria.

3) ¿Qué aspectos de la administración de la memoria encontró más fácil implementar?
El algoritmo para first-fit resulto ser el mas fácil de implementar pues según la estructura que emplee se me facilito recorrerla y ubicar los procesos en memoria.

4) ¿Qué cambiaría en su diseño actual?
R// cambiaria dos aspectos:
1 - Las estructuras empleadas que se basan en listas indexadas por medio del uso de arreglos dinámicos, por una estructura de árbol.
2 - El algoritmo de recorrido por uno más eficiente empleando la estructura de árbol antes mocionada.

Feliz Navidad!