Métodos de asignación de bloques a archivos

De Departamento de Informatica
Saltar a: navegación, buscar


Contenido

Introducción

Hay distintas maneras de asignar espacio en el disco a nuestros archivos y/o directorios. La idea principal de estos métodos es optimizar el uso de los recursos de almacenamiento y garantizar un rápido acceso a los archivos y datos(algunas con mejor o menor éxito que otras).

Estos métodos se agrupan en 3 categorías:

  • Asignación continua.
  • Asignación enlazada.
  • Asignación Indizada.

Adicionalmente los sistemas de archivos no solo deben guardar los datos reales en el disco, si no que ademas datos asociados a los archivos conocidos como metadatos, que permiten llevar registros de: espacio vacio en discos, nombres de archivos,fechas asociadas a los archivos (creacion, modificacion etc), ubicacion de archivos en disco, entre otras cosas.

Los metadatos pueden almacenarce de distintas formas por ejemplo: Inodos, tablas de asignacion, "chunks", etc. [1]

Conceptos

Disposición en disco

ej. particiones

Información de arranque

(directorio): serie secuencial de bloques que se cargan como una imagen binaria en la memoria.

Cargador de arranque

(en espacio de arranque): necesario si tenemos más de un Sistema Operativo

Partición Raíz

contiene el kernel del Sistema Operativo y se carga en el arranque

Sistema de Archivos

puede ser una estructura de datos o una colección de archivos. Existe el sistema física y sistema lógico de archivos. El lógico contiene los metadatos (como el directorio de cada sistema) y la especificación del tipo de sistema (en niveles, grafo, etc), commandos: create, delete, open, close, read, write, append, seek, etc . El sistema físico corresponde a dónde está, valga la redundancia, físicamente almacenado este sistema. Es necesario montar un sistema de archivos, lo cual se hace a través de una tabla de montaje para luego montarlo en disco. Para tener varios sistemas de archivos coexistiendo es necesario un diseño orientado a objetos.

Metadatos

Los metadatos son usados para describir datos digitales, usando estándares de metadatos, describiendo los contenidos y contexto de los archivos. En si es "informacion acerca de contenedores de información".

Los sistemas de archivos almacenan metadatos como el tiempo de creación de archivo, la hora del último acceso, el tiempo del archivo metadatos que han cambiado, o el momento en que el archivo última copia de seguridad, la longitud de los datos contenidos en un archivo puede es almacenado según el número de bloques asignados para el archivo, la fecha última modificación del archivo (como Timestamp). Entre otras informaciones puede incluir el tipo de archivo ya sea bloque, carácter, socket, subdirectorio, etc., hasta su configuración de permisos de acceso ya sea si el archivo es de sólo lectura, ejecutable .

Según el sistema de archivos se pueden guardar metadatos adicionales, como NTFS, XFS, ext2/ext3. Otros sistemas de archivos pueden asignar atributos definidos por el usuario, como el autor, codificación de caracteres, el tamaño de una imagen.

Niveles del Sistema de Archivos

  • Nivel 1: Interfaz-->llamadas a sistema y descriptores de archivo
  • Nivel2: VFS: sistema de archivos virtual. Permite que haya varios sistemas de archivos, por lo tanto separa las funciones básicas de un sistema de archivos de la implementación particular de cada uno. También designa inequívocamente a cada archivo mediante la estructura de vnodo.

Directorios

Dependiendo de su implementación es cómo se almacenan en la memoria. Debido a que en algunos sistemas (como UNIX) los directorios son tratados como un archivo más, sería adecuado referirse a ellos también.

Listas

Forma más simple para implementar directorios. Se tiene una lista lineal con los nombres de los archivos con punteros a los bloques de datos. Aún asi para ejecutar una búsqueda lineal puede provocar un gran consumo de tiempo.

Ventaja
  • Fácil de programar
  • Si la lista está ordenda se puede listar el directorio sin necesidad de un nuevo paso para ello.
Desventajas
  • Altos tiempos de ejecución
  • Búsquedas lineales (costo n)
  • Agregar un directorio: se debe recorrer toda la lista para asegurarse de que no haya archivos con el mismo nombre
  • Eliminación: engorrosa
  • Para reutilizar espacio, luego de un borrado, hay distintas opciones:
    • marcar la entrada como vacía (de manera lógica)
    • tener una lista aparte de espacios disponibles en la lista
    • correr el último elemento de la lista al espacio desocupado para reducir el largo.
Solución

