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
770 Así pues, cuando se utilize la estructura para por ejemplo leer un registro,
771 sucedera lo siguiente:
774 efs->leer_registro(params) -- calls --> emufs_tipo3_leer_registro(params)
777 Como se puede observar, la estructura
781 permitirá el manejo de cualquier tipo de archivo, a través del mismo código,
782 dandole gran flexibilidad a nuestro sistema, que podrá expandirse a más
783 tipos de archivos de ser necesario.
789 Acompañando al archivo de datos (
793 ) el cual es responsable de la contención de los registros, tendremos tres
794 archivos auxiliares (
806 ) cuya funcionalidad y propósito pasamos a describir a continuación, sin
807 antes remarcar que los tres archivos poseen una sola implementación para
808 las distintas formas de organización física que hemos implementado (tres
809 para ser mas exactos).
812 Entre las ventajas de poseer la misma implementación se encuentra el tener
813 un API común entre los tres tipos para el manejo de la localización de
814 sus registros, administración de espacio libre e Id's liberados, sin necesidad
815 de realizar n-implementaciones para un mismo objetivo final.
818 Además, la obtención de ciertos datos estadísticos como espacio libre, o
819 cantidad de registros, se realiza a través de la misma interfaz, y también
820 se ha facilitado en cierto grado la re-organización física de un archivo
821 (pasar de un tipo a otro), dado el uso de estos tres archivos auxiliares
822 en común para funciones tan predominantes como índexación, administración
823 de espacio libre y recuperación de Id's.
827 \begin_inset LatexCommand \label{sec:idx}
834 El archivo índice (.idx), permite la localización de los registros en el
835 .DAT de forma directa, mediante la obtención de su offset respecto del inicio
836 del .dat, o nro bloque (segun el tipo de organización física) en donde se
837 encuentra un registro dado, indicado por su
842 Los registros de este archivo se encuentran representados una estructura
843 que indica un número de registro y el bloque u offset en donde se encuentra
847 Es necesario que este archivo esté ordenado por
851 , ya que esto permitirá el acceso directo al mismo, para la rápida obtención
852 del nro de bloque u offset y posterior búsqueda de un registro en el archivo
859 Los registros de este archivo se encuentran representados a nivel codigo
860 por el siguiente tipo de dato interno (
867 typedef struct emufs_idx_t {
873 EMUFS_OFFSET location;
880 \begin_inset Float table
887 Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion
893 <lyxtabular version="3" rows="2" columns="3">
895 <column alignment="center" valignment="top" leftline="true" width="0">
896 <column alignment="center" valignment="top" leftline="true" width="0">
897 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
898 <row topline="true" bottomline="true">
899 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
907 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
915 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
923 <row topline="true" bottomline="true">
924 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
932 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
940 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
945 Indica que el registro de id_reg = 5, se encuentra en el bloque 54
957 \begin_inset Float table
964 Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion
970 <lyxtabular version="3" rows="2" columns="3">
972 <column alignment="center" valignment="top" leftline="true" width="0">
973 <column alignment="center" valignment="top" leftline="true" width="0">
974 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
975 <row topline="true" bottomline="true">
976 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
984 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
992 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1000 <row topline="true" bottomline="true">
1001 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1009 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1017 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1022 Indica que el registro de id_reg = 5, se encuentra en el bloque 54
1042 Como se puede observar, para distintas organizaciones el significado de
1043 los registros en este archivo es diferente y se utilizará de distinta manera
1050 Las declaraciones e implementación se pueden encontrar en
1064 \labelwidthstring 00.00.0000
1072 Los registros del archivo indice (
1076 ), poseen una correspondencia 1 a 1, con los Id's de los registros en el
1082 Con esto, queremos decir que el N-ésimo registro del archivo índice, será
1083 aquél que posea la información para localizar al registro cuyo
1087 es N, dentro del archivo de datos (
1097 Cabe aclarar que por si bien el indice se encuentra ordenado por
1101 , los registros en el archivo de datos, por lo general no lo estarán (ordenados
1107 emufs_idx_buscar_registro(), emufs_idx_get()
1109 \labelwidthstring 00.00.0000
1115 Ante la alta de un registro en el archivo de datos, se insetará un nuevo
1116 registro en el archivo índice, con el id_reg del registro en cuestion,
1117 y el offset u bloque donde se lo haya grabado en disco.
1123 \labelwidthstring 00.00.0000
1129 Ante el borrado de un registro del archivo de datos, se accederá el registro
1130 correspondiente en el índice, y se actualizara su LOCATION, estableciendolo
1131 en el valor especial
1135 , el cual indica que ese registro ha sido eliminado y por ende no se lo
1136 podrá localizar en el futuro.
1137 Como se verá mas adelante, según el tipo de organización física, el registro
1138 puede ser borrado concretamente del .
1149 \labelwidthstring 00.00.0000
1155 Ante la modificación en la posición física de un registro dentro del archivo
1156 de datos (por ejemplo luego del proceso de recompactación, se realizará
1157 la modificación respectiva del campo
1165 emufs_idx_actualizar()
1169 \begin_inset LatexCommand \label{sec:fsc}
1173 Archivo de control de espacio libre
1176 El archivo de espacio libre (
1180 ) (espacio por bloque o gaps en archivo, según el tipo de organización física),
1181 tiene como función la administración del espacio libre, generado por previas
1182 eliminaciones de registros en el archivo de datos.
1183 El mismo, nos indicará donde hay lugar para insertar un nuevo registro.
1186 Para el caso de una organización por bloque, nos dirá en que bloque o si
1187 se debe generar un nuevo bloque.
1188 En el caso de la organización sin bloques, nos indicará en que gap o si
1189 al final del archivo.
1192 Los registros de este archivo se encuentran representados una estructura
1193 que indica un número de bloque u offset y el espacio libre disponible en
1194 el mismo (o apartir del mismo en el caso del offset).
1201 : Por requerimiento del algoritmo de compactación el tipo de organización
1202 física con reg long var, sin bloques, los gaps se graban en forma ordenada
1204 (El orden se corresponde con lo que hay en el .dat).
1210 Los registros de este archivo se encuentran representados a nivel codigo
1211 por el siguiente tipo de dato interno (
1218 typedef struct emufs_fsc_t {
1221 EMUFS_BLOCK_ID marker;
1224 EMUFS_FREE freespace;
1234 \begin_inset Float table
1241 Ejemplo de registro en archivo de control de espacio libre para un archivo
1246 \begin_inset Tabular
1247 <lyxtabular version="3" rows="2" columns="3">
1249 <column alignment="center" valignment="top" leftline="true" width="0">
1250 <column alignment="center" valignment="top" leftline="true" width="0">
1251 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
1252 <row topline="true" bottomline="true">
1253 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1261 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1269 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1277 <row topline="true" bottomline="true">
1278 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1286 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1294 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1299 Indica que en el bloque 12, hay 120 bytes libres al final del mismo.
1311 \begin_inset Float table
1318 Ejemplo de registro en archivo de
1322 para un archivo sin bloques
1326 \begin_inset Tabular
1327 <lyxtabular version="3" rows="2" columns="3">
1329 <column alignment="center" valignment="top" leftline="true" width="0">
1330 <column alignment="center" valignment="top" leftline="true" width="0">
1331 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
1332 <row topline="true" bottomline="true">
1333 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1341 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1349 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1357 <row topline="true" bottomline="true">
1358 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1366 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1374 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1379 Indica que a partir del byte 12 del archivo de datos, hay 120 bytes libres.
1399 Como se puede observar, para distintas organizaciones el significado de
1400 los registros en este archivo es diferente y se utilizará de distinta manera
1404 Funciones principales
1407 Las declaraciones e implementación se pueden encontrar en
1421 \labelwidthstring 00.00.0000
1427 Ante la operación de alta de un registro en el archivo de datos, se realizará
1428 la búsqueda de espacio libre donde este podrá ser insertado.
1429 En el caso de organizaciones con bloques, se buscará en que
1433 se posee espacio suficiente para albergar el nuevo registro (o a partir
1442 bloques consecutivos libres).
1443 En el caso de organizacion sin bloque, se buscará un gap o espacio libre
1444 en el archivo, obteniéndose en consecuencia, el
1453 emufs_fsc_buscar_lugar(), emufs_fsc_buscar_n_lugares()
1455 \labelwidthstring 00.00.0000
1461 Luego de una operación de baja o alta de un registro en el archivo de datos
1466 ), incrementará o decrementará respectivamente el espacio libre en el archivo
1467 de datos, y esto deberá ser registrado, agregando un nuevo registro en
1468 el archivo de espacios libres (
1472 ) o bien modificandoló.
1476 En el caso de organizaciónes con bloques, se actualizará el valor del espacio
1481 en el bloque (ya sea incrementandoló o decrementandoló) o bien se insertará
1482 un nuevo registro en caso de que se esté creando un nuevo bloque en el
1483 archivo de datos (en este caso no será debido a un alta o baja de registro
1484 como se mencionó al principio).
1488 Para el caso de organización sin bloques, en el caso de baja de un registro
1493 ) se insertará un nuevo registro en el
1497 dando cuenta de la aparición de un nuevo gap en el archivo de datos (
1501 ), y en caso de estar este lindante con otro gap, se realizará el merge
1503 (esto esta explicado más en profundidad en los casos particulares de organizaci
1504 ón fisica, registros variables sin bloques).
1505 Para el caso de una alta en el archivo de datos (
1509 ), el valor del gap donde se haya insertado se actualizará.
1514 emufs_fsc_agregar(), emufs_fsc_agregar_gap(), emufs_fsc_actualizar(), emufs_fsc_
1517 \labelwidthstring 00.00.0000
1523 : Unicamente para el caso de una organización que presente gaps en el archivo,
1524 se podrá dar a lugar la eliminación de un registro del archivo de espacios
1530 Esta situación tendrá efecto cuando se inserte un registro que entre perfecto
1531 en un gap disponible, y por ende el gap desaparecerá.
1535 emufs_fsc_borrar_gap()
1539 \begin_inset LatexCommand \label{sec:did}
1543 Archivo de id's recuperables
1546 El archivo de Id's liberado (
1550 ) llevará cuenta de aquellos Id's de registros (
1554 ) que ya no se encuentran siendo utilizados y fueron liberados por registros
1555 eliminados previamente.
1556 A través del mismo, se podrá realizar la reutilización de Id's ante la
1557 alta de nuevos registros.
1560 A nivel físico, este archivo poseerá una secuencia de datos del tipo EMUFS_REG_I
1561 D, y el comportamiento del sistema de recuperación de Id's será el de una
1563 Es decir, ante el requerimiento de un
1567 libre por una función del sistema como por ejemplo la alta de un nuevo
1568 registro, el API del archivo (
1572 ), obtendrá el último dato del mismo (el
1576 que fue liberado mas recientemente), y truncará el archivo eliminando el
1581 recuperado de la tabla.
1582 (LIFO, Last in First Out).
1588 Este archivo tiene registros de un solo campo,
1592 el cual simboliza al id que fue liberado en un proceso de baja de registros.
1595 Funciones principales
1598 Las declaraciones e implementación se pueden encontrar en
1612 \labelwidthstring 00.00.0000
1618 Ante la eliminación de un registro del archivo de datos (
1622 ) se procederá al agregado del correspondiente
1626 que fue liberado por dicha operación, al archivo
1640 \labelwidthstring 00.00.0000
1646 Cuando el sistema desee grabar un nuevo registro en el archivo de datos,
1651 disponible para el mismo.
1652 El sistema de administración de Id's libres, obtendrá el último
1656 que se guardó en el archivo (o se eliminó del archivo de datos), y truncará
1657 el archivo eliminandolo.
1665 emufs_did_get_last()
1669 \begin_inset LatexCommand \label{cha:tipo1}
1673 Archivo con bloques parametrizados y registros de longitud variable
1676 Este tipo de archivo tiene varias complicaciones, al tratarse de un punto
1678 \begin_inset LatexCommand \ref{cha:tipo2}
1683 \begin_inset LatexCommand \ref{cha:tipo3}
1687 (cuenta tanto con bloques como con registros variables), hereda los inconvenien
1688 tes (y ventajas) de ambos, más los propios.
1689 Al implementar este tipo de archivo se puso enfásis en la eficiencia mientras
1690 esta no comprometa la mantenibilidad del código, es por esto que en algunas
1691 circunstancias no se hace un uso óptimo del espacio.
1694 La implementación de este tipo de archivo puede ser encontrada en
1698 mientras que su interfaz pública está disponible en
1708 El archivo está compuesto por la
1713 \begin_inset LatexCommand \pageref{sec:cabecera_gral}
1718 El valor que toma en este tipo de archivo es 0 (o el valor simbólico
1727 Luego le sigue una cabecera propia del archivo (un
1731 , 4 bytes) que almacena el tamaño del bloque que usa el archivo.
1732 De esta menera, al abrir un archivo de este tipo no se necesita tener ninguna
1733 información sobre él.
1734 A esta cabecera le siguen cero o más bloques del tamaño fijo especificado
1735 en la cabecera antes mencionada.
1741 +-----------+-----------+------------------------//-+
1744 | tipo | tam_bloque| Cero o más bloques ...
1752 +-----------+-----------+------------------------//-+
1755 /- 4 bytes -/- 4 bytes -/
1758 Organización física de un bloque
1761 Cada bloque no guarda información en sí, sólo se comporta como un contenedor
1763 Esto no significa que un bloque no tenga utilidad, el bloque es utilizado
1764 para proveer un acceso semi-aleatorio a los registros.
1765 Para esto se utiliza el archivo de índice (ver página
1766 \begin_inset LatexCommand \ref{sec:idx}
1770 ), que almacena pares [identificador de registro, número de bloque].
1771 Para que sea suficiente este único índice para hallar un registro (siendo
1772 que puede haber más de un registro por bloque), es necesario
1774 alinear los registros a izquierda
1777 Esto significa que hay que asegurar que siempre los registros en un bloque
1778 se presenten de forma consecutiva, jamás permitiendo que haya un espacio
1779 libre entre registros (en un mismo bloque).
1782 Podemos ver un ejemplo de esto en forma gráfica:
1785 bloque N-1 | bloque N | bloque N+1
1788 /----------+------------+------------+---------------+-----------/
1793 | registro 1 | registro 2 | espacio libre |
1798 /----------+------------+------------+---------------+-----------/
1801 /------------- tamaño del bloque ---------/
1804 De esta forma, una vez obtenido el número de bloque, se pueda recorrer secuencia
1805 lmente hasta encontrar el registro deseado.
1806 A fin de llevar el conteo de espacio libre se utiliza el archivo de control
1807 de espacio libre (ver página
1808 \begin_inset LatexCommand \ref{sec:fsc}
1812 ), de forma tal que no sea necesario recorrer secuencialmente en busca de
1813 espacio libre al hacer una inserción.
1816 Puede darse un caso excepcional en el que un registro sea más grande que
1817 un bloque, en este caso el registro se almacenará en N bloques consecutivos
1818 (siendo N la cantidad de bloques que necesita el registro), ocupando completos
1819 los todos los bloques a excepción del último, en el que posteriormente
1820 se pueden agregar más registros.
1821 \layout Subsubsection
1824 \begin_inset LatexCommand \label{sub:tipo1_reg}
1828 Organización física de un registro.
1831 El registro es el que representa al dato realmente que se quiere almacenar.
1832 Para representar ese dato se necesita una determinada información de control,
1833 tanto para poder identificar el registro en un bloque (en búsquedas secuenciale
1834 s dentro del bloque) como para saber su longitud (dado que este tipo de
1835 archivo utiliza registros de tamaño variable).
1838 Siguiendo la metodología general de E
1839 \begin_inset Formula $\mu$
1842 FS, se optó por incluir esta información de control como una cabecera al
1843 comienzo del registro, siguiendo a esta los datos en sí.
1844 La cabecera está compuesta por un identificador (
1848 ) de registro (EMUFS_REG_ID, 4 bytes) seguido por el tamaño (
1852 ) del registros (EMUFS_REG_SIZE, 4 bytes).
1853 Podemos ver gráficamente como se se compone un registro:
1859 +-----------+-----------+------------------+
1862 | id | tamaño | datos ...
1866 +-----------+-----------+------------------+
1869 /- 4 bytes -/- 4 bytes -/- [tamaño] bytes -/
1870 \layout Subsubsection
1873 \begin_inset LatexCommand \label{sub:tipo1_reg_multi}
1877 Organización física de un registro más grande que un bloque (registro
1884 Puede darse el caso excepcional en que un registro sea de mayor longitud
1886 Al ser una situación excepcional, no siempre se resuelve de la forma más
1887 eficiente ni se mínimiza el espacio ocupado por datos de control (como
1888 se dijo anteriormente, se prefirió conservar la simpleza del código, adoptando
1889 algoritmos generales aunque no sea de la forma más eficiente o maximizando
1890 el uso del espacio para no perjudicar la mantenibilidad).
1893 Para menejar un registro
1897 se optó por limitarlo a la siguiente estructura (suponiendo que el registro
1898 ocupa N bloques, con N > 1 y que un
1902 es una porción del registro que entra en un bloque):
1909 se almacenan en bloques completos consecutivos.
1912 El último fragmento se almacena al comienzo del bloque inmediatamente posterior
1916 Cada framento posee las cabeceras mencionadas en la sección
1917 \begin_inset LatexCommand \ref{sub:tipo1_reg}
1921 , cuyo contenido es el siguiente:
1929 se almacena el identificador único obtenido al hacer el alta.
1936 se almacena el tamaño del
1940 actual más los tamaños de los
1944 posteriores, quedando en el primer
1948 el tamaño completo del registro y en el último sólo el tamaño del
1956 Como puede observarse, la información de control en los
1960 intermedios puede ser redundante, pero se conserva para poder realizar
1961 algoritmos genéricos (que se basan en que al principio de un bloque, si
1962 no está vacío, hay una cabecera de un registro) y para facilitar chequeos
1963 de integridad del archivo.
1966 A continuación se presenta un ejemplo gráfico de un registro multibloque
1967 de 10 bytes (de contenido
1968 \begin_inset Quotes eld
1972 \begin_inset Quotes erd
1975 ) almacenado en un archivo con bloques de 12 bytes (4 para datos):
1978 | bloque 0 | bloque 1 | bloque 2
1981 +-------------------+-------------------+-------------------+-//-+
1984 | registro 0 - 1/3 | registro 0 - 2/3 | registro 0 - 3/3..|
1991 |+----+-----+------+|+----+-----+------+|+----+-----+----+..| // |
1994 || id | tam | datos||| id | tam | datos||| id | tam |dato|..|
2001 ||----+-----+------+||----+-----+------+||----+-----+----+..| // |
2004 || 0 | 10 | 1234 ||| 0 | 6 | 5678 ||| 0 | 2 | 90 |..|
2011 |+----+-----+------+|+----+-----+------+|+----+-----+----+..| // |
2014 +-------------------+-------------------+-------------------+-
2024 2 bytes libres al final del bloque 2
2027 Este es un ejemplo figurativo, ya que se puso como límite mínimo de tamaño
2028 de bloque 16 bytes (para que haya al menos la misma cantidad de espacio
2029 para datos que para información de control).
2030 Este límite mínimo ya roza lo absurdo (es muy ineficiente por la gran cantidad
2031 de accesos a disco que necesita).
2032 El límite físico es de 9 bytes (8 para información de control, 1 para datos).
2035 Funciones principales
2038 Las funciones principales son las necesarias para completar la estructura
2040 \begin_inset LatexCommand \pageref{sub:EMUFS}
2047 Lectura de registros
2050 Para leer un registro se hace uso del archivo de índice (ver página
2051 \begin_inset LatexCommand \pageref{sec:idx}
2055 ), obteniéndose el número de bloque en donde está almacenado el registro
2057 Una vez obtenido, se carga en memoria el bloque entero y se busca secuencialmen
2058 te en él (leyendo la cabecera de cada registro y salteando los datos) hasta
2059 encontrar el registro pedido.
2060 Una vez encontrado se lo copia y devuelve.
2063 Si se tratara de un registro
2068 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2072 ), se procede forma similar, sólo que se cargan en memoria uno a uno los
2073 bloques que componen el registro y se van copiando (y uniendo) los
2082 emufs_tipo1_leer_registro()
2088 Para realizar el alta de un registro, lo primero que se obtiene es un identifica
2089 dor, buscando primero en el archivo de identificadores recuperables (pág.
2091 \begin_inset LatexCommand \ref{sec:did}
2095 ) y de no haber ninguno, buscando el mayor identificador presente en el
2096 archivo de índice (pág.
2098 \begin_inset LatexCommand \ref{sec:idx}
2103 El paso siguiente es buscar un bloque con espacio libre suficiente como
2104 para almacenar el registro (y su cabecera) en el archivo de control de
2107 \begin_inset LatexCommand \ref{sec:fsc}
2111 ) y cargarlo completo en memoria.
2112 De no encontrarse, se crea un bloque nuevo al final de archivo.
2113 En el bloque cargado en memoria, se agrega el registro nuevo (con su cabecera)
2114 al comienzo del espacio libre (calculado a partir del tamaño del bloque
2115 y el espacio libre en bloque) y se lo graba en disco.
2116 Finalmente se agrega (o actualiza) el identificador al archivo índice y
2117 el espacio libre en el bloque.
2120 Si el registro ocupara más de un bloque (ver sección
2121 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2125 ), se buscan N bloques consecutivos (todos los que necesite el registro)
2126 absolutamente libres
2132 Incluso el último bloque debe estar absolutamente libre para cumplir con
2133 las condiciones presentadas en la sección
2134 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2141 y graba bloque a bloque cada
2145 del registro (con sus cabeceras intermedias), al último
2149 se lo trata de forma análoga a un registro
2154 Por cada bloque utilizado se actualiza el archivo de control de espacio
2160 emufs_tipo1_agregar_registro()
2166 Al eliminar un registro lo primero que se hace es actualizar los archivos
2167 de índice y de indentificadores recuperables, poniendo como número de bloque
2172 y agregando el identificador del registro a borrar respectivamente.
2173 También se actualiza el archivo de control de espacio libre por cada bloque
2174 (en caso de ser más de uno, en registros
2178 , se actualizan todos los bloques) y se carga el bloque en memoria para
2181 alinear los datos a izquierda
2183 (en caso de ser un registro
2187 , esto se realiza sólo para el último bloque).
2188 Para alinear los datos, se recorre secuencialmente en bloque (leyendo la
2189 cabecera de cada registro y salteando los datos) hasta encontrar el registro
2191 Encontrado el registro, se copian todos los bytes que se encuentran entre
2192 el fin del registro a borrar y el fin del bloque, en el comienzo del bloque
2198 emufs_tipo1_borrar_registro()
2201 Modificación de registros
2204 Se optó por un algoritmo simple y general, que usa las funciones de alto
2205 nivel mencionadas hasta ahora.
2206 Simplemento borra el registro y vuelve a crearlo.
2207 Al recuperar el último identificador de registro borrado, nos aseguramos
2208 de que se mantenga el identificador del registro.
2213 emufs_tipo1_modificar_registro()
2216 Obtención de estadísticas
2219 Es una función bastante simple, con una única complicación que mencionaremos
2223 Para obtener las máximas desviaciones, cantidad total de espacio libre,
2224 cantidad de registros y tamaño de los archivos auxiliares se utilizan las
2225 funciones apropiadas de los archivos auxiliares (ver secciones
2226 \begin_inset LatexCommand \ref{sec:idx}
2231 \begin_inset LatexCommand \ref{sec:fsc}
2236 \begin_inset LatexCommand \ref{sec:did}
2243 Para obtener la cantidad de bloques se hace el siguiente calculo:
2246 cant_bloques = (tamaño_archivo_datos - tamaño_cabecera_archivo_datos)
2252 Hasta aquí no hay mayores inconvenientes.
2253 El problema se presenta para calcular el tamaño de la información de control
2254 utilizada por el archivo de datos; se utiliza el siguiente cálculo:
2257 tam_info_control_datos = tamaño_cabecera_archivo_datos
2260 + cant_registros * tamaño_cabecera_registro;
2263 Aunque a simple vista esto parece acertado, no contempla el caso de los
2269 \begin_inset LatexCommand \pageref{sub:tipo1_reg_multi}
2273 ), estos registros almacenan
2275 tamaño_cabecera_registro * N
2281 es la cantidad de bloques que ocupan.
2282 Salvar este caso sería muy costoso, porque habría que recorrer el archivo
2283 registro a registro,
2291 e ir contando todas las cabeceras de registro que aparecen (similar a lo
2292 que se hace en la compactación, ver sección
2293 \begin_inset LatexCommand \ref{sub:tipo1_compact}
2298 Al tratarse este de un caso excepcional, se optó por mantener la función
2299 simple ya que funciona bien en la mayoría de los casos.
2304 emufs_tipo1_leer_estadisticas()
2308 \begin_inset LatexCommand \label{sub:tipo1_compact}
2312 Compactación del archivo de datos
2315 Esta función es una de las más simples, porque se limita a un algoritmo
2316 muy simple que utiliza las funciones de
2320 antes nombradas para realizar su tarea.
2321 Básicamente recorre el archivo de índices de registros, de comienzo a fin,
2322 leyendo el registro, borrándolo y volviéndolo a insertar.
2323 Si había espacio libre en un bloque anterior al que estaba, será insertado
2324 en él, si no volverá a grabarse en el lugar en que estaba.
2325 De esta forma se aprovechan todos los espacios libres intermedios, concluyendo
2326 con un archivo igual o más pequeño que el original.
2329 Esta implementación no es la más eficiente, pero siendo que esta es una
2330 operación costosa y excepcional por naturaleza, se optó por mantener el
2331 algoritmo simple a costo de un poco de eficiencia.
2336 emufs_tipo1_compactar()
2339 Detalles de implementación (funciones internas, ver si lo ponemos o no)
2343 \begin_inset LatexCommand \label{cha:tipo2}
2347 Archivo sin bloques y registros de longitud variable
2350 Este tipo de archivo nos traerá a la mesa la particularidad de grabar registros
2351 de longitud variable sin realizar su agrupación en bloques, y como veremos
2352 en la siguiente sección, tambien permitirá la administración de gaps que
2353 queden en el archivo luego de operaciones de baja de registros.
2359 Este tipo de archivo realizará el almacenamiento de registros de longitud
2360 variable en disco, su borrado y modificación sin la utilización de bloques
2362 Su implementación se encuentra en los archivos fuente (
2373 Los archivos del tipo 2, presentarán al comienzo del mismo un header compuesto
2374 simplemente por un dato del tipo EMUFS_Tipo (int) el cual indicará el tipo
2375 de archivo en cuestión.
2378 Para poder entender mejor la organización fisica de este tipo de archivo,
2379 tomemos el caso hipotético en el que se encuentran grabados
2383 (comenzando desde registro 0) de
2392 Supongamos también que entre el registro 0 y 1 se encontraba un
2394 registro de 10 bytes
2409 Si miramos al archivo de datos (.dat) en el disco nos encontraremos con
2411 \begin_inset Float figure
2418 Organización física de los registros en disco
2422 \begin_inset Graphics
2423 filename graphics/Example1.png
2434 Como se puede observar, a nivel físico cada registro grabado esta compuesto
2435 por un Header cuyo tamaño total es de 8 bytes (
2443 ), y posteriormente el registro (bloque de datos) en sí.
2444 Luego se encuentra el espacio libre de 18 bytes dejado por el registro
2445 de 10 bytes eliminado (10 bytes de datos + header de 8 bytes) y finalmente
2446 el segundo registro mencionado.dsds
2449 Comportamiento Particular de los Archivos Auxiliares
2452 Como fue explicado al inicio de la documentación, la implementación de cualquier
2453 a de las tres organizaciones físicas de archivos presenta la necesidad de
2454 poseer tres archivos auxiliares que actuarán como índice de direcciones
2459 ), administrador de espacio libre (
2463 ) y administrador de Id's liberados (
2470 No obstante, cada tipo de organización presentara sus particularidades respecto
2471 de estos tres archivos, las cuales describiremos a continuación en caso
2473 \layout Subsubsection
2475 Archivo índice o de posiciones relativas (.idx)
2482 ), permite la localización de los registros en el .DAT de forma directa,
2483 mediante la obtención de su offset o posición relativa respecto del inicio
2488 en donde se encuentra un registro dado, indicado por su ID.
2491 Así pues, si tomamos el ejemplo descripto al inicio de este capítulo, tendremos
2492 las siguientes entradas en el archivo índice
2497 \begin_inset Float table
2504 Organización física del archivo de índice o posiciones relativas.
2508 \begin_inset Tabular
2509 <lyxtabular version="3" rows="3" columns="3">
2511 <column alignment="center" valignment="top" leftline="true" width="0">
2512 <column alignment="center" valignment="top" leftline="true" width="0">
2513 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
2514 <row topline="true" bottomline="true">
2515 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2525 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2535 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2543 <row topline="true">
2544 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2554 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2564 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2569 El primer registro (reg0) comienza en el byte 4
2573 <row topline="true" bottomline="true">
2574 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2582 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2592 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2597 El segundo registro (reg1) comienza en el byte 60
2617 LOCATION indica donde comienza el header del registro buscado, y por consiguien
2618 te luego del header tendremos el registro en sí (los datos).
2619 \layout Subsubsection
2621 Achivo de Gaps / Espacios Libres (.fsc)
2624 El archivo de espacios libres o gaps (.fsc), tiene como función la administración
2625 del espacio libre o gaps (agujeros), generados por previas eliminaciones
2626 de registros en el archivo de datos.
2627 El mismo, nos indicará donde hay lugar para insertar un nuevo registro
2628 (se podrán insertar en algún gap acorde, o bien al final del archivo).
2629 Este archivo será utilizado tambien para el proceso de compactación de
2630 un archivo, explicado luego.
2633 Así pues, si tomamos el ejemplo descripto al inicio del documento, tendremos
2634 las siguientes entradas en el archivo índice
2639 \begin_inset Float table
2646 Organización física del archivo de
2650 o control de espacio libre.
2654 \begin_inset Tabular
2655 <lyxtabular version="3" rows="2" columns="3">
2657 <column alignment="center" valignment="top" leftline="true" width="0">
2658 <column alignment="center" valignment="top" leftline="true" width="0">
2659 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
2660 <row topline="true" bottomline="true">
2661 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2671 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2681 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2689 <row topline="true" bottomline="true">
2690 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2700 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2710 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2715 18 bytes libres a partir del byte 42 del .dat
2735 Por requerimiento del algoritmo de compactación, los gaps se graban en
2736 forma ordenada en el (.fsc).
2737 (El orden se corresponde con lo que hay en el
2742 \layout Subsubsection*
2747 Si bien la utilización concreta de los GAPS será explicada posteriormente
2748 en la ALTA y BAJA de registros, debemos remarcar la funcionalidad de MERGING
2749 que posee nuestro sistema FSC.
2752 Ante la eliminación de un registro del archivo de datos, se generara por
2753 consiguiente un gap o espacio libre en alguna posición del archivo.
2754 Ese gap deberá ser registrado en el archivo de gaps (.fsc).
2755 Ahora bien, nuestro sistema de gaps, contemplará como es debido, la posibilidad
2756 de que se haya eliminado un registro que posee un GAP por delante, un GAP
2757 por detrás, o bien un GAP por delante y por detrás del mismo.
2760 Nuestro sistema actuará en consecuencia, realizando un merge de los espacios
2761 libres, y unificándolos en una UNICA entrada en el archivo .fsc, que contendrá
2762 como dato de freespace, la suma correspondiente de los espacios libres
2764 \layout Subsubsection
2766 Archivo de ID's liberados (.did)
2769 El archivo de ID's liberados no presenta ningún aspecto particular en este
2770 tipo de organización.
2771 Remitirse al capítulo correspondiente a los archivos auxiliares para consultar
2772 su estructura y funcionamiento.
2775 Funciones Principales
2790 se encuentran las cabeceras y la implementación de las funciones principales
2791 respectivamente, las cuales dan funcionalidad a esta organización.
2795 A continuación se comentará el funcionamiento algunas de las mas importantes.
2798 Lectura de registros
2801 Como se vió al comienzo, los registros en este tipo de archivo no se encuentran
2802 agrupados en bloques de ninguna índole y estan dispersos a lo largo del
2803 archivo, con la particularidad de que pueden existir gaps o espacio libre,
2804 entre dos registros dados.
2807 Por ende la lectura de registros en este tipo de organización es muy simple
2808 y dada la inexistencia de bloques, el procedimiento será el siguiente:
2811 Se determina el offset en bytes, donde comienza el registro deseado, a través
2812 de su ID, buscando la misma en el archivo índice (
2819 Ya determinada la posición física del registro dentro del archivo de datos
2824 ), nos posicionamos en la misma, y leemos el header del registro (
2833 Contando así con el tamaño del registro, procedemos a leer el mismo (los
2834 datos), dando por finalizada la lectura.
2839 emufs_tipo2_leer_registro()
2845 En el proceso de alta de registros entrarán en juego dos archivos descriptos
2848 sección de archivos auxiliares
2850 , siendo estos el archivo índice (
2854 ), y el archivo de gaps / espacios libres (
2861 Así pues, a la hora de realizar una inserción de un registro en el archivo
2862 de datos, el procedimiento será el siguiente:
2865 Calculamos el espacio que necesitaremos para el registro: sizeof(
2873 ) + sizeof(registro).
2876 Determinamos donde debemos insertar el registro, ya sea un gap donde entre,
2877 o bien al final del archivo.
2880 Insertamos el registro e información de control (
2888 ), en la posición indicada en el paso 2.
2891 En caso de haber utilizado un GAP, actualizamos el espacio libre restante
2892 en el mismo y en caso de que se haya utilizado al totalidad del GAP, se
2893 lo elimina del archivo (
2900 Actualizamos la entrada correspondiente al registro ingresado (determinada
2901 por su RegID), en el archivo índice (
2905 ), indicando su offset donde podrá ser accedido luego.
2910 emufs_tipo2_agregar_registro()
2916 En el proceso de baja de registros entrarán en juego los tres archivos descripto
2919 sección de archivos auxiliares
2921 , siendo estos el archivo índice (
2925 ), el archivo de gaps / espacios libres (
2929 ) y el archivo de ID's liberados (
2936 Dado que en la implementación de este tipo de organización física contamos
2937 con los gaps o espacios libres entre registros, no se eliminará fisicamente
2938 el registro del archivo de datos (
2942 ), pues entonces carecería de sentido el archivo anteriormente mencionado
2948 En cambio, se agrega el gap dejado por la eliminación a dicho archivo,
2949 y se marca fisicamente en el archivo de datos la eliminación mediante un
2950 fill de los bytes correspondientes con un caracter nulo.
2951 (hexa 00 y con el propósito de probar fehacientemente que el sistema funciona).
2954 El proceso de baja o eliminación de un registro constará luego de los siguientes
2958 Se obtiene el offset o posición relativa en donde se encuentra grabado el
2959 registro dentro del archivo de datos.
2962 Se obtiene el tamaño del registro y se realiza un dummyfill del sector del
2963 archivo correspondiente al registro que se está dando de baja.
2964 (Se rellena la zona correspondiente a su header+data).
2967 Se agrega el GAP generado al archivo de gaps o espacios libres, y en caso
2968 de haberse generado un GAP lindante con otro GAP, se realizará un merge
2969 de los mismos y se los registrará bajo una única entrada en el archivo
2970 de espacios libres (.fsc).
2973 Se agrega el ID que fue liberado, al archivo de ID's liberados (
2977 ), al final del mismo (
2984 Se marca en el archivo índice (
2988 ) la eliminación, mediante el valor ¨-1¨ en el registro correspondiente
2989 al registro recién eliminado (se le cambia el valor al n-esimo registro,
2990 donde N = IDReg del reg eliminado).
2995 emufs_tipo2_borrar_registro()
2998 Modificación de registros
3001 Dada la naturaleza del archivo de ID's liberados, y el manejo de espacio
3002 libre del que consta esta organización de archivo, el proceso de modificación
3003 de un registro se limita a los siguientes pasos:
3006 Se realiza la lectura del registro, mediante el respectivo procedimiento
3007 ya desarollado anteriormente.
3010 Una vez que se cuenta con los nuevos datos modificados, se procede a dar
3011 de baja el registro que ha sido modificado, e inmediatamente después se
3012 realiza una inserción con los nuevos datos.
3021 Como fue indicado, dada la naturaleza de PILA del subsistema de administración
3022 de ID liberados, es asegurado que la nueva inserción del registro modificado
3023 se realizará con el mismo RegID.
3028 emufs_tipo2_modificar_registro()
3031 Obtención de estadísticas
3034 Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
3035 cantidad de bloques, cantidad de registros, espacio libre total, espacio
3036 libre promedio, espacio libre máximo y mínimo, etc.
3039 Esta información es el resultado de ciertos cálculos realizados tanto en
3040 el archivo de datos como en los archivos índice.
3043 Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
3044 del archivo de datos, espacio libre total, cantidad de registros, cantidad
3045 de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
3051 emufs_tipo2_leer_estadisticas()
3054 Compactación del archivo de datos
3057 Asi como los otros dos tipos de datos, el que nos compete también cuenta
3058 con la posibilidad de realizar la compactación de datos cuando el usuario
3059 lo desee, justificando todos los registros a izquierda, eliminando así
3060 los gaps existentes y decrementando el tamaño del archivo en disco (truncandolo
3064 Para poder comprender como hemos implementado el proceso de recompactación
3065 en nuestro tipo de archivo 2, nos ayudaremos de esquemas a través de los
3066 cuales iremos describiendo el proceso.
3067 Notemos antes, que el proceso de compactación esta directamente ligado
3068 con el archivo de gaps o espacios libres (
3075 Comenzemos con el siguiente cuadro situacional:
3076 \begin_inset Float figure
3083 Archivo con gaps entre registros previo a compactación
3087 \begin_inset Graphics
3088 filename graphics/Compact1.png
3100 Partiendo de esta base, el algoritmo de compactación tomará en su inicio
3101 al primer gap existente dentro del archivo de datos, en este caso llamado
3107 Luego, establecerá que el
3111 a partir de donde se quieren mover datos, sera:
3114 StartGap0 + SizeGap0 = EndGap0 = Source
3117 Lo cual no es nada más y nada menos que lo obvio, la fuente a partir de
3118 donde se mueven los datos, sera el fin del primer gap, donde comienzan
3124 ) del movimiento, se establece inicialmente, el inicio del gap, o sea
3126 StartGap0 = Destination
3131 Luego, el algoritmo entrara en un bucle while (mientras haya bucles por
3132 levantar), el cual trabajara hasta el final de la compactación de la siguiente
3143 Se levanta el proximo gap al levantado en una instancia previa.
3144 En este ejemplo, durante el primer loop del while, se levantará
3149 Luego, se calcula cuantos bytes hay que mover hacia el Destination de la
3173 Lo cual nuevamente es lógico pues querremos mover lo que se encuentra entre
3174 el final del primer gap levantado y el inicio del siguiente).
3177 Se realiza el movimiento de los datos, utilizando las direcciones
3185 , así como la variable
3189 que nos indica cuantos bytes transferir.
3195 La transferencia se hace de a chunks de 25 bytes + un resto segun el valor
3199 Se establece como gap de referencia, al ultimo gap leido (En este caso se
3212 ) y termina el código de repetición del bucle, dando lugar a la carga del
3213 siguiente gap en el inicio del mismo.
3221 Luego del primer bucle, el archivo se vera de la siguiente forma:
3222 \begin_inset Float figure
3229 Archivo con gaps en disco luego del primer bucle de compactación
3233 \begin_inset Graphics
3234 filename graphics/Compact2.png
3245 Notemos que al final de la porción de datos de los bytes movidos (donde
3250 ), hay basura que será pisada por el próximo movimiento.
3253 En el próximo loop, el bucle levantará un nuevo gap, y utilizando el gap
3254 anterior (En esta caso el Gap anterior será
3258 ) como referencia, realizará los mismos cálculos, desde donde transferir
3259 y cuantos bytes mover.
3260 (El destino es solo establecido inicialmente por código, y para el resto
3261 del algoritmo es el lugar donde quedo el puntero destination luego de la
3265 Una vez que se salga del bucle while, se realizará un último movimiento
3266 preprogramado, donde la fuente (
3270 ) será el final del ultimo gap, y la cantidad de bytes a mover será lo que
3271 se encuentre luego del mismo hasta el fin de archivo.
3274 Source = StartLastGap + SizeLastGap = EndLastGap
3277 Mustmove_bytes = Datsize - Source
3280 Damos por terminada así, la explicación del algoritmo de compresión el cual
3281 para el caso del tipo 2, es realmente bastante sencillo.
3286 emufs_tipo2_compactar()
3289 Consideraciones y Políticas de Diseño
3292 Se han tomado ciertas consideraciones para algunos casos particulares que
3293 se pueden presentar durante el uso/ejecución de la aplicación, así como
3294 tambien politicas respecto del diseño e implementación del sistema:
3297 En la organización física tipo 2 para los registros que se graban en disco
3298 hemos decidido utilizar como encabezado de cada uno de ellos, los datos
3299 [ID_REG][REG_SIZE], los cuales fueron detallados previamente.
3300 Si bien se podría haber descartado el grabado del ID del registro en el
3301 archivo de datos y puede parecer redundante, dado que poseemos el archivo
3302 índice con el offset directo, el mismo se lo graba por distintos motivos:
3306 A) En caso de la corrupción del archivo índice (.idx), podremos gracias a
3307 que poseemos en el archivo de datos, el ID de cada registro, recrear dicho
3308 índice, ayudándonos del archivo de espacios libres (
3312 ), para poder saltear los espacios libres y e ir recorriendo secuencialmente
3313 los registros, reconstruyendo así el índice en cuestión.
3314 (esta función de reconstrucción no pudo ser implementada para esta entrega,
3315 pero es una posibilidad real).
3319 B) Luego de un proceso de recompactación, los espacios libres que pudieron
3320 haber existido en el archivo de datos (
3324 ), son eliminados y los registros han cambiado de posición.
3325 Por ello, recorriendo secuencialmente por única vez el archivo de datos,
3326 se procede a la actualización / reconstrucción del índice de direcciones
3334 Si se desea insertar un registro y no se puede hayar un gap o espacio libre
3335 donde quepa, se los inserta al final del archivo.
3338 Ante una operación de baja de un registro, el mismo no es físicamente borrado
3339 del archivo de datos (
3343 ), simplemente los bytes que ocupa son llenados con hexa (00).
3344 Paralelamente, se procede a actualiza el archivo índice, insertando como
3345 valor de OFFSET para el registro eliminado, el valor ¨-1¨, indicando así
3346 la inexistencia del registro para el futuro, y por otro lado se genera
3347 la entrada de espacio libre en el archivo de gaps (
3354 La reutilización de ID's liberados por previas operaciones de baja de registros,
3355 se ve implementada por el archivo de ID liberados (.did), y su comportamiento
3356 es el de una pila por lo que el último ID liberado, sera el próximo a ser
3360 Como fue explicado en la implementación del archivo índice, existe una correspon
3361 dencia 1 a 1 entre los registros allí presentes (en el .idx) y los ID's de
3362 los registros, por lo cual el registro N-ésimo del archivo índice, será
3363 el correspondiente al registro de datos cuyo ID es igual a N.
3366 El proceso de compactación de archivos, realiza los movimientos de información
3367 requeridos para dicho propósito de a chunks de 25 bytes por vez.
3368 Este valor es fijo, pero se lo podría hacer parametrizable mediante la
3369 GUI en próximas entregas.
3373 \begin_inset LatexCommand \label{cha:tipo3}
3377 Archivo con bloques parametrizados y registros de longitud constante
3380 Las distintas organizaciones de archivos buscan aprovechar al máximo el
3381 espacio del archivo.
3384 En este caso veremos que sucede luego de agregar y borrar una gran cantidad
3385 de registros del archivo, lo que provoca como consecuencia directa la fragmenta
3386 ción del archivo, es decir, quedan huecos entre un registro y otro, lo que
3387 produce un desperdicio de espacio.
3390 La implementación de este tipo de archivo puede ser encontrada en
3394 mientras que su interfaz pública está disponible en
3404 Esta organización guarda los registros pertenecientes al archivo en bloques
3405 de tamaño parametrizado, de modo que intentará guardar la mayor cantidad
3406 de registros que quepan en un bloque.
3410 Así como los graba, también tendrá la posibilidad de leer registros y borrarlos
3414 El archivo estara compuesto por una cabecera que da información sobre el
3415 tipo (2, o el valor T3 del tipo
3419 en este caso) de organización, el tamaño de los bloques y el tamaño de
3426 +-----------+-----------+-----------+------------------------//-+
3429 | tipo | tam_bloque| tam_reg | Cero o más bloques ...
3437 +-----------+-----------+-----------+------------------------//-+
3440 /- 4 bytes -/- 4 bytes -/- 4 bytes -/
3443 Organización Física de un Bloque
3446 Cada bloque será capaz de contener la cantidad de registros enteros que
3448 De esta manera un registro que no entre completamente en el bloque deberá
3449 almacenarce en un bloque diferente.
3452 Los bloques no contienen ninguna información adicional, solo se conoce su
3453 tamaño y se usa para delimitar
3454 \begin_inset Quotes eld
3458 \begin_inset Quotes erd
3461 zonas en el archivo y obtener de esta manera acceso semi-aleatoreo a los
3465 bloque N-1 | bloque N | bloque N+1
3468 /----------+------------+------------+---------------+-----------/
3473 | registro 1 | registro 2 | espacio libre |
3478 /----------+------------+------------+---------------+-----------/
3481 /------------- tamaño del bloque ---------/
3484 Organizacion Física de Registros
3487 Cada registro se almacena en un bloque, y contiene una cabecera que indica
3492 por este motivo al realizar la busqueda de espacio en un bloque se lo hará
3493 preguntando por el tamaño del registro más
3495 sizeof(EMUFS_REG_ID).
3501 +-----------+-------------------+
3508 +-----------+-------------------+
3511 /- 4 bytes -/- [tam_reg] bytes -/
3514 Organización Física de Registros
3519 Al ser los registros de longitud constante, se ha adoptado que un registro
3524 nunca podrá estar almacenado en algún lugar que no sea el comienzo de un
3526 De esta manera se puede calcular cuantos bloques ocupará un registro y
3527 se podrá solicitar lugar para almacenarlo con la ayuda de la función
3529 emufs_fsc_buscar_n_lugares(),
3531 que es muy importante para evitar el solapamiento de registros.
3532 Esta consideración acarrea como consecuencia directa un alto costo en términos
3533 del espacio desperdiciado.
3536 A continuación se presenta un ejemplo gráfico de un registro multibloque
3537 de 26 bytes (de contenido
3538 \begin_inset Quotes eld
3541 12345678901234567890123456
3542 \begin_inset Quotes erd
3545 ) almacenado en un archivo con bloques de bytes 14 bytes (10 para datos)
3546 y registros de 38 bytes:
3549 | bloque 0 | bloque 1 | bloque 2
3552 +-------------------+-------------------+-------------------+-//-+
3555 | registro 0 - 1/3 | registro 0 - 2/3 | registro 0 - 3/3..|
3562 |+----+------------+|+----+------------+|+----+--------+....| // |
3565 || id | datos ||| id | datos ||| id | datos |....|
3572 ||----+------------+||----+------------+||----+--------+....| // |
3575 || 0 | 1234567890 ||| 0 | 1234567890 ||| 0 | 123456 |....|
3582 |+----+------------+|+----+------------+|+----+--------+....| // |
3585 +-------------------+-------------------+-------------------+-
3595 4 bytes libres (e inutilizables) al final del bloque 2
3598 Funciones Principales
3609 se encuentran las cabeceras y la implementación de las funciones principales
3610 respectivamente, las cuales dan funcionalidad a esta organización.
3613 A continuación se comentará la descripción de algunas acciones importantes.
3616 Lectura de registros
3619 La lectura de un registro se realiza con la ayuda del archivo .
3623 el cual contiene la información de la posición del registro dentro del
3625 Una vez leida esta información, se recupera el bloque (en su totalidad)
3626 del archivo y se busca secuencialmente el registro con el
3635 emufs_tipo3_leer_registro()
3641 Graba un registro en un bloque donde haya espacio suficiente, y si no crea
3642 un nuevo bloque y lo agrega al final del archivo.
3645 Luego de grabar un registro, actualiza los archivos de índice .idx y .fsc
3646 para mantener la coherencia.
3649 Cuando nos encontramos con registros multibloque, se calcula cuantos bloques
3650 ocupará el registro de la siguiente manera:
3652 Cantidad de Bloques = 1 + Tamaño del Registro/(Tamaño del Bloque-Sizeof(EMUFS_RE
3656 Esta ecuación solo falla en el caso que el tamaño del registro y el tamaño
3657 del bloque sean iguales, en tal caso, se coloca el valor 1 en
3664 Y con esta información se realiza un ciclo
3668 que grabará tantas veces como sea necesario levantando y grabando los bloques
3674 emufs_tipo3_grabar_registro()
3680 Borra un registro del archivo de datos, para esto levanta el bloque al que
3681 pertenece el archivo y ajusta los demás registros justificandolos hacia
3685 Cabe destacar que para dar de baja un registro no hace falta borrarlo del
3686 archivo de datos, solo es necesario borrar las entradas en los archivos
3687 de índice, pero cuando se realiza el ajuste el algoritmo toma porciones
3688 del bloque del tamaño de un registro mas su encabezado - comenzando desde
3689 el siguiente al que fue borrado - y copia (sobreescribe) sobre el anterior.
3690 De esta manera, la información correspondiente al registro borrado no estará
3691 presente en el archivo de datos.
3692 Esto es una consecuencia del ajuste al borrar un registro, pudiendo no
3693 ser así, si no se realizara el mismo.
3696 En el caso de los registros multibloque, se eliminará la porción del registro
3697 contenida en el primer bloque y se actualizarán de manera conveniente los
3698 archivos índice, para restaurarlos a un valor verdadero.
3703 emufs_tipo3_borrar_registro()
3706 Obtención de estadísticas
3709 Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
3710 cantidad de bloques, cantidad de registros, espacio libre total, espacio
3711 libre promedio, espacio libre máximo y mínimo, etc.
3714 Esta información es el resultado de ciertos cálculos realizados tanto en
3715 el archivo de datos como en los archivos índice.
3718 Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
3719 del archivo de datos, espacio libre total, cantidad de registros, cantidad
3720 de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
3726 emufs_tipo3_leer_estadisticas()
3729 Compactación del archivo de datos
3732 Esta función intenta reorganizar el archivo de manera que el espacio libre
3733 sea lo menor posible, recordando siempre que un registro no puede ser almacenad
3734 o en mas de un bloque excepto que el tamaño del registro sea mayor que el
3738 Para realizar esto, se aprovecha la funcionalidad de
3740 emufs_tipo3_grabar_registro()
3742 ya que esta tiene la capacidad de determinar una posición mas eficiente
3743 en el archivo para un registro.
3744 Por esto lo que se hace es levantar uno por uno los registros y volverlos
3745 a grabar, de ese modo todos los
3749 que pudieron haberse formado por la eliminación de registros serán cubiertos
3753 Al estar utilizando recuperación de
3757 borrados, esto me asegura que el registro borrado-guardado conservará el
3761 Al finalizar este proceso se verifica si existen bloques vacios para truncar
3763 Lo mismo se debe hacer con el archivo de espacios libres .
3767 el cual disminuye su tamaño también.
3772 void emufs_tipo3_compactar()
3775 Consideraciones y Políticas de Diseño
3778 Se han tomado ciertas consideraciones para algunos casos particulares que
3779 se pueden presentar durante el uso/ejecución de la aplicación.
3782 Cada registro tiene un encabezado que indica el
3789 Si el tamaño del registro es mayor que el tamaño del bloque el registro
3790 se particionará en la cantidad de bloques que sea necesario, pero siempre
3791 se guardará desde el comienzo de un bloque, esto quiere decir que nunca
3792 se podrá encontrar un comienzo de registro en algún lugar de un bloque
3793 que no sea el comienzo del mismo.
3796 Si el registro se divide en mas de un bloque, se le coloca el id como encabezado
3797 igualmente, pero en el archivo .
3801 solo se guarda el primer bloque.
3806 se actualizan todos los bloques con el espacio libre que realmente tienen.
3812 Las comparaciones, pruebas, etc...
projects / z.facultad / 75.06 / emufs.git / blob