From: Leandro Lucarella Date: Mon, 19 Apr 2004 01:09:50 +0000 (+0000) Subject: - Agrego parte de la organizacion fisica general (fijense si tienen algo X-Git-Tag: svn_import_r684~328 X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/0f2b5ec6914f7db18a051a77160bb2496803a9ff - Agrego parte de la organizacion fisica general (fijense si tienen algo regundante es sus tipos de archivos). - Agrego un primer puchito de lo mio. - Mergeo lo de Alan. - Hago algunas correcciones de formato minimas. --- diff --git a/doc/informe.lyx b/doc/informe.lyx index b568fdc..4c38cdd 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -92,16 +92,117 @@ EMUFS_BLOCK_ID \layout Standard etc +\layout Section + + +\begin_inset LatexCommand \label{sec:cabecera_gral} + +\end_inset + +Organización física general de un archivo E +\begin_inset Formula $\mu$ +\end_inset + +FS +\layout Standard + +Todo archivo E +\begin_inset Formula $\mu$ +\end_inset + +FS está compuesto por 4 archivos a nivel de sistema operativo: archivo de + datos (con 3 formatos posibles, ver páginas +\begin_inset LatexCommand \pageref{cha:tipo1} + +\end_inset + +, +\begin_inset LatexCommand \pageref{cha:tipo2} + +\end_inset + + y +\begin_inset LatexCommand \pageref{cha:tipo3} + +\end_inset + +), archivo de índice (ver página +\begin_inset LatexCommand \pageref{sec:idx} + +\end_inset + +), archivo de control de espacio libre (ver página +\begin_inset LatexCommand \pageref{sec:fsc} + +\end_inset + +) y archivo de índices recuperables (ver página +\begin_inset LatexCommand \pageref{sec:did} + +\end_inset + +). +\layout Standard + +El archivo de datos está compuesto por: +\layout Itemize + +Una +\emph on +cabecera general +\emph default + compuesta por un +\family typewriter +int +\family default + (4 bytes en plataformas Linux de 32 bits) que representa el tipo de archivo. +\layout Itemize + +Datos dependientes del tipo de archivo. +\layout Standard + +La +\emph on +cabecera general +\emph default + es utilizada para poder detectar el formato de un archivo al abrirlo. + Los datos dependientes del tipo de archivo serán explicados en sus secciones + correspondientes. +\layout LyX-Code + +archivo +\layout LyX-Code + ++-----------+--------------------------------------------//-+ +\layout LyX-Code + +| tipo | Datos dependientes del tipo de archivo ... + +\backslash + +\backslash + | +\layout LyX-Code + ++-----------+--------------------------------------------//-+ +\layout LyX-Code + +/- 4 bytes -/ \layout Chapter Archivos Auxiliares \layout Comment -Por que los 3 tipos usan los mismo. +Por que los 3 tipos usan lo mismo. Ventajas y desventajas. \layout Section -Archivo de índice (.idx) + +\begin_inset LatexCommand \label{sec:idx} + +\end_inset + +Archivo de índice \layout Standard Con la ayuda de un archivo de bloques y registros (de extensión .idx), podremos @@ -137,7 +238,7 @@ id un registro en el archivo de datos. \layout Subsection -Estructura física +Organización física \layout Standard El tipo EMUFS_IDX define la estuctura de los registros de este archivo. @@ -167,10 +268,15 @@ ponerlo mas lindo... Comportamiento (funciones generales) \layout Section -Archivo de control de espacio libre (.fsc) + +\begin_inset LatexCommand \label{sec:fsc} + +\end_inset + +Archivo de control de espacio libre \layout Subsection -Estructura Física +Organización Física \layout Standard La estuctura que define este archivo es la siguiente: @@ -186,19 +292,159 @@ EMUFS_FREE freespace indica la cantidad de espacio libre que queda en el bloque. \layout Section -Archivo de índices recuperables (.did) + +\begin_inset LatexCommand \label{sec:did} + +\end_inset + +Archivo de índices recuperables +\layout Standard + +(.did) \layout Standard idem anterior \layout Chapter + +\begin_inset LatexCommand \label{cha:tipo1} + +\end_inset + Archivo con bloques parametrizados y registros de longitud variable \layout Standard -introduccion +Este tipo de archivo tiene varias complicaciones, al tratarse de un punto + intermedio entre el +\begin_inset LatexCommand \ref{cha:tipo2} + +\end_inset + + y el +\begin_inset LatexCommand \ref{cha:tipo3} + +\end_inset + + (cuenta tanto con bloques como con registros variables), hereda los inconvenien +tes (y ventajas) de ambos, más los propios. + Al implementar este tipo de archivo se puso enfásis en la eficiencia mientras + esta no comprometa la mantenibilidad del código, es por esto que en algunas + circunstancias no se hace un uso óptimo del espacio. +\layout Standard + +La implementación de este tipo de archivo puede ser encontrada en +\family typewriter +emufs/tipo1.c +\family default + mientras que su interfaz pública está disponible en +\family typewriter +emufs/tipo1.h +\family default +. \layout Section Organización física +\layout Standard + +El archivo está compuesto por la +\emph on +cabecera general +\emph default + (ver página +\begin_inset LatexCommand \pageref{sec:cabecera_gral} + +\end_inset + +). + El valor que toma en este tipo de archivo es 0 (o el valor simbólico +\family typewriter +T1 +\family default + del tipo +\family typewriter +EMUFS_Tipo +\family default +). + Luego le sigue una cabecera propia del archivo (un EMUFS_BLOCK_SIZE, 4 + bytes) que almacena el tamaño del bloque que usa el archivo. + De esta menera, al abrir un archivo de este tipo no se necesita tener ninguna + información sobre él. + A esta cabecera le siguen cero o más bloques del tamaño fijo especificado + en la cabecera antes mencionada. +\layout LyX-Code + +archivo +\layout LyX-Code + ++-----------+-----------+------------------------//-+ +\layout LyX-Code + +| tipo | tam bloque| Cero o más bloques ... + +\backslash + +\backslash + | +\layout LyX-Code + ++-----------+-----------+------------------------//-+ +\layout LyX-Code + +/- 4 bytes -/- 4 bytes -/ +\layout Subsection + +Organización física de un bloque +\layout Standard + +Cada bloque no guarda información en sí, sólo se comporta como un contenedor + de registros. + Esto no significa que un bloque no tenga utilidad, el bloque es utilizado + para proveer un acceso semi-aleatorio a los registros. + Para esto se utiliza el archivo de índice (ver página +\begin_inset LatexCommand \ref{sec:idx} + +\end_inset + +), que almacena pares (identificador de registro, número de bloque). + Para que sea suficiente este único índice para hallar un registro (siendo + que puede haber más de un registro por bloque), es necesario +\emph on +alinear los registros a izquierda +\emph default +. +\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 Standard + +De forma tal que una vez obtenido el número de bloque se pueda recorrer + secuencialmente hasta encontrar el registro deseado. + A fin de llevar el conteo de espacio libre se utiliza el archivo de control + de espacio libre (ver página +\begin_inset LatexCommand \ref{sec:fsc} + +\end_inset + +), de forma tal que no sea necesario recorrer secuencialmente en busca de + espacio libre al hacer una inserción. +\layout Standard + +Puede darse un caso excepcional en el que un registro sea más grande que + un bloque, en este caso el registro se almacenará en N bloques consecutivos + (siendo N la cantidad de bloques que necesita el registro), ocupando completos + los todos los bloques a excepción del último, en el que posteriormente + se pueden agregar más registros. \layout Section Comportamiento (funciones de la interfáz) @@ -207,21 +453,587 @@ Comportamiento (funciones de la interf Detalles de implementación (funciones internas, ver si lo ponemos o no) \layout Chapter + +\begin_inset LatexCommand \label{cha:tipo2} + +\end_inset + Archivo sin bloques y registros de longitud variable \layout Standard -introduccion +Este tipo de archivo nos traerá a la mesa la particularidad de grabar registros + de longitud variable sin realizar su agrupación en bloques, y como veremos + en la siguiente sección, tambien permitirá la administración de gaps que + queden en el archivo luego de operaciones de baja de registros. \layout Section Organización física -\layout Section +\layout Standard -Comportamiento (funciones de la interfáz) +Este tipo de archivo realizará el almacenamiento de registros de longitud + variable en disco, su borrado y modificación sin la utilización de bloques + de ningún tipo. + Su implementación se encuentra en los archivos fuente ( +\series bold +tipo2.c +\series default + y +\series bold +tipo2.h +\series default +). +\layout Standard + +Los archivos del tipo 2, presentarán al comienzo del mismo un header compuesto + simplemente por un dato del tipo EMUFS_Tipo (int) el cual indicará el tipo + de archivo en cuestión. +\layout Standard + +Para poder entender mejor la organización fisica de este tipo de archivo, + tomemos el caso hipotético en el que se encuentran grabados +\series bold +dos registros +\series default + (comenzando desde registro 0) de +\series bold +30 bytes +\series default +, y +\series bold +25 bytes +\series default +, respectivamente. + Supongamos también que entre el registro 0 y 1 se encontraba un +\series bold +registro de 10 bytes +\series default + que fue +\series bold +borrado +\series default +, generando un +\series bold +gap +\series default + +\series bold +o freespace +\series default +. + Si miramos al archivo de datos (.dat) en el disco nos encontraremos con + lo siguiente: +\begin_inset Float figure +placement H +wide false +collapsed true + +\layout Caption + +NOMBRE, ARREGLAME!!!! +\layout Standard + + +\begin_inset Graphics + filename graphics/Example1.png + width 100text% + +\end_inset + + +\end_inset + + +\layout Standard + +Como se puede observar, a nivel físico cada registro grabado esta compuesto + por un Header cuyo tamaño total es de 8 bytes ( +\series bold +EMUFS_REG_ID +\series default + + +\series bold +EMUFS_REG_SIZE +\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 Section -Detalles de implementación (funciones internas, ver si lo ponemos o no) +Comportamiento (funciones de la interfaz) +\layout Standard + +Dentro de +\series bold +\emph on +tipo2.h +\series default +\emph default + y +\series bold +\emph on +tipo2.c +\series default +\emph default + se encuentran las cabeceras y la implementación de las funciones principales + respectivamente, las cuales dan funcionalidad a esta organización. + +\layout Standard + +A continuación se comentará el funcionamiento algunas de las mas importantes. +\layout Subsection + +Lectura de registros +\layout Standard + +Como se vió al comienzo, los registros en este tipo de archivo no se encuentran + agrupados en bloques de ninguna índole y estan dispersos a lo largo del + archivo, con la particularidad de que pueden existir gaps o espacio libre, + entre dos registros dados. +\layout Standard + +Por ende la lectura de registros en este tipo de organización es muy simple + y dada la inexistencia de bloques, el procedimiento será el siguiente: +\layout Enumerate + +Se determina el offset en bytes, donde comienza el registro deseado, a través + de su ID, buscando la misma en el archivo índice ( +\series bold +.idx +\series default +) +\layout Enumerate + +Ya determinada la posición física del registro dentro del archivo de datos + ( +\series bold +.dat +\series default +), nos posicionamos en la misma, y leemos el header del registro ( +\series bold +IDReg +\series default + + +\series bold +RegSize +\series default +). + Contando así con el tamaño del registro, procedemos a leer el mismo (los + datos), dando por finalizada la lectura. +\layout Subsection + +Altas de registros +\layout Standard + +En el proceso de alta de registros entrarán en juego dos archivos descriptos + en la +\emph on +sección de archivos auxiliares +\emph default +, siendo estos el archivo índice ( +\series bold +.idx +\series default +), y el archivo de gaps / espacios libres ( +\series bold +.fsc +\series default +). +\layout Standard + +Así pues, a la hora de realizar una inserción de un registro en el archivo + de datos, el procedimiento será el siguiente: +\layout Enumerate + +Calculamos el espacio que necesitaremos para el registro: sizeof( +\series bold +EMUFS_REG_ID +\series default +) + sizeof( +\series bold +EMUFS_REG_SIZE +\series default +) + sizeof(registro). +\layout Enumerate + +Determinamos donde debemos insertar el registro, ya sea un gap donde entre, + o bien al final del archivo. +\layout Enumerate + +Insertamos el registro e información de control ( +\series bold +header +\series default ++ +\series bold +data +\series default +), en la posición indicada en el paso 2. +\layout Enumerate + +En caso de haber utilizado un GAP, actualizamos el espacio libre restante + en el mismo y en caso de que se haya utilizado al totalidad del GAP, se + lo elimina del archivo ( +\series bold +.fsc +\series default +). +\layout Enumerate + +Actualizamos la entrada correspondiente al registro ingresado (determinada + por su RegID), en el archivo índice ( +\series bold +.idx +\series default +), indicando su offset donde podrá ser accedido luego. +\layout Subsection + +Bajas de registros +\layout Standard + +En el proceso de baja de registros entrarán en juego los tres archivos descripto +s en la +\emph on +sección de archivos auxiliares +\emph default +, siendo estos el archivo índice ( +\series bold +.idx +\series default +), el archivo de gaps / espacios libres ( +\series bold +.fsc +\series default +) y el archivo de ID's liberados ( +\series bold +.did +\series default +). +\layout Standard + +Dado que en la implementación de este tipo de organización física contamos + con los gaps o espacios libres entre registros, no se eliminará fisicamente + el registro del archivo de datos ( +\series bold +.dat +\series default +), pues entonces carecería de sentido el archivo anteriormente mencionado + ( +\series bold +.fsc +\series default +). + En cambio, se agrega el gap dejado por la eliminación a dicho archivo, + y se marca fisicamente en el archivo de datos la eliminación mediante un + fill de los bytes correspondientes con un caracter nulo. + (hexa 00 y con el propósito de probar fehacientemente que el sistema funciona). +\layout Standard + +El proceso de baja o eliminación de un registro constará luego de los siguientes + pasos: +\layout Enumerate + +Se obtiene el offset o posición relativa en donde se encuentra grabado el + registro dentro del archivo de datos. +\layout Enumerate + +Se obtiene el tamaño del registro y se realiza un dummyfill del sector del + archivo correspondiente al registro que se está dando de baja. + (Se rellena la zona correspondiente a su header+data). +\layout Enumerate + +Se agrega el GAP generado al archivo de gaps o espacios libres, y en caso + de haberse generado un GAP lindante con otro GAP, se realizará un merge + de los mismos y se los registrará bajo una única entrada en el archivo + de espacios libres (.fsc). +\layout Enumerate + +Se agrega el ID que fue liberado, al archivo de ID's liberados ( +\series bold +.did +\series default +), al final del mismo ( +\emph on +pila +\emph default +). +\layout Enumerate + +Se marca en el archivo índice ( +\series bold +.idx +\series default +) 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 Subsection + +Modificación de registros +\layout Standard + +Dada la naturaleza del archivo de ID's liberados, y el manejo de espacio + libre del que consta esta organización de archivo, el proceso de modificación + de un registro se limita a los siguientes pasos: +\layout Enumerate + +Se realiza la lectura del registro, mediante el respectivo procedimiento + ya desarollado anteriormente. +\layout Enumerate + +Una vez que se cuenta con los nuevos datos modificados, se procede a dar + de baja el registro que ha sido modificado, e inmediatamente después se + realiza una inserción con los nuevos datos. +\layout Standard + + +\series bold +\emph on +NOTA: +\series default +\emph default + 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 Subsection + +Obtención de estadísticas +\layout Subsection + +Compactación del archivo de datos +\layout Standard + +Asi como los otros dos tipos de datos, el que nos compete también cuenta + con la posibilidad de realizar la compactación de datos cuando el usuario + lo desee, justificando todos los registros a izquierda, eliminando así + los gaps existentes y decrementando el tamaño del archivo en disco (truncandolo +). +\layout Standard + +Para poder comprender como hemos implementado el proceso de recompactación + en nuestro tipo de archivo 2, nos ayudaremos de esquemas a través de los + cuales iremos describiendo el proceso. + Notemos antes, que el proceso de compactación esta directamente ligado + con el archivo de gaps o espacios libres ( +\series bold +.fsc +\series default +). +\layout Standard + +Comenzemos con el siguiente cuadro situacional: +\begin_inset Float figure +placement H +wide false +collapsed true + +\layout Caption + +NOMBRE, ARREGLAMEE!!! +\layout Standard + + +\begin_inset Graphics + filename graphics/Compact1.png + width 100text% + keepAspectRatio + +\end_inset + + +\end_inset + + +\layout Standard + +Partiendo de esta base, el algoritmo de compactación tomará en su inicio + al primer gap existente dentro del archivo de datos, en este caso llamado + +\series bold +Gap0 +\series default +. + Luego, establecerá que el +\series bold +Source +\series default + a partir de donde se quieren mover datos, sera: +\layout LyX-Code + +StartGap0 + SizeGap0 = EndGap0 = Source +\layout Standard + +Lo cual no es nada más y nada menos que lo obvio, la fuente a partir de + donde se mueven los datos, sera el fin del primer gap, donde comienzan + datos. + Como destino ( +\series bold +Destination +\series default +) del movimiento, se establece inicialmente, el inicio del gap, o sea +\series bold +StartGap0 = Destination +\series default +. +\layout Standard + +Luego, el algoritmo entrara en un bucle while (mientras haya bucles por + levantar), el cual trabajara hasta el final de la compactación de la siguiente + manera: +\layout Standard + + +\series bold +Mientras haya Gaps +\series default + { +\layout Enumerate + +Se levanta el proximo gap al levantado en una instancia previa. + En este ejemplo, durante el primer loop del while, se levantará +\series bold +Gap1 +\layout Enumerate + +Luego, se calcula cuantos bytes hay que mover hacia el Destination de la + siguiente manera: +\layout Enumerate + + +\series bold +Mustmove_bytes +\series default + = +\series bold +StartGap1 +\series default + - +\series bold +Source +\series default + = +\series bold +StartGap1 +\series default + - +\series bold +EndGap0 ( +\series default +Lo cual nuevamente es lógico pues querremos mover lo que se encuentra entre + el final del primer gap levantado y el inicio del siguiente). +\layout Enumerate + +Se realiza el movimiento de los datos, utilizando las direcciones +\series bold +Source +\series default + y +\series bold +Destination +\series default +, así como la variable +\series bold +Mustmove_bytes +\series default + que nos indica cuantos bytes transferir. +\series bold + +\newline +IMPORTANTE: +\emph on +La transferencia se hace de a chunks de 25 bytes + un resto segun el valor + de Mustmove_bytes. +\layout Enumerate + +Se establece como gap de referencia, al ultimo gap leido (En este caso se + realiza: +\series bold +StartGap0 +\series default + = +\series bold +StartGap1 +\series default +, +\series bold +Gap0Size = Gap1Size +\series default +) y termina el código de repetición del bucle, dando lugar a la carga del + siguiente gap en el inicio del mismo. +\layout Standard + + +\series bold +} +\layout Standard + +Luego del primer bucle, el archivo se vera de la siguiente forma: +\begin_inset Float figure +placement H +wide false +collapsed true + +\layout Caption + +NOMBRE, ARREGLAME!!!! +\layout Standard + + +\begin_inset Graphics + filename graphics/Compact2.png + width 100text% + +\end_inset + + +\end_inset + + +\layout Standard + +Notemos que al final de la porción de datos de los bytes movidos (donde + quedo apuntando +\series bold +Destination +\series default +), hay basura que será pisada por el próximo movimiento. +\layout Standard + +En el próximo loop, el bucle levantará un nuevo gap, y utilizando el gap + anterior (En esta caso el Gap anterior será +\series bold +Gap1 +\series default +) como referencia, realizará los mismos cálculos, desde donde transferir + y cuantos bytes mover. + (El destino es solo establecido inicialmente por código, y para el resto + del algoritmo es el lugar donde quedo el puntero destination luego de la + última escritura). +\layout Standard + +Una vez que se salga del bucle while, se realizará un último movimiento + preprogramado, donde la fuente ( +\series bold +Source +\series default +) será el final del ultimo gap, y la cantidad de bytes a mover será lo que + se encuentre luego del mismo hasta el fin de archivo. +\layout LyX-Code + +Source = StartLastGap + SizeLastGap = EndLastGap +\layout LyX-Code + +Mustmove_bytes = Datsize - Source +\layout Standard + +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 Chapter + +\begin_inset LatexCommand \label{cha:tipo3} + +\end_inset + Archivo con bloques parametrizados y registros de longitud constante \layout Standard @@ -340,10 +1152,9 @@ ID especificado. \layout Standard - -\emph on -ver: void* emufs_tipo3_leer_registro(EMUFS *emu, EMUFS_REG_ID ID, EMUFS_REG_SIZE -* reg_size, int* err) +Ver: +\family typewriter +emufs_tipo3_leer_registro() \layout Subsubsection Grabar Registro @@ -357,10 +1168,9 @@ Luego de grabar un registro, actualiza los archivos de para mantener la coherencia. \layout Standard - -\emph on -ver: EMUFS_REG_ID emufs_tipo3_grabar_registro(EMUFS *emu, void *ptr, EMUFS_REG_S -IZE tam, int* err) +Ver: +\family typewriter +emufs_tipo3_grabar_registro() \layout Subsubsection Borrar Registro @@ -394,9 +1204,9 @@ Completa una estructura del tipo EMUFS_Estadisticas con las estad libres, etc. \layout Standard - -\emph on -ver: EMUFS_Estadisticas emufs_tipo3_leer_estadisticas(EMUFS *emu) +Ver: +\family typewriter +emufs_tipo3_leer_estadisticas() \layout Subsubsection Compactar el Archivo @@ -432,9 +1242,9 @@ fsc el cual disminuye su tamaño también. \layout Standard - -\emph on -ver: void emufs_tipo3_compactar(EMUFS *emu) +Ver: +\family typewriter +void emufs_tipo3_compactar() \layout Section Consideraciones y Políticas de Diseño