Chapter 5, Tipo2 uploaded y terminado al menos por ahora

[z.facultad/75.06/emufs.git] / doc / informe.lyx

diff --git a/doc/informe.lyx b/doc/informe.lyx
index adaf45663e90b8fd25c789b7580bfbc24c286e9a..5f84015c46e702426b2d07003d2041b382deb90a 100644 (file)
--- a/doc/informe.lyx
+++ b/doc/informe.lyx
@@ -813,7 +813,7 @@ collapsed true
 
 \layout Caption
 
 
 \layout Caption
 

-NOMBRE, ARREGLAME!!!!
+Organización física de los registros en disco

 \layout Standard
 
 
 \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 (
 
 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
 \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
 \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
+<lyxtabular version="3" rows="3" columns="3">
+<features>
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on 
+ID_REGISTRO
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on 
+OFFSET
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+\end_inset 
+</cell>
+</row>
+<row topline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+0
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+4
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+El primer registro (reg0) comienza en el byte 4
+\end_inset 
+</cell>
+</row>
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+1
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+60
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+El segundo registro (reg1) comienza en el byte 60
+\end_inset 
+</cell>
+</row>
+</lyxtabular>
+
+\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
+<lyxtabular version="3" rows="2" columns="3">
+<features>
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on 
+OFFSET
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on 
+FREESPACE
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+\end_inset 
+</cell>
+</row>
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+42
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+18
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+18 bytes libres a partir del byte 42 del .dat
+\end_inset 
+</cell>
+</row>
+</lyxtabular>
+
+\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)
 \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.
 ).
  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
 \layout Subsection
 
 Altas de registros


@@ -932,16 +1239,12 @@ As
 \layout Enumerate
 
 Calculamos el espacio que necesitaremos para el registro: sizeof(
 \layout Enumerate
 
 Calculamos el espacio que necesitaremos para el registro: sizeof(

-\family typewriter 

 \series bold 
 EMUFS_REG_ID
 \series bold 
 EMUFS_REG_ID

-\family default 

 \series default 
 ) + sizeof(
 \series default 
 ) + sizeof(

-\family typewriter 

 \series bold 
 EMUFS_REG_SIZE
 \series bold 
 EMUFS_REG_SIZE

-\family default 

 \series default 
 ) + sizeof(registro).
 \layout Enumerate
 \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.
 .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
 \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).
 ) 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
 \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.
  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 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
 \layout Subsection
 
 Compactación del archivo de datos


@@ -1118,7 +1456,7 @@ collapsed true
 
 \layout Caption
 
 
 \layout Caption
 

-NOMBRE, ARREGLAMEE!!!
+Archivo con gaps entre registros previo a compactación

 \layout Standard
 
 
 \layout Standard
 
 


@@ -1264,7 +1602,7 @@ collapsed true
 
 \layout Caption
 
 
 \layout Caption
 

-NOMBRE, ARREGLAME!!!!
+Archivo con gaps en disco luego del primer bucle de compactación

 \layout Standard
 
 
 \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.
 
 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
 
 
 \layout Chapter