Даже в ранних версиях системы UNIX применялась довольно сложная многопользовательская файловая система, так как в основе этой системы лежала операционная система MULTICS. Далее будет рассмотрена файловая система V7, разработанная для компьютера PDP-11, сделавшего систему UNIX знаменитой.
Файловая система представляет собой дерево, начинающееся в корневом каталоге, с добавлением связей, формирующих направленный ациклический граф. Имена файлов могут содержать до 14 любых символов ASCII, кроме слеша (поскольку он служит разделителем компонентов пути) и символа NUL (поскольку он используется для дополнения имен короче 14 символов). Символ NUL имеет числовое значение 0.
Каталог UNIX содержит по одной записи для каждого файла этого каталога. Каждая запись каталога максимально проста, так как в системе UNIX используется система i-узлов (см. рис. 4.10). Запись каталога, как показано на рис. 4.27, состоит всего из двух полей: имени файла (14 байт) и номера i-узла для этого файла (2 байта). Эти параметры ограничивают количество файлов в файловой системе до 64 К.
Подобно i-узлу на рис. 4.10 i-узлы системы UNIX содержат некоторые атрибуты, которые содержат размер файла, три указателя времени (создания, последнего доступа и последнего изменения), идентификатор владельца, группы, информацию о защите и счетчик указывающих на этот i-узел записей в каталогах. Последнее поле необходимо для установления связей. При добавлении к i-узлу новой связи счетчик в i-узле увеличивается на единицу. При удалении связи счетчик в i-узле уменьшается на единицу. Когда значение счетчика достигает нуля, i-узел освобождается, а дисковые блоки возвращаются в список свободных блоков.
Для учета дисковых блоков файла используется общий принцип, показанный на рис. 4.10, позволяющий работать с очень большими файлами. Первые 10 дисковых адресов хранятся в самом i-узле, поэтому для небольших файлов вся необходимая информация содержится непосредственно в i-узле, считываемом с диска в оперативную память при открытии файла. Для файлов большего размера один из адресов в i-узле представляет собой адрес блока диска, называемого однократным косвенным блоком. Этот блок содержит дополнительные дисковые адреса. Если и этого недостаточно, используется другой адрес в i-узле, называемый двукратным косвенным блоком и содержащий адрес блока, в котором хранятся адреса однократных косвенных блоков. Если и этого мало, используется трехкратный косвенный блок. Полная схема показана на рис. 4.28.
При открытии файла файловая система по предоставленному имени файла должна найти его блоки на диске. Рассмотрим, как происходит поиск по абсолютному имени /usr/ast/mbox. В этом примере будет использоваться файловая система UNIX, хотя для всех иерархических каталоговых систем применяется в основном такой же алгоритм. Сначала файловая система определяет местоположение корневого каталога. В системе UNIX его i-узел размещается в фиксированном месте на диске. По этому i-узлу система определяет местоположение корневого каталога, который может находиться в любом месте диска, в данном примере — в блоке 1.
Затем файловая система считывает корневой каталог и ищет в нем первый компонент пути, usr, чтобы определить номер i-узла файла /usr. Определить местоположение i-узла по его номеру несложно, поскольку у каждого из них есть свое фиксированное место на диске. По этому i-узлу файловая система определяет местоположение каталога для /usr и ищет в нем следующий компонент, ast. Найдя описатель ast, файловая система получает i-узел для каталога /usr/ast. По этому i-узлу она может найти сам каталог и искать в нем файл mbox. При этом i-узел файла mbox считывается в память и остается там, пока файл не будет закрыт. Процесс поиска показан на рис. 4.29.
Поиск по относительным именам путей ведется так же, как и по абсолютным, с той лишь разницей, что алгоритм начинает работу не с корневого, а с рабочего каталога. В каждом каталоге есть элементы «.» и «..», помещаемые в каталог в момент его создания. Элемент «.» содержит номер i-узла текущего каталога, а элемент «..» — номер i-узла родительского каталога. Таким образом, процедура, ведущая поиск файла ../dick/prog.c, просто находит «..» в рабочем каталоге, разыскивает в нем номер i-узла родительского каталога, в котором ищет описатель каталога dick. Для обработки этих имен не требуется никакого специального механизма. Что касается системы каталогов, она представляет собой обыкновенные ASCII-строки, ничем не отличающиеся от любых других имен. Единственная тонкость в том, что элемент «..» в корневом каталоге указывает на сам этот каталог.
Источник: «Современные операционные системы 4-е изд.», Таненбаум Э., Бос Х., 2015