Управление свободным и занятым дисковым пространством.

В современных ОС используется несколько способов учета используемого места на диске. Рассмотрим наиболее распространенные.

Учет при помощи организации битового вектора.

Часто список свободных блоков диска реализован в виде битового вектора (bit map или bit vector). Каждый блок представлен одним битом, принимающим значение 0 или 1, в зависимости от того занят он или свободен. Например, 00111100111100011000001 ....

Главное преимущество этого подхода - он относительно прост и эффективен при нахождении первого свободного блока, или n последовательных блоков на диске. Многие компьютеры имеют инструкции манипулирования битами, которые могут быть использованы для этой цели. Например, компьютеры семейств Intel и Motorola имеют инструкции, которые при помощи которых можно легко локализовать первый единичный бита в слове.

Описываемый метод учета свободных блоков используется в Apple Macintosh.

К сожалению, этот метод эффективен, только если битовый вектор помещается в памяти целиком, что возможно только для относительно небольших дисков. Например, диск размером 1.3 Гб с блоками по 512 байт нуждается в таблице размером 332К для управления свободными блоками.

Учет при помощи организации связного списка.

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

Эта схема не всегда эффективна. Для трассирования списка нужно сделать много обращений к диску. Однако к счастью нам необходим, как правило, только первый свободный блок.

Иногда прибегают к модификации подхода связного списка, организуя хранение адресов n свободных блоков в первом свободном блоке. Первые n-1 этих блоков действительно используются. Последний блок содержит адреса других n блоков. И т.д.