Страница: 13/18
while (value(semaphore) < 0)
{
V(semaphore);
};
Если вмешательства со стороны других процессов нет, ядро повторяет цикл до тех пор, пока значение семафора не станет больше или равно 0, ибо это означает, что в состоянии приостанова по семафору нет больше ни одного процесса. Тем не менее, нельзя исключить и такую возможность, что сразу после того, как процесс A при тестировании семафора на одноименном процессоре обнаружил нулевое значение семафора, процесс B на своем процессоре выполняет операцию P, уменьшая значение семафора до –1.
|
|
Процесс A продолжит свое выполнение, думая, что им возобновлены все приостановленные по семафору процессы. Таким образом, цикл выполнения операции не дает гарантии возобновления всех приостановленных процессов, поскольку он не является элементарным. Рассмотрим еще один феномен, связанный с использованием семафоров в однопроцессорной системе. Предположим, что два процесса, A и B, конкурируют за семафор. Процесс A обнаруживает, что семафор свободен и что процесс B приостановлен; значение семафора равно -1. Когда с помощью операции V процесс A освобождает семафор, он выводит тем самым процесс B из состояния приостанова и вновь делает значение семафора нулевым. Теперь предположим, что процесс A, по-прежнему выполняясь в режиме ядра, пытается снова заблокировать семафор. Производя операцию P, процесс приостановится, поскольку семафор имеет нулевое значение, несмотря на то, что ресурс пока свободен. Системе придется "раскошелиться" на дополнительное переключение контекста. С другой стороны, если бы блокировка была реализована на основе однопроцессорной схемы (sleep-lock), процесс A получил бы право на повторное использование ресурса, поскольку за это время ни один из процессов не смог бы заблокировать его. Для этого случая схема sleep-lock более подходит, чем схема с использованием семафоров. Когда блокируются сразу несколько семафоров, очередность блокирования должна исключать возникновение тупиковых ситуаций. В качестве примера рассмотрим два семафора, A и B, и два алгоритма, требующих одновременной блокировки семафоров. Если бы алгоритмы устанавливали блокировку на семафоры в обратном порядке, как следует из рисунка,
|
|
последовало бы возникновение тупиковой ситуации; процесс A на одноименном процессоре захватывает семафор SA, в то время как процесс B на своем процессоре захватывает семафор SB. Процесс A пытается захватить и семафор SB, но в результате операции P переходит в состояние приостанова, поскольку значение семафора SB не превышает 0. То же самое происходит с процессом B, когда последний пытается захватить семафор SA. Ни тот, ни другой процессы продолжаться уже не могут. Для предотвращения возникновения подобных ситуаций используются соответствующие алгоритмы обнаружения опасности взаимной блокировки, устанавливающие наличие опасной ситуации и ликвидирующие ее. Тем не менее, использование таких алгоритмов "утяжеляет" ядро. Поскольку число ситуаций, в которых процесс должен одновременно захватывать несколько семафоров, довольно ограничено, легче было бы реализовать алгоритмы, предупреждающие возникновение тупиковых ситуаций еще до того, как они будут иметь место. Если, к примеру, какой-то набор семафоров всегда блокируется в одном и том же порядке, тупиковая ситуация никогда не возникнет. Но в том случае, когда захвата семафоров в обратном порядке избежать не удается, операция CP предотвратит возникновение тупиковой ситуации:
|
|
Реферат опубликован: 6/09/2006