Архитектура Unix




. Алгоритм превращения имени пути поиска в индекс



Рисунок 4.11. Алгоритм превращения имени пути поиска в индекс



алгоритм namei /* превращение имени пути поиска в индекс */ входная информация: имя пути поиска выходная информация: заблокированный индекс { если (путь поиска берет начало с корня) рабочий индекс = индексу корня (алгоритм iget); в противном случае рабочий индекс = индексу текущего каталога (алгоритм iget); выполнить (пока путь поиска не кончился) { считать следующую компоненту имени пути поиска; проверить соответствие рабочего индекса каталогу и права доступа; если (рабочий индекс соответствует корню и компо- нента имени "..") продолжить; /* цикл с условием продолжения */ считать каталог (рабочий индекс), повторяя алго- ритмы bmap, bread и brelse; если (компонента соответствует записи в каталоге (рабочем индексе)) { получить номер индекса для совпавшей компонен- ты; освободить рабочий индекс (алгоритм iput); рабочий индекс = индексу совпавшей компоненты (алгоритм iget); } в противном случае /* компонента отсутствует в каталоге */ возвратить (нет индекса); } возвратить (рабочий индекс); }


Алгоритм 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 не работали еще на машинах с большим объемом памяти, поэтому значительный упор был сделан на простые алгоритмы, такие как алгоритмы линейного поиска. Более сложные схемы поиска потребовали бы отличной, более сложной, структуры каталога, и возможно работали бы медленнее даже в небольших каталогах по сравнению со схемой линейного поиска.

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









Содержание  Назад  Вперед