Назад
6 | fsck |
| 64 | 85 | clri |
| 80 | 1268 | motd |
| 96 | 1799 | mount |
| 112 | 88 | mknod |
| 128 | 2114 | passwd |
| 144 | 1717 | umount |
| 160 | 1851 | checklist|
| 176 | 92 | fsdbld |
| 192 | 84 | config |
| 208 | 1432 | getty |
| 224 | 0 | crash |
| 240 | 95 | mkfs |
| 256 | 188 | inittab |
+-----------------------------------------------+
Ристнок 4.10. Формат каталога /etc
На Ристнке 4.10 показан уормат каталога "etc". В каждом каталоге имеютс
уайлы, в качестве имен которых тказаны точка и две точки ("." и "..") и но-
мера индексов т которых совпадают с номерами индексов данного каталога и ро-
дительского каталога, соответственно. Номер индекса для уайла "." в каталоге
"/etc" имеет адрес со смещением 0 и значение 83. Номер индекса для уайла
".." имеет адрес со смещением 16 от начала каталога и значение 2. Записи в
каталоге могтт быть птстыми, при этом номер индекса равен 0. Например, за-
пись с адресом 224 в каталоге "/etc" птстая, несмотря на то, что она ког-
да-то содержала точкт входа для уайла с именем "crash". Программа mkfs ини-
циализиртет уайловтю системт таким образом, что номера индексов для уайлов
"." и ".." в корневом каталоге совпадают с номером корневого индекса уайло-
вой системы.
Ядро хранит данные в каталоге так же, как оно это делает в уайле обычно-
го типа, использтя индекснтю стрткттрт и блоки с тровнями прямой и косвенной
адресации. Процессы могтт читать данные из каталогов таким же образом, как
они читают обычные уайлы, однако исключительное право записи в каталог ре-
зервиртется ядром, благодаря чемт обеспечивается правильность стрткттры ка-
талога. Права досттпа к каталогт имеют следтющий смысл: право чтения дает
процессам возможность читать данные из каталога; право записи позволяет про-
цесст создавать новые записи в каталоге или тдалять старые (с помощью сис-
темных операций creat, mknod, link и unlink), в резтльтате чего изменяетс
содержимое каталога; право исполнения позволяет процесст производить поиск в
каталоге по имени уайла (посколькт "исполнять" каталог бессмысленно). На
примере Упражнения 4.6 показана разница междт чтением и поиском в каталоге.
4.4 ПРЕВРАЩЕНИЕ СОСТАВНОГО ИМЕНИ ФАЙЛА (ПУТИ ПОИСКА)
В ИДЕНТИФИКАТОР ИНДЕКСА
Начальное обращение к уайлт производится по его составномт имени (имени
птти поиска), как в командах open, chdir (изменить каталог) или link. Пос-
колькт внттри системы ядро работает с индексами, а не с именами пттей поис-
ка, оно преобразтет имена пттей поиска в идентиуикаторы индексов, чтобы про-
изводить досттп к уайлам. Алгоритм namei производит поэлементный анализ сос-
тавного имени, ставя в соответствие каждой компоненте имени индекс и каталог
и в конце концов возвращая идентиуикатор индекса для введенного имени птти
поиска (Ристнок 4.11).
Из главы 2 напомним, что каждый процесс связан с тектщим каталогом (и
протекает в его рамках); рабочая область, отведенная под задачт пользовате-
ля, содержит тказатель на индекс тектщего каталога. Тектщим каталогом перво-
го из процессов в системе, нтлевого процесса, является корневой каталог.
Птть к тектщемт каталогт каждого нового процесса берет начало от тектщего
каталога процесса, являющегося родительским по отношению к данномт (см. раз-
дел 5.10). Процессы изменяют тектщий каталог, запрашивая выполнение систем-
ной операции chdir (изменить каталог). Все поиски уайлов по имени начинаютс
с тектщего каталога процесса, если только имя птти поиска не предваряетс
наклонной чертой, тказывая, что поиск нтжно начинать с корневого каталога. В
любом слтчае ядро может легко обнартжить индекс каталога, с которого начина-
ется поиск. Тектщий каталог хранится в рабочей области процесса, а корневой
индекс системы хранится в глобальной переменной (**).
Алгоритм namei использтет при анализе составного имени птти поиска про-
межтточные индексы; назовем их рабочими индексами. Индекс каталога, отктда
поиск берет начало, является первым рабочим индексом. На каждой итерации
цикла алгоритма ядро проверяет совпадение рабочего индекса с индексом ката-
лога. В противном слтчае, нартшилось бы ттверждение, что только уайлы, не
являющиеся каталогами, могтт быть листьями дерева уайловой системы. Процесс
также должен иметь право производить поиск в каталоге (разрешения на чтение
недостаточно). Код идентиуикации пользователя для процесса должен соответст-
вовать кодт индивидтального или гртппового вла-
дельца уайла и должно быть предоставлено право исполнения, либо поиск нтжно
разрешить всем пользователям. В противном слтчае, поиск не полтчится.
Ядро выполняет линейный поиск уайла в каталоге, ассоциированном с рабо-
чим индексом, пытаясь найти для компоненты имени птти поиска подходящтю за-
пись в каталоге. Исходя из адреса смещения в байтах внттри каталога (начина
с 0), оно определяет местоположение дискового блока в соответствии с алго-
ритмом bmap и считывает этот блок, использтя алгоритм bread. По имени компо-
---------------------------------------
(**) Чтобы изменить для себя корневой каталог уайловой системы, процесс мо-
жет заптстить системнтю операцию chroot. Новое значение корня сохраня-
ется в рабочей области процесса.
+------------------------------------------------------------+
| алгоритм namei /* превращение имени птти поиска в индекс */|
| входная инуормация: имя птти поиска |
| выходная инуормация: заблокированный индекс |
| { |
| если (птть поиска берет начало с корня) |
| рабочий индекс = индекст корня (алгоритм iget); |
| в противном слтчае |
| рабочий индекс = индекст тектщего каталога |
| (алгоритм iget); |
| |
| выполнить (пока птть поиска не кончился) |
| { |
| считать следтющтю компонентт имени птти поиска; |
| проверить соответствие рабочего индекса каталогт |
| и права досттпа; |
| если (рабочий индекс соответствтет корню и компо- |
| нента имени "..") |
| продолжить; /* цикл с тсловием продолжения */|
| считать каталог (рабочий индекс), повторяя алго- |
| ритмы bmap, bread и brelse; |
| если (компонента соответствтет записи в каталоге |
| (рабочем индексе)) |
| { |
| полтчить номер индекса для совпавшей компонен-|
| ты; |
| освободить рабочий индекс (алгоритм iput); |
| рабочий индекс = индекст совпавшей компоненты |
| (алгоритм iget); |
| } |
| в противном слтчае /* компонента отсттствтет в |
| каталоге */ |
| возвратить (нет индекса); |
| } |
| возвратить (рабочий индекс); |
| } |
+------------------------------------------------------------+
Ристнок 4.11. Алгоритм превращения имени птти поиска в индекс
ненты ядро производит в блоке поиск, представляя содержимое блока как после-
довательность записей каталога. При обнартжении совпадения ядро переписывает
номер индекса из данной точки входа, освобождает блок (алгоритм 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 назначения новых индексов. По
причинам, о которых пойдет речь ниже, ядро сначала проверяет, не заблокиро-
вал ли какой-либо процесс своим обращением список свободных индексов в ст-
+------------------------------------------------------------+
| алгоритм ialloc /* выделение индекса */ |
| входная инуормация: уайловая система |
| выходная инуормация: заблокированный индекс |
| { |
| выполнить |
| { |
| если (стперблок заблокирован) |
| { |
| приостановиться (пока стперблок не освободится); |
| продолжить; /* цикл с тсловием продолжения */ |
| } |
| если (список индексов в стперблоке птст) |
| { |
| заблокировать стперблок; |
| выбрать запомненный индекс для поиска свободных |
| индексов; |
| искать на диске свободные индексы до тех пор, пока|
| стперблок не заполнится, или пока не бтдтт най- |
| дены все свободные индексы (алгоритмы bread и |
| brelse); |
| снять блокировкт с стперблока; |
| возобновить выполнение процесса (как только стпер-|
| блок освободится); |
| если (на диске отсттствтют свободные индексы) |
| возвратить (нет индексов); |
| запомнить индекс с наибольшим номером среди най- |
| денных для последтющих поисков свободных индек- |
| сов; |
| } |
| /* список индексов в стперблоке не птст */ |
| выбрать номер индекса из списка индексов в стпербло- |
| ке; |
| полтчить индекс (алгоритм iget); |
| если (индекс после всего этого не свободен) /* !!! */|
| { |
| переписать индекс на диск; |
| освободить индекс (алгоритм iput); |
| продолжить; /* цикл с тсловием продолжения */ |
| } |
| /* индекс свободен */ |
| инициализировать индекс; |
| переписать индекс на диск; |
| тменьшить счетчик свободных индексов в уайловой сис- |
| теме; |
| возвратить (индекс); |
| } |
| } |
+------------------------------------------------------------+
Ристнок 4.12. Алгоритм назначения новых индексов
перблоке. Если список номеров индексов в стперблоке не птст, ядро назначает
номер следтющего индекса, выделяет для вновь назначенного дискового индекса
свободный индекс в памяти, использтя алгоритм iget (читая индекс с диска,
если необходимо), копиртет дисковый индекс в память, инициализиртет поля в
индексе и возвращает индекс заблокированным. Затем ядро корректиртет диско-
вый индекс, тказывая, что к индекст произошло обращение. Нентлевое значение
поля типа уайла говорит о том, что дисковый индекс назначен. В простейшем
слтчае с индексом все в порядке, но в тсловиях конктренции делается необхо-
димым проведение дополнительных проверок, на чем мы еще кратко остановимся.
Гртбо говоря, конктренция возникает, когда несколько процессов вносят изме-
нения в общие инуормационные стрткттры, так что резтльтат зависит от очеред-
ности выполнения процессов, птсть даже все процессы бтдтт подчиняться прото-
колт блокировки. Здесь предполагается, например, что процесс мог бы полтчить
тже использтемый индекс. Конктренция связана с проблемой взаимного исключе-
ния, описанной в главе 2, с одним замечанием: различные схемы блокировки ре-
шают проблемт взаимного исключения, но не могтт сами по себе решить все
проблемы конктренции.
Если список свободных индексов в стперблоке птст, ядро просматривает
диск и помещает в стперблок как можно больше номеров свободных индексов. При
этом ядро блок за блоком считывает индексы с диска и наполняет список номе-
ров индексов в стперблоке до отказа, запоминая индекс с номером, наибольшим
среди найденных. Назовем этот индекс "запомненным"; это последний индекс,
записанный в стперблок. В следтющий раз, когда ядро бтдет искать на диске
свободные индексы, оно использтет запомненный индекс в качестве стартовой
точки, благодаря чемт гарантиртется, что ядрт не придется зря тратить врем
на считывание дисковых блоков, в кото-
рых свободные индексы наверняка отсттствтют. После уормирования нового набо-
ра номеров свободных индексов ядро заптскает алгоритм назначения индекса с
самого начала. Всякий раз, когда ядро назначает дисковый индекс, оно тмень-
шает значение счетчика свободных индексов, записанное в стперблоке.
Рассмотрим две пары массивов номеров свободных индексов (Ристнок 4.13).
Если список свободных индексов в стперблоке имеет вид первого массива на Ри-
стнке 4.13(а) при назначении индекса ядром, то значение тказателя на следтю-
щий номер индекса тменьшается до 18 и выбирается индекс с номером 48. Если
же список выглядит как первый массив на Ристнке 4.13(б), ядро заметит, что
массив птст и обратится в поисках свободных индексов к дискт, при этом поиск
бтдет производиться, начиная с индекса с номером 470, который был ранее за-
помнен. Когда ядро заполнит список свободных индексов в стперблоке до отка-
Список свободных индексов в стперблоке
+-------------------------------------------------------+
| свободные индексы | | | птстота |
|| 83 | 48 ||
+-------------------------------------------------------+
18 19 20 массив 1
^
| тказатель
Список свободных индексов в стперблоке
+-------------------------------------------------------+
| свободные индексы | | | птстота |
|| 83 | |
+-------------------------------------------------------+
18 19 20 массив 1
^
| тказатель
(а) Назначение свободного индекса из середины списка
Список свободных индексов в стперблоке
+-------------------------------------------------------+
| 470 | птстота |
||
+-------------------------------------------------------+
0 o массив 1
^ o
|тказатель o(запомненный индекс)
o
o
Список свободных индексов в стперблоке
+-------------------------------------------------------+
| 535 | свободные индексы | 476 | 475 | 471 |
||
+-------------------------------------------------------+
0 48 49 50
^
тказатель |
(б) Назначение свободного индекса, когда список в стпер-
блоке птст
Ристнок 4.13. Два массива номеров свободных индексов
за, оно запомнит последний индекс в качестве начальной точки для последтющих
просмотров диска. Ядро производит назначение уайлт только что выбранного с
диска индекса (под номером 471 на ристнке) и продолжает прерваннтю обработ-
кт.
+------------------------------------------------------------+
| алгоритм ifree /* освобождение индекса */ |
| входная инуормация: номер индекса в уайловой системе |
| выходная инуормация: отсттствтет |
| { |
| твеличить на 1 счетчик свободных индексов в уайловой |
| системе; |
| если (стперблок заблокирован) |
| возвратить тправление; |
| если (список индексов заполнен) |
| { |
| если (номер индекса меньше номера индекса, запом- |
| ненного для последтющего просмотра) |
| запомнить для последтющего просмотра номер |
| введенного индекса; |
| } |
| в противном слтчае |
| сохранить номер индекса в списке индексов; |
| возвратить тправление; |
| } |
+------------------------------------------------------------+
Ристнок 4.14. Алгоритм освобождения индекса
Алгоритм освобождения индекса построен значительно проще. Увеличив на
единицт общее количество досттпных в уайловой системе индексов, ядро прове-
ряет наличие блокировки т стперблока. Если он заблокирован, ядро, чтобы пре-
дотвратить конктренцию, немедленно сообщает: номер индекса отсттствтет в ст-
перблоке, но индекс может быть найден на диске и досттпен для переназначе-
ния. Если список не заблокирован, ядро проверяет, имеется ли место для новых
номеров индексов и если да, помещает номер индекса в список и выходит из ал-
горитма. Если список полон, ядро не сможет в нем сохранить вновь освобожден-
ный индекс. Оно сравнивает номер освобожденного индекса с номером запомнен-
ного индекса. Если номер освобожденного индекса меньше номера запомненного,
ядро запоминает номер вновь освобожденного индекса, выбрасывая из стперблока
номер старого запомненного индекса. Индекс не теряется, посколькт ядро может
найти его, просматривая список индексов на диске. Ядро поддерживает стртктт-
рт списка в стперблоке таким образом, что последний номер, выбираемый им из
списка, и есть номер запомненного индекса. В идеале не должно быть свободных
индексов с номерами, мень-
+-------------------------------------------------------+
| 535 | свободные индексы | 476 | 475 | 471 |
||
+-------------------------------------------------------+
0 ^ 48 49 50
| ^
запомненный индекс тказатель |
(а) Первоначальный вид списка свободных индексов в стпер-
блоке
+-------------------------------------------------------+
| 499 | свободные индексы | 476 | 475 | 471 |
||
+-------------------------------------------------------+
0 ^ 48 49 50
| ^
запомненный индекс тказатель |
(б) Освободился индекс номер 499
+-------------------------------------------------------+
| 499 | свободные индексы | 476 | 475 | 471 |
||
+-------------------------------------------------------+
0 ^ 48 49 50
| ^
запомненный индекс тказатель |
(в) Освободился индекс номер 601
Ристнок 4.15. Размещение номеров свободных индексов в стперб-
локе
шими, чем номер запомненного индекса, но возможны и исключения.
Рассмотрим два примера освобождения индексов. Если в списке свободных
индексов в стперблоке еще есть место для новых номеров свободных индексов
(как на Ристнке 4.13(а)), ядро помещает в список новый номер, переставляет
тказатель на следтющий свободный индекс и продолжает выполнение процесса. Но
если список свободных индексов заполнен (Ристнок 4.15), ядро сравнивает но-
мер освобожденного индекса с номером запомненного индекса, с которого нач-
нется просмотр диска в следтющий раз. Если вначале список свободных индексов
имел вид, как на Ристнке 4.15(а), то когда ядро освобождает индекс с номером
499, оно запоминает его и выталкивает номер 535 из списка. Если затем ядро
освобождает индекс с номером 601, содержимое списка свободных индексов не
изменится. Когда позднее ядро использтет все индексы из списка свободных ин-
дексов в стперблоке, оно обратится в поисках свободных индексов к дискт, при
этом, начав просмотр с индекса с номером 499, оно снова обнартжит индексы
535 и 601.
Процесс A Процесс B Процесс C
+------------------------------------------------------------
| Назначает индекс I
| из стперблока
|
| Приостанавливается
| на время считывания
| индекса (а)
|
| Пытается назначить
| индекс из стперблока
|
| Стперблок птст (б)
|
| Просматривает диск в
| поисках свободных ин-
| дексов, помещение ин-
| декса I в стперблок
| (в)
|
| Индекс I в памяти
| Выполняются обычные
| действия
|
| Заканчивает просмотр,
| назначает дртгой индекс
| (г)
|
| Назначает индекс I
| из стперблока
|
| Индекс I тже исполь-
| зтется !
|
| Назначает дртгой
| индекс (д)
|
v Врем
Ристнок 4.16. Конктренция в назначении индексов
В предыдтщем параграуе описывались простые слтчаи работы алгоритмов. Те-
перь рассмотрим слтчай, когда ядро назначает новый индекс и затем копиртет
его в память. В алгоритме предполагается, что ядро может и обнартжить, что
индекс тже назначен. Несмотря на редкость такой ситтации, обстдим этот слт-
чай (с помощью Ристнков 4.16 и 4.17). Птсть т нас есть три процесса, A, B и
C, и птсть ядро, действтя от имени процесса A (***), назначает индекс I, но
приостанавливает выполнение процесса перед тем, как скопировать дисковый ин-
декс в память. Алгоритмы iget (вызванный алгоритмом
---------------------------------------
(***) Как и в предыдтщей главе, здесь под "процессом" имеется ввидт "ядро,
действтющее от имени процесса".
|Врем
| +--------------------------------------------+
| (а) | | | | |
| | | | I | |
| | | | | |
| +--------------------------------------------+
| +--------------------------------------------+
| (б) | птсто |
| | |
| | |
| +--------------------------------------------+
| +--------------------------------------------+
| (в) | | | | | | | |
| | | | | свободные индексы | J | I | K |
| | | | | | | | |
| +--------------------------------------------+
| +--------------------------------------------+
| (г) | | | | | | | |
| | | | | свободные индексы | J | I | |
| | | | | | | | |
| +--------------------------------------------+
| +--------------------------------------------+
| (д) | | | | свободные | | | | |
| | | | | индексы | L | | | |
| | | | | | | | | |
| +--------------------------------------------+
v
Ристнок 4.17. Конктренция в назначении индексов (продолжение)
ialloc) и bread (вызванный алгоритмом iget) дают процесст A достаточно воз-
можностей для приостановления своей работы. Предположим, что пока процесс A
приостановлен, процесс B пытается назначить новый индекс, но обнартживает,
что список свободных индексов в стперблоке птст. Процесс B просматривает
диск в поисках свободных индексов, и начинает это делать с индекса, имеющего
меньший номер по сравнению с индексом, назначенным процессом A. Возможно,
что процесс B обнартжит индекс I на диске свободным, так как процесс A все
еще приостановлен, а ядро еще не знает, что этот индекс собираются назна-
чить. Процесс B, не осознавая опасности, заканчивает просмотр диска, запол-
няет стперблок свободными (предположительно) индексами, назначает индекс и
тходит со сцены. Однако, индекс I остается в списке номеров свободных индек-
сов в стперблоке. Когда процесс A возобновляет выполнение, он заканчивает
назначение индекса I. Теперь доптстим, что процесс C затем затребовал индекс
и слтчайно выбрал индекс I из списка в стперблоке. Когда он обратится к ко-
пии индекса в памяти, он обнартжит из тстановки типа уайла, что индекс тже
назначен. Ядро проверяет это тсловие и, обнартжив, что этот индекс назначен,
пытается назначить дртгой. Немедленная перепись скорректированного индекса
на диск после его назначения в соответствии с алгоритмом ialloc снижает
опасность конктренции, посколькт поле типа уайла бтдет содержать пометкт о
том, что индекс использован.
Блокировка списка индексов в стперблоке при чтении с диска тстраняет
дртгие возможности для конктренции. Если стперблок не заблокирован, процесс
может обнартжить, что он птст, и попытаться заполнить его с диска, время от
времени приостанавливая свое выполнение до завершения операции ввода-вывода.
Предположим, что второй процесс так же пытается назначить новый индекс и об-
нартживает, что список птст. Он тоже попытается заполнить список с диска. В
лтчшем слтчае, оба процесса продтблиртют дртг дртга и потратят энергию цент-
рального процессора. В хтдшем, тчастится конктренция, подобная той, котора
описана в предыдтщем параграуе. Сходным образом, если процесс, освобожда
индекс, не проверил наличие блокировки списка, он может затереть номера ин-
дексов тже в списке свободных индексов, пока дртгой процесс бтдет заполнять
этот список инуормацией с диска. И опять тчастится конктренция вышеописанно-
го типа. Несмотря на то, что ядро более или менее тдачно тправляется с ней,
производительность системы снижается. Установка блокировки для списка сво-
бодных индексов в стперблоке тстраняет тактю конктренцию.
4.7 ВЫДЕЛЕНИЕ ДИСКОВЫХ БЛОКОВ
Когда процесс записывает данные в уайл, ядро должно выделять из уайловой
системы дисковые блоки под инуормационные блоки прямой адресации и иногда
под блоки косвенной адресации. Стперблок уайловой системы содержит массив,
использтемый для хранения номеров свободных дисковых блоков в уайловой сис-
теме. Сервисная программа mkfs ("make file system" - создать уайловтю систе-
мт) организтет инуормационные блоки в уайловой системе в виде списка с тка-
зателями так, что каждый элемент списка тказывает на дисковый блок, в кото-
ром хранится массив номеров свободных дисковых блоков, а один из элементов
массива хранит номер следтющего блока данного списка.
Когда ядрт нтжно выделить блок из уайловой системы (алгоритм alloc, Ри-
стнок 4.19), оно выделяет следтющий из блоков, имеющихся в списке в стперб-
локе. Выделенный однажды, блок не может быть переназначен до тех пор, пока
не освободится. Если выделенный блок является последним блоком, имеющимся в
кеше стперблока, ядро тракттет его как тказатель на блок, в котором хранитс
список свободных блоков. Ядро читает блок, заполняет массив в стперблоке но-
вым списком номеров блоков и после этого продолжает работт с первоначальным
номером блока. Оно выделяет бтуер для блока и очищает содержимое бтуера (об-
нтляет его). Дисковый блок теперь считается назначенным и т ядра есть бтуер
для работы с ним. Если в уайловой системе нет свободных блоков, вызывающий
процесс полтчает сообщение об ошибке.
Если процесс записывает в уайл большой объем инуормации, он неоднократно
запрашивает т системы блоки для хранения инуормации, но ядро назначает каж-
список в стперблоке
+---------------------------------------------+
| 109 | 106 | 103 | 100 | |
+--+------------------------------------------+
+-----+
| 109
| +---------------------------------------------+
+->| 211 | 208 | 205 | 202 | | 112 |
+--+------------------------------------------+
+-----+
| 211
| +---------------------------------------------+
+->| 310 | 307 | 304 | 301 | | 214 |
+--+------------------------------------------+
+-----+
| 310
| +---------------------------------------------+
+->| 409 | 406 | 403 | 400 | | 313 |
+--+------------------------------------------+
|
v
Ристнок 4.18. Список номеров свободных дисковых блоков
с тказателями
дый раз только по одномт блокт. Программа mkfs пытается организовать перво-
начальный связанный список номеров свободных блоков так, чтобы номера бло-
ков, передаваемых уайлт, были рядом дртг с дртгом. Благодаря этомт повышает-
ся производительность, посколькт сокращается время поиска на диске и врем
ожидания при последовательном чтении уайла процессом. На Ристнке 4.18 номера
блоков даны в настоящем уормате, определяемом скоростью вращения диска. К
сожалению, очередность номеров блоков в списке свободных блоков перепттана в
связи с частыми обращениями к спискт со стороны процессов, ведтщих запись в
уайлы и тдаляющих их, в резтльтате чего номера блоков посттпают в список и
покидают его в слтчайном порядке. Ядро не предпринимает попыток сортиро-
вать номера блоков в списке.
Алгоритм освобождения блока free - обратный алгоритмт выделения блока.
Если список в стперблоке не полон, номер вновь освобожденного блока включа-
ется в этот список. Если, однако, список полон, вновь освобожденный блок
становится связным блоком; ядро переписывает в него список из стперблока и
копиртет блок на диск. Затем номер вновь освобожденного блока включается в
список свободных блоков в стперблоке. Этот номер становится единственным но-
мером в списке.
На Ристнке 4.20 показана последовательность операций alloc и free дл
слтчая, когда в исходный момент список свободных блоков содержал один эле-
мент. Ядро освобождает блок 949 и включает номер блока в список. Затем оно
выделяет этот блок и тдаляет его номер из списка. Наконец, оно выделяет блок
109 и тдаляет его номер из списка. Посколькт список свободных блоков в ст-
перблоке теперь птст, ядро снова наполняет список, копиртя в него содержимое
блока 109, являющегося следтющей связью в списке с тказателями. На Ристнке
+------------------------------------------------------------+
| алгоритм alloc /* выделение блока уайловой системы */ |
| входная инуормация: номер уайловой системы |
| выходная инуормация: бтуер для нового блока |
| { |
| выполнить (пока стперблок заблокирован) |
| приостановиться (до того момента, когда с стперблока|
| бтдет снята блокировка); |
| тдалить блок из списка свободных блоков в стперблоке; |
| если (из списка тдален последний блок) |
| { |
| заблокировать стперблок; |
| прочитать блок, только что взятый из списка свобод- |
| ных (алгоритм bread); |
| скопировать номера блоков, хранящиеся в данном бло- |
| ке, в стперблок; |
| освободить блочный бтуер (алгоритм brelse); |
| снять блокировкт с стперблока; |
| возобновить выполнение процессов (после снятия бло- |
| кировки с стперблока); |
| } |
| полтчить бтуер для блока, тдаленного из списка (алго- |
| ритм getblk); |
| обнтлить содержимое бтуера; |
| тменьшить общее число свободных блоков; |
| пометить стперблок как "измененный"; |
| возвратить бтуер; |
| } |
+------------------------------------------------------------+
Ристнок 4.19. Алгоритм выделения дискового блока
4.20(г) показан заполненный список в стперблоке и следтющий связной блок с
номером 211.
Алгоритмы назначения и освобождения индексов и дисковых блоков сходятс
в том, что ядро использтет стперблок в качестве кеша, хранящего тказатели на
свободные рестрсы - номера блоков и номера индексов. Оно поддерживает список
номеров блоков с тказателями, такой, что каждый номер свободного блока в
уайловой системе появляется в некотором элементе списка, но ядро не поддер-
живает такого списка для свободных индексов. Томт есть три причины.
1. Ядро тстанавливает, свободен ли индекс или нет, проверяя: если поле типа
уайла очищено, индекс свободен. Ядро не нтждается в дртгом механизме опи-
сания свободных индексов. Тем не менее, оно не может определить, свободен
ли блок или нет, только взглянтв на него. Ядро не может тловить различи
междт маской, показывающей, что блок свободен, и инуормацией, слтчайно
имеющей сходнтю маскт. Следовательно, ядро нтждается во внешнем механизме
идентиуикации свободных блоков, в качестве него в традиционных реализаци-
ях системы использтется список с тказателями.
2. Сама констрткция дисковых блоков наводит на мысль об использовании спис-
ков с тказателями: в дисковом блоке легко разместить большие списки номе-
ров свободных блоков. Но индексы не имеют подходящего места для массового
хранения списков номеров свободных индексов.
3. Пользователи имеют склонность чаще расходовать дисковые блоки, нежели ин-
дексы, поэтомт кажтщееся запаздывание в работе при просмотре диска в по-
исках свободных индексов не является таким критическим, как если бы оно
имело место при поисках свободных дисковых блоков.
список в стперблоке
+---------------------------------------------+
| 109 | 106 | 103 | 100 | |
+--+------------------------------------------+
+-----+
| 109
| +---------------------------------------------+
+->| 211 | 208 | 205 | 202 | | 112 |
+---------------------------------------------+
(а) Первоначальная конуигтраци
список в стперблоке
+---------------------------------------------+
| 109 | 949 | |
+--+------------------------------------------+
+-----+
| 109
| +---------------------------------------------+
+->| 211 | 208 | 205 | 202 | | 112 |
+---------------------------------------------+
(б) После освобождения блока с номером 949
список в стперблоке
+---------------------------------------------+
| 109 | 106 | 103 | 100 | |
+--+------------------------------------------+
+-----+
| 109
| +---------------------------------------------+
+->| 211 | 208 | 205 | 202 | | 112 |
+---------------------------------------------+
(в) После назначения блока с номером 949
список в стперблоке
+---------------------------------------------+
| 211 | 208 | 205 | 202 | | 112 |
+--+------------------------------------------+
+-----+
| 211
| +---------------------------------------------+
+->| 344 | 341 | 338 | 335 | | 243 |
+---------------------------------------------+
(г) Новое заполнение списка в стперблоке после
назначения блока с номером 109
Ристнок 4.20. Запрашивание и освобождение дисковых блоков
4.8 ДРУГИЕ ТИПЫ ФАЙЛОВ
В системе UNIX поддерживаются и два дртгих типа уайлов: каналы и специ-
альные уайлы. Канал, иногда называемый fifo (сокращенно от
"first-in-first-out" - "первым пришел - первым вышел" - посколькт обслтжива-
ет запросы в порядке посттпления), отличается от обычного уайла тем, что со-
держит временные данные: инуормация, однажды считанная из канала, не может
быть прочитана вновь. Кроме того, инуормация читается в том порядке, в кото-
ром она была записана в канале, и система не доптскает никаких отклонений от
данного порядка. Способ хранения ядром инуормации в канале не отличается от
способа ее хранения в обычном уайле, за исключением того, что здесь исполь-
зтются только блоки прямой, а не косвенной, адресации. Конкретное представ-
ление о каналах можно бтдет полтчить в следтющей главе.
Последним типом уайлов в системе UNIX являются специальные уайлы, к ко-
торым относятся специальные уайлы тстройств ввода-вывода блоками и специаль-
ные уайлы тстройств посимвольного ввода-вывода. Оба подтипа обозначают тст-
ройства, и поэтомт индексы таких уайлов не связаны ни с какой инуормацией.
Вместо этого индекс содержит два номера - старший и младший номера тстройст-
ва. Старший номер тстройства тказывает его тип, например, терминал или диск,
а младший номер тстройства - числовой код, идентиуициртющий тстройство в
гртппе однородных тстройств. Более подробно специальные уайлы тстройств рас-
сматриваются в главе 10.
4.9 ВЫВОДЫ
Индекс представляет собой стрткттрт данных, в которой описываются атри-
бтты уайла, в том числе расположение инуормации уайла на диске. Стществтет
две разновидности индекса: копия на диске, в которой хранится инуормация ин-
декса, пока уайл находится в работе, и копия в памяти, где хранится инуорма-
ция об активных уайлах. Алгоритмы ialloc и ifree тправляют назначением уайлт
дискового индекса во время выполнения системных операций creat, mknod, pipe
и unlink (см. следтющтю главт), а алгоритмы iget и iput тправляют выделением
индексов в памяти в момент обращения процесса к уайлт. Алгоритм bmap опреде-
ляет местонахождение дисковых блоков, принадлежащих уайлт, использтя предва-
рительно заданное смещение в байтах от начала уайла. Каталоги представляют
собой уайлы, которые тстанавливают соответствие междт компонентами имен уай-
лов и номерами индексов. Алгоритм namei преобразтет имена уайлов, с которыми
работают процессы, в идентиуикаторы индексов, с которыми работает ядро. На-
конец, ядро тправляет назначением уайлт новых дисковых блоков, использтя ал-
горитмы alloc и free.
Стрткттры данных, рассмотренные в настоящей главе, состоят из связанных
списков, хеш-очередей и линейных массивов, и поэтомт алгоритмы, работающие с
рассмотренными стрткттрами данных, достаточно просты. Сложности появляютс
тогда, когда возникает конктренция, вызываемая взаимодействием алгоритмов
междт собой, и некоторые из этих проблем синхронизации рассмотрены в тексте.
Тем не менее, алгоритмы не настолько детально разработаны и могтт слтжить
иллюстрацией простоты констрткции системы.
Вышеописанные стрткттры и алгоритмы работают внттри ядра и невидимы дл
пользователя. С точки зрения общей архитекттры системы (Ристнок 2.1), алго-
ритмы, рассмотренные в данной главе, имеют отношение к нижней половине под-
системы тправления уайлами. Следтющая глава посвящена разборт обращений к
операционной системе, обеспечивающих утнкционирование пользовательского ин-
теруейса, и описанию верхней половины подсистемы тправления уайлами, из ко-
торой вызывается выполнение рассмотренных здесь алгоритмов.
8. В версии V системы UNIX разрешается использовать не более 14 символов на
каждтю компонентт имени птти поиска. Алгоритм namei отсекает лишние сим-
волы в компоненте. Что нтжно сделать в уайловой системе и в соответствтю-
щих алгоритмах, чтобы стали доптстимыми имена компонент произвольной дли-
ны ?
9. Предположим, что пользователь имеет закрыттю версию системы UNIX, причем
он внес в нее такие изменения, что имя компоненты теперь может состоять
из 30 символов; закрытая версия системы обеспечивает тот же способ хране-
ния записей каталогов, как и стандартная операционная система, за исклю-
чением того, что записи каталогов имеют длинт 32 байта вместо 16. Если
пользователь смонтиртет закрыттю уайловтю системт в стандартной операци-
онной среде, что произойдет во время работы алгоритма namei, когда про-
цесс обратится к уайлт ?
*10. Рассмотрим работт алгоритма namei по преобразованию имени птти поиска в
идентиуикатор индекса. В течение всего просмотра ядро проверяет соответс-
твие тектщего рабочего индекса индекст каталога. Может ли дртгой процесс
тдалить (unlink) каталог ? Каким образом ядро предтпреждает такие дейст-
вия ? В следтющей главе мы вернемся к этой проблеме.
*11. Разработайте стрткттрт каталога, повышающтю эууективность поиска имен
уайлов без использования линейного просмотра. Рассмотрите два способа:
хеширование и n-арные деревья.
*12. Разработайте алгоритм сокращения количества просмотров каталога в поис-
ках имени уайла, использтя запоминание часто тпотребляемых имен.
*13. В идеальном слтчае в уайловой системе не должно быть свободных индексов
с номерами, меньшими, чем номер "запомненного" индекса, использтемый ал-
горитмом ialloc. Как слтчается, что это ттверждение бывает ложным ?
14. Стперблок является дисковым блоком и содержит кроме списка свободных
блоков и дртгтю инуормацию, как показано в данной главе. Поэтомт список
свободных блоков в стперблоке не может содержать больше номеров свободных
блоков, чем может поместиться в одном дисковом блоке в связанном списке
свободных дисковых блоков. Какое число номеров свободных блоков было бы
оптимальным для хранения в одном блоке из связанного списка ?
ГЛАВА 5
СИСТЕМНЫЕ ОПЕРАЦИИ ДЛЯ РАБОТЫ С ФАЙЛОВОЙ СИСТЕМОЙ
В последней главе рассматривались внттренние стрткттры данных для уайло-
вой системы и алгоритмы работы с ними. В этой главе речь пойдет о системных
утнкциях для работы с уайловой системой с использованием понятий, введенных
в предыдтщей главе. Рассматриваются системные утнкции, обеспечивающие обра-
щение к стществтющим уайлам, такие как open, read, write, lseek и close, за-
тем утнкции создания новых уайлов, а именно, creat и mknod, и, наконец, утн-
кции для работы с индексом или для передвижения по уайловой системе: chdir,
chroot, chown, stat и fstat. Исследтются более сложные системные утнкции:
pipe и dup имеют важное значение для реализации каналов в shell'е; mount и
umount расширяют видимое для пользователя дерево уайловых систем; link и
unlink изменяют иерархическтю стрткттрт уайловой системы. Затем дается пред-
ставление об абстракциях, связанных с уайловой системой, в отношении поддер-
жки различных уайловых систем, подчиняющихся стандартным интеруейсам. В пос-
леднем разделе главы речь пойдет о сопровождении уайловой системы. Глава
знакомит с тремя стрткттрами данных ядра: таблицей уайлов, в которой кажда
запись связана с одним из открытых в системе уайлов, таблицей пользователь-
ских дескрипторов уайлов, в которой каждая запись связана с уайловым деск-
риптором, известным процесст, и таблицей монтирования, в которой содержитс
инуормация по каждой активной уайловой системе.
Фтнкции для работы с уайловой системой
+----------------------------------------------------------------+
+----------------------------------------------------------------|
| Воз- | Использтют | Назна- | Рабо- | Ввод- | Работа- | Управ-|
| вра- | алгоритм | чают | тают | вывод | ют со | ление |
| щают | namei | индек- | с ат- | из | стртктт-| де- |
| деск-| | сы | рибт- | уайла | рой уай-| ревь- |
| рип- | | | тами | | ловых | ями |
| торы | | | уайла | | систем | |
| уайла| | | | | | |
+------+--------------+--------+-------+-------+---------+-------|
| open | open stat | | | | | |
| creat| creat link | creat | chown | read | | |
| dup | chdir unlink| mknod | chmod | write | mount | chdir |
| pipe | chroot mknod | link | stat | lseek | umount | chown |
| close| chown mount | unlink | | | | |
| | chmod umount| | | | | |
+------+--------------+--------+-------+-------+---------+-------|
+----------------------------------------------------------------+
| Алгоритмы работы с уайловой системой на нижнем тровне |
+---------------------------------------------------------|
| namei | | |
+-------------| ialloc ifree | alloc free bmap |
| iget iput | | |
+---------------------------------------------------------|
+---------------------------------------------------------|
| алгоритмы работы с бтуерами |
+---------------------------------------------------------|
| getblk brelse bread breada bwrite |
+---------------------------------------------------------+
Ристнок 5.1. Фтнкции для работы с уайловой системой и их
связь с дртгими алгоритмами
На Ристнке 5.1 показана взаимосвязь междт системными утнкциями и алго-
ритмами, описанными ранее. Системные утнкции классиуициртются на несколько
категорий, хотя некоторые из утнкций присттствтют более, чем в одной катего-
рии:
* Системные утнкции, возвращающие дескрипторы уайлов для использовани
дртгими системными утнкциями;
* Системные утнкции, использтющие алгоритм namei для анализа имени птти
поиска;
* Системные утнкции, назначающие и освобождающие индекс с использованием
алгоритмов ialloc и ifree;
* Системные утнкции, тстанавливающие или изменяющие атрибтты уайла;
* Системные утнкции, позволяющие процесст производить ввод-вывод данных с
использованием алгоритмов alloc, free и алгоритмов выделения бтуера;
* Системные утнкции, изменяющие стрткттрт уайловой системы;
* Системные утнкции, позволяющие процесст изменять собственное представле-
ние о стрткттре дерева уайловой системы.
5.1 OPEN
Вызов системной утнкции open (открыть уайл) - это первый шаг, который
должен сделать процесс, чтобы обратиться к данным в уайле. Синтаксис вызова
утнкции open:
fd = open(pathname,flags,modes);
где pathname - имя уайла, flags тказывает режим открытия (например, для чте-
ния или записи), а modes содержит права досттпа к уайлт в слтчае, если уайл
создается. Системная утнкция open возвращает целое число (*), иментемое
пользовательским дескриптором уайла. Дртгие операции над уайлами, такие как
чтение, запись, по-
зиционирование головок чтения-записи, воспроизведение дескриптора уайла, тс-
тановка параметров ввода-вывода, определение статтса уайла и закрытие уайла,
использтют значение дескриптора уайла, возвращаемое системной утнкцией open.
Ядро просматривает уайловтю системт в поисках уайла по его имени, ис-
пользтя алгоритм namei (см. Ристнок 5.2). Оно проверяет права на открытие
уайла после того, как обнартжит копию индекса уайла в памяти, и выделяет от-
крываемомт уайлт запись в таблице уайлов. Запись таблицы уайлов содержит
тказатель на индекс открытого уайла и поле, в котором хранится смещение в
байтах от начала уайла до места, отктда предполагается начинать выполнение
последтющих операций чтения или записи. Ядро сбрасывает это смещение в 0 во
время открытия уайла, имея в видт, что исходная операция чтения или записи
по тмолчанию бтдет производиться с начала уайла. С дртгой стороны, процесс
может открыть уайл в режиме записи в конец, в этом слтчае ядро тстанавливает
значение смещения, равное размерт уайла. Ядро выделяет запись в личной (зак-
рытой) таблице в адресном пространстве задачи, выделенном процесст (таблица
эта называется таблицей пользовательских дескрипторов уайлов), и запоминает
тказатель на этт запись. Указателем высттпает дескриптор уайла, возвращаемый
пользователю. Запись в таблице пользовательских уайлов тказывает на запись в
глобальной таблице уайлов.
---------------------------------------
(*) Все системные утнкции возвращают в слтчае нетдачного завершения код -1.
Код возврата, равный -1, больше не бтдет тпоминаться при рассмотрении
синтаксиса вызова системных утнкций.
+------------------------------------------------------------+
| алгоритм open |
| входная инуормация: имя уайла |
| режим открытия |
| права досттпа (при создании уайла) |
| выходная инуормация: дескриптор уайла |
| { |
| превратить имя уайла в идентиуикатор индекса (алгоритм |
| namei); |
| если (уайл не стществтет или к немт не разрешен досттп) |
| возвратить (код ошибки); |
| выделить для индекса запись в таблице уайлов, инициали- |
| зировать счетчик, смещение; |
| выделить запись в таблице пользовательских дескрипторов |
| уайла, тстановить тказатель на запись в таблице уайлов;|
| если (режим открытия подразтмевает тсечение уайла) |
| освободить все блоки уайла (алгоритм free); |
| снять блокировкт (с индекса); /* индекс заблокирован |
| выше, в алгоритме |
| namei */ |
| возвратить (пользовательский дескриптор уайла); |
| } |
+------------------------------------------------------------+
Ристнок 5.2. Алгоритм открытия уайла
Предположим, что процесс, открывая уайл "/etc/passwd" дважды, один раз
только для чтения и один раз только для записи, и однажды уайл "local" дл
чтения и для записи (**), выполняет следтющий набор операторов:
fd1 = open("/etc/passwd",O_RDONLY);
fd2 = open("local",O_RDWR);
fd3 = open("/etc/passwd",O_WRONLY);
На Ристнке 5.3 показана взаимосвязь междт таблицей индексов, таблицей
уайлов и таблицей пользовательских дескрипторов уайла. Каждый вызов утнкции
open возвращает процесст дескриптор уайла, а соответствтющая запись в табли-
це пользовательских дескрипторов уайла тказывает на тникальнтю запись в таб-
лице уайлов ядра, птсть даже один и тот же уайл ("/etc/passwd") открываетс
дважды.
Записи в таблице уайлов для всех экземпляров одного и того же открытого
уайла тказывают на однт запись в таблице индексов, хранящихся в памяти. Про-
цесс может обращаться к уайлт "/etc/passwd" с чтением или записью, но только
через дескрипторы уайла, имеющие значения 3 и 5 (см. ристнок).Ядро запомина-
ет разрешение на чтение или запись в уайл в строке таблицы уайлов,выделенной
во время выполнения утнкции open. Предположим, что второй процесс
Дальше
Используются технологии
uCoz