В современных ОС используется несколько способов учета используемого места на диске. Рассмотрим наиболее распространенные.
Учет при помощи организации битового вектора.
Часто список свободных блоков диска реализован в виде битового вектора (bit map или bit vector). Каждый блок представлен одним битом, принимающим значение 0 или 1, в зависимости от того занят он или свободен. Например, 00111100111100011000001 ....
Главное преимущество этого подхода - он относительно прост и эффективен при нахождении первого свободного блока, или n последовательных блоков на диске. Многие компьютеры имеют инструкции манипулирования битами, которые могут быть использованы для этой цели. Например, компьютеры семейств Intel и Motorola имеют инструкции, которые при помощи которых можно легко локализовать первый единичный бита в слове.
Описываемый метод учета свободных блоков используется в Apple Macintosh.
К сожалению, этот метод эффективен, только если битовый вектор помещается в памяти целиком, что возможно только для относительно небольших дисков. Например, диск размером 1.3 Гб с блоками по 512 байт нуждается в таблице размером 332К для управления свободными блоками.
Учет при помощи организации связного списка.
Другой подход - связать в список все свободные блоки, поддерживая указатель на первый свободный блок в специальном месте диска, попутно кэшируя в памяти эту информацию.
Эта схема не всегда эффективна. Для трассирования списка нужно сделать много обращений к диску. Однако к счастью нам необходим, как правило, только первый свободный блок.
Иногда прибегают к модификации подхода связного списка, организуя хранение адресов n свободных блоков в первом свободном блоке. Первые n-1 этих блоков действительно используются. Последний блок содержит адреса других n блоков. И т.д.