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$
54 Se detallan a continuación los tipos de datos definidos y utilizados en
55 las distintas implementaciones que conforman nuestro sistema, siendo el
56 más importante de ellos, la estructura
60 que actúa como interfaz común para el manejo de cualquier tipo de archivo
61 (no importa que tipo de organización física posea un archivo, esta estructura
62 prooverá una interfaz (funciones) para su manejo).
68 En la implementación de cada tipo de organización física, así como tambien
69 en las API de los archivos auxiliares comunes a ellas, se da la utilización
70 de tipo definidos para una clara interfaz entre las mismas, los cuales
71 son brevemente descriptos a continuación y pueden ser hallados en el archivo
83 : usado para representar un
94 : usado para representar el tamaño en bytes de un registro.
101 : usado para representar un número de bloque.
108 : usado para representar el tamaño en bytes de un bloque.
115 : usado para representar espacio libre en bytes.
122 : usado para representar un offset.
142 es la estuctura principal que encapsula todas las funciones para el manejo
143 de un archivo de datos.
144 Posee punteros a funciones que dependiendo de la organización fisica por
145 la cual se opte dentro del sistema, serán asignados de acorde.
149 Su declaración puede ser observada en el archivo
153 y la misma cuenta con los siguiente campos:
160 que es un tipo enumerado que indica cual es la organización.
167 indica el tamaño del bloque para los tipos 1 y 3.
174 indica el tamaño del registro, para el tipo 3 que posee tamaño constante.
181 puntero a la función para leer un bloque.
186 void *leer_bloque_raw()
188 puntero a la función para leer un bloque, el anterior y el siguiente.
193 void **leer_registro()
195 puntero a la función para leer un registro.
200 void **leer_registro_raw()
202 puntero a la función para leer un registro con su encabezado.
207 EMUFS_REG_ID *grabar_registro()
209 puntero a la función para grabar un registro.
214 EMUFS_REG_ID *modificar_registro()
216 puntero a la función para modificar un registro.
221 int *borrar_registro()
223 puntero a la función para borrar un registro.
228 EMUFS_Estadisticas *leer_estadisticas()
230 puntero a la función para cargar una estructura con las estadísticas.
237 puntero a la función para compactar un archivo.
244 almacena el nombre del archivo sin extensión.
247 Esta estructura define los valores de sus punteros según el tipo de organización
248 que se desee manejar y esto se realiza a través del API emufs, implementado
253 , que se describirá posteriormente.
256 Por ejemplo si se desea crear un archivo de nombre
257 \begin_inset Quotes eld
261 \begin_inset Quotes erd
264 organizado de la forma 3, se invoca a la función:
269 emufs_crear(filename,tipo,tam_bloque,tam_reg),
275 es el nombre que tendrán los archivos de datos e índice,
279 es el tipo de organización - bloques parametrizados y registros constantes
284 es el tamaño del bloque, y
288 es el tamaño del registro.
291 Para las diferentes organizaciones puede ser que alguno de estos 2 últimos
292 valores no tengan sentido almacenarlas y tomaran un valor por defecto igual
296 Según el tipo de organización, se inicializan los punteros a las funciones.
303 emufs_tipo3_leer_bloque()
305 , y lo mismo sucede con los demás.
315 es un tipo de dato enum, el cual será utilizado en la cabecera de todo
320 ), para indicar los distintos tipos de organización física.
321 Su declaración puede verse en el archivo
326 A saberse los valores y significado correspondiente que puede tomar este
334 : Archivos con registros de longitud variable y bloques parametrizables.
341 : Archivos con registros de longitud variable sin bloques.
348 : Archivos con registros de longitud fija y bloques parametrizables.
358 es una estructura que almacenará los datos pertinentes a las estadísticas
359 de un archivo dado, y será utilizada para visualizar dichas observaciones
363 Su declaración puede ser observada en el archivo
367 y la misma cuenta con los siguiente campos:
378 : indica el tamaño del archivo de datos (.dat) en bytes.
389 : indica el tamaño de los archivos auxiliares sumados en bytes.
400 : indica la cantidad de bytes en información de control utilizados para
412 : promedio de espacio libre en el archivo de datos (por bloque o gap promedio
424 : total de espacio libre en el archivo de datos.
435 : máximo espacio libre en el archivo de datos (en un bloque o máximo gap
458 : cantidad de bloques en el archivo de datos (.
473 : cantidad de registros en el archivo de datos (
480 En base a la estructura descripta anteriormente y mediante la utilización
481 de la función de lectura de estadísticas l
483 emufs_leer_estadisticas()
485 disponible en la estructura común
489 handler de cualquier tipo de archivo, podremos obtener una serie de estadística
490 s que pasamos a detallar (más alla de los datos básicos como cant registros,
491 cant bloques, tam archivo, etc):
494 Relación entre espacio libre y el tamaño del archivo de datos (
501 Relación entre el espacio ocupado por información de control y el tamaño
502 del archivo de datos (
509 Cantidad promedio de espacio libre (en bloque o gap promedio)
512 Desviaciones extremas de espacio libre (máximo/mínimo espacio libre en bloque
517 \begin_inset LatexCommand \label{sec:cabecera_gral}
521 Organización física general de un archivo E
522 \begin_inset Formula $\mu$
529 \begin_inset Formula $\mu$
532 FS está compuesto por 4 archivos a nivel de sistema operativo: archivo de
533 datos (con 3 formatos posibles, ver páginas
534 \begin_inset LatexCommand \pageref{cha:tipo1}
539 \begin_inset LatexCommand \pageref{cha:tipo2}
544 \begin_inset LatexCommand \pageref{cha:tipo3}
548 ), archivo de índice (ver página
549 \begin_inset LatexCommand \pageref{sec:idx}
553 ), archivo de control de espacio libre (ver página
554 \begin_inset LatexCommand \pageref{sec:fsc}
558 ) y archivo de índices recuperables (ver página
559 \begin_inset LatexCommand \pageref{sec:did}
566 El archivo de datos está compuesto por:
577 (4 bytes en plataformas Linux de 32 bits) que representa el tipo de archivo.
580 Datos dependientes del tipo de archivo.
587 es utilizada para poder detectar el formato de un archivo al abrirlo.
588 Los datos dependientes del tipo de archivo serán explicados en sus secciones
595 +-----------+--------------------------------------------//-+
598 | tipo | Datos dependientes del tipo de archivo ...
606 +-----------+--------------------------------------------//-+
612 Uso de la estructura EMUFS
615 Como fue mencionado anteriormente en la descripción de la estructura EMUFS,
616 la misma proporciona al usuario una interfaz a través de la cual puede
617 realizar el manejo de archivos en forma genérica, abstrayéndose del tipo
618 de organización física en particular que dicho archivo posea.
623 y las funciones que inicializan la estructura se encuentran en
628 Es decir que a traves de esta estructura, podemos manejar cualquier tipo
629 de archivo, mediante una misma interfaz en común.
634 posee además de ciertos datos que describen la organización física de un
635 archivo dado como por ejemplo
653 , una serie de punteros a funciones para el manejo del archivo del cual
657 Entre dichos funciones se encuentran:
663 leer_bloque(), borrar_registro()
671 modificar_registro, leer_estadisticas()
678 Para entender mejor el uso de esta estructura para el manejo de los archivos,
679 mostraremos un ejemplo concreto.
680 Supongamos que tenemos el siguiente código:
683 EMUFS *efs = emufs_crear(¨articulos.dat¨,T3,200,50);
686 Esto hará que se cree el archivo de datos
690 , con la organización física tipo 3 con registros de longitud fija de 50
691 bytes y bloques de 200 bytes.
692 Al mismo tiempo, los se asginarán valores a los punteros a funciones que
693 posee dicha estructura, la cual de ahora en más estará en condiciones de
694 manejar un archivo del tipo 3.
695 Gráficamente lo que sucede es:
699 \begin_inset Float figure
706 Inicialización de estructura EMUFS para un caso Archivo Tipo 3
710 \begin_inset Graphics
711 filename graphics/Emufsinit.png
722 Así pues, cuando se utilize la estructura para por ejemplo leer un registro,
723 sucedera lo siguiente:
726 efs->leer_registro(params) -- calls --> emufs_tipo3_leer_registro(params)
729 Como se puede observar, la estructura
733 permitirá el manejo de cualquier tipo de archivo, a través del mismo código,
734 dandole gran flexibilidad a nuestro sistema, que podrá expandirse a más
735 tipos de archivos de ser necesario.
741 Acompañando al archivo de datos (
745 ) el cual es responsable de la contención de los registros, tendremos tres
746 archivos auxiliares (
758 ) cuya funcionalidad y propósito pasamos a describir a continuación, sin
759 antes remarcar que los tres archivos poseen una sola implementación para
760 las distintas formas de organización física que hemos implementado (tres
761 para ser mas exactos).
764 Entre las ventajas de poseer la misma implementación se encuentra el tener
765 un API común entre los tres tipos para el manejo de la localización de
766 sus registros, administración de espacio libre e Id's liberados, sin necesidad
767 de realizar n-implementaciones para un mismo objetivo final.
770 Además, la obtención de ciertos datos estadísticos como espacio libre, o
771 cantidad de registros, se realiza a través de la misma interfaz, y también
772 se ha facilitado en cierto grado la re-organización física de un archivo
773 (pasar de un tipo a otro), dado el uso de estos tres archivos auxiliares
774 en común para funciones tan predominantes como índexación, administración
775 de espacio libre y recuperación de Id's.
779 \begin_inset LatexCommand \label{sec:idx}
786 El archivo índice (.idx), permite la localización de los registros en el
787 .DAT de forma directa, mediante la obtención de su offset respecto del inicio
788 del .dat, o nro bloque (segun el tipo de organización física) en donde se
789 encuentra un registro dado, indicado por su
794 Los registros de este archivo se encuentran representados una estructura
795 que indica un número de registro y el bloque u offset en donde se encuentra
799 Es necesario que este archivo esté ordenado por
803 , ya que esto permitirá el acceso directo al mismo, para la rápida obtención
804 del nro de bloque u offset y posterior búsqueda de un registro en el archivo
811 Los registros de este archivo se encuentran representados a nivel codigo
812 por el siguiente tipo de dato interno (
819 typedef struct emufs_idx_t {
825 EMUFS_OFFSET location;
832 \begin_inset Float table
839 Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion
845 <lyxtabular version="3" rows="2" columns="3">
847 <column alignment="center" valignment="top" leftline="true" width="0">
848 <column alignment="center" valignment="top" leftline="true" width="0">
849 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
850 <row topline="true" bottomline="true">
851 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
859 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
867 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
875 <row topline="true" bottomline="true">
876 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
884 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
892 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
897 Indica que el registro de id_reg = 5, se encuentra en el bloque 54
909 \begin_inset Float table
916 Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion
922 <lyxtabular version="3" rows="2" columns="3">
924 <column alignment="center" valignment="top" leftline="true" width="0">
925 <column alignment="center" valignment="top" leftline="true" width="0">
926 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
927 <row topline="true" bottomline="true">
928 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
936 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
944 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
952 <row topline="true" bottomline="true">
953 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
961 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
969 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
974 Indica que el registro de id_reg = 5, se encuentra en el bloque 54
994 Como se puede observar, para distintas organizaciones el significado de
995 los registros en este archivo es diferente y se utilizará de distinta manera
1002 Las declaraciones e implementación se pueden encontrar en
1016 \labelwidthstring 00.00.0000
1024 Los registros del archivo indice (
1028 ), poseen una correspondencia 1 a 1, con los Id's de los registros en el
1034 Con esto, queremos decir que el N-ésimo registro del archivo índice, será
1035 aquél que posea la información para localizar al registro cuyo
1039 es N, dentro del archivo de datos (
1049 Cabe aclarar que por si bien el indice se encuentra ordenado por
1053 , los registros en el archivo de datos, por lo general no lo estarán.
1059 emufs_idx_buscar_registro()
1061 \labelwidthstring 00.00.0000
1067 Ante la alta de un registro en el archivo de datos, se insetará un nuevo
1068 registro en el archivo índice, con el id_reg del registro en cuestion,
1069 y el offset u bloque donde se lo haya grabado en disco.
1075 \labelwidthstring 00.00.0000
1081 Ante el borrado de un registro del archivo de datos, se accederá el registro
1082 correspondiente en el índice, y se actualizara su LOCATION, estableciendolo
1083 en el valor especial
1087 , el cual indica que ese registro ha sido eliminado y por ende no se lo
1088 podrá localizar en el futuro.
1089 Como se verá mas adelante, según el tipo de organización física, el registro
1090 puede ser borrado concretamente del .
1101 \labelwidthstring 00.00.0000
1107 Ante la modificación en la posición física de un registro dentro del archivo
1108 de datos (por ejemplo luego del proceso de recompactación, se realizará
1109 la modificación respectiva del campo
1117 emufs_idx_actualizar()
1121 \begin_inset LatexCommand \label{sec:fsc}
1125 Archivo de control de espacio libre
1128 El archivo de espacio libre (
1132 ) (espacio por bloque o gaps en archivo, según el tipo de organización física),
1133 tiene como función la administración del espacio libre, generado por previas
1134 eliminaciones de registros en el archivo de datos.
1135 El mismo, nos indicará donde hay lugar para insertar un nuevo registro.
1138 Para el caso de una organización por bloque, nos dirá en que bloque o si
1139 se debe generar un nuevo bloque.
1140 En el caso de la organización sin bloques, nos indicará en que gap o si
1141 al final del archivo.
1144 Los registros de este archivo se encuentran representados una estructura
1145 que indica un número de bloque u offset y el espacio libre disponible en
1146 el mismo (o apartir del mismo en el caso del offset).
1153 : Por requerimiento del algoritmo de compactación el tipo de organización
1154 física con reg long var, sin bloques, los gaps se graban en forma ordenada
1156 (El orden se corresponde con lo que hay en el .dat).
1162 Los registros de este archivo se encuentran representados a nivel codigo
1163 por el siguiente tipo de dato interno (
1170 typedef struct emufs_fsc_t {
1173 EMUFS_BLOCK_ID marker;
1176 EMUFS_FREE freespace;
1186 \begin_inset Float table
1193 Ejemplo de registro en archivo de control de espacio libre para un archivo
1198 \begin_inset Tabular
1199 <lyxtabular version="3" rows="2" columns="3">
1201 <column alignment="center" valignment="top" leftline="true" width="0">
1202 <column alignment="center" valignment="top" leftline="true" width="0">
1203 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
1204 <row topline="true" bottomline="true">
1205 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1213 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1221 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1229 <row topline="true" bottomline="true">
1230 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1238 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1246 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1251 Indica que en el bloque 12, hay 120 bytes libres al final del mismo.
1263 \begin_inset Float table
1270 Ejemplo de registro en archivo de
1274 para un archivo sin bloques
1278 \begin_inset Tabular
1279 <lyxtabular version="3" rows="2" columns="3">
1281 <column alignment="center" valignment="top" leftline="true" width="0">
1282 <column alignment="center" valignment="top" leftline="true" width="0">
1283 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
1284 <row topline="true" bottomline="true">
1285 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1293 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1301 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1309 <row topline="true" bottomline="true">
1310 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1318 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1326 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1331 Indica que a partir del byte 12 del archivo de datos, hay 120 bytes libres.
1351 Como se puede observar, para distintas organizaciones el significado de
1352 los registros en este archivo es diferente y se utilizará de distinta manera
1356 Funciones principales
1359 Las declaraciones e implementación se pueden encontrar en
1373 \labelwidthstring 00.00.0000
1379 Ante la operación de alta de un registro en el archivo de datos, se realizará
1380 la búsqueda de espacio libre donde este podrá ser insertado.
1381 En el caso de organizaciones con bloques, se buscará en que
1385 se posee espacio suficiente para albergar el nuevo registro.
1386 En el caso de organizacion sin bloque, se buscará un gap o espacio libre
1387 en el archivo, obteniéndose en consecuencia, el
1395 emufs_fsc_buscar_lugar()
1397 \labelwidthstring 00.00.0000
1403 Luego de una operación de baja o alta de un registro en el archivo de datos
1408 ), incrementará o decrementará respectivamente el espacio libre en el archivo
1409 de datos, y esto deberá ser registrado, agregando un nuevo registro en
1410 el archivo de espacios libres (
1414 ) o bien modificandoló.
1418 En el caso de organizaciónes con bloques, se actualizará el valor del espacio
1423 en el bloque (ya sea incrementandoló o decrementandoló) o bien se insertará
1424 un nuevo registro en caso de que se esté creando un nuevo bloque en el
1425 archivo de datos (en este caso no será debido a un alta o baja de registro
1426 como se mencionó al principio).
1430 Para el caso de organización sin bloques, en el caso de baja de un registro
1435 ) se insertará un nuevo registro en el
1439 dando cuenta de la aparición de un nuevo gap en el archivo de datos (
1443 ), y en caso de estar este lindante con otro gap, se realizará el merge
1445 (esto esta explicado más en profundidad en los casos particulares de organizaci
1446 ón fisica, registros variables sin bloques).
1447 Para el caso de una alta en el archivo de datos (
1451 ), el valor del gap donde se haya insertado se actualizará.
1456 emufs_fsc_agregar(), emufs_fsc_agregar_gap(), emufs_fsc_actualizar(), emufs_fsc_
1459 \labelwidthstring 00.00.0000
1465 : Unicamente para el caso de una organización que presente gaps en el archivo,
1466 se podrá dar a lugar la eliminación de un registro del archivo de espacios
1472 Esta situación tendrá efecto cuando se inserte un registro que entre perfecto
1473 en un gap disponible, y por ende el gap desaparecerá.
1477 emufs_fsc_borrar_gap()
1481 \begin_inset LatexCommand \label{sec:did}
1485 Archivo de id's recuperables
1488 El archivo de Id's liberado (
1492 ) llevará cuenta de aquellos Id's de registros (
1496 ) que ya no se encuentran siendo utilizados y fueron liberados por registros
1497 eliminados previamente.
1498 A través del mismo, se podrá realizar la reutilización de Id's ante la
1499 alta de nuevos registros.
1502 A nivel físico, este archivo poseerá una secuencia de datos del tipo EMUFS_REG_I
1503 D, y el comportamiento del sistema de recuperación de Id's será el de una
1505 Es decir, ante el requerimiento de un
1509 libre por una función del sistema como por ejemplo la alta de un nuevo
1510 registro, el API del archivo (
1514 ), obtendrá el último dato del mismo (el
1518 que fue liberado mas recientemente), y truncará el archivo eliminando el
1523 recuperado de la tabla.
1524 (LIFO, Last in First Out).
1530 Este archivo tiene registros de un solo campo,
1534 el cual simboliza al id que fue liberado en un proceso de baja de registros.
1537 Funciones principales
1540 Las declaraciones e implementación se pueden encontrar en
1554 \labelwidthstring 00.00.0000
1560 Ante la eliminación de un registro del archivo de datos (
1564 ) se procederá al agregado del correspondiente
1568 que fue liberado por dicha operación, al archivo
1582 \labelwidthstring 00.00.0000
1588 Cuando el sistema desee grabar un nuevo registro en el archivo de datos,
1593 disponible para el mismo.
1594 El sistema de administración de Id's libres, obtendrá el último
1598 que se guardó en el archivo (o se eliminó del archivo de datos), y truncará
1599 el archivo eliminandolo.
1607 emufs_did_get_last()
1611 \begin_inset LatexCommand \label{cha:tipo1}
1615 Archivo con bloques parametrizados y registros de longitud variable
1618 Este tipo de archivo tiene varias complicaciones, al tratarse de un punto
1620 \begin_inset LatexCommand \ref{cha:tipo2}
1625 \begin_inset LatexCommand \ref{cha:tipo3}
1629 (cuenta tanto con bloques como con registros variables), hereda los inconvenien
1630 tes (y ventajas) de ambos, más los propios.
1631 Al implementar este tipo de archivo se puso enfásis en la eficiencia mientras
1632 esta no comprometa la mantenibilidad del código, es por esto que en algunas
1633 circunstancias no se hace un uso óptimo del espacio.
1636 La implementación de este tipo de archivo puede ser encontrada en
1640 mientras que su interfaz pública está disponible en
1650 El archivo está compuesto por la
1655 \begin_inset LatexCommand \pageref{sec:cabecera_gral}
1660 El valor que toma en este tipo de archivo es 0 (o el valor simbólico
1669 Luego le sigue una cabecera propia del archivo (un
1673 , 4 bytes) que almacena el tamaño del bloque que usa el archivo.
1674 De esta menera, al abrir un archivo de este tipo no se necesita tener ninguna
1675 información sobre él.
1676 A esta cabecera le siguen cero o más bloques del tamaño fijo especificado
1677 en la cabecera antes mencionada.
1683 +-----------+-----------+------------------------//-+
1686 | tipo | tam bloque| Cero o más bloques ...
1694 +-----------+-----------+------------------------//-+
1697 /- 4 bytes -/- 4 bytes -/
1700 Organización física de un bloque
1703 Cada bloque no guarda información en sí, sólo se comporta como un contenedor
1705 Esto no significa que un bloque no tenga utilidad, el bloque es utilizado
1706 para proveer un acceso semi-aleatorio a los registros.
1707 Para esto se utiliza el archivo de índice (ver página
1708 \begin_inset LatexCommand \ref{sec:idx}
1712 ), que almacena pares [identificador de registro, número de bloque].
1713 Para que sea suficiente este único índice para hallar un registro (siendo
1714 que puede haber más de un registro por bloque), es necesario
1716 alinear los registros a izquierda
1719 Esto significa que hay que asegurar que siempre los registros en un bloque
1720 se presenten de forma consecutiva, jamás permitiendo que haya un espacio
1721 libre entre registros (en un mismo bloque).
1724 Podemos ver un ejemplo de esto en forma gráfica:
1727 bloque N-1 | bloque N | bloque N+1
1730 /----------+------------+------------+---------------+-----------/
1735 | registro 1 | registro 2 | espacio libre |
1740 /----------+------------+------------+---------------+-----------/
1743 /------------- tamaño del bloque ---------/
1746 De esta forma, una vez obtenido el número de bloque, se pueda recorrer secuencia
1747 lmente hasta encontrar el registro deseado.
1748 A fin de llevar el conteo de espacio libre se utiliza el archivo de control
1749 de espacio libre (ver página
1750 \begin_inset LatexCommand \ref{sec:fsc}
1754 ), de forma tal que no sea necesario recorrer secuencialmente en busca de
1755 espacio libre al hacer una inserción.
1758 Puede darse un caso excepcional en el que un registro sea más grande que
1759 un bloque, en este caso el registro se almacenará en N bloques consecutivos
1760 (siendo N la cantidad de bloques que necesita el registro), ocupando completos
1761 los todos los bloques a excepción del último, en el que posteriormente
1762 se pueden agregar más registros.
1763 \layout Subsubsection
1766 \begin_inset LatexCommand \label{sub:tipo1_reg}
1770 Organización física de un registro.
1773 El registro es el que representa al dato realmente que se quiere almacenar.
1774 Para representar ese dato se necesita una determinada información de control,
1775 tanto para poder identificar el registro en un bloque (en búsquedas secuenciale
1776 s dentro del bloque) como para saber su longitud (dado que este tipo de
1777 archivo utiliza registros de tamaño variable).
1780 Siguiendo la metodología general de E
1781 \begin_inset Formula $\mu$
1784 FS, se optó por incluir esta información de control como una cabecera al
1785 comienzo del registro, siguiendo a esta los datos en sí.
1786 La cabecera está compuesta por un identificador (
1790 ) de registro (EMUFS_REG_ID, 4 bytes) seguido por el tamaño (
1794 ) del registros (EMUFS_REG_SIZE, 4 bytes).
1795 Podemos ver gráficamente como se se compone un registro:
1801 +-----------+-----------+------------------+
1804 | id | tamaño | datos ...
1808 +-----------+-----------+------------------+
1811 /- 4 bytes -/- 4 bytes -/- [tamaño] bytes -/
1812 \layout Subsubsection
1815 \begin_inset LatexCommand \label{sub:tipo1_reg_multi}
1819 Organización física de un registro más grande que un bloque (registro
1826 Puede darse el caso excepcional en que un registro sea de mayor longitud
1828 Al ser una situación excepcional, no siempre se resuelve de la forma más
1829 eficiente ni se mínimiza el espacio ocupado por datos de control (como
1830 se dijo anteriormente, se prefirió conservar la simpleza del código, adoptando
1831 algoritmos generales aunque no sea de la forma más eficiente o maximizando
1832 el uso del espacio para no perjudicar la mantenibilidad).
1835 Para menejar un registro
1839 se optó por limitarlo a la siguiente estructura (suponiendo que el registro
1840 ocupa N bloques, con N > 1 y que un
1844 es una porción del registro que entra en un bloque):
1851 se almacenan en bloques completos consecutivos.
1854 El último fragmento se almacena al comienzo del bloque inmediatamente posterior
1858 Cada framento posee las cabeceras mencionadas en la sección
1859 \begin_inset LatexCommand \ref{sub:tipo1_reg}
1863 , cuyo contenido es el siguiente:
1871 se almacena el identificador único obtenido al hacer el alta.
1878 se almacena el tamaño del
1882 actual más los tamaños de los
1886 posteriores, quedando en el primer
1890 el tamaño completo del registro y en el último sólo el tamaño del
1898 Como puede observarse, la información de control en los
1902 intermedios puede ser redundante, pero se conserva para poder realizar
1903 algoritmos genéricos (que se basan en que al principio de un bloque, si
1904 no está vacío, hay una cabecera de un registro) y para facilitar chequeos
1905 de integridad del archivo.
1908 A continuación se presenta un ejemplo gráfico de un registro multibloque
1909 de 10 bytes (de contenido
1910 \begin_inset Quotes eld
1914 \begin_inset Quotes erd
1917 ) almacenado en un archivo con bloques de 4 bytes:
1920 | bloque 0 | bloque 1 | bloque 2
1923 +-------------------+-------------------+-------------------+-//-+
1926 | registro 0 - 1/3 | registro 0 - 2/3 | registro 0 - 3/3..|
1933 |+----+-----+------+|+----+-----+------+|+----+-----+----+..| // |
1936 || id | tam | datos||| id | tam | datos||| id | tam |dato|..|
1943 ||----+-----+------+||----+-----+------+||----+-----+----+..| // |
1946 || 0 | 10 | 1234 ||| 0 | 6 | 5678 ||| 0 | 2 | 90 |..|
1953 |+----+-----+------+|+----+-----+------+|+----+-----+----+..| // |
1956 +-------------------+-------------------+-------------------+-
1963 Funciones principales
1966 Las funciones principales son las necesarias para completar la estructura
1968 \begin_inset LatexCommand \pageref{sub:EMUFS}
1975 Lectura de registros
1978 Para leer un registro se hace uso del archivo de índice (ver página
1979 \begin_inset LatexCommand \pageref{sec:idx}
1983 ), obteniéndose el número de bloque en donde está almacenado el registro
1985 Una vez obtenido, se carga en memoria el bloque entero y se busca secuencialmen
1986 te en él (leyendo la cabecera de cada registro y salteando los datos) hasta
1987 encontrar el registro pedido.
1988 Una vez encontrado se lo copia y devuelve.
1991 Si se tratara de un registro
1996 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2000 ), se procede forma similar, sólo que se cargan en memoria uno a uno los
2001 bloques que componen el registro y se van copiando (y uniendo) los
2010 emufs_tipo1_leer_registro()
2016 Para realizar el alta de un registro, lo primero que se obtiene es un identifica
2017 dor, buscando primero en el archivo de identificadores recuperables (pág.
2019 \begin_inset LatexCommand \ref{sec:did}
2023 ) y de no haber ninguno, buscando el mayor identificador presente en el
2024 archivo de índice (pág.
2026 \begin_inset LatexCommand \ref{sec:idx}
2031 El paso siguiente es buscar un bloque con espacio libre suficiente como
2032 para almacenar el registro (y su cabecera) en el archivo de control de
2035 \begin_inset LatexCommand \ref{sec:fsc}
2039 ) y cargarlo completo en memoria.
2040 De no encontrarse, se crea un bloque nuevo al final de archivo.
2041 En el bloque cargado en memoria, se agrega el registro nuevo (con su cabecera)
2042 al comienzo del espacio libre (calculado a partir del tamaño del bloque
2043 y el espacio libre en bloque) y se lo graba en disco.
2044 Finalmente se agrega (o actualiza) el identificador al archivo índice y
2045 el espacio libre en el bloque.
2048 Si el registro ocupara más de un bloque (ver sección
2049 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2053 ), se buscan N bloques consecutivos (todos los que necesite el registro)
2054 absolutamente libres
2060 Incluso el último bloque debe estar absolutamente libre para cumplir con
2061 las condiciones presentadas en la sección
2062 \begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
2069 y graba bloque a bloque cada
2073 del registro (con sus cabeceras intermedias), al último
2077 se lo trata de forma análoga a un registro
2082 Por cada bloque utilizado se actualiza el archivo de control de espacio
2088 emufs_tipo1_agregar_registro()
2094 Al eliminar un registro lo primero que se hace es actualizar los archivos
2095 de índice y de indentificadores recuperables, poniendo como número de bloque
2100 y agregando el identificador del registro a borrar respectivamente.
2101 También se actualiza el archivo de control de espacio libre por cada bloque
2102 (en caso de ser más de uno, en registros
2106 , se actualizan todos los bloques) y se carga el bloque en memoria para
2109 alinear los datos a izquierda
2111 (en caso de ser un registro
2115 , esto se realiza sólo para el último bloque).
2116 Para alinear los datos, se recorre secuencialmente en bloque (leyendo la
2117 cabecera de cada registro y salteando los datos) hasta encontrar el registro
2119 Encontrado el registro, se copian todos los bytes que se encuentran entre
2120 el fin del registro a borrar y el fin del bloque, en el comienzo del bloque
2126 emufs_tipo1_borrar_registro()
2129 Modificación de registros
2132 Se optó por un algoritmo simple y general, que usa las funciones de alto
2133 nivel mencionadas hasta ahora.
2134 Simplemento borra el registro y vuelve a crearlo.
2135 Al recuperar el último identificador de registro borrado, nos aseguramos
2136 de que se mantenga el identificador del registro.
2141 emufs_tipo1_modificar_registro()
2144 Obtención de estadísticas
2147 Es una función bastante simple, con una única complicación que mencionaremos
2151 Para obtener las máximas desviaciones, cantidad total de espacio libre,
2152 cantidad de registros y tamaño de los archivos auxiliares se utilizan las
2153 funciones apropiadas de los archivos auxiliares (ver secciones
2154 \begin_inset LatexCommand \ref{sec:idx}
2159 \begin_inset LatexCommand \ref{sec:fsc}
2164 \begin_inset LatexCommand \ref{sec:did}
2171 Para obtener la cantidad de bloques se hace el siguiente calculo:
2174 cant_bloques = (tamaño_archivo_datos - tamaño_cabecera_archivo_datos)
2180 Hasta aquí no hay mayores inconvenientes.
2181 El problema se presenta para calcular el tamaño de la información de control
2182 utilizada por el archivo de datos; se utiliza el siguiente cálculo:
2185 tam_info_control_datos = tamaño_cabecera_archivo_datos
2188 + cant_registros * tamaño_cabecera_registro;
2191 Aunque a simple vista esto parece acertado, no contempla el caso de los
2197 \begin_inset LatexCommand \pageref{sub:tipo1_reg_multi}
2201 ), estos registros almacenan
2203 tamaño_cabecera_registro * N
2209 es la cantidad de bloques que ocupan.
2210 Salvar este caso sería muy costoso, porque habría que recorrer el archivo
2211 registro a registro,
2219 e ir contando todas las cabeceras de registro que aparecen (similar a lo
2220 que se hace en la compactación, ver sección
2221 \begin_inset LatexCommand \ref{sub:tipo1_compact}
2226 Al tratarse este de un caso excepcional, se optó por mantener la función
2227 simple ya que funciona bien en la mayoría de los casos.
2232 emufs_tipo1_leer_estadisticas()
2236 \begin_inset LatexCommand \label{sub:tipo1_compact}
2240 Compactación del archivo de datos
2243 Esta función es una de las más simples, porque se limita a un algoritmo
2244 muy simple que utiliza las funciones de
2248 antes nombradas para realizar su tarea.
2249 Básicamente recorre el archivo de índices de registros, de comienzo a fin,
2250 leyendo el registro, borrándolo y volviéndolo a insertar.
2251 Si había espacio libre en un bloque anterior al que estaba, será insertado
2252 en él, si no volverá a grabarse en el lugar en que estaba.
2253 De esta forma se aprovechan todos los espacios libres intermedios, concluyendo
2254 con un archivo igual o más pequeño que el original.
2257 Esta implementación no es la más eficiente, pero siendo que esta es una
2258 operación costosa y excepcional por naturaleza, se optó por mantener el
2259 algoritmo simple a costo de un poco de eficiencia.
2264 emufs_tipo1_compactar()
2267 Detalles de implementación (funciones internas, ver si lo ponemos o no)
2271 \begin_inset LatexCommand \label{cha:tipo2}
2275 Archivo sin bloques y registros de longitud variable
2278 Este tipo de archivo nos traerá a la mesa la particularidad de grabar registros
2279 de longitud variable sin realizar su agrupación en bloques, y como veremos
2280 en la siguiente sección, tambien permitirá la administración de gaps que
2281 queden en el archivo luego de operaciones de baja de registros.
2287 Este tipo de archivo realizará el almacenamiento de registros de longitud
2288 variable en disco, su borrado y modificación sin la utilización de bloques
2290 Su implementación se encuentra en los archivos fuente (
2301 Los archivos del tipo 2, presentarán al comienzo del mismo un header compuesto
2302 simplemente por un dato del tipo EMUFS_Tipo (int) el cual indicará el tipo
2303 de archivo en cuestión.
2306 Para poder entender mejor la organización fisica de este tipo de archivo,
2307 tomemos el caso hipotético en el que se encuentran grabados
2311 (comenzando desde registro 0) de
2320 Supongamos también que entre el registro 0 y 1 se encontraba un
2322 registro de 10 bytes
2337 Si miramos al archivo de datos (.dat) en el disco nos encontraremos con
2339 \begin_inset Float figure
2346 Organización física de los registros en disco
2350 \begin_inset Graphics
2351 filename graphics/Example1.png
2362 Como se puede observar, a nivel físico cada registro grabado esta compuesto
2363 por un Header cuyo tamaño total es de 8 bytes (
2371 ), y posteriormente el registro (bloque de datos) en sí.
2372 Luego se encuentra el espacio libre de 18 bytes dejado por el registro
2373 de 10 bytes eliminado (10 bytes de datos + header de 8 bytes) y finalmente
2374 el segundo registro mencionado.dsds
2377 Comportamiento Particular de los Archivos Auxiliares
2380 Como fue explicado al inicio de la documentación, la implementación de cualquier
2381 a de las tres organizaciones físicas de archivos presenta la necesidad de
2382 poseer tres archivos auxiliares que actuarán como índice de direcciones
2387 ), administrador de espacio libre (
2391 ) y administrador de Id's liberados (
2398 No obstante, cada tipo de organización presentara sus particularidades respecto
2399 de estos tres archivos, las cuales describiremos a continuación en caso
2401 \layout Subsubsection
2403 Archivo índice o de posiciones relativas (.idx)
2410 ), permite la localización de los registros en el .DAT de forma directa,
2411 mediante la obtención de su offset o posición relativa respecto del inicio
2416 en donde se encuentra un registro dado, indicado por su ID.
2419 Así pues, si tomamos el ejemplo descripto al inicio de este capítulo, tendremos
2420 las siguientes entradas en el archivo índice
2425 \begin_inset Float table
2432 Organización física del archivo de índice o posiciones relativas.
2436 \begin_inset Tabular
2437 <lyxtabular version="3" rows="3" columns="3">
2439 <column alignment="center" valignment="top" leftline="true" width="0">
2440 <column alignment="center" valignment="top" leftline="true" width="0">
2441 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
2442 <row topline="true" bottomline="true">
2443 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2453 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2463 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2471 <row topline="true">
2472 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2482 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2492 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2497 El primer registro (reg0) comienza en el byte 4
2501 <row topline="true" bottomline="true">
2502 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2510 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2520 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2525 El segundo registro (reg1) comienza en el byte 60
2545 LOCATION indica donde comienza el header del registro buscado, y por consiguien
2546 te luego del header tendremos el registro en sí (los datos).
2547 \layout Subsubsection
2549 Achivo de Gaps / Espacios Libres (.fsc)
2552 El archivo de espacios libres o gaps (.fsc), tiene como función la administración
2553 del espacio libre o gaps (agujeros), generados por previas eliminaciones
2554 de registros en el archivo de datos.
2555 El mismo, nos indicará donde hay lugar para insertar un nuevo registro
2556 (se podrán insertar en algún gap acorde, o bien al final del archivo).
2557 Este archivo será utilizado tambien para el proceso de compactación de
2558 un archivo, explicado luego.
2561 Así pues, si tomamos el ejemplo descripto al inicio del documento, tendremos
2562 las siguientes entradas en el archivo índice
2567 \begin_inset Float table
2574 Organización física del archivo de
2578 o control de espacio libre.
2582 \begin_inset Tabular
2583 <lyxtabular version="3" rows="2" columns="3">
2585 <column alignment="center" valignment="top" leftline="true" width="0">
2586 <column alignment="center" valignment="top" leftline="true" width="0">
2587 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
2588 <row topline="true" bottomline="true">
2589 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2599 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2609 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2617 <row topline="true" bottomline="true">
2618 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2628 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
2638 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
2643 18 bytes libres a partir del byte 42 del .dat
2663 Por requerimiento del algoritmo de compactación, los gaps se graban en
2664 forma ordenada en el (.fsc).
2665 (El orden se corresponde con lo que hay en el
2670 \layout Subsubsection*
2675 Si bien la utilización concreta de los GAPS será explicada posteriormente
2676 en la ALTA y BAJA de registros, debemos remarcar la funcionalidad de MERGING
2677 que posee nuestro sistema FSC.
2680 Ante la eliminación de un registro del archivo de datos, se generara por
2681 consiguiente un gap o espacio libre en alguna posición del archivo.
2682 Ese gap deberá ser registrado en el archivo de gaps (.fsc).
2683 Ahora bien, nuestro sistema de gaps, contemplará como es debido, la posibilidad
2684 de que se haya eliminado un registro que posee un GAP por delante, un GAP
2685 por detrás, o bien un GAP por delante y por detrás del mismo.
2688 Nuestro sistema actuará en consecuencia, realizando un merge de los espacios
2689 libres, y unificándolos en una UNICA entrada en el archivo .fsc, que contendrá
2690 como dato de freespace, la suma correspondiente de los espacios libres
2692 \layout Subsubsection
2694 Archivo de ID's liberados (.did)
2697 El archivo de ID's liberados no presenta ningún aspecto particular en este
2698 tipo de organización.
2699 Remitirse al capítulo correspondiente a los archivos auxiliares para consultar
2700 su estructura y funcionamiento.
2703 Funciones Principales
2718 se encuentran las cabeceras y la implementación de las funciones principales
2719 respectivamente, las cuales dan funcionalidad a esta organización.
2723 A continuación se comentará el funcionamiento algunas de las mas importantes.
2726 Lectura de registros
2729 Como se vió al comienzo, los registros en este tipo de archivo no se encuentran
2730 agrupados en bloques de ninguna índole y estan dispersos a lo largo del
2731 archivo, con la particularidad de que pueden existir gaps o espacio libre,
2732 entre dos registros dados.
2735 Por ende la lectura de registros en este tipo de organización es muy simple
2736 y dada la inexistencia de bloques, el procedimiento será el siguiente:
2739 Se determina el offset en bytes, donde comienza el registro deseado, a través
2740 de su ID, buscando la misma en el archivo índice (
2747 Ya determinada la posición física del registro dentro del archivo de datos
2752 ), nos posicionamos en la misma, y leemos el header del registro (
2761 Contando así con el tamaño del registro, procedemos a leer el mismo (los
2762 datos), dando por finalizada la lectura.
2767 emufs_tipo2_leer_registro()
2773 En el proceso de alta de registros entrarán en juego dos archivos descriptos
2776 sección de archivos auxiliares
2778 , siendo estos el archivo índice (
2782 ), y el archivo de gaps / espacios libres (
2789 Así pues, a la hora de realizar una inserción de un registro en el archivo
2790 de datos, el procedimiento será el siguiente:
2793 Calculamos el espacio que necesitaremos para el registro: sizeof(
2801 ) + sizeof(registro).
2804 Determinamos donde debemos insertar el registro, ya sea un gap donde entre,
2805 o bien al final del archivo.
2808 Insertamos el registro e información de control (
2816 ), en la posición indicada en el paso 2.
2819 En caso de haber utilizado un GAP, actualizamos el espacio libre restante
2820 en el mismo y en caso de que se haya utilizado al totalidad del GAP, se
2821 lo elimina del archivo (
2828 Actualizamos la entrada correspondiente al registro ingresado (determinada
2829 por su RegID), en el archivo índice (
2833 ), indicando su offset donde podrá ser accedido luego.
2838 emufs_tipo2_agregar_registro()
2844 En el proceso de baja de registros entrarán en juego los tres archivos descripto
2847 sección de archivos auxiliares
2849 , siendo estos el archivo índice (
2853 ), el archivo de gaps / espacios libres (
2857 ) y el archivo de ID's liberados (
2864 Dado que en la implementación de este tipo de organización física contamos
2865 con los gaps o espacios libres entre registros, no se eliminará fisicamente
2866 el registro del archivo de datos (
2870 ), pues entonces carecería de sentido el archivo anteriormente mencionado
2876 En cambio, se agrega el gap dejado por la eliminación a dicho archivo,
2877 y se marca fisicamente en el archivo de datos la eliminación mediante un
2878 fill de los bytes correspondientes con un caracter nulo.
2879 (hexa 00 y con el propósito de probar fehacientemente que el sistema funciona).
2882 El proceso de baja o eliminación de un registro constará luego de los siguientes
2886 Se obtiene el offset o posición relativa en donde se encuentra grabado el
2887 registro dentro del archivo de datos.
2890 Se obtiene el tamaño del registro y se realiza un dummyfill del sector del
2891 archivo correspondiente al registro que se está dando de baja.
2892 (Se rellena la zona correspondiente a su header+data).
2895 Se agrega el GAP generado al archivo de gaps o espacios libres, y en caso
2896 de haberse generado un GAP lindante con otro GAP, se realizará un merge
2897 de los mismos y se los registrará bajo una única entrada en el archivo
2898 de espacios libres (.fsc).
2901 Se agrega el ID que fue liberado, al archivo de ID's liberados (
2905 ), al final del mismo (
2912 Se marca en el archivo índice (
2916 ) la eliminación, mediante el valor ¨-1¨ en el registro correspondiente
2917 al registro recién eliminado (se le cambia el valor al n-esimo registro,
2918 donde N = IDReg del reg eliminado).
2923 emufs_tipo2_borrar_registro()
2926 Modificación de registros
2929 Dada la naturaleza del archivo de ID's liberados, y el manejo de espacio
2930 libre del que consta esta organización de archivo, el proceso de modificación
2931 de un registro se limita a los siguientes pasos:
2934 Se realiza la lectura del registro, mediante el respectivo procedimiento
2935 ya desarollado anteriormente.
2938 Una vez que se cuenta con los nuevos datos modificados, se procede a dar
2939 de baja el registro que ha sido modificado, e inmediatamente después se
2940 realiza una inserción con los nuevos datos.
2949 Como fue indicado, dada la naturaleza de PILA del subsistema de administración
2950 de ID liberados, es asegurado que la nueva inserción del registro modificado
2951 se realizará con el mismo RegID.
2956 emufs_tipo2_modificar_registro()
2959 Obtención de estadísticas
2962 Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
2963 cantidad de bloques, cantidad de registros, espacio libre total, espacio
2964 libre promedio, espacio libre máximo y mínimo, etc.
2967 Esta información es el resultado de ciertos cálculos realizados tanto en
2968 el archivo de datos como en los archivos índice.
2971 Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
2972 del archivo de datos, espacio libre total, cantidad de registros, cantidad
2973 de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
2979 emufs_tipo2_leer_estadisticas()
2982 Compactación del archivo de datos
2985 Asi como los otros dos tipos de datos, el que nos compete también cuenta
2986 con la posibilidad de realizar la compactación de datos cuando el usuario
2987 lo desee, justificando todos los registros a izquierda, eliminando así
2988 los gaps existentes y decrementando el tamaño del archivo en disco (truncandolo
2992 Para poder comprender como hemos implementado el proceso de recompactación
2993 en nuestro tipo de archivo 2, nos ayudaremos de esquemas a través de los
2994 cuales iremos describiendo el proceso.
2995 Notemos antes, que el proceso de compactación esta directamente ligado
2996 con el archivo de gaps o espacios libres (
3003 Comenzemos con el siguiente cuadro situacional:
3004 \begin_inset Float figure
3011 Archivo con gaps entre registros previo a compactación
3015 \begin_inset Graphics
3016 filename graphics/Compact1.png
3028 Partiendo de esta base, el algoritmo de compactación tomará en su inicio
3029 al primer gap existente dentro del archivo de datos, en este caso llamado
3035 Luego, establecerá que el
3039 a partir de donde se quieren mover datos, sera:
3042 StartGap0 + SizeGap0 = EndGap0 = Source
3045 Lo cual no es nada más y nada menos que lo obvio, la fuente a partir de
3046 donde se mueven los datos, sera el fin del primer gap, donde comienzan
3052 ) del movimiento, se establece inicialmente, el inicio del gap, o sea
3054 StartGap0 = Destination
3059 Luego, el algoritmo entrara en un bucle while (mientras haya bucles por
3060 levantar), el cual trabajara hasta el final de la compactación de la siguiente
3071 Se levanta el proximo gap al levantado en una instancia previa.
3072 En este ejemplo, durante el primer loop del while, se levantará
3077 Luego, se calcula cuantos bytes hay que mover hacia el Destination de la
3101 Lo cual nuevamente es lógico pues querremos mover lo que se encuentra entre
3102 el final del primer gap levantado y el inicio del siguiente).
3105 Se realiza el movimiento de los datos, utilizando las direcciones
3113 , así como la variable
3117 que nos indica cuantos bytes transferir.
3123 La transferencia se hace de a chunks de 25 bytes + un resto segun el valor
3127 Se establece como gap de referencia, al ultimo gap leido (En este caso se
3140 ) y termina el código de repetición del bucle, dando lugar a la carga del
3141 siguiente gap en el inicio del mismo.
3149 Luego del primer bucle, el archivo se vera de la siguiente forma:
3150 \begin_inset Float figure
3157 Archivo con gaps en disco luego del primer bucle de compactación
3161 \begin_inset Graphics
3162 filename graphics/Compact2.png
3173 Notemos que al final de la porción de datos de los bytes movidos (donde
3178 ), hay basura que será pisada por el próximo movimiento.
3181 En el próximo loop, el bucle levantará un nuevo gap, y utilizando el gap
3182 anterior (En esta caso el Gap anterior será
3186 ) como referencia, realizará los mismos cálculos, desde donde transferir
3187 y cuantos bytes mover.
3188 (El destino es solo establecido inicialmente por código, y para el resto
3189 del algoritmo es el lugar donde quedo el puntero destination luego de la
3193 Una vez que se salga del bucle while, se realizará un último movimiento
3194 preprogramado, donde la fuente (
3198 ) será el final del ultimo gap, y la cantidad de bytes a mover será lo que
3199 se encuentre luego del mismo hasta el fin de archivo.
3202 Source = StartLastGap + SizeLastGap = EndLastGap
3205 Mustmove_bytes = Datsize - Source
3208 Damos por terminada así, la explicación del algoritmo de compresión el cual
3209 para el caso del tipo 2, es realmente bastante sencillo.
3214 emufs_tipo2_compactar()
3217 Consideraciones y Políticas de Diseño
3220 Se han tomado ciertas consideraciones para algunos casos particulares que
3221 se pueden presentar durante el uso/ejecución de la aplicación, así como
3222 tambien politicas respecto del diseño e implementación del sistema:
3225 En la organización física tipo 2 para los registros que se graban en disco
3226 hemos decidido utilizar como encabezado de cada uno de ellos, los datos
3227 [ID_REG][REG_SIZE], los cuales fueron detallados previamente.
3228 Si bien se podría haber descartado el grabado del ID del registro en el
3229 archivo de datos y puede parecer redundante, dado que poseemos el archivo
3230 índice con el offset directo, el mismo se lo graba por distintos motivos:
3234 A) En caso de la corrupción del archivo índice (.idx), podremos gracias a
3235 que poseemos en el archivo de datos, el ID de cada registro, recrear dicho
3236 índice, ayudándonos del archivo de espacios libres (
3240 ), para poder saltear los espacios libres y e ir recorriendo secuencialmente
3241 los registros, reconstruyendo así el índice en cuestión.
3242 (esta función de reconstrucción no pudo ser implementada para esta entrega,
3243 pero es una posibilidad real).
3247 B) Luego de un proceso de recompactación, los espacios libres que pudieron
3248 haber existido en el archivo de datos (
3252 ), son eliminados y los registros han cambiado de posición.
3253 Por ello, recorriendo secuencialmente por única vez el archivo de datos,
3254 se procede a la actualización / reconstrucción del índice de direcciones
3262 Si se desea insertar un registro y no se puede hayar un gap o espacio libre
3263 donde quepa, se los inserta al final del archivo.
3266 Ante una operación de baja de un registro, el mismo no es físicamente borrado
3267 del archivo de datos (
3271 ), simplemente los bytes que ocupa son llenados con hexa (00).
3272 Paralelamente, se procede a actualiza el archivo índice, insertando como
3273 valor de OFFSET para el registro eliminado, el valor ¨-1¨, indicando así
3274 la inexistencia del registro para el futuro, y por otro lado se genera
3275 la entrada de espacio libre en el archivo de gaps (
3282 La reutilización de ID's liberados por previas operaciones de baja de registros,
3283 se ve implementada por el archivo de ID liberados (.did), y su comportamiento
3284 es el de una pila por lo que el último ID liberado, sera el próximo a ser
3288 Como fue explicado en la implementación del archivo índice, existe una correspon
3289 dencia 1 a 1 entre los registros allí presentes (en el .idx) y los ID's de
3290 los registros, por lo cual el registro N-ésimo del archivo índice, será
3291 el correspondiente al registro de datos cuyo ID es igual a N.
3294 El proceso de compactación de archivos, realiza los movimientos de información
3295 requeridos para dicho propósito de a chunks de 25 bytes por vez.
3296 Este valor es fijo, pero se lo podría hacer parametrizable mediante la
3297 GUI en próximas entregas.
3301 \begin_inset LatexCommand \label{cha:tipo3}
3305 Archivo con bloques parametrizados y registros de longitud constante
3308 Las distintas organizaciones de archivos buscan aprovechar al máximo el
3309 espacio del archivo.
3312 En este caso veremos que sucede luego de agregar y borrar una gran cantidad
3313 de registros del archivo, lo que provoca como consecuencia directa la fragmenta
3314 ción del archivo, es decir, quedan huecos entre un registro y otro, lo que
3315 produce un desperdicio de espacio.
3318 La implementación de este tipo de archivo puede ser encontrada en
3322 mientras que su interfaz pública está disponible en
3332 Esta organización guarda los registros pertenecientes al archivo en bloques
3333 de tamaño parametrizado, de modo que intentará guardar la mayor cantidad
3334 de registros que quepan en un bloque.
3338 Así como los graba, también tendrá la posibilidad de leer registros y borrarlos
3342 El archivo estara compuesto por una cabecera que da información sobre el
3343 tipo de organización, el tamaño de los bloques y el tamaño de los registros.
3346 Organización Física de un Bloque
3349 Cada bloque será capaz de contener la cantidad de registros enteros que
3351 De esta manera un registro que no entre completamente en el bloque deberá
3352 almacenarce en un bloque diferente.
3355 Los bloques no contienen ninguna información adicional, solo se conoce su
3356 tamaño y se usa para delimitar
3357 \begin_inset Quotes eld
3361 \begin_inset Quotes erd
3364 zonas en el archivo.
3367 Organizacion Física de Registros
3370 Cada registro se almacena en un bloque, y contiene una cabecera que indica
3375 por este motivo al realizar la busqueda de espacio en un bloque se lo hará
3376 preguntando por el tamaño del registro más
3378 sizeof(EMUFS_REG_ID).
3382 Organización Física de Registros Multibloque
3385 Al ser los registros de longitud constante, se ha adoptado que un registro
3386 multibloque nunca podra estar almacenado en algún lugar que no sea el comienzo
3388 De esta manera se puede calcular cuantos bloques ocupará un registro y
3389 se podrá solicitar lugar para almacenarlo con la ayuda de la función
3391 emufs_fsc_buscar_n_lugares(),
3393 que es muy importante para evitar el solapamiento de registros.
3394 Esta consideración acarrea como consecuencia directa un alto costo en términos
3395 del espacio desperdiciado.
3398 Funciones Principales
3409 se encuentran las cabeceras y la implementación de las funciones principales
3410 respectivamente, las cuales dan funcionalidad a esta organización.
3413 A continuación se comentará la descripción de algunas acciones importantes.
3419 La lectura de un registro se realiza con la ayuda del archivo .
3423 el cual contiene la información de la posición del registro dentro del
3425 Una vez leida esta información, se recupera el bloque (en su totalidad)
3426 del archivo y se busca secuencialmente el registro con el
3435 emufs_tipo3_leer_registro()
3441 Graba un registro en un bloque donde haya espacio suficiente, y si no crea
3442 un nuevo bloque y lo agrega al final del archivo.
3445 Luego de grabar un registro, actualiza los archivos de índice .idx y .fsc
3446 para mantener la coherencia.
3451 emufs_tipo3_grabar_registro()
3457 Borra un registro del archivo de datos, para esto levanta el bloque al que
3458 pertenece el archivo y ajusta los demás registros justificandolos hacia
3462 Cabe destacar que para dar de baja un registro no hace falta borrarlo del
3463 archivo de datos, solo es necesario borrar las entradas en los archivos
3464 de índice, pero cuando se realiza el ajuste el algoritmo toma porciones
3465 del bloque del tamaño de un registro mas su encabezado - comenzando desde
3466 el siguiente al que fue borrado - y copia (sobreescribe) sobre el anterior.
3467 De esta manera, la información correspondiente al registro borrado no estará
3468 presente en el archivo de datos.
3469 Esto es una consecuencia del ajuste al borrar un registro, pudiendo no
3470 ser así, si no se realizara el mismo.
3475 emufs_tipo3_borrar_registro()
3481 Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
3482 cantidad de bloques, cantidad de registros, espacio libre total, espacio
3483 libre promedio, espacio libre máximo y mínimo, etc.
3486 Esta información es el resultado de ciertos cálculos realizados tanto en
3487 el archivo de datos como en los archivos índice.
3490 Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
3491 del archivo de datos, espacio libre total, cantidad de registros, cantidad
3492 de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
3498 emufs_tipo3_leer_estadisticas()
3501 Compactar el Archivo
3504 Esta función intenta reorganizar el archivo de manera que el espacio libre
3505 sea lo menor posible, recordando siempre que un registro no puede ser almacenad
3506 o en mas de un bloque excepto que el tamaño del registro sea mayor que el
3510 Para realizar esto, se aprovecha la funcionalidad de
3512 emufs_tipo3_grabar_registro()
3514 ya que esta tiene la capacidad de determinar una posición mas eficiente
3515 en el archivo para un registro.
3516 Por esto lo que se hace es levantar uno por uno los registros y volverlos
3517 a grabar, de ese modo todos los
3521 que pudieron haberse formado por la eliminación de registros serán cubiertos
3525 Al estar utilizando recuperación de
3529 borrados, esto me asegura que el registro borrado-guardado conservará el
3533 Al finalizar este proceso se verifica si existen bloques vacios para truncar
3535 Lo mismo se debe hacer con el archivo de espacios libres .
3539 el cual disminuye su tamaño también.
3544 void emufs_tipo3_compactar()
3547 Consideraciones y Políticas de Diseño
3550 Se han tomado ciertas consideraciones para algunos casos particulares que
3551 se pueden presentar durante el uso/ejecución de la aplicación.
3554 Cada registro tiene un encabezado que indica el
3561 Si el tamaño del registro es mayor que el tamaño del bloque el registro
3562 se particionará en la cantidad de bloques que sea necesario, pero siempre
3563 se guardará desde el comienzo de un bloque, esto quiere decir que nunca
3564 se podrá encontrar un comienzo de registro en algún lugar de un bloque
3565 que no sea el comienzo del mismo.
3568 Si el registro se divide en mas de un bloque, se le coloca el id como encabezado
3569 igualmente, pero en el archivo .
3573 solo se guarda el primer bloque.
3578 se actualizan todos los bloques con el espacio libre que realmente tienen.
3584 Las comparaciones, pruebas, etc...