From 088c62b17f5b04891f9b5fd4a682670b88143b99 Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Mon, 19 Apr 2004 02:18:29 +0000 Subject: [PATCH] Chapter 5, Tipo2 uploaded y terminado al menos por ahora --- doc/informe.lyx | 444 +++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 435 insertions(+), 9 deletions(-) diff --git a/doc/informe.lyx b/doc/informe.lyx index adaf456..5f84015 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -813,7 +813,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAME!!!! +Organización física de los registros en disco \layout Standard @@ -831,19 +831,321 @@ NOMBRE, ARREGLAME!!!! Como se puede observar, a nivel físico cada registro grabado esta compuesto por un Header cuyo tamaño total es de 8 bytes ( -\family typewriter \series bold EMUFS_REG_ID \series default + \series bold EMUFS_REG_SIZE -\family default \series default ), y posteriormente el registro (bloque de datos) en sí. Luego se encuentra el espacio libre de 18 bytes dejado por el registro de 10 bytes eliminado (10 bytes de datos + header de 8 bytes) y finalmente el segundo registro mencionado.dsds +\layout Subsection + +Comportamiento Particular de los Archivos Auxiliares +\layout Standard + +Como fue explicado al inicio de la documentación, la implementación de cualquier +a de las tres organizaciones físicas de archivos presenta la necesidad de + poseer tres archivos auxiliares que actuarán como índice de direcciones + de registro (. +\series bold +idx +\series default +), administrador de espacio libre ( +\series bold +.fsc +\series default +) y administrador de Id's liberados ( +\series bold +.did +\series default +) respectivamente. +\layout Standard + +No obstante, cada tipo de organización presentara sus particularidades respecto + de estos tres archivos, las cuales describiremos a continuación en caso + de haberla. +\layout Subsubsection + +Archivo índice o de posiciones relativas (.idx) +\layout Standard + +El archivo indice ( +\series bold +.idx +\series default +), permite la localizacin de los registros en el .DAT de forma directa, mediante + la obtención de su offset o posición relativa respecto del inicio del +\series bold +.dat +\series default + en donde se encuentra un registro dado, indicado por su ID. +\layout Standard + +Así pues, si tomamos el ejemplo descripto al inicio de este capítudlo, tendremos + las siguientes entradas en el archivo indice +\series bold +.idx +\series default + : +\newline + +\layout Standard + + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + + +\emph on +ID_REGISTRO +\end_inset + + +\begin_inset Text + +\layout Standard + + +\emph on +OFFSET +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\series bold +0 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +4 +\end_inset + + +\begin_inset Text + +\layout Standard + +El primer registro (reg0) comienza en el byte 4 +\end_inset + + + + +\begin_inset Text + +\layout Standard + +1 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +60 +\end_inset + + +\begin_inset Text + +\layout Standard + +El segundo registro (reg1) comienza en el byte 60 +\end_inset + + + + +\end_inset + + +\layout Standard + + +\series bold +\emph on +\SpecialChar ~ + +\newline +Observación: +\series default +\emph default + LOCATION indica donde comienza el header del registro buscado, y por consiguien +te luego del header tendremos el registro en sí (los datos). +\layout Subsubsection + +Achivo de Gaps / Espacios Libres (.fsc) +\layout Standard + +El archivo de espacios libres o gaps (.fsc), tiene como función la administracion + del espacio libre o gaps (agujeros), generados por previas eliminaciones + de registros en el archivo de datos. + El mismo, nos indicará donde hay lugar para insertar un nuevo registro + (se podrán insertar en algún gap acorde, o bien al final del archivo). + Este archivo será utilizado tambien para el proceso de compactación de + un archivo, explicado luego. +\layout Standard + +Así pues, si tomamos el ejemplo descripto al inicio del documento, tendremos + las siguientes entradas en el archivo índice +\series bold +.fsc +\series default + : +\newline + +\newline + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + + +\emph on +OFFSET +\end_inset + + +\begin_inset Text + +\layout Standard + + +\emph on +FREESPACE +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\series bold +42 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +18 +\end_inset + + +\begin_inset Text + +\layout Standard + +18 bytes libres a partir del byte 42 del .dat +\end_inset + + + + +\end_inset + + +\layout Standard + + +\series bold +\emph on +\SpecialChar ~ + +\newline +Nota: +\series default +\emph default + Por requerimiento del algoritmo de compactación, los gaps se graban en + forma ordenada en el (.fsc). + (El orden se corresponde con lo que hay en el .dat) +\layout Subsubsection* + +GAP Merging +\layout Standard + +Si bien la utilización concreta de los GAPS será explicada posteriormente + en la ALTA y BAJA de registros, debemos remarcar la funcionalidad de MERGING + que posee nuestro sistema FSC. +\layout Standard + +Ante la eliminación de un registro del archivo de datos, se generara por + consiguiente un gap o espacio libre en alguna posición del archivo. + Ese gap deberá ser registrado en el archivo de gaps (.fsc). + Ahora bien, nuestro sistema de gaps, contemplará como es debido, la posibilidad + de que se haya eliminado un registro que posee un GAP por delante, un GAP + por detrás, o bien un GAP por delante y por detrás del mismo. +\layout Standard + +Nuestro sistema actuará en consecuencia, realizando un merge de los espacios + libres, y unificándolos en una UNICA entrada en el archivo .fsc, que contendrá + como dato de freespace, la suma correspondiente de los espacios libres + antes mencionados. +\layout Subsubsection + +Archivo de ID's liberados (.did) +\layout Standard + +El archivo de ID's liberados no presenta ningún aspecto particular en este + tipo de organización. + Remitirse al capítulo correspondiente a los archivos auxiliares para consultar + su estructura y funcionamiento. \layout Section Comportamiento (funciones de la interfaz) @@ -906,6 +1208,11 @@ RegSize ). Contando así con el tamaño del registro, procedemos a leer el mismo (los datos), dando por finalizada la lectura. +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_leer_registro() \layout Subsection Altas de registros @@ -932,16 +1239,12 @@ As \layout Enumerate Calculamos el espacio que necesitaremos para el registro: sizeof( -\family typewriter \series bold EMUFS_REG_ID -\family default \series default ) + sizeof( -\family typewriter \series bold EMUFS_REG_SIZE -\family default \series default ) + sizeof(registro). \layout Enumerate @@ -976,6 +1279,11 @@ Actualizamos la entrada correspondiente al registro ingresado (determinada .idx \series default ), indicando su offset donde podrá ser accedido luego. +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_agregar_registro() \layout Subsection Bajas de registros @@ -1056,6 +1364,11 @@ Se marca en el archivo ) la eliminación, mediante el valor ¨-1¨ en el registro correspondiente al registro recién eliminado (se le cambia el valor al n-esimo registro, donde N = IDReg del reg eliminado). +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_borrar_registro() \layout Subsection Modificación de registros @@ -1084,9 +1397,34 @@ NOTA: Como fue indicado, dada la naturaleza de PILA del subsistema de administración de ID liberados, es asegurado que la nueva inserción del registro modificado se realizará con el mismo RegID. +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_modificar_registro() \layout Subsection Obtención de estadísticas +\layout Standard + +Se puede tener acceso a las estadísticas generales del archivo, por ejemplo, + cantidad de bloques, cantidad de registros, espacio libre total, espacio + libre promedio, espacio libre máximo y mínimo, etc. +\layout Standard + +Esta información es el resultado de ciertos cálculos realizados tanto en + el archivo de datos como en los archivos índice. +\layout Standard + +Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas + del archivo de datos, espacio libre total, cantidad de registros, cantidad + de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios + libres, etc. +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_leer_estadisticas() \layout Subsection Compactación del archivo de datos @@ -1118,7 +1456,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAMEE!!! +Archivo con gaps entre registros previo a compactación \layout Standard @@ -1264,7 +1602,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAME!!!! +Archivo con gaps en disco luego del primer bucle de compactación \layout Standard @@ -1317,6 +1655,94 @@ Mustmove_bytes = Datsize - Source Damos por terminada así, la explicación del algoritmo de compresión el cual para el caso del tipo 2, es realmente bastante sencillo. +\layout Standard + +Ver: +\family typewriter +void emufs_tipo2_compactar() +\layout Section + +Consideraciones y Políticas de Diseño +\layout Standard + +Se han tomado ciertas consideraciones para algunos casos particulares que + se pueden presentar durante el uso/ejecución de la aplicación, así como + tambien politicas respecto del diseño e implementación del sistema: +\layout Itemize + +En la organización física tipo 2 para los registros que se graban en disco + hemos decidido utilizar como encabezado de cada uno de ellos, los datos + [ID_REG][REG_SIZE], los cuales fueron detallados previamente. + Si bien se podría haber descartado el grabado del ID del registro en el + archivo de datos y puede parecer redundante, dado que poseemos el archivo + índice con el offset directo, el mismo se lo graba por distintos motivos: +\newline + +\newline +A) En caso de la corrupción del archivo índice (.idx), podremos gracias a + que poseemos en el archivo de datos, el ID de cada registro, recrear dicho + índice, ayudándonos del archivo de espacios libres ( +\series bold +.fsc +\series default +), para poder saltear los espacios libres y e ir recorriendo secuencialmente + los registros, reconstruyendo así el índice en cuestión. + (esta función de reconstrucción no pudo ser implementada para esta entrega, + pero es una posibilidad real). +\newline + +\newline +B) Luego de un proceso de recompactación, los espacios libres que pudieron + haber existido en el archivo de datos ( +\series bold +.dat +\series default +), son eliminados y los registros han cambiado de posición. + Por ello, recorriendo secuencialmente por única vez el archivo de datos, + se procede a la actualización / reconstrucción del índice de direcciones + u offsets (. +\series bold +idx +\series default +) +\layout Itemize + +Si se desea insertar un registro y no se puede hayar un gap o espacio libre + donde quepa, se los inserta al final del archivo. +\layout Itemize + +Ante una operación de baja de un registro, el mismo no es físicamente borrado + del archivo de datos ( +\series bold +.dat +\series default +), simplemente los bytes que ocupa son llenados con hexa (00). + Paralelamente, se procede a actualiza el archivo índice, insertando como + valor de OFFSET para el registro eliminado, el valor ¨-1¨, indicando así + la inexistencia del registro para el futuro, y por otro lado se genera + la entrada de espacio libre en el archivo de gaps ( +\series bold +.fsc +\series default +). +\layout Itemize + +La reutilización de ID's liberados por previas operaciones de baja de registros, + se ve implementada por el archivo de ID liberados (.did), y su comportamiento + es el de una pila por lo que el último ID liberado, sera el próximo a ser + reutilizado (LIFO). +\layout Itemize + +Como fue explicado en la implementación del archivo índice, existe una correspon +dencia 1 a 1 entre los registros allí presentes (en el .idx) y los ID's de + los registros, por lo cual el registro N-ésimo del archivo índice, será + el correspondiente al registro de datos cuyo ID es igual a N. +\layout Itemize + +El proceso de compactación de archivos, realiza los movimientos de información + requeridos para dicho propósito de a chunks de 25 bytes por vez. + Este valor es fijo, pero se lo podría hacer parametrizable mediante la + GUI en próximas entregas. \layout Chapter -- 2.43.0