Архитектура операционной системы UNIX (ЛП) - Бах Морис Дж.

Рисунок 3.2. Список свободных буферов

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

Рисунок 3.3. Буферы в хеш-очередях

На Рисунке 3.3 изображены буферы в хеш-очередях: заголовки хеш-очередей показаны в левой части рисунка, а квадратиками в каждой строке показаны буферы в соответствующей хеш-очереди. Так, квадратики с числами 28, 4 и 64 представляют буферы в хеш-очереди для «блока 0 модуля 4». Пунктирным линиям между буферами соответствуют указатели вперед и назад вдоль хеш-очереди; для простоты на следующих рисунках этой главы данные указатели не показываются, но их присутствие подразумевается. Кроме того, на рисунке блоки идентифицируются только своими номерами и функция хеширования построена на использовании только номеров блоков; однако на практике также используется номер устройства.

Любой буфер всегда находится в хеш-очереди, но его положение в очереди не имеет значения. Как уже говорилось, никакая пара буферов не может одновременно содержать данные одного и того же дискового блока; поэтому каждый дисковый блок в буферном пуле существует в одной и только одной хеш-очереди и представлен в ней только один раз. Тем не менее, буфер может находиться в списке свободных буферов, если его статус «свободен». Поскольку буфер может быть одновременно в хеш-очереди и в списке свободных буферов, у ядра есть два способа его обнаружения. Ядро просматривает хеш-очередь, если ему нужно найти определенный буфер, и выбирает буфер из списка свободных буферов, если ему нужен любой свободный буфер. В следующем разделе будет показано, каким образом ядро осуществляет поиск определенных дисковых блоков в буферном кеше, а также как оно работает с буферами в хеш-очередях и в списке свободных буферов. Еще раз напомним: буфер всегда находится в хеш — очереди, а в списке свободных буферов может быть, но может и отсутствовать.

3.3 МЕХАНИЗМ ПОИСКА БУФЕРА

Как показано на Рисунке 2.1, алгоритмы верхнего уровня, используемые ядром для подсистемы управления файлами, инициируют выполнение алгоритмов управления буферным кешем. При выборке блока алгоритмы верхнего уровня устанавливают логический номер устройства и номер блока, к которым они хотели бы получить доступ. Например, если процесс хочет считать данные из файла, ядро устанавливает, в какой файловой системе находится файл и в каком блоке файловой системы содержатся данные, о чем подробнее мы узнаем из главы 4. Собираясь считать данные из определенного дискового блока, ядро проверяет, находится ли блок в буферном пуле, и если нет, назначает для него свободный буфер. Собираясь записать данные в определенный дисковый блок, ядро проверяет, находится ли блок в буферном пуле, и если нет, назначает для этого блока свободный буфер. Для выделения буферов из пула в алгоритмах чтения и записи дисковых блоков используется операция getblk (Рисунок 3.4).

Рассмотрим в этом разделе пять возможных механизмов использования getblk для выделения буфера под дисковый блок.

1. Ядро обнаруживает блок в хеш-очереди, соответствующий ему буфер свободен.

2. Ядро не может обнаружить блок в хеш-очереди, поэтому оно выделяет буфер из списка свободных буферов.

3. Ядро не может обнаружить блок в хеш-очереди и, пытаясь выделить буфер из списка свободных буферов (как в случае 2), обнаруживает в списке буфер, который помечен как «занят на время записи». Ядро должно переписать этот буфер на диск и выделить другой буфер.

4. Ядро не может обнаружить блок в хеш-очереди, а список свободных буферов пуст.

5. Ядро обнаруживает блок в хеш-очереди, но его буфер в настоящий момент занят.

Обсудим каждый случай более подробно.

Осуществляя поиск блока в буферном пуле по комбинации номеров устройства и блока, ядро ищет хеш-очередь, которая бы содержала этот блок. Просматривая хеш-очередь, ядро придерживается списка с указателями, пока (как в первом случае) не найдет буфер с искомыми номерами устройства и блока. Ядро проверяет занятость блока и в том случае, если он свободен, помечает буфер «занятым» для того, чтобы другие процессы[8] не смогли к нему обратиться. Затем ядро удаляет буфер из списка свободных буферов, поскольку буфер не может одновременно быть занятым и находиться в указанном списке. Если другие процессы попытаются обратиться к блоку в то время, когда его буфер занят, они приостановятся до тех пор, пока буфер не освободится. На Рисунке 3.5 показан первый случай, когда ядро ищет блок 4 в хеш-очереди, помеченной как «блок 0 модуль 4». Обнаружив буфер, ядро удаляет его из списка свободных буферов, делая блоки 5 и 28 соседями в списке.

алгоритм getblk

входная информация: номер файловой системы номер блока

выходная информация: буфер, который можно использовать для блока

{

 do if (буфер не найден) {

  if (блок в хеш-очереди)  {

   if (буфер занят) { /* случай 5 */

    sleep (до освобождения буфера);

    continue; /* цикл с условием продолжения */

   }

   пометить буфер занятым; /* случай 1 */

   удалить буфер из списка свободных буферов;

   return буфер;

  }

  else { /* блока нет в хеш-очереди */

   if (в списке нет свободных буферов) { /*случай 4*/

    sleep (до освобождения любого буфера);

    continue; /* цикл с условием продолжения */

   }

   удалить буфер из списка свободных буферов;

   if (буфер помечен для отложенной переписи) { /* случай 3 */

    асинхронная перепись содержимого буфера на диск;

    continue; /* цикл с условием продолжения */

   }

   /* случай 2 — поиск свободного буфера */

   удалить буфер из старой хеш-очереди;