Внутренее представление файлов.

09/04/96 13:04 u_files.lek
Морис Дж. Бах (Maurice J. Bach) "THE DESIGN OF THE UNIX OPERATING SYSTEM" Copyright c 1986 Корпорация Bell Telephone Laboratories. Перевод с английского к.т.н. Крюкова А.В.

Внутренее представление файлов.

Как уже сказано ранее, каждый файл в системе UNIX имеет уникальный индекс.

Индекс содержит информацию, необходимую любому процессу для того, чтобы обратиться к файлу, например, права собственности на файл, права доступа к файлу, размер файла и расположение данных файла в файловой системе. Процессы обращаются к файлам, используя четко определенный набор системных вызовов и идентифицируя файл строкой символов, выступающих в качестве составного имени файла. Каждое составное имя однозначно определяет файл, благодаря чему ядро системы преобразует это имя в индекс файла.

Рассматриваемые алгоритмы, уровнем выше по сравнению с алгоритмами управления буферным кешем:

ИНДЕКСЫ

Основные положения

Индексы существуют на диске в статической форме и ядро считывает их в память прежде, чем начать с ними работать. Дисковые индексы включают в себя следующие поля:

* Идентификатор владельца файла.

* Идентификатор группового владельца.

* Тип файла. Файл может быть:

* Права доступа к файлу. Система разграничивает права доступа к файлу для трех классов пользователей:

Каждому классу выделяются определенные права на чтение, запись и исполнение файла, которые устанавливаются индивидуально (в случае каталога, разрешение на исполнение интерпретируется как право произ водить поиск в каталоге по имени файла).

Суперпользователь имеет право доступа ко всем файлам в системе.

* Календарные сведения, характеризующие работу с файлом:

* Число указателей на файл, означающее количество имен, используемых при поиске файла в иерархии каталогов.

* Таблица адресов на диске, в которых располагается информация файла. Хотя пользователи трактуют информацию в файле как логический поток байтов, ядро располагает эти данные в несоприкасающихся дисковых блоках. Дисковые блоки, содержащие информацию файла, указываются в индексе.

* Размер файла. Данные в файле адресуются с помощью смещения в байтах относительно начала файла, начиная со смещения, равного 0, поэтому размер файла в байтах на 1 больше максимального смещения.

ПРИМЕЧАНИЕ: Ядро кодирует все вышеперечисленные данные в индексе. При работе с файлом, копия индекса распологается в памяти, при этом добавляются следующие поля:

* Состояние индекса в памяти, отражающее:

* Логический номер устройства файловой системы, содержащей файл.

* Номер индекса. Так как индексы на диске хранятся в линейном массиве ядро идентифицирует номер дискового индекса по его местоположению в массиве.

В дисковом индексе это поле не нужно.

* Указатели на другие индексы в памяти. Ядро связывает индексы в хеш-очереди и включает их в список свободных индексов подобно тому, как связывает буферы в буферные хеш-очереди и включает их в список свободных буферов. Хеш-очередь идентифицируется в соответствии с логическим номером устройства и номером индекса. Ядро может располагать в памяти не более одной копии данного дискового индекса, но индексы могут находиться одновременно как в хеш-очереди, так и в списке свободных индексов.

* Счетчик ссылок, означающий количество активных экземпляров файла (таких, которые открыты).

Выделение индекса (iget)

Ядро идентифицирует индексы по имени файловой системы и номеру индекса и выделяет индексы в памяти по запросам соответствующих алгоритмов. Алгоритм iget назначает индексу место для копии в памяти; он почти идентичен алгоритму getblk для поиска дискового блока в буферном кеше.

Ядро преобразует номера устройства и индекса в имя хеш-очереди и просматривает эту хеш-очередь в поисках индекса. Если индекс не обнаружен, ядро выделяет его из списка свободных индексов и блокирует его. Затем ядро готовится к чтению с диска в память индекса, к которому оно обращается.

Ядро уже знает номера индекса и логического устройства и вычисляет номер логического блока на диске, содержащего индекс, с учетом того, сколько дисковых индексов помещается в одном дисковом блоке.

