The design of the unix operating system by Maurice J
| Вид материала | Реферат |
| 4.6 Назначение индекса новому файлу |
- Лекция 10. Файловые системы Unix, 116.79kb.
- Уровни рассмотрения, 314.07kb.
- Курс по операционным системам (на примере ос windows) Основан на учебном курсе Windows, 29.21kb.
- Выполнил ученик 11 «А» класса, 443.51kb.
- Ос лекция 1 (2-й семестр – временно), 101.4kb.
- Operating System, 7686.97kb.
- Unix-подобные операционные системы, характеристики, особенности, разновидности, 40.63kb.
- 1. ms sql server. Общие сведения, 66.03kb.
- Shanti ananda maurice, 89.84kb.
- Методические материалы, 3002.45kb.
полнение системной операции chdir (изменить каталог). Все поиски
файлов по имени начинаются с текущего каталога процесса, если
только имя пути поиска не предваряется наклонной чертой, указы-
вая, что поиск нужно начинать с корневого каталога. В любом слу-
чае ядро может легко обнаружить индекс каталога, с которого начи-
нается поиск. Текущий каталог хранится в рабочей области
процесса, а корневой индекс системы хранится в глобальной пере-
менной (**).
Алгоритм namei использует при анализе составного имени пути
поиска промежуточные индексы; назовем их рабочими индексами. Ин-
декс каталога, откуда поиск берет начало, является первым рабочим
индексом. На каждой итерации цикла алгоритма ядро проверяет сов-
падение рабочего индекса с индексом каталога. В противном случае,
нарушилось бы утверждение, что только файлы, не являющиеся ката-
логами, могут быть листьями дерева файловой системы. Процесс так-
же должен иметь право производить поиск в каталоге (разрешения на
чтение недостаточно). Код идентификации пользователя для процесса
должен соответствовать коду индивидуального или группового вла-
---------------------------------------
(**) Чтобы изменить для себя корневой каталог файловой системы,
процесс может запустить системную операцию chroot. Новое
значение корня сохраняется в рабочей области процесса.
-------------------------------------------------------------┐
│ алгоритм namei /* превращение имени пути поиска в индекс */│
│ входная информация: имя пути поиска │
│ выходная информация: заблокированный индекс │
│ { │
│ если (путь поиска берет начало с корня) │
│ рабочий индекс = индексу корня (алгоритм iget); │
│ в противном случае │
│ рабочий индекс = индексу текущего каталога │
│ (алгоритм iget); │
│ │
│ выполнить (пока путь поиска не кончился) │
│ { │
│ считать следующую компоненту имени пути поиска; │
│ проверить соответствие рабочего индекса каталогу │
│ и права доступа; │
│ если (рабочий индекс соответствует корню и компо- │
│ нента имени "..") │
│ продолжить; /* цикл с условием продолжения */│
│ считать каталог (рабочий индекс), повторяя алго- │
│ ритмы bmap, bread и brelse; │
│ если (компонента соответствует записи в каталоге │
│ (рабочем индексе)) │
│ { │
│ получить номер индекса для совпавшей компонен-│
│ ты; │
│ освободить рабочий индекс (алгоритм iput); │
│ рабочий индекс = индексу совпавшей компоненты │
│ (алгоритм iget); │
│ } │
│ в противном случае /* компонента отсутствует в │
│ каталоге */ │
│ возвратить (нет индекса); │
│ } │
│ возвратить (рабочий индекс); │
│ } │
L-------------------------------------------------------------
Рисунок 4.11. Алгоритм превращения имени пути поиска в индекс
дельца файла и должно быть предоставлено право исполнения, либо
поиск нужно разрешить всем пользователям. В противном случае, по-
иск не получится.
Ядро выполняет линейный поиск файла в каталоге, ассоциирован-
ном с рабочим индексом, пытаясь найти для компоненты имени пути
поиска подходящую запись в каталоге. Исходя из адреса смещения в
байтах внутри каталога (начиная с 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, в файловой системе имеется ли-
нейный список индексов. Индекс считается свободным, если поле его
типа хранит нулевое значение. Если процессу понадобился новый ин-
декс, ядро теоретически могло бы произвести поиск свободного ин-
декса в списке индексов. Однако, такой поиск обошелся бы дорого,
поскольку потребовал бы по меньшей мере одну операцию чтения (до-
пустим, с диска) на каждый индекс. Для повышения производитель-
ности в суперблоке файловой системы хранится массив номеров сво-
бодных индексов в файловой системе.
На Рисунке 4.12 приведен алгоритм ialloc назначения новых ин-
дексов. По причинам, о которых пойдет речь ниже, ядро сначала
проверяет, не заблокировал ли какой-либо процесс своим обращением
список свободных индексов в суперблоке. Если список номеров ин-
дексов в суперблоке не пуст, ядро назначает номер следующего ин-
декса, выделяет для вновь назначенного дискового индекса свобод-
ный индекс в памяти, используя алгоритм iget (читая индекс с
диска, если необходимо), копирует дисковый индекс в память, ини-
циализирует поля в индексе и возвращает индекс заблокированным.
Затем ядро корректирует дисковый индекс, указывая, что к индексу
произошло обращение. Ненулевое значение поля типа файла говорит о
том, что дисковый индекс назначен. В простейшем случае с индексом
все в порядке, но в условиях конкуренции делается необходимым
проведение дополнительных проверок, на чем мы еще кратко остано-
вимся. Грубо говоря, конкуренция возникает, когда несколько про-
цессов вносят изменения в общие информационные структуры, так что
результат зависит от очередности выполнения процессов, пусть даже
все процессы будут подчиняться протоколу блокировки. Здесь пред-
полагается, например, что процесс мог бы получить уже используе-
мый индекс. Конкуренция связана с проблемой взаимного исключения,
описанной в главе 2, с одним замечанием: различные схемы блоки-
ровки решают проблему взаимного исключения, но не могут сами по
себе решить все проблемы конкуренции.
Если список свободных индексов в суперблоке пуст, ядро прос-
матривает диск и помещает в суперблок как можно больше номеров
свободных индексов. При этом ядро блок за блоком считывает индек-
сы с диска и наполняет список номеров индексов в суперблоке до
отказа, запоминая индекс с номером, наибольшим среди найденных.
Назовем этот индекс "запомненным"; это последний индекс, записан-
ный в суперблок. В следующий раз, когда ядро будет искать на дис-
ке свободные индексы, оно использует запомненный индекс в качест-
ве стартовой точки, благодаря чему гарантируется, что ядру не
придется зря тратить время на считывание дисковых блоков, в кото-
-------------------------------------------------------------┐
│ алгоритм ialloc /* выделение индекса */ │
│ входная информация: файловая система │
│ выходная информация: заблокированный индекс │
│ { │
│ выполнить │
│ { │
│ если (суперблок заблокирован) │
│ { │
│ приостановиться (пока суперблок не освободится); │
│ продолжить; /* цикл с условием продолжения */ │
│ } │
│ если (список индексов в суперблоке пуст) │
│ { │
│ заблокировать суперблок; │
│ выбрать запомненный индекс для поиска свободных │
│ индексов; │
│ искать на диске свободные индексы до тех пор, пока│
│ суперблок не заполнится, или пока не будут най- │
│ дены все свободные индексы (алгоритмы bread и │
│ brelse); │
│ снять блокировку с суперблока; │
│ возобновить выполнение процесса (как только супер-│
│ блок освободится); │
│ если (на диске отсутствуют свободные индексы) │
│ возвратить (нет индексов); │
│ запомнить индекс с наибольшим номером среди най- │
│ денных для последующих поисков свободных индек- │
│ сов; │
│ } │
│ /* список индексов в суперблоке не пуст */ │
│ выбрать номер индекса из списка индексов в супербло- │
│ ке; │
│ получить индекс (алгоритм iget); │
│ если (индекс после всего этого не свободен) /* !!! */│
│ { │
│ переписать индекс на диск; │
│ освободить индекс (алгоритм iput); │
│ продолжить; /* цикл с условием продолжения */ │
│ } │
│ /* индекс свободен */ │
│ инициализировать индекс; │
│ переписать индекс на диск; │
│ уменьшить счетчик свободных индексов в файловой сис- │
│ теме; │
│ возвратить (индекс); │
│ } │
│ } │
L-------------------------------------------------------------
Рисунок 4.12. Алгоритм назначения новых индексов
рых свободные индексы наверняка отсутствуют. После формирования
нового набора номеров свободных индексов ядро запускает алгоритм
назначения индекса с самого начала. Всякий раз, когда ядро назна-
чает дисковый индекс, оно уменьшает значение счетчика свободных
индексов, записанное в суперблоке.
Список свободных индексов в суперблоке
----------------------T------T------T-------------------┐
│ свободные индексы │ │ │ пустота │
│<>│ 83 │ 48 │<>│
L---------------------+------+------+--------------------
18 19 20 массив 1
│ указатель
Список свободных индексов в суперблоке
----------------------T------T------T-------------------┐
│ свободные индексы │ │ │ пустота │
│<>│ 83 │ <│>│
L---------------------+------+------+--------------------
18 19 20 массив 1
│ указатель
(а) Назначение свободного индекса из середины списка
Список свободных индексов в суперблоке
-------T------------------------------------------------┐
│ 470 │ пустота │
│<│>│
L------+-------------------------------------------------
0 массив 1
│указатель (запомненный индекс)
Список свободных индексов в суперблоке
-------T------------------------------T-----T-----T-----┐
│ 535 │ свободные индексы │ 476 │ 475 │ 471 │
│<││││>│
L------+------------------------------+-----+-----+------
0 48 49 50
указатель │
(б) Назначение свободного индекса, когда список в супер-
блоке пуст
Рисунок 4.13. Два массива номеров свободных индексов
Рассмотрим две пары массивов номеров свободных индексов (Ри-
сунок 4.13). Если список свободных индексов в суперблоке имеет
вид первого массива на Рисунке 4.13(а) при назначении индекса яд-
ром, то значение указателя на следующий номер индекса уменьшается
до 18 и выбирается индекс с номером 48. Если же список выглядит
как первый массив на Рисунке 4.13(б), ядро заметит, что массив
пуст и обратится в поисках свободных индексов к диску, при этом
поиск будет производиться, начиная с индекса с номером 470, кото-
рый был ранее запомнен. Когда ядро заполнит список свободных ин-
дексов в суперблоке до отказа, оно запомнит последний индекс в
качестве начальной точки для последующих просмотров диска. Ядро
производит назначение файлу только что выбранного с диска индекса
(под номером 471 на рисунке) и продолжает прерванную обработку.
-------------------------------------------------------------┐
│ алгоритм ifree /* освобождение индекса */ │
│ входная информация: номер индекса в файловой системе │
│ выходная информация: отсутствует │
│ { │
│ увеличить на 1 счетчик свободных индексов в файловой │
│ системе; │
│ если (суперблок заблокирован) │
│ возвратить управление; │
│ если (список индексов заполнен) │
│ { │
│ если (номер индекса меньше номера индекса, запом- │
│ ненного для последующего просмотра) │
│ запомнить для последующего просмотра номер │
│ введенного индекса; │
│ } │
│ в противном случае │
│ сохранить номер индекса в списке индексов; │
│ возвратить управление; │
│ } │
L-------------------------------------------------------------
Рисунок 4.14. Алгоритм освобождения индекса
Алгоритм освобождения индекса построен значительно проще.
Увеличив на единицу общее количество доступных в файловой системе
индексов, ядро проверяет наличие блокировки у суперблока. Если он
заблокирован, ядро, чтобы предотвратить конкуренцию, немедленно
сообщает: номер индекса отсутствует в суперблоке, но индекс может
быть найден на диске и доступен для переназначения. Если список
не заблокирован, ядро проверяет, имеется ли место для новых номе-
ров индексов и если да, помещает номер индекса в список и выходит
из алгоритма. Если список полон, ядро не сможет в нем сохранить
вновь освобожденный индекс. Оно сравнивает номер освобожденного
индекса с номером запомненного индекса. Если номер освобожденного
индекса меньше номера запомненного, ядро запоминает номер вновь
освобожденного индекса, выбрасывая из суперблока номер старого
запомненного индекса. Индекс не теряется, поскольку ядро может
найти его, просматривая список индексов на диске. Ядро поддержи-
вает структуру списка в суперблоке таким образом, что последний
номер, выбираемый им из списка, и есть номер запомненного индек-
са. В идеале не должно быть свободных индексов с номерами, мень-
-------T------------------------------T-----T-----T-----┐
│ 535 │ свободные индексы │ 476 │ 475 │ 471 │
│<││││>│
L------+------------------------------+-----+-----+------
0 48 49 50
│
запомненный индекс указатель │
(а) Первоначальный вид списка свободных индексов в супер-
блоке
-------T------------------------------T-----T-----T-----┐
│ 499 │ свободные индексы │ 476 │ 475 │ 471 │
│<││││>│
L------+------------------------------+-----+-----+------
0 48 49 50
│
запомненный индекс указатель │
(б) Освободился индекс номер 499
-------T------------------------------T-----T-----T-----┐
│ 499 │ свободные индексы │ 476 │ 475 │ 471 │
│<││││>│
L------+------------------------------+-----+-----+------
0 48 49 50
│
запомненный индекс указатель │
(в) Освободился индекс номер 601
Рисунок 4.15. Размещение номеров свободных индексов в суперб-
локе
шими, чем номер запомненного индекса, но возможны и исключения.
Рассмотрим два примера освобождения индексов. Если в списке
свободных индексов в суперблоке еще есть место для новых номеров
свободных индексов (как на Рисунке 4.13(а)), ядро помещает в спи-
сок новый номер, переставляет указатель на следующий свободный
индекс и продолжает выполнение процесса. Но если список свободных
индексов заполнен (Рисунок 4.15), ядро сравнивает номер освобож-
денного индекса с номером запомненного индекса, с которого нач-
нется просмотр диска в следующий раз. Если вначале список свобод-
ных индексов имел вид, как на Рисунке 4.15(а), то когда ядро
освобождает индекс с номером 499, оно запоминает его и выталкива-
ет номер 535 из списка. Если затем ядро освобождает индекс с но-
мером 601, содержимое списка свободных индексов не изменится.
Когда позднее ядро использует все индексы из списка свободных ин-