Морис Бах - Архитектура операционной системы UNIX

номер блока = ((номер индекса — 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 и поэтому ядро не может гарантировать момент, когда индекс станет доступным. Следовательно, процесс, приостанавливающий свое выполнение в ожидании освобождения индекса, может никогда не возобновиться. Ядро скорее прервет выполнение системного вызова, чем оставит такой процесс в «зависшем» состоянии. Однако, процессы не имеют такого контроля над буферами. Поскольку процесс не может удержать буфер заблокированным в течение выполнения нескольких системных операций, ядро здесь может гарантировать скорое освобождение буфера, и процесс поэтому приостанавливается до того момента, когда он станет доступным.