алгоритм namei /* превращение имени пути поиска в индекс */
входная информация: имя пути поиска
выходная информация: заблокированный индекс
{
if (путь поиска берет начало с корня) рабочий индекс = индексу корня (алгоритм iget);
else индекс = индексу текущего каталога (алгоритм iget);
выполнить (пока путь поиска не кончился) {
считать следующую компоненту имени пути поиска;
проверить соответствие рабочего индекса каталогу и права доступа;
if (рабочий индекс соответствует корню и компонента имени «..») continue; /* цикл с условием продолжения */
считать каталог (рабочий индекс), повторяя алгоритмы bmap, bread и brelse;
if (компонента соответствует записи в каталоге (рабочем индексе)) {
получить номер индекса для совпавшей компоненты;
освободить рабочий индекс (алгоритм iput);
рабочий индекс = индексу совпавшей компоненты (алгоритм iget);
}
else /* компонента отсутствует в каталоге */ return (нет индекса);
}
return (рабочий индекс);
}
Рисунок 4.11. Алгоритм превращения имени пути поиска в индекс
Алгоритм namei использует при анализе составного имени пути поиска промежуточные индексы; назовем их рабочими индексами. Индекс каталога, откуда поиск берет начало, является первым рабочим индексом. На каждой итерации цикла алгоритма ядро проверяет совпадение рабочего индекса с индексом каталога. В противном случае, нарушилось бы утверждение, что только файлы, не являющиеся каталогами, могут быть листьями дерева файловой системы. Процесс также должен иметь право производить поиск в каталоге (разрешения на чтение недостаточно). Код идентификации пользователя для процесса должен соответствовать коду индивидуального или группового владельца файла и должно быть предоставлено право исполнения, либо поиск нужно разрешить всем пользователям. В противном случае, поиск не получится.
Ядро выполняет линейный поиск файла в каталоге, ассоциированном с рабочим индексом, пытаясь найти для компоненты имени пути поиска подходящую запись в каталоге. Исходя из адреса смещения в байтах внутри каталога (начиная с 0), оно определяет местоположение дискового блока в соответствии с алгоритмом bmap и считывает этот блок, используя алгоритм bread. По имени компоненты ядро производит в блоке поиск, представляя содержимое блока как последовательность записей каталога. При обнаружении совпадения ядро переписывает номер индекса из данной точки входа, освобождает блок (алгоритм brelse) и старый рабочий индекс (алгоритм iput), и переназначает индекс найденной компоненты (алгоритм iget). Новый индекс становится рабочим индексом. Если ядро не находит в блоке подходящего имени, оно освобождает блок, прибавляет к адресу смещения число байтов в блоке, превращает новый адрес смещения в номер дискового блока (алгоритм bmap) и читает следующий блок. Ядро повторяет эту процедуру до тех пор, пока имя компоненты пути поиска не совпадет с именем точки входа в каталоге, либо до тех пор, пока не будет достигнут конец каталога.
Предположим, например, что процессу нужно открыть файл «/etc/passwd». Когда ядро начинает анализировать имя файла, оно наталкивается на наклонную черту («/») и получает индекс корня системы. Сделав корень текущим рабочим индексом, ядро наталкивается на строку «etc». Проверив соответствие текущего индекса каталогу («/») и наличие у процесса права производить поиск в каталоге, ядро ищет в корневом каталоге файл с именем «etc». Оно просматривает корневой каталог блок за блоком и исследует каждую запись в блоке, пока не обнаружит точку входа для файла «etc». Найдя эту точку входа, ядро освобождает индекс, отведенный для корня (алгоритм iput), и выделяет индекс файлу «etc» (алгоритм iget) в соответствии с номером индекса в обнаруженной записи. Удостоверившись в том, что «etc» является каталогом, а также в том, что имеются необходимые права производить поиск, ядро просматривает каталог «etc» блок за блоком в поисках записи, соответствующей файлу «passwd». Если посмотреть на Рисунок 4.10, можно увидеть, что запись о файле «passwd» является девятой записью в каталоге. Обнаружив ее, ядро освобождает индекс, выделенный файлу «etc», и выделяет индекс файлу «passwd», после чего — поскольку имя пути поиска исчерпано — возвращает этот индекс процессу.
Естественно задать вопрос об эффективности линейного поиска в каталоге записи, соответствующей компоненте имени пути поиска. Ричи показывает (см. [Ritchie 78b], стр.1968), что линейный поиск эффективен, поскольку он ограничен размером каталога. Более того, ранние версии системы UNIX не работали еще на машинах с большим объемом памяти, поэтому значительный упор был сделан на простые алгоритмы, такие как алгоритмы линейного поиска. Более сложные схемы поиска потребовали бы отличной, более сложной, структуры каталога, и возможно работали бы медленнее даже в небольших каталогах по сравнению со схемой линейного поиска.
4.5 СУПЕРБЛОК
До сих пор в этой главе описывалась структура файла, при этом предполагалось, что индекс предварительно связывался с файлом и что уже были определены дисковые блоки, содержащие информацию. В следующих разделах описывается, каким образом ядро назначает индексы и дисковые блоки. Чтобы понять эти алгоритмы, рассмотрим структуру суперблока.
Суперблок состоит из следующих полей:
• размер файловой системы,
• количество свободных блоков в файловой системе,
• список свободных блоков, имеющихся в файловой системе,
• индекс следующего свободного блока в списке свободных блоков,
• размер списка индексов,
• количество свободных индексов в файловой системе,
• список свободных индексов в файловой системе,
• следующий свободный индекс в списке свободных индексов,
• заблокированные поля для списка свободных блоков и свободных индексов,
• флаг, показывающий, что в суперблок были внесены изменения.
В оставшейся части главы будет объяснено, как пользоваться массивами, указателями и замками блокировки. Ядро периодически переписывает суперблок на диск, если в суперблок были внесены изменения, для того, чтобы обеспечивалась согласованность с данными, хранящимися в файловой системе.
4.6 НАЗНАЧЕНИЕ ИНДЕКСА НОВОМУ ФАЙЛУ
Для выделения известного индекса, то есть индекса, для которого предварительно определен собственный номер (и номер файловой системы), ядро использует алгоритм iget. В алгоритме namei, например, ядро определяет номер индекса, устанавливая соответствие между компонентой имени пути поиска и именем в каталоге. Другой алгоритм, ialloc, выполняет назначение дискового индекса вновь создаваемому файлу.
Как уже говорилось в главе 2, в файловой системе имеется линейный список индексов. Индекс считается свободным, если поле его типа хранит нулевое значение. Если процессу понадобился новый индекс, ядро теоретически могло бы произвести поиск свободного индекса в списке индексов. Однако, такой поиск обошелся бы дорого, поскольку потребовал бы по меньшей мере одну операцию чтения (допустим, с диска) на каждый индекс. Для повышения производительности в суперблоке файловой системы хранится массив номеров свободных индексов в файловой системе.
алгоритм ialloc /* выделение индекса */
входная информация: файловая система
выходная информация: заблокированный индекс
{
do {
if (суперблок заблокирован) {
sleep (пока суперблок не освободится);
continue; /* цикл с условием продолжения */
}
if (список индексов в суперблоке пуст) {
заблокировать суперблок; выбрать запомненный индекс для поиска свободных индексов;
искать на диске свободные индексы до тех пор, пока суперблок не заполнится или пока не будут найдены все свободные индексы (алгоритмы bread и brelse);
снять блокировку с суперблока;
возобновить выполнение процесса (как только суперблок освободится);