Вычисления производятся по формуле:
номер блока = ((номер индекса - 1) / число индексов в блоке) + начальный блок в списке индексов где операция деления возвращает целую часть частного.

Если ядро знает номера устройства и дискового блока, оно читает блок, используя алгоритм bread, затем вычисляет смещение индекса в байтах внутри блока по формуле:

((номер индекса - 1) модуль (число индексов в блоке)) *

* размер дискового индекса

Ядро удаляет индекс в памяти из списка свободных индексов, помещает его в соответствующую хеш-очередь и устанавливает значение счетчика ссылок равным 1. Ядро переписывает поля типа файла и владельца файла, установки прав доступа, число указателей на файл, размер файла и таблицу адресов из дискового индекса в память и возвращает заблокированный в памяти индекс.

В отдичие от алгоритма getblk, привыполнении ядром алгоритма iget при пустом списке свободных индексов, оно сообщает об ошибке.

Так как процессы контролируют выделение индексов на пользовательском уровне посредством запуска системных операций open и close и поэтому ядро не может гарантировать момент, когда индекс станет доступным. Следовательно, процесс, приостанавливающий свое выполнение в ожидании освобождения индекса, может никогда не возобновиться.

Освобождение индексов (iput)

В том случае, когда ядро освобождает индекс, оно уменьшает значение счетчика ссылок для него. Если это значение становится равным 0, ядро переписывает индекс на диск в том случае, когда копия индекса в памяти отличается от дискового индекса.

Они различаются, если изменилось содержимое файла, если к файлу производилось обращение или если изменились владелец файла либо права доступа к файлу. Ядро помещает индекс в список свободных индексов, наиболее эффективно располагая индекс в кеше на случай, если он вскоре понадобится вновь. Ядро может также освободить все связанные с файлом информационные блоки и индекс, если число ссылок на файл равно 0.

СТРУКТУРА ФАЙЛА ОБЫЧНОГО ТИПА

Как уже говорилось, индекс включает в себя таблицу адресов расположения информации файла на диске. Так как каждый блок на диске адресуется по своему номеру, в этой таблице хранится совокупность номеров дисковых блоков. Если бы данные файла занимали непрерывный участок на диске (то есть файл занимал бы линейную последовательность дисковых блоков), то для обращения к данным в файле было бы достаточно хранить в индексе адрес начального блока и размер файла. Однако, такая стратегия размещения данных не позволяет осуществлять простое расширение и сжатие файлов в файловой системе без риска фрагментации свободного пространства памяти на диске. Более того, ядру пришлось бы выделять и резервировать непрерывное пространство в файловой системе перед выполнением операций, могущих привести к увеличению размера файла.

Для того, чтобы небольшая структура индекса позволяла работать с большими файлами, таблица адресов дисковых блоков приводится в соответствие со структурой, представленной на Рисунке. Версия V системы UNIX работает с 13 точками входа в таблицу адресов индекса, но принципиальные моменты не зависят от количества точек входа. Блок, имеющий пометку "ПРЯМАЯ АДРЕСАЦИЯ" на рисунке, содержит номера дисковых блоков, в которых хранятся реальные данные. Блок, имеющий пометку "ОДИНАРНАЯ КОСВЕННАЯ АДРЕСАЦИЯ", указывает на блок, содержащий список номеров блоков прямой адресации. Чтобы обратиться к данным с помощью блока косвенной адресации, ядро должно считать этот блок, найти соответствующий вход в блок прямой адресации и, считав блок прямой адресации, обнаружить данные. Блок, имеющий пометку "ДВОЙНАЯ КОСВЕННАЯ

АДРЕСАЦИЯ", содержит список номеров блоков одинарной косвенной адресации,

а блок, имеющий пометку "ТРОЙНАЯ КОСВЕННАЯ АДРЕСАЦИЯ", содержит список

номеров блоков двойной косвенной адресации.

Рисунок. Блоки прямой и косвенной адресации в индексе