Como solución se plantea mantener la lista siempre ordenada, pero esto complica los procesos de inserción y borrado. También algunos sistemas operativos implementan una "caché de software" con información acerca del último archivo utilizado, de esa manera no hay que volver a buscarlo linealmente en la lista.

Hashing

El sistema de Hashing, a partir de una función, entrega distitnas claves a cada archivo. Estas claves van a una "tabla de hash". Desde esta tabla se obtienen punteros a listas lineales de archivos. Combinando hashing con listas lineales se reduce considereablemente el tiempo de búsqueda.

Desventajas
  • La función de hash podría proporcionar a distintos archivos una misma clave.
  • Dependiende del algoritmo es el tiempo de procesamiento que tardará en generar claves.
  • Las tablas de hash tienen un tamaño fijo, las claves que se obtienen de las funciones estan comprendidas en el rango que abarca la tabla. Si se expande esta tabla, la función de hash será distinta ya que tiene que considerar más entradas en la tabla. Al usar la nueva función, pueden generarse llaves que sobreescriban las anteriores.
Solución

Para solucionar esto, en vez de agrandar la tabla se puede tener una "lista de desborde", donde se van insertando las nuevas claves. Así provocará menos colisiones, pero se sigue dificultando aún más la navegación por las listas.

Métodos de Asignación de Archivos

Existen tres grandes metodos para almacenar archivos en discos, Asignación Enlazada, Asignación Contigua y Asignación Indexada

Asignación Contigua

Como el nombre lo dice, los bloques que pertenecen a un mismo archivo se ubican de manera contigua. lo que es particularmente útil en el caso de los discos mecánicos ya que no es necesario realizar grandes movimientos en el cabezal para leer el archivo. También reduce las búsquedas en el disco, ya que se sabe que están en cierto espacio contiguo y no es necesario explorar todo para llegar a la información deseada. Cada directorio contiene, para cada archivo, la dirección del bloque en que comienza y la longitud del área asignada a este archivo. [2]

Acceso

La asignación contigua puede tener acceso directo como secuencial.

Directo : Conociendo el bloque inicial y la posición relativa del bloque buscado, simplemente se suma la cantidad de bloques para obtener la ubicación del bloque deseado. Secuencial : Lectura bloque a bloque en orden, partiendo desde el inicial, y finalizando ya sea en el bloque final o en uno intermedio deseado. [2]

Ventajas

  • Fácil implementación, pues solo es necesario el bloque inicial y la cantidad de bloques para llevar el registro de un archivo.
  • Una vez almacenado es muy fácil acceder al archivo
  • Excelente desempeño de lectura, pues el archivo entero puede ser leído en una única operación, solo se necesita una buqueda para encontrar el archivo, luego de esto no hay mas búsquedas u otros retrasos rotacionales, por lo que los datos pueden ser transmitido al máximo ancho de banda del dispositivo.

[2]

Desventajas

Fragmentación de disco

El disco se fragmenta con el tiempo (presencia de archivos y huecos), cuando el disco no esta muy lleno no es un gran problema, pues cada archivo nuevo puede ser escrito al final del disco. Pero con el disco mas lleno se debe compactar el disco (desfragmentar) o reutilizar el espacio de los huecos. Para esto ultimo, se requiere llevar una lista de huecos; para almacenar un archivo de esta manera, se deberá encontrar una porción contigua del disco que tenga, como mínimo, el tamaño completo del archivo. Esto resulta complicado, se reconoce un problema de fragmentación externa.

En tiempos pasados, para solucionar la fragmentación externa, el usuario manualmente copiaba los contenidos del disco a otro (generalmente un diskette) y luego lo volvía a copiar en disco.

Como se debe disponer de un bloque de cierto tamaño para un archivo completo hay que estimar cuál es el tamaño total del archivo a guardar. Si el archivo existe, no es complicado conocer su tamaño, pero, si se quiere asignar espacio para un archivo nuevo, es bastante más difícil llegar de aproximar. Lo mismo si sabemos que un archivo crecerá en el tiempo, debemos asignarle más espacio que el necesario inicialmente, pero esto dejará huecos sin usar durante , quizá largos, periodos de tiempo(eso es lo que se conoce como fragmentación interna). [2]

Soluciones

  • Extensión: bloque contiguo extra asignado al archivo
  • Desfragmentación: Proceso que re-acomoda todos los bloques de manera que los archivos queden en áreas contiguas (entre bloques y entre archivos). Esto elimina los espacios entre archivos
  • Registro de lista de bloques vacíos (huecos): lleva una lista o registro de los espacios vacíos disponibles en el disco, para que en ellos puedan ser acomodados nuevos archivos.

