Proyecto Programado # 4

Universidad de Costa Rica

Escuela de Ciencias de la Computación e Informática

CI-1310 Sistemas Operativos

• Descripción
• Las asignaciones de multiprogramción y de memoria virtual hacen uso del sistema de archivos de Nachos. La cuarta fase de Nachos es construir este sistema de archivos. Como en las primeras tareas, el estudiante tiene acceso a una parte del código que necesita; la otra parte debe hacerla de manera que complete y mejore el sistema de archivos que actualmente tiene Nachos
• El primer paso, como siempre, es leer y entender el sistema de archivos parcial que ahora existe. Para ello, corra el programa provisto en el directorio "filesys" (./nachos -f -cp test/small small) para un caso de prueba sencillo del código, en este ejemplo, la opción -f da formato lógico al disco físico emulado (se trata de un archivo llamado "DISK" en ese directorio), y -cp copia el archivo del sistema de archivos de UNIX `test/small', con el nombre "small" dentro de ese disco recién creado
• El código del "file system" está en los archivos que se describen en la siguiente tabla:

• fstest.cc	un caso de prueba simple para el sistema de archivos
  filesys.h filesys.cc	interfaz de alto nivel para el sistema de archivos
  directory.h directory.cc	convierte los nombres de archivos a sus correspondientes encabezados de archivo en disco; la estructura de datos del directorio se almacena como un archivo
  filehdr.h filehdr.cc	administra la estructura que representa la distribución de los datos del archivo en el disco
  openfile.h openfile.cc	convierte las lecturas y escrituras de archivo en lecturas y escrituras de un sector de disco
  synchdisk.h synchdisk.cc	provee acceso sincronizado a un disco físico no sincronizado, de tal manera que los hilos se bloqueen hasta que su solicitud haya sido completada
  disk.h disk.cc	emula un disco físico al enviar las solicitudes de lectura y escritura de bloques de disco a un archivo UNIX y luego generar una interrupción después de algún período de tiempo. Los detalles de cómo hacer las solicitudes de lectura y escritura varían considerablemente de un dispositivo a otro; en la práctica, usted querría esconder estos detalles detrás de algo parecido a la abstracción provista por este módulo.

• El sistema de archivos provisto tiene una interfaz similar a la de UNIX, es por ello que usted puede leer las páginas de "man" de UNIX para los llamados al sistema creat, open, close, read, write, lseek y unlink
• El sistema de archivos de Nachos, tiene llamadas que son similares, pero no idénticas a esas; el sistema de archivos convierte esas llamadas en operaciones físicas del disco
• Una de las principales diferencias entre el sistema de archivos de UNIX y el de Nachos, es que el de este último está implantado en C++. "Create" (como el "creat" de UNIX, "Open" (como el "open") y "Remove" (como el "unlink") están definidos en el objeto "FileSystem", ya que ellos manipulan los nombres de archivos y directorios. "FileSystem::Open" regresa un puntero a un objeto "OpenFile", el cual es usado para operaciones sobre archivos directamente tales como "Seek" ("lseek"), "Read" ("read"), "Write" ("write"). Un archivo abierto se cierra destruyendo el objeto "OpenFile"
• Varias de las estructuras de datos del sistema de archivos de Nachos están almacenadas tanto en memoria como en el disco. A fin de proveer alguna uniformidad, todas estas estructuras de datos deben proveer procedimientos para leer datos del disco y colocarlos en memoria ("FetchFrom") y otro procedimiento para almacenar la información en el disco nuevamente ("WriteBack"). Tome en cuenta que las representaciones en disco y en memoria no tienen que ser idénticas
• El código provisto implanta todas las partes importantes de un sistema de archivos, pero tiene algunas limitaciones. Su trabajo es el de corregir algunas de estas limitaciones. Tome en cuenta de que existen interacciones entre las distintas partes de esta asignación, por ejemplo, la manera como implante archivos grandes puede afectar el desempeño del sistema de archivos

• Direcciones

• La asignación consiste en completar los puntos 1, 2, y 3. Los puntos 4, 5 y 6 son opcionales
1. Complete el sistema de archivos básico agregando sincronización a fin de permitir que múltiples hilos puedan utilizarlo concurrentemente. Por ahora el sistema provisto supone que solo va a ser accedido por un único hilo a la vez. Adicionalmente para asegurar que las estructuras de datos no se vuelvan inconsistentes, el sistema de archivos modificado debe incluir las siguientes restricciones:
• El mismo archivo puede ser leído y escrito por distintos hilos concurrentemente. Cada hilo abre el archivo de manera independiente, se le asigna su propio puntero para la posición actual del archivo. Por lo tanto, dos hilos pueden leer secuencialmente el mismo archivo sin interferir entre sí
• Todas las operaciones deben ser atómicas y serializables. Por ejemplo, si un hilo está en medio de una escritura a un archivo, otro hilo que concurrentemente lee el mismo archivo verá todos los cambios realizados en él por la escritura o ninguno, esdecir, los datos tal y como estaban antes de que el hilo que escribe haya comenzado suoperacion
• Cuando un hilo borra un archivo, los otros hilos que tengan ese archivo abierto pueden seguir leyendo y escribiendo en él hasta que lo cierren. Borrar un archivo (FileSystem::Remove) debe evitar las siguientes aperturas a ese archivo, pero los bloques del disco que ocupa ese archivo solo pueden recuperarse hasta que el archivo haya sido cerrado por todos los hilos que lo habían abierto
• Sugerencia: para esta parte puede ser importante mantener una tabla de archivos abiertos
• Revise los archivos "openfile.h" y "openfile.c" y la definición de la clase "Openfile"
2. Modifique el sistema de archivos de manera que permita que el tamaño máximo de un archivo sea tan grande como el disco (128 Kb). En el sistema de archivos básico, cada archivo está limitado a un tamaño de solo 4 Kb. Cada archivo tiene un encabezado (clase "FileHeader") que es una tabla de punteros directos a sus bloques de datos en el disco. Como este encabezado está almacenado en un sector del disco, el tamaño máximo del archivo está limitado a la cantidad de punteros que caben en un sector del disco. Incrementar el tamaño a 128 Kb puede requerir del uso de punteros doblemente indirectos o cualquier otra de las técnicas que se estudiaron
3. Implante archivos extendibles dinámicamente. En el sistema de archivos básico, el tamaño del archivo se indica cuando el archivo es creado. Una ventaja de ésto es que una vez que se crea la estructura del "FileHeader", no se cambia nunca más. En la mayoría de los sistemas de archivos, un archivo es creado inicialmente con tamaño 0 y luego es expandido cada vez que se hace una escritura en él. Modifique el sistema de archivos para permitir esto; como un caso de prueba, permita que el archivo que contiene la información del directorio pueda crecer más allá de su límite actual de diez archivos. Tome en cuenta que el acceso a las estructuras de datos debe estar correctamente sincronizado
4. Mejore el desempeño del sistema de archivos. Recompile Nachos utilizando la bandera REALISM (-DREALISM) utilícelo como una métrica para el número de pulsos (ticks) necesarios para correr (i) el caso de prueba (nachos -t), que escribe y luego lee en secuencia un archivo grande, y (ii) como prueba del sistema de memoria virtual de la asignación 3 (utilizando el sistema de archivos de Nachos y no el de Unix)
• Se presentan un par de sugerencias que puede utilizar para mejorar el rendimiento:
• Optimizar el posicionamiento de las cabezas (seek time) y la latencia de rotación. Para leer o escribir en un sector, las cabezas del disco deben colocarse sobre la pista adecuada (seek time) y luego el sistema debe esperar hasta que el sector correcto pase por las cabezas (latencia de rotación). En sistemas donde el acceso al disco es crítico, esto puede ser causa de un desempeño pobre. Estos problemas pueden ser corregidos (i) tratando de colocar los bloques de datos de un archivo sobre la misma pista y (ii) cuando hay varias solicitudes encoladas, se pueden escoger aquellas que tengan el retraso menor primero (SSTF), pero evitando, al mismo tiempo, tener problemas de inanición con algunas solicitudes
• Modificar el sistema de archivos para mantener en memoria los bloques de los datos de los archivos (cache). Cuando se hace una solicitud para leer un bloque, verificar primero si el bloque está en la cache, si es así, no se necesita ningún acceso al disco y el bloque se puede regresar inmediatamente. Otra mejora es que en lugar de siempre escribir los datos modificados al disco, estos bloques sucios se pueden mantener en la memoria cache y más tarde ser escritos en el disco, esto se conoce como escritura atrasada (write-behind). Otra mejora es automáticamente leer el siguiente bloque de un archivo en la cache, cuando se solicita un bloque de ese archivo, en caso de que este otro bloque pueda ser utilizado en el futuro, esta técnica se conoce como lectura adelantada (read-ahead)
• En cuanto al desempeño, se deben permitir actualizaciones concurrentes a diferentes directorios, pero utilice las técnicas de concurrencia para realizar las actualizaciones del mismo directorio (por ejemplo, para asegurarse de que un archivo sea borrado solo una vez)
5. Implante un espacio de nombres jerárquico. En el sistema de archivos básico todos los archivos están en un solo directorio; haga los cambios necesarios para permitir que las entradas del directorio apunten a archivos o a otros directorios. Para ello se necesitan rutinas para interpretar la ruta del nombre de los archivos en la secuencia de directorios donde se encuentra el archivo. También es necesario implantar rutinas para cambiar el directorio de trabajo actual (ver el comando cd de Unix) y para desplegar el contenido del directorio actual
• El tamaño del cache a utilizar está limitado a 64 sectores del disco (aproximadamente un 6% del tamaño del disco); este límite de espacio incluye la memoria necesaria para los archivos abiertos, el bitmap, etc., si se mantienen en memoria principal
• Para cada una que usted implante, explique cuáles son las mejoras de desempeño obtenidas en los casos de prueba y por qué las otras alternativas (las que no implantó) no representan ganancia
6. Extra puntos (10%) El disco de Nachos se puede corromper si el sistema no termina correctamente (por ejemplo, después de una caída debido a un problema del software o si se termina el debugger (gdb) sin finalizar el programa). Esto es por que algunas operaciones del sistema de archivos requieren más de una operación de escritura en el disco físico. Por ejemplo, cuando se crea un nuevo archivo es necesario crear un nuevo encabezado (FileHeader) de archivo en el disco, actualizar el directorio y el mapa de bits de los bloques libres. Si el sistema colapsa después de haber realizado solo una parte de todas esas actualizaciones, el disco puede quedar en estado inconsistente. Para obtener estos puntos extra, diseñe su sistema de archivos de manera confiable
• Este problema se puede manejar de dos formas diferentes. Una manera es llevar el registro de cada vez que se comienza y termina una secuencia de escrituras atómicas. Otra manera es estructurar el sistema de archivos de tal manera que cada actualización se efectúe escribiendo sólo un bloque del disco. Por ejemplo, para modificar un archivo, se pueden escribir los datos en un nuevo bloque del disco, cambiar el encabezado del archivo para que apunte a este bloque, y por último recuperar el bloque viejo del archivo para colocarlo en la lista de libres. Note que la lista de libres puede ser redundante; se debe ser capaz de reconstruirla luego de una caída de otras partes del disco
• A manera de ayuda, se puede suponer (algo no muy realístico) que las caídas ocurren ya sea antes o después, pero no durante las escrituras en el disco. En otras palabras, un sector del disco va a tener los valores viejos o los nuevos, pero no una parte de cada uno
• Para esta parte, se puede probar el sistema botándolo en un punto totalmente inoportuno, por ejemplo, en medio de la actualización del directorio, luego tratar de construir el disco