способен диск. Таким образом, непрерывные файлы легко реализуются и обладают высокой производительностью.

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

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

Списки

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

Файл А

Физический 4 блок

Файл В

Физический блок

Рис. 5.6. Размещение файла в виде связного списка блоков диска

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

С другой стороны, хотя последовательный доступ к такому файлу несложен, произвольный доступ будет довольно медленным. Чтобы получить доступ к бло-

ку п, операционная система должна сначала прочитать первые п-1 блоков по очереди. Очевидно, такая схема оказывается очень медленной.

Список с индексацией

Оба недостатка предыдущей схемы организации файлов в виде списков могут быть устранены, если указатели на следующие блоки хранить не прямо в блоках, а в отдельной таблице, загружаемой в память. На рис. 5.7 показан внешний вид такой таблицы для файлов с рис. 5.6. На обоих рисунках показаны два файла. Файл А занимает блоки диска 4, 7, 2, 10 и 12, а файл В - блоки 6, 3, 11 и 14. С помощью таблицы мы можем начать с блока 4 и следовать по цепочке до конца файла. Те же действия применимы для второго файла, если начать с блока 6. Обе цепочки завершаются специальным маркером (например, 1), не являющимся допустимым номером блока. Такая таблица, загружаемая в оперативную память, называется FAT (File Allocation Table - таблица размещения файлов).

Физический блок

<- Файл А начинается здесь

- Файл В начинается здесь

4- Неиспользуемый блок

Рис. 5.7. Таблица размещения файлов

При такой организации все блоки доступны для данных. Кроме того, значительно упрощается произвольный доступ. Хотя для обращения к какому-либо блоку файла все равно понадобится проследовать по цепочке по всем ссылкам вплоть до требуемого блока, в данном случае вся цепочка ссылок уже хранится в памяти и ее прохождение не требует дополнительных дисковых операций. Как и в предыдущем случае, в каталоге достаточно хранить один целый индекс (номер начального блока файла) для обеспечения доступа ко всем частям файла.

Основной недостаток этого метода состоит в том, что вся таблица должна постоянно находиться в памяти. Для 500-мегабайтового диска с блоками размером 1 Кбайт потребовалась бы таблица из 500 ООО записей, по одной для каждого из 500 ООО блоков диска. Каждая запись должна состоять как минимум из трех байтов. Для ускорения поиска размер записей должен быть увеличен до 4 байт. Таким образом, резидентная таблица будет занимать 1,5 или 2 Мбайт оперативной памяти. Таблица, конечно, может быть размещена в виртуальной памяти, но и в этом случае ее размер оказывается чрезмерно большим, к тому же постоянная выгрузка таблицы на диск и загрузка ее с диска существенно снизят производительность файловых операций.

1-узлы

Последний метод отслеживания принадлежности блоков диска файлам заключается в связывании с каждым файлом структуры данных, называемой i-узлом (index node - индекс-узел), содержащей атрибуты файла и адреса блоков файла. Простой пример f-узла показан на рис. 5.8. При наличии г-узла можно найти все блоки файла. Большое преимущество такой схемы перед хранящейся в памяти таблицей из списков состоит в том, что каждый конкретный г-узел должен находиться в памяти только тогда, когда соответствующий ему файл открыт. Если каждый г-узел занимает п байтов, а одновременно открыть можно k файлов, для массива г-узлов потребуется в памяти всего kn байтов.

1-узел

Однократный косвенный блок

Адреса блоков данных

Рис. 5.8. Пример i-узла