Sistemas Operativos I y II

Introducción

Universidad Tecnológica Centroamericana UNITEC
Sistemas Operativos II
Reporte del proyecto # 1
Alumno: Douglas Yovanny Velásquez Escoto
Cuenta: 971269
Catedrático: Ing. Egdares Futch H.
Lugar y Fecha: Tegucigalpa M.D.C 29 de octubre de 2006


Descripción y funcionamiento del proyecto

Este proyecto consiste en el desarrollo en el lenguaje de programación Java (J2SE), un simulador programado para investigar las diferencias relativas de los algoritmos de asignación de memoria y las políticas de reemplazo de páginas (FIFO, LRU, LFU y OPT). El programa generara estadísticas, apropiadas para cada módulo.

El simulador consta de tres módulos:

1) Generador de strings de referencia a memoria

El simulador cuenta con una opción para generar un archivo conteniendo 10,000 strings de referencia a memoria (direcciones de 20 bits), generadas de la siguiente manera:

• La dirección de referencia inicial se escoge de forma aleatoria para comenzar.
• Para las demás referencias a memoria, la siguiente referencia a memoria será dentro la misma página, con probabilidad s (alta).
• Si la siguiente referencia a memoria no es dentro de la página actual, entonces con alguna otra probabilidad o (alta), la referencia será en la página antes de la actual (actual-1) o la página después de la actual (actual+1), equiprobablemente, de acuerdo al principio de la Localidad de Referencias.
• En caso contrario, se escoge de forma aleatoria (podría volver a ser la actual o actual-1 o actual+1).

El archivo tiene el formato Dinero, indicando únicamente si la referencia a cada página es lectura o escritura (tipos Dinero 0 y 1).

2) Manejador de memoria contigua

El módulo manejador de memoria contigua simula el uso de asignación de memoria en sistemas operativos no paginados. Implemente las políticas first-fit y best-fit, asumiendo que los procesos no crecen ni se encogen, en un computador con 256 KB de RAM.

Este módulo usa como input un archivo de strings de referencia generado por el módulo descrito en 1), interpretándolo de tal manera que la acción 0 indica “asignar memoria” y la acción “1” indica “desasignar memoria”. Las direcciones generadas se usarán de la siguiente manera: los primeros cuatro bits denotan el Process ID, los siguientes 16 bits denotan el tamaño de la memoria solicitada, en bytes. Este módulo manejar errores, si acaso un proceso solicita más memoria (crece), o desasigna memoria (encoge) sin estar cargado en RAM.

• Fusión de bloques libres: cuando un proceso termine (“desasigne memoria”), la memoria que el proceso tenía asignadas se regresa a la lista de disponibles. Se combinar agujeros que estén adyacentes uno a otro para formar un bloque libre más grande, con el fin de reducir el nivel de fragmentación.
• Compactación: el manejador de memoria compacta la memoria si detecta fragmentación externa, que ocurrirá cuando un proceso nuevo pida memoria y no se pueda asignar debido a fragmentación.

La salida del módulo consiste de las siguientes estadísticas
Tamaño de la memoria, memoria libre, memoria usada, numero de agujeros, número de procesos activos, número de veces compactada, fragmentación externa, fragmentación interna, referencias procesadas, se muestra de forma gráfica, y si puede desplegar esta información cuando el usuario lo solicite.

Quote:
Ejemplo:
Tamaño de la memoria = 262144 bytes, asignados = 113165, libres = 148979
Actualmente hay 3 “agujeros” y 5 procesos activos
Se ha compactado la memoria 7 veces
Fragmentación: interna=23% externa=32%
Direcciones procesadas=862

Lista de agujeros:
Agujero 1: Posición Inicial: 75895, Tamaño: 66175
..

Lista de procesos:
process id: 8, Posición Inicial: 218683, Tamaño del Proceso: 23132, Memoria utilizada: 100%
..


Se puede cambiar la velocidad de la simulación estableciendo intervalos de pause desde 1 milisegundo o ejecutarse paso a paso cada referencia del archivo generado por el modulo 1)

Además muestra los mensajes que incluye los errores

Quote:
Ejemplo:
Acción :0, Proceso :14, Memoria :17560
No se puede asignar memoria, Process id: 14, requiere: 17560, Asignado: 0
Acción :1, Proceso :14, Memoria :18975
No se puede liberar memoria, no se encuentra el proceso, Process id: 14, requiere: 18975
Acción :1, Proceso :14, Memoria :19911
No se puede liberar memoria, no se encuentra el proceso, Process id: 14, requiere: 19911
Acción :0, Proceso :14, Memoria :19179
No se puede asignar memoria, Process id: 14, requiere: 19179, Asignado: 18538
Acción :0, Proceso :14, Memoria :20367
No se puede asignar memoria, Process id: 14, requiere: 20367, Asignado: 0
..


