Страница:
| получить индекс (алгоритм iget); |
| если (индекс после всего этого не свободен) /* !!! */|
| { |
| переписать индекс на диск; |
| освободить индекс (алгоритм iput); |
| продолжить; /* цикл с условием продолжения */ |
| } |
| /* индекс свободен */ |
| инициализировать индекс; |
| переписать индекс на диск; |
| уменьшить счетчик свободных индексов в файловой сис- |
| теме; |
| возвратить (индекс); |
| } |
| } |
+------------------------------------------------------------+
Рисунок 4.12. Алгоритм назначения новых индексов
74
перблоке. Если список номеров индексов в суперблоке не пуст, ядро назначает
номер следующего индекса, выделяет для вновь назначенного дискового индекса
свободный индекс в памяти, используя алгоритм iget (читая индекс с диска,
если необходимо), копирует дисковый индекс в память, инициализирует поля в
индексе и возвращает индекс заблокированным. Затем ядро корректирует диско-
вый индекс, указывая, что к индексу произошло обращение. Ненулевое значение
поля типа файла говорит о том, что дисковый индекс назначен. В простейшем
случае с индексом все в порядке, но в условиях конкуренции делается необхо-
димым проведение дополнительных проверок, на чем мы еще кратко остановимся.
Грубо говоря, конкуренция возникает, когда несколько процессов вносят изме-
нения в общие информационные структуры, так что результат зависит от очеред-
ности выполнения процессов, пусть даже все процессы будут подчиняться прото-
колу блокировки. Здесь предполагается, например, что процесс мог бы получить
уже используемый индекс. Конкуренция связана с проблемой взаимного исключе-
ния, описанной в главе 2, с одним замечанием: различные схемы блокировки ре-
шают проблему взаимного исключения, но не могут сами по себе решить все
проблемы конкуренции.
Если список свободных индексов в суперблоке пуст, ядро просматривает
диск и помещает в суперблок как можно больше номеров свободных индексов. При
этом ядро блок за блоком считывает индексы с диска и наполняет список номе-
ров индексов в суперблоке до отказа, запоминая индекс с номером, наибольшим
среди найденных. Назовем этот индекс "запомненным"; это последний индекс,
записанный в суперблок. В следующий раз, когда ядро будет искать на диске
свободные индексы, оно использует запомненный индекс в качестве стартовой
точки, благодаря чему гарантируется, что ядру не придется зря тратить время
на считывание дисковых блоков, в кото-
рых свободные индексы наверняка отсутствуют. После формирования нового набо-
ра номеров свободных индексов ядро запускает алгоритм назначения индекса с
самого начала. Всякий раз, когда ядро назначает дисковый индекс, оно умень-
шает значение счетчика свободных индексов, записанное в суперблоке.
Рассмотрим две пары массивов номеров свободных индексов (Рисунок 4.13).
Если список свободных индексов в суперблоке имеет вид первого массива на Ри-
сунке 4.13(а) при назначении индекса ядром, то значение указателя на следую-
щий номер индекса уменьшается до 18 и выбирается индекс с номером 48. Если
же список выглядит как первый массив на Рисунке 4.13(б), ядро заметит, что
массив пуст и обратится в поисках свободных индексов к диску, при этом поиск
будет производиться, начиная с индекса с номером 470, который был ранее за-
помнен. Когда ядро заполнит список свободных индексов в суперблоке до отка-
Список свободных индексов в суперблоке
+---------------------+------+------+-------------------+
| свободные индексы | | | пустота |
|<>| 83 | 48 |<>|
+---------------------+------+------+-------------------+
18 19 20 массив 1
^
| указатель
Список свободных индексов в суперблоке
+---------------------+------+------+-------------------+
| свободные индексы | | | пустота |
|<>| 83 | <|>|
+---------------------+------+------+-------------------+
18 19 20 массив 1
^
| указатель
(а) Назначение свободного индекса из середины списка
75
Список свободных индексов в суперблоке
+------+------------------------------------------------+
| 470 | пустота |
|<|>|
+------+------------------------------------------------+
0 массив 1
^
|указатель (запомненный индекс)
Список свободных индексов в суперблоке
+------+------------------------------+-----+-----+-----+
| 535 | свободные индексы | 476 | 475 | 471 |
|<||||>|
+------+------------------------------+-----+-----+-----+
0 48 49 50
^
указатель |
(б) Назначение свободного индекса, когда список в супер-
блоке пуст
Рисунок 4.13. Два массива номеров свободных индексов
за, оно запомнит последний индекс в качестве начальной точки для последующих
просмотров диска. Ядро производит назначение файлу только что выбранного с
диска индекса (под номером 471 на рисунке) и продолжает прерванную обработ-
ку.
+------------------------------------------------------------+
| алгоритм ifree /* освобождение индекса */ |
| входная информация: номер индекса в файловой системе |
| выходная информация: отсутствует |
| { |
| увеличить на 1 счетчик свободных индексов в файловой |
| системе; |
| если (суперблок заблокирован) |
| возвратить управление; |
| если (список индексов заполнен) |
| { |
| если (номер индекса меньше номера индекса, запом- |
| ненного для последующего просмотра) |
| запомнить для последующего просмотра номер |
| введенного индекса; |
| } |
| в противном случае |
| сохранить номер индекса в списке индексов; |
| возвратить управление; |
| } |
+------------------------------------------------------------+
Рисунок 4.14. Алгоритм освобождения индекса
Алгоритм освобождения индекса построен значительно проще. Увеличив на
единицу общее количество доступных в файловой системе индексов, ядро прове-
ряет наличие блокировки у суперблока. Если он заблокирован, ядро, чтобы пре-
дотвратить конкуренцию, немедленно сообщает: номер индекса отсутствует в су-
перблоке, но индекс может быть найден на диске и доступен для переназначе-
76
ния. Если список не заблокирован, ядро проверяет, имеется ли место для новых
номеров индексов и если да, помещает номер индекса в список и выходит из ал-
горитма. Если список полон, ядро не сможет в нем сохранить вновь освобожден-
ный индекс. Оно сравнивает номер освобожденного индекса с номером запомнен-
ного индекса. Если номер освобожденного индекса меньше номера запомненного,
ядро запоминает номер вновь освобожденного индекса, выбрасывая из суперблока
номер старого запомненного индекса. Индекс не теряется, поскольку ядро может
найти его, просматривая список индексов на диске. Ядро поддерживает структу-
ру списка в суперблоке таким образом, что последний номер, выбираемый им из
списка, и есть номер запомненного индекса. В идеале не должно быть свободных
индексов с номерами, мень-
+------+------------------------------+-----+-----+-----+
| 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, содержимое списка свободных индексов не
изменится. Когда позднее ядро использует все индексы из списка свободных ин-
77
дексов в суперблоке, оно обратится в поисках свободных индексов к диску, при
этом, начав просмотр с индекса с номером 499, оно снова обнаружит индексы
535 и 601.
Процесс A Процесс B Процесс C
+------------------------------------------------------------
| Назначает индекс I - -
| из суперблока - -
| - -
| Приостанавливается - -
| на время считывания - -
| индекса (а) - -
| - - -
| - Пытается назначить -
| - индекс из суперблока -
| - -
| - Суперблок пуст (б) -
| - -
| - Просматривает диск в -
| - поисках свободных ин- -
| - дексов, помещение ин- -
| - декса I в суперблок -
| - (в) -
| - - -
| Индекс I в памяти - -
| Выполняются обычные - -
| действия - -
| - - -
| - Заканчивает просмотр, -
| - назначает другой индекс -
| - (г) -
| - - -
| - - Назначает индекс I
| - - из суперблока
| - -
| - - Индекс I уже исполь-
| - - зуется !
| - -
| - - Назначает другой
| - - индекс (д)
| - -
v Время
Рисунок 4.16. Конкуренция в назначении индексов
В предыдущем параграфе описывались простые случаи работы алгоритмов. Те-
перь рассмотрим случай, когда ядро назначает новый индекс и затем копирует
его в память. В алгоритме предполагается, что ядро может и обнаружить, что
индекс уже назначен. Несмотря на редкость такой ситуации, обсудим этот слу-
чай (с помощью Рисунков 4.16 и 4.17). Пусть у нас есть три процесса, A, B и
C, и пусть ядро, действуя от имени процесса A (***), назначает индекс I, но
приостанавливает выполнение процесса перед тем, как скопировать дисковый ин-
декс в память. Алгоритмы iget (вызванный алгоритмом
---------------------------------------
(***) Как и в предыдущей главе, здесь под "процессом" имеется ввиду "ядро,
действующее от имени процесса".
78
|Время
| +---+---+---+--------------------------------+
| (а) | | | | |
| | | | 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 снижает
опасность конкуренции, поскольку поле типа файла будет содержать пометку о
том, что индекс использован.
Блокировка списка индексов в суперблоке при чтении с диска устраняет
другие возможности для конкуренции. Если суперблок не заблокирован, процесс
может обнаружить, что он пуст, и попытаться заполнить его с диска, время от
времени приостанавливая свое выполнение до завершения операции ввода-вывода.
Предположим, что второй процесс так же пытается назначить новый индекс и об-
наруживает, что список пуст. Он тоже попытается заполнить список с диска. В
лучшем случае, оба процесса продублируют друг друга и потратят энергию цент-
рального процессора. В худшем, участится конкуренция, подобная той, которая
79
описана в предыдущем параграфе. Сходным образом, если процесс, освобождая
индекс, не проверил наличие блокировки списка, он может затереть номера ин-
дексов уже в списке свободных индексов, пока другой процесс будет заполнять
этот список информацией с диска. И опять участится конкуренция вышеописанно-
го типа. Несмотря на то, что ядро более или менее удачно управляется с ней,
производительность системы снижается. Установка блокировки для списка сво-
бодных индексов в суперблоке устраняет такую конкуренцию.
Когда процесс записывает данные в файл, ядро должно выделять из файловой
системы дисковые блоки под информационные блоки прямой адресации и иногда
под блоки косвенной адресации. Суперблок файловой системы содержит массив,
используемый для хранения номеров свободных дисковых блоков в файловой сис-
теме. Сервисная программа 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. Список номеров свободных дисковых блоков
с указателями
80
дый раз только по одному блоку. Программа mkfs пытается организовать перво-
начальный связанный список номеров свободных блоков так, чтобы номера бло-
ков, передаваемых файлу, были рядом друг с другом. Благодаря этому повышает-
ся производительность, поскольку сокращается время поиска на диске и время
ожидания при последовательном чтении файла процессом. На Рисунке 4.18 номера
блоков даны в настоящем формате, определяемом скоростью вращения диска. К
сожалению, очередность номеров блоков в списке свободных блоков перепутана в
связи с частыми обращениями к списку со стороны процессов, ведущих запись в
файлы и удаляющих их, в результате чего номера блоков поступают в список и
покидают его в случайном порядке. Ядро не предпринимает попыток сортиро-
вать номера блоков в списке.
Алгоритм освобождения блока free - обратный алгоритму выделения блока.
Если список в суперблоке не полон, номер вновь освобожденного блока включа-
ется в этот список. Если, однако, список полон, вновь освобожденный блок
становится связным блоком; ядро переписывает в него список из суперблока и
копирует блок на диск. Затем номер вновь освобожденного блока включается в
список свободных блоков в суперблоке. Этот номер становится единственным но-
мером в списке.
На Рисунке 4.20 показана последовательность операций alloc и free для
случая, когда в исходный момент список свободных блоков содержал один эле-
мент. Ядро освобождает блок 949 и включает номер блока в список. Затем оно
выделяет этот блок и удаляет его номер из списка. Наконец, оно выделяет блок
109 и удаляет его номер из списка. Поскольку список свободных блоков в су-
перблоке теперь пуст, ядро снова наполняет список, копируя в него содержимое
блока 109, являющегося следующей связью в списке с указателями. На Рисунке
+------------------------------------------------------------+
| алгоритм alloc /* выделение блока файловой системы */ |
| входная информация: номер файловой системы |
| выходная информация: буфер для нового блока |
| { |
| выполнить (пока суперблок заблокирован) |
| приостановиться (до того момента, когда с суперблока|
| будет снята блокировка); |
| удалить блок из списка свободных блоков в суперблоке; |
| если (из списка удален последний блок) |
| { |
| заблокировать суперблок; |
| прочитать блок, только что взятый из списка свобод- |
| ных (алгоритм bread); |
| скопировать номера блоков, хранящиеся в данном бло- |
| ке, в суперблок; |
| освободить блочный буфер (алгоритм brelse); |
| снять блокировку с суперблока; |
| возобновить выполнение процессов (после снятия бло- |
| кировки с суперблока); |
| } |
| получить буфер для блока, удаленного из списка (алго- |
| ритм getblk); |
| обнулить содержимое буфера; |
| уменьшить общее число свободных блоков; |
| пометить суперблок как "измененный"; |
| возвратить буфер; |
| } |
+------------------------------------------------------------+
Рисунок 4.19. Алгоритм выделения дискового блока
81
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
82
список в суперблоке
+-----+-----+-----+-----+---------------+-----+
| 211 | 208 | 205 | 202 | ------------- | 112 |
+--+--+-----+-----+-----+---------------+-----+
+-----+
| 211
| +-----+-----+-----+-----+---------------+-----+
+->| 344 | 341 | 338 | 335 | ------------- | 243 |
+-----+-----+-----+-----+---------------+-----+
(г) Новое заполнение списка в суперблоке после
назначения блока с номером 109
Рисунок 4.20. Запрашивание и освобождение дисковых блоков
В системе UNIX поддерживаются и два других типа файлов: каналы и специ-
альные файлы. Канал, иногда называемый fifo (сокращенно от
"first-in-first-out" - "первым пришел - первым вышел" - поскольку обслужива-
ет запросы в порядке поступления), отличается от обычного файла тем, что со-
держит временные данные: информация, однажды считанная из канала, не может
быть прочитана вновь. Кроме того, информация читается в том порядке, в кото-
ром она была записана в канале, и система не допускает никаких отклонений от
данного порядка. Способ хранения ядром информации в канале не отличается от
способа ее хранения в обычном файле, за исключением того, что здесь исполь-
зуются только блоки прямой, а не косвенной, адресации. Конкретное представ-
ление о каналах можно будет получить в следующей главе.
Последним типом файлов в системе UNIX являются специальные файлы, к ко-
торым относятся специальные файлы устройств ввода-вывода блоками и специаль-
ные файлы устройств посимвольного ввода-вывода. Оба подтипа обозначают уст-
ройства, и поэтому индексы таких файлов не связаны ни с какой информацией.
Вместо этого индекс содержит два номера - старший и младший номера устройст-
ва. Старший номер устройства указывает его тип, например, терминал или диск,
а младший номер устройства - числовой код, идентифицирующий устройство в
группе однородных устройств. Более подробно специальные файлы устройств рас-
сматриваются в главе 10.
Индекс представляет собой структуру данных, в которой описываются атри-
буты файла, в том числе расположение информации файла на диске. Существует
две разновидности индекса: копия на диске, в которой хранится информация ин-
декса, пока файл находится в работе, и копия в памяти, где хранится информа-
ция об активных файлах. Алгоритмы ialloc и ifree управляют назначением файлу
дискового индекса во время выполнения системных операций creat, mknod, pipe
и unlink (см. следующую главу), а алгоритмы iget и iput управляют выделением
индексов в памяти в момент обращения процесса к файлу. Алгоритм bmap опреде-
ляет местонахождение дисковых блоков, принадлежащих файлу, используя предва-
рительно заданное смещение в байтах от начала файла. Каталоги представляют
собой файлы, которые устанавливают соответствие между компонентами имен фай-
лов и номерами индексов. Алгоритм namei преобразует имена файлов, с которыми
работают процессы, в идентификаторы индексов, с которыми работает ядро. На-
конец, ядро управляет назначением файлу новых дисковых блоков, используя ал-
горитмы alloc и free.
83
Структуры данных, рассмотренные в настоящей главе, состоят из связанных
списков, хеш-очередей и линейных массивов, и поэтому алгоритмы, работающие с
рассмотренными структурами данных, достаточно просты. Сложности появляются
тогда, когда возникает конкуренция, вызываемая взаимодействием алгоритмов
между собой, и некоторые из этих проблем синхронизации рассмотрены в тексте.
Тем не менее, алгоритмы не настолько детально разработаны и могут служить
иллюстрацией простоты конструкции системы.
Вышеописанные структуры и алгоритмы работают внутри ядра и невидимы для
пользователя. С точки зрения общей архитектуры системы (Рисунок 2.1), алго-
ритмы, рассмотренные в данной главе, имеют отношение к нижней половине под-
системы управления файлами. Следующая глава посвящена разбору обращений к
операционной системе, обеспечивающих функционирование пользовательского ин-
терфейса, и описанию верхней половины подсистемы управления файлами, из ко-
торой вызывается выполнение рассмотренных здесь алгоритмов.
8. В версии V системы UNIX разрешается использовать не более 14 символов на
каждую компоненту имени пути поиска. Алгоритм namei отсекает лишние сим-
волы в компоненте. Что нужно сделать в файловой системе и в соответствую-
щих алгоритмах, чтобы стали допустимыми имена компонент произвольной дли-
ны ?
9. Предположим, что пользователь имеет закрытую версию системы UNIX, причем
он внес в нее такие изменения, что имя компоненты теперь может состоять
из 30 символов; закрытая версия системы обеспечивает тот же способ хране-
ния записей каталогов, как и стандартная операционная система, за исклю-
чением того, что записи каталогов имеют длину 32 байта вместо 16. Если
пользователь смонтирует закрытую файловую систему в стандартной операци-
онной среде, что произойдет во время работы алгоритма namei, когда про-
цесс обратится к файлу ?
*10. Рассмотрим работу алгоритма namei по преобразованию имени пути поиска в
идентификатор индекса. В течение всего просмотра ядро проверяет соответс-
твие текущего рабочего индекса индексу каталога. Может ли другой процесс
удалить (unlink) каталог ? Каким образом ядро предупреждает такие дейст-
вия ? В следующей главе мы вернемся к этой проблеме.
*11. Разработайте структуру каталога, повышающую эффективность поиска имен
файлов без использования линейного просмотра. Рассмотрите два способа:
хеширование и n-арные деревья.
*12. Разработайте алгоритм сокращения количества просмотров каталога в поис-
ках имени файла, используя запоминание часто употребляемых имен.
*13. В идеальном случае в файловой системе не должно быть свободных индексов
с номерами, меньшими, чем номер "запомненного" индекса, используемый ал-
горитмом ialloc. Как случается, что это утверждение бывает ложным ?
14. Суперблок является дисковым блоком и содержит кроме списка свободных
блоков и другую информацию, как показано в данной главе. Поэтому список
свободных блоков в суперблоке не может содержать больше номеров свободных
блоков, чем может поместиться в одном дисковом блоке в связанном списке
свободных дисковых блоков. Какое число номеров свободных блоков было бы
оптимальным для хранения в одном блоке из связанного списка ?
84
| если (индекс после всего этого не свободен) /* !!! */|
| { |
| переписать индекс на диск; |
| освободить индекс (алгоритм iput); |
| продолжить; /* цикл с условием продолжения */ |
| } |
| /* индекс свободен */ |
| инициализировать индекс; |
| переписать индекс на диск; |
| уменьшить счетчик свободных индексов в файловой сис- |
| теме; |
| возвратить (индекс); |
| } |
| } |
+------------------------------------------------------------+
Рисунок 4.12. Алгоритм назначения новых индексов
74
перблоке. Если список номеров индексов в суперблоке не пуст, ядро назначает
номер следующего индекса, выделяет для вновь назначенного дискового индекса
свободный индекс в памяти, используя алгоритм iget (читая индекс с диска,
если необходимо), копирует дисковый индекс в память, инициализирует поля в
индексе и возвращает индекс заблокированным. Затем ядро корректирует диско-
вый индекс, указывая, что к индексу произошло обращение. Ненулевое значение
поля типа файла говорит о том, что дисковый индекс назначен. В простейшем
случае с индексом все в порядке, но в условиях конкуренции делается необхо-
димым проведение дополнительных проверок, на чем мы еще кратко остановимся.
Грубо говоря, конкуренция возникает, когда несколько процессов вносят изме-
нения в общие информационные структуры, так что результат зависит от очеред-
ности выполнения процессов, пусть даже все процессы будут подчиняться прото-
колу блокировки. Здесь предполагается, например, что процесс мог бы получить
уже используемый индекс. Конкуренция связана с проблемой взаимного исключе-
ния, описанной в главе 2, с одним замечанием: различные схемы блокировки ре-
шают проблему взаимного исключения, но не могут сами по себе решить все
проблемы конкуренции.
Если список свободных индексов в суперблоке пуст, ядро просматривает
диск и помещает в суперблок как можно больше номеров свободных индексов. При
этом ядро блок за блоком считывает индексы с диска и наполняет список номе-
ров индексов в суперблоке до отказа, запоминая индекс с номером, наибольшим
среди найденных. Назовем этот индекс "запомненным"; это последний индекс,
записанный в суперблок. В следующий раз, когда ядро будет искать на диске
свободные индексы, оно использует запомненный индекс в качестве стартовой
точки, благодаря чему гарантируется, что ядру не придется зря тратить время
на считывание дисковых блоков, в кото-
рых свободные индексы наверняка отсутствуют. После формирования нового набо-
ра номеров свободных индексов ядро запускает алгоритм назначения индекса с
самого начала. Всякий раз, когда ядро назначает дисковый индекс, оно умень-
шает значение счетчика свободных индексов, записанное в суперблоке.
Рассмотрим две пары массивов номеров свободных индексов (Рисунок 4.13).
Если список свободных индексов в суперблоке имеет вид первого массива на Ри-
сунке 4.13(а) при назначении индекса ядром, то значение указателя на следую-
щий номер индекса уменьшается до 18 и выбирается индекс с номером 48. Если
же список выглядит как первый массив на Рисунке 4.13(б), ядро заметит, что
массив пуст и обратится в поисках свободных индексов к диску, при этом поиск
будет производиться, начиная с индекса с номером 470, который был ранее за-
помнен. Когда ядро заполнит список свободных индексов в суперблоке до отка-
Список свободных индексов в суперблоке
+---------------------+------+------+-------------------+
| свободные индексы | | | пустота |
|<>| 83 | 48 |<>|
+---------------------+------+------+-------------------+
18 19 20 массив 1
^
| указатель
Список свободных индексов в суперблоке
+---------------------+------+------+-------------------+
| свободные индексы | | | пустота |
|<>| 83 | <|>|
+---------------------+------+------+-------------------+
18 19 20 массив 1
^
| указатель
(а) Назначение свободного индекса из середины списка
75
Список свободных индексов в суперблоке
+------+------------------------------------------------+
| 470 | пустота |
|<|>|
+------+------------------------------------------------+
0 массив 1
^
|указатель (запомненный индекс)
Список свободных индексов в суперблоке
+------+------------------------------+-----+-----+-----+
| 535 | свободные индексы | 476 | 475 | 471 |
|<||||>|
+------+------------------------------+-----+-----+-----+
0 48 49 50
^
указатель |
(б) Назначение свободного индекса, когда список в супер-
блоке пуст
Рисунок 4.13. Два массива номеров свободных индексов
за, оно запомнит последний индекс в качестве начальной точки для последующих
просмотров диска. Ядро производит назначение файлу только что выбранного с
диска индекса (под номером 471 на рисунке) и продолжает прерванную обработ-
ку.
+------------------------------------------------------------+
| алгоритм ifree /* освобождение индекса */ |
| входная информация: номер индекса в файловой системе |
| выходная информация: отсутствует |
| { |
| увеличить на 1 счетчик свободных индексов в файловой |
| системе; |
| если (суперблок заблокирован) |
| возвратить управление; |
| если (список индексов заполнен) |
| { |
| если (номер индекса меньше номера индекса, запом- |
| ненного для последующего просмотра) |
| запомнить для последующего просмотра номер |
| введенного индекса; |
| } |
| в противном случае |
| сохранить номер индекса в списке индексов; |
| возвратить управление; |
| } |
+------------------------------------------------------------+
Рисунок 4.14. Алгоритм освобождения индекса
Алгоритм освобождения индекса построен значительно проще. Увеличив на
единицу общее количество доступных в файловой системе индексов, ядро прове-
ряет наличие блокировки у суперблока. Если он заблокирован, ядро, чтобы пре-
дотвратить конкуренцию, немедленно сообщает: номер индекса отсутствует в су-
перблоке, но индекс может быть найден на диске и доступен для переназначе-
76
ния. Если список не заблокирован, ядро проверяет, имеется ли место для новых
номеров индексов и если да, помещает номер индекса в список и выходит из ал-
горитма. Если список полон, ядро не сможет в нем сохранить вновь освобожден-
ный индекс. Оно сравнивает номер освобожденного индекса с номером запомнен-
ного индекса. Если номер освобожденного индекса меньше номера запомненного,
ядро запоминает номер вновь освобожденного индекса, выбрасывая из суперблока
номер старого запомненного индекса. Индекс не теряется, поскольку ядро может
найти его, просматривая список индексов на диске. Ядро поддерживает структу-
ру списка в суперблоке таким образом, что последний номер, выбираемый им из
списка, и есть номер запомненного индекса. В идеале не должно быть свободных
индексов с номерами, мень-
+------+------------------------------+-----+-----+-----+
| 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, содержимое списка свободных индексов не
изменится. Когда позднее ядро использует все индексы из списка свободных ин-
77
дексов в суперблоке, оно обратится в поисках свободных индексов к диску, при
этом, начав просмотр с индекса с номером 499, оно снова обнаружит индексы
535 и 601.
Процесс A Процесс B Процесс C
+------------------------------------------------------------
| Назначает индекс I - -
| из суперблока - -
| - -
| Приостанавливается - -
| на время считывания - -
| индекса (а) - -
| - - -
| - Пытается назначить -
| - индекс из суперблока -
| - -
| - Суперблок пуст (б) -
| - -
| - Просматривает диск в -
| - поисках свободных ин- -
| - дексов, помещение ин- -
| - декса I в суперблок -
| - (в) -
| - - -
| Индекс I в памяти - -
| Выполняются обычные - -
| действия - -
| - - -
| - Заканчивает просмотр, -
| - назначает другой индекс -
| - (г) -
| - - -
| - - Назначает индекс I
| - - из суперблока
| - -
| - - Индекс I уже исполь-
| - - зуется !
| - -
| - - Назначает другой
| - - индекс (д)
| - -
v Время
Рисунок 4.16. Конкуренция в назначении индексов
В предыдущем параграфе описывались простые случаи работы алгоритмов. Те-
перь рассмотрим случай, когда ядро назначает новый индекс и затем копирует
его в память. В алгоритме предполагается, что ядро может и обнаружить, что
индекс уже назначен. Несмотря на редкость такой ситуации, обсудим этот слу-
чай (с помощью Рисунков 4.16 и 4.17). Пусть у нас есть три процесса, A, B и
C, и пусть ядро, действуя от имени процесса A (***), назначает индекс I, но
приостанавливает выполнение процесса перед тем, как скопировать дисковый ин-
декс в память. Алгоритмы iget (вызванный алгоритмом
---------------------------------------
(***) Как и в предыдущей главе, здесь под "процессом" имеется ввиду "ядро,
действующее от имени процесса".
78
|Время
| +---+---+---+--------------------------------+
| (а) | | | | |
| | | | 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 снижает
опасность конкуренции, поскольку поле типа файла будет содержать пометку о
том, что индекс использован.
Блокировка списка индексов в суперблоке при чтении с диска устраняет
другие возможности для конкуренции. Если суперблок не заблокирован, процесс
может обнаружить, что он пуст, и попытаться заполнить его с диска, время от
времени приостанавливая свое выполнение до завершения операции ввода-вывода.
Предположим, что второй процесс так же пытается назначить новый индекс и об-
наруживает, что список пуст. Он тоже попытается заполнить список с диска. В
лучшем случае, оба процесса продублируют друг друга и потратят энергию цент-
рального процессора. В худшем, участится конкуренция, подобная той, которая
79
описана в предыдущем параграфе. Сходным образом, если процесс, освобождая
индекс, не проверил наличие блокировки списка, он может затереть номера ин-
дексов уже в списке свободных индексов, пока другой процесс будет заполнять
этот список информацией с диска. И опять участится конкуренция вышеописанно-
го типа. Несмотря на то, что ядро более или менее удачно управляется с ней,
производительность системы снижается. Установка блокировки для списка сво-
бодных индексов в суперблоке устраняет такую конкуренцию.
Когда процесс записывает данные в файл, ядро должно выделять из файловой
системы дисковые блоки под информационные блоки прямой адресации и иногда
под блоки косвенной адресации. Суперблок файловой системы содержит массив,
используемый для хранения номеров свободных дисковых блоков в файловой сис-
теме. Сервисная программа 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. Список номеров свободных дисковых блоков
с указателями
80
дый раз только по одному блоку. Программа mkfs пытается организовать перво-
начальный связанный список номеров свободных блоков так, чтобы номера бло-
ков, передаваемых файлу, были рядом друг с другом. Благодаря этому повышает-
ся производительность, поскольку сокращается время поиска на диске и время
ожидания при последовательном чтении файла процессом. На Рисунке 4.18 номера
блоков даны в настоящем формате, определяемом скоростью вращения диска. К
сожалению, очередность номеров блоков в списке свободных блоков перепутана в
связи с частыми обращениями к списку со стороны процессов, ведущих запись в
файлы и удаляющих их, в результате чего номера блоков поступают в список и
покидают его в случайном порядке. Ядро не предпринимает попыток сортиро-
вать номера блоков в списке.
Алгоритм освобождения блока free - обратный алгоритму выделения блока.
Если список в суперблоке не полон, номер вновь освобожденного блока включа-
ется в этот список. Если, однако, список полон, вновь освобожденный блок
становится связным блоком; ядро переписывает в него список из суперблока и
копирует блок на диск. Затем номер вновь освобожденного блока включается в
список свободных блоков в суперблоке. Этот номер становится единственным но-
мером в списке.
На Рисунке 4.20 показана последовательность операций alloc и free для
случая, когда в исходный момент список свободных блоков содержал один эле-
мент. Ядро освобождает блок 949 и включает номер блока в список. Затем оно
выделяет этот блок и удаляет его номер из списка. Наконец, оно выделяет блок
109 и удаляет его номер из списка. Поскольку список свободных блоков в су-
перблоке теперь пуст, ядро снова наполняет список, копируя в него содержимое
блока 109, являющегося следующей связью в списке с указателями. На Рисунке
+------------------------------------------------------------+
| алгоритм alloc /* выделение блока файловой системы */ |
| входная информация: номер файловой системы |
| выходная информация: буфер для нового блока |
| { |
| выполнить (пока суперблок заблокирован) |
| приостановиться (до того момента, когда с суперблока|
| будет снята блокировка); |
| удалить блок из списка свободных блоков в суперблоке; |
| если (из списка удален последний блок) |
| { |
| заблокировать суперблок; |
| прочитать блок, только что взятый из списка свобод- |
| ных (алгоритм bread); |
| скопировать номера блоков, хранящиеся в данном бло- |
| ке, в суперблок; |
| освободить блочный буфер (алгоритм brelse); |
| снять блокировку с суперблока; |
| возобновить выполнение процессов (после снятия бло- |
| кировки с суперблока); |
| } |
| получить буфер для блока, удаленного из списка (алго- |
| ритм getblk); |
| обнулить содержимое буфера; |
| уменьшить общее число свободных блоков; |
| пометить суперблок как "измененный"; |
| возвратить буфер; |
| } |
+------------------------------------------------------------+
Рисунок 4.19. Алгоритм выделения дискового блока
81
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
82
список в суперблоке
+-----+-----+-----+-----+---------------+-----+
| 211 | 208 | 205 | 202 | ------------- | 112 |
+--+--+-----+-----+-----+---------------+-----+
+-----+
| 211
| +-----+-----+-----+-----+---------------+-----+
+->| 344 | 341 | 338 | 335 | ------------- | 243 |
+-----+-----+-----+-----+---------------+-----+
(г) Новое заполнение списка в суперблоке после
назначения блока с номером 109
Рисунок 4.20. Запрашивание и освобождение дисковых блоков
В системе UNIX поддерживаются и два других типа файлов: каналы и специ-
альные файлы. Канал, иногда называемый fifo (сокращенно от
"first-in-first-out" - "первым пришел - первым вышел" - поскольку обслужива-
ет запросы в порядке поступления), отличается от обычного файла тем, что со-
держит временные данные: информация, однажды считанная из канала, не может
быть прочитана вновь. Кроме того, информация читается в том порядке, в кото-
ром она была записана в канале, и система не допускает никаких отклонений от
данного порядка. Способ хранения ядром информации в канале не отличается от
способа ее хранения в обычном файле, за исключением того, что здесь исполь-
зуются только блоки прямой, а не косвенной, адресации. Конкретное представ-
ление о каналах можно будет получить в следующей главе.
Последним типом файлов в системе UNIX являются специальные файлы, к ко-
торым относятся специальные файлы устройств ввода-вывода блоками и специаль-
ные файлы устройств посимвольного ввода-вывода. Оба подтипа обозначают уст-
ройства, и поэтому индексы таких файлов не связаны ни с какой информацией.
Вместо этого индекс содержит два номера - старший и младший номера устройст-
ва. Старший номер устройства указывает его тип, например, терминал или диск,
а младший номер устройства - числовой код, идентифицирующий устройство в
группе однородных устройств. Более подробно специальные файлы устройств рас-
сматриваются в главе 10.
Индекс представляет собой структуру данных, в которой описываются атри-
буты файла, в том числе расположение информации файла на диске. Существует
две разновидности индекса: копия на диске, в которой хранится информация ин-
декса, пока файл находится в работе, и копия в памяти, где хранится информа-
ция об активных файлах. Алгоритмы ialloc и ifree управляют назначением файлу
дискового индекса во время выполнения системных операций creat, mknod, pipe
и unlink (см. следующую главу), а алгоритмы iget и iput управляют выделением
индексов в памяти в момент обращения процесса к файлу. Алгоритм bmap опреде-
ляет местонахождение дисковых блоков, принадлежащих файлу, используя предва-
рительно заданное смещение в байтах от начала файла. Каталоги представляют
собой файлы, которые устанавливают соответствие между компонентами имен фай-
лов и номерами индексов. Алгоритм namei преобразует имена файлов, с которыми
работают процессы, в идентификаторы индексов, с которыми работает ядро. На-
конец, ядро управляет назначением файлу новых дисковых блоков, используя ал-
горитмы alloc и free.
83
Структуры данных, рассмотренные в настоящей главе, состоят из связанных
списков, хеш-очередей и линейных массивов, и поэтому алгоритмы, работающие с
рассмотренными структурами данных, достаточно просты. Сложности появляются
тогда, когда возникает конкуренция, вызываемая взаимодействием алгоритмов
между собой, и некоторые из этих проблем синхронизации рассмотрены в тексте.
Тем не менее, алгоритмы не настолько детально разработаны и могут служить
иллюстрацией простоты конструкции системы.
Вышеописанные структуры и алгоритмы работают внутри ядра и невидимы для
пользователя. С точки зрения общей архитектуры системы (Рисунок 2.1), алго-
ритмы, рассмотренные в данной главе, имеют отношение к нижней половине под-
системы управления файлами. Следующая глава посвящена разбору обращений к
операционной системе, обеспечивающих функционирование пользовательского ин-
терфейса, и описанию верхней половины подсистемы управления файлами, из ко-
торой вызывается выполнение рассмотренных здесь алгоритмов.
8. В версии V системы UNIX разрешается использовать не более 14 символов на
каждую компоненту имени пути поиска. Алгоритм namei отсекает лишние сим-
волы в компоненте. Что нужно сделать в файловой системе и в соответствую-
щих алгоритмах, чтобы стали допустимыми имена компонент произвольной дли-
ны ?
9. Предположим, что пользователь имеет закрытую версию системы UNIX, причем
он внес в нее такие изменения, что имя компоненты теперь может состоять
из 30 символов; закрытая версия системы обеспечивает тот же способ хране-
ния записей каталогов, как и стандартная операционная система, за исклю-
чением того, что записи каталогов имеют длину 32 байта вместо 16. Если
пользователь смонтирует закрытую файловую систему в стандартной операци-
онной среде, что произойдет во время работы алгоритма namei, когда про-
цесс обратится к файлу ?
*10. Рассмотрим работу алгоритма namei по преобразованию имени пути поиска в
идентификатор индекса. В течение всего просмотра ядро проверяет соответс-
твие текущего рабочего индекса индексу каталога. Может ли другой процесс
удалить (unlink) каталог ? Каким образом ядро предупреждает такие дейст-
вия ? В следующей главе мы вернемся к этой проблеме.
*11. Разработайте структуру каталога, повышающую эффективность поиска имен
файлов без использования линейного просмотра. Рассмотрите два способа:
хеширование и n-арные деревья.
*12. Разработайте алгоритм сокращения количества просмотров каталога в поис-
ках имени файла, используя запоминание часто употребляемых имен.
*13. В идеальном случае в файловой системе не должно быть свободных индексов
с номерами, меньшими, чем номер "запомненного" индекса, используемый ал-
горитмом ialloc. Как случается, что это утверждение бывает ложным ?
14. Суперблок является дисковым блоком и содержит кроме списка свободных
блоков и другую информацию, как показано в данной главе. Поэтому список
свободных блоков в суперблоке не может содержать больше номеров свободных
блоков, чем может поместиться в одном дисковом блоке в связанном списке
свободных дисковых блоков. Какое число номеров свободных блоков было бы
оптимальным для хранения в одном блоке из связанного списка ?
84