4.3 КАТАЛОГИ Из главы 1 напомним, что каталоги являются файлами, из которых строится иерархическая структура файловой системы; они играют важную роль в превраще- нии имени файла в номер индекса. Каталог - это файл, содержимым которого яв- ляется набор записей, состоящих из номера индекса и имени файла, включенного в каталог. Составное имя - это строка символов, завершающаяся пустым симво- лом и разделяемая наклонной чертой ("/") на несколько компонент. Каждая ком- понента, кроме последней, должна быть именем каталога, но последняя компо- нента может быть именем файла, не являющегося каталогом. В версии V системы UNIX длина каждой компоненты ограничивается 14 символами; таким образом, вместе с 2 байтами, отводимыми на номер индекса, размер записи каталога сос- тавляет 16 байт. +-----------------------------------------------+ | Смещение в байтах Номер индекса Имя | | внутри каталога (2 байта) файла | +--------------------+---------------+----------+ | 0 | 83 | . | | 16 | 2 | .. | | 32 | 1798 | init | | 48 | 1276 | 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 ини- циализирует файловую систему таким образом, что номера индексов для файлов "." и ".." в корневом каталоге совпадают с номером корневого индекса файло- вой системы. Ядро хранит данные в каталоге так же, как оно это делает в файле обычно- го типа, используя индексную структуру и блоки с уровнями прямой и косвенной адресации. Процессы могут читать данные из каталогов таким же образом, как 70 они читают обычные файлы, однако исключительное право записи в каталог ре- зервируется ядром, благодаря чему обеспечивается правильность структуры ка- талога. Права доступа к каталогу имеют следующий смысл: право чтения дает процессам возможность читать данные из каталога; право записи позволяет про- цессу создавать новые записи в каталоге или удалять старые (с помощью сис- темных операций creat, mknod, link и unlink), в результате чего изменяется содержимое каталога; право исполнения позволяет процессу производить поиск в каталоге по имени файла (поскольку "исполнять" каталог бессмысленно). На примере Упражнения 4.6 показана разница между чтением и поиском в каталоге. 4.4 ПРЕВРАЩЕНИЕ СОСТАВНОГО ИМЕНИ ФАЙЛА (ПУТИ ПОИСКА) В ИДЕНТИФИКАТОР ИНДЕКСА Начальное обращение к файлу производится по его составному имени (имени пути поиска), как в командах open, chdir (изменить каталог) или link. Пос- кольку внутри системы ядро работает с индексами, а не с именами путей поис- ка, оно преобразует имена путей поиска в идентификаторы индексов, чтобы про- изводить доступ к файлам. Алгоритм namei производит поэлементный анализ сос- тавного имени, ставя в соответствие каждой компоненте имени индекс и каталог и в конце концов возвращая идентификатор индекса для введенного имени пути поиска (Рисунок 4.11). Из главы 2 напомним, что каждый процесс связан с текущим каталогом (и протекает в его рамках); рабочая область, отведенная под задачу пользовате- ля, содержит указатель на индекс текущего каталога. Текущим каталогом перво- го из процессов в системе, нулевого процесса, является корневой каталог. Путь к текущему каталогу каждого нового процесса берет начало от текущего каталога процесса, являющегося родительским по отношению к данному (см. раз- дел 5.10). Процессы изменяют текущий каталог, запрашивая выполнение систем- ной операции chdir (изменить каталог). Все поиски файлов по имени начинаются с текущего каталога процесса, если только имя пути поиска не предваряется наклонной чертой, указывая, что поиск нужно начинать с корневого каталога. В любом случае ядро может легко обнаружить индекс каталога, с которого начина- ется поиск. Текущий каталог хранится в рабочей области процесса, а корневой индекс системы хранится в глобальной переменной (**). Алгоритм namei использует при анализе составного имени пути поиска про- межуточные индексы; назовем их рабочими индексами. Индекс каталога, откуда поиск берет начало, является первым рабочим индексом. На каждой итерации цикла алгоритма ядро проверяет совпадение рабочего индекса с индексом ката- лога. В противном случае, нарушилось бы утверждение, что только файлы, не являющиеся каталогами, могут быть листьями дерева файловой системы. Процесс также должен иметь право производить поиск в каталоге (разрешения на чтение недостаточно). Код идентификации пользователя для процесса должен соответст- вовать коду индивидуального или группового вла- дельца файла и должно быть предоставлено право исполнения, либо поиск нужно разрешить всем пользователям. В противном случае, поиск не получится. Ядро выполняет линейный поиск файла в каталоге, ассоциированном с рабо- чим индексом, пытаясь найти для компоненты имени пути поиска подходящую за- пись в каталоге. Исходя из адреса смещения в байтах внутри каталога (начиная с 0), оно определяет местоположение дискового блока в соответствии с алго- ритмом bmap и считывает этот блок, используя алгоритм bread. По имени компо- --------------------------------------- (**) Чтобы изменить для себя корневой каталог файловой системы, процесс мо- жет запустить системную операцию chroot. Новое значение корня сохраня- ется в рабочей области процесса. 71 +------------------------------------------------------------+ | алгоритм namei /* превращение имени пути поиска в индекс */| | входная информация: имя пути поиска | | выходная информация: заблокированный индекс | | { | | если (путь поиска берет начало с корня) | | рабочий индекс = индексу корня (алгоритм iget); | | в противном случае | | рабочий индекс = индексу текущего каталога | | (алгоритм iget); | | | | выполнить (пока путь поиска не кончился) | | { | | считать следующую компоненту имени пути поиска; | | проверить соответствие рабочего индекса каталогу | | и права доступа; | | если (рабочий индекс соответствует корню и компо- | | нента имени "..") | | продолжить; /* цикл с условием продолжения */| | считать каталог (рабочий индекс), повторяя алго- | | ритмы bmap, bread и brelse; | | если (компонента соответствует записи в каталоге | | (рабочем индексе)) | | { | | получить номер индекса для совпавшей компонен-| | ты; | | освободить рабочий индекс (алгоритм iput); | | рабочий индекс = индексу совпавшей компоненты | | (алгоритм iget); | | } | | в противном случае /* компонента отсутствует в | | каталоге */ | | возвратить (нет индекса); | | } | | возвратить (рабочий индекс); | | } | +------------------------------------------------------------+ Рисунок 4.11. Алгоритм превращения имени пути поиска в индекс ненты ядро производит в блоке поиск, представляя содержимое блока как после- довательность записей каталога. При обнаружении совпадения ядро переписывает номер индекса из данной точки входа, освобождает блок (алгоритм brelse) и старый рабочий индекс (алгоритм iput), и переназначает индекс найденной ком- поненты (алгоритм iget). Новый индекс становится рабочим индексом. Если ядро не находит в блоке подходящего имени, оно освобождает блок, прибавляет к ад- ресу смещения число байтов в блоке, превращает новый адрес смещения в номер дискового блока (алгоритм bmap) и читает следующий блок. Ядро повторяет эту процедуру до тех пор, пока имя компоненты пути поиска не совпадет с именем точки входа в каталоге, либо до тех пор, пока не будет достигнут конец ката- лога. Предположим, например, что процессу нужно открыть файл "/etc/ passwd". Когда ядро начинает анализировать имя файла, оно наталкивается на наклонную черту ("/") и получает индекс корня системы. Сделав корень текущим рабочим индексом, ядро наталкивается на строку "etc". Проверив соответствие текущего индекса каталогу ("/") и наличие у процесса права производить поиск в ката- логе, ядро ищет в корневом каталоге файл с именем "etc". Оно просматривает корневой каталог блок за блоком и исследует каждую запись в блоке, пока не 72 обнаружит точку входа для файла "etc". Найдя эту точку входа, ядро освобож- дает индекс, отведенный для корня (алгоритм iput), и выделяет индекс файлу "etc" (алгоритм iget) в соответствии с номером индекса в обнаруженной запи- си. Удостоверившись в том, что "etc" является каталогом, а также в том, что имеются необходимые права производить поиск, ядро просматривает каталог "etc" блок за блоком в поисках записи, соответствующей файлу "passwd". Если посмотреть на Рисунок 4.10, можно увидеть, что запись о файле "passwd" явля- ется девятой записью в каталоге. Обнаружив ее, ядро освобождает индекс, вы- деленный файлу "etc", и выделяет индекс файлу "passwd", после чего - пос- кольку имя пути поиска исчерпано - возвращает этот индекс процессу. Естественно задать вопрос об эффективности линейного поиска в каталоге записи, соответствующей компоненте имени пути поиска. Ричи показывает (см. [Ritchie 78b], стр.1968), что линейный поиск эффективен, поскольку он огра- ничен размером каталога. Более того, ранние версии системы UNIX не работали еще на машинах с большим объемом памяти, поэтому значительный упор был сде- лан на простые алгоритмы, такие как алгоритмы линейного поиска. Более слож- ные схемы поиска потребовали бы отличной, более сложной, структуры каталога, и возможно работали бы медленнее даже в небольших каталогах по сравнению со схемой линейного поиска. 4.5 СУПЕРБЛОК До сих пор в этой главе описывалась структура файла, при этом предпола- галось, что индекс предварительно связывался с файлом и что уже были опреде- лены дисковые блоки, содержащие информацию. В следующих разделах описывает- ся, каким образом ядро назначает индексы и дисковые блоки. Чтобы понять эти алгоритмы, рассмотрим структуру суперблока. Суперблок состоит из следующих полей: * размер файловой системы, * количество свободных блоков в файловой системе, * список свободных блоков, имеющихся в файловой системе, * индекс следующего свободного блока в списке свободных блоков, * размер списка индексов, * количество свободных индексов в файловой системе, * список свободных индексов в файловой системе, * следующий свободный индекс в списке свободных индексов, * заблокированные поля для списка свободных блоков и свободных индексов, * флаг, показывающий, что в суперблок были внесены изменения. В оставшейся части главы будет объяснено, как пользоваться массивами, указателями и замками блокировки. Ядро периодически переписывает суперблок на диск, если в суперблок были внесены изменения, для того, чтобы обеспечи- валась согласованность с данными, хранящимися в файловой системе. 4.6 НАЗНАЧЕНИЕ ИНДЕКСА НОВОМУ ФАЙЛУ Для выделения известного индекса, то есть индекса, для которого предва- рительно определен собственный номер (и номер файловой системы), ядро ис- пользует алгоритм iget. В алгоритме namei, например, ядро определяет номер индекса, устанавливая соответствие между компонентой имени пути поиска и именем в каталоге. Другой алгоритм, ialloc, выполняет назначение дискового индекса вновь создаваемому файлу. Как уже говорилось в главе 2, в файловой системе имеется линейный список индексов. Индекс считается свободным, если поле его типа хранит нулевое зна- чение. Если процессу понадобился новый индекс, ядро теоретически могло бы произвести поиск свободного индекса в списке индексов. Однако, такой поиск обошелся бы дорого, поскольку потребовал бы по меньшей мере одну операцию 73 чтения (допустим, с диска) на каждый индекс. Для повышения производительнос- ти в суперблоке файловой системы хранится массив номеров свободных индексов в файловой системе. На Рисунке 4.12 приведен алгоритм ialloc назначения новых индексов. По причинам, о которых пойдет речь ниже, ядро сначала проверяет, не заблокиро- вал ли какой-либо процесс своим обращением список свободных индексов в су- +------------------------------------------------------------+ | алгоритм ialloc /* выделение индекса */ | | входная информация: файловая система | | выходная информация: заблокированный индекс | | { | | выполнить | | { | | если (суперблок заблокирован) | | { | | приостановиться (пока суперблок не освободится); | | продолжить; /* цикл с условием продолжения */ | | } | | если (список индексов в суперблоке пуст) | | { | | заблокировать суперблок; | | выбрать запомненный индекс для поиска свободных | | индексов; | | искать на диске свободные индексы до тех пор, пока| | суперблок не заполнится, или пока не будут най- | | дены все свободные индексы (алгоритмы bread и | | brelse); | | снять блокировку с суперблока; | | возобновить выполнение процесса (как только супер-| | блок освободится); | | если (на диске отсутствуют свободные индексы) | | возвратить (нет индексов); | | запомнить индекс с наибольшим номером среди най- | | денных для последующих поисков свободных индек- | | сов; | | } | | /* список индексов в суперблоке не пуст */ | | выбрать номер индекса из списка индексов в супербло- | | ке; | | получить индекс (алгоритм 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 описана в предыдущем параграфе. Сходным образом, если процесс, освобождая индекс, не проверил наличие блокировки списка, он может затереть номера ин- дексов уже в списке свободных индексов, пока другой процесс будет заполнять этот список информацией с диска. И опять участится конкуренция вышеописанно- го типа. Несмотря на то, что ядро более или менее удачно управляется с ней, производительность системы снижается. Установка блокировки для списка сво- бодных индексов в суперблоке устраняет такую конкуренцию. 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. Список номеров свободных дисковых блоков с указателями 80 дый раз только по одному блоку. Программа mkfs пытается организовать перво- начальный связанный список номеров свободных блоков так, чтобы номера бло- ков, передаваемых файлу, были рядом друг с другом. Благодаря этому повышает- ся производительность, поскольку сокращается время поиска на диске и время ожидания при последовательном чтении файла процессом. На Рисунке 4.18 номера блоков даны в настоящем формате, определяемом скоростью вращения диска. К сожалению, очередность номеров блоков в списке свободных блоков перепутана в связи с частыми обращениями к списку со стороны процессов, ведущих запись в файлы и удаляющих их, в результате чего номера блоков поступают в список и покидают его в случайном порядке. Ядро не предпринимает попыток сортиро- вать номера блоков в списке. Алгоритм освобождения блока free - обратный алгоритму выделения блока. Если список в суперблоке не полон, номер вновь освобожденного блока включа- ется в этот список. Если, однако, список полон, вновь освобожденный блок становится связным блоком; ядро переписывает в него список из суперблока и копирует блок на диск. Затем номер вновь освобожденного блока включается в список свободных блоков в суперблоке. Этот номер становится единственным но- мером в списке. На Рисунке 4.20 показана последовательность операций alloc и free для случая, когда в исходный момент список свободных блоков содержал один эле- мент. Ядро освобождает блок 949 и включает номер блока в список. Затем оно выделяет этот блок и удаляет его номер из списка. Наконец, оно выделяет блок 109 и удаляет его номер из списка. Поскольку список свободных блоков в су- перблоке теперь пуст, ядро снова наполняет список, копируя в него содержимое блока 109, являющегося следующей связью в списке с указателями. На Рисунке +------------------------------------------------------------+ | алгоритм alloc /* выделение блока файловой системы */ | | входная информация: номер файловой системы | | выходная информация: буфер для нового блока | | { | | выполнить (пока суперблок заблокирован) | | приостановиться (до того момента, когда с суперблока| | будет снята блокировка); | | удалить блок из списка свобод