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

Рассмотрим в этом разделе пять возможных механизмов использования 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 — поиск свободного буфера */

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

   включить буфер в новую хеш-очередь;

   return буфер;

  }

 }

}

Рисунок 3.4. Алгоритм выделения буфера

Рисунок 3.5. Поиск буфера — случай 1: буфер в хеш-очереди

алгоритм brelse

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

выходная информация: отсутствует

{

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

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

 поднять приоритет прерывания процессора так, чтобы блокировать любые прерывания;

 if (содержимое буфера верно и буфер не старый) поставить буфер в конец списка свободных буферов;

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

 понизить приоритет прерывания процессора с тем, чтобы вновь разрешить прерывания;

 разблокировать (буфер);

}

Рисунок 3.6. Алгоритм высвобождения буфера