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 simple es muy ineficiente, algunos sistemas de archivos modernos utilizan implementaciones avanzadas o híbridas de mapas de bits de espacio libre.
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 indica un sector en uso. Cada sector sería de tamaño fijo. Para fines explicativos, utilizaremos un disco duro de 4 GB con sectores de 4096 bytes y supondremos 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 que quepa el 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 truncara posteriormente a 8 KB, el bit del sector final se volvería a poner a cero, lo que indicaría que vuelve a estar disponible para su uso.
A medida que crece el tamaño de la unidad, la cantidad de tiempo necesario para buscar espacio libre puede volverse irrazonable. Para abordar esto, las implementaciones del mundo real de mapas de bits de espacio libre encontrarán formas de centralizar la información sobre el espacio libre. Un enfoque consiste en dividir el mapa de bits en muchos 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 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 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 de nuevo 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.