The design of the unix operating system by Maurice J
| Вид материала | Реферат |
| 4.2 Структура файла обычного типа 4.4 Превращение составного имени файла (пути поиска) в иден |
- Лекция 10. Файловые системы Unix, 116.79kb.
- Уровни рассмотрения, 314.07kb.
- Курс по операционным системам (на примере ос windows) Основан на учебном курсе Windows, 29.21kb.
- Выполнил ученик 11 «А» класса, 443.51kb.
- Ос лекция 1 (2-й семестр – временно), 101.4kb.
- Operating System, 7686.97kb.
- Unix-подобные операционные системы, характеристики, особенности, разновидности, 40.63kb.
- 1. ms sql server. Общие сведения, 66.03kb.
- Shanti ananda maurice, 89.84kb.
- Методические материалы, 3002.45kb.
внутренней структуры обычных файлов и некоторых моментов, связан-
ных с чтением и записью ядром информации файлов. В разделе 4.3
исследуется строение каталогов - структур данных, позволяющих яд-
ру организовывать файловую систему в виде иерархии файлов, раздел
4.4 содержит алгоритм преобразования имен пользовательских файлов
в индексы. В разделе 4.5 дается структура суперблока, а в разде-
лах 4.6 и 4.7 представлены алгоритмы назначения файлам дисковых
индексов и дисковых блоков. Наконец, в разделе 4.8 идет речь о
других типах файлов в системе, а именно о каналах и файлах уст-
ройств.
Алгоритмы, описанные в этой главе, уровнем выше по сравнению
с алгоритмами управления буферным кешем, рассмотренными в преды-
дущей главе (Рисунок 4.1). Алгоритм iget возвращает последний из
идентифицированных индексов с возможностью считывания его с дис-
ка, используя буферный кеш, а алгоритм iput освобождает индекс.
Алгоритм bmap устанавливает параметры ядра, связанные с обращени-
ем к файлу. Алгоритм namei преобразует составное имя пользова-
тельского файла в имя индекса, используя алгоритмы iget, iput и
Алгоритмы работы с файловой системой на нижнем уровне
---------------------T------------------T-----------------┐
│ namei │ │ │
+--------------------+ alloc free │ ialloc ifree │
│ iget iput bmap │ │ │
+--------------------+------------------+-----------------+
+---------------------------------------------------------+
│ алгоритмы работы с буферами │
+---------------------------------------------------------+
│ getblk brelse bread breada bwrite │
L----------------------------------------------------------
Рисунок 4.1. Алгоритмы файловой системы
bmap. Алгоритмы alloc и free выделяют и освобождают дисковые бло-
ки для файлов, алгоритмы ialloc и ifree назначают и освобождают
для файлов индексы.
4.1 ИНДЕКСЫ
4.1.1 Определение
Индексы существуют на диске в статической форме и ядро считы-
вает их в память прежде, чем начать с ними работать. Дисковые ин-
дексы включают в себя следующие поля:
* Идентификатор владельца файла. Права собственности разделены
между индивидуальным владельцем и "групповым" и тем самым по-
могают определить круг пользователей, имеющих права доступа к
файлу. Суперпользователь имеет право доступа ко всем файлам в
системе.
* Тип файла. Файл может быть файлом обычного типа, каталогом,
специальным файлом, соответствующим устройствам ввода-вывода
символами или блоками, а также абстрактным файлом канала (ор-
ганизующим обслуживание запросов в порядке поступления, "пер-
вым пришел - первым вышел").
* Права доступа к файлу. Система разграничивает права доступа к
файлу для трех классов пользователей: индивидуального вла-
дельца файла, группового владельца и прочих пользователей;
каждому классу выделены определенные права на чтение, запись
и исполнение файла, которые устанавливаются индивидуально.
Поскольку каталоги как файлы не могут быть исполнены, разре-
шение на исполнение в данном случае интерпретируется как пра-
во производить поиск в каталоге по имени файла.
* Календарные сведения, характеризующие работу с файлом: время
внесения последних изменений в файл, время последнего обраще-
ния к файлу, время внесения последних изменений в индекс.
* Число указателей на файл, означающее количество имен, исполь-
зуемых при поиске файла в иерархии каталогов. Указатели на
файл подробно рассматриваются в главе 5.
* Таблица адресов на диске, в которых располагается информация
файла. Хотя пользователи трактуют информацию в файле как ло-
гический поток байтов, ядро располагает эти данные в несопри-
касающихся дисковых блоках. Дисковые блоки, содержащие инфор-
мацию файла, указываются в индексе.
* Размер файла. Данные в файле адресуются с помощью смещения в
байтах относительно начала файла, начиная со смещения, равно-
го 0, поэтому размер файла в байтах на 1 больше максимального
смещения. Например, если пользователь создает файл и записы-
вает только 1 байт информации по адресу со смещением 1000 от
начала файла, размер файла составит 1001 байт.
В индексе отсутствует составное имя файла, необходимое для
осуществления доступа к файлу.
----------------------------------------┐
│ владелец mjb │
│ группа os │
│ тип - обычный файл │
│ права доступа rwxr-xr-x │
│ последнее обращение 23 Окт 1984 13:45 │
│ последнее изменение 22 Окт 1984 10:30 │
│ коррекция индекса 23 Окт 1984 13:30 │
│ размер 6030 байт │
│ дисковые адреса │
L----------------------------------------
Рисунок 4.2. Пример дискового индекса
На Рисунке 4.2 показан дисковый индекс некоторого файла. Этот
индекс принадлежит обычному файлу, владелец которого - "mjb" и
размер которого - 6030 байт. Система разрешает пользователю
"mjb" производить чтение, запись и исполнение файла; членам груп-
пы "os" и всем остальным пользователям разрешается только читать
или исполнять файл, но не записывать в него данные. Последний раз
файл был прочитан 23 октября 1984 года в 13:45, запись последний
раз производилась 22 октября 1984 года в 10:30. Индекс изменялся
последний раз 23 октября 1984 года в 13:30, хотя никакая информа-
ция в это время в файл не записывалась. Ядро кодирует все вышепе-
речисленные данные в индексе. Обратите внимание на различие в за-
писи на диск содержимого индекса и содержимого файла. Содержимое
файла меняется только тогда, когда в файл производится запись.
Содержимое индекса меняется как при изменении содержимого файла,
так и при изменении владельца файла, прав доступа и набора указа-
телей. Изменение содержимого файла автоматически вызывает коррек-
цию индекса, однако коррекция индекса еще не означает изменения
содержимого файла.
Копия индекса в памяти, кроме полей дискового индекса, вклю-
чает в себя и следующие поля:
* Состояние индекса в памяти, отражающее
- заблокирован ли индекс,
- ждет ли снятия блокировки с индекса какой-либо процесс,
- отличается ли представление индекса в памяти от своей дис-
ковой копии в результате изменения содержимого индекса,
- отличается ли представление индекса в памяти от своей дис-
ковой копии в результате изменения содержимого файла,
- находится ли файл в верхней точке (см. раздел 5.15).
* Логический номер устройства файловой системы, содержащей файл.
* Номер индекса. Так как индексы на диске хранятся в линейном
массиве (см. раздел 2.2.1), ядро идентифицирует номер диско-
вого индекса по его местоположению в массиве. В дисковом ин-
дексе это поле не нужно.
* Указатели на другие индексы в памяти. Ядро связывает индексы
в хеш-очереди и включает их в список свободных индексов по-
добно тому, как связывает буферы в буферные хеш-очереди и
включает их в список свободных буферов. Хеш-очередь идентифи-
цируется в соответствии с логическим номером устройства и но-
мером индекса. Ядро может располагать в памяти не более одной
копии данного дискового индекса, но индексы могут находиться
одновременно как в хеш-очереди, так и в списке свободных ин-
дексов.
* Счетчик ссылок, означающий количество активных экземпляров
файла (таких, которые открыты).
Многие поля в копии индекса, с которой ядро работает в памя-
ти, аналогичны полям в заголовке буфера, и управление индексами
похоже на управление буферами. Индекс так же блокируется, в ре-
зультате чего другим процессам запрещается работа с ним; эти про-
цессы устанавливают в индексе специальный флаг, возвещающий о
том, что выполнение обратившихся к индексу процессов следует во-
зобновить, как только блокировка будет снята. Установкой других
флагов ядро отмечает противоречия между дисковым индексом и его
копией в памяти. Когда ядру нужно будет записать изменения в файл
или индекс, ядро перепишет копию индекса из памяти на диск только
после проверки этих флагов.
Наиболее разительным различием между копией индекса в памяти
и заголовком буфера является наличие счетчика ссылок, подсчитыва-
ющего количество активных экземпляров файла. Индекс активен, ког-
да процесс выделяет его, например, при открытии файла. Индекс на-
ходится в списке свободных индексов, только если значение его
счетчика ссылок равно 0, и это значит, что ядро может переназна-
чить свободный индекс в памяти другому дисковому индексу. Таким
образом, список свободных индексов выступает в роли кеша для не-
активных индексов. Если процесс пытается обратиться к файлу, чей
индекс в этот момент отсутствует в индексном пуле, ядро переназ-
начает свободный индекс из списка для использования этим процес-
сом. С другой стороны, у буфера нет счетчика ссылок; он находится
в списке свободных буферов тогда и только тогда, когда он разбло-
кирован.
-------------------------------------------------------------┐
│ алгоритм iget │
│ входная информация: номер индекса в файловой системе │
│ выходная информация: заблокированный индекс │
│ { │
│ выполнить │
│ { │
│ если (индекс в индексном кеше) │
│ { │
│ если (индекс заблокирован) │
│ { │
│ приостановиться (до освобождения индекса); │
│ продолжить; /* цикл с условием продолжения */ │
│ } │
│ /* специальная обработка для точек монтирования │
│ (глава 5) */ │
│ если (индекс в списке свободных индексов) │
│ убрать из списка свободных индексов; │
│ увеличить счетчик ссылок для индекса; │
│ возвратить (индекс); │
│ } │
│ /* индекс отсутствует в индексном кеше */ │
│ если (список свободных индексов пуст) │
│ возвратить (ошибку); │
│ убрать новый индекс из списка свободных индексов; │
│ сбросить номер индекса и файловой системы; │
│ убрать индекс из старой хеш-очереди, поместить в новую;│
│ считать индекс с диска (алгоритм bread); │
│ инициализировать индекс (например, установив счетчик │
│ ссылок в 1); │
│ возвратить (индекс); │
│ } │
│ } │
L-------------------------------------------------------------
Рисунок 4.3. Алгоритм выделения индексов в памяти
4.1.2 Обращение к индексам
Ядро идентифицирует индексы по имени файловой системы и номе-
ру индекса и выделяет индексы в памяти по запросам соответствую-
щих алгоритмов. Алгоритм iget назначает индексу место для копии в
памяти (Рисунок 4.3); он почти идентичен алгоритму getblk для по-
иска дискового блока в буферном кеше. Ядро преобразует номера ус-
тройства и индекса в имя хеш-очереди и просматривает эту хеш-оче-
редь в поисках индекса. Если индекс не обнаружен, ядро выделяет
его из списка свободных индексов и блокирует его. Затем ядро го-
товится к чтению с диска в память индекса, к которому оно обраща-
ется. Ядро уже знает номера индекса и логического устройства и
вычисляет номер логического блока на диске, содержащего индекс, с
учетом того, сколько дисковых индексов помещается в одном диско-
вом блоке. Вычисления производятся по формуле
номер блока = ((номер индекса - 1) / число индексов в блоке) +
+ начальный блок в списке индексов
где операция деления возвращает целую часть частного. Например,
предположим, что блок 2 является начальным в списке индексов и
что в каждом блоке помещаются 8 индексов, тогда индекс с номером
8 находится в блоке 2, а индекс с номером 9 - в блоке 3. Если же
в дисковом блоке помещаются 16 индексов, тогда индексы с номерами
8 и 9 располагаются в дисковом блоке с номером 2, а индекс с но-
мером 17 является первым индексом в дисковом блоке 3.
Если ядро знает номера устройства и дискового блока, оно чи-
тает блок, используя алгоритм bread (глава 2), затем вычисляет
смещение индекса в байтах внутри блока по формуле:
((номер индекса - 1) модуль (число индексов в блоке)) *
* размер дискового индекса
Например, если каждый дисковый индекс занимает 64 байта и в блоке
помещаются 8 индексов, тогда индекс с номером 8 имеет адрес со
смещением 448 байт от начала дискового блока. Ядро убирает индекс
в памяти из списка свободных индексов, помещает его в соответс-
твующую хеш-очередь и устанавливает значение счетчика ссылок рав-
ным 1. Ядро переписывает поля типа файла и владельца файла, уста-
новки прав доступа, число указателей на файл, размер файла и
таблицу адресов из дискового индекса в память и возвращает забло-
кированный в памяти индекс.
Ядро манипулирует с блокировкой индекса и счетчиком ссылок
независимо один от другого. Блокировка - это установка, которая
действует на время выполнения системного вызова и имеет целью
запретить другим процессам обращаться к индексу пока тот в работе
(и возможно хранит противоречивые данные). Ядро снимает блокиров-
ку по окончании обработки системного вызова: блокировка индекса
никогда не выходит за границы системного вызова. Ядро увеличивает
значение счетчика ссылок с появлением каждой активной ссылки на
файл. Например, в разделе 5.1 будет показано, как ядро увеличива-
ет значение счетчика ссылок тогда, когда процесс открывает файл.
Оно уменьшает значение счетчика ссылок только тогда, когда ссылка
становится неактивной, например, когда процесс закрывает файл.
Таким образом, установка счетчика ссылок сохраняется для множест-
ва системных вызовов. Блокировка снимается между двумя обращения-
ми к операционной системе, чтобы позволить процессам одновременно
производить разделенный доступ к файлу; установка счетчика ссылок
действует между обращениями к операционной системе, чтобы предуп-
редить переназначение ядром активного в памяти индекса. Таким об-
разом, ядро может заблокировать и разблокировать выделенный ин-
декс независимо от значения счетчика ссылок. Выделением и осво-
бождением индексов занимаются и отличные от open системные опера-
ции, в чем мы и убедимся в главе 5.
Возвращаясь к алгоритму iget, заметим, что если ядро пытается
взять индекс из списка свободных индексов и обнаруживает список
пустым, оно сообщает об ошибке. В этом отличие от идеологии, ко-
торой следует ядро при работе с дисковыми буферами, где процесс
приостанавливает свое выполнение до тех пор, пока буфер не осво-
бодится. Процессы контролируют выделение индексов на пользова-
тельском уровне посредством запуска системных операций open и
close и поэтому ядро не может гарантировать момент, когда индекс
станет доступным. Следовательно, процесс, приостанавливающий свое
выполнение в ожидании освобождения индекса, может никогда не во-
зобновиться. Ядро скорее прервет выполнение системного вызова,
чем оставит такой процесс в "зависшем" состоянии. Однако, процес-
сы не имеют такого контроля над буферами. Поскольку процесс не
может удержать буфер заблокированным в течение выполнения нес-
кольких системных операций, ядро здесь может гарантировать скорое
освобождение буфера, и процесс поэтому приостанавливается до того
момента, когда он станет доступным.
В предшествующих параграфах рассматривался случай, когда ядро
выделяет индекс, отсутствующий в индексном кеше. Если индекс на-
ходится в кеше, процесс (A) обнаружит его в хеш-очереди и прове-
рит, не заблокирован ли индекс другим процессом (B). Если индекс
заблокирован, процесс A приостанавливается и выставляет флаг у
индекса в памяти, показывая, что он ждет освобождения индекса.
Когда позднее процесс B разблокирует индекс, он "разбудит" все
процессы (включая процесс A), ожидающие освобождения индекса.
Когда же наконец процесс A сможет использовать индекс, он забло-
кирует его, чтобы другие процессы не могли к нему обратиться. Ес-
ли первоначально счетчик ссылок имел значение, равное 0, индекс
также появится в списке свободных индексов, поэтому ядро уберет
его оттуда: индекс больше не является свободным. Ядро увеличивает
значение счетчика ссылок и возвращает заблокированный индекс.
Если суммировать все вышесказанное, можно отметить, что алго-
ритм iget имеет отношение к начальной стадии системных вызовов,
когда процесс впервые обращается к файлу. Этот алгоритм возвраща-
ет заблокированную индексную структуру со значением счетчика ссы-
лок, на 1 большим, чем оно было раньше. Индекс в памяти содержит
текущую информацию о состоянии файла. Ядро снимает блокировку с
индекса перед выходом из системной операции, поэтому другие сис-
темные вызовы могут обратиться к индексу, если пожелают. В главе
5 рассматриваются эти случаи более подробно.
-------------------------------------------------------------┐
│ алгоритм iput /* разрешение доступа к индексу в памяти */│
│ входная информация: указатель на индекс в памяти │
│ выходная информация: отсутствует │
│ { │
│ заблокировать индекс если он еще не заблокирован; │
│ уменьшить на 1 счетчик ссылок для индекса; │
│ если (значение счетчика ссылок == 0) │
│ { │
│ если (значение счетчика связей == 0) │
│ { │
│ освободить дисковые блоки для файла (алгоритм │
│ free, раздел 4.7); │
│ установить тип файла равным 0; │
│ освободить индекс (алгоритм ifree, раздел 4.6); │
│ } │
│ если (к файлу обращались или изменился индекс или │
│ изменилось содержимое файла) │
│ скорректировать дисковый индекс; │
│ поместить индекс в список свободных индексов; │
│ } │
│ снять блокировку с индекса; │
│ } │
L-------------------------------------------------------------
Рисунок 4.4. Освобождение индекса
4.1.3 Освобождение индексов
В том случае, когда ядро освобождает индекс (алгоритм iput,
Рисунок 4.4), оно уменьшает значение счетчика ссылок для него.
Если это значение становится равным 0, ядро переписывает индекс
на диск в том случае, когда копия индекса в памяти отличается от
дискового индекса. Они различаются, если изменилось содержимое
файла, если к файлу производилось обращение или если изменились
владелец файла либо права доступа к файлу. Ядро помещает индекс в
список свободных индексов, наиболее эффективно располагая индекс
в кеше на случай, если он вскоре понадобится вновь. Ядро может
также освободить все связанные с файлом информационные блоки и
индекс, если число ссылок на файл равно 0.
4.2 СТРУКТУРА ФАЙЛА ОБЫЧНОГО ТИПА
Как уже говорилось, индекс включает в себя таблицу адресов
расположения информации файла на диске. Так как каждый блок на
диске адресуется по своему номеру, в этой таблице хранится сово-
купность номеров дисковых блоков. Если бы данные файла занимали
непрерывный участок на диске (то есть файл занимал бы линейную
последовательность дисковых блоков), то для обращения к данным в
файле было бы достаточно хранить в индексе адрес начального блока
и размер файла. Однако, такая стратегия размещения данных не поз-
воляет осуществлять простое расширение и сжатие файлов в файловой
системе без риска фрагментации свободного пространства памяти на
диске. Более того, ядру пришлось бы выделять и резервировать неп-
рерывное пространство в файловой системе перед выполнением опера-
ций, могущих привести к увеличению размера файла.
-------------T----------T----------T----------T-------------
│ Файл A │ Файл B │ Файл C │
-------------+----------+----------+----------+-------------
40 50 60 70
Адреса блоков
-------------T----------T----------T----------T---------T---
│ Файл 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), что максимальный размер
файла превышает 16 Гбайт, если использовать в индексе 10 блоков
прямой адресации и 1 одинарной косвенной адресации, 1 двойной
косвенной адресации и 1 тройной косвенной адресации. Если же
учесть, что длина поля "размер файла" в индексе - 32 бита, то
размер файла в действительности ограничен 4 Гбайтами (2 в степени
32).
Процессы обращаются к информации в файле, задавая смещение в
байтах. Они рассматривают файл как поток байтов и ведут подсчет
байтов, начиная с нулевого адреса и заканчивая адресом, равным
размеру файла. Ядро переходит от байтов к блокам: файл начинается
с нулевого логического блока и заканчивается блоком, номер кото-
рого определяется исходя из размера файла. Ядро обращается к ин-
дексу и превращает логический блок, принадлежащий файлу, в соот-
ветствующий дисковый блок. На Рисунке 4.8 представлен алгоритм
bmap пересчета смещения в байтах от начала файла в номер физичес-
кого блока на диске.
Рассмотрим формат файла в блоках (Рисунок 4.9) и предположим,
что дисковый блок занимает 1024 байта. Если процессу нужно обра-
титься к байту, имеющему смещение от начала файла, равное 9000, в
результате вычислений ядро приходит к выводу, что этот байт рас-
полагается в блоке прямой адресации с номером 8 (начиная с 0).
Затем ядро обращается к блоку с номером 367; 808-й байт в этом
Информацион-
Индекс ные блоки
--------------┐ ------┐
│ прямой адр. +----------------------------------->│ │
│ 0│ │ │
+-------------+ L------
│ прямой адр. +-----------------┐ ------┐
│ 1│ L----------------->│ │
+-------------+ │ │
│ прямой адр. +-----------------┐ L------
│ 2│ │ ------┐
+-------------+ L----------------->│ │
│ прямой адр. +-----------------┐ │ │
│ 3│ │ L------
+-------------+ │ ------┐
│ прямой адр. │ L----------------->│ │
│ 4│ │ │
+-------------+ L------
│ прямой адр. │
│ 5│
+-------------+
│ прямой адр. │
│ 6│
+-------------+ ------┐
│ прямой адр. │ ------------------>│ │
│ 7│ │ │ │
+-------------+ ---------------- L------
│ прямой адр. │ │ ------┐
│ 8│ │ ------------------>│ │
+-------------+ │ │ │ │
│ прямой адр. +--- -------┐ │ L------
│ 9│ +------+----- ------┐
+-------------+ -->+------+ ------->│ │
│ одинарной +--- +------+ │ │ │
│косвенной адр│ L------- │ L------
+-------------+ -->-------┐ -->-------┐ │ ------┐
│ двойной +--- +------+ │ +------+ │ -->│ │
│косвенной адр│ +------+ │ +------+ │ │ │ │
+-------------+ +------+-- +------+---- │ L------
│ тройной +--┐ L------- L------- L---┐
│косвенной адр│ L->-------┐ -->-------┐ ->-------T--
L-------------- +------+ │ +------+ │ +------+
+------+-- +------+ │ +------+
+------+ +------+-- +------+
L------- L------- L-------
Рисунок 4.6. Блоки прямой и косвенной адресации в индексе
-----------------------------------------------------------┐
│ 10 блоков прямой адресации по 1 Кбайту каждый = 10 Кбайт │
│ 1 блок косвенной адресации с 256 блоками прямой │
│ адресации = 256 Кбайт │
│ 1 блок двойной косвенной адресации с 256 блоками │
│ косвенной адресации = 64 Мбайта│
│ 1 блок тройной косвенной адресации с 256 блоками │
│ двойной косвенной адресации = 16 Гбайт │
L-----------------------------------------------------------
Рисунок 4.7. Объем файла в байтах при размере блока 1 Кбайт
-------------------------------------------------------------┐
│ алгоритм bmap /* отображение адреса смещения в байтах от │
│ начала логического файла на адрес блока │
│ в файловой системе */ │
│ входная информация: (1) индекс │
│ (2) смещение в байтах │
│ выходная информация: (1) номер блока в файловой системе │
│ (2) смещение в байтах внутри блока │
│ (3) число байт ввода-вывода в блок │
│ (4) номер блока с продвижением │
│ { │
│ вычислить номер логического блока в файле исходя из │
│ заданного смещения в байтах; │
│ вычислить номер начального байта в блоке для ввода- │
│ вывода; /* выходная информация 2 */ │
│ вычислить количество байт для копирования пользова- │
│ телю; /* выходная информация 3 */ │
│ проверить возможность чтения с продвижением, пометить │
│ индекс; /* выходная информация 4 */ │
│ определить уровень косвенности; │
│ выполнить (пока уровень косвенности другой) │
│ { │
│ определить указатель в индексе или блок косвенной │
│ адресации исходя из номера логического блока в │
│ файле; │
│ получить номер дискового блока из индекса или из │
│ блока косвенной адресации; │
│ освободить буфер от данных, полученных в резуль- │
│ тате выполнения предыдущей операции чтения с │
│ диска (алгоритм brelse); │
│ если (число уровней косвенности исчерпано) │
│ возвратить (номер блока); │
│ считать дисковый блок косвенной адресации (алго- │
│ ритм bread); │
│ установить номер логического блока в файле исходя │
│ из уровня косвенности; │
│ } │
│ } │
L-------------------------------------------------------------
Рисунок 4.8. Преобразование адреса смещения в номер блока в
файловой системе
блоке (если вести отсчет с 0) и является 9000-м байтом в файле.
Если процессу нужно обратиться по адресу, указанному смещением
350000 байт от начала файла, он должен считать блок двойной кос-
венной адресации, который на рисунке имеет номер 9156. Так как
блок косвенной адресации имеет место для 256 номеров блоков, пер-
вым байтом, к которому будет получен доступ в результате обраще-
--------------┐
│ 4096 │
+-------------+
│ 228 │
+-------------+
│ 45423 │
+-------------+
│ 0 │
+-------------+
│ 0 │
+-------------+ ------------>-------┐
│ 11111 │ │ │ │
+-------------+ │ │ │
│ 0 │ │ │ │
+-------------+ │ L-------
│ 101 │ │ 367
+-------------+ │ информаци-
│ 367 +----------------------- онный
+-------------+ блок
│ 0 │ -->-------┐
+-------------+ ----->-------┐ │ │ │ --->-------┐
│ 428 │ │ │ 331 +--- │ │ │ │ │
+-------------+ │ 0+------+ 75+------+ │ │ │
│ 9156 +--- │ │ │ 3333 +--- │ │
+-------------+ L------- +------+ L-------
│ 824 │ 9156 │ │ 3333
L-------------- двойная L------- информаци-
адресация 331 онный
одинарная блок
адресация
Рисунок 4.9. Размещение блоков в файле и его индексе
ния к блоку двойной косвенной адресации, будет байт с номером
272384 (256К + 10К); таким образом, байт с номером 350000 будет
иметь в блоке двойной косвенной адресации номер 77616. Поскольку
каждый блок одинарной косвенной адресации позволяет обращаться к
256 Кбайтам, байт с номером 350000 должен располагаться в нулевом
блоке одинарной косвенной адресации для блока двойной косвенной
адресации, а именно в блоке 331. Так как в каждом блоке прямой
адресации для блока одинарной косвенной адресации хранится 1
Кбайт, байт с номером 77616 находится в 75-м блоке прямой адреса-
ции для блока одинарной косвенной адресации, а именно в блоке
3333. Наконец, байт с номером в файле 350000 имеет в блоке 3333
номер 816.
При ближайшем рассмотрении Рисунка 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 они показательны.
4.3 КАТАЛОГИ
Из главы 1 напомним, что каталоги являются файлами, из кото-
рых строится иерархическая структура файловой системы; они играют
важную роль в превращении имени файла в номер индекса. Каталог -
это файл, содержимым которого является набор записей, состоящих
из номера индекса и имени файла, включенного в каталог. Составное
имя - это строка символов, завершающаяся пустым символом и разде-
ляемая наклонной чертой ("/") на несколько компонент. Каждая ком-
понента, кроме последней, должна быть именем каталога, но послед-
няя компонента может быть именем файла, не являющегося каталогом.
В версии V системы UNIX длина каждой компоненты ограничивается 14
символами; таким образом, вместе с 2 байтами, отводимыми на номер
индекса, размер записи каталога составляет 16 байт.
------------------------------------------------┐
│ Смещение в байтах Номер индекса Имя │
│ внутри каталога (2 байта) файла │
+--------------------T---------------T----------+
│ 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 │
L--------------------+---------------+-----------
Рисунок 4.10. Формат каталога /etc
На Рисунке 4.10 показан формат каталога "etc". В каждом ката-
логе имеются файлы, в качестве имен которых указаны точка и две
точки ("." и "..") и номера индексов у которых совпадают с номе-
рами индексов данного каталога и родительского каталога, соот-
ветственно. Номер индекса для файла "." в каталоге "/etc" имеет
адрес со смещением 0 и значение 83. Номер индекса для файла ".."
имеет адрес со смещением 16 от начала каталога и значение 2. За-
писи в каталоге могут быть пустыми, при этом номер индекса равен
0. Например, запись с адресом 224 в каталоге "/etc" пустая, нес-
мотря на то, что она когда-то содержала точку входа для файла с
именем "crash". Программа mkfs инициализирует файловую систему
таким образом, что номера индексов для файлов "." и ".." в корне-
вом каталоге совпадают с номером корневого индекса файловой сис-
темы.
Ядро хранит данные в каталоге так же, как оно это делает в
файле обычного типа, используя индексную структуру и блоки с
уровнями прямой и косвенной адресации. Процессы могут читать дан-
ные из каталогов таким же образом, как они читают обычные файлы,
однако исключительное право записи в каталог резервируется ядром,
благодаря чему обеспечивается правильность структуры каталога.
Права доступа к каталогу имеют следующий смысл: право чтения дает
процессам возможность читать данные из каталога; право записи
позволяет процессу создавать новые записи в каталоге или удалять
старые (с помощью системных операций creat, mknod, link и
unlink), в результате чего изменяется содержимое каталога; право
исполнения позволяет процессу производить поиск в каталоге по
имени файла (поскольку "исполнять" каталог бессмысленно). На при-
мере Упражнения 4.6 показана разница между чтением и поиском в
каталоге.
4.4 ПРЕВРАЩЕНИЕ СОСТАВНОГО ИМЕНИ ФАЙЛА (ПУТИ ПОИСКА) В ИДЕН-
ТИФИКАТОР ИНДЕКСА
Начальное обращение к файлу производится по его составному
имени (имени пути поиска), как в командах open, chdir (изменить
каталог) или link. Поскольку внутри системы ядро работает с ин-
дексами, а не с именами путей поиска, оно преобразует имена путей
поиска в идентификаторы индексов, чтобы производить доступ к фай-
лам. Алгоритм namei производит поэлементный анализ составного
имени, ставя в соответствие каждой компоненте имени индекс и ка-
талог и в конце концов возвращая идентификатор индекса для вве-
денного имени пути поиска (Рисунок 4.11).
Из главы 2 напомним, что каждый процесс связан с текущим ка-
талогом (и протекает в его рамках); рабочая область, отведенная
под задачу пользователя, содержит указатель на индекс текущего
каталога. Текущим каталогом первого из процессов в системе, нуле-
вого процесса, является корневой каталог. Путь к текущему катало-
гу каждого нового процесса берет начало от текущего каталога про-
цесса, являющегося родительским по отношению к данному (см.