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

Ядро идентифицирует индексы по имени файловой системы и номеру индекса и выделяет индексы в памяти по запросам соответствующих алгоритмов. Алгоритм 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. Ядро переписывает поля типа файла и владельца файла, установки прав доступа, число указателей на файл, размер файла и таблицу адресов из дискового индекса в память и возвращает заблокированный в памяти индекс.