[2]

Asignación Enlazada

Lista de bloques enlazados.
Tabla FAT

Cada archivo es una lista ligada de bloques de disco, en cada bloque existe un puntero que direciona hacia el bloque siguiente, el resto del bloque es usado para almacenar datos, de esta forma, todos los bloques del disco pueden ser usados. [3] [4]

Ventaja

  • Al ser una lista enlazada,sólo se necesita la dirección del bloque inicial, los demás bloques pueden ser encontrados a partir del primero.
  • No desperdicia espacio, pues no requiere dejar espacios vacíos para ubicación, re-ubicación o el crecimiento de archivos, lo que conlleva a un buen manejo del espacio libre.
  • No Produce Fragmentación externa.[5]

[4]

Desventaja

  • Solo es eficiente para archivos de acceso secuencial, el acceso a archivo de forma aleatoria o directa es bastante lenta, pues para leer el bloque n, se deben leer n-1 bloques antes de poder acceder al bloque deseado, lo que conlleva muchas lecturas y por consiguiente mucho tiempo.
  • Si se pierde un puntero al siguiente bloque, se pierde acceso al resto del archivo.
  • Perdida de espacio en los bloques, debido a los punteros.
  • Perdida de eficiencia, en la lectura datos en múltiplos del tamaño del bloque, pues la cantidad de datos guardados ya no sera una potencia de 2 debido a los punteros, por ende la cantidad de datos que caben en un bloque completo se deben distribir entre 2, lo que requiere una posterior concatenación generando un overhead debido a la copia necesaria en la operación.

[4]

Solución

  • En los casos de perdida de algún puntero al bloque siguiente, es útil implementar los bloques como listas doblemente enlazadas, para saber en donde se encuentran los bloques faltantes que no se pueden encontrar.

[4]

Asignación Enlazada usando una tabla en memoria

Los problemas de este método, pueden mejorarse, sacando los punteros de los bloques de disco y poniéndolos en una tabla ubicada en memoria. Aquí es donde nacen los sistemas "FAT" o por sus siglas en ingles "File Allocation Table" (Tabla de Asignación de Archivos), usados en sistemas MS/DOS, OS2, windows 9x entre otras implementaciones en sistemas mas actuales.

Con esta organización, los bloques están disponibles para datos por completo, el acceso aleatorio es mas fácil y rápido, pues si bien la lista aun debe ser seguida para llegar al bloque, eso se hace en memoria y por ende no requiere lecturas adicionales de disco. Aun es posible encontrar un archivo completo solo con la dirección del bloque inicial.

Su principal desventaja que la tabla debe estar en memoria todo el tiempo, por consiguiente con una cantidad grande de bloques, se requiere una tabla proporcionalmente grande también, por lo que el uso de memoria es considerable. Por ejemplo: con un disco de 20-GB, bloques de 1-KB, la tabla necesita 20 millones de entradas; considerando cada una de estas entre 3 a 4 bytes, la tabla en memoria puede ocupar entre 60 a 80 MB todo el tiempo. Se podría poner la tabla en memoria paginada, pero significaría lidiar con los problemas de la memoria virtual ademas de generar trafico de paginación. [4]

Asignación Indexada

Un i-node con tres niveles de indirección

También conocido como asignación por "I-Nodes" (nodos indexados), este método lleva el rastro de que bloque pertenece a cada archivo, asignando un I-node con todos los punteros hacia los demás bloques en el orden correspondiente, para cada archivo existe un I-node. El I-node lista los atributos y las direcciones de bloques del archivo asociado, por lo que dado su I-nodo, es posible encontrar todos los bloques de un Archivo. Existe perdida de espacio ya que cada archivo necesitar un I-nodo independiente de cuantos datos contenga el bloque. El rendimiento depende del archivo si se accede de manera secuencial o aleatoria, o si el archivo es muy grande o muy pequeño. [6]

Ventajas

  • No requiere una gran tabla en memoria como en FAT: Simplemente se carga el I-nodo de el/los archivo(s) abierto(s) en cada momento.

Si el nodo ocupa n bytes y se puede abrir k archivos a la vez en el sistema, solo se requieren nk bytes en memoria. Para que nk fuese de una magnitud similar a FAT deberían abrirse todos los archivos del disco duro a la vez. Por lo que en definitiva el uso de memoria no depende del tamaño de disco, si no de la cantidad de archivos en uso.

  • Permite el acceso especifico del archivo.
  • Acceso Aleatorio.
  • No produce fragmentación Externa.

