Los mapas de bits de espacio libre son un método utilizado para rastrear los sectores asignados por algunos sistemas de archivos . Si bien el diseño más simplista es altamente ineficiente, algunos sistemas de archivos modernos utilizan implementaciones avanzadas o híbridas de mapas de bits de espacio libre.
Ejemplo
La forma más simple de mapa de bits de espacio libre es una matriz de bits , es decir, un bloque de bits . En este ejemplo, un cero indicaría un sector libre, mientras que un uno indicaría un sector en uso. Cada sector tendría un tamaño fijo. Para fines explicativos, utilizaremos un disco duro de 4 GB con sectores de 4096 bytes y asumiremos que el mapa de bits en sí está almacenado en otro lugar. El disco de ejemplo requeriría 1.048.576 bits, uno para cada sector, o 1 MB . Aumentar el tamaño de la unidad aumentará proporcionalmente el tamaño del mapa de bits, mientras que multiplicar el tamaño del sector producirá una reducción proporcional.
Cuando el sistema operativo (SO) necesita escribir un archivo, escaneará el mapa de bits hasta que encuentre suficientes ubicaciones libres para ajustarse al archivo. Si se almacenara un archivo de 12 KB en la unidad de ejemplo, se encontrarían tres bits cero, se cambiarían a unos y los datos se escribirían en los tres sectores representados por esos bits. Si el archivo se trunca posteriormente a 8 KB, el bit del sector final se volvería a poner a cero, lo que indica que está nuevamente disponible para su uso.
Ventajas
- Simple: cada bit corresponde directamente a un sector
- Verificación rápida de asignación de acceso aleatorio: verificar si un sector está libre es tan simple como verificar el bit correspondiente
- Eliminación rápida: no es necesario sobrescribir los datos al eliminarlos; [ aclaración necesaria ] voltear el bit correspondiente es suficiente
- Costo fijo: tanto una ventaja como una desventaja. Otras técnicas para almacenar información de espacio libre tienen una cantidad variable de sobrecarga dependiendo del número y tamaño de las extensiones de espacio libre. Los mapas de bits nunca pueden funcionar tan bien como otras técnicas en sus respectivas circunstancias ideales, pero tampoco sufren casos patológicos. Dado que el mapa de bits nunca crece, se reduce ni se mueve, se requieren menos búsquedas para encontrar la información deseada
- Baja sobrecarga de almacenamiento como porcentaje del tamaño de la unidad: incluso con tamaños de sector relativamente pequeños, el espacio de almacenamiento requerido para el mapa de bits es pequeño. Una unidad de 2 TB podría representarse completamente con un simple mapa de bits de 64 MB .
Desventajas
- Desperdicio en discos más grandes: el diseño simplista comienza a desperdiciar grandes cantidades de espacio (en un sentido absoluto) para volúmenes extremadamente grandes [1]
- Escalabilidad deficiente: si bien el tamaño sigue siendo insignificante como porcentaje del tamaño del disco, la búsqueda de espacio libre se vuelve más lenta a medida que el disco se llena. Si el mapa de bits es más grande que la memoria disponible , el rendimiento cae precipitadamente en todas las operaciones [1]
- Fragmentación : si se toman los sectores libres tal como se encuentran, las unidades con creación y eliminación frecuentes de archivos se fragmentarán rápidamente. Si la búsqueda intenta encontrar bloques contiguos, la búsqueda de espacio libre se vuelve mucho más lenta incluso para discos moderadamente llenos. Los datos fragmentados también ralentizan la velocidad de lectura en los discos duros mecánicos debido a la búsqueda de latencia del cabezal magnético, aunque esto no es un problema en la memoria flash .
Técnicas avanzadas
A medida que aumenta el tamaño de la unidad, la cantidad de tiempo necesaria para buscar espacio libre puede resultar irrazonable. Para abordar esto, las implementaciones del mundo real de mapas de bits de espacio libre encontrarán formas de centralizar la información en el espacio libre. Un método consiste en dividir el mapa de bits en varios fragmentos. Luego, una matriz separada almacena la cantidad de sectores libres en cada fragmento, por lo que los fragmentos con espacio insuficiente se pueden omitir fácilmente y la cantidad total de espacio libre es más fácil de calcular. Encontrar espacio libre ahora implica buscar primero la matriz de resumen y luego buscar el fragmento de mapa de bits asociado para los sectores exactos disponibles. [1]
Este enfoque reduce drásticamente el costo de encontrar espacio libre, pero no ayuda con el proceso de liberar espacio. Si el tamaño combinado de la matriz de resumen y el mapa de bits es mayor de lo que se puede almacenar fácilmente en la memoria y se libera una gran cantidad de archivos con sectores dispersos, se necesita una enorme cantidad de acceso al disco para encontrar todos los sectores, disminuir el contador de resumen y voltea los bits a cero. Esto reduce en gran medida los beneficios del mapa de bits, ya que ya no realiza su función de resumir el espacio libre rápidamente sin leer del disco.
Ver también
- Mapa de disponibilidad de bloques
- Sistema de archivos de alto rendimiento (HPFS)
- exFAT
- Índice de mapa de bits : un medio de indexar bases de datos que con frecuencia se superpone con diseños eficientes de mapas de bits de espacio libre.
- Árbol B : un medio alternativo de rastrear el espacio libre almacenando un conjunto ordenado de extensiones de espacio libre
Referencias
- ↑ a b c Bonwick, Jeff (14 de septiembre de 2007). "Mapas espaciales" . Archivado desde el original el 1 de abril de 2009 . Consultado el 2 de octubre de 2009 .