Процессы обращаются к информации в файле, задавая смещение в байтах. Они рассматривают файл как поток байтов и ведут подсчет байтов, начиная с нулевого адреса и заканчивая адресом, равным размеру файла. Ядро переходит от байтов к блокам: файл начинается с нулевого логического блока и заканчивается блоком, номер которого определяется исходя из размера файла.

Ядро обращается к индексу и превращает логический блок, принадлежащий файлу, в соответствующий дисковый блок.

Рисунок 4.7. Объем файла в байтах при размере блока 1 Кбайт

ПРИМЕЧАНИЕ: В результате записи информации в файл с использованием функции lseek в файле могут оказаться блоки, несодержащие информации.

Дисковое пространство для них не выделяется, а в индексе указывается ссылка на нулевой блок (естественно их наличие подразумевается).

КАТАЛОГИ

Каталоги являются файлами, из которых строится иерархическая структура файловой системы; они играют важную роль в превращении имени файла в номер индекса. Каталог - это файл, содержимым которого является набор записей, состоящих из номера индекса и имени файла, включенного в каталог. Составное имя - это строка символов, завершающаяся пустым символом и разделяемая наклонной чертой ("/") на несколько компонент. Каждая компонента, кроме последней, должна быть именем каталога, но последняя компонента может быть именем файла, не являющегося каталогом. В версии V системы UNIX длина каждой компоненты ограничивается 14 символами; таким образом, вместе с 2 байтами, отводимыми на номер индекса, РАЗМЕР ЗАПИСИ КАТАЛОГА составляет 16 байт.

Рисунок. Формат каталога /etc

На Рисунке показан формат каталога "etc". В каждом каталоге имеются файлы, в качестве имен которых указаны точка и две точки ("." и "..") и номера индексов у которых совпадают с номерами индексов данного каталога и родительского каталога, соответственно. Записи в каталоге могут быть пустыми, при этом номер индекса равен 0. Номера индексов для файлов "." и ".." в корневом каталоге совпадают с номером корневого индекса файловой системы.

Ядро хранит данные в каталоге так же, как оно это делает в файле обычного типа, используя индексную структуру и блоки с уровнями прямой и косвенной адресации. Процессы могут читать данные из каталогов таким же образом, как они читают обычные файлы, однако ИСКЛЮЧИТЕЛЬНОЕ ПРАВО ЗАПИСИ в каталог резервируется ядром, благодаря чему обеспечивается правильность структуры каталога.

Права доступа к каталогу имеют следующий смысл:

ПРЕОБРАЗОВАНИЕ СОСТАВНОГО ИМЕНИ ФАЙЛА (ПУТИ ПОИСКА) В ИДЕНТИФИКАТОР ИНДЕКСА

Начальное обращение к файлу производится по его составному имени (имени пути поиска), как в командах open, chdir (изменить каталог) или link. Поскольку внутри системы ядро работает с индексами, а не с именами путей поиска, оно преобразует имена путей поиска в идентификаторы индексов, чтобы производить доступ к файлам. Алгоритм namei производит поэлементный анализ составного имени, ставя в соответствие каждой компоненте имени индекс и каталог и в конце концов возвращая идентификатор индекса для введенного имени пути поиска. Все поиски файлов по имени начинаются с текущего каталога процесса, если только имя пути поиска не предваряется наклонной чертой, указывая, что поиск нужно начинать с корневого каталога. В любом случае ядро может легко обнаружить индекс каталога, с которого начинается поиск. Текущий каталог хранится в рабочей области процесса, а корневой индекс системы хранится в глобальной переменной.

Алгоритм namei использует при анализе составного имени пути поиска промежуточные индексы (рабочие индексы). Индекс каталога, откуда поиск берет начало, является первым рабочим индексом. На каждой итерации цикла алгоритма ядро проверяет совпадение рабочего индекса с индексом каталога. Процесс также должен иметь право производить поиск в каталоге (разрешения на чтение недостаточно). Код идентификации пользователя для процесса должен соответствовать коду индивидуального или группового владельца файла и должно быть предоставлено право исполнения, либо поиск нужноразрешить всем пользователям. В противном случае, поиск не получится.

