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

Обратимся еще раз к алгоритму getblk, рассмотренному нами в главе 3. Алгоритм работает с тремя структурами данных: заголовком буфера, хеш-очередью буферов и списком свободных буферов. Ядро связывает семафор со всеми экземплярами каждой структуры. Другими словами, если у ядра имеются в распоряжении 200 буферов, заголовок каждого из них включает в себя семафор, используемый для захвата буфера; когда процесс выполняет над семафором операцию P, другие процессы, тоже пожелавшие захватить буфер, приостанавливаются до тех пор, пока первый процесс не исполнит операцию V. У каждой хеш-очереди буферов также имеется семафор, блокирующий доступ к очереди. В однопроцессорной системе блокировка хеш-очереди не нужна, ибо процесс никогда не переходит в состояние приостанова, оставляя очередь в несогласованном (неупорядоченном) виде. В многопроцессорной системе, тем не менее, возможны ситуации, когда с одной и той же хеш-очередью работают два процесса; в каждый момент времени семафор открывает доступ к очереди только для одного процесса. По тем же причинам и список свободных буферов нуждается в семафоре для защиты содержащейся в нем информации от искажения.

алгоритм getblk /* многопроцессорная версия */

входная информация:

 номер файловой системы

 номер блока

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

{

 do while(буфер не будет обнаружен) {

  P(семафор хеш-очереди);

  if (блок находится в хеш-очереди) {

   if (операция CP(семафор буфера) завершается неудачно) { /* буфер занят */

    V(семафор хеш-очереди);

    P(семафор буфера); /* приостанов до момента освобождения */

    if (операция CP(семафор хеш-очереди) завершается неудачно) {

     V(семафор буфера);

     continue; /* выход в цикл "выполнять" */

    }

    else if (номер устройства или номер блока изменились) {

     V(семафор буфера);

     V(семафор хеш-очереди);

    }

   }

   do while(операция CP(семафор списка свободных буферов) не завершится успешно);

   /* "кольцевой цикл" */

   пометить буфер занятым;

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

   V(семафор списка свободных буферов);

   V(семафор хеш-очереди);

   return буфер;

  }

  else

   /* буфер отсутствует в хеш-очереди здесь начинается выполнение оставшейся части алгоритма */

 }

}

Рисунок 12.14. Выделение буфера с использованием семафоров