3) Manejador de memoria paginada

El módulo manejador de memoria paginada sirve para investigar la efectividad relativa de las estrategias de reemplazo de páginas FIFO, LRU, LFU, Second Chance (CLOCK) y OPT para algunos parámetros del sistema. El objeto es medir el número de page faults generados por cada estrategia.

Para este módulo, se asume que cada proceso obtiene 1 megabyte (1024 kilobytes) de memoria virtual, divididos en 1K páginas y un tamaño de página de 1024 bytes. Es decir que el proceso puede generar direcciones virtuales con referencias de página de 0 a 1023, que vendrán del archivo de strings de referencia generado por el módulo 1).

La simulación proporción información sobre los page faults ocurridos para cada una de las estrategias al proporcionar el número de page frame que se utilizara:


Ejemplo de salida: (100 page frame)
Estrategia de reemplazo de páginas FIFO, número de page foults = 1260
Estrategia de reemplazo de páginas LRU, número de page foults = 1264
Estrategia de reemplazo de páginas LFU, número de page foults = 1928
Estrategia de reemplazo de páginas CLOCK, número de page foults = 1260
Estrategia de reemplazo de páginas OPT, número de page foults = 952




Cómo se compila y usa el proyecto

Se requiere Maquina Virtual de Java
Versión recomendada: 1.5.0 (build 1.5.0_05-b05)

Para compilar se ejecuta el archivo Make.bat que contiene lo siguiente
.-Compilación de archivos
\j2sdk1.4.2_05\bin\javac generadorString.java
\j2sdk1.4.2_05\bin\javac MCBestFit.java
…
\j2sdk1.4.2_05\bin\javac Proyecto1.java
.-Cada uno de los archivos .java

Creación del jar ejecutable
\j2sdk1.4.2_05\bin\jar cvfm Proyecto1.jar MANIFEST.MF BloqueMemoria.class generadorString.class …
.-Cada uno de los archivos .class que se genero en la compilación

.-\j2sdk1.4.2_05\bin\ la ubicación donde se encuentra el archivo javac y jar

Para ejecutar
javaw –jar Proyecto1.jar o ejecutar desde el explorador de Windows
La cual presentar una ventana con diferentes botones y cuadros de texto para acceder a los 3 módulos


Descripción de rutinas y procedimientos usados

Clases usadas
generadorString
MCBestFit
MCBesttFitForm
MCFirstFitForm
MCFistFit
MemoriaContinua
memPaginacion
Proyecto1

Clase generadorString
Esta clase hace el trabajo del modulo 1

java.lang.Object
generadorString
________________________________________
establecerS
Set de la probabilidad s

establecerO
Set de la probabilidad s

establecerTamPage
Set del tamaño de la página

CrearArchivo
Crea el archivo en donde se almacenara los 10,000 string de referencia a memoria, generados por el método GenerarLinea

GenerarLinea
Genera si la referencia es de escritura o lectura (tipos Dinero 0 y 1)
Determina si es la primera referencia ejecuta el método generarDireccionInicial
Si no generarDireccionProbabilidad

generarDireccionInicial
Genera un número aleatorio de 0 a (2^20)-1, y lo convierte a hexadecimal

generarDireccionProbabilidad
Utiliza la Probabilidades s y o para genera la siguiente dirección a través de método
generarDireccionPagina en caso contrario genera con generarDireccionInicial

generarDireccionPagina
Genera la dirección en base a la página que se especifica en generarDireccionProbabilidad


Clase MemoriaContinua
Clase abstracta que implementa el modulo 2 tanto para best-fit como para First-fit

java.lang.Object
java.lang.Thread
MemoriaContinua

abrirArchivo
Abre el archivo generado por el módulo 1

RunInicia la simulación mediante hilo

iniciarValores
Establece los valores del tamaño de la memoria a utilizar y los objetos para dibujar

iniciarSimulacion
Llama a los métodos del la clase concreta para crear el árbol de memoria crearArbolMemoria y agrega el bloque inicial de memoria conteniendo el tamaño total (256K);

Continuar
Cuando se detiene la ejecución del hilo Continuar reanuda la ejecución, con esta función se implementa la ejecución paso a paso de las referencias de memoria

procesarLinea
Cada una de las referencias de memoria se procesa en este método, determinando si se agrega un nuevo proceso, si se quita el proceso, si se agrega o quita memoria al proceso, si se compacta la memoria, mediante las búsquedas utilizando los métodos de búsquedas definidos.
Este método genera el mensaje de la simulación a demás de los mensajes de error.

agregarProceso
Agrega un nuevo proceso también quita del espacio disponible de memoria

