Страница:
| 6| -
+-------------+ +-----+
| прямой адр. | +----------------->| |
| 7| | | |
+-------------+ +--------------+ +-----+
| прямой адр. | | +-----+
| 8| | +----------------->| |
+-------------+ | | | |
| прямой адр. +--+ +------+ | +-----+
| 9| +------+----+ +-----+
+-------------+ +->+------+ +------>| |
| одинарной +--+ +------+ | | |
|косвенной адр| +------+ | +-----+
+-------------+ +->+------+ +->+------+ | +-----+
| двойной +--+ +------+ | +------+ | +->| |
|косвенной адр| +------+ | +------+ | | | |
+-------------+ +------+-+ +------+---+ | +-----+
| тройной +--+ +------+ +------+ +---+
|косвенной адр| +->+------+ +->+------+ +>+------+-+
+-------------+ +------+ | +------+ | +------+
+------+-+ +------+ | +------+
+------+ +------+-+ +------+
+------+ +------+ +------+
Рисунок 4.6. Блоки прямой и косвенной адресации в индексе
66
+----------------------------------------------------------+
| 10 блоков прямой адресации по 1 Кбайту каждый = 10 Кбайт |
| 1 блок косвенной адресации с 256 блоками прямой |
| адресации = 256 Кбайт |
| 1 блок двойной косвенной адресации с 256 блоками |
| косвенной адресации = 64 Мбайта|
| 1 блок тройной косвенной адресации с 256 блоками |
| двойной косвенной адресации = 16 Гбайт |
+----------------------------------------------------------+
Рисунок 4.7. Объем файла в байтах при размере блока 1 Кбайт
+------------------------------------------------------------+
| алгоритм bmap /* отображение адреса смещения в байтах от |
| начала логического файла на адрес блока |
| в файловой системе */ |
| входная информация: (1) индекс |
| (2) смещение в байтах |
| выходная информация: (1) номер блока в файловой системе |
| (2) смещение в байтах внутри блока |
| (3) число байт ввода-вывода в блок |
| (4) номер блока с продвижением |
| { |
| вычислить номер логического блока в файле исходя из |
| заданного смещения в байтах; |
| вычислить номер начального байта в блоке для ввода- |
| вывода; /* выходная информация 2 */ |
| вычислить количество байт для копирования пользова- |
| телю; /* выходная информация 3 */ |
| проверить возможность чтения с продвижением, пометить |
| индекс; /* выходная информация 4 */ |
| определить уровень косвенности; |
| выполнить (пока уровень косвенности другой) |
| { |
| определить указатель в индексе или блок косвенной |
| адресации исходя из номера логического блока в |
| файле; |
| получить номер дискового блока из индекса или из |
| блока косвенной адресации; |
| освободить буфер от данных, полученных в резуль- |
| тате выполнения предыдущей операции чтения с |
| диска (алгоритм brelse); |
| если (число уровней косвенности исчерпано) |
| возвратить (номер блока); |
| считать дисковый блок косвенной адресации (алго- |
| ритм bread); |
| установить номер логического блока в файле исходя |
| из уровня косвенности; |
| } |
| } |
+------------------------------------------------------------+
Рисунок 4.8. Преобразование адреса смещения в номер блока в
файловой системе
67
ствующий дисковый блок. На Рисунке 4.8 представлен алгоритм bmap пересчета
смещения в байтах от начала файла в номер физического блока на диске.
Рассмотрим формат файла в блоках (Рисунок 4.9) и предположим, что диско-
вый блок занимает 1024 байта. Если процессу нужно обратиться к байту, имею-
щему смещение от начала файла, равное 9000, в результате вычислений ядро
приходит к выводу, что этот байт располагается в блоке прямой адресации с
номером 8 (начиная с 0). Затем ядро обращается к блоку с номером 367; 808-й
байт в этом
блоке (если вести отсчет с 0) и является 9000-м байтом в файле. Если процес-
су нужно обратиться по адресу, указанному смещением 350000 байт от начала
файла, он должен считать блок двойной косвенной адресации, который на рисун-
ке имеет номер 9156. Так как блок косвенной адресации имеет место для 256
номеров блоков, первым байтом, к которому будет получен доступ в результате
обраще-
+-------------+
| 4096 |
+-------------+
| 228 |
+-------------+
| 45423 |
+-------------+
| 0 |
+-------------+
| 0 |
+-------------+ +----------->+------+
| 11111 | | | |
+-------------+ | | |
| 0 | | | |
+-------------+ | +------+
| 101 | | 367
+-------------+ | информаци-
| 367 +----------------------+ онный
+-------------+ блок
| 0 | +->+------+
+-------------+ +---->+------+ | | | +-->+------+
| 428 | | | 331 +--+ | | | | |
+-------------+ | 0+------+ 75+------+ | | |
| 9156 +--+ | | | 3333 +--+ | |
+-------------+ +------+ +------+ +------+
| 824 | 9156 | | 3333
+-------------+ двойная +------+ информаци-
адресация 331 онный
одинарная блок
адресация
Рисунок 4.9. Размещение блоков в файле и его индексе
ния к блоку двойной косвенной адресации, будет байт с номером 272384 (256К +
10К); таким образом, байт с номером 350000 будет иметь в блоке двойной кос-
венной адресации номер 77616. Поскольку каждый блок одинарной косвенной ад-
ресации позволяет обращаться к 256 Кбайтам, байт с номером 350000 должен
располагаться в нулевом блоке одинарной косвенной адресации для блока двой-
ной косвенной адресации, а именно в блоке 331. Так как в каждом блоке прямой
адресации для блока одинарной косвенной адресации хранится 1 Кбайт, байт с
номером 77616 находится в 75-м блоке прямой адресации для блока одинарной
косвенной адресации, а именно в блоке 3333. Наконец, байт с номером в файле
350000 имеет в блоке 3333 номер 816.
68
При ближайшем рассмотрении Рисунка 4.9 обнаруживается, что несколько
входов для блока в индексе имеют значение 0 и это значит, что в данных запи-
сях информация о логических блоках отсутствует. Такое имеет место, если в
соответствующие блоки файла никогда не записывалась информация и по этой
причине у номеров блоков остались их первоначальные нулевые значения. Для
таких блоков пространство на диске не выделяется. Подобное расположение бло-
ков в файле вызывается процессами, запускающими системные операции lseek и
write (см. следующую главу). В следующей главе также объясняется, каким об-
разом ядро обрабатывает системные вызовы операции read, с помощью которой
производится обращение к блокам.
Преобразование адресов с большими смещениями, в частности с использова-
нием блоков тройной косвенной адресации, является сложной процедурой, требу-
ющей от ядра обращения уже к трем дисковым блокам в дополнение к индексу и
информационному блоку. Даже если ядро обнаружит блоки в буферном кеше, опе-
рация останется дорогостоящей, так как ядру придется многократно обращаться
к буферному кешу и приостанавливать свою работу в ожидании снятия блокировки
с буферов. Насколько эффективен этот алгоритм на практике ? Это зависит от
того, как используется система, а также от того, кто является пользователем
и каков состав задач, вызывающий потребность в более частом обращении к
большим или, наоборот, маленьким файлам. Однако, как уже было замечено
[Mullender 84], большинство файлов в системе UNIX имеет размер, не превышаю-
щий 10 Кбайт и даже 1 Кбайта ! (*) Поскольку 10 Кбайт файла располагаются в
блоках прямой адресации, к большей части данных, хранящихся в файлах, доступ
может производиться за одно обращение к диску.Поэтому в отличие от обращения
к большим файлам, работа с файлами стандартного размера протекает быстро.
В двух модификациях только что описанной структуры индекса предпринима-
ется попытка использовать размерные характеристики файла. Основной принцип в
реализации файловой системы BSD 4.2 [McKusick 84] состоит в том, что чем
больше объем данных, к которым ядро может получить доступ за одно обращение
к диску, тем быстрее протекает работа с файлом. Это свидетельствует в пользу
увеличения размера логического блока на диске, поэтому в системе BSD разре-
шается иметь логические блоки размером 4 или 8 Кбайт. Однако, увеличение
размера блоков на диске приводит к увеличению фрагментации блоков, при кото-
рой значительные участки дискового пространства остаются неиспользуемыми.
Например, если размер логического блока 8 Кбайт, тогда файл размером 12
Кбайт занимает 1 полный блок и половину второго блока. Другая половина вто-
рого блока (4 Кбайта) фактически теряется; другие файлы не могут использо-
вать ее для хранения данных. Если размеры файлов таковы, что число байт, по-
павших в последний блок, является равномерно распределенной величиной, то
средние потери дискового пространства составляют полблока на каждый файл;
объем теряемого дискового пространства достигает в файловой системе с логи-
ческими блоками размером 4 Кбайта 45% [McKusick 84]. Выход из этой ситуации
в системе BSD состоит в выделении только части блока (фрагмента) для разме-
щения оставшейся информации файла. Один дисковый блок может включать в себя
фрагменты, принадлежащие нескольким файлам. Некоторые подробности этой реа-
лизации исследуются на примере упражнения в главе 5.
Второй модификацией рассмотренной классической структуры индекса являет-
ся идея хранения в индексе информации файла (см. [Mullender 84]). Если уве-
личить размер индекса так, чтобы индекс занимал весь дисковый блок, неболь-
шая часть блока может быть использована для собственно индексных структур, а
оставшаяся часть - для хранения конца файла и даже во многих случаях для
хранения файла целиком. Основное преимущество такого подхода заключается в
том, что необходимо только одно обращение к диску для считывания индекса и
всей информации, если файл помещается в индексном блоке.
---------------------------------------
(*) На примере 19978 файлов Маллендер и Танненбаум говорят, что приблизи-
тельно 85% файлов имеют размер менее 8 Кбайт и 48% - менее 1 Кбайта.
Несмотря на то, что эти данные варьируются от одной реализации системы к
другой, для многих реализаций системы UNIX они показательны.
69
Из главы 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 показана разница между чтением и поиском в каталоге.
В ИДЕНТИФИКАТОР ИНДЕКСА
Начальное обращение к файлу производится по его составному имени (имени
пути поиска), как в командах 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 не работали
еще на машинах с большим объемом памяти, поэтому значительный упор был сде-
лан на простые алгоритмы, такие как алгоритмы линейного поиска. Более слож-
ные схемы поиска потребовали бы отличной, более сложной, структуры каталога,
и возможно работали бы медленнее даже в небольших каталогах по сравнению со
схемой линейного поиска.
До сих пор в этой главе описывалась структура файла, при этом предпола-
галось, что индекс предварительно связывался с файлом и что уже были опреде-
лены дисковые блоки, содержащие информацию. В следующих разделах описывает-
ся, каким образом ядро назначает индексы и дисковые блоки. Чтобы понять эти
алгоритмы, рассмотрим структуру суперблока.
Суперблок состоит из следующих полей:
* размер файловой системы,
* количество свободных блоков в файловой системе,
* список свободных блоков, имеющихся в файловой системе,
* индекс следующего свободного блока в списке свободных блоков,
* размер списка индексов,
* количество свободных индексов в файловой системе,
* список свободных индексов в файловой системе,
* следующий свободный индекс в списке свободных индексов,
* заблокированные поля для списка свободных блоков и свободных индексов,
* флаг, показывающий, что в суперблок были внесены изменения.
В оставшейся части главы будет объяснено, как пользоваться массивами,
указателями и замками блокировки. Ядро периодически переписывает суперблок
на диск, если в суперблок были внесены изменения, для того, чтобы обеспечи-
валась согласованность с данными, хранящимися в файловой системе.
Для выделения известного индекса, то есть индекса, для которого предва-
рительно определен собственный номер (и номер файловой системы), ядро ис-
пользует алгоритм iget. В алгоритме namei, например, ядро определяет номер
индекса, устанавливая соответствие между компонентой имени пути поиска и
именем в каталоге. Другой алгоритм, ialloc, выполняет назначение дискового
индекса вновь создаваемому файлу.
Как уже говорилось в главе 2, в файловой системе имеется линейный список
индексов. Индекс считается свободным, если поле его типа хранит нулевое зна-
чение. Если процессу понадобился новый индекс, ядро теоретически могло бы
произвести поиск свободного индекса в списке индексов. Однако, такой поиск
обошелся бы дорого, поскольку потребовал бы по меньшей мере одну операцию
73
чтения (допустим, с диска) на каждый индекс. Для повышения производительнос-
ти в суперблоке файловой системы хранится массив номеров свободных индексов
в файловой системе.
На Рисунке 4.12 приведен алгоритм ialloc назначения новых индексов. По
причинам, о которых пойдет речь ниже, ядро сначала проверяет, не заблокиро-
вал ли какой-либо процесс своим обращением список свободных индексов в су-
+------------------------------------------------------------+
| алгоритм ialloc /* выделение индекса */ |
| входная информация: файловая система |
| выходная информация: заблокированный индекс |
| { |
| выполнить |
| { |
| если (суперблок заблокирован) |
| { |
| приостановиться (пока суперблок не освободится); |
| продолжить; /* цикл с условием продолжения */ |
| } |
| если (список индексов в суперблоке пуст) |
| { |
| заблокировать суперблок; |
| выбрать запомненный индекс для поиска свободных |
| индексов; |
| искать на диске свободные индексы до тех пор, пока|
| суперблок не заполнится, или пока не будут най- |
| дены все свободные индексы (алгоритмы bread и |
| brelse); |
| снять блокировку с суперблока; |
| возобновить выполнение процесса (как только супер-|
| блок освободится); |
| если (на диске отсутствуют свободные индексы) |
| возвратить (нет индексов); |
| запомнить индекс с наибольшим номером среди най- |
| денных для последующих поисков свободных индек- |
| сов; |
| } |
| /* список индексов в суперблоке не пуст */ |
| выбрать номер индекса из списка индексов в супербло- |
| ке; |
+-------------+ +-----+
| прямой адр. | +----------------->| |
| 7| | | |
+-------------+ +--------------+ +-----+
| прямой адр. | | +-----+
| 8| | +----------------->| |
+-------------+ | | | |
| прямой адр. +--+ +------+ | +-----+
| 9| +------+----+ +-----+
+-------------+ +->+------+ +------>| |
| одинарной +--+ +------+ | | |
|косвенной адр| +------+ | +-----+
+-------------+ +->+------+ +->+------+ | +-----+
| двойной +--+ +------+ | +------+ | +->| |
|косвенной адр| +------+ | +------+ | | | |
+-------------+ +------+-+ +------+---+ | +-----+
| тройной +--+ +------+ +------+ +---+
|косвенной адр| +->+------+ +->+------+ +>+------+-+
+-------------+ +------+ | +------+ | +------+
+------+-+ +------+ | +------+
+------+ +------+-+ +------+
+------+ +------+ +------+
Рисунок 4.6. Блоки прямой и косвенной адресации в индексе
66
+----------------------------------------------------------+
| 10 блоков прямой адресации по 1 Кбайту каждый = 10 Кбайт |
| 1 блок косвенной адресации с 256 блоками прямой |
| адресации = 256 Кбайт |
| 1 блок двойной косвенной адресации с 256 блоками |
| косвенной адресации = 64 Мбайта|
| 1 блок тройной косвенной адресации с 256 блоками |
| двойной косвенной адресации = 16 Гбайт |
+----------------------------------------------------------+
Рисунок 4.7. Объем файла в байтах при размере блока 1 Кбайт
+------------------------------------------------------------+
| алгоритм bmap /* отображение адреса смещения в байтах от |
| начала логического файла на адрес блока |
| в файловой системе */ |
| входная информация: (1) индекс |
| (2) смещение в байтах |
| выходная информация: (1) номер блока в файловой системе |
| (2) смещение в байтах внутри блока |
| (3) число байт ввода-вывода в блок |
| (4) номер блока с продвижением |
| { |
| вычислить номер логического блока в файле исходя из |
| заданного смещения в байтах; |
| вычислить номер начального байта в блоке для ввода- |
| вывода; /* выходная информация 2 */ |
| вычислить количество байт для копирования пользова- |
| телю; /* выходная информация 3 */ |
| проверить возможность чтения с продвижением, пометить |
| индекс; /* выходная информация 4 */ |
| определить уровень косвенности; |
| выполнить (пока уровень косвенности другой) |
| { |
| определить указатель в индексе или блок косвенной |
| адресации исходя из номера логического блока в |
| файле; |
| получить номер дискового блока из индекса или из |
| блока косвенной адресации; |
| освободить буфер от данных, полученных в резуль- |
| тате выполнения предыдущей операции чтения с |
| диска (алгоритм brelse); |
| если (число уровней косвенности исчерпано) |
| возвратить (номер блока); |
| считать дисковый блок косвенной адресации (алго- |
| ритм bread); |
| установить номер логического блока в файле исходя |
| из уровня косвенности; |
| } |
| } |
+------------------------------------------------------------+
Рисунок 4.8. Преобразование адреса смещения в номер блока в
файловой системе
67
ствующий дисковый блок. На Рисунке 4.8 представлен алгоритм bmap пересчета
смещения в байтах от начала файла в номер физического блока на диске.
Рассмотрим формат файла в блоках (Рисунок 4.9) и предположим, что диско-
вый блок занимает 1024 байта. Если процессу нужно обратиться к байту, имею-
щему смещение от начала файла, равное 9000, в результате вычислений ядро
приходит к выводу, что этот байт располагается в блоке прямой адресации с
номером 8 (начиная с 0). Затем ядро обращается к блоку с номером 367; 808-й
байт в этом
блоке (если вести отсчет с 0) и является 9000-м байтом в файле. Если процес-
су нужно обратиться по адресу, указанному смещением 350000 байт от начала
файла, он должен считать блок двойной косвенной адресации, который на рисун-
ке имеет номер 9156. Так как блок косвенной адресации имеет место для 256
номеров блоков, первым байтом, к которому будет получен доступ в результате
обраще-
+-------------+
| 4096 |
+-------------+
| 228 |
+-------------+
| 45423 |
+-------------+
| 0 |
+-------------+
| 0 |
+-------------+ +----------->+------+
| 11111 | | | |
+-------------+ | | |
| 0 | | | |
+-------------+ | +------+
| 101 | | 367
+-------------+ | информаци-
| 367 +----------------------+ онный
+-------------+ блок
| 0 | +->+------+
+-------------+ +---->+------+ | | | +-->+------+
| 428 | | | 331 +--+ | | | | |
+-------------+ | 0+------+ 75+------+ | | |
| 9156 +--+ | | | 3333 +--+ | |
+-------------+ +------+ +------+ +------+
| 824 | 9156 | | 3333
+-------------+ двойная +------+ информаци-
адресация 331 онный
одинарная блок
адресация
Рисунок 4.9. Размещение блоков в файле и его индексе
ния к блоку двойной косвенной адресации, будет байт с номером 272384 (256К +
10К); таким образом, байт с номером 350000 будет иметь в блоке двойной кос-
венной адресации номер 77616. Поскольку каждый блок одинарной косвенной ад-
ресации позволяет обращаться к 256 Кбайтам, байт с номером 350000 должен
располагаться в нулевом блоке одинарной косвенной адресации для блока двой-
ной косвенной адресации, а именно в блоке 331. Так как в каждом блоке прямой
адресации для блока одинарной косвенной адресации хранится 1 Кбайт, байт с
номером 77616 находится в 75-м блоке прямой адресации для блока одинарной
косвенной адресации, а именно в блоке 3333. Наконец, байт с номером в файле
350000 имеет в блоке 3333 номер 816.
68
При ближайшем рассмотрении Рисунка 4.9 обнаруживается, что несколько
входов для блока в индексе имеют значение 0 и это значит, что в данных запи-
сях информация о логических блоках отсутствует. Такое имеет место, если в
соответствующие блоки файла никогда не записывалась информация и по этой
причине у номеров блоков остались их первоначальные нулевые значения. Для
таких блоков пространство на диске не выделяется. Подобное расположение бло-
ков в файле вызывается процессами, запускающими системные операции lseek и
write (см. следующую главу). В следующей главе также объясняется, каким об-
разом ядро обрабатывает системные вызовы операции read, с помощью которой
производится обращение к блокам.
Преобразование адресов с большими смещениями, в частности с использова-
нием блоков тройной косвенной адресации, является сложной процедурой, требу-
ющей от ядра обращения уже к трем дисковым блокам в дополнение к индексу и
информационному блоку. Даже если ядро обнаружит блоки в буферном кеше, опе-
рация останется дорогостоящей, так как ядру придется многократно обращаться
к буферному кешу и приостанавливать свою работу в ожидании снятия блокировки
с буферов. Насколько эффективен этот алгоритм на практике ? Это зависит от
того, как используется система, а также от того, кто является пользователем
и каков состав задач, вызывающий потребность в более частом обращении к
большим или, наоборот, маленьким файлам. Однако, как уже было замечено
[Mullender 84], большинство файлов в системе UNIX имеет размер, не превышаю-
щий 10 Кбайт и даже 1 Кбайта ! (*) Поскольку 10 Кбайт файла располагаются в
блоках прямой адресации, к большей части данных, хранящихся в файлах, доступ
может производиться за одно обращение к диску.Поэтому в отличие от обращения
к большим файлам, работа с файлами стандартного размера протекает быстро.
В двух модификациях только что описанной структуры индекса предпринима-
ется попытка использовать размерные характеристики файла. Основной принцип в
реализации файловой системы BSD 4.2 [McKusick 84] состоит в том, что чем
больше объем данных, к которым ядро может получить доступ за одно обращение
к диску, тем быстрее протекает работа с файлом. Это свидетельствует в пользу
увеличения размера логического блока на диске, поэтому в системе BSD разре-
шается иметь логические блоки размером 4 или 8 Кбайт. Однако, увеличение
размера блоков на диске приводит к увеличению фрагментации блоков, при кото-
рой значительные участки дискового пространства остаются неиспользуемыми.
Например, если размер логического блока 8 Кбайт, тогда файл размером 12
Кбайт занимает 1 полный блок и половину второго блока. Другая половина вто-
рого блока (4 Кбайта) фактически теряется; другие файлы не могут использо-
вать ее для хранения данных. Если размеры файлов таковы, что число байт, по-
павших в последний блок, является равномерно распределенной величиной, то
средние потери дискового пространства составляют полблока на каждый файл;
объем теряемого дискового пространства достигает в файловой системе с логи-
ческими блоками размером 4 Кбайта 45% [McKusick 84]. Выход из этой ситуации
в системе BSD состоит в выделении только части блока (фрагмента) для разме-
щения оставшейся информации файла. Один дисковый блок может включать в себя
фрагменты, принадлежащие нескольким файлам. Некоторые подробности этой реа-
лизации исследуются на примере упражнения в главе 5.
Второй модификацией рассмотренной классической структуры индекса являет-
ся идея хранения в индексе информации файла (см. [Mullender 84]). Если уве-
личить размер индекса так, чтобы индекс занимал весь дисковый блок, неболь-
шая часть блока может быть использована для собственно индексных структур, а
оставшаяся часть - для хранения конца файла и даже во многих случаях для
хранения файла целиком. Основное преимущество такого подхода заключается в
том, что необходимо только одно обращение к диску для считывания индекса и
всей информации, если файл помещается в индексном блоке.
---------------------------------------
(*) На примере 19978 файлов Маллендер и Танненбаум говорят, что приблизи-
тельно 85% файлов имеют размер менее 8 Кбайт и 48% - менее 1 Кбайта.
Несмотря на то, что эти данные варьируются от одной реализации системы к
другой, для многих реализаций системы UNIX они показательны.
69
Из главы 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 показана разница между чтением и поиском в каталоге.
В ИДЕНТИФИКАТОР ИНДЕКСА
Начальное обращение к файлу производится по его составному имени (имени
пути поиска), как в командах 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 не работали
еще на машинах с большим объемом памяти, поэтому значительный упор был сде-
лан на простые алгоритмы, такие как алгоритмы линейного поиска. Более слож-
ные схемы поиска потребовали бы отличной, более сложной, структуры каталога,
и возможно работали бы медленнее даже в небольших каталогах по сравнению со
схемой линейного поиска.
До сих пор в этой главе описывалась структура файла, при этом предпола-
галось, что индекс предварительно связывался с файлом и что уже были опреде-
лены дисковые блоки, содержащие информацию. В следующих разделах описывает-
ся, каким образом ядро назначает индексы и дисковые блоки. Чтобы понять эти
алгоритмы, рассмотрим структуру суперблока.
Суперблок состоит из следующих полей:
* размер файловой системы,
* количество свободных блоков в файловой системе,
* список свободных блоков, имеющихся в файловой системе,
* индекс следующего свободного блока в списке свободных блоков,
* размер списка индексов,
* количество свободных индексов в файловой системе,
* список свободных индексов в файловой системе,
* следующий свободный индекс в списке свободных индексов,
* заблокированные поля для списка свободных блоков и свободных индексов,
* флаг, показывающий, что в суперблок были внесены изменения.
В оставшейся части главы будет объяснено, как пользоваться массивами,
указателями и замками блокировки. Ядро периодически переписывает суперблок
на диск, если в суперблок были внесены изменения, для того, чтобы обеспечи-
валась согласованность с данными, хранящимися в файловой системе.
Для выделения известного индекса, то есть индекса, для которого предва-
рительно определен собственный номер (и номер файловой системы), ядро ис-
пользует алгоритм iget. В алгоритме namei, например, ядро определяет номер
индекса, устанавливая соответствие между компонентой имени пути поиска и
именем в каталоге. Другой алгоритм, ialloc, выполняет назначение дискового
индекса вновь создаваемому файлу.
Как уже говорилось в главе 2, в файловой системе имеется линейный список
индексов. Индекс считается свободным, если поле его типа хранит нулевое зна-
чение. Если процессу понадобился новый индекс, ядро теоретически могло бы
произвести поиск свободного индекса в списке индексов. Однако, такой поиск
обошелся бы дорого, поскольку потребовал бы по меньшей мере одну операцию
73
чтения (допустим, с диска) на каждый индекс. Для повышения производительнос-
ти в суперблоке файловой системы хранится массив номеров свободных индексов
в файловой системе.
На Рисунке 4.12 приведен алгоритм ialloc назначения новых индексов. По
причинам, о которых пойдет речь ниже, ядро сначала проверяет, не заблокиро-
вал ли какой-либо процесс своим обращением список свободных индексов в су-
+------------------------------------------------------------+
| алгоритм ialloc /* выделение индекса */ |
| входная информация: файловая система |
| выходная информация: заблокированный индекс |
| { |
| выполнить |
| { |
| если (суперблок заблокирован) |
| { |
| приостановиться (пока суперблок не освободится); |
| продолжить; /* цикл с условием продолжения */ |
| } |
| если (список индексов в суперблоке пуст) |
| { |
| заблокировать суперблок; |
| выбрать запомненный индекс для поиска свободных |
| индексов; |
| искать на диске свободные индексы до тех пор, пока|
| суперблок не заполнится, или пока не будут най- |
| дены все свободные индексы (алгоритмы bread и |
| brelse); |
| снять блокировку с суперблока; |
| возобновить выполнение процесса (как только супер-|
| блок освободится); |
| если (на диске отсутствуют свободные индексы) |
| возвратить (нет индексов); |
| запомнить индекс с наибольшим номером среди най- |
| денных для последующих поисков свободных индек- |
| сов; |
| } |
| /* список индексов в суперблоке не пуст */ |
| выбрать номер индекса из списка индексов в супербло- |
| ке; |