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$
48 Esta es la documentación correspondiente a las API`s para el manejo de tres
49 organizaciones de archivo diferentes.
50 A continuación se describe cada una de ellas y su modo de funcionamiento
51 y sus características principales.
52 De la correcta elección de la organización, dependerá la eficiencia de
53 la aplicación que la utilice.
57 EMUFS se presenta como un
65 , capaz de administrar datos almacenados en cualquiera de las tres organizacione
66 s de archivo previamente mencionadas, las cuales a saberse son:
69 Registros de Longitud Variable, Bloques de tamaño parametrizable
72 Registros de Longitud Variable, Sin Bloques
75 Registros de Longitud Fija, Bloques de tamaño parametrizables
78 A través de este trabajo, se podrán observar las diferencias entre distintos
79 tipos de organización de archivos, ventajas y desventajas de cada una de
80 ellas, y las situaciones particulares que deberá sortear un filesystem,
81 como la partición de registros en distintos bloques, manejo de espacio
82 libre, compactación de un archivo, etc.
85 A continuación, veremos que el manejo de los archivos en EMUFS se realiza
86 a través de una estructura de control comun para cualquier tipo de archivo,
87 dandole flexibilidad y escalabilidad a nuestro sistema.
90 Hacia el final de esta presentación, se observaran las pruebas realizadas
91 con las distintas organizaciones de archivos, y las conclusiones obtenidos
101 Se detallan a continuación los tipos de datos definidos y utilizados en
102 las distintas implementaciones que conforman nuestro sistema, siendo el
103 más importante de ellos, la estructura
107 que actúa como interfaz común para el manejo de cualquier tipo de archivo
108 (no importa que tipo de organización física posea un archivo, esta estructura
109 prooverá una interfaz (funciones) para su manejo).
115 En la implementación de cada tipo de organización física, así como tambien
116 en las API de los archivos auxiliares comunes a ellas, se da la utilización
117 de tipo definidos para una clara interfaz entre las mismas, los cuales
118 son brevemente descriptos a continuación y pueden ser hallados en el archivo
130 : usado para representar un
141 : usado para representar el tamaño en bytes de un registro.
148 : usado para representar un número de bloque.
155 : usado para representar el tamaño en bytes de un bloque.
162 : usado para representar espacio libre en bytes.
169 : usado para representar un offset.
189 es la estuctura principal que encapsula todas las funciones para el manejo
190 de un archivo de datos.
191 Posee punteros a funciones que dependiendo de la organización fisica por
192 la cual se opte dentro del sistema, serán asignados de acorde.
196 Su declaración puede ser observada en el archivo
200 y la misma cuenta con los siguiente campos:
207 que es un tipo enumerado que indica cual es la organización.
214 indica el tamaño del bloque para los tipos 1 y 3.
221 indica el tamaño del registro, para el tipo 3 que posee tamaño constante.
228 puntero a la función para leer un bloque.
233 void *leer_bloque_raw()
235 puntero a la función para leer un bloque, el anterior y el siguiente.
240 void **leer_registro()
242 puntero a la función para leer un registro.
247 void **leer_registro_raw()
249 puntero a la función para leer un registro con su encabezado.
254 EMUFS_REG_ID *grabar_registro()
256 puntero a la función para grabar un registro.
261 EMUFS_REG_ID *modificar_registro()
263 puntero a la función para modificar un registro.
268 int *borrar_registro()
270 puntero a la función para borrar un registro.
275 EMUFS_Estadisticas *leer_estadisticas()
277 puntero a la función para cargar una estructura con las estadísticas.
284 puntero a la función para compactar un archivo.
291 almacena el nombre del archivo sin extensión.
294 Esta estructura define los valores de sus punteros según el tipo de organización
295 que se desee manejar y esto se realiza a través del API emufs, implementado
300 , que se describirá posteriormente.
303 Por ejemplo si se desea crear un archivo de nombre
304 \begin_inset Quotes eld
308 \begin_inset Quotes erd
311 organizado de la forma 3, se invoca a la función:
316 emufs_crear(filename,tipo,tam_bloque,tam_reg),
322 es el nombre que tendrán los archivos de datos e índice,
326 es el tipo de organización - bloques parametrizados y registros constantes
331 es el tamaño del bloque, y
335 es el tamaño del registro.
338 Para las diferentes organizaciones puede ser que alguno de estos 2 últimos
339 valores no tengan sentido almacenarlas y tomaran un valor por defecto igual
343 Según el tipo de organización, se inicializan los punteros a las funciones.
350 emufs_tipo3_leer_bloque()
352 , y lo mismo sucede con los demás.
362 es un tipo de dato enum, el cual será utilizado en la cabecera de todo
367 ), para indicar los distintos tipos de organización física.
368 Su declaración puede verse en el archivo
373 A saberse los valores y significado correspondiente que puede tomar este
381 : Archivos con registros de longitud variable y bloques parametrizables.
388 : Archivos con registros de longitud variable sin bloques.
395 : Archivos con registros de longitud fija y bloques parametrizables.
405 es una estructura que almacenará los datos pertinentes a las estadísticas
406 de un archivo dado, y será utilizada para visualizar dichas observaciones
410 Su declaración puede ser observada en el archivo
414 y la misma cuenta con los siguiente campos:
425 : indica el tamaño del archivo de datos (.dat) en bytes.
436 : indica el tamaño de los archivos auxiliares sumados en bytes.
447 : indica la cantidad de bytes en información de control utilizados para
459 : promedio de espacio libre en el archivo de datos (por bloque o gap promedio
471 : total de espacio libre en el archivo de datos.
482 : máximo espacio libre en el archivo de datos (en un bloque o máximo gap
505 : cantidad de bloques en el archivo de datos (.
520 : cantidad de registros en el archivo de datos (
527 En base a la estructura descripta anteriormente y mediante la utilización
528 de la función de lectura de estadísticas l
530 emufs_leer_estadisticas()
532 disponible en la estructura común
536 handler de cualquier tipo de archivo, podremos obtener una serie de estadística
537 s que pasamos a detallar (más alla de los datos básicos como cant registros,
538 cant bloques, tam archivo, etc):
541 Relación entre espacio libre y el tamaño del archivo de datos (
548 Relación entre el espacio ocupado por información de control y el tamaño
549 del archivo de datos (
556 Cantidad promedio de espacio libre (en bloque o gap promedio)
559 Desviaciones extremas de espacio libre (máximo/mínimo espacio libre en bloque
564 \begin_inset LatexCommand \label{sec:cabecera_gral}
568 Organización física general de un archivo E
569 \begin_inset Formula $\mu$
576 \begin_inset Formula $\mu$
579 FS está compuesto por 4 archivos a nivel de sistema operativo: archivo de
580 datos (con 3 formatos posibles, ver páginas
581 \begin_inset LatexCommand \pageref{cha:tipo1}
586 \begin_inset LatexCommand \pageref{cha:tipo2}
591 \begin_inset LatexCommand \pageref{cha:tipo3}
595 ), archivo de índice (ver página
596 \begin_inset LatexCommand \pageref{sec:idx}
600 ), archivo de control de espacio libre (ver página
601 \begin_inset LatexCommand \pageref{sec:fsc}
605 ) y archivo de índices recuperables (ver página
606 \begin_inset LatexCommand \pageref{sec:did}
613 El archivo de datos está compuesto por:
624 (4 bytes en plataformas Linux de 32 bits) que representa el tipo de archivo.
627 Datos dependientes del tipo de archivo.
634 es utilizada para poder detectar el formato de un archivo al abrirlo.
635 Los datos dependientes del tipo de archivo serán explicados en sus secciones
642 +-----------+--------------------------------------------//-+
645 | tipo | Datos dependientes del tipo de archivo ...
653 +-----------+--------------------------------------------//-+
659 Uso de la estructura EMUFS
662 Como fue mencionado anteriormente en la descripción de la estructura EMUFS,
663 la misma proporciona al usuario una interfaz a través de la cual puede
664 realizar el manejo de archivos en forma genérica, abstrayéndose del tipo
665 de organización física en particular que dicho archivo posea.
670 y las funciones que inicializan la estructura se encuentran en
675 Es decir que a traves de esta estructura, podemos manejar cualquier tipo
676 de archivo, mediante una misma interfaz en común.
681 posee además de ciertos datos que describen la organización física de un
682 archivo dado como por ejemplo
700 , una serie de punteros a funciones para el manejo del archivo del cual
704 Entre dichos funciones se encuentran:
710 leer_bloque(), borrar_registro()
718 modificar_registro, leer_estadisticas()
725 Para entender mejor el uso de esta estructura para el manejo de los archivos,
726 mostraremos un ejemplo concreto.
727 Supongamos que tenemos el siguiente código:
730 EMUFS *efs = emufs_crear(¨articulos.dat¨,T3,200,50);
733 Esto hará que se cree el archivo de datos
737 , con la organización física tipo 3 con registros de longitud fija de 50
738 bytes y bloques de 200 bytes.
739 Al mismo tiempo, los se asginarán valores a los punteros a funciones que
740 posee dicha estructura, la cual de ahora en más estará en condiciones de
741 manejar un archivo del tipo 3.
742 Gráficamente lo que sucede es:
746 \begin_inset Float figure
753 Inicialización de estructura EMUFS para un caso Archivo Tipo 3
757 \begin_inset Graphics
758 filename graphics/Emufsinit.png
769 Así pues, cuando se utilize la estructura para por ejemplo leer un registro,
770 sucedera lo siguiente:
773 efs->leer_registro(params) -- calls --> emufs_tipo3_leer_registro(params)
776 Como se puede observar, la estructura
780 permitirá el manejo de cualquier tipo de archivo, a través del mismo código,
781 dandole gran flexibilidad a nuestro sistema, que podrá expandirse a más
782 tipos de archivos de ser necesario.
788 Acompañando al archivo de datos (
792 ) el cual es responsable de la contención de los registros, tendremos tres
793 archivos auxiliares (
805 ) cuya funcionalidad y propósito pasamos a describir a continuación, sin
806 antes remarcar que los tres archivos poseen una sola implementación para
807 las distintas formas de organización física que hemos implementado (tres
808 para ser mas exactos).
811 Entre las ventajas de poseer la misma implementación se encuentra el tener
812 un API común entre los tres tipos para el manejo de la localización de
813 sus registros, administración de espacio libre e Id's liberados, sin necesidad
814 de realizar n-implementaciones para un mismo objetivo final.
817 Además, la obtención de ciertos datos estadísticos como espacio libre, o
818 cantidad de registros, se realiza a través de la misma interfaz, y también
819 se ha facilitado en cierto grado la re-organización física de un archivo
820 (pasar de un tipo a otro), dado el uso de estos tres archivos auxiliares
821 en común para funciones tan predominantes como índexación, administración
822 de espacio libre y recuperación de Id's.
826 \begin_inset LatexCommand \label{sec:idx}
833 El archivo índice (.idx), permite la localización de los registros en el
834 .DAT de forma directa, mediante la obtención de su offset respecto del inicio
835 del .dat, o nro bloque (segun el tipo de organización física) en donde se
836 encuentra un registro dado, indicado por su
841 Los registros de este archivo se encuentran representados una estructura
842 que indica un número de registro y el bloque u offset en donde se encuentra
846 Es necesario que este archivo esté ordenado por
850 , ya que esto permitirá el acceso directo al mismo, para la rápida obtención
851 del nro de bloque u offset y posterior búsqueda de un registro en el archivo
858 Los registros de este archivo se encuentran representados a nivel codigo
859 por el siguiente tipo de dato interno (
866 typedef struct emufs_idx_t {
872 EMUFS_OFFSET location;
879 \begin_inset Float table
886 Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion
892 <lyxtabular version="3" rows="2" columns="3">
894 <column alignment="center" valignment="top" leftline="true" width="0">
895 <column alignment="center" valignment="top" leftline="true" width="0">
896 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
897 <row topline="true" bottomline="true">
898 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
906 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
914 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
922 <row topline="true" bottomline="true">
923 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
931 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
939 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
944 Indica que el registro de id_reg = 5, se encuentra en el bloque 54
956 \begin_inset Float table
963 Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion
969 <lyxtabular version="3" rows="2" columns="3">
971 <column alignment="center" valignment="top" leftline="true" width="0">
972 <column alignment="center" valignment="top" leftline="true" width="0">
973 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
974 <row topline="true" bottomline="true">
975 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
983 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
991 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
999 <row topline="true" bottomline="true">
1000 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1008 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1016 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1021 Indica que el registro de id_reg = 5, se encuentra en el bloque 54
1041 Como se puede observar, para distintas organizaciones el significado de
1042 los registros en este archivo es diferente y se utilizará de distinta manera
1049 Las declaraciones e implementación se pueden encontrar en
1063 \labelwidthstring 00.00.0000
1071 Los registros del archivo indice (
1075 ), poseen una correspondencia 1 a 1, con los Id's de los registros en el
1081 Con esto, queremos decir que el N-ésimo registro del archivo índice, será
1082 aquél que posea la información para localizar al registro cuyo
1086 es N, dentro del archivo de datos (
1096 Cabe aclarar que por si bien el indice se encuentra ordenado por
1100 , los registros en el archivo de datos, por lo general no lo estarán.
1106 emufs_idx_buscar_registro()
1108 \labelwidthstring 00.00.0000
1114 Ante la alta de un registro en el archivo de datos, se insetará un nuevo
1115 registro en el archivo índice, con el id_reg del registro en cuestion,
1116 y el offset u bloque donde se lo haya grabado en disco.
1122 \labelwidthstring 00.00.0000
1128 Ante el borrado de un registro del archivo de datos, se accederá el registro
1129 correspondiente en el índice, y se actualizara su LOCATION, estableciendolo
1130 en el valor especial
1134 , el cual indica que ese registro ha sido eliminado y por ende no se lo
1135 podrá localizar en el futuro.
1136 Como se verá mas adelante, según el tipo de organización física, el registro
1137 puede ser borrado concretamente del .
1148 \labelwidthstring 00.00.0000
1154 Ante la modificación en la posición física de un registro dentro del archivo
1155 de datos (por ejemplo luego del proceso de recompactación, se realizará
1156 la modificación respectiva del campo
1164 emufs_idx_actualizar()
1168 \begin_inset LatexCommand \label{sec:fsc}
1172 Archivo de control de espacio libre
1175 El archivo de espacio libre (
1179 ) (espacio por bloque o gaps en archivo, según el tipo de organización física),
1180 tiene como función la administración del espacio libre, generado por previas
1181 eliminaciones de registros en el archivo de datos.
1182 El mismo, nos indicará donde hay lugar para insertar un nuevo registro.
1185 Para el caso de una organización por bloque, nos dirá en que bloque o si
1186 se debe generar un nuevo bloque.
1187 En el caso de la organización sin bloques, nos indicará en que gap o si
1188 al final del archivo.
1191 Los registros de este archivo se encuentran representados una estructura
1192 que indica un número de bloque u offset y el espacio libre disponible en
1193 el mismo (o apartir del mismo en el caso del offset).
1200 : Por requerimiento del algoritmo de compactación el tipo de organización
1201 física con reg long var, sin bloques, los gaps se graban en forma ordenada
1203 (El orden se corresponde con lo que hay en el .dat).
1209 Los registros de este archivo se encuentran representados a nivel codigo
1210 por el siguiente tipo de dato interno (
1217 typedef struct emufs_fsc_t {
1220 EMUFS_BLOCK_ID marker;
1223 EMUFS_FREE freespace;
1233 \begin_inset Float table
1240 Ejemplo de registro en archivo de control de espacio libre para un archivo
1245 \begin_inset Tabular
1246 <lyxtabular version="3" rows="2" columns="3">
1248 <column alignment="center" valignment="top" leftline="true" width="0">
1249 <column alignment="center" valignment="top" leftline="true" width="0">
1250 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
1251 <row topline="true" bottomline="true">
1252 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1260 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1268 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1276 <row topline="true" bottomline="true">
1277 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1285 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1293 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1298 Indica que en el bloque 12, hay 120 bytes libres al final del mismo.
1310 \begin_inset Float table
1317 Ejemplo de registro en archivo de
1321 para un archivo sin bloques
1325 \begin_inset Tabular
1326 <lyxtabular version="3" rows="2" columns="3">
1328 <column alignment="center" valignment="top" leftline="true" width="0">
1329 <column alignment="center" valignment="top" leftline="true" width="0">
1330 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
1331 <row topline="true" bottomline="true">
1332 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1340 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1348 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1356 <row topline="true" bottomline="true">
1357 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1365 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1373 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1378 Indica que a partir del byte 12 del archivo de datos, hay 120 bytes libres.
1398 Como se puede observar, para distintas organizaciones el significado de
1399 los registros en este archivo es diferente y se utilizará de distinta manera
1403 Funciones principales
1406 Las declaraciones e implementación se pueden encontrar en
1420 \labelwidthstring 00.00.0000
1426 Ante la operación de alta de un registro en el archivo de datos, se realizará
1427 la búsqueda de espacio libre donde este podrá ser insertado.
1428 En el caso de organizaciones con bloques, se buscará en que
1432 se posee espacio suficiente para albergar el nuevo registro.
1433 En el caso de organizacion sin bloque, se buscará un gap o espacio libre
1434 en el archivo, obteniéndose en consecuencia, el
1442 emufs_fsc_buscar_lugar()
1444 \labelwidthstring 00.00.0000
1450 Luego de una operación de baja o alta de un registro en el archivo de datos
1455 ), incrementará o decrementará respectivamente el espacio libre en el archivo
1456 de datos, y esto deberá ser registrado, agregando un nuevo registro en
1457 el archivo de espacios libres (
1461 ) o bien modificandoló.
1465 En el caso de organizaciónes con bloques, se actualizará el valor del espacio
1470 en el bloque (ya sea incrementandoló o decrementandoló) o bien se insertará
1471 un nuevo registro en caso de que se esté creando un nuevo bloque en el
1472 archivo de datos (en este caso no será debido a un alta o baja de registro
1473 como se mencionó al principio).
1477 Para el caso de organización sin bloques, en el caso de baja de un registro
1482 ) se insertará un nuevo registro en el
1486 dando cuenta de la aparición de un nuevo gap en el archivo de datos (
1490 ), y en caso de estar este lindante con otro gap, se realizará el merge
1492 (esto esta explicado más en profundidad en los casos particulares de organizaci
1493 ón fisica, registros variables sin bloques).
1494 Para el caso de una alta en el archivo de datos (
1498 ), el valor del gap donde se haya insertado se actualizará.
1503 emufs_fsc_agregar(), emufs_fsc_agregar_gap(), emufs_fsc_actualizar(), emufs_fsc_
1506 \labelwidthstring 00.00.0000
1512 : Unicamente para el caso de una organización que presente gaps en el archivo,
1513 se podrá dar a lugar la eliminación de un registro del archivo de espacios
1519 Esta situación tendrá efecto cuando se inserte un registro que entre perfecto
1520 en un gap disponible, y por ende el gap desaparecerá.
1524 emufs_fsc_borrar_gap()
1528 \begin_inset LatexCommand \label{sec:did}
1532 Archivo de id's recuperables
1535 El archivo de Id's liberado (
1539 ) llevará cuenta de aquellos Id's de registros (
1543 ) que ya no se encuentran siendo utilizados y fueron liberados por registros
1544 eliminados previamente.
1545 A través del mismo, se podrá realizar la reutilización de Id's ante la
1546 alta de nuevos registros.
1549 A nivel físico, este archivo poseerá una secuencia de datos del tipo EMUFS_REG_I
1550 D, y el comportamiento del sistema de recuperación de Id's será el de una
1552 Es decir, ante el requerimiento de un
1556 libre por una función del sistema como por ejemplo la alta de un nuevo
1557 registro, el API del archivo (
1561 ), obtendrá el último dato del mismo (el
1565 que fue liberado mas recientemente), y truncará el archivo eliminando el
1570 recuperado de la tabla.
1571 (LIFO, Last in First Out).
1577 Este archivo tiene registros de un solo campo,
1581 el cual simboliza al id que fue liberado en un proceso de baja de registros.
1584 Funciones principales
1587 Las declaraciones e implementación se pueden encontrar en
1601 \labelwidthstring 00.00.0000
1607 Ante la eliminación de un registro del archivo de datos (
1611 ) se procederá al agregado del correspondiente
1615 que fue liberado por dicha operación, al archivo
1629 \labelwidthstring 00.00.0000
1635 Cuando el sistema desee grabar un nuevo registro en el archivo de datos,
1640 disponible para el mismo.
1641 El sistema de administración de Id's libres, obtendrá el último
1645 que se guardó en el archivo (o se eliminó del archivo de datos), y truncará
1646 el archivo eliminandolo.
1654 emufs_did_get_last()
1658 \begin_inset LatexCommand \label{cha:tipo1}
1662 Archivo con bloques parametrizados y registros de longitud variable
1665 Este tipo de archivo tiene varias complicaciones, al tratarse de un punto
1667 \begin_inset LatexCommand \ref{cha:tipo2}
1672 \begin_inset LatexCommand \ref{cha:tipo3}
1676 (cuenta tanto con bloques como con registros variables), hereda los inconvenien
1677 tes (y ventajas) de ambos, más los propios.
1678 Al implementar este tipo de archivo se puso enfásis en la eficiencia mientras
1679 esta no comprometa la mantenibilidad del código, es por esto que en algunas
1680 circunstancias no se hace un uso óptimo del espacio.
1683 La implementación de este tipo de archivo puede ser encontrada en
1687 mientras que su interfaz pública está disponible en
1697 El archivo está compuesto por la
1702 \begin_inset LatexCommand \pageref{sec:cabecera_gral}
1707 El valor que toma en este tipo de archivo es 0 (o el valor simbólico
1716 Luego le sigue una cabecera propia del archivo (un
1720 , 4 bytes) que almacena el tamaño del bloque que usa el archivo.
1721 De esta menera, al abrir un archivo de este tipo no se necesita tener ninguna
1722 información sobre él.
1723 A esta cabecera le siguen cero o más bloques del tamaño fijo especificado
1724 en la cabecera antes mencionada.
1730 +-----------+-----------+------------------------//-+
1733 | tipo | tam bloque| Cero o más bloques ...
1741 +-----------+-----------+------------------------//-+
1744 /- 4 bytes -/- 4 bytes -/
1747 Organización física de un bloque
1750 Cada bloque no guarda información en sí, sólo se comporta como un contenedor
1752 Esto no significa que un bloque no tenga utilidad, el bloque es utilizado
1753 para proveer un acceso semi-aleatorio a los registros.
1754 Para esto se utiliza el archivo de índice (ver página
1755 \begin_inset LatexCommand \ref{sec:idx}
1759 ), que almacena pares [identificador de registro, número de bloque].
1760 Para que sea suficiente este único índice para hallar un registro (siendo
1761 que puede haber más de un registro por bloque), es necesario
1763 alinear los registros a izquierda
1766 Esto significa que hay que asegurar que siempre los registros en un bloque
1767 se presenten de forma consecutiva, jamás permitiendo que haya un espacio
1768 libre entre registros (en un mismo bloque).
1771 Podemos ver un ejemplo de esto en forma gráfica:
1774 bloque N-1 | bloque N | bloque N+1
1777 /----------+------------+------------+---------------+-----------/
1782 | registro 1 | registro 2 | espacio libre |
1787 /----------+------------+------------+---------------+-----------/
1790 /------------- tamaño del bloque ---------/
1793 De esta forma, una vez obtenido el número de bloque, se pueda recorrer secuencia
1794 lmente hasta encontrar el registro deseado.
1795 A fin de llevar el conteo de espacio libre se utiliza el archivo de control
1796 de espacio libre (ver página
1797 \begin_inset LatexCommand \ref{sec:fsc}
1801 ), de forma tal que no sea necesario recorrer secuencialmente en busca de
1802 espacio libre al hacer una inserción.
1805 Puede darse un caso excepcional en el que un registro sea más grande que
1806 un bloque, en este caso el registro se almacenará en N bloques consecutivos
1807 (siendo N la cantidad de bloques que necesita el registro), ocupando completos
1808 los todos los bloques a excepción del último, en el que posteriormente
1809 se pueden agregar más registros.
1810 \layout Subsubsection
1813 \begin_inset LatexCommand \label{sub:tipo1_reg}
1817 Organización física de un registro.
1820 El registro es el que representa al dato realmente que se quiere almacenar.
1821 Para representar ese dato se necesita una determinada información de control,
1822 tanto para poder identificar el registro en un bloque (en búsquedas secuenciale
1823 s dentro del bloque) como para saber su longitud (dado que este tipo de
1824 archivo utiliza registros de tamaño variable).
1827 Siguiendo la metodología general de E
1828 \begin_inset Formula $\mu$
1831 FS, se optó por incluir esta información de control como una cabecera al
1832 comienzo del registro, siguiendo a esta los datos en sí.
1833 La cabecera está compuesta por un identificador (
1837 ) de registro (EMUFS_REG_ID, 4 bytes) seguido por el tamaño (
1841 ) del registros (EMUFS_REG_SIZE, 4 bytes).
1842 Podemos ver gráficamente como se se compone un registro:
1848 +-----------+-----------+------------------+
1851 | id | tamaño | datos ...
1855 +-----------+-----------+------------------+
1858 /- 4 bytes -/- 4 bytes -/- [tamaño] bytes -/
1859 \layout Subsubsection
1862 \begin_inset LatexCommand \label{sub:tipo1_reg_multi}
1866 Organización física de un registro más grande que un bloque (registro
1873 Puede darse el caso excepcional en que un registro sea de mayor longitud
1875 Al ser una situación excepcional, no siempre se resuelve de la forma más
1876 eficiente ni se mínimiza el espacio ocupado por datos de control (como
1877 se dijo anteriormente, se prefirió conservar la simpleza del código, adoptando
1878 algoritmos generales aunque no sea de la forma más eficiente o maximizando
1879 el uso del espacio para no perjudicar la mantenibilidad).
1882 Para menejar un registro
1886 se optó por limitarlo a la siguiente estructura (suponiendo que el registro
1887 ocupa N bloques, con N > 1 y que un
1891 es una porción del registro que entra en un bloque):
1898 se almacenan en bloques completos consecutivos.
1901 El último fragmento se almacena al comienzo del bloque inmediatamente posterior
1905 Cada framento posee las cabeceras mencionadas en la sección
1906 \begin_inset LatexCommand \ref{sub:tipo1_reg}
1910 , cuyo contenido es el siguiente:
1918 se almacena el identificador único obtenido al hacer el alta.
1925 se almacena el tamaño del
1929 actual más los tamaños de los
1933 posteriores, quedando en el primer
1937 el tamaño completo del registro y en el último sólo el tamaño del
1945 Como puede observarse, la información de control en los
1949 intermedios puede ser redundante, pero se conserva para poder realizar
1950 algoritmos genéricos (que se basan en que al principio de un bloque, si
1951 no está vacío, hay una cabecera de un registro) y para facilitar chequeos
1952 de integridad del archivo.
1955 A continuación se presenta un ejemplo gráfico de un registro multibloque
1956 de 10 bytes (de contenido
1957 \begin_inset Quotes eld
1961 \begin_inset Quotes erd
1964 ) almacenado en un archivo con bloques de 4 bytes:
1967 | bloque 0 | bloque 1 | bloque 2
1970 +-------------------+-------------------+-------------------+-//-+
1973 | registro 0 - 1/3 | registro 0 - 2/3 | registro 0 - 3/3..|
1980 |+----+-----+------+|+----+-----+------+|+----+-----+----+..| // |
1983 || id | tam | datos||| id | tam | datos||| id | tam |dato|..|
1990 ||----+-----+------+||----+-----+------+||----+-----+----+..| // |
1993 || 0 | 10 | 1234 ||| 0 | 6 | 5678 ||| 0 | 2 | 90 |..|
2000 |+----+-----+------+|+----+-----+------+|+----+-----+----+..| // |
2003 +-------------------+-------------------+-------------------+-
2010 Funciones principales
2013 Las funciones principales son las necesarias para completar la estructura
2015 \begin_inset LatexCommand \pageref{sub:EMUFS}
2022 Lectura de registros
2025 Para leer un registro se hace uso del archivo de índice (ver página
2026 \begin_inset LatexCommand \pageref{sec:idx}
2030 ), obteniéndose el número de bloque en donde está almacenado el registro
2032 Una vez obtenido, se carga en memoria el bloque entero y se busca secuencialmen
2033 te en él (leyendo la cabecera de cada registro y salteando los datos) hasta
2034 encontrar el registro pedido.
2035 Una vez encontrado se lo copia y devuelve.
2038 Si se tratara de un registro
2043 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2047 ), se procede forma similar, sólo que se cargan en memoria uno a uno los
2048 bloques que componen el registro y se van copiando (y uniendo) los
2057 emufs_tipo1_leer_registro()
2063 Para realizar el alta de un registro, lo primero que se obtiene es un identifica
2064 dor, buscando primero en el archivo de identificadores recuperables (pág.
2066 \begin_inset LatexCommand \ref{sec:did}
2070 ) y de no haber ninguno, buscando el mayor identificador presente en el
2071 archivo de índice (pág.
2073 \begin_inset LatexCommand \ref{sec:idx}
2078 El paso siguiente es buscar un bloque con espacio libre suficiente como
2079 para almacenar el registro (y su cabecera) en el archivo de control de
2082 \begin_inset LatexCommand \ref{sec:fsc}
2086 ) y cargarlo completo en memoria.
2087 De no encontrarse, se crea un bloque nuevo al final de archivo.
2088 En el bloque cargado en memoria, se agrega el registro nuevo (con su cabecera)
2089 al comienzo del espacio libre (calculado a partir del tamaño del bloque
2090 y el espacio libre en bloque) y se lo graba en disco.
2091 Finalmente se agrega (o actualiza) el identificador al archivo índice y
2092 el espacio libre en el bloque.
2095 Si el registro ocupara más de un bloque (ver sección
2096 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2100 ), se buscan N bloques consecutivos (todos los que necesite el registro)
2101 absolutamente libres
2107 Incluso el último bloque debe estar absolutamente libre para cumplir con
2108 las condiciones presentadas en la sección
2109 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2116 y graba bloque a bloque cada
2120 del registro (con sus cabeceras intermedias), al último
2124 se lo trata de forma análoga a un registro
2129 Por cada bloque utilizado se actualiza el archivo de control de espacio
2135 emufs_tipo1_agregar_registro()
2141 Al eliminar un registro lo primero que se hace es actualizar los archivos
2142 de índice y de indentificadores recuperables, poniendo como número de bloque
2147 y agregando el identificador del registro a borrar respectivamente.
2148 También se actualiza el archivo de control de espacio libre por cada bloque
2149 (en caso de ser más de uno, en registros
2153 , se actualizan todos los bloques) y se carga el bloque en memoria para
2156 alinear los datos a izquierda
2158 (en caso de ser un registro
2162 , esto se realiza sólo para el último bloque).
2163 Para alinear los datos, se recorre secuencialmente en bloque (leyendo la
2164 cabecera de cada registro y salteando los datos) hasta encontrar el registro
2166 Encontrado el registro, se copian todos los bytes que se encuentran entre
2167 el fin del registro a borrar y el fin del bloque, en el comienzo del bloque
2173 emufs_tipo1_borrar_registro()
2176 Modificación de registros
2179 Se optó por un algoritmo simple y general, que usa las funciones de alto
2180 nivel mencionadas hasta ahora.
2181 Simplemento borra el registro y vuelve a crearlo.
2182 Al recuperar el último identificador de registro borrado, nos aseguramos
2183 de que se mantenga el identificador del registro.
2188 emufs_tipo1_modificar_registro()
2191 Obtención de estadísticas
2194 Es una función bastante simple, con una única complicación que mencionaremos
2198 Para obtener las máximas desviaciones, cantidad total de espacio libre,
2199 cantidad de registros y tamaño de los archivos auxiliares se utilizan las
2200 funciones apropiadas de los archivos auxiliares (ver secciones
2201 \begin_inset LatexCommand \ref{sec:idx}
2206 \begin_inset LatexCommand \ref{sec:fsc}
2211 \begin_inset LatexCommand \ref{sec:did}
2218 Para obtener la cantidad de bloques se hace el siguiente calculo:
2221 cant_bloques = (tamaño_archivo_datos - tamaño_cabecera_archivo_datos)
2227 Hasta aquí no hay mayores inconvenientes.
2228 El problema se presenta para calcular el tamaño de la información de control
2229 utilizada por el archivo de datos; se utiliza el siguiente cálculo:
2232 tam_info_control_datos = tamaño_cabecera_archivo_datos
2235 + cant_registros * tamaño_cabecera_registro;
2238 Aunque a simple vista esto parece acertado, no contempla el caso de los
2244 \begin_inset LatexCommand \pageref{sub:tipo1_reg_multi}
2248 ), estos registros almacenan
2250 tamaño_cabecera_registro * N
2256 es la cantidad de bloques que ocupan.
2257 Salvar este caso sería muy costoso, porque habría que recorrer el archivo
2258 registro a registro,
2266 e ir contando todas las cabeceras de registro que aparecen (similar a lo
2267 que se hace en la compactación, ver sección
2268 \begin_inset LatexCommand \ref{sub:tipo1_compact}
2273 Al tratarse este de un caso excepcional, se optó por mantener la función
2274 simple ya que funciona bien en la mayoría de los casos.
2279 emufs_tipo1_leer_estadisticas()
2283 \begin_inset LatexCommand \label{sub:tipo1_compact}
2287 Compactación del archivo de datos
2290 Esta función es una de las más simples, porque se limita a un algoritmo
2291 muy simple que utiliza las funciones de
2295 antes nombradas para realizar su tarea.
2296 Básicamente recorre el archivo de índices de registros, de comienzo a fin,
2297 leyendo el registro, borrándolo y volviéndolo a insertar.
2298 Si había espacio libre en un bloque anterior al que estaba, será insertado
2299 en él, si no volverá a grabarse en el lugar en que estaba.
2300 De esta forma se aprovechan todos los espacios libres intermedios, concluyendo
2301 con un archivo igual o más pequeño que el original.
2304 Esta implementación no es la más eficiente, pero siendo que esta es una
2305 operación costosa y excepcional por naturaleza, se optó por mantener el
2306 algoritmo simple a costo de un poco de eficiencia.
2311 emufs_tipo1_compactar()
2314 Detalles de implementación (funciones internas, ver si lo ponemos o no)
2318 \begin_inset LatexCommand \label{cha:tipo2}
2322 Archivo sin bloques y registros de longitud variable
2325 Este tipo de archivo nos traerá a la mesa la particularidad de grabar registros
2326 de longitud variable sin realizar su agrupación en bloques, y como veremos
2327 en la siguiente sección, tambien permitirá la administración de gaps que
2328 queden en el archivo luego de operaciones de baja de registros.
2334 Este tipo de archivo realizará el almacenamiento de registros de longitud
2335 variable en disco, su borrado y modificación sin la utilización de bloques
2337 Su implementación se encuentra en los archivos fuente (
2348 Los archivos del tipo 2, presentarán al comienzo del mismo un header compuesto
2349 simplemente por un dato del tipo EMUFS_Tipo (int) el cual indicará el tipo
2350 de archivo en cuestión.
2353 Para poder entender mejor la organización fisica de este tipo de archivo,
2354 tomemos el caso hipotético en el que se encuentran grabados
2358 (comenzando desde registro 0) de
2367 Supongamos también que entre el registro 0 y 1 se encontraba un
2369 registro de 10 bytes
2384 Si miramos al archivo de datos (.dat) en el disco nos encontraremos con
2386 \begin_inset Float figure
2393 Organización física de los registros en disco
2397 \begin_inset Graphics
2398 filename graphics/Example1.png
2409 Como se puede observar, a nivel físico cada registro grabado esta compuesto
2410 por un Header cuyo tamaño total es de 8 bytes (
2418 ), y posteriormente el registro (bloque de datos) en sí.
2419 Luego se encuentra el espacio libre de 18 bytes dejado por el registro
2420 de 10 bytes eliminado (10 bytes de datos + header de 8 bytes) y finalmente
2421 el segundo registro mencionado.dsds
2424 Comportamiento Particular de los Archivos Auxiliares
2427 Como fue explicado al inicio de la documentación, la implementación de cualquier
2428 a de las tres organizaciones físicas de archivos presenta la necesidad de
2429 poseer tres archivos auxiliares que actuarán como índice de direcciones
2434 ), administrador de espacio libre (
2438 ) y administrador de Id's liberados (
2445 No obstante, cada tipo de organización presentara sus particularidades respecto
2446 de estos tres archivos, las cuales describiremos a continuación en caso
2448 \layout Subsubsection
2450 Archivo índice o de posiciones relativas (.idx)
2457 ), permite la localización de los registros en el .DAT de forma directa,
2458 mediante la obtención de su offset o posición relativa respecto del inicio
2463 en donde se encuentra un registro dado, indicado por su ID.
2466 Así pues, si tomamos el ejemplo descripto al inicio de este capítulo, tendremos
2467 las siguientes entradas en el archivo índice
2472 \begin_inset Float table
2479 Organización física del archivo de índice o posiciones relativas.
2483 \begin_inset Tabular
2484 <lyxtabular version="3" rows="3" columns="3">
2486 <column alignment="center" valignment="top" leftline="true" width="0">
2487 <column alignment="center" valignment="top" leftline="true" width="0">
2488 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
2489 <row topline="true" bottomline="true">
2490 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2500 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2510 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2518 <row topline="true">
2519 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2529 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2539 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2544 El primer registro (reg0) comienza en el byte 4
2548 <row topline="true" bottomline="true">
2549 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2557 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2567 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2572 El segundo registro (reg1) comienza en el byte 60
2592 LOCATION indica donde comienza el header del registro buscado, y por consiguien
2593 te luego del header tendremos el registro en sí (los datos).
2594 \layout Subsubsection
2596 Achivo de Gaps / Espacios Libres (.fsc)
2599 El archivo de espacios libres o gaps (.fsc), tiene como función la administración
2600 del espacio libre o gaps (agujeros), generados por previas eliminaciones
2601 de registros en el archivo de datos.
2602 El mismo, nos indicará donde hay lugar para insertar un nuevo registro
2603 (se podrán insertar en algún gap acorde, o bien al final del archivo).
2604 Este archivo será utilizado tambien para el proceso de compactación de
2605 un archivo, explicado luego.
2608 Así pues, si tomamos el ejemplo descripto al inicio del documento, tendremos
2609 las siguientes entradas en el archivo índice
2614 \begin_inset Float table
2621 Organización física del archivo de
2625 o control de espacio libre.
2629 \begin_inset Tabular
2630 <lyxtabular version="3" rows="2" columns="3">
2632 <column alignment="center" valignment="top" leftline="true" width="0">
2633 <column alignment="center" valignment="top" leftline="true" width="0">
2634 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
2635 <row topline="true" bottomline="true">
2636 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2646 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2656 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2664 <row topline="true" bottomline="true">
2665 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2675 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2685 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2690 18 bytes libres a partir del byte 42 del .dat
2710 Por requerimiento del algoritmo de compactación, los gaps se graban en
2711 forma ordenada en el (.fsc).
2712 (El orden se corresponde con lo que hay en el
2717 \layout Subsubsection*
2722 Si bien la utilización concreta de los GAPS será explicada posteriormente
2723 en la ALTA y BAJA de registros, debemos remarcar la funcionalidad de MERGING
2724 que posee nuestro sistema FSC.
2727 Ante la eliminación de un registro del archivo de datos, se generara por
2728 consiguiente un gap o espacio libre en alguna posición del archivo.
2729 Ese gap deberá ser registrado en el archivo de gaps (.fsc).
2730 Ahora bien, nuestro sistema de gaps, contemplará como es debido, la posibilidad
2731 de que se haya eliminado un registro que posee un GAP por delante, un GAP
2732 por detrás, o bien un GAP por delante y por detrás del mismo.
2735 Nuestro sistema actuará en consecuencia, realizando un merge de los espacios
2736 libres, y unificándolos en una UNICA entrada en el archivo .fsc, que contendrá
2737 como dato de freespace, la suma correspondiente de los espacios libres
2739 \layout Subsubsection
2741 Archivo de ID's liberados (.did)
2744 El archivo de ID's liberados no presenta ningún aspecto particular en este
2745 tipo de organización.
2746 Remitirse al capítulo correspondiente a los archivos auxiliares para consultar
2747 su estructura y funcionamiento.
2750 Funciones Principales
2765 se encuentran las cabeceras y la implementación de las funciones principales
2766 respectivamente, las cuales dan funcionalidad a esta organización.
2770 A continuación se comentará el funcionamiento algunas de las mas importantes.
2773 Lectura de registros
2776 Como se vió al comienzo, los registros en este tipo de archivo no se encuentran
2777 agrupados en bloques de ninguna índole y estan dispersos a lo largo del
2778 archivo, con la particularidad de que pueden existir gaps o espacio libre,
2779 entre dos registros dados.
2782 Por ende la lectura de registros en este tipo de organización es muy simple
2783 y dada la inexistencia de bloques, el procedimiento será el siguiente:
2786 Se determina el offset en bytes, donde comienza el registro deseado, a través
2787 de su ID, buscando la misma en el archivo índice (
2794 Ya determinada la posición física del registro dentro del archivo de datos
2799 ), nos posicionamos en la misma, y leemos el header del registro (
2808 Contando así con el tamaño del registro, procedemos a leer el mismo (los
2809 datos), dando por finalizada la lectura.
2814 emufs_tipo2_leer_registro()
2820 En el proceso de alta de registros entrarán en juego dos archivos descriptos
2823 sección de archivos auxiliares
2825 , siendo estos el archivo índice (
2829 ), y el archivo de gaps / espacios libres (
2836 Así pues, a la hora de realizar una inserción de un registro en el archivo
2837 de datos, el procedimiento será el siguiente:
2840 Calculamos el espacio que necesitaremos para el registro: sizeof(
2848 ) + sizeof(registro).
2851 Determinamos donde debemos insertar el registro, ya sea un gap donde entre,
2852 o bien al final del archivo.
2855 Insertamos el registro e información de control (
2863 ), en la posición indicada en el paso 2.
2866 En caso de haber utilizado un GAP, actualizamos el espacio libre restante
2867 en el mismo y en caso de que se haya utilizado al totalidad del GAP, se
2868 lo elimina del archivo (
2875 Actualizamos la entrada correspondiente al registro ingresado (determinada
2876 por su RegID), en el archivo índice (
2880 ), indicando su offset donde podrá ser accedido luego.
2885 emufs_tipo2_agregar_registro()
2891 En el proceso de baja de registros entrarán en juego los tres archivos descripto
2894 sección de archivos auxiliares
2896 , siendo estos el archivo índice (
2900 ), el archivo de gaps / espacios libres (
2904 ) y el archivo de ID's liberados (
2911 Dado que en la implementación de este tipo de organización física contamos
2912 con los gaps o espacios libres entre registros, no se eliminará fisicamente
2913 el registro del archivo de datos (
2917 ), pues entonces carecería de sentido el archivo anteriormente mencionado
2923 En cambio, se agrega el gap dejado por la eliminación a dicho archivo,
2924 y se marca fisicamente en el archivo de datos la eliminación mediante un
2925 fill de los bytes correspondientes con un caracter nulo.
2926 (hexa 00 y con el propósito de probar fehacientemente que el sistema funciona).
2929 El proceso de baja o eliminación de un registro constará luego de los siguientes
2933 Se obtiene el offset o posición relativa en donde se encuentra grabado el
2934 registro dentro del archivo de datos.
2937 Se obtiene el tamaño del registro y se realiza un dummyfill del sector del
2938 archivo correspondiente al registro que se está dando de baja.
2939 (Se rellena la zona correspondiente a su header+data).
2942 Se agrega el GAP generado al archivo de gaps o espacios libres, y en caso
2943 de haberse generado un GAP lindante con otro GAP, se realizará un merge
2944 de los mismos y se los registrará bajo una única entrada en el archivo
2945 de espacios libres (.fsc).
2948 Se agrega el ID que fue liberado, al archivo de ID's liberados (
2952 ), al final del mismo (
2959 Se marca en el archivo índice (
2963 ) la eliminación, mediante el valor ¨-1¨ en el registro correspondiente
2964 al registro recién eliminado (se le cambia el valor al n-esimo registro,
2965 donde N = IDReg del reg eliminado).
2970 emufs_tipo2_borrar_registro()
2973 Modificación de registros
2976 Dada la naturaleza del archivo de ID's liberados, y el manejo de espacio
2977 libre del que consta esta organización de archivo, el proceso de modificación
2978 de un registro se limita a los siguientes pasos:
2981 Se realiza la lectura del registro, mediante el respectivo procedimiento
2982 ya desarollado anteriormente.
2985 Una vez que se cuenta con los nuevos datos modificados, se procede a dar
2986 de baja el registro que ha sido modificado, e inmediatamente después se
2987 realiza una inserción con los nuevos datos.
2996 Como fue indicado, dada la naturaleza de PILA del subsistema de administración
2997 de ID liberados, es asegurado que la nueva inserción del registro modificado
2998 se realizará con el mismo RegID.
3003 emufs_tipo2_modificar_registro()
3006 Obtención de estadísticas
3009 Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
3010 cantidad de bloques, cantidad de registros, espacio libre total, espacio
3011 libre promedio, espacio libre máximo y mínimo, etc.
3014 Esta información es el resultado de ciertos cálculos realizados tanto en
3015 el archivo de datos como en los archivos índice.
3018 Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
3019 del archivo de datos, espacio libre total, cantidad de registros, cantidad
3020 de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
3026 emufs_tipo2_leer_estadisticas()
3029 Compactación del archivo de datos
3032 Asi como los otros dos tipos de datos, el que nos compete también cuenta
3033 con la posibilidad de realizar la compactación de datos cuando el usuario
3034 lo desee, justificando todos los registros a izquierda, eliminando así
3035 los gaps existentes y decrementando el tamaño del archivo en disco (truncandolo
3039 Para poder comprender como hemos implementado el proceso de recompactación
3040 en nuestro tipo de archivo 2, nos ayudaremos de esquemas a través de los
3041 cuales iremos describiendo el proceso.
3042 Notemos antes, que el proceso de compactación esta directamente ligado
3043 con el archivo de gaps o espacios libres (
3050 Comenzemos con el siguiente cuadro situacional:
3051 \begin_inset Float figure
3058 Archivo con gaps entre registros previo a compactación
3062 \begin_inset Graphics
3063 filename graphics/Compact1.png
3075 Partiendo de esta base, el algoritmo de compactación tomará en su inicio
3076 al primer gap existente dentro del archivo de datos, en este caso llamado
3082 Luego, establecerá que el
3086 a partir de donde se quieren mover datos, sera:
3089 StartGap0 + SizeGap0 = EndGap0 = Source
3092 Lo cual no es nada más y nada menos que lo obvio, la fuente a partir de
3093 donde se mueven los datos, sera el fin del primer gap, donde comienzan
3099 ) del movimiento, se establece inicialmente, el inicio del gap, o sea
3101 StartGap0 = Destination
3106 Luego, el algoritmo entrara en un bucle while (mientras haya bucles por
3107 levantar), el cual trabajara hasta el final de la compactación de la siguiente
3118 Se levanta el proximo gap al levantado en una instancia previa.
3119 En este ejemplo, durante el primer loop del while, se levantará
3124 Luego, se calcula cuantos bytes hay que mover hacia el Destination de la
3148 Lo cual nuevamente es lógico pues querremos mover lo que se encuentra entre
3149 el final del primer gap levantado y el inicio del siguiente).
3152 Se realiza el movimiento de los datos, utilizando las direcciones
3160 , así como la variable
3164 que nos indica cuantos bytes transferir.
3170 La transferencia se hace de a chunks de 25 bytes + un resto segun el valor
3174 Se establece como gap de referencia, al ultimo gap leido (En este caso se
3187 ) y termina el código de repetición del bucle, dando lugar a la carga del
3188 siguiente gap en el inicio del mismo.
3196 Luego del primer bucle, el archivo se vera de la siguiente forma:
3197 \begin_inset Float figure
3204 Archivo con gaps en disco luego del primer bucle de compactación
3208 \begin_inset Graphics
3209 filename graphics/Compact2.png
3220 Notemos que al final de la porción de datos de los bytes movidos (donde
3225 ), hay basura que será pisada por el próximo movimiento.
3228 En el próximo loop, el bucle levantará un nuevo gap, y utilizando el gap
3229 anterior (En esta caso el Gap anterior será
3233 ) como referencia, realizará los mismos cálculos, desde donde transferir
3234 y cuantos bytes mover.
3235 (El destino es solo establecido inicialmente por código, y para el resto
3236 del algoritmo es el lugar donde quedo el puntero destination luego de la
3240 Una vez que se salga del bucle while, se realizará un último movimiento
3241 preprogramado, donde la fuente (
3245 ) será el final del ultimo gap, y la cantidad de bytes a mover será lo que
3246 se encuentre luego del mismo hasta el fin de archivo.
3249 Source = StartLastGap + SizeLastGap = EndLastGap
3252 Mustmove_bytes = Datsize - Source
3255 Damos por terminada así, la explicación del algoritmo de compresión el cual
3256 para el caso del tipo 2, es realmente bastante sencillo.
3261 emufs_tipo2_compactar()
3264 Consideraciones y Políticas de Diseño
3267 Se han tomado ciertas consideraciones para algunos casos particulares que
3268 se pueden presentar durante el uso/ejecución de la aplicación, así como
3269 tambien politicas respecto del diseño e implementación del sistema:
3272 En la organización física tipo 2 para los registros que se graban en disco
3273 hemos decidido utilizar como encabezado de cada uno de ellos, los datos
3274 [ID_REG][REG_SIZE], los cuales fueron detallados previamente.
3275 Si bien se podría haber descartado el grabado del ID del registro en el
3276 archivo de datos y puede parecer redundante, dado que poseemos el archivo
3277 índice con el offset directo, el mismo se lo graba por distintos motivos:
3281 A) En caso de la corrupción del archivo índice (.idx), podremos gracias a
3282 que poseemos en el archivo de datos, el ID de cada registro, recrear dicho
3283 índice, ayudándonos del archivo de espacios libres (
3287 ), para poder saltear los espacios libres y e ir recorriendo secuencialmente
3288 los registros, reconstruyendo así el índice en cuestión.
3289 (esta función de reconstrucción no pudo ser implementada para esta entrega,
3290 pero es una posibilidad real).
3294 B) Luego de un proceso de recompactación, los espacios libres que pudieron
3295 haber existido en el archivo de datos (
3299 ), son eliminados y los registros han cambiado de posición.
3300 Por ello, recorriendo secuencialmente por única vez el archivo de datos,
3301 se procede a la actualización / reconstrucción del índice de direcciones
3309 Si se desea insertar un registro y no se puede hayar un gap o espacio libre
3310 donde quepa, se los inserta al final del archivo.
3313 Ante una operación de baja de un registro, el mismo no es físicamente borrado
3314 del archivo de datos (
3318 ), simplemente los bytes que ocupa son llenados con hexa (00).
3319 Paralelamente, se procede a actualiza el archivo índice, insertando como
3320 valor de OFFSET para el registro eliminado, el valor ¨-1¨, indicando así
3321 la inexistencia del registro para el futuro, y por otro lado se genera
3322 la entrada de espacio libre en el archivo de gaps (
3329 La reutilización de ID's liberados por previas operaciones de baja de registros,
3330 se ve implementada por el archivo de ID liberados (.did), y su comportamiento
3331 es el de una pila por lo que el último ID liberado, sera el próximo a ser
3335 Como fue explicado en la implementación del archivo índice, existe una correspon
3336 dencia 1 a 1 entre los registros allí presentes (en el .idx) y los ID's de
3337 los registros, por lo cual el registro N-ésimo del archivo índice, será
3338 el correspondiente al registro de datos cuyo ID es igual a N.
3341 El proceso de compactación de archivos, realiza los movimientos de información
3342 requeridos para dicho propósito de a chunks de 25 bytes por vez.
3343 Este valor es fijo, pero se lo podría hacer parametrizable mediante la
3344 GUI en próximas entregas.
3348 \begin_inset LatexCommand \label{cha:tipo3}
3352 Archivo con bloques parametrizados y registros de longitud constante
3355 Las distintas organizaciones de archivos buscan aprovechar al máximo el
3356 espacio del archivo.
3359 En este caso veremos que sucede luego de agregar y borrar una gran cantidad
3360 de registros del archivo, lo que provoca como consecuencia directa la fragmenta
3361 ción del archivo, es decir, quedan huecos entre un registro y otro, lo que
3362 produce un desperdicio de espacio.
3365 La implementación de este tipo de archivo puede ser encontrada en
3369 mientras que su interfaz pública está disponible en
3379 Esta organización guarda los registros pertenecientes al archivo en bloques
3380 de tamaño parametrizado, de modo que intentará guardar la mayor cantidad
3381 de registros que quepan en un bloque.
3385 Así como los graba, también tendrá la posibilidad de leer registros y borrarlos
3389 El archivo estara compuesto por una cabecera que da información sobre el
3390 tipo de organización, el tamaño de los bloques y el tamaño de los registros.
3393 Organización Física de un Bloque
3396 Cada bloque será capaz de contener la cantidad de registros enteros que
3398 De esta manera un registro que no entre completamente en el bloque deberá
3399 almacenarce en un bloque diferente.
3402 Los bloques no contienen ninguna información adicional, solo se conoce su
3403 tamaño y se usa para delimitar
3404 \begin_inset Quotes eld
3408 \begin_inset Quotes erd
3411 zonas en el archivo.
3414 Organizacion Física de Registros
3417 Cada registro se almacena en un bloque, y contiene una cabecera que indica
3422 por este motivo al realizar la busqueda de espacio en un bloque se lo hará
3423 preguntando por el tamaño del registro más
3425 sizeof(EMUFS_REG_ID).
3429 Organización Física de Registros Multibloque
3432 Al ser los registros de longitud constante, se ha adoptado que un registro
3433 multibloque nunca podra estar almacenado en algún lugar que no sea el comienzo
3435 De esta manera se puede calcular cuantos bloques ocupará un registro y
3436 se podrá solicitar lugar para almacenarlo con la ayuda de la función
3438 emufs_fsc_buscar_n_lugares(),
3440 que es muy importante para evitar el solapamiento de registros.
3441 Esta consideración acarrea como consecuencia directa un alto costo en términos
3442 del espacio desperdiciado.
3445 Funciones Principales
3456 se encuentran las cabeceras y la implementación de las funciones principales
3457 respectivamente, las cuales dan funcionalidad a esta organización.
3460 A continuación se comentará la descripción de algunas acciones importantes.
3466 La lectura de un registro se realiza con la ayuda del archivo .
3470 el cual contiene la información de la posición del registro dentro del
3472 Una vez leida esta información, se recupera el bloque (en su totalidad)
3473 del archivo y se busca secuencialmente el registro con el
3482 emufs_tipo3_leer_registro()
3488 Graba un registro en un bloque donde haya espacio suficiente, y si no crea
3489 un nuevo bloque y lo agrega al final del archivo.
3492 Luego de grabar un registro, actualiza los archivos de índice .idx y .fsc
3493 para mantener la coherencia.
3496 Cuando nos encontramos con registros multibloque, se calcula cuantos bloques
3497 ocupará el registro de la siguiente manera: Cantidad de Bloques = 1 + Tamaño
3498 del Registro/(Tamaño del Bloque-Sizeof(EMUFS_REG_ID)
3501 y con esta información se realiza un ciclo
3505 que grabará tantas veces como sea necesario.
3510 emufs_tipo3_grabar_registro()
3516 Borra un registro del archivo de datos, para esto levanta el bloque al que
3517 pertenece el archivo y ajusta los demás registros justificandolos hacia
3521 Cabe destacar que para dar de baja un registro no hace falta borrarlo del
3522 archivo de datos, solo es necesario borrar las entradas en los archivos
3523 de índice, pero cuando se realiza el ajuste el algoritmo toma porciones
3524 del bloque del tamaño de un registro mas su encabezado - comenzando desde
3525 el siguiente al que fue borrado - y copia (sobreescribe) sobre el anterior.
3526 De esta manera, la información correspondiente al registro borrado no estará
3527 presente en el archivo de datos.
3528 Esto es una consecuencia del ajuste al borrar un registro, pudiendo no
3529 ser así, si no se realizara el mismo.
3532 En el caso de los registros multibloque, se eliminará la porción del registro
3533 contenida en el primer bloque y se actualizarán de manera conveniente los
3534 archivos índice, para restaurarlos a un valor verdadero.
3539 emufs_tipo3_borrar_registro()
3545 Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
3546 cantidad de bloques, cantidad de registros, espacio libre total, espacio
3547 libre promedio, espacio libre máximo y mínimo, etc.
3550 Esta información es el resultado de ciertos cálculos realizados tanto en
3551 el archivo de datos como en los archivos índice.
3554 Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
3555 del archivo de datos, espacio libre total, cantidad de registros, cantidad
3556 de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
3562 emufs_tipo3_leer_estadisticas()
3565 Compactar el Archivo
3568 Esta función intenta reorganizar el archivo de manera que el espacio libre
3569 sea lo menor posible, recordando siempre que un registro no puede ser almacenad
3570 o en mas de un bloque excepto que el tamaño del registro sea mayor que el
3574 Para realizar esto, se aprovecha la funcionalidad de
3576 emufs_tipo3_grabar_registro()
3578 ya que esta tiene la capacidad de determinar una posición mas eficiente
3579 en el archivo para un registro.
3580 Por esto lo que se hace es levantar uno por uno los registros y volverlos
3581 a grabar, de ese modo todos los
3585 que pudieron haberse formado por la eliminación de registros serán cubiertos
3589 Al estar utilizando recuperación de
3593 borrados, esto me asegura que el registro borrado-guardado conservará el
3597 Al finalizar este proceso se verifica si existen bloques vacios para truncar
3599 Lo mismo se debe hacer con el archivo de espacios libres .
3603 el cual disminuye su tamaño también.
3608 void emufs_tipo3_compactar()
3611 Consideraciones y Políticas de Diseño
3614 Se han tomado ciertas consideraciones para algunos casos particulares que
3615 se pueden presentar durante el uso/ejecución de la aplicación.
3618 Cada registro tiene un encabezado que indica el
3625 Si el tamaño del registro es mayor que el tamaño del bloque el registro
3626 se particionará en la cantidad de bloques que sea necesario, pero siempre
3627 se guardará desde el comienzo de un bloque, esto quiere decir que nunca
3628 se podrá encontrar un comienzo de registro en algún lugar de un bloque
3629 que no sea el comienzo del mismo.
3632 Si el registro se divide en mas de un bloque, se le coloca el id como encabezado
3633 igualmente, pero en el archivo .
3637 solo se guarda el primer bloque.
3642 se actualizan todos los bloques con el espacio libre que realmente tienen.
3648 Las comparaciones, pruebas, etc...
projects / z.facultad / 75.06 / emufs.git / blob