Ядро выполняет линейный поиск файла в каталоге, ассоциированном с рабочим индексом, пытаясь найти для компоненты имени пути поиска подходящую запись в каталоге. Исходя из адреса смещения в байтах внутри каталога (начиная с 0), оно определяет местоположение дискового блока в соответствии с алгоритмом bmap и считывает этот блок, используя алгоритм bread. По имени компоненты ядро производит в блоке поиск, представляя содержимое блока как последовательность записей каталога. При обнаружении совпадения ядро переписывает номер индекса из данной точки входа, освобождает блок (алгоритм brelse) и старый рабочий индекс (алгоритм iput), и переназначает индекс найденной компоненты (алгоритм iget). Новый индекс становится рабочим индексом. Если ядро не находит в блоке подходящего имени, оно освобождает блок, прибавляет к адресу смещения число байтов в блоке, превращает новый адрес смещения в номер дискового блока (алгоритм bmap) и читает следующий блок. Ядро повторяет эту процедуру до тех пор, пока имя компоненты пути поиска не совпадет с именем точки входа в каталоге, либо до тех пор, пока не будет достигнут конец каталога. суперблок

Суперблок состоит из следующих полей:

Ядро периодически переписывает суперблок на диск, если в суперблок были внесены изменения, для того, чтобы обеспечивалась согласованность с данными, хранящимися в файловой системе.

НАЗНАЧЕНИЕ ИНДЕКСА НОВОМУ ФАЙЛУ

Для выделения известного индекса, то есть индекса, для которого предварительно определен собственный номер (и номер файловой системы), ядро использует алгоритм iget.

Другой алгоритм, ialloc, выполняет назначение дискового индекса вновь создаваемому файлу.

В файловой системе имеется линейный список индексов. Индекс считается свободным, если поле его типа хранит нулевое значение. Для повышения производительности в суперблоке файловой системы хранится массив номеров свободных индексов в файловой системе.

Если список номеров индексов в суперблоке не пуст, ядро назначает номер следующего индекса, выделяет для вновь назначенного дискового индекса свободный индекс в памяти, используя алгоритм iget (читая индекс с диска, если необходимо), копирует дисковый индекс в память, инициализирует поля в индексе и возвращает индекс заблокированным. Затем ядро корректирует дисковый индекс, указывая, что к индексу произошло обращение.

Если список свободных индексов в суперблоке пуст, ядро просматривает диск и помещает в суперблок как можно больше номеров свободных индексов. При этом ядро блок за блоком считывает индексы с диска и наполняет список номеров индексов в суперблоке до отказа, запоминая индекс с номером, наибольшим среди найденных. В следующий раз, когда ядро будет искать на диске свободные индексы, оно использует запомненный индекс в качестве стартовой точки, благодаря чему гарантируется, что ядру не придется зря тратить время на считывание дисковых блоков, в которых свободные индексы наверняка отсутствуют. После формирования нового набора номеров свободныхиндексов ядро запускает алгоритм назначения индекса с самого начала. Всякий раз, когда ядро назначает дисковый индекс, оно уменьшает значение счетчика свободных индексов, записанное в суперблоке.

(а) Назначение свободного индекса из середины списка

 

(б) Назначение свободного индекса, когда список в суперблоке пуст

Рисунок. Два случая назначения номеров свободных индексов

ОСВОБОЖДЕНИЕ ИНДЕКСА

Алгоритм освобождения индекса построен значительно проще. Увеличив на единицу общее количество доступных в файловой системе индексов, ядро проверяет наличие блокировки у суперблока. Если он заблокирован, ядро, чтобы предотвратить конкуренцию, немедленно сообщает: номер индекса отсутствует в суперблоке, но индекс может быть найден на диске и доступен для переназначения. Если список не заблокирован, ядро проверяет, имеется ли место для новых номеров индексов и если да, помещает номер индекса в список и выходит из алгоритма. Если список полон, ядро не сможет в нем сохранить вновь освобожденный индекс. Оно сравнивает номер освобожденного индекса с номером запомненного индекса. Если номер освобожденного индекса меньше номера запомненного, ядро запоминает номер вновь освобожденного индекса, выбрасывая из суперблока номер старого запомненного индекса.

