Los mapas de bits de espacio libre son un método utilizado para rastrear sectores asignados por algunos sistemas de archivos . Si bien el diseño más simplista es muy ineficiente, algunos sistemas de archivos modernos utilizan implementaciones avanzadas o híbridas de mapas de bits de espacio libre [ ¿cuáles? ] .
La forma más simple de mapa de bits en 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 indica un sector en uso. Cada sector tendría un tamaño fijo. Para propósitos explicativos, usaremos un disco duro de 4 GiB 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 128 KiB . 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 que quepa el archivo. Si se almacenara un archivo de 12 KiB 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 posteriormente el archivo se truncara a 8 KiB, el bit del sector final volvería a cero, lo que indica que está nuevamente disponible para su uso.
A medida que crece el tamaño de la unidad, la cantidad de tiempo necesaria para buscar espacio libre puede resultar excesiva. 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 muchos fragmentos. Luego, una matriz separada almacena la cantidad de sectores libres en cada fragmento, de modo que los fragmentos con espacio insuficiente se puedan omitir fácilmente y la cantidad total de espacio libre sea más fácil de calcular. Encontrar espacio libre ahora implica buscar primero en la matriz de resumen y luego buscar en el fragmento de mapa de bits asociado los sectores exactos disponibles. [1]
Este enfoque reduce drásticamente el coste de encontrar espacio libre, pero no ayuda en el proceso de liberación de 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, disminuya el contador de resumen. y volteamos 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 rápidamente el espacio libre sin leer del disco.