doc/informe.lyx

   1 #LyX 1.3 created this file. For more info see http://www.lyx.org/
   2 \lyxformat 221
   3 \textclass book
   4 \language spanish
   5 \inputencoding auto
   6 \fontscheme palatino
   7 \graphics default
   8 \paperfontsize default
   9 \spacing single
  10 \papersize a4paper
  11 \paperpackage widemarginsa4
  12 \use_geometry 0
  13 \use_amsmath 0
  14 \use_natbib 0
  15 \use_numerical_citations 0
  16 \paperorientation portrait
  17 \secnumdepth 3
  18 \tocdepth 3
  19 \paragraph_separation indent
  20 \defskip medskip
  21 \quotes_language english
  22 \quotes_times 2
  23 \papercolumns 1
  24 \papersides 1
  25 \paperpagestyle default
  26
  27 \layout Title
  28
  29 E
  30 \begin_inset Formula $\mu$
  31 \end_inset
  32
  33 FS
  34 \layout Author
  35
  36 Nicolás Dimov
  37 \newline
  38 Alan Kennedy
  39 \newline
  40 Leandro Lucarella
  41 \newline
  42 Ricardo Markiewicz
  43 \layout Chapter
  44
  45 Introducción
  46 \layout Chapter
  47
  48 Estructura común
  49 \layout Section
  50
  51 Tipos
  52 \layout Subsection
  53
  54 EMUFS
  55 \layout Standard
  56
  57
  58 \emph on
  59 EMUFS
  60 \emph default
  61 es la estuctura principal que encapsula todas las funciones para el manejo
  62  de un archivo de datos.
  63 \layout Standard
  64
  65 Esta estructura consta de:
  66 \layout Enumerate
  67
  68 EMUFS_Tipo que es un tipo enumerado que indica cual es la organización.
  69 \layout Enumerate
  70
  71 EMUFS_BLOCK_SIZE indica el tamaño del bloque para los tipos 1 y 3.
  72 \layout Enumerate
  73
  74 EMUFS_REG_SIZE indica el tamaño del registro, para el tipo 3 que posee tamaño
  75  constante.
  76 \layout Enumerate
  77
  78 void *leer_bloque()
  79 \layout Comment
  80
  81 no me convence esta descripcion.
  82
  83 \layout Subsection
  84
  85 EMUFS_Tipo
  86 \layout Subsection
  87
  88 EMUFS_Estadisticas
  89 \layout Subsection
  90
  91 EMUFS_BLOCK_ID
  92 \layout Standard
  93
  94 etc
  95 \layout Chapter
  96
  97 Archivos Auxiliares
  98 \layout Comment
  99
 100 Por que los 3 tipos usan los mismo.
 101  Ventajas y desventajas.
 102 \layout Section
 103
 104 Archivo de índice (.idx)
 105 \layout Standard
 106
 107 Con la ayuda de un archivo de bloques y registros (de extensión .idx), podremos
 108  ubicar cualquier registro existente dentro del archivo.
 109 \layout Standard
 110
 111 El archivo de índice contiene una estructura que contiene el id de un registro
 112  y el número de bloque al que pertenece.
 113  Este archivo esta ordenado por
 114 \emph on
 115 id
 116 \emph default
 117 , de modo que incrementa su tamaño cada vez que se grabe en el archivo de
 118  datos un nuevo registro, excepto que un registro haya sido borrado con
 119  anterioridad lo cual produce que al guardar un nuevo registro se actualice
 120  y no crezca.
 121 \layout Standard
 122
 123 Si un registro es borrado del archivo de datos, debe actualizarse el índice,
 124  esto se logra colocando un flag que indique que el id no pertenece a ningún
 125  bloque, hemos adoptado poner -1 en el campo location de la estructura
 126 \emph on
 127 EMUFS_IDX
 128 \emph default
 129 .
 130 \layout Standard
 131
 132 Es necesario que este archivo esté ordenado por
 133 \emph on
 134 id
 135 \emph default
 136  de registro, ya que esto permitirá el acceso directo para la búsqueda de
 137  un registro en el archivo de datos.
 138 \layout Subsection
 139
 140 Estructura física
 141 \layout Standard
 142
 143 El tipo EMUFS_IDX define la estuctura de los registros de este archivo.
 144 \layout Standard
 145
 146 Esta estructura está compuesta por don enteros (long).
 147 \layout Itemize
 148
 149 EMUFS_REG_ID reg_id indica el
 150 \emph on
 151 id
 152 \emph default
 153  del registro
 154 \layout Itemize
 155
 156 EMUFS_BLOCK_ID location número de bloque donde se encuentra el registro.
 157 \layout Standard
 158
 159 EMUFS_REG_ID y EMUFS_BLOCK_ID son
 160 \emph on
 161 unsigned long.
 162 \layout Comment
 163
 164 ponerlo mas lindo...
 165 \layout Subsection
 166
 167 Comportamiento (funciones generales)
 168 \layout Section
 169
 170 Archivo de control de espacio libre (.fsc)
 171 \layout Standard
 172
 173 idem anterior
 174 \layout Section
 175
 176 Archivo de índices recuperables (.did)
 177 \layout Standard
 178
 179 idem anterior
 180 \layout Chapter
 181
 182 Archivo con bloques parametrizados y registros de longitud variable
 183 \layout Standard
 184
 185 introduccion
 186 \layout Section
 187
 188 Organización física
 189 \layout Section
 190
 191 Comportamiento (funciones de la interfáz)
 192 \layout Section
 193
 194 Detalles de implementación (funciones internas, ver si lo ponemos o no)
 195 \layout Chapter
 196
 197 Archivo sin bloques y registros de longitud variable
 198 \layout Standard
 199
 200 introduccion
 201 \layout Section
 202
 203 Organización física
 204 \layout Section
 205
 206 Comportamiento (funciones de la interfáz)
 207 \layout Section
 208
 209 Detalles de implementación (funciones internas, ver si lo ponemos o no)
 210 \layout Chapter
 211
 212 Archivo con bloques parametrizados y registros de longitud constante
 213 \layout Standard
 214
 215 Las distintas organizaciones de archivos buscan aprovechar al máximo el
 216  espacio del archivo.
 217 \layout Standard
 218
 219 En este caso veremos que sucede luego de agregar y borrar una gran cantidad
 220  de registros del archivo, lo que provoca como consecuencia directa la fragmenta
 221 ción del archivo, es decir, quedan huecos entre un registro y otro, lo que
 222  produce un desperdicio de espacio.
 223 \layout Section
 224
 225 Organización Física
 226 \layout Standard
 227
 228 Esta organización guarda los registros pertenecientes al archivo en bloques
 229  de tamaño parametrizado, de modo que intentará guardar la mayor cantidad
 230  de registros que quepan en un bloque.
 231
 232 \layout Standard
 233
 234 Así como los graba, también tendrá la posibilidad de leer registros y borrarlos
 235  del archivo.
 236 \layout Subsection
 237
 238 Comportamiento Particular de los Archivos Auxiliares
 239 \layout Subsubsection
 240
 241 Archivo de Bloques y Registros (.idx)
 242 \layout Comment
 243
 244 buscar algun caso extraordinario.
 245 \layout Subsubsection
 246
 247 Archivo de Bloques y Espacio Libre (.fsc)
 248 \layout Standard
 249
 250 El archivo de de espacios libres permite decidir a la hora de guardar un
 251  registro, donde será guardado.
 252
 253 \layout Standard
 254
 255 La estructura de este archivo está formada por un número que indica el bloque
 256  y otro que indica el espacio libre en él.
 257 \layout Standard
 258
 259 De esta manera al querer guardar un registro este archivo informará donde
 260  cabe el mismo, previa invocación al la función
 261 \emph on
 262 EMUFS_BLOCK_ID emufs_fsc_buscar_lugar(EMUFS *, EMUFS_FREE, EMUFS_FREE*)
 263 \emph default
 264  perteneciente a fsc.h, la cual devuelve el número de bloque donde entra
 265  el registro o -1 si no hay un bloque con lugar suficiente, y toma como
 266  parámetros una estructura
 267 \emph on
 268 EMUFS
 269 \emph default
 270 , y dos
 271 \emph on
 272 EMUFS_FREE
 273 \emph default
 274  donde el segndo parámetro es el tamaño buscado, y el tercero devuelve el
 275  tamaño disponible.
 276 \layout Standard
 277
 278 De la misma manera, al borrar un registro este archivo debe ser actualizado
 279  colocando el nuevo espacio libre en el bloque.
 280 \layout Subsubsection
 281
 282 Archivo de Id`s Borrados (.did)
 283 \layout Standard
 284
 285 Este archivo funciona como una pila de id`s borrados, es decir, cuando se
 286  borra un registro el id se almacena en este archivo y será recuperado cuando
 287  se desee grabar un registro nuevo, de esta manera se aprovechan todos los
 288  id`s sin necesidad de crear uno nuevo cada vez que se borra y graba un
 289  registro.
 290 \layout Section
 291
 292 Funciones Principales
 293 \layout Subsection
 294
 295 EMUFS Tipo 3
 296 \layout Standard
 297
 298 Dento de
 299 \emph on
 300 tipo3.h
 301 \emph default
 302  y
 303 \emph on
 304 tipo3.c
 305 \emph default
 306  se encuentran las cabeceras y la implementación de las funciones principales
 307  respectivamente, las cuales dan funcionalidad a esta organización.
 308 \layout Standard
 309
 310 A continuación se comentará la descripción de algunas acciones importantes.
 311 \layout Subsubsection
 312
 313 Leer Registro
 314 \layout Standard
 315
 316 La lectura de un registro se realiza con la ayuda del archivo .
 317 \emph on
 318 idx
 319 \emph default
 320  el cual contiene la información de la posición del registro dentro del
 321  archivo de datos.
 322  Una vez leida esta información, se recupera el bloque (en su totalidad)
 323  del archivo y se busca secuencialmente el registro con el
 324 \emph on
 325 ID
 326 \emph default
 327  especificado.
 328 \layout Standard
 329
 330
 331 \emph on
 332 ver: void* emufs_tipo3_leer_registro(EMUFS *emu, EMUFS_REG_ID ID, EMUFS_REG_SIZE
 333 * reg_size, int* err)
 334 \layout Subsubsection
 335
 336 Grabar Registro
 337 \layout Standard
 338
 339 Graba un registro en un bloque donde haya espacio suficiente, y si no crea
 340  un nuevo bloque y lo agrega al final del archivo.
 341 \layout Standard
 342
 343 Luego de grabar un registro, actualiza los archivos de índice .idx y .fsc
 344  para mantener la coherencia.
 345 \layout Standard
 346
 347
 348 \emph on
 349 ver: EMUFS_REG_ID emufs_tipo3_grabar_registro(EMUFS *emu, void *ptr, EMUFS_REG_S
 350 IZE tam, int* err)
 351 \layout Subsubsection
 352
 353 Borrar Registro
 354 \layout Standard
 355
 356 Borra un registro del archivo de datos, para esto levanta el bloque al que
 357  pertenece el archivo y ajusta los demás registros justificandolos hacia
 358  la izquierda.
 359 \layout Standard
 360
 361 Cabe destacar que para dar de baja un registro no hace falta borrarlo del
 362  archivo de datos, solo es necesario borrar las entradas en los archivos
 363  de índice.
 364 \layout Subsubsection
 365
 366 Leer Estadísticas
 367 \layout Standard
 368
 369 Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
 370  cantidad de bloques, cantidad de registros, espacio libre total, espacio
 371  libre promedio, espacio libre máximo y mínimo, etc.
 372 \layout Standard
 373
 374 Esta información es el resultado de ciertos cálculos realizados tanto en
 375  el archivo de datos como en los archivos índice.
 376 \layout Standard
 377
 378 Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
 379  del archivo de datos, espacio libre total, cantidad de registros, cantidad
 380  de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
 381  libres, etc.
 382 \layout Standard
 383
 384
 385 \emph on
 386 ver: EMUFS_Estadisticas emufs_tipo3_leer_estadisticas(EMUFS *emu)
 387 \layout Subsubsection
 388
 389 Compactar el Archivo
 390 \layout Standard
 391
 392 Esta función intenta reorganizar el archivo de manera que el espacio libre
 393  sea lo menor posible, recordando siempre que un registro no puede ser almacenad
 394 o en mas de un bloque excepto que el tamaño del registro sea mayor que el
 395  del bloque.
 396 \layout Standard
 397
 398 Para realizar esto, se aprovecha la funcionalidad de
 399 \emph on
 400 emufs_tipo3_grabar_registro()
 401 \emph default
 402 ya que esta tiene la capacidad de determinar una posición mas eficiente
 403  en el archivo para un registro.
 404  Por esto lo que se hace es levantar uno por uno los registros y volverlos
 405  a grabar, de ese modo todos los
 406 \emph on
 407 gaps
 408 \emph default
 409 que pudieron haberse formado por la eliminación de registros serán cubiertos
 410  por otros.
 411 \layout Standard
 412
 413 Al finalizar este proceso se verifica si existen bloques vacios para truncar
 414  el archivo.
 415  Lo mismo se debe hacer con el archivo de espacios libres .
 416 \emph on
 417 fsc
 418 \emph default
 419 el cual disminuye su tamaño también.
 420 \layout Standard
 421
 422
 423 \emph on
 424 ver: void emufs_tipo3_compactar(EMUFS *emu)
 425 \layout Section
 426
 427 Consideraciones y Políticas de Diseño
 428 \layout Comment
 429
 430 Esto para mi va en organización física.
 431 \layout Standard
 432
 433 Se han tomado ciertas consideraciones para algunos casos particulares que
 434  se pueden presentar durante el uso/ejecución de la aplicación.
 435 \layout Enumerate
 436
 437 Cada registro tiene un encabezado que indica el
 438 \emph on
 439 id
 440 \emph default
 441 del mismo.
 442 \layout Enumerate
 443
 444 Si el tamaño del registro es mayor que el tamaño del bloque el registro
 445  se particionará en la cantidad de bloques que sea necesario, pero siempre
 446  se guardará desde el comienzo de un bloque, esto quiere decir que nunca
 447  se podrá encontrar un comienzo de registro en algún lugar de un bloque
 448  que no sea el comienzo del mismo.
 449 \layout Enumerate
 450
 451 Si el registro se divide en mas de un bloque, se le coloca el id como encabezado
 452  igualmente, pero en el archivo .
 453 \emph on
 454 idx
 455 \emph default
 456  solo se guarda el primer bloque.
 457  En el
 458 \emph on
 459 .fsc
 460 \emph default
 461  se actualizan todos los bloques con el espacio libre que realmente tienen.
 462 \layout Chapter
 463
 464 Conclusiones
 465 \layout Standard
 466
 467 Las comparaciones, pruebas, etc...
 468 \the_end