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

алгоритм P /* операция над семафором типа P */
входная информация:
 (1) семафор
 (2) приоритет
выходная информация:
 0 — в случае нормального завершения
 -1 — в случае аварийного выхода из состояния приостанова по сигналу, принятому в режиме ядра
{
 Pprim(semaphore.lock);
 уменьшить (semaphore.value);

 if (semaphore.value ›= 0) {

  Vprim(semaphore.lock);
  return (0);
 }
 /* следует перейти в состояние приостанова */

 if (проверяются сигналы) {

  if (имеется сигнал, прерывающий нахождение в состоянии приостанова) {

   увеличить (semaphore.value);

   if (сигнал принят в режиме ядра) {

    Vprim(semaphore.lock);
    return(-1);
   }

   else {

    Vprim(semaphore.lock);
    longjmp;
   }
  }
 }
 поставить процесс в конец списка приостановленных по семафору;
 Vprim(semaphore.lock);
 выполнить переключение контекста;
 проверить сигналы (см. выше);
 return(0);
}

Рисунок 12.8. Алгоритм выполнения операции P

Рассмотрим еще один феномен, связанный с использованием семафоров в однопроцессорной системе. Предположим, что два процесса, A и B, конкурируют за семафор. Процесс A обнаруживает, что семафор свободен и что процесс B приостановлен; значение семафора равно -1. Когда с помощью операции V процесс A освобождает семафор, он выводит тем самым процесс B из состояния приостанова и вновь делает значение семафора нулевым. Теперь предположим, что процесс A, по-прежнему выполняясь в режиме ядра, пытается снова заблокировать семафор. Производя операцию P, процесс приостановится, поскольку семафор имеет нулевое значение, несмотря на то, что ресурс пока свободен. Системе придется "раскошелиться" на дополнительное переключение контекста. С другой стороны, если бы блокировка была реализована на основе однопроцессорной схемы (sleep-lock), процесс A получил бы право на повторное использование ресурса, поскольку за это время ни один из процессов не смог бы заблокировать его. Для этого случая схема sleep-lock более подходит, чем схема с использованием семафоров.

алгоритм V /* операция над семафором типа V */
входная информация: адрес семафора
выходная информация: отсутствует
{
 Pprim(semaphore.lock);
 увеличить (semaphore.value);

 if (semaphore.value ‹= 0) {

  удалить из списка процессов, приостановленных по семафору, первый по счету процесс;
  перевести его в состояние готовности к запуску;
 }
 Vprim(semaphore.lock);
}

Рисунок 12.9. Алгоритм выполнения операции V

Когда блокируются сразу несколько семафоров, очередность блокирования должна исключать возникновение тупиковых ситуаций. В качестве примера рассмотрим два семафора, A и B, и два алгоритма, требующих одновременной блокировки семафоров. Если бы алгоритмы устанавливали блокировку на семафоры в обратном порядке, как следует из Рисунка 12.11, последовало бы возникновение тупиковой ситуации; процесс A на одноименном процессоре захватывает семафор SA, в то время как процесс B на своем процессоре захватывает семафор SB. Процесс A пытается захватить и семафор SB, но в результате операции P переходит в состояние приостанова, поскольку значение семафора SB не превышает 0. То же самое происходит с процессом B, когда последний пытается захватить семафор SA. Ни тот, ни другой процессы продолжаться уже не могут.

Для предотвращения возникновения подобных ситуаций используются соответствующие алгоритмы обнаружения опасности взаимной блокировки, устанавливающие наличие опасной ситуации и ликвидирующие ее. Тем не менее, использование таких алгоритмов "утяжеляет" ядро. Поскольку число ситуаций, в которых процесс должен одновременно захватывать несколько семафоров, довольно ограничено, легче было бы реализовать алгоритмы, предупреждающие возникновение тупиковых ситуаций еще до того, как они будут иметь место. Если, к примеру, какой-то набор семафоров всегда блокируется в одном и том же порядке, тупиковая ситуация никогда не возникнет. Но в том случае, когда захвата семафоров в обратном порядке избежать не удается, операция CP предотвратит возникновение тупиковой ситуации (см. Рисунок 12.12): если операция завершится неудачно, процесс B освободит свои ресурсы, дабы избежать взаимной блокировки, и позже запустит алгоритм на выполнение повторно, скорее всего тогда, когда процесс A завершит работу с ресурсом.

Чтобы предупредить одновременное обращение процессов к ресурсу, программа обработки прерываний, казалось бы, могла воспользоваться семафором, но из-за того, что она не может приостанавливать свою работу (см. главу 6), использовать операцию P в этой программе нельзя. Вместо этого можно использовать "циклическую блокировку" (spin lock) и не переходить в состояние приостанова, как в следующем примере:

Рисунок 12.10. Неудачное имитация функции wakeup при использовании операции V

Рисунок 12.11. Возникновение тупиковой ситуации из-за смены очередности блокирования

Рисунок 12.12. Использование операции P условного типа для предотвращения взаимной блокировки

Операция повторяется в цикле до тех пор, пока значение семафора не превысит 0; программа обработки прерываний не приостанавливается и цикл завершается только тогда, когда значение семафора станет положительным, после чего это значение будет уменьшено операцией CP.