Морис Бах - Архитектура операционной системы UNIX
4.1.2 Обращение к индексам
Ядро идентифицирует индексы по имени файловой системы и номеру индекса и выделяет индексы в памяти по запросам соответствующих алгоритмов. Алгоритм iget назначает индексу место для копии в памяти (Рисунок 4.3); он почти идентичен алгоритму getblk для поиска дискового блока в буферном кеше. Ядро преобразует номера устройства и индекса в имя хеш-очереди и просматривает эту хеш-очередь в поисках индекса. Если индекс не обнаружен, ядро выделяет его из списка свободных индексов и блокирует его. Затем ядро готовится к чтению с диска в память индекса, к которому оно обращается. Ядро уже знает номера индекса и логического устройства и вычисляет номер логического блока на диске, содержащего индекс, с учетом того, сколько дисковых индексов помещается в одном дисковом блоке. Вычисления производятся по формуле
номер блока = ((номер индекса — 1) / число индексов в блоке) + начальный блок в списке индексов
где операция деления возвращает целую часть частного. Например, предположим, что блок 2 является начальным в списке индексов и что в каждом блоке помещаются 8 индексов, тогда индекс с номером 8 находится в блоке 2, а индекс с номером 9 — в блоке 3. Если же в дисковом блоке помещаются 16 индексов, тогда индексы с номерами 8 и 9 располагаются в дисковом блоке с номером 2, а индекс с номером 17 является первым индексом в дисковом блоке 3.
алгоритм iget
входная информация: номер индекса в файловой системе
выходная информация: заблокированный индекс
{
do {
if (индекс в индексном кеше) {
if (индекс заблокирован) {
sleep (до освобождения индекса);
continue; /* цикл с условием продолжения */
}
/* специальная обработка для точек монтирования (глава 5) */
if (индекс в списке свободных индексов) убрать из списка свободных индексов;
увеличить счетчик ссылок для индекса;
return (индекс);
}
/* индекс отсутствует в индексном кеше */
if (список свободных индексов пуст) return (ошибку);
убрать новый индекс из списка свободных индексов;
сбросить номер индекса и файловой системы;
убрать индекс из старой хеш-очереди, поместить в новую;
считать индекс с диска (алгоритм bread);
инициализировать индекс (например, установив счетчик ссылок в 1);
return(индекс);
}
}
Рисунок 4.3. Алгоритм выделения индексов в памяти
Если ядро знает номера устройства и дискового блока, оно читает блок, используя алгоритм bread (глава 2), затем вычисляет смещение индекса в байтах внутри блока по формуле:
((номер индекса – 1) mod (число индексов в блоке)) * размер дискового индекса
Например, если каждый дисковый индекс занимает 64 байта и в блоке помещаются 8 индексов, тогда индекс с номером 8 имеет адрес со смещением 448 байт от начала дискового блока. Ядро убирает индекс в памяти из списка свободных индексов, помещает его в соответствующую хеш-очередь и устанавливает значение счетчика ссылок равным 1. Ядро переписывает поля типа файла и владельца файла, установки прав доступа, число указателей на файл, размер файла и таблицу адресов из дискового индекса в память и возвращает заблокированный в памяти индекс.
Ядро манипулирует с блокировкой индекса и счетчиком ссылок независимо один от другого. Блокировка — это установка, которая действует на время выполнения системного вызова и имеет целью запретить другим процессам обращаться к индексу пока тот в работе (и возможно хранит противоречивые данные). Ядро снимает блокировку по окончании обработки системного вызова: блокировка индекса никогда не выходит за границы системного вызова. Ядро увеличивает значение счетчика ссылок с появлением каждой активной ссылки на файл. Например, в разделе 5.1 будет показано, как ядро увеличивает значение счетчика ссылок тогда, когда процесс открывает файл. Оно уменьшает значение счетчика ссылок только тогда, когда ссылка становится неактивной, например, когда процесс закрывает файл. Таким образом, установка счетчика ссылок сохраняется для множества системных вызовов. Блокировка снимается между двумя обращениями к операционной системе, чтобы позволить процессам одновременно производить разделенный доступ к файлу; установка счетчика ссылок действует между обращениями к операционной системе, чтобы предупредить переназначение ядром активного в памяти индекса. Таким образом, ядро может заблокировать и разблокировать выделенный индекс независимо от значения счетчика ссылок. Выделением и освобождением индексов занимаются и отличные от open системные операции, в чем мы и убедимся в главе 5.
Возвращаясь к алгоритму iget, заметим, что если ядро пытается взять индекс из списка свободных индексов и обнаруживает список пустым, оно сообщает об ошибке. В этом отличие от идеологии, которой следует ядро при работе с дисковыми буферами, где процесс приостанавливает свое выполнение до тех пор, пока буфер не освободится. Процессы контролируют выделение индексов на пользовательском уровне посредством запуска системных операций open и close и поэтому ядро не может гарантировать момент, когда индекс станет доступным. Следовательно, процесс, приостанавливающий свое выполнение в ожидании освобождения индекса, может никогда не возобновиться. Ядро скорее прервет выполнение системного вызова, чем оставит такой процесс в «зависшем» состоянии. Однако, процессы не имеют такого контроля над буферами. Поскольку процесс не может удержать буфер заблокированным в течение выполнения нескольких системных операций, ядро здесь может гарантировать скорое освобождение буфера, и процесс поэтому приостанавливается до того момента, когда он станет доступным.
В предшествующих параграфах рассматривался случай, когда ядро выделяет индекс, отсутствующий в индексном кеше. Если индекс находится в кеше, процесс (A) обнаружит его в хеш-очереди и проверит, не заблокирован ли индекс другим процессом (B). Если индекс заблокирован, процесс A приостанавливается и выставляет флаг у индекса в памяти, показывая, что он ждет освобождения индекса. Когда позднее процесс B разблокирует индекс, он «разбудит» все процессы (включая процесс A), ожидающие освобождения индекса. Когда же наконец процесс A сможет использовать индекс, он заблокирует его, чтобы другие процессы не могли к нему обратиться. Если первоначально счетчик ссылок имел значение, равное 0, индекс также появится в списке свободных индексов, поэтому ядро уберет его оттуда: индекс больше не является свободным. Ядро увеличивает значение счетчика ссылок и возвращает заблокированный индекс.
Если суммировать все вышесказанное, можно отметить, что алгоритм iget имеет отношение к начальной стадии системных вызовов, когда процесс впервые обращается к файлу. Этот алгоритм возвращает заблокированную индексную структуру со значением счетчика ссылок, на 1 большим, чем оно было раньше. Индекс в памяти содержит текущую информацию о состоянии файла. Ядро снимает блокировку с индекса перед выходом из системной операции, поэтому другие системные вызовы могут обратиться к индексу, если пожелают. В главе 5 рассматриваются эти случаи более подробно.
алгоритм iput /* разрешение доступа к индексу в памяти */
входная информация: указатель на индекс в памяти
выходная информация: отсутствует
{
заблокировать индекс если он еще не заблокирован;
уменьшить на 1 счетчик ссылок для индекса;
if (значение счетчика ссылок == 0) {
if (значение счетчика связей == 0) {
освободить дисковые блоки для файла (алгоритм free, раздел 4.7);
установить тип файла равным 0;
освободить индекс (алгоритм ifree, раздел 4.6);
}
if (к файлу обращались или изменился индекс или изменилось содержимое файла)
скорректировать дисковый индекс;
поместить индекс в список свободных индексов;
}
снять блокировку с индекса;
}
Рисунок 4.4. Освобождение индекса
4.1.3 Освобождение индексов
В том случае, когда ядро освобождает индекс (алгоритм iput, Рисунок 4.4), оно уменьшает значение счетчика ссылок для него. Если это значение становится равным 0, ядро переписывает индекс на диск в том случае, когда копия индекса в памяти отличается от дискового индекса. Они различаются, если изменилось содержимое файла, если к файлу производилось обращение или если изменились владелец файла либо права доступа к файлу. Ядро помещает индекс в список свободных индексов, наиболее эффективно располагая индекс в кеше на случай, если он вскоре понадобится вновь. Ядро может также освободить все связанные с файлом информационные блоки и индекс, если число ссылок на файл равно 0.
