Растровое изображение свободного места - Free space bitmap

Растровые изображения в свободном пространстве являются одним из методов отслеживания выделенных сектора некоторыми файловые системы. Хотя самый упрощенный дизайн крайне неэффективен, некоторые современные файловые системы используют расширенные или гибридные реализации растровых изображений свободного пространства.

Пример

Простейшая форма растрового изображения свободного пространства - это битовый массив, т.е. блок биты. В этом примере ноль указывает на свободный сектор, а единица указывает на используемый сектор. Каждый сектор будет иметь фиксированный размер. Для пояснения мы будем использовать 4ГиБ жесткий диск с 4096 байт секторов, и предположим, что сама битовая карта хранится в другом месте. Для примера диска потребуется 1 048 576 бит, по одному на каждый сектор, или 1МиБ. Увеличение размера диска пропорционально увеличит размер битовой карты, в то время как умножение размера сектора приведет к пропорциональному уменьшению.

Когда Операционная система (ОС) необходимо записать файл, он будет сканировать растровое изображение, пока не найдет достаточно свободных мест для размещения файла. Если бы файл размером 12 КиБ был сохранен на примере диска, были бы найдены три нулевых бита, заменены на единицы, и данные будут записаны в трех секторах, представленных этими битами. Если бы файл был впоследствии усечен до 8 КиБ, бит последнего сектора был бы установлен обратно в ноль, указывая, что он снова доступен для использования.

Преимущества

Просто: каждый бит напрямую соответствует сектору
Быстрая проверка распределения произвольного доступа: проверка того, свободен ли сектор, так же просто, как проверка соответствующего бита
Быстрое удаление: данные не нужно перезаписывать при удалении;^{[требуется разъяснение ]} перевернуть соответствующий бит достаточно
Фиксированная стоимость: как преимущество, так и недостаток. Другие методы хранения информации о свободном пространстве имеют переменную величину накладных расходов в зависимости от количества и размера экстентов свободного пространства. Растровые изображения никогда не могут работать так же хорошо, как другие методы в соответствующих идеальных условиях, но и не страдают патологическими случаями. Поскольку растровое изображение никогда не растет, не сжимается и не перемещается, требуется меньше операций поиска, чтобы найти нужную информацию.
Низкие накладные расходы на хранилище в процентах от размера диска: даже при относительно небольших размерах секторов пространство для хранения, необходимое для растрового изображения, невелико. А 2TiB привод может быть полностью представлен всего лишь 64МиБ битовая карта.

Недостатки

Расточительство на больших дисках: упрощенный дизайн начинает тратить большое количество места (в абсолютном смысле) для чрезвычайно больших объемов^[1]
Плохая масштабируемость: хотя размер остается незначительным в процентах от размера диска, поиск свободного места становится медленнее по мере заполнения диска. Если растровое изображение больше доступного объем памяти, производительность резко падает на всех операциях^[1]
Фрагментация: Если свободные сектора берутся по мере их обнаружения, диски с частым созданием и удалением файлов быстро становятся фрагментированными. Если поиск пытается найти смежные блоки, поиск свободного места становится намного медленнее даже для умеренно заполненных дисков.

Продвинутые техники

По мере увеличения размера диска время, необходимое для поиска свободного места, может стать неоправданным. Чтобы решить эту проблему, реальные реализации растровых изображений свободного пространства найдут способы централизовать информацию о свободном пространстве. Один из подходов - разбить растровое изображение на несколько частей. Затем в отдельном массиве хранится количество свободных секторов в каждом фрагменте, поэтому фрагменты с недостаточным пространством можно легко пропустить, а общий объем свободного пространства легче вычислить. Теперь поиск свободного места влечет за собой поиск в сводном массиве, а затем поиск в соответствующем фрагменте растрового изображения точных доступных секторов.^[1]

Такой подход резко снижает затраты на поиск свободного места, но не помогает в процессе его освобождения. Если объединенный размер сводного массива и растрового изображения больше, чем может быть легко сохранен в памяти, и большое количество файлов с разбросанными секторами освобождается, требуется огромный доступ к диску, чтобы найти все сектора, уменьшить суммарный счетчик и переверните биты обратно в ноль. Это значительно снижает преимущества растрового изображения, поскольку оно больше не выполняет свою функцию быстрого суммирования свободного пространства без чтения с диска.

Смотрите также

Карта доступности блока
Файловая система с высокой производительностью (HPFS)
exFAT
Индекс растрового изображения - Средство индексирования баз данных, которое часто пересекается с эффективными дизайнами растровых изображений свободного пространства
B-дерево - Альтернативный способ отслеживания свободного пространства путем сохранения отсортированного набора экстентов свободного пространства.