1 #LyX 1.3 created this file. For more info see http://www.lyx.org/
11 \paperpackage widemarginsa4
15 \use_numerical_citations 0
16 \paperorientation portrait
19 \paragraph_separation indent
21 \quotes_language english
25 \paperpagestyle default
30 \begin_inset Formula $\mu$
61 es la estuctura principal que encapsula todas las funciones para el manejo
62 de un archivo de datos.
65 Esta estructura consta de:
68 EMUFS_Tipo que es un tipo enumerado que indica cual es la organización.
71 EMUFS_BLOCK_SIZE indica el tamaño del bloque para los tipos 1 y 3.
74 EMUFS_REG_SIZE indica el tamaño del registro, para el tipo 3 que posee tamaño
81 no me convence esta descripcion.
98 \begin_inset LatexCommand \label{sec:cabecera_gral}
102 Organización física general de un archivo E
103 \begin_inset Formula $\mu$
110 \begin_inset Formula $\mu$
113 FS está compuesto por 4 archivos a nivel de sistema operativo: archivo de
114 datos (con 3 formatos posibles, ver páginas
115 \begin_inset LatexCommand \pageref{cha:tipo1}
120 \begin_inset LatexCommand \pageref{cha:tipo2}
125 \begin_inset LatexCommand \pageref{cha:tipo3}
129 ), archivo de índice (ver página
130 \begin_inset LatexCommand \pageref{sec:idx}
134 ), archivo de control de espacio libre (ver página
135 \begin_inset LatexCommand \pageref{sec:fsc}
139 ) y archivo de índices recuperables (ver página
140 \begin_inset LatexCommand \pageref{sec:did}
147 El archivo de datos está compuesto por:
158 (4 bytes en plataformas Linux de 32 bits) que representa el tipo de archivo.
161 Datos dependientes del tipo de archivo.
168 es utilizada para poder detectar el formato de un archivo al abrirlo.
169 Los datos dependientes del tipo de archivo serán explicados en sus secciones
176 +-----------+--------------------------------------------//-+
179 | tipo | Datos dependientes del tipo de archivo ...
187 +-----------+--------------------------------------------//-+
196 Por que los 3 tipos usan lo mismo.
197 Ventajas y desventajas.
201 \begin_inset LatexCommand \label{sec:idx}
208 Con la ayuda de un archivo de bloques y registros (de extensión .idx), podremos
209 ubicar cualquier registro existente dentro del archivo.
212 El archivo de índice contiene una estructura que contiene el id de un registro
213 y el número de bloque al que pertenece.
214 Este archivo esta ordenado por
218 , de modo que incrementa su tamaño cada vez que se grabe en el archivo de
219 datos un nuevo registro, excepto que un registro haya sido borrado con
220 anterioridad lo cual produce que al guardar un nuevo registro se actualice
224 Si un registro es borrado del archivo de datos, debe actualizarse el índice,
225 esto se logra colocando un flag que indique que el id no pertenece a ningún
226 bloque, hemos adoptado poner -1 en el campo location de la estructura
233 Es necesario que este archivo esté ordenado por
237 de registro, ya que esto permitirá el acceso directo para la búsqueda de
238 un registro en el archivo de datos.
244 El tipo EMUFS_IDX define la estuctura de los registros de este archivo.
247 Esta estructura está compuesta por:
250 EMUFS_REG_ID reg_id indica el
257 EMUFS_BLOCK_ID location número de bloque donde se encuentra el registro.
260 EMUFS_REG_ID y EMUFS_BLOCK_ID son
268 Comportamiento (funciones generales)
272 \begin_inset LatexCommand \label{sec:fsc}
276 Archivo de control de espacio libre
279 El archivo de de espacios libres permite decidir a la hora de guardar un
280 registro, donde será guardado.
284 La estructura de este archivo está formada por un número que indica el bloque
285 y otro que indica el espacio libre en él.
288 De esta manera al querer guardar un registro este archivo informará donde
289 cabe el mismo, previa invocación al la función
291 EMUFS_BLOCK_ID emufs_fsc_buscar_lugar(EMUFS *, EMUFS_FREE, EMUFS_FREE*)
293 perteneciente a fsc.h, la cual devuelve el número de bloque donde entra
294 el registro o -1 si no hay un bloque con lugar suficiente, y toma como
295 parámetros una estructura
303 donde el segndo parámetro es el tamaño buscado, y el tercero devuelve el
307 De la misma manera, al borrar un registro este archivo debe ser actualizado
308 colocando el nuevo espacio libre en el bloque.
314 La estuctura que define este archivo es la siguiente:
317 EMUFS_FSC que contiene:
320 EMUFS_BLOCK_ID indica el número de bloque
323 EMUFS_FREE freespace indica la cantidad de espacio libre que queda en el
327 EMUFS_FSC y EMUFS_FREE son
336 \begin_inset LatexCommand \label{sec:did}
340 Archivo de índices recuperables
344 Este archivo funciona como una pila de id`s borrados, es decir, cuando se
349 se almacena en este archivo y será recuperado cuando se desee grabar un
350 registro nuevo, de esta manera se aprovechan todos los
354 sin necesidad de crear uno nuevo cada vez que se borra y graba un registro.
360 Este archivo tiene registros de un solo campo, EMUFS_REG_ID el cual simboliza
367 Las declaraciones e implementación se pueden encontrar en
386 al archivo, el cual será el primero recuperado.
389 ver: emufs_did_agregar()
400 que se guardó en el archivo (o se eliminó del archivo de datos), y trunca
404 ver: emufs_did_get_last()
414 \begin_inset LatexCommand \label{cha:tipo1}
418 Archivo con bloques parametrizados y registros de longitud variable
421 Este tipo de archivo tiene varias complicaciones, al tratarse de un punto
423 \begin_inset LatexCommand \ref{cha:tipo2}
428 \begin_inset LatexCommand \ref{cha:tipo3}
432 (cuenta tanto con bloques como con registros variables), hereda los inconvenien
433 tes (y ventajas) de ambos, más los propios.
434 Al implementar este tipo de archivo se puso enfásis en la eficiencia mientras
435 esta no comprometa la mantenibilidad del código, es por esto que en algunas
436 circunstancias no se hace un uso óptimo del espacio.
439 La implementación de este tipo de archivo puede ser encontrada en
443 mientras que su interfaz pública está disponible en
453 El archivo está compuesto por la
458 \begin_inset LatexCommand \pageref{sec:cabecera_gral}
463 El valor que toma en este tipo de archivo es 0 (o el valor simbólico
472 Luego le sigue una cabecera propia del archivo (un EMUFS_BLOCK_SIZE, 4
473 bytes) que almacena el tamaño del bloque que usa el archivo.
474 De esta menera, al abrir un archivo de este tipo no se necesita tener ninguna
475 información sobre él.
476 A esta cabecera le siguen cero o más bloques del tamaño fijo especificado
477 en la cabecera antes mencionada.
483 +-----------+-----------+------------------------//-+
486 | tipo | tam bloque| Cero o más bloques ...
494 +-----------+-----------+------------------------//-+
497 /- 4 bytes -/- 4 bytes -/
500 Organización física de un bloque
503 Cada bloque no guarda información en sí, sólo se comporta como un contenedor
505 Esto no significa que un bloque no tenga utilidad, el bloque es utilizado
506 para proveer un acceso semi-aleatorio a los registros.
507 Para esto se utiliza el archivo de índice (ver página
508 \begin_inset LatexCommand \ref{sec:idx}
512 ), que almacena pares (identificador de registro, número de bloque).
513 Para que sea suficiente este único índice para hallar un registro (siendo
514 que puede haber más de un registro por bloque), es necesario
516 alinear los registros a izquierda
521 bloque N-1 | bloque N | bloque N+1
524 /----------+------------+------------+-------------------+-----------/
529 | registro 1 | registro 2 | espacio libre ...
532 /----------+------------+------------+-------------------+-----------/
535 De forma tal que una vez obtenido el número de bloque se pueda recorrer
536 secuencialmente hasta encontrar el registro deseado.
537 A fin de llevar el conteo de espacio libre se utiliza el archivo de control
538 de espacio libre (ver página
539 \begin_inset LatexCommand \ref{sec:fsc}
543 ), de forma tal que no sea necesario recorrer secuencialmente en busca de
544 espacio libre al hacer una inserción.
547 Puede darse un caso excepcional en el que un registro sea más grande que
548 un bloque, en este caso el registro se almacenará en N bloques consecutivos
549 (siendo N la cantidad de bloques que necesita el registro), ocupando completos
550 los todos los bloques a excepción del último, en el que posteriormente
551 se pueden agregar más registros.
554 Comportamiento (funciones de la interfáz)
557 Detalles de implementación (funciones internas, ver si lo ponemos o no)
561 \begin_inset LatexCommand \label{cha:tipo2}
565 Archivo sin bloques y registros de longitud variable
568 Este tipo de archivo nos traerá a la mesa la particularidad de grabar registros
569 de longitud variable sin realizar su agrupación en bloques, y como veremos
570 en la siguiente sección, tambien permitirá la administración de gaps que
571 queden en el archivo luego de operaciones de baja de registros.
577 Este tipo de archivo realizará el almacenamiento de registros de longitud
578 variable en disco, su borrado y modificación sin la utilización de bloques
580 Su implementación se encuentra en los archivos fuente (
591 Los archivos del tipo 2, presentarán al comienzo del mismo un header compuesto
592 simplemente por un dato del tipo EMUFS_Tipo (int) el cual indicará el tipo
593 de archivo en cuestión.
596 Para poder entender mejor la organización fisica de este tipo de archivo,
597 tomemos el caso hipotético en el que se encuentran grabados
601 (comenzando desde registro 0) de
610 Supongamos también que entre el registro 0 y 1 se encontraba un
627 Si miramos al archivo de datos (.dat) en el disco nos encontraremos con
629 \begin_inset Float figure
636 NOMBRE, ARREGLAME!!!!
640 \begin_inset Graphics
641 filename graphics/Example1.png
652 Como se puede observar, a nivel físico cada registro grabado esta compuesto
653 por un Header cuyo tamaño total es de 8 bytes (
661 ), y posteriormente el registro (bloque de datos) en sí.
662 Luego se encuentra el espacio libre de 18 bytes dejado por el registro
663 de 10 bytes eliminado (10 bytes de datos + header de 8 bytes) y finalmente
664 el segundo registro mencionado.dsds
667 Comportamiento (funciones de la interfaz)
682 se encuentran las cabeceras y la implementación de las funciones principales
683 respectivamente, las cuales dan funcionalidad a esta organización.
687 A continuación se comentará el funcionamiento algunas de las mas importantes.
693 Como se vió al comienzo, los registros en este tipo de archivo no se encuentran
694 agrupados en bloques de ninguna índole y estan dispersos a lo largo del
695 archivo, con la particularidad de que pueden existir gaps o espacio libre,
696 entre dos registros dados.
699 Por ende la lectura de registros en este tipo de organización es muy simple
700 y dada la inexistencia de bloques, el procedimiento será el siguiente:
703 Se determina el offset en bytes, donde comienza el registro deseado, a través
704 de su ID, buscando la misma en el archivo índice (
711 Ya determinada la posición física del registro dentro del archivo de datos
716 ), nos posicionamos en la misma, y leemos el header del registro (
725 Contando así con el tamaño del registro, procedemos a leer el mismo (los
726 datos), dando por finalizada la lectura.
732 En el proceso de alta de registros entrarán en juego dos archivos descriptos
735 sección de archivos auxiliares
737 , siendo estos el archivo índice (
741 ), y el archivo de gaps / espacios libres (
748 Así pues, a la hora de realizar una inserción de un registro en el archivo
749 de datos, el procedimiento será el siguiente:
752 Calculamos el espacio que necesitaremos para el registro: sizeof(
760 ) + sizeof(registro).
763 Determinamos donde debemos insertar el registro, ya sea un gap donde entre,
764 o bien al final del archivo.
767 Insertamos el registro e información de control (
775 ), en la posición indicada en el paso 2.
778 En caso de haber utilizado un GAP, actualizamos el espacio libre restante
779 en el mismo y en caso de que se haya utilizado al totalidad del GAP, se
780 lo elimina del archivo (
787 Actualizamos la entrada correspondiente al registro ingresado (determinada
788 por su RegID), en el archivo índice (
792 ), indicando su offset donde podrá ser accedido luego.
798 En el proceso de baja de registros entrarán en juego los tres archivos descripto
801 sección de archivos auxiliares
803 , siendo estos el archivo índice (
807 ), el archivo de gaps / espacios libres (
811 ) y el archivo de ID's liberados (
818 Dado que en la implementación de este tipo de organización física contamos
819 con los gaps o espacios libres entre registros, no se eliminará fisicamente
820 el registro del archivo de datos (
824 ), pues entonces carecería de sentido el archivo anteriormente mencionado
830 En cambio, se agrega el gap dejado por la eliminación a dicho archivo,
831 y se marca fisicamente en el archivo de datos la eliminación mediante un
832 fill de los bytes correspondientes con un caracter nulo.
833 (hexa 00 y con el propósito de probar fehacientemente que el sistema funciona).
836 El proceso de baja o eliminación de un registro constará luego de los siguientes
840 Se obtiene el offset o posición relativa en donde se encuentra grabado el
841 registro dentro del archivo de datos.
844 Se obtiene el tamaño del registro y se realiza un dummyfill del sector del
845 archivo correspondiente al registro que se está dando de baja.
846 (Se rellena la zona correspondiente a su header+data).
849 Se agrega el GAP generado al archivo de gaps o espacios libres, y en caso
850 de haberse generado un GAP lindante con otro GAP, se realizará un merge
851 de los mismos y se los registrará bajo una única entrada en el archivo
852 de espacios libres (.fsc).
855 Se agrega el ID que fue liberado, al archivo de ID's liberados (
859 ), al final del mismo (
866 Se marca en el archivo índice (
870 ) la eliminación, mediante el valor ¨-1¨ en el registro correspondiente
871 al registro recién eliminado (se le cambia el valor al n-esimo registro,
872 donde N = IDReg del reg eliminado).
875 Modificación de registros
878 Dada la naturaleza del archivo de ID's liberados, y el manejo de espacio
879 libre del que consta esta organización de archivo, el proceso de modificación
880 de un registro se limita a los siguientes pasos:
883 Se realiza la lectura del registro, mediante el respectivo procedimiento
884 ya desarollado anteriormente.
887 Una vez que se cuenta con los nuevos datos modificados, se procede a dar
888 de baja el registro que ha sido modificado, e inmediatamente después se
889 realiza una inserción con los nuevos datos.
898 Como fue indicado, dada la naturaleza de PILA del subsistema de administración
899 de ID liberados, es asegurado que la nueva inserción del registro modificado
900 se realizará con el mismo RegID.
903 Obtención de estadísticas
906 Compactación del archivo de datos
909 Asi como los otros dos tipos de datos, el que nos compete también cuenta
910 con la posibilidad de realizar la compactación de datos cuando el usuario
911 lo desee, justificando todos los registros a izquierda, eliminando así
912 los gaps existentes y decrementando el tamaño del archivo en disco (truncandolo
916 Para poder comprender como hemos implementado el proceso de recompactación
917 en nuestro tipo de archivo 2, nos ayudaremos de esquemas a través de los
918 cuales iremos describiendo el proceso.
919 Notemos antes, que el proceso de compactación esta directamente ligado
920 con el archivo de gaps o espacios libres (
927 Comenzemos con el siguiente cuadro situacional:
928 \begin_inset Float figure
935 NOMBRE, ARREGLAMEE!!!
939 \begin_inset Graphics
940 filename graphics/Compact1.png
952 Partiendo de esta base, el algoritmo de compactación tomará en su inicio
953 al primer gap existente dentro del archivo de datos, en este caso llamado
959 Luego, establecerá que el
963 a partir de donde se quieren mover datos, sera:
966 StartGap0 + SizeGap0 = EndGap0 = Source
969 Lo cual no es nada más y nada menos que lo obvio, la fuente a partir de
970 donde se mueven los datos, sera el fin del primer gap, donde comienzan
976 ) del movimiento, se establece inicialmente, el inicio del gap, o sea
978 StartGap0 = Destination
983 Luego, el algoritmo entrara en un bucle while (mientras haya bucles por
984 levantar), el cual trabajara hasta el final de la compactación de la siguiente
995 Se levanta el proximo gap al levantado en una instancia previa.
996 En este ejemplo, durante el primer loop del while, se levantará
1001 Luego, se calcula cuantos bytes hay que mover hacia el Destination de la
1025 Lo cual nuevamente es lógico pues querremos mover lo que se encuentra entre
1026 el final del primer gap levantado y el inicio del siguiente).
1029 Se realiza el movimiento de los datos, utilizando las direcciones
1037 , así como la variable
1041 que nos indica cuantos bytes transferir.
1047 La transferencia se hace de a chunks de 25 bytes + un resto segun el valor
1051 Se establece como gap de referencia, al ultimo gap leido (En este caso se
1064 ) y termina el código de repetición del bucle, dando lugar a la carga del
1065 siguiente gap en el inicio del mismo.
1073 Luego del primer bucle, el archivo se vera de la siguiente forma:
1074 \begin_inset Float figure
1081 NOMBRE, ARREGLAME!!!!
1085 \begin_inset Graphics
1086 filename graphics/Compact2.png
1097 Notemos que al final de la porción de datos de los bytes movidos (donde
1102 ), hay basura que será pisada por el próximo movimiento.
1105 En el próximo loop, el bucle levantará un nuevo gap, y utilizando el gap
1106 anterior (En esta caso el Gap anterior será
1110 ) como referencia, realizará los mismos cálculos, desde donde transferir
1111 y cuantos bytes mover.
1112 (El destino es solo establecido inicialmente por código, y para el resto
1113 del algoritmo es el lugar donde quedo el puntero destination luego de la
1117 Una vez que se salga del bucle while, se realizará un último movimiento
1118 preprogramado, donde la fuente (
1122 ) será el final del ultimo gap, y la cantidad de bytes a mover será lo que
1123 se encuentre luego del mismo hasta el fin de archivo.
1126 Source = StartLastGap + SizeLastGap = EndLastGap
1129 Mustmove_bytes = Datsize - Source
1132 Damos por terminada así, la explicación del algoritmo de compresión el cual
1133 para el caso del tipo 2, es realmente bastante sencillo.
1137 \begin_inset LatexCommand \label{cha:tipo3}
1141 Archivo con bloques parametrizados y registros de longitud constante
1144 Las distintas organizaciones de archivos buscan aprovechar al máximo el
1145 espacio del archivo.
1148 En este caso veremos que sucede luego de agregar y borrar una gran cantidad
1149 de registros del archivo, lo que provoca como consecuencia directa la fragmenta
1150 ción del archivo, es decir, quedan huecos entre un registro y otro, lo que
1151 produce un desperdicio de espacio.
1157 Esta organización guarda los registros pertenecientes al archivo en bloques
1158 de tamaño parametrizado, de modo que intentará guardar la mayor cantidad
1159 de registros que quepan en un bloque.
1163 Así como los graba, también tendrá la posibilidad de leer registros y borrarlos
1167 Comportamiento Particular de los Archivos Auxiliares
1168 \layout Subsubsection
1170 Archivo de Bloques y Registros (.idx)
1173 buscar algun caso extraordinario.
1174 \layout Subsubsection
1176 Archivo de Bloques y Espacio Libre (.fsc)
1177 \layout Subsubsection
1179 Archivo de Id`s Borrados (.did)
1182 El comportamiento de este archivo, es común para todas las organizaciones
1183 y se ha explicado en 3.3.2.
1186 Funciones Principales
1200 se encuentran las cabeceras y la implementación de las funciones principales
1201 respectivamente, las cuales dan funcionalidad a esta organización.
1204 A continuación se comentará la descripción de algunas acciones importantes.
1205 \layout Subsubsection
1210 La lectura de un registro se realiza con la ayuda del archivo .
1214 el cual contiene la información de la posición del registro dentro del
1216 Una vez leida esta información, se recupera el bloque (en su totalidad)
1217 del archivo y se busca secuencialmente el registro con el
1226 emufs_tipo3_leer_registro()
1227 \layout Subsubsection
1232 Graba un registro en un bloque donde haya espacio suficiente, y si no crea
1233 un nuevo bloque y lo agrega al final del archivo.
1236 Luego de grabar un registro, actualiza los archivos de índice .idx y .fsc
1237 para mantener la coherencia.
1242 emufs_tipo3_grabar_registro()
1243 \layout Subsubsection
1248 Borra un registro del archivo de datos, para esto levanta el bloque al que
1249 pertenece el archivo y ajusta los demás registros justificandolos hacia
1253 Cabe destacar que para dar de baja un registro no hace falta borrarlo del
1254 archivo de datos, solo es necesario borrar las entradas en los archivos
1255 de índice, pero cuando se realiza el ajuste el algoritmo toma porciones
1256 del bloque del tamaño de un registro mas su encabezado - comenzando desde
1257 el siguiente al que fue borrado - y copia (sobreescribe) sobre el anterior.
1258 De esta manera, la información correspondiente al registro borrado no estará
1259 presente en el archivo de datos.
1260 Esto es una consecuencia del ajuste al borrar un registro, pudiendo no
1261 ser así, si no se realizara el mismo.
1262 \layout Subsubsection
1267 Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
1268 cantidad de bloques, cantidad de registros, espacio libre total, espacio
1269 libre promedio, espacio libre máximo y mínimo, etc.
1272 Esta información es el resultado de ciertos cálculos realizados tanto en
1273 el archivo de datos como en los archivos índice.
1276 Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
1277 del archivo de datos, espacio libre total, cantidad de registros, cantidad
1278 de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
1284 emufs_tipo3_leer_estadisticas()
1285 \layout Subsubsection
1287 Compactar el Archivo
1290 Esta función intenta reorganizar el archivo de manera que el espacio libre
1291 sea lo menor posible, recordando siempre que un registro no puede ser almacenad
1292 o en mas de un bloque excepto que el tamaño del registro sea mayor que el
1296 Para realizar esto, se aprovecha la funcionalidad de
1298 emufs_tipo3_grabar_registro()
1300 ya que esta tiene la capacidad de determinar una posición mas eficiente
1301 en el archivo para un registro.
1302 Por esto lo que se hace es levantar uno por uno los registros y volverlos
1303 a grabar, de ese modo todos los
1307 que pudieron haberse formado por la eliminación de registros serán cubiertos
1311 Al finalizar este proceso se verifica si existen bloques vacios para truncar
1313 Lo mismo se debe hacer con el archivo de espacios libres .
1317 el cual disminuye su tamaño también.
1322 void emufs_tipo3_compactar()
1325 Consideraciones y Políticas de Diseño
1328 Esto para mi va en organización física.
1331 Se han tomado ciertas consideraciones para algunos casos particulares que
1332 se pueden presentar durante el uso/ejecución de la aplicación.
1335 Cada registro tiene un encabezado que indica el
1342 Si el tamaño del registro es mayor que el tamaño del bloque el registro
1343 se particionará en la cantidad de bloques que sea necesario, pero siempre
1344 se guardará desde el comienzo de un bloque, esto quiere decir que nunca
1345 se podrá encontrar un comienzo de registro en algún lugar de un bloque
1346 que no sea el comienzo del mismo.
1349 Si el registro se divide en mas de un bloque, se le coloca el id como encabezado
1350 igualmente, pero en el archivo .
1354 solo se guarda el primer bloque.
1359 se actualizan todos los bloques con el espacio libre que realmente tienen.
1365 Las comparaciones, pruebas, etc...
projects / z.facultad / 75.06 / emufs.git / blob