До сих пор мы говорили, что на диске файлы могут располагаться как последовательно, так и непоследовательно, но зачем нужны эти два варианта расположения мы еще не объяснили. Последовательными файлами легко управлять, но если максимальный размер файла заранее не известен, использовать эту технологию нельзя. Если файл начинается с сектора j и продолжается в направлении соседних секторов, он может наткнуться на другой файл в секторе k, тогда ему не хватит места на расширение. Если же файл располагается непоследовательно, то таких проблем не возникает, поскольку следующие блоки можно поместить в другое место на диске. Если диск содержит ряд «рабочих» файлов, конечные размеры которых могут меняться, записать их на диск в последовательные блоки размещения практически невозможно. Иногда можно переместить существующий файл, но это накладно.
В то же время, если максимальный размер всех файлов известен заранее (например, как бывает при создании компакт-диска), программа может определить последовательности секторов, точно равных по длине каждому файлу. Если файлы размером 1200, 700, 2000 и 900 секторов нужно поместить на компакт-диск, они просто могут начинаться с секторов 0, 1200, 1900 и 3900 соответственно (оглавление здесь не учитывается). Найти любую часть любого файла легко, поскольку известен первый сектор файла.
Чтобы выделить пространство на диске для файла, операционная система должна следить, какие блоки доступны, а какие уже заняты другими файлами. При записи на компакт-диск вычисление производится один раз и навсегда, а на жестком диске файлы постоянно записываются и удаляются. Один из способов отслеживать состояние диска — хранить список всех пустот (неиспользованных фрагментов), где пустой фрагмент может быть размером с любое число последовательных блоков размещения. Этот список называется списком свободной памяти (free list). На рис. 6.19, а изображен список свободной памяти для диска с рис. 6.18, б.
Рис. 6.19. Два подхода к трассировке свободных секторов: список свободной памяти (а);
битовая карта (б)
Альтернативный подход — хранить битовую карту диска (один бит на один блок размещения), как показано на рис. 6.19, б. Единичный бит показывает, что блок уже занят, а нулевой — что свободен.
Первый подход позволяет легко найти неиспользуемый фрагмент определенной длины. Однако у этого метода есть недостаток: по мере создания и уничтожения файлов размер списка будет меняться, а это нежелательно. Преимущество битовой карты состоит в том, что ее размер постоянен. Кроме того, для изменения статуса блока размещения (из свободного на занятый или наоборот) достаточно поменять значение всего одного бита. Однако при таком подходе трудно найти блок заданного размера. Оба метода требуют, чтобы при записи файла на диск или удаления файла с диска список размещения или карта обновлялись.
Перед тем как закончить обсуждение вопроса о реализации файловой системы, нужно сказать несколько слов о размере блока размещения. Здесь играют роль несколько факторов. Во-первых, тормозят доступ к диску время поиска и время, затрачиваемое на вращение диска. Если на нахождение начала блока тратится 10 мс, то гораздо выгоднее считать 8 Кбайт (это займет примерно 1 мс), чем 1 Кбайт (это займет примерно 0,125 мс), так как, если считывать 8 Кбайт как 8 блоков по 1 Кбайт, потребуется выполнять поиск 8 раз. Для повышения производительности нужны большие блоки размещения.