|
Часть 4
ГЛАВА 4
EВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ ФАЙЛОВF
Как уже было замечено в главе 2, каждый файл в системе UNIX имеет уни-
кальный индекс. Индекс содержит информацию, необходимую любому процессу для
того, чтобы обратиться к файлу, например, права собственности на файл, права
доступа к файлу, размер файла и расположение данных файла в файловой систе-
ме. Процессы обращаются к файлам, используя четко определенный набор систем-
ных вызовов и идентифицируя файл строкой символов, выступающих в качестве
составного имени файла. Каждое составное имя однозначно определяет файл,
благодаря чему ядро системы преобразует это имя в индекс файла.
Эта глава посвящена описанию внутренней структуры файлов в операционной
системе UNIX, в следующей же главе рассматриваются обращения к операционной
системе, связанные с обработкой файлов. Раздел 4.1 касается индекса и работы
с ним ядра, раздел 4.2 - внутренней структуры обычных файлов и некоторых мо-
ментов, связанных с чтением и записью ядром информации файлов. В разделе 4.3
исследуется строение каталогов - структур данных, позволяющих ядру организо-
вывать файловую систему в виде иерархии файлов, раздел 4.4 содержит алгоритм
преобразования имен пользовательских файлов в индексы. В разделе 4.5 дается
структура суперблока, а в разделах 4.6 и 4.7 представлены алгоритмы назначе-
ния файлам дисковых индексов и дисковых блоков. Наконец, в разделе 4.8 идет
речь о других типах файлов в системе, а именно о каналах и файлах устройств.
Алгоритмы, описанные в этой главе, уровнем выше по сравнению с алгорит-
мами управления буферным кешем, рассмотренными в предыдущей главе (Рисунок
4.1). Алгоритм iget возвращает последний из идентифицированных индексов с
возможностью считывания его с диска, используя буферный кеш, а алгоритм iput
освобождает индекс. Алгоритм bmap устанавливает параметры ядра, связанные с
обращением к файлу. Алгоритм namei преобразует составное имя пользователь-
ского файла в имя индекса, используя алгоритмы iget, iput и
Алгоритмы работы с файловой системой на нижнем уровне
ЪДДДДДДДДДДДДДДДДДДДДВДДДДДДДДДДДДДДДДДДВДДДДДДДДДДДДДДДДДї
і namei і і і
ГДДДДДДДДДДДДДДДДДДДДґ alloc free і ialloc ifree і
і iget iput bmap і і і
ГДДДДДДДДДДДДДДДДДДДДБДДДДДДДДДДДДДДДДДДБДДДДДДДДДДДДДДДДДґ
ГДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДґ
і алгоритмы работы с буферами і
ГДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДґ
і getblk brelse bread breada bwrite і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
Рисунок 4.1. Алгоритмы файловой системы
bmap. Алгоритмы alloc и free выделяют и освобождают дисковые блоки для фай-
лов, алгоритмы ialloc и ifree назначают и освобождают для файлов индексы.
E4.1 ИНДЕКСЫF
E4.1.1 ОпределениеF
Индексы существуют на диске в статической форме и ядро считывает их в
59
память прежде, чем начать с ними работать. Дисковые индексы включают в себя
следующие поля:
* Идентификатор владельца файла. Права собственности разделены между инди-
видуальным владельцем и "групповым" и тем самым помогают определить круг
пользователей, имеющих права доступа к файлу. Суперпользователь имеет
право доступа ко всем файлам в системе.
* Тип файла. Файл может быть файлом обычного типа, каталогом, специальным
файлом, соответствующим устройствам ввода-вывода символами или блоками,
а также абстрактным файлом канала (организующим обслуживание запросов в
порядке поступления, "первым пришел - первым вышел").
* Права доступа к файлу. Система разграничивает права доступа к файлу для
трех классов пользователей: индивидуального владельца файла, группового
владельца и прочих пользователей; каждому классу выделены определенные
права на чтение, запись и исполнение файла, которые устанавливаются ин-
дивидуально. Поскольку каталоги как файлы не могут быть исполнены, раз-
решение на исполнение в данном случае интерпретируется как право произ-
водить поиск в каталоге по имени файла.
* Календарные сведения, характеризующие работу с файлом: время внесения
последних изменений в файл, время последнего обращения к файлу, время
внесения последних изменений в индекс.
* Число указателей на файл, означающее количество имен, используемых при
поиске файла в иерархии каталогов. Указатели на файл подробно рассматри-
ваются в главе 5.
* Таблица адресов на диске, в которых располагается информация файла. Хотя
пользователи трактуют информацию в файле как логический поток байтов,
ядро располагает эти данные в несоприкасающихся дисковых блоках. Диско-
вые блоки, содержащие информацию файла, указываются в индексе.
* Размер файла. Данные в файле адресуются с помощью смещения в байтах от-
носительно начала файла, начиная со смещения, равного 0, поэтому размер
файла в байтах на 1 больше максимального смещения. Например, если поль-
зователь создает файл и записывает только 1 байт информации по адресу со
смещением 1000 от начала файла, размер файла составит 1001 байт. В ин-
дексе отсутствует составное имя файла, необходимое для осуществления
доступа к файлу.
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДї
і владелец mjb і
і группа os і
і тип - обычный файл і
і права доступа rwxr-xr-x і
і последнее обращение 23 Окт 1984 13:45 і
і последнее изменение 22 Окт 1984 10:30 і
і коррекция индекса 23 Окт 1984 13:30 і
і размер 6030 байт і
і дисковые адреса і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
Рисунок 4.2. Пример дискового индекса
На Рисунке 4.2 показан дисковый индекс некоторого файла. Этот индекс
принадлежит обычному файлу, владелец которого - "mjb" и размер которого -
6030 байт. Система разрешает пользователю "mjb" производить чтение, запись и
исполнение файла; членам группы "os" и всем остальным пользователям разреша-
ется только читать или исполнять файл, но не записывать в него данные. Пос-
ледний раз файл был прочитан 23 октября 1984 года в 13:45, запись последний
раз производилась 22 октября 1984 года в 10:30. Индекс изменялся последний
раз 23 октября 1984 года в 13:30, хотя никакая информация в это время в файл
не записывалась. Ядро кодирует все вышеперечисленные данные в индексе. Обра-
60
тите внимание на различие в записи на диск содержимого индекса и содержимого
файла. Содержимое файла меняется только тогда, когда в файл производится за-
пись. Содержимое индекса меняется как при изменении содержимого файла, так и
при изменении владельца файла, прав доступа и набора указателей. Изменение
содержимого файла автоматически вызывает коррекцию индекса, однако коррекция
индекса еще не означает изменения содержимого файла.
Копия индекса в памяти, кроме полей дискового индекса, включает в себя и
следующие поля:
* Состояние индекса в памяти, отражающее
- заблокирован ли индекс,
- ждет ли снятия блокировки с индекса какой-либо процесс,
- отличается ли представление индекса в памяти от своей дисковой копии в
результате изменения содержимого индекса,
- отличается ли представление индекса в памяти от своей дисковой копии в
результате изменения содержимого файла,
- находится ли файл в верхней точке (см. раздел 5.15).
* Логический номер устройства файловой системы, содержащей файл.
* Номер индекса. Так как индексы на диске хранятся в линейном массиве (см.
раздел 2.2.1), ядро идентифицирует номер дискового индекса по его место-
положению в массиве. В дисковом индексе это поле не нужно.
* Указатели на другие индексы в памяти. Ядро связывает индексы в хеш-оче-
реди и включает их в список свободных индексов подобно тому, как связы-
вает буферы в буферные хеш-очереди и включает их в список свободных бу-
феров. Хеш-очередь идентифицируется в соответствии с логическим номером
устройства и номером индекса. Ядро может располагать в памяти не более
одной копии данного дискового индекса, но индексы могут находиться од-
новременно как в хеш-очереди, так и в списке свободных индексов.
* Счетчик ссылок, означающий количество активных экземпляров файла (таких,
которые открыты).
Многие поля в копии индекса, с которой ядро работает в памяти, анало-
гичны полям в заголовке буфера, и управление индексами похоже на управление
буферами. Индекс так же блокируется, в результате чего другим процессам зап-
рещается работа с ним; эти процессы устанавливают в индексе специальный
флаг, возвещающий о том, что выполнение обратившихся к индексу процессов
следует возобновить, как только блокировка будет снята. Установкой других
флагов ядро отмечает противоречия между дисковым индексом и его копией в па-
мяти. Когда ядру нужно будет записать изменения в файл или индекс, ядро пе-
репишет копию индекса из памяти на диск только после проверки этих флагов.
Наиболее разительным различием между копией индекса в памяти и заголов-
ком буфера является наличие счетчика ссылок, подсчитывающего количество ак-
тивных экземпляров файла. Индекс активен, когда процесс выделяет его, напри-
мер, при открытии файла. Индекс находится в списке свободных индексов, толь-
ко если значение его счетчика ссылок равно 0, и это значит, что ядро может
переназначить свободный индекс в памяти другому дисковому индексу. Таким об-
разом, список свободных индексов выступает в роли кеша для неактивных индек-
сов. Если процесс пытается обратиться к файлу, чей индекс в этот момент от-
сутствует в индексном пуле, ядро переназначает свободный индекс из списка
для использования этим процессом. С другой стороны, у буфера нет счетчика
ссылок; он находится в списке свободных буферов тогда и только тогда, когда
он разблокирован.
E4.1.2 Обращение к индексамF
Ядро идентифицирует индексы по имени файловой системы и номеру индекса и
выделяет индексы в памяти по запросам соответствующих алгоритмов. Алгоритм
iget назначает индексу место для копии в памяти (Рисунок 4.3); он почти
идентичен алгоритму getblk для поиска дискового блока в буферном кеше. Ядро
преобразует номера устройства и индекса в имя хеш-очереди и просматривает
эту хеш-очередь в поисках индекса. Если индекс не обнаружен, ядро выделяет
61
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДї
і алгоритм iget і
і входная информация: номер индекса в файловой системе і
і выходная информация: заблокированный индекс і
і { і
і выполнить і
і { і
і если (индекс в индексном кеше) і
і { і
і если (индекс заблокирован) і
і { і
і приостановиться (до освобождения индекса); і
і продолжить; /* цикл с условием продолжения */ і
і } і
і /* специальная обработка для точек монтирования і
і (глава 5) */ і
і если (индекс в списке свободных индексов) і
і убрать из списка свободных индексов; і
і увеличить счетчик ссылок для индекса; і
і возвратить (индекс); і
і } і
і /* индекс отсутствует в индексном кеше */ і
і если (список свободных индексов пуст) і
і возвратить (ошибку); і
і убрать новый индекс из списка свободных индексов; і
і сбросить номер индекса и файловой системы; і
і убрать индекс из старой хеш-очереди, поместить в новую;і
і считать индекс с диска (алгоритм bread); і
і инициализировать индекс (например, установив счетчик і
і ссылок в 1); і
і возвратить (индекс); і
і } і
і } і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
Рисунок 4.3. Алгоритм выделения индексов в памяти
его из списка свободных индексов и блокирует его. Затем ядро готовится к
чтению с диска в память индекса, к которому оно обращается. Ядро уже знает
номера индекса и логического устройства и вычисляет номер логического блока
на диске, содержащего индекс, с учетом того, сколько дисковых индексов поме-
щается в одном дисковом блоке. Вычисления производятся по формуле
номер блока = ((номер индекса - 1) / число индексов в блоке) +
+ начальный блок в списке индексов
где операция деления возвращает целую часть частного. Например, предположим,
что блок 2 является начальным в списке индексов и что в каждом блоке помеща-
ются 8 индексов, тогда индекс с номером 8 находится в блоке 2, а индекс с
номером 9 - в блоке 3. Если же в дисковом блоке помещаются 16 индексов, тог-
да индексы с номерами 8 и 9 располагаются в дисковом блоке с номером 2, а
индекс с номером 17 является первым индексом в дисковом блоке 3.
Если ядро знает номера устройства и дискового блока, оно читает блок,
используя алгоритм bread (глава 2), затем вычисляет смещение индекса в бай-
тах внутри блока по формуле:
((номер индекса - 1) модуль (число индексов в блоке)) *
* размер дискового индекса
62
Например, если каждый дисковый индекс занимает 64 байта и в блоке помещаются
8 индексов, тогда индекс с номером 8 имеет адрес со смещением 448 байт от
начала дискового блока. Ядро убирает индекс в памяти из списка свободных ин-
дексов, помещает его в соответствующую хеш-очередь и устанавливает значение
счетчика ссылок равным 1. Ядро переписывает поля типа файла и владельца фай-
ла, установки прав доступа, число указателей на файл, размер файла и таблицу
адресов из дискового индекса в память и возвращает заблокированный в памяти
индекс.
Ядро манипулирует с блокировкой индекса и счетчиком ссылок независимо
один от другого. Блокировка - это установка, которая действует на время вы-
полнения системного вызова и имеет целью запретить другим процессам обра-
щаться к индексу пока тот в работе (и возможно хранит противоречивые дан-
ные). Ядро снимает блокировку по окончании обработки системного вызова: бло-
кировка индекса никогда не выходит за границы системного вызова. Ядро увели-
чивает значение счетчика ссылок с появлением каждой активной ссылки на файл.
Например, в разделе 5.1 будет показано, как ядро увеличивает значение счет-
чика ссылок тогда, когда процесс открывает файл. Оно уменьшает значение
счетчика ссылок только тогда, когда ссылка становится неактивной, например,
когда процесс закрывает файл. Таким образом, установка счетчика ссылок сох-
раняется для множества системных вызовов. Блокировка снимается между двумя
обращениями к операционной системе, чтобы позволить процессам одновременно
производить разделенный доступ к файлу; установка счетчика ссылок действует
между обращениями к операционной системе, чтобы предупредить переназначение
ядром активного в памяти индекса. Таким образом, ядро может заблокировать и
разблокировать выделенный индекс независимо от значения счетчика ссылок. Вы-
делением и освобождением индексов занимаются и отличные от open системные
операции, в чем мы и убедимся в главе 5.
Возвращаясь к алгоритму iget, заметим, что если ядро пытается взять ин-
декс из списка свободных индексов и обнаруживает список пустым, оно сообщает
об ошибке. В этом отличие от идеологии, которой следует ядро при работе с
дисковыми буферами, где процесс приостанавливает свое выполнение до тех пор,
пока буфер не освободится. Процессы контролируют выделение индексов на поль-
зовательском уровне посредством запуска системных операций open и close и
поэтому ядро не может гарантировать момент, когда индекс станет доступным.
Следовательно, процесс, приостанавливающий свое выполнение в ожидании осво-
бождения индекса, может никогда не возобновиться. Ядро скорее прервет выпол-
нение системного вызова, чем оставит такой процесс в "зависшем" состоянии.
Однако, процессы не имеют такого контроля над буферами. Поскольку процесс не
может удержать буфер заблокированным в течение выполнения нескольких систем-
ных операций, ядро здесь может гарантировать скорое освобождение буфера, и
процесс поэтому приостанавливается до того момента, когда он станет доступ-
ным.
В предшествующих параграфах рассматривался случай, когда ядро выделяет
индекс, отсутствующий в индексном кеше. Если индекс находится в кеше, про-
цесс (A) обнаружит его в хеш-очереди и проверит, не заблокирован ли индекс
другим процессом (B). Если индекс заблокирован, процесс A приостанавливается
и выставляет флаг у индекса в памяти, показывая, что он ждет освобождения
индекса. Когда позднее процесс B разблокирует индекс, он "разбудит" все про-
цессы (включая процесс A), ожидающие освобождения индекса. Когда же наконец
процесс A сможет использовать индекс, он заблокирует его, чтобы другие про-
цессы не могли к нему обратиться. Если первоначально счетчик ссылок имел
значение, равное 0, индекс также появится в списке свободных индексов, поэ-
тому ядро уберет его оттуда: индекс больше не является свободным. Ядро уве-
личивает значение счетчика ссылок и возвращает заблокированный индекс.
Если суммировать все вышесказанное, можно отметить, что алгоритм iget
имеет отношение к начальной стадии системных вызовов, когда процесс впервые
обращается к файлу. Этот алгоритм возвращает заблокированную индексную
структуру со значением счетчика ссылок, на 1 большим, чем оно было раньше.
Индекс в памяти содержит текущую информацию о состоянии файла. Ядро снимает
63
блокировку с индекса перед выходом из системной операции, поэтому другие
системные вызовы могут обратиться к индексу, если пожелают. В главе 5 расс-
матриваются эти случаи более подробно.
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДї
і алгоритм iput /* разрешение доступа к индексу в памяти */і
і входная информация: указатель на индекс в памяти і
і выходная информация: отсутствует і
і { і
і заблокировать индекс если он еще не заблокирован; і
і уменьшить на 1 счетчик ссылок для индекса; і
і если (значение счетчика ссылок == 0) і
і { і
і если (значение счетчика связей == 0) і
і { і
і освободить дисковые блоки для файла (алгоритм і
і free, раздел 4.7); і
і установить тип файла равным 0; і
і освободить индекс (алгоритм ifree, раздел 4.6); і
і } і
і если (к файлу обращались или изменился индекс или і
і изменилось содержимое файла) і
і скорректировать дисковый индекс; і
і поместить индекс в список свободных индексов; і
і } і
і снять блокировку с индекса; і
і } і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
Рисунок 4.4. Освобождение индекса
E4.1.3 Освобождение индексовF
В том случае, когда ядро освобождает индекс (алгоритм iput, Рисунок
4.4), оно уменьшает значение счетчика ссылок для него. Если это значение
становится равным 0, ядро переписывает индекс на диск в том случае, когда
копия индекса в памяти отличается от дискового индекса. Они различаются, ес-
ли изменилось содержимое файла, если к файлу производилось обращение или ес-
ли изменились владелец файла либо права доступа к файлу. Ядро помещает ин-
декс в список свободных индексов, наиболее эффективно располагая индекс в
кеше на случай, если он вскоре понадобится вновь. Ядро может также освобо-
дить все связанные с файлом информационные блоки и индекс, если число ссылок
на файл равно 0.
E4.2 СТРУКТУРА ФАЙЛА ОБЫЧНОГО ТИПАF
Как уже говорилось, индекс включает в себя таблицу адресов расположения
информации файла на диске. Так как каждый блок на диске адресуется по своему
номеру, в этой таблице хранится совокупность номеров дисковых блоков. Если
бы данные файла занимали непрерывный участок на диске (то есть файл занимал
бы линейную последовательность дисковых блоков), то для обращения к данным в
файле было бы достаточно хранить в индексе адрес начального блока и размер
файла. Однако, такая стратегия размещения данных не позволяет осуществлять
простое расширение и сжатие файлов в файловой системе без риска фрагментации
свободного пространства памяти на диске. Более того, ядру пришлось бы выде-
лять и резервировать непрерывное пространство в файловой системе перед вы-
64
полнением операций, могущих привести к увеличению размера файла.
ДДДДДДДДДДДДДВДДДДДДДДДДВДДДДДДДДДДВДДДДДДДДДДВДДДДДДДДДДДДД
щщщщщщщщщщ і Файл A і Файл B і Файл C і щщщщщщщщщщщ
ДДДДДДДДДДДДДБДДДДДДДДДДБДДДДДДДДДДБДДДДДДДДДДБДДДДДДДДДДДДД
40 50 60 70
Адреса блоков
ДДДДДДДДДДДДДВДДДДДДДДДДВДДДДДДДДДДВДДДДДДДДДДВДДДДДДДДДВДДД
щщщщщщщщщщ і Файл A і Свободны і Файл C і Файл B і щщ
ДДДДДДДДДДДДДБДДДДДДДДДДБДДДДДДДДДДБДДДДДДДДДДБДДДДДДДДДБДДД
40 50 60 70 81
Адреса блоков
Рисунок 4.5. Размещение непрерывных файлов и фрагментация
свободного пространства
Предположим, например, что пользователь создает три файла, A, B и C,
каждый из которых занимает 10 дисковых блоков, а также что система выделила
для размещения этих трех файлов непрерывное место. Если потом пользователь
захочет добавить 5 блоков с информацией к среднему файлу, B, ядру придется
скопировать файл B в то место в файловой системе, где найдется окно размером
15 блоков. В дополнение к затратам ресурсов на проведение этой операции дис-
ковые блоки, занимаемые информацией файла B, станут неиспользуемыми, если
только они не понадобятся файлам размером не более 10 блоков (Рисунок 4.5).
Ядро могло бы минимизировать фрагментацию пространства памяти, периодически
запуская процедуры чистки памяти, уплотняющие имеющуюся память, но это пот-
ребовало бы дополнительного расхода временных и системных ресурсов.
В целях повышения гибкости ядро присоединяет к файлу по одному блоку,
позволяя информации файла быть разбросанной по всей файловой системе. Но та-
кая схема размещения усложняет задачу поиска данных. Таблица адресов содер-
жит список номеров блоков, содержащих принадлежащую файлу информацию, однако
простые вычисления показывают, что линейным списком блоков файла в индексе
трудно управлять. Если логический блок занимает 1 Кбайт, то файлу, состояще-
му из 10 Кбайт, потребовался бы индекс на 10 номеров блоков, а файлу, состо-
ящему из 100 Кбайт, понадобился бы индекс на 100 номеров блоков. Либо пусть
размер индекса будет варьироваться в зависимости от размера файла, либо
пришлось бы установить относительно жесткое ограничение на размер файла.
Для того, чтобы небольшая структура индекса позволяла работать с больши-
ми файлами, таблица адресов дисковых блоков приводится в соответствие со
структурой, представленной на Рисунке 4.6. Версия V системы UNIX работает с
13 точками входа в таблицу адресов индекса, но принципиальные моменты не за-
висят от количества точек входа. Блок, имеющий пометку "прямая адресация" на
рисунке, содержит номера дисковых блоков, в которых хранятся реальные дан-
ные. Блок, имеющий пометку "одинарная косвенная адресация", указывает на
блок, содержащий список номеров блоков прямой адресации. Чтобы обратиться к
данным с помощью блока косвенной адресации, ядро должно считать этот блок,
найти соответствующий вход в блок прямой адресации и, считав блок прямой ад-
ресации, обнаружить данные. Блок, имеющий пометку "двойная косвенная адреса-
ция", содержит список номеров блоков одинарной косвенной адресации, а блок,
имеющий пометку "тройная косвенная адресация", содержит список номеров бло-
ков двойной косвенной адресации.
В принципе, этот метод можно было бы распространить и на поддержку бло-
ков четверной косвенной адресации, блоков пятерной косвенной адресации и так
далее, но на практике оказывается достаточно имеющейся структуры. Предполо-
жим, что размер логического блока в файловой системе 1 Кбайт и что номер
блока занимает 32 бита (4 байта). Тогда в блоке может храниться до 256 номе-
ров блоков. Расчеты показывают (Рисунок 4.7), что максимальный размер файла
65
превышает 16 Гбайт, если использовать в индексе 10 блоков прямой адресации и
1 одинарной косвенной адресации, 1 двойной косвенной адресации и 1 тройной
косвенной адресации. Если же учесть, что длина поля "размер файла" в индексе
- 32 бита, то размер файла в действительности ограничен 4 Гбайтами (2 в сте-
пени 32).
Процессы обращаются к информации в файле, задавая смещение в байтах. Они
рассматривают файл как поток байтов и ведут подсчет байтов, начиная с нуле-
вого адреса и заканчивая адресом, равным размеру файла. Ядро переходит от
байтов к блокам: файл начинается с нулевого логического блока и заканчивает-
ся блоком, номер которого определяется исходя из размера файла. Ядро обраща-
ется к индексу и превращает логический блок, принадлежащий файлу, в соответ-
Информацион-
Индекс ные блоки
ЪДДДДДДДДДДДДДї ЪДДДДДї
і прямой адр. ГДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД>і і
і 0і і і
ГДДДДДДДДДДДДДґ АДДДДДЩ
і прямой адр. ГДДДДДДДДДДДДДДДДДї ЪДДДДДї
і 1і АДДДДДДДДДДДДДДДДД>і і
ГДДДДДДДДДДДДДґ і і
і прямой адр. ГДДДДДДДДДДДДДДДДДї АДДДДДЩ
і 2і і ЪДДДДДї
ГДДДДДДДДДДДДДґ АДДДДДДДДДДДДДДДДД>і і
і прямой адр. ГДДДДДДДДДДДДДДДДДї і і
і 3і і АДДДДДЩ
ГДДДДДДДДДДДДДґ і ЪДДДДДї
і прямой адр. і АДДДДДДДДДДДДДДДДД>і і
і 4і і і
ГДДДДДДДДДДДДДґ АДДДДДЩ
і прямой адр. і щ
і 5і щ
ГДДДДДДДДДДДДДґ щ
і прямой адр. і щ
і 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
E4.3 КАТАЛОГИF
Из главы 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 показана разница между чтением и поиском в каталоге.
E4.4 ПРЕВРАЩЕНИЕ СОСТАВНОГО ИМЕНИ ФАЙЛА (ПУТИ ПОИСКА)F
EВ ИДЕНТИФИКАТОР ИНДЕКСАF
Начальное обращение к файлу производится по его составному имени (имени
пути поиска), как в командах 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 не работали
еще на машинах с большим объемом памяти, поэтому значительный упор был сде-
лан на простые алгоритмы, такие как алгоритмы линейного поиска. Более слож-
ные схемы поиска потребовали бы отличной, более сложной, структуры каталога,
и возможно работали бы медленнее даже в небольших каталогах по сравнению со
схемой линейного поиска.
E4.5 СУПЕРБЛОКF
До сих пор в этой главе описывалась структура файла, при этом предпола-
галось, что индекс предварительно связывался с файлом и что уже были опреде-
лены дисковые блоки, содержащие информацию. В следующих разделах описывает-
ся, каким образом ядро назначает индексы и дисковые блоки. Чтобы понять эти
алгоритмы, рассмотрим структуру суперблока.
Суперблок состоит из следующих полей:
* размер файловой системы,
* количество свободных блоков в файловой системе,
* список свободных блоков, имеющихся в файловой системе,
* индекс следующего свободного блока в списке свободных блоков,
* размер списка индексов,
* количество свободных индексов в файловой системе,
* список свободных индексов в файловой системе,
* следующий свободный индекс в списке свободных индексов,
* заблокированные поля для списка свободных блоков и свободных индексов,
* флаг, показывающий, что в суперблок были внесены изменения.
В оставшейся части главы будет объяснено, как пользоваться массивами,
указателями и замками блокировки. Ядро периодически переписывает суперблок
на диск, если в суперблок были внесены изменения, для того, чтобы обеспечи-
валась согласованность с данными, хранящимися в файловой системе.
E4.6 НАЗНАЧЕНИЕ ИНДЕКСА НОВОМУ ФАЙЛУF
Для выделения известного индекса, то есть индекса, для которого предва-
рительно определен собственный номер (и номер файловой системы), ядро ис-
пользует алгоритм 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
описана в предыдущем параграфе. Сходным образом, если процесс, освобождая
индекс, не проверил наличие блокировки списка, он может затереть номера ин-
дексов уже в списке свободных индексов, пока другой процесс будет заполнять
этот список информацией с диска. И опять участится конкуренция вышеописанно-
го типа. Несмотря на то, что ядро более или менее удачно управляется с ней,
производительность системы снижается. Установка блокировки для списка сво-
бодных индексов в суперблоке устраняет такую конкуренцию.
E4.7 ВЫДЕЛЕНИЕ ДИСКОВЫХ БЛОКОВF
Когда процесс записывает данные в файл, ядро должно выделять из файловой
системы дисковые блоки под информационные блоки прямой адресации и иногда
под блоки косвенной адресации. Суперблок файловой системы содержит массив,
используемый для хранения номеров свободных дисковых блоков в файловой сис-
теме. Сервисная программа 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. Запрашивание и освобождение дисковых блоков
E4.8 ДРУГИЕ ТИПЫ ФАЙЛОВF
В системе UNIX поддерживаются и два других типа файлов: каналы и специ-
альные файлы. Канал, иногда называемый fifo (сокращенно от
"first-in-first-out" - "первым пришел - первым вышел" - поскольку обслужива-
ет запросы в порядке поступления), отличается от обычного файла тем, что со-
держит временные данные: информация, однажды считанная из канала, не может
быть прочитана вновь. Кроме того, информация читается в том порядке, в кото-
ром она была записана в канале, и система не допускает никаких отклонений от
данного порядка. Способ хранения ядром информации в канале не отличается от
способа ее хранения в обычном файле, за исключением того, что здесь исполь-
зуются только блоки прямой, а не косвенной, адресации. Конкретное представ-
ление о каналах можно будет получить в следующей главе.
Последним типом файлов в системе UNIX являются специальные файлы, к ко-
торым относятся специальные файлы устройств ввода-вывода блоками и специаль-
ные файлы устройств посимвольного ввода-вывода. Оба подтипа обозначают уст-
ройства, и поэтому индексы таких файлов не связаны ни с какой информацией.
Вместо этого индекс содержит два номера - старший и младший номера устройст-
ва. Старший номер устройства указывает его тип, например, терминал или диск,
а младший номер устройства - числовой код, идентифицирующий устройство в
группе однородных устройств. Более подробно специальные файлы устройств рас-
сматриваются в главе 10.
E4.9 ВЫВОДЫF
Индекс представляет собой структуру данных, в которой описываются атри-
буты файла, в том числе расположение информации файла на диске. Существует
две разновидности индекса: копия на диске, в которой хранится информация ин-
декса, пока файл находится в работе, и копия в памяти, где хранится информа-
ция об активных файлах. Алгоритмы 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
|