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

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

• 1 Пример
  • 1.1 Преимущества
  • 1.2 Недостатки
• 2 Продвинутые техники
• 3 См. Также
• 4 ссылки

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

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

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

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

Недостатки

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

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

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

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