Если номер освобожденного индекса больше номера запомненного, то измененний в список не вносится. Индекс не теряется, поскольку ядро может найти его, просматривая список индексов на диске. Ядро поддерживает структуру списка в суперблоке таким образом, что последний номер, выбираемый им из списка, и есть номер запомненного индекса. В идеале не должно быть свободных индексов с номерами, меньшими, чем номер запомненного индекса.

(б) Освободился индекс номер 499

Рисунок. Размещение номеров свободных индексов в суперблоке

ВЫДЕЛЕНИЕ ДИСКОВЫХ БЛОКОВ

Когда процесс записывает данные в файл, ядро должно выделять из файловой системы дисковые блоки под информационные блоки прямой адресации и иногда под блоки косвенной адресации. Суперблок файловой системы содержит массив, используемый для хранения номеров свободных дисковых блоков в файловой системе. Сервисная программа mkfs ("make file system" - создать файловую систему) организует информационные блоки в файловой системе в виде списка с указателями так, что каждый элемент списка указывает на дисковый блок, в котором хранится массив номеров свободных дисковых блоков, а один из элементов массива хранит номер следующего блока данного списка.

Когда ядру нужно выделить блок из файловой системы (алгоритм alloc), оно выделяет следующий из блоков, имеющихся в списке в суперблоке. Если выделенный блок является последним блоком, имеющимся в кеше суперблока, ядро трактует его как указатель на блок, в котором хранится список свободных блоков. Ядро читает блок, заполняет массив в суперблоке новым списком номеров блоков и после этого продолжает работу с первоначальным номером блока. Если в файловой системе нет свободных блоков, вызывающий процесс получает сообщение об ошибке. Если процесс записывает в файл большой объем информации, он неоднократно запрашивает у системы блоки для хранения информации, но ядро назначает каждый раз только по одному блоку.

Рисунок. Список номеров свободных дисковых блоков с указателями

Программа mkfs пытается организовать первоначальный связанный список номеров свободных блоков так, чтобы номера блоков, передаваемых файлу, были рядом друг с другом. Благодаря этому повышается производительность, поскольку сокращается время поиска на диске и время ожидания при последовательном чтении файла процессом.
Ядро не предпринимает попыток сортировать номера блоков в списке.

ОСВОБОЖДЕНИЕ ДИСКОВЫХ БЛОКОВ

Алгоритм освобождения блока (free) - обратный алгоритму выделения блока. Если список в суперблоке не полон, номер вновь освобожденного блока включается в этот список. Если, однако, список полон, вновь освобожденный блок становится связным блоком; ядро переписывает в него список из суперблока и копирует блок на диск. Затем номер вновь освобожденного блока включается в список свободных блоков в суперблоке. Этот номер становится единственным номером в списке.

ДРУГИЕ ТИПЫ ФАЙЛОВ

В системе UNIX поддерживаются и два других типа файлов: каналы и специальные файлы.

КАНАЛ, иногда называемый fifo (сокращенно от "first-in-first-out" - "первым пришел - первым вышел" - поскольку обслуживает запросы в порядке поступления), отличается от обычного файла тем, что содержит временные данные: информация, однажды считанная из канала, не может быть прочитана вновь. Кроме того, информация читается в том порядке, в котором она была записана в канале, и система не допускает никаких отклонений от данного порядка. Способ хранения ядром информации в канале не отличается от способа ее хранения в обычном файле, за исключением того, что здесь используются только блоки прямой, а не косвенной, адресации.

Последним типом файлов в системе UNIX являются СПЕЦИАЛЬНЫЕ ФАЙЛЫ, к которым относятся специальные файлы устройств ввода-вывода блоками и специальные файлы устройств посимвольного ввода-вывода. Оба подтипа обозначают устройства, и поэтому индексы таких файлов не связаны ни с какой информацией. Вместо этого индекс содержит два номера - старший и младший номера устройства. Старший номер устройства указывает его тип, например, терминал или диск, а младший номер устройства - числовой код, идентифицирующий устройство в группе однородных устройств.

Stay-at-home