X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/dc1d6d2ce387d0563612e569d4ff6e16dbc332e7..cd61d59673e28422ae9940d985868d436a75eed3:/doc/informe.lyx?ds=sidebyside diff --git a/doc/informe.lyx b/doc/informe.lyx index 1084ef8..7139768 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -43,6 +43,53 @@ Ricardo Markiewicz \layout Chapter Introducción +\layout Standard + +Esta es la documentación correspondiente a las API`s para el manejo de tres + organizaciones de archivo diferentes. + A continuación se describe cada una de ellas y su modo de funcionamiento + y sus características principales. + De la correcta elección de la organización, dependerá la eficiencia de + la aplicación que la utilice. + +\layout Standard + +EMUFS se presenta como un +\emph on +emulador +\emph default + de un +\emph on +filesystem +\emph default +, capaz de administrar datos almacenados en cualquiera de las tres organizacione +s de archivo previamente mencionadas, las cuales a saberse son: +\layout Enumerate + +Registros de Longitud Variable, Bloques de tamaño parametrizable +\layout Enumerate + +Registros de Longitud Variable, Sin Bloques +\layout Enumerate + +Registros de Longitud Fija, Bloques de tamaño parametrizables +\layout Standard + +A través de este trabajo, se podrán observar las diferencias entre distintos + tipos de organización de archivos, ventajas y desventajas de cada una de + ellas, y las situaciones particulares que deberá sortear un filesystem, + como la partición de registros en distintos bloques, manejo de espacio + libre, compactación de un archivo, etc. +\layout Standard + +A continuación, veremos que el manejo de los archivos en EMUFS se realiza + a través de una estructura de control comun para cualquier tipo de archivo, + dandole flexibilidad y escalabilidad a nuestro sistema. +\layout Standard + +Hacia el final de esta presentación, se observaran las pruebas realizadas + con las distintas organizaciones de archivos, y las conclusiones obtenidos + al respecto. \layout Chapter Estructura común @@ -62,6 +109,73 @@ EMUFS prooverá una interfaz (funciones) para su manejo). \layout Subsection +Tipos Comunes +\layout Standard + +En la implementación de cada tipo de organización física, así como tambien + en las API de los archivos auxiliares comunes a ellas, se da la utilización + de tipo definidos para una clara interfaz entre las mismas, los cuales + son brevemente descriptos a continuación y pueden ser hallados en el archivo + +\series bold +emufs.h +\series default +: +\layout Itemize + + +\family typewriter +EMUFS_REG_ID +\family default +: usado para representar un +\emph on +Id +\emph default + de un registro. +\layout Itemize + + +\family typewriter +EMUFS_REG_SIZE +\family default +: usado para representar el tamaño en bytes de un registro. +\layout Itemize + + +\family typewriter +EMUFS_BLOCK_ID +\family default +: usado para representar un número de bloque. +\layout Itemize + + +\family typewriter +EMUFS_BLOCK_SIZE +\family default +: usado para representar el tamaño en bytes de un bloque. +\layout Itemize + + +\family typewriter +EMUFS_FREE +\family default +: usado para representar espacio libre en bytes. +\layout Itemize + + +\family typewriter +EMUFS_OFFSET +\family default +: usado para representar un offset. +\layout Standard + +Todos son del tipo +\family typewriter +unsigned long +\family default +. +\layout Subsection + EMUFS \layout Standard @@ -194,10 +308,12 @@ facturas \begin_inset Quotes erd \end_inset - organizado de la forma 3, se invoca a la función + organizado de la forma 3, se invoca a la función: +\layout Standard + + \family typewriter -EMUFS *emufs_crear(const char *filename, EMUFS_Tipo tipo,EMUFS_BLOCK_SIZE - tam_bloque, EMUFS_REG_SIZE tam_reg), +emufs_crear(filename,tipo,tam_bloque,tam_reg), \family default donde \family typewriter @@ -256,15 +372,27 @@ emufs.h. A saberse los valores y significado correspondiente que puede tomar este tipo de dato son: -\layout Enumerate +\layout Itemize -Archivos con registros de longitud variable y bloques parametrizables. -\layout Enumerate -Archivos con registros de longitud variable sin bloques. -\layout Enumerate +\series bold +T1 +\series default + : Archivos con registros de longitud variable y bloques parametrizables. +\layout Itemize + -Archivos con registros de longitud fija y bloques parametrizables. +\series bold +T2 +\series default + : Archivos con registros de longitud variable sin bloques. +\layout Itemize + + +\series bold +T3 +\series default + : Archivos con registros de longitud fija y bloques parametrizables. \layout Subsection EMUFS_Estadisticas @@ -290,60 +418,91 @@ y la misma cuenta con los siguiente campos: \family typewriter unsigned long \family default - tam_archivo: indica el tamaño del archivo de datos (.dat) en bytes. + +\family typewriter +tam_archivo +\family default +: indica el tamaño del archivo de datos (.dat) en bytes. \layout Itemize \family typewriter unsigned long \family default - tam_archivos_aux: indica el tamaño de los archivos auxiliares sumados en - bytes. + +\family typewriter +tam_archivos_aux +\family default +: indica el tamaño de los archivos auxiliares sumados en bytes. \layout Itemize \family typewriter unsigned long \family default - tam_info_control_dat: indica la cantidad de bytes en información de control - utilizados para el archivo. + +\family typewriter +tam_info_control_dat +\family default +: indica la cantidad de bytes en información de control utilizados para + el archivo. \layout Itemize \family typewriter unsigned long \family default - media_fs: promedio de espacio libre en el archivo de datos (por bloque - o gap promedio segun la org) + +\family typewriter +media_fs +\family default +: promedio de espacio libre en el archivo de datos (por bloque o gap promedio + segun la org) \layout Itemize \family typewriter unsigned long \family default - total_fs: total de espacio libre en el archivo de datos. + +\family typewriter +total_fs +\family default +: total de espacio libre en el archivo de datos. \layout Itemize \family typewriter unsigned long \family default - max_fs: máximo espacio libre en el archivo de datos (en un bloque o máximo - gap segun la org). + +\family typewriter +max_fs +\family default +: máximo espacio libre en el archivo de datos (en un bloque o máximo gap + segun la org). \layout Itemize \family typewriter unsigned long \family default - min_fs: idem pero mínimo. + +\family typewriter +min_fs +\family default +: idem pero mínimo. \layout Itemize \family typewriter unsigned long \family default - cant_bloques: cantidad de bloques en el archivo de datos (. + +\family typewriter +cant_bloques +\family default +: cantidad de bloques en el archivo de datos (. \series bold dat \series default @@ -354,7 +513,11 @@ dat \family typewriter unsigned long \family default - cant_registros: cantidad de registros en el archivo de datos ( + +\family typewriter +cant_registros +\family default +: cantidad de registros en el archivo de datos ( \series bold .dat \series default @@ -362,7 +525,7 @@ unsigned long \layout Standard En base a la estructura descripta anteriormente y mediante la utilización - de la función + de la función de lectura de estadísticas l \family typewriter emufs_leer_estadisticas() \family default @@ -395,73 +558,6 @@ Cantidad promedio de espacio libre (en bloque o gap promedio) Desviaciones extremas de espacio libre (máximo/mínimo espacio libre en bloque o mayor/menor gap) -\layout Subsection - -Tipos Comunes -\layout Standard - -En la implementación de cada tipo de organización física, así como tambien - en las API de los archivos auxiliares comunes a ellas, se da la utilización - de tipo definidos para una clara interfaz entre las mismas, los cuales - son brevemente descriptos a continuación y pueden ser hallados en el archivo - -\series bold -emufs.h -\series default -: -\layout Itemize - - -\family typewriter -EMUFS_REG_ID -\family default -: usado para representar un -\emph on -Id -\emph default - de un registro. -\layout Itemize - - -\family typewriter -EMUFS_REG_SIZE -\family default -: usado para representar el tamaño en bytes de un registro. -\layout Itemize - - -\family typewriter -EMUFS_BLOCK_ID -\family default -: usado para representar un número de bloque. -\layout Itemize - - -\family typewriter -EMUFS_BLOCK_SIZE -\family default -: usado para representar el tamaño en bytes de un bloque. -\layout Itemize - - -\family typewriter -EMUFS_FREE -\family default -: usado para representar espacio libre en bytes. -\layout Itemize - - -\family typewriter -EMUFS_OFFSET -\family default -: usado para representar un offset. -\layout Standard - -Todos son del tipo -\family typewriter -unsigned long -\family default -. \layout Section @@ -558,6 +654,133 @@ archivo \layout LyX-Code /- 4 bytes -/ +\layout Section + +Uso de la estructura EMUFS +\layout Standard + +Como fue mencionado anteriormente en la descripción de la estructura EMUFS, + la misma proporciona al usuario una interfaz a través de la cual puede + realizar el manejo de archivos en forma genérica, abstrayéndose del tipo + de organización física en particular que dicho archivo posea. + Se la declara en +\series bold +emufs.h +\series default + y las funciones que inicializan la estructura se encuentran en +\series bold +emufs.c +\layout Standard + +Es decir que a traves de esta estructura, podemos manejar cualquier tipo + de archivo, mediante una misma interfaz en común. + La estructura +\family typewriter +EMUFS +\family default +posee además de ciertos datos que describen la organización física de un + archivo dado como por ejemplo +\series bold +\emph on +tamaño de registro +\series default +\emph default +, +\series bold +\emph on +tamaño de bloque +\series default +\emph default + y +\series bold +\emph on +nombre del archivo +\series default +\emph default +, una serie de punteros a funciones para el manejo del archivo del cual + es handler: +\layout Standard + +Entre dichos funciones se encuentran: +\family typewriter +leer_registro() +\family default +, +\family typewriter +leer_bloque(), borrar_registro() +\family default +, +\family typewriter +agregar_registro() +\family default +, +\family typewriter +modificar_registro, leer_estadisticas() +\family default +, +\family typewriter +compactar(). +\layout Standard + +Para entender mejor el uso de esta estructura para el manejo de los archivos, + mostraremos un ejemplo concreto. + Supongamos que tenemos el siguiente código: +\layout LyX-Code + +EMUFS *efs = emufs_crear(¨articulos.dat¨,T3,200,50); +\layout Standard + +Esto hará que se cree el archivo de datos +\series bold +articulos.dat +\series default +, con la organización física tipo 3 con registros de longitud fija de 50 + bytes y bloques de 200 bytes. + Al mismo tiempo, los se asginarán valores a los punteros a funciones que + posee dicha estructura, la cual de ahora en más estará en condiciones de + manejar un archivo del tipo 3. + Gráficamente lo que sucede es: +\layout Standard + + +\begin_inset Float figure +placement H +wide false +collapsed true + +\layout Caption + +Inicialización de estructura EMUFS para un caso Archivo Tipo 3 +\layout Standard +\align center + +\begin_inset Graphics + filename graphics/Emufsinit.png + scale 75 + keepAspectRatio + +\end_inset + + +\end_inset + + +\layout Standard + +Así pues, cuando se utilize la estructura para por ejemplo leer un registro, + sucedera lo siguiente: +\layout LyX-Code + +efs->leer_registro(params) -- calls --> emufs_tipo3_leer_registro(params) +\layout Standard + +Como se puede observar, la estructura +\family typewriter +EMUFS +\family default + permitirá el manejo de cualquier tipo de archivo, a través del mismo código, + dandole gran flexibilidad a nuestro sistema, que podrá expandirse a más + tipos de archivos de ser necesario. \layout Chapter Archivos Auxiliares @@ -641,12 +864,6 @@ EMUFS_IDX ): \layout LyX-Code -typedef unsigned long EMUFS_REG_ID; -\layout LyX-Code - -typedef unsigned long EMUFS_OFFSET; -\layout LyX-Code - typedef struct emufs_idx_t { \layout LyX-Code @@ -872,22 +1089,22 @@ id_reg .dat \series default ). -\newline - \series bold + +\newline NOTA: \series default Cabe aclarar que por si bien el indice se encuentra ordenado por \family typewriter id_reg \family default -, los registros en el archivo de datos, por lo general no lo estarán. - (ordenados por id). +, los registros en el archivo de datos, por lo general no lo estarán (ordenados + por id). \newline Ver: \family typewriter -emufs_idx_buscar_registro() +emufs_idx_buscar_registro(), emufs_idx_get() \layout List \labelwidthstring 00.00.0000 @@ -910,9 +1127,13 @@ emufs_idx_agregar() Baja: \series default Ante el borrado de un registro del archivo de datos, se accederá el registro - correspondiente en el índice, y se actualizara su LOCATION, estableciendolo - en el valor -1 UL, el cual indica que ese registro ha sido eliminado y - por ende no se lo podrá localizar en el futuro. + correspondiente en el índice, y se actualizara su LOCATION, estableciendolo + en el valor especial +\family typewriter +EMUFS_NOT_FOUND +\family default +, el cual indica que ese registro ha sido eliminado y por ende no se lo + podrá localizar en el futuro. Como se verá mas adelante, según el tipo de organización física, el registro puede ser borrado concretamente del . \series bold @@ -997,10 +1218,10 @@ EMUFS_FSC typedef struct emufs_fsc_t { \layout LyX-Code - unsigned long int marker; + EMUFS_BLOCK_ID marker; \layout LyX-Code - unsigned long int freespace; + EMUFS_FREE freespace; \layout LyX-Code } EMUFS_FSC; @@ -1209,17 +1430,27 @@ B \family typewriter nro_bloque \family default - se posee espacio suficiente para albergar el nuevo registro. + se posee espacio suficiente para albergar el nuevo registro (o a partir + de qué +\family typewriter +nro_bloque +\family default + se encuentran +\family typewriter +N +\family default + bloques consecutivos libres). En el caso de organizacion sin bloque, se buscará un gap o espacio libre en el archivo, obteniéndose en consecuencia, el \family typewriter offset \family default hasta el mismo. + \newline Ver: \family typewriter -emufs_fsc_buscar_lugar() +emufs_fsc_buscar_lugar(), emufs_fsc_buscar_n_lugares() \layout List \labelwidthstring 00.00.0000 @@ -1510,7 +1741,7 @@ archivo +-----------+-----------+------------------------//-+ \layout LyX-Code -| tipo | tam bloque| Cero o más bloques ... +| tipo | tam_bloque| Cero o más bloques ... \backslash @@ -1622,7 +1853,7 @@ tama Podemos ver gráficamente como se se compone un registro: \layout LyX-Code -registro id +registro [id] \layout LyX-Code +-----------+-----------+------------------+ @@ -1741,7 +1972,7 @@ A continuaci \begin_inset Quotes erd \end_inset -) almacenado en un archivo con bloques de 4 bytes: +) almacenado en un archivo con bloques de 12 bytes (4 para datos): \layout LyX-Code | bloque 0 | bloque 1 | bloque 2 @@ -1785,6 +2016,20 @@ A continuaci \backslash -+ +\layout LyX-Code + + ^^ +\layout LyX-Code + + 2 bytes libres al final del bloque 2 +\layout Standard + +Este es un ejemplo figurativo, ya que se puso como límite mínimo de tamaño + de bloque 16 bytes (para que haya al menos la misma cantidad de espacio + para datos que para información de control). + Este límite mínimo ya roza lo absurdo (es muy ineficiente por la gran cantidad + de accesos a disco que necesita). + El límite físico es de 9 bytes (8 para información de control, 1 para datos). \layout Section Funciones principales @@ -2166,7 +2411,7 @@ o freespace \begin_inset Float figure placement H wide false -collapsed true +collapsed false \layout Caption @@ -3167,7 +3412,32 @@ As \layout Standard El archivo estara compuesto por una cabecera que da información sobre el - tipo de organización, el tamaño de los bloques y el tamaño de los registros. + tipo (2, o el valor T3 del tipo +\family typewriter +EMUFS_Tipo +\family default + en este caso) de organización, el tamaño de los bloques y el tamaño de + los registros. +\layout LyX-Code + +archivo +\layout LyX-Code + ++-----------+-----------+-----------+------------------------//-+ +\layout LyX-Code + +| tipo | tam_bloque| tam_reg | Cero o más bloques ... + +\backslash + +\backslash + | +\layout LyX-Code + ++-----------+-----------+-----------+------------------------//-+ +\layout LyX-Code + +/- 4 bytes -/- 4 bytes -/- 4 bytes -/ \layout Subsection Organización Física de un Bloque @@ -3188,7 +3458,27 @@ virtualmente \begin_inset Quotes erd \end_inset - zonas en el archivo. + zonas en el archivo y obtener de esta manera acceso semi-aleatoreo a los + registros. +\layout LyX-Code + +bloque N-1 | bloque N | bloque N+1 +\layout LyX-Code + +/----------+------------+------------+---------------+-----------/ +\layout LyX-Code + + +\backslash + | registro 1 | registro 2 | espacio libre | +\backslash + +\layout LyX-Code + +/----------+------------+------------+---------------+-----------/ +\layout LyX-Code + + /------------- tamaño del bloque ---------/ \layout Subsection Organizacion Física de Registros @@ -3203,15 +3493,36 @@ por este motivo al realizar la busqueda de espacio en un bloque se lo har preguntando por el tamaño del registro más \family typewriter sizeof(EMUFS_REG_ID). - +\layout LyX-Code + +registro [id] +\layout LyX-Code + ++-----------+-------------------+ +\layout LyX-Code + +| id | datos ... + | +\layout LyX-Code + ++-----------+-------------------+ +\layout LyX-Code + +/- 4 bytes -/- [tam_reg] bytes -/ \layout Subsection -Organización Física de Registros Multibloque +Organización Física de Registros +\emph on +Multibloque \layout Standard Al ser los registros de longitud constante, se ha adoptado que un registro - multibloque nunca podra estar almacenado en algún lugar que no sea el comienzo - de un bloque. + +\emph on +multibloque +\emph default + nunca podrá estar almacenado en algún lugar que no sea el comienzo de un + bloque. De esta manera se puede calcular cuantos bloques ocupará un registro y se podrá solicitar lugar para almacenarlo con la ayuda de la función \family typewriter @@ -3220,19 +3531,81 @@ emufs_fsc_buscar_n_lugares(), que es muy importante para evitar el solapamiento de registros. Esta consideración acarrea como consecuencia directa un alto costo en términos del espacio desperdiciado. +\layout Standard + +A continuación se presenta un ejemplo gráfico de un registro multibloque + de 26 bytes (de contenido +\begin_inset Quotes eld +\end_inset + +12345678901234567890123456 +\begin_inset Quotes erd +\end_inset + +) almacenado en un archivo con bloques de bytes 14 bytes (10 para datos) + y registros de 38 bytes: +\layout LyX-Code + +| bloque 0 | bloque 1 | bloque 2 +\layout LyX-Code + ++-------------------+-------------------+-------------------+-//-+ +\layout LyX-Code + +| registro 0 - 1/3 | registro 0 - 2/3 | registro 0 - 3/3..| +\backslash + +\backslash + | +\layout LyX-Code + +|+----+------------+|+----+------------+|+----+--------+....| // | +\layout LyX-Code + +|| id | datos ||| id | datos ||| id | datos |....| +\backslash + +\backslash + | +\layout LyX-Code + +||----+------------+||----+------------+||----+--------+....| // | +\layout LyX-Code + +|| 0 | 1234567890 ||| 0 | 1234567890 ||| 0 | 123456 |....| +\backslash + +\backslash + | +\layout LyX-Code + +|+----+------------+|+----+------------+|+----+--------+....| // | +\layout LyX-Code + ++-------------------+-------------------+-------------------+- +\backslash + +\backslash +-+ +\layout LyX-Code + + ^^^^ +\layout LyX-Code + + 4 bytes libres (e inutilizables) al final del bloque 2 \layout Section Funciones Principales \layout Standard Dento de -\emph on +\family typewriter tipo3.h -\emph default +\family default y -\emph on +\family typewriter tipo3.c -\emph default +\family default se encuentran las cabeceras y la implementación de las funciones principales respectivamente, las cuales dan funcionalidad a esta organización. \layout Standard @@ -3240,7 +3613,7 @@ tipo3.c A continuación se comentará la descripción de algunas acciones importantes. \layout Subsection -Leer Registro +Lectura de registros \layout Standard La lectura de un registro se realiza con la ayuda del archivo . @@ -3262,7 +3635,7 @@ Ver: emufs_tipo3_leer_registro() \layout Subsection -Grabar Registro +Alta de registros \layout Standard Graba un registro en un bloque donde haya espacio suficiente, y si no crea @@ -3273,12 +3646,35 @@ Luego de grabar un registro, actualiza los archivos de para mantener la coherencia. \layout Standard +Cuando nos encontramos con registros multibloque, se calcula cuantos bloques + ocupará el registro de la siguiente manera: +\family typewriter +Cantidad de Bloques = 1 + Tamaño del Registro/(Tamaño del Bloque-Sizeof(EMUFS_RE +G_ID) +\layout Standard + +Esta ecuación solo falla en el caso que el tamaño del registro y el tamaño + del bloque sean iguales, en tal caso, se coloca el valor 1 en +\family typewriter +Cantidad de Bloques +\family default + post verificación. +\layout Standard + +Y con esta información se realiza un ciclo +\family typewriter +for +\family default + que grabará tantas veces como sea necesario levantando y grabando los bloques + que correspondan. +\layout Standard + Ver: \family typewriter emufs_tipo3_grabar_registro() \layout Subsection -Borrar Registro +Baja de registros \layout Standard Borra un registro del archivo de datos, para esto levanta el bloque al que @@ -3297,12 +3693,17 @@ Cabe destacar que para dar de baja un registro no hace falta borrarlo del ser así, si no se realizara el mismo. \layout Standard +En el caso de los registros multibloque, se eliminará la porción del registro + contenida en el primer bloque y se actualizarán de manera conveniente los + archivos índice, para restaurarlos a un valor verdadero. +\layout Standard + Ver: \family typewriter emufs_tipo3_borrar_registro() \layout Subsection -Leer Estadísticas +Obtención de estadísticas \layout Standard Se puede tener acceso a las estadísticas generales del archivo, por ejemplo, @@ -3325,7 +3726,7 @@ Ver: emufs_tipo3_leer_estadisticas() \layout Subsection -Compactar el Archivo +Compactación del archivo de datos \layout Standard Esta función intenta reorganizar el archivo de manera que el espacio libre