[6]

Desventajas

  • Permite fragmentación externa, pero causa sobrecarga en el I-nodo.
  • Desperdicio de espacio para archivos muy pequeños.
  • Tamaño de archivo limitado debido al tamaño prefijado del I-nodo, para solventar esto se usa la indirección.

[6]

Solución

  • Una solución para sobre pasar las limitaciones de tamaños de archivos es usar un nivel de direccionamiento, reservando la ultima dirección del i-nodo no para datos, si no que para la dirección de un bloque de indirección que contiene mas direcciones de bloques de datos. Esta idea, se puede extender a doble o tripe indirección.

[6]

Manejo de Espacio Libre

Vector de Bits

Cada bit representa un bloque de disco, 0 si esta libre, 1 si está asignado. Existen algoritmos que encuentran facilmente bloques contiguos según su tamaño. Se crea un bitmap que requiere un espacio extra aunque muy pequeño.

Bites =\frac{Espacio\ disco}{Tama\tilde{n}o\ block}

Lista Enlazada

Cada bloque libre contiene un puntero a el siguiente bloque libre, no necesita espacio para el Vector de Bits pero si para punteros, es por eso que es mas dificil obtener espacio contiguo facilmente, aún asi generalmente no es operación muy utilizada, ademas de que los SO agrregar y eliminan bloques del principio de la lista.[7]

Agrupación

Una variación de lista Enlazada libre es una lista unida con las direcciones de bloques de indices, y en estos bloques indices las direcciones de los bloques libres. Si un bloque tiene N direcciones, entonces el primer bloque en la Lista Enlazada contiene hasta N-1 direcciones de bloques libres y un puntero a el siguiente bloque de direcciones libres

Contador

Cuando existe un conjunto de bloques contiguos que estén libres, se tiene por un puntero a el bloque y el tamaño del grupo de sectores vacios, si el promedio el número de bloques libre contiguos es mayor que 2 este metodo ofrece ahorrar espacio necesitado para la lista de bloques lbres (Tecnica similar usada en imagenes para ciertos grupos de pixeles contiguos del mismo color).

Referencias

[8][9][10][11][12][13][14]

  1. http://en.wikibooks.org/wiki/Operating_System_Design/File_Systems/Allocation
  2. 2,0 2,1 2,2 2,3 2,4 Tanenbaum, Andrew S. Operating Systems: Desing and Implementation/ Andrew S. Tanenbaum, Albert S. Woodhull. --3rd ed. Page 499
  3. http://so.fciencias.unam.mx/presentaciones/ch11.pdf
  4. 4,0 4,1 4,2 4,3 4,4 Tanenbaum, Andrew S. Operating Systems: Desing and Implementation/ Andrew S. Tanenbaum, Albert S. Woodhull. --3rd ed. Page 500
  5. http://www.gayatlacomulco.com/tutorials/sistemasoperativos2/unidad4.htm#ASIGNACI%C3%93N%20LIGADA
  6. 6,0 6,1 6,2 6,3 Tanenbaum, Andrew S. Operating Systems: Desing and Implementation/ Andrew S. Tanenbaum, Albert S. Woodhull. --3rd ed. Page 501
  7. http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/11_FileSystemImplementation.html
  8. https://sites.google.com/site/osupaep2010/sistemas-de-archivos/almacenamiento-fisico-de-datos/asignacion-del-espacio-de-almacenamiento/asignacion-encadenada
  9. http://www.cs.bgu.ac.il/~arik/usail/concepts/filesystems/def-of-filesys.html
  10. http://www2.cs.uregina.ca/~hamilton/courses/330/notes/filesys/filesys.html
  11. Computer Science 331 Hash Functions Mike Jacobson Department of Computer Science University of Calgary Lecture #20 descargado de: http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&ved=0CIMBEBYwCQ&url=http%3A%2F%2Fpages.cpsc.ucalgary.ca%2F~jacobs%2FCourses%2Fcpsc331%2FF08%2Fnotes%2Flecture20.pdf&ei=pw2jUImyAqnm0gHC0YGQBg&usg=AFQjCNE3pcc--B9Ly4FZz1q0i33M2_aXNQ&cad=rja)
  12. http://www.itver.edu.mx/so1/sistemas_operativos.htm
  13. http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO2.htm
  14. http://informatica-sinlimites.blogspot.com/2010/08/que-es-la-desfragmentacion-del-disco.html
Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas