95 - 141

Связанный список. Хранение файла в виде связанного списка дисковых блоков.

Внешняя фрагментация – основная проблема метода выделение непрерывной последовательностью дисковых блоков – может быть устранена за счет представления файла в виде связанного списка блоков диска. Запись в директории содержит указатель на первый и последний блоки файла (иногда в качестве варианта используется специальный знак конца файла – EOF). Каждый блок содержит указатель на следующий блок.

Внешняя фрагментация для данного метода отсутствует. Любой свободный блок может быть использован для удовлетворения запроса. Заметим, что нет необходимости декларировать размер файла в момент создания. Файл может расти неограниченно.

Связанное выделение имеет, однако, несколько существенных недостатков.

Во-первых, при прямом доступе к файлу для поиска i-го блока нужно осуществить несколько обращений к диску, последовательно считывая блоки от 1 до i – 1, т. е. выборка логически смежных записей, которые занимают физически несмежные секторы, может требовать много времени. Здесь мы теряем все преимущества прямого доступа к файлу.

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

Наконец, для указателя на следующий блок внутри блока нужно выделить место, что не всегда удобно. Емкость блока, традиционно являющаяся степенью двойки, таким образом, перестает быть степенью двойки, так как указатель отбирает несколько байтов. Поэтому метод связанного списка обычно в чистом виде не используется.

Таблица отображения файлов (FAT)

Одним из вариантов способа является хранение указателей не в дисковых блоках, а в индексной таблице в памяти, которая называется таблицей размещения файлов (FAT – file allocation table) (Рис 1). Этой схемы придерживаются многие ОС (MS-DOS, OS/2, MS Windows и др.)

Рис 1. Метод связанного списка с использованием таблицы в оперативной памяти

По-прежнему существенно, что запись в директории содержит только ссылку на первый блок. Далее при помощи таблицы FAT можно локализовать блоки файла независимо от его размера. В тех строках таблицы, которые соответствуют последним блокам файлов, обычно записывается некоторое граничное значение, например EOF.

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

Содержание