Реализация классической файловой системы UNIX

Все системы UNIX могут под­держивать несколько дисковых разделов, каждый со своей файловой системой.

В классической системе UNIX раздел диска содержит файловую систему со следующей структурой. Блок 0 не используется системой и час­то содержит программу загрузки компьютера. Блок 1 представляет собой супер­блок. В нем хранится критическая информация о размещении файловой системы, включая количество i-узлов, количество дисковых блоков, а также начало списка свободных блоков диска (обычно несколько сот записей). При уничтожении супер­блока файловая система окажется нечитаемой. Следом за суперблоком располагаются i-узлы (i-nodes, сокращение от index-nodes – индекс-узлы). Они нумеруются от 1 до некоторого максимального числа. Каждый i-узел имеет 64 байт в длину и описывает ровно один файл, i-узел содер­жит учетную информацию (включая всю информацию, возвращаемую системным вызовом stat, который ее просто берет в i-узле), а также достаточное количество информации, чтобы найти все блоки файла на диске. Следом за i-узлами располагаются блоки с данными. Здесь хранятся все фай­лы и каталоги. Если файл или каталог состоит более чем из одного блока, блоки файла не обязаны располагаться на диске подряд. В действительности блоки боль­шого файла, как правило, оказываются разбросанными по всему диску.

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

Если искомый файл присутствует в каталоге, система извлекает его i-узел и использует его в качестве индекса в таблице i-узлов (на диске), чтобы найти соответствующий i-узел и считать его в память. Этот i-узел помещается в таблицу i-узлов – структуру данных в ядре, содержащую все i-узлы открытых в данный мо­мент файлов и каталогов. Формат i-узлов варьируется от одной версии UNIX к другой. Как минимум i-узел должен содержать все поля, возвращаемые системным вызовом stat.

Поиск файла по абсолютному пути, например /man/labs/operat немного сложнее. Сначала система находит корневой каталог, как правило, использующий i-узел с но­мером 2 (i-узел 1 обычно резервируется для хранения дефектных блоков). Затем он ищет в корневом каталоге строку «man», чтобы получить номер i-узла каталога /man. Затем считывается этот i-узел, и из него извлекаются номера блоков, в которых располагается каталог /man. После этого считывается каталог /man, в котором ищет­ся строка «labs». Когда нужная запись найдена, из нее извлекается номер i-узла для каталога /man/labs и т. д. Таким образом, использование относительного имени фай­ла не только удобнее для пользователя, но также представляет существенно мень­шее количество работы для файловой системы.

Рассмотрим далее, как система считывает файл. По дескриптору файла файловая система должна найти i-узел соответствую­щего файла. С каждым дескриптором файла должен быть связан указатель в файле, определяющий байт в файле, кото­рый будет считан или записан при следующем обращении к файлу. Указатель помещается в таблицу деск­рипторов файла. При этом каждый процесс, открывающий файл, получает соб­ственную позицию в файле. Для передачи указателя от одного процесса другому вводится в обращение новая таблица – таблица открытых файлов, которая располагается между таблицей дескрипторов файлов и таблицей i-узлов. Указатели хранятся в файле, а бит чтения/записи в этой таблице. Задача таблицы открытых файлов заключа­ется в том, чтобы позволить родительскому и дочернему процессам совместно использовать один указатель в файле, но для посторонних процессов выделять отдельные указатели.

Каждый i-узел содержит дисковые адреса первых 10 блоков файла. Если позиция в файле попадает в его первые 10 блоков, то считывается нужный блок файла, а данные копируются пользователю. Для поддержки файлов, длина которых превышает 10 блоков, в i-узле содержится дисковый адрес одинарного косвенного блока. Этот блок содержит дисковые адреса дополни­тельных блоков файла. Например, если размер блока составляет 1 Кбайт, а диско­вый адрес занимает 4 байта, то одинарный косвенный блок может хранить до 256 дис­ковых адресов. Такая схема позволяет поддержать файлы размером до 266 Кбайт. Для файлов, размер которых превосходит 266 Кбайт, используется двойной косвенный блок. Он содержит адреса 256 одинарных косвенных блоков, каждый из которых содержит адреса 256 блоков данных. Такая схема позволяет поддер­жать файлы размером до 10 + 2 в степени 16 блоков (67 119 104 байт). Если и этого оказыва­ется недостаточно, в i-узле есть место для тройного косвенного блока. Его указа­тели показывают на 256 двойных косвенных блоков.