Страница:
Как уже было замечено в главе 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 назначают и освобождают для файлов индексы.
Индексы существуют на диске в статической форме и ядро считывает их в
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, и это значит, что ядро может
переназначить свободный индекс в памяти другому дисковому индексу. Таким об-
разом, список свободных индексов выступает в роли кеша для неактивных индек-
сов. Если процесс пытается обратиться к файлу, чей индекс в этот момент от-
сутствует в индексном пуле, ядро переназначает свободный индекс из списка
для использования этим процессом. С другой стороны, у буфера нет счетчика
ссылок; он находится в списке свободных буферов тогда и только тогда, когда
он разблокирован.
Ядро идентифицирует индексы по имени файловой системы и номеру индекса и
выделяет индексы в памяти по запросам соответствующих алгоритмов. Алгоритм
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. Освобождение индекса
В том случае, когда ядро освобождает индекс (алгоритм iput, Рисунок
4.4), оно уменьшает значение счетчика ссылок для него. Если это значение
становится равным 0, ядро переписывает индекс на диск в том случае, когда
копия индекса в памяти отличается от дискового индекса. Они различаются, ес-
ли изменилось содержимое файла, если к файлу производилось обращение или ес-
ли изменились владелец файла либо права доступа к файлу. Ядро помещает ин-
декс в список свободных индексов, наиболее эффективно располагая индекс в
кеше на случай, если он вскоре понадобится вновь. Ядро может также освобо-
дить все связанные с файлом информационные блоки и индекс, если число ссылок
на файл равно 0.
Как уже говорилось, индекс включает в себя таблицу адресов расположения
информации файла на диске. Так как каждый блок на диске адресуется по своему
номеру, в этой таблице хранится совокупность номеров дисковых блоков. Если
бы данные файла занимали непрерывный участок на диске (то есть файл занимал
бы линейную последовательность дисковых блоков), то для обращения к данным в
файле было бы достаточно хранить в индексе адрес начального блока и размер
файла. Однако, такая стратегия размещения данных не позволяет осуществлять
простое расширение и сжатие файлов в файловой системе без риска фрагментации
свободного пространства памяти на диске. Более того, ядру пришлось бы выде-
лять и резервировать непрерывное пространство в файловой системе перед вы-
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| -
+-------------+ -
| прямой адр. | -
кальный индекс. Индекс содержит информацию, необходимую любому процессу для
того, чтобы обратиться к файлу, например, права собственности на файл, права
доступа к файлу, размер файла и расположение данных файла в файловой систе-
ме. Процессы обращаются к файлам, используя четко определенный набор систем-
ных вызовов и идентифицируя файл строкой символов, выступающих в качестве
составного имени файла. Каждое составное имя однозначно определяет файл,
благодаря чему ядро системы преобразует это имя в индекс файла.
Эта глава посвящена описанию внутренней структуры файлов в операционной
системе 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 назначают и освобождают для файлов индексы.
Индексы существуют на диске в статической форме и ядро считывает их в
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, и это значит, что ядро может
переназначить свободный индекс в памяти другому дисковому индексу. Таким об-
разом, список свободных индексов выступает в роли кеша для неактивных индек-
сов. Если процесс пытается обратиться к файлу, чей индекс в этот момент от-
сутствует в индексном пуле, ядро переназначает свободный индекс из списка
для использования этим процессом. С другой стороны, у буфера нет счетчика
ссылок; он находится в списке свободных буферов тогда и только тогда, когда
он разблокирован.
Ядро идентифицирует индексы по имени файловой системы и номеру индекса и
выделяет индексы в памяти по запросам соответствующих алгоритмов. Алгоритм
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. Освобождение индекса
В том случае, когда ядро освобождает индекс (алгоритм iput, Рисунок
4.4), оно уменьшает значение счетчика ссылок для него. Если это значение
становится равным 0, ядро переписывает индекс на диск в том случае, когда
копия индекса в памяти отличается от дискового индекса. Они различаются, ес-
ли изменилось содержимое файла, если к файлу производилось обращение или ес-
ли изменились владелец файла либо права доступа к файлу. Ядро помещает ин-
декс в список свободных индексов, наиболее эффективно располагая индекс в
кеше на случай, если он вскоре понадобится вновь. Ядро может также освобо-
дить все связанные с файлом информационные блоки и индекс, если число ссылок
на файл равно 0.
Как уже говорилось, индекс включает в себя таблицу адресов расположения
информации файла на диске. Так как каждый блок на диске адресуется по своему
номеру, в этой таблице хранится совокупность номеров дисковых блоков. Если
бы данные файла занимали непрерывный участок на диске (то есть файл занимал
бы линейную последовательность дисковых блоков), то для обращения к данным в
файле было бы достаточно хранить в индексе адрес начального блока и размер
файла. Однако, такая стратегия размещения данных не позволяет осуществлять
простое расширение и сжатие файлов в файловой системе без риска фрагментации
свободного пространства памяти на диске. Более того, ядру пришлось бы выде-
лять и резервировать непрерывное пространство в файловой системе перед вы-
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| -
+-------------+ -
| прямой адр. | -