Обычно эта величина значительно меньше, чем размер FAT, описанной в предыдущем разделе. Это легко объясняется. Размер таблицы, хранящей список всех блоков диска, пропорционален емкости самого диска. Для диска из п блоков потребуется п записей в таблице. Таким образом, размер таблицы линейно растет с ростом размера диска. Для схемы г-узлов, напротив, требуется массив в памяти с длиной, пропорциональной максимальному количеству файлов, которые можно открыть одновременно. При этом не важно, будет ли размер диска 1 Гбайт, 10 Гбайт или 100 Гбайт.

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

5.3.2. Реализация каталогов

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

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

Каталоги в СР/М

Мы начнем изучение каталогов с самого простого примера - файловой системы СР/М, проиллюстрированной на рис. 5.9. В этой системе только один каталог, поэтому файловой системе, чтобы найти файл, нужно просмотреть только этот единственный каталог. Обнаружив запись, файловая система получает информацию и о номерах блоков на диске, а также атрибуты файла, поскольку все это хранится в каталоге. Если файлу требуется больше дисковых блоков, чем помещается в одной записи, для него выделяются дополнительные.

Рассмотрим назначение полей на рис. 5.9. Поле Код пользователя помогает определить, какому пользователю принадлежит файл. При поиске файла проверяются только те записи, которые принадлежат текущему пользователю. Следующие два поля задают имя/расширение файла. Поле Экстент необходимо потому.

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

Байты 1

3 1 2 <-

-16-

Имя файла

Код пользователя

Экстент

Номер дисковых блоков

Тип файла Счетчик блоков (расширение)

Рис. 5.9. Запись файла в каталоге содержит все номера его блоков

Каталоги в MS-DOS

Теперь давайте рассмотрим системы с иерархической структурой каталогов. На рис. 5.10 показана структура записи каталога в MS-DOS. Запись имеет размер 32 байта и содержит имя файла, его атрибуты и номер его первого блока. Этот номер используется как индекс в таблице на рис. 5.7. Остальные блоки можно найти, следуя по цепочке.

Байты

Расширение Атрибуты

Зарезервировано

Рис. 5.10. Структура каталога в MS-DOS

Время Дата Номер

первого блока

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

Каталоги в UNIX

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

Байты 2

Имя файла

Номер i-узла

Рис. 5.11. Запись каталога в UNIX

Когда открывается файл, файловая система должна найти на диске указанное ей имя файла. Рассмотрим, как будет происходить поиск файла /usr/ast/mbox. В качестве примера мы взяли UNIX, но все сказанное относится и к другим иерархическим системам.

Сначала файловая система обнаруживает корневой каталог. В UNIX его г-узел расположен в фиксированном месте на диске. Затем она выделяет первый компонент пути, usr, и ищет в корневом каталоге номер г-узла для файла /usr. Обнаружить г-узел по его номеру несложно, так как расположение узлов фиксировано. Далее система продолжает поиск с этого г-узла и находит следующий компонент, ast. Обнаружив его, система получает номер г-узла для каталога /usr/ast. Наконец, в этом каталоге ищется сам файл mbox. Затем г -узел файла считывается в память и остается там до тех пор, пока файл не будет закрыт. Процесс поиска файла проиллюстрирован на рис. 5.12.

1-узвл 6 содержит данные

Корневой каталог о каталоге /usr

Режимный код Размер Времена

Блок 132 содержит каталог 132

1-узеп 26 содержит данные о каталоге /usr/ast

В резупьтате

поиска эпемента usr попучаем i-узеп 6

Режимный код Размер Времена

В 1-узле 6 Запись /usr/ast В i-узпе 26 указывается, ссылается указывается, что /usr находится на 1-узел 26 что /usr/ast вбпоке132 находится

в бпоке 406

Рис. 5.12. Шаги поиска файла /usr/ast/mbox

Блок 406 содержит каталог /usr/ast

Запись /usr/ast/mbox ссыпается на i-узел 60

Относительные пути обрабатываются точно так же, как и абсолютные, за исключением того, что поиск начинается не с корневого каталога, а с текущего.