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

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

Пример

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

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

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

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

Недостатки

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

Передовые методы

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

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

См. также

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

Ссылки

^ Jump up to: ^а ^б ^с Бонвик, Джефф (14 сентября 2007 г.). «Космические карты» . Архивировано из оригинала 1 апреля 2009 года . Проверено 2 октября 2009 г.

[bonwick-1] Jump up to: ^а ^б ^с Бонвик, Джефф (14 сентября 2007 г.). «Космические карты» . Архивировано из оригинала 1 апреля 2009 года . Проверено 2 октября 2009 г.

[ 1 ]