quitarProceso
Quita un proceso y une los espacios de memoria libre, combinando agujeros que estén adyacentes, este método une el espacio adyacente que se encuentra adelante, y para el espacio adyacente que se encuentra atrás, utiliza la llamada al método unirAnterior

buscarProceso
Busca un proceso en el árbol de procesos por id

mostrarProcesos
Utilizado para dibujar

dMemoria
Dibuja la memoria libre

dProceso
Dibuja los procesos en su correspondiente ubicación, con su fragmentación interna utilizando las coordenadas obtenidas por obtenerPorcentaje

obtenerPorcentaje
Establece la simetría del dibujo y la escala a transformar las posiciones de memoria

Compactar
Compacta la memoria cuando hay fragmentación externa

Listar
Muestra la estadística de la simulación

ComparadorTamano
Para ordenar el árbol de memoria por tamaño

ComparadorDireccion
Para ordenar el árbol de memoria por posición

ComparadorProceso
Para ordenar el árbol de procesos por id

ComparadorProcesoPosIni
Para ordenar el árbol de procesos por posición

Clase MCBesttFitForm
java.lang.Object
java.awt.Component
java.awt.Container
java.awt.Window
java.awt.Frame
javax.swing.JFrame
MCBesttFitForm

Clase de interfase de usuario que llama a la clase
MCBestFit
Métodos heredados de JFrame


Clase MCBestFit
Esta clase implementa la política Best-fit del modulo 2 extendida de la clase MemoriaContinua

java.lang.Object
java.lang.Thread
MemoriaContinua
MCBestFit

crearArbolMemoria
Crea el árbol que se utilizara para administrar los espacios disponibles.

buscarMemoria
Busca en el árbol el bloque de memoria.

unirAnterior
Unir una bloque de memoria que se acaba de liberar con el bloque libre anterior consecutivo, si existe ese bloque.


Clase MCFirstFitForm
java.lang.Object
java.awt.Component
java.awt.Container
java.awt.Window
java.awt.Frame
javax.swing.JFrame
MCFirstFitForm

Clase de interfase de usuario que llama a la clase
MCFistFit
Métodos heredados de JFrame


Clase MCFistFitEsta clase implementa la política First-fit del modulo 2 extendida de la clase MemoriaContinua

java.lang.Object
java.lang.Thread
MemoriaContinua
MCFistFit

crearArbolMemoria
Crea el árbol que se utilizara para administrar los espacios disponibles.

buscarMemoria
Busca en el árbol el bloque de memoria.

unirAnterior
Unir una bloque de memoria que se acaba de liberar con el bloque libre anterior consecutivo, si existe ese bloque.


Clase memPaginacion
java.lang.Object
java.awt.Component
java.awt.Container
java.awt.Window
java.awt.Frame
javax.swing.JFrame
memPaginacion

Clase que implementa el módulo 3

iniciarSimulacion
Inicializa las listas y los valores para la simulación y lee cada línea del archivo generado por el modulo uno y llama a los metodos FIFO, LRU,LFU,CLOCK y OPT
Y al final muestra la información de los page foults.


FIFO
Implementa la estrategia de reemplazo de página FIFO

LRU
Implementa la estrategia de reemplazo de página LRU

LFU
Implementa la estrategia de reemplazo de página LFU

Desplazar
Desplaza un bit con alguna frecuencia en la lista de bits del algoritmo LFU

CLOCK
Implementa la estrategia de reemplazo de página CLOCK

OPT
Implementa la estrategia de reemplazo de página OPT

abrirArchivo
Abre el archivo generado por el modulo 1 y lo deja listo para ser leído por el método iniciarSimulacion




Comentarios de implementación y preguntas indicadas

Comentarios del módulo 2
En este módulo se utilizo una clase abstracta que implementa la memoria continua utilizando dos árboles uno para manejar los espacios libres y otra para manejar los procesos.
Los árboles utilizados son de tipo TreeSet de la clase de Java
Las clases concretas son las que implementan las politicas best-fit y First-fit

En las políticas Best-fit se utiliza el comparador ComparadorTamano para crear el árbol de memoria, para que el árbol se encuentre ordenado por tamaño.
Las búsqueda por tamaño se realiza mediante el método de búsqueda del la clase TreeSet tailSet que devuelve la rama de los nodos mayores al valor especificado en la búsqueda, si este nodo existe es el primero y se obtiene mediante el metodo fisrt () del conjunto de la clase de java SortedSet
Las búsquedas por dirección se realizan linealmente a través de un recorrido por el árbol

En las políticas First-fit se utiliza el comparador ComparadorDireccion para crear el árbol de memoria, para que el árbol se encuentre ordenado por posiciones de memoria.
Las búsqueda por dirección se realiza mediante el método de búsqueda del la clase TreeSet tailSet que devuelve la rama de los nodos mayores al valor especificado en la búsqueda, si este nodo existe es el primero y se obtiene mediante el método fisrt () del conjunto de la clase de java SortedSet
Las búsquedas por tamaño se realizan linealmente a través de un recorrido por el árbol.
Las búsquedas de procesos se implementan de igual manera

En las políticas First-fit ,en la fusión de bloques libres para encontrar el nodo adyacente anterior en el árbol de memoria se utiliza el método de búsqueda del la clase TreeSet headSet que devuelve la rama de los nodos menores al valor especificado en la búsqueda, si este nodo existe es el ultimo y se obtiene mediante el metodo last() del conjunto de la clase de java SortedSet .

En las políticas Best-fit, en la fusión de bloques libres para encontrar el nodo adyacente anterior en el árbol de memoria se realiza un recorrido de todo el árbol, hasta encontrar un bloque adyacente anterior ya que como esta ordenado por tamaño, no se sabe cual es la posición que tiene en la memoria cada nodo.



Comentarios del módulo 3
En el módulo 3 se utilizo la clase Vector de java para implementar las estrategias de reemplazo de paginas al igual que para implementar el bit se utilizo la clase vector
La clase vector es de tipo lista.



Resumen de los page foults

Probabilidad s = 0.80 y o 0.80

10 page frames
Estrategia de reemplazo de páginas FIFO, número de page foults = 1433
Estrategia de reemplazo de páginas LRU, número de page foults = 1433
Estrategia de reemplazo de páginas LFU, número de page foults = 2226
Estrategia de reemplazo de páginas CLOCK, número de page foults = 1433
Estrategia de reemplazo de páginas OPT, número de page foults = 1335

50 page frames
Estrategia de reemplazo de páginas FIFO, número de page foults = 1390
Estrategia de reemplazo de páginas LRU, número de page foults = 1389
Estrategia de reemplazo de páginas LFU, número de page foults = 2073
Estrategia de reemplazo de páginas CLOCK, número de page foults = 1390
Estrategia de reemplazo de páginas OPT, número de page foults = 1120

100 page frames
Estrategia de reemplazo de páginas FIFO, número de page foults = 1329
Estrategia de reemplazo de páginas LRU, número de page foults = 1327
Estrategia de reemplazo de páginas LFU, número de page foults = 1931
Estrategia de reemplazo de páginas CLOCK, número de page foults = 1329
Estrategia de reemplazo de páginas OPT, número de page foults = 1002

Probabilidad s = 0.95 y o 0.95

10 page frames

Estrategia de reemplazo de páginas FIFO, número de page foults = 128
Estrategia de reemplazo de páginas LRU, número de page foults = 125
Estrategia de reemplazo de páginas LFU, número de page foults = 406
Estrategia de reemplazo de páginas CLOCK, número de page foults = 128
Estrategia de reemplazo de páginas OPT, número de page foults = 121

50 page frames
Estrategia de reemplazo de páginas FIFO, número de page foults = 118
Estrategia de reemplazo de páginas LRU, número de page foults = 120
Estrategia de reemplazo de páginas LFU, número de page foults = 338
Estrategia de reemplazo de páginas CLOCK, número de page foults = 118
Estrategia de reemplazo de páginas OPT, número de page foults = 114

100 page frames

Estrategia de reemplazo de páginas FIFO, número de page foults = 114
Estrategia de reemplazo de páginas LRU, número de page foults = 114
Estrategia de reemplazo de páginas LFU, número de page foults = 150
Estrategia de reemplazo de páginas CLOCK, número de page foults = 114
Estrategia de reemplazo de páginas OPT, número de page foults = 114



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 OPT es la de mejor rendimiento
La estrategia LFU es la de peor rendimiento

Las estrategias FIFO y LRU tienen casi el mismo rendimiento con diferencia que cuando se aumenta el número de frames se puede ver una mejora la mayoría de veces mejorando LRU

FIFO y CLOCK mantienen el mismo rendimiento
El peor

Yo escogería la estrategia de replazo LRU ya que es la mejor después de OPT, y no es tan difícil de implementar como OPT ya que este debe conocer todas las referencias de memoria de antemano.


2) ¿Qué aspectos de la administración de memoria encontró que fue más difícil implementar?
La más difícil fue la memoria continua ya que se tienen que mantener información de los agujeros y los procesos y toda la implementación que realiza manejar memoria continua.

3) ¿Qué aspectos de la administración de la memoria encontró más fácil implementar?
La estrategia de reemplazo FIFO es la mas fácil de implementar, también lo es LRU.

4) ¿Qué cambiaría en su diseño actual?
En las estrategias de reemplazo se pueden implementar más mejoras a los algoritmos, por lo demás no cambiaria nada a este diseño.