Страница:
+-------------------------------------------------------+
| struct semaphore { |
| int lock; |
| }; |
| |
| Init(semaphore) |
| struct semaphore semaphore; |
| { |
| semaphore.lock = 1; |
| } |
| |
| Pprim(semaphore) |
| struct semaphore semaphore; |
| { |
| while (read_and_clear(semaphore.lock)) |
| ; |
| } |
| |
| Vprim(semaphore) |
| struct semaphore semaphore; |
| { |
| semaphore.lock = 1; |
| } |
+-------------------------------------------------------+
Рисунок 12.7. Операции над семафором, использующие инструкцию
read and clear
состояние приостанова в связи с невозможностью обработки больших объемов ин-
формации. Позже, когда драйвер будет готов к приему следующей порции данных,
он возобновит все приостановленные им процессы. Использование операций P и V
в тех случаях, когда устанавливающие блокировку процессы получают доступ к
ресурсу поочередно, а все остальные процессы - в порядке поступления запро-
сов, является более предпочтительным. В сравнении с однопроцессорной проце-
дурой блокирования (sleep-lock) данная схема обычно выигрывает, так как если
при наступлении события все процессы возобновляются, большинство из них мо-
жет вновь наткнуться на блокировку и снова перейти в состояние приостанова.
С другой стороны, в тех случаях, когда требуется вывести из состояния приос-
танова все процессы одновременно, использование операций P и V представляет
известную сложность.
Если операция возвращает значение семафора, является ли она эквивалент-
ной функции wakeup ?
while (value(semaphore) < 0)
V(semaphore);
Если вмешательства со стороны других процессов нет, ядро повторяет цикл
до тех пор, пока значение семафора не станет больше или равно 0, ибо это оз-
начает, что в состоянии приостанова по семафору нет больше ни одного процес-
са. Тем не менее, нельзя исклю-
чить и такую возможность, что сразу после того, как процесс A при тестирова-
нии семафора на одноименном процессоре обнаружил нулевое значение семафора,
процесс B на своем процессоре выполняет операцию P, уменьшая значение сема-
фора до -1 (Рисунок 12.10). Процесс A продолжит свое выполнение, думая, что
им возобновлены все приостановленные по семафору процессы. Таким образом,
цикл выполнения операции не дает гарантии возобновления всех приостановлен-
ных процессов, поскольку он не является элементарным.
370
+------------------------------------------------------------+
| алгоритм P /* операция над семафором типа P */ |
| входная информация: (1) семафор |
| (2) приоритет |
| выходная информация: 0 - в случае нормального завершения |
| -1 - в случае аварийного выхода из |
| состояния приостанова по сигналу, при-|
| нятому в режиме ядра |
| { |
| Pprim(semaphore.lock); |
| уменьшить (semaphore.value); |
| если (semaphore.value >= 0) |
| { |
| Vprim(semaphore.lock); |
| вернуть (0); |
| } |
| /* следует перейти в состояние приостанова */ |
| если (проверяются сигналы) |
| { |
| если (имеется сигнал, прерывающий нахождение в сос- |
| тоянии приостанова) |
| { |
| увеличить (semaphore.value); |
| если (сигнал принят в режиме ядра) |
| { |
| Vprim(semaphore.lock); |
| вернуть (-1); |
| } |
| в противном случае |
| { |
| Vprim(semaphore.lock); |
| longjmp; |
| } |
| } |
| } |
| поставить процесс в конец списка приостановленных по се-|
| мафору; |
| Vprim(semaphore.lock); |
| выполнить переключение контекста; |
| проверить сигналы (см. выше); |
| вернуть (0); |
| } |
+------------------------------------------------------------+
Рисунок 12.8. Алгоритм выполнения операции P
Рассмотрим еще один феномен, связанный с использованием семафоров в од-
нопроцессорной системе. Предположим, что два процесса, A и B, конкурируют за
семафор. Процесс A обнаруживает, что семафор свободен и что процесс B приос-
тановлен; значение семафора равно -1. Когда с помощью операции V процесс A
освобождает семафор, он выводит тем самым процесс B из состояния приостанова
и вновь делает значение семафора нулевым. Теперь предположим, что процесс A,
по-прежнему выполняясь в режиме ядра, пытается снова заблокировать семафор.
Производя операцию P, процесс приостановится, поскольку семафор имеет нуле-
вое значение, несмотря на то, что ресурс пока свободен. Системе придется
"раскошелиться" на дополнительное переключение контекста. С другой стороны,
если бы блокировка была реализована на основе однопроцессорной схемы
371
+------------------------------------------------------------+
| алгоритм V /* операция над семафором типа V */ |
| входная информация: адрес семафора |
| выходная информация: отсутствует |
| { |
| Pprim(semaphore.lock); |
| увеличить (semaphore.value); |
| если (semaphore.value <= 0) |
| { |
| удалить из списка процессов, приостановленных по се-|
| мафору, первый по счету процесс; |
| перевести его в состояние готовности к запуску; |
| } |
| Vprim(semaphore.lock); |
| } |
+------------------------------------------------------------+
Рисунок 12.9. Алгоритм выполнения операции V
(sleep-lock), процесс A получил бы право на повторное использование ресурса,
поскольку за это время ни один из процессов не смог бы заблокировать его.
Для этого случая схема sleep-lock более подходит, чем схема с использованием
семафоров.
Когда блокируются сразу несколько семафоров, очередность блокирования
должна исключать возникновение тупиковых ситуаций. В качестве примера расс-
мотрим два семафора, A и B, и два алгоритма, требующих одновременной блоки-
ровки семафоров. Если бы алгоритмы устанавливали блокировку на семафоры в
обратном порядке, как следует из Рисунка 12.11, последовало бы возникновение
тупиковой ситуации; процесс A на одноименном процессоре захватывает семафор
SA, в то время как процесс B на своем процессоре захватывает семафор SB.
Процесс A пытается захватить и семафор SB, но в результате операции P пере-
ходит в состояние приостанова, поскольку значение семафора SB не превышает
0. То же самое происходит с процессом B, когда последний пытается захватить
семафор SA. Ни тот, ни другой процессы продолжаться уже не могут.
Для предотвращения возникновения подобных ситуаций используются соответ-
ствующие алгоритмы обнаружения опасности взаимной блокировки, устанавливаю-
щие наличие опасной ситуации и ликвидирующие ее. Тем не менее, использование
таких алгоритмов "утяжеляет" ядро. Поскольку число ситуаций, в которых про-
цесс должен одновременно захватывать несколько семафоров, довольно ограниче-
но, легче было бы реализовать алгоритмы, предупреждающие возникновение тупи-
ковых ситуаций еще до того, как они будут иметь место. Если, к примеру, ка-
кой-то набор семафоров всегда блокируется в одном и том же порядке, тупико-
вая ситуация никогда не возникнет. Но в том случае, когда захвата семафоров
в обратном порядке избежать не
удается, операция CP предотвратит возникновение тупиковой ситуации (см. Ри-
сунок 12.12): если операция завершится неудачно, процесс B освободит свои
ресурсы, дабы избежать взаимной блокировки, и позже запустит алгоритм на вы-
полнение повторно, скорее всего тогда, когда процесс A завершит работу с ре-
сурсом.
Чтобы предупредить одновременное обращение процессов к ресурсу, програм-
ма обработки прерываний, казалось бы, могла воспользоваться семафором, но
из-за того, что она не может приостанавливать свою работу (см. главу 6), ис-
пользовать операцию P в этой программе нельзя. Вместо этого можно использо-
вать "циклическую блокировку" (spin lock) и не переходить в состояние приос-
танова, как в следующем примере:
while (! CP(semaphore));
372
Процесс A/Процессор A Процесс B/Процессор B
+-----------------------------------------------------------
| - +------------------------+ -
| - | Значение семафора = -1 | -
| - +------------------------+ -
| проверяет(значение сема- -
| фора < 0) ? -
| (да) -
| V(семафор) -
| - -
| - +------------------------+ -
| - | Значение семафора = 0 | -
| - +------------------------+ -
| проверяет(значение сема- -
| фора < 0) ? -
| - -
| - P(семафор)
| - Значение семафора = -1
| -
| (нет)
| НЕВЕРНО !!
v
Время
Рисунок 12.10. Неудачное имитация функции wakeup при исполь-
зовании операции V
Операция повторяется в цикле до тех пор, пока значение семафора не превысит
0; программа обработки прерываний не приостанавливается и цикл завершается
только тогда, когда значение семафора станет положительным, после чего это
значение будет уменьшено операцией CP.
Чтобы предотвратить ситуацию взаимной блокировки, ядру нужно запретить
все прерывания, выполняющие "циклическую блокировку". Иначе выполнение про-
цесса, захватившего семафор, будет прервано еще до того, как он сможет осво-
бодить семафор; если программа обработки прерываний попытается захватить
этот семафор, используя "циклическую блокировку", ядро заблокирует само се-
бя. В качестве примера обратимся к Рисунку 12.13. В момент возникновения
Процесс A/Процессор A Процесс B/Процессор B
+-----------------------------------------------------------
| P(семафор SA); -
| - -
| - -
| - -
| - P(семафор SB);
| - -
| - -
| - -
| - P(семафор SA);
| - приостанавливается
| -
| P(семафор SB);
| приостанавливается
|
v Взаимная блокировка !!
Время
Рисунок 12.11. Возникновение тупиковой ситуации
из-за смены очередности блокирования
373
прерывания значение семафора не превышает 0, поэтому результатом выполнения
операции CP всегда будет "ложь". Проблема решается путем запрещения всех
прерываний на то время, пока семафор захвачен процессом.
В данном разделе мы рассмотрим четыре алгоритма ядра, реализованных с
использованием семафоров. Алгоритм выделения буфера иллюстрирует сложную
схему блокирования, на примере алгоритма wait показана синхронизация выпол-
нения процессов, схема блокирования драйверов реализует изящный подход к ре-
шению данной проблемы, и наконец, метод решения проблемы холостой работы
процессора показывает, что нужно сделать, чтобы избежать конкуренции между
процессами.
Обратимся еще раз к алгоритму getblk, рассмотренному нами в главе 3. Ал-
горитм работает с тремя структурами данных: заголовком буфера, хеш-очередью
буферов и списком свободных буферов. Ядро связывает семафор со всеми экземп-
лярами каждой структуры. Другими словами, если у ядра имеются в распоряжении
200 буферов, заголовок каждого из них включает в себя семафор, используемый
для захвата буфера; когда процесс выполняет над семафором операцию P, другие
процессы, тоже пожелавшие захватить буфер, приостанавливаются до тех пор,
пока первый процесс не исполнит операцию V. У каждой хеш-очереди буферов
также имеется семафор, блокирующий доступ к очереди. В однопроцессорной сис-
теме блокировка хеш-оче-
Процесс A/Процессор A Процесс B/Процессор B
+-----------------------------------------------------------
| P(семафор SA); -
| - -
| - P(семафор SB);
| - -
| - -
| - если (! CP(семафор SA))
| - {
| - V(семафор SB);
| - перезапустить алго-
| - ритм
| - }
| P(семафор SB);
| приостанавливается
v
Время
Рисунок 12.12. Использование операции P условного типа для
предотвращения взаимной блокировки
реди не нужна, ибо процесс никогда не переходит в состояние приостанова, ос-
тавляя очередь в несогласованном (неупорядоченном) виде. В многопроцессорной
системе, тем не менее, возможны ситуации, когда с одной и той же хеш-оче-
редью работают два процесса; в каждый момент времени семафор открывает дос-
374
туп к очереди только для одного процесса. По тем же причинам и список сво-
бодных буферов нуждается в семафоре для защиты содержащейся в нем информации
от искажения.
На Рисунке 12.14 показана первая часть алгоритма getblk, реализованная в
многопроцессорной системе с использованием семафоров. Просматривая буферный
кеш в поисках указанного блока, ядро с помощью операции P захватывает сема-
фор, принадлежащий хеш-очереди. Если над семафором уже кем-то произведена
операция данного типа, текущий процесс приостанавливается до тех пор, пока
процесс, захвативший семафор, не освободит его, выполнив операцию V. Когда
текущий процесс получает право исключительного контроля над хеш-очередью, он
приступает к поиску подходящего буфера. Предположим, что буфер находится в
хеш-очереди. Ядро (процесс A) пытается захватить буфер, но если оно исполь-
зует операцию P и если буфер уже захвачен, ядру придется приостановить свою
работу, оставив хеш-очередь заблокированной и не допуская таким образом об-
ращений к ней со стороны других процессов, даже если последние ведут поиск
незахваченных буферов. Пусть вместо этого процесс A захватывает буфер, ис-
пользуя операцию CP; если операция завершается успешно, буфер становится от-
крытым для процесса. Процесс A захватывает семафор, принадлежащий списку
свободных буферов, выполняя операцию CP, поскольку семафор захватывается на
непродолжительное время и, следовательно, приостанавливать свою работу, вы-
полняя операцию P, процесс просто не имеет возможности. Ядро убирает буфер
из списка свободных буферов, снимает блокировку со списка и с хеш-очереди и
возвращает захваченный буфер.
|
| P(семафор);
| (Значение семафора теперь равно 0)
|
| Прерывание
|
| CP(семафор) завершается неудачно ---
| семафор захвачен
|
| Семафор не освобождается до выхода из прерывания.
|
| Выход из прерывания без его обработки невозможен.
|
| Тупиковая ситуация (взаимная блокировка)
v
Время
Рисунок 12.13. Взаимная блокировка при выполнении программы
обработки прерывания
Предположим, что операция CP над буфером завершилась неудачно из-за то-
го, что семафор, принадлежащий буферу, оказался захваченным. Процесс A осво-
бождает семафор, связанный с хеш-очередью, и приостанавливается, пытаясь вы-
полнить операцию P над семафором буфера. Операция P над семафором будет вы-
полняться, несмотря на то, что операция CP уже потерпела неудачу. По завер-
шении выполнения операции процесс A получает власть над буфером. Так как в
оставшейся части алгоритма предполагается, что буфер и хеш-очередь захваче-
ны, процесс A теперь пытается захватить хеш-очередь (*). Поскольку очеред-
---------------------------------------
(*) Вместо захвата хеш-очереди в этом месте можно было бы установить соот-
ветствующий флаг, проверяемый далее перед выполнением операции V, но
чтобы проиллюстрировать схему захвата семафоров в обратной последова-
тельности, в изложении мы будем придерживаться ранее описанного вариан-
та.
375
ность захвата здесь (сначала семафор буфера, потом семафор очереди) обратна
вышеуказанной очередности, над семафором выполняется операция CP. Если по-
пытка захвата заканчивается неудачей, имеет место обычная обработка, требую-
щаяся по ходу задачи. Но если захват удается, ядро не может быть уверено в
+------------------------------------------------------------+
| алгоритм getblk /* многопроцессорная версия */ |
| входная информация: номер файловой системы |
| номер блока |
| выходная информация: захваченный буфер, предназначенный для|
| обработки содержимого блока |
| { |
| выполнять (пока буфер не будет обнаружен) |
| { |
| P(семафор хеш-очереди); |
| если (блок находится в хеш-очереди) |
| { |
| если (операция CP(семафор буфера) завершается не- |
| удачно) /* буфер занят */ |
| { |
| V(семафор хеш-очереди); |
| P(семафор буфера); /* приостанов до момен-|
| * та освобождения |
| */ |
| если (операция CP(семафор хеш-очереди) заверша-|
| ется неудачно) |
| { |
| V(семафор буфера); |
| продолжить; /* выход в цикл "выполнять" |
| */ |
| } |
| в противном случае если (номер устройства или |
| номер блока изменились) |
| { |
| V(семафор буфера); |
| V(семафор хеш-очереди); |
| } |
| } |
| выполнять (пока операция CP(семафор списка свобод-|
| ных буферов) не завершится успешно) |
| ; /* "кольцевой цикл" */ |
| пометить буфер занятым; |
| убрать буфер из списка свободных буферов; |
| V(семафор списка свободных буферов); |
| V(семафор хеш-очереди); |
| вернуть буфер; |
| } |
| в противном случае /* буфер отсутствует в хеш- |
| * очереди |
| */ |
| /* здесь начинается выполнение оставшейся части алго-|
| * ритма |
| */ |
| } |
| } |
+------------------------------------------------------------+
Рисунок 12.14. Выделение буфера с использованием семафоров
376
том, что захвачен корректный буфер, поскольку содержимое буфера могло быть
ранее изменено другим процессом, обнаружившим буфер в списке свободных буфе-
ров и захватившим на время его семафор. Процесс A, ожидая освобождения сема-
фора, не имеет ни малейшего представления о том, является ли интересующий
его буфер тем буфером, который ему нужен, и поэтому прежде всего он должен
убедиться в правильности содержимого буфера; если проверка дает отрицатель-
ный результат, алгоритм запускается сначала. Если содержимое буфера коррект-
но, процесс A завершает выполнение алгоритма.
+------------------------------------------------------------+
| многопроцессорная версия алгоритма wait |
| { |
| для (;;) /* цикл */ |
| { |
| перебор всех процессов-потомков: |
| если (потомок находится в состоянии "прекращения |
| существования") |
| вернуть управление; |
| P(zombie_semaphore); /* начальное значение - 0 */|
| } |
| } |
+------------------------------------------------------------+
Рисунок 12.15. Многопроцессорная версия алгоритма wait
Оставшуюся часть алгоритма можно рассмотреть в качестве упражнения.
Из главы 7 мы уже знаем о том, что во время выполнения системной функции
wait процесс приостанавливает свою работу до момента завершения выполнения
своего потомка. В многопроцессорной системе перед процессом встает задача не
упустить при выполнении алгоритма wait потомка, прекратившего существование
с помощью функции exit; если, например, в то время, пока на одном процессоре
процесс-родитель запускает функцию wait, на другом процессоре его потомок
завершил свою работу, родителю нет необходимости приостанавливать свое вы-
полнение в ожидании завершения второго потомка. В каждой записи таблицы про-
цессов имеется семафор, именуемый zombie_semaphore и имеющий в начале нуле-
вое значение. Этот семафор используется при организации взаимодействия
wait/exit (Рисунок 12.15). Когда потомок завершает работу, он выполняет над
семафором своего родителя операцию V, выводя родителя из состояния приоста-
нова, если тот перешел в него во время исполнения функции wait. Если потомок
завершился раньше, чем родитель запустил функцию wait, этот факт будет обна-
ружен родителем, который тут же выйдет из состояния ожидания. Если оба про-
цесса исполняют функции exit и wait параллельно, но потомок исполняет функ-
цию exit уже после того, как родитель проверил его статус, операция V, вы-
полненная потомком, воспрепятствует переходу родителя в состояние приостано-
ва. В худшем случае процесс-родитель просто повторяет цикл лишний раз.
В многопроцессорной реализации вычислительной системы на базе компьюте-
ров AT&T 3B20 семафоры в структуру загрузочного кода драйверов не включают-
ся, а операции типа P и V выполняются в точках входа в каждый драйвер (см.
[Bach 84]). В главе 10 мы говорили о том, что интерфейс, реализуемый драйве-
рами устройств, характеризуется очень небольшим числом точек входа (на прак-
377
тике их около 20). Защита драйверов осуществляется на уровне точек входа в
них:
P(семафор драйвера);
открыть (драйвер);
V(семафор драйвера);
Если для всех точек входа в драйвер использовать один и тот же семафор,
но при этом для разных драйверов - разные семафоры, критический участок
программы драйвера будет исполняться процессом монопольно. Семафоры могут
назначаться как отдельному устройству, так и классам устройств. Так, напри-
мер, отдельный семафор может быть связан и с отдельным физическим терминалом
и со всеми терминалами сразу. В первом случае быстродействие системы выше,
ибо процессы, обращающиеся к терминалу, не захватывают семафор, имеющий от-
ношение к другим терминалам, как во втором случае. Драйверы некоторых уст-
ройств, однако, поддерживают внутреннюю связь с другими драйверами; в таких
случаях использование одного семафора для класса устройств облегчает понима-
ние задачи. В качестве альтернативы в вычислительной системе 3B20A предос-
тавлена возможность такого конфигурирования отдельных устройств, при котором
программы драйвера запускаются на точно указанных процессорах.
Проблемы возникают тогда, когда драйвер прерывает работу системы и его
семафор захвачен: программа обработки прерываний не может быть вызвана, так
как иначе возникла бы угроза разрушения данных. С другой стороны, ядро не
может оставить прерывание необработанным. Система 3B20A выстраивает прерыва-
ния в очередь и ждет момента освобождения семафора, когда вызов программы
обработки прерываний не будет иметь опасные последствия.
Когда ядро выполняет переключение контекста в однопроцессорной системе,
оно функционирует в контексте процесса, уступающего управление (см. главу
6). Если в системе нет процессов, готовых к запуску, ядро переходит в состо-
яние простоя в контексте процесса, выполнявшегося последним. Получив преры-
вание от таймера или других периферийных устройств, оно обрабатывает его в
контексте того же процесса.
В многопроцессорной системе ядро не может простаивать в контексте про-
цесса, выполнявшегося последним. Посмотрим, что произойдет после того, как
процесс, приостановивший свою работу на процессоре A, выйдет из состояния
приостанова. Процесс в целом готов к запуску, но он запускается не сразу же
по выходе из состояния приостанова, даже несмотря на то, что его контекст
уже находится в распоряжении процессора A. Если этот процесс выбирается для
запуска процессором B, последний переключается на его контекст и возобновля-
ет его выполнение. Когда в результате прерывания процессор A выйдет из прос-
тоя, он будет продолжать свою работу в контексте процесса A до тех пор, пока
не произведет переключение контекста. Таким образом, в течение короткого
промежутка времени с одним и тем же адресным пространством (в частности, со
стеком ядра) будут вести работу (и, что весьма вероятно, производить запись)
сразу два процессора.
Решение этой проблемы состоит в создании некоторого фиктивного процесса;
когда процессор находится в состоянии простоя, ядро переключается на кон-
текст фиктивного процесса, делая этот контекст текущим для бездействующего
| struct semaphore { |
| int lock; |
| }; |
| |
| Init(semaphore) |
| struct semaphore semaphore; |
| { |
| semaphore.lock = 1; |
| } |
| |
| Pprim(semaphore) |
| struct semaphore semaphore; |
| { |
| while (read_and_clear(semaphore.lock)) |
| ; |
| } |
| |
| Vprim(semaphore) |
| struct semaphore semaphore; |
| { |
| semaphore.lock = 1; |
| } |
+-------------------------------------------------------+
Рисунок 12.7. Операции над семафором, использующие инструкцию
read and clear
состояние приостанова в связи с невозможностью обработки больших объемов ин-
формации. Позже, когда драйвер будет готов к приему следующей порции данных,
он возобновит все приостановленные им процессы. Использование операций P и V
в тех случаях, когда устанавливающие блокировку процессы получают доступ к
ресурсу поочередно, а все остальные процессы - в порядке поступления запро-
сов, является более предпочтительным. В сравнении с однопроцессорной проце-
дурой блокирования (sleep-lock) данная схема обычно выигрывает, так как если
при наступлении события все процессы возобновляются, большинство из них мо-
жет вновь наткнуться на блокировку и снова перейти в состояние приостанова.
С другой стороны, в тех случаях, когда требуется вывести из состояния приос-
танова все процессы одновременно, использование операций P и V представляет
известную сложность.
Если операция возвращает значение семафора, является ли она эквивалент-
ной функции wakeup ?
while (value(semaphore) < 0)
V(semaphore);
Если вмешательства со стороны других процессов нет, ядро повторяет цикл
до тех пор, пока значение семафора не станет больше или равно 0, ибо это оз-
начает, что в состоянии приостанова по семафору нет больше ни одного процес-
са. Тем не менее, нельзя исклю-
чить и такую возможность, что сразу после того, как процесс A при тестирова-
нии семафора на одноименном процессоре обнаружил нулевое значение семафора,
процесс B на своем процессоре выполняет операцию P, уменьшая значение сема-
фора до -1 (Рисунок 12.10). Процесс A продолжит свое выполнение, думая, что
им возобновлены все приостановленные по семафору процессы. Таким образом,
цикл выполнения операции не дает гарантии возобновления всех приостановлен-
ных процессов, поскольку он не является элементарным.
370
+------------------------------------------------------------+
| алгоритм P /* операция над семафором типа P */ |
| входная информация: (1) семафор |
| (2) приоритет |
| выходная информация: 0 - в случае нормального завершения |
| -1 - в случае аварийного выхода из |
| состояния приостанова по сигналу, при-|
| нятому в режиме ядра |
| { |
| Pprim(semaphore.lock); |
| уменьшить (semaphore.value); |
| если (semaphore.value >= 0) |
| { |
| Vprim(semaphore.lock); |
| вернуть (0); |
| } |
| /* следует перейти в состояние приостанова */ |
| если (проверяются сигналы) |
| { |
| если (имеется сигнал, прерывающий нахождение в сос- |
| тоянии приостанова) |
| { |
| увеличить (semaphore.value); |
| если (сигнал принят в режиме ядра) |
| { |
| Vprim(semaphore.lock); |
| вернуть (-1); |
| } |
| в противном случае |
| { |
| Vprim(semaphore.lock); |
| longjmp; |
| } |
| } |
| } |
| поставить процесс в конец списка приостановленных по се-|
| мафору; |
| Vprim(semaphore.lock); |
| выполнить переключение контекста; |
| проверить сигналы (см. выше); |
| вернуть (0); |
| } |
+------------------------------------------------------------+
Рисунок 12.8. Алгоритм выполнения операции P
Рассмотрим еще один феномен, связанный с использованием семафоров в од-
нопроцессорной системе. Предположим, что два процесса, A и B, конкурируют за
семафор. Процесс A обнаруживает, что семафор свободен и что процесс B приос-
тановлен; значение семафора равно -1. Когда с помощью операции V процесс A
освобождает семафор, он выводит тем самым процесс B из состояния приостанова
и вновь делает значение семафора нулевым. Теперь предположим, что процесс A,
по-прежнему выполняясь в режиме ядра, пытается снова заблокировать семафор.
Производя операцию P, процесс приостановится, поскольку семафор имеет нуле-
вое значение, несмотря на то, что ресурс пока свободен. Системе придется
"раскошелиться" на дополнительное переключение контекста. С другой стороны,
если бы блокировка была реализована на основе однопроцессорной схемы
371
+------------------------------------------------------------+
| алгоритм V /* операция над семафором типа V */ |
| входная информация: адрес семафора |
| выходная информация: отсутствует |
| { |
| Pprim(semaphore.lock); |
| увеличить (semaphore.value); |
| если (semaphore.value <= 0) |
| { |
| удалить из списка процессов, приостановленных по се-|
| мафору, первый по счету процесс; |
| перевести его в состояние готовности к запуску; |
| } |
| Vprim(semaphore.lock); |
| } |
+------------------------------------------------------------+
Рисунок 12.9. Алгоритм выполнения операции V
(sleep-lock), процесс A получил бы право на повторное использование ресурса,
поскольку за это время ни один из процессов не смог бы заблокировать его.
Для этого случая схема sleep-lock более подходит, чем схема с использованием
семафоров.
Когда блокируются сразу несколько семафоров, очередность блокирования
должна исключать возникновение тупиковых ситуаций. В качестве примера расс-
мотрим два семафора, A и B, и два алгоритма, требующих одновременной блоки-
ровки семафоров. Если бы алгоритмы устанавливали блокировку на семафоры в
обратном порядке, как следует из Рисунка 12.11, последовало бы возникновение
тупиковой ситуации; процесс A на одноименном процессоре захватывает семафор
SA, в то время как процесс B на своем процессоре захватывает семафор SB.
Процесс A пытается захватить и семафор SB, но в результате операции P пере-
ходит в состояние приостанова, поскольку значение семафора SB не превышает
0. То же самое происходит с процессом B, когда последний пытается захватить
семафор SA. Ни тот, ни другой процессы продолжаться уже не могут.
Для предотвращения возникновения подобных ситуаций используются соответ-
ствующие алгоритмы обнаружения опасности взаимной блокировки, устанавливаю-
щие наличие опасной ситуации и ликвидирующие ее. Тем не менее, использование
таких алгоритмов "утяжеляет" ядро. Поскольку число ситуаций, в которых про-
цесс должен одновременно захватывать несколько семафоров, довольно ограниче-
но, легче было бы реализовать алгоритмы, предупреждающие возникновение тупи-
ковых ситуаций еще до того, как они будут иметь место. Если, к примеру, ка-
кой-то набор семафоров всегда блокируется в одном и том же порядке, тупико-
вая ситуация никогда не возникнет. Но в том случае, когда захвата семафоров
в обратном порядке избежать не
удается, операция CP предотвратит возникновение тупиковой ситуации (см. Ри-
сунок 12.12): если операция завершится неудачно, процесс B освободит свои
ресурсы, дабы избежать взаимной блокировки, и позже запустит алгоритм на вы-
полнение повторно, скорее всего тогда, когда процесс A завершит работу с ре-
сурсом.
Чтобы предупредить одновременное обращение процессов к ресурсу, програм-
ма обработки прерываний, казалось бы, могла воспользоваться семафором, но
из-за того, что она не может приостанавливать свою работу (см. главу 6), ис-
пользовать операцию P в этой программе нельзя. Вместо этого можно использо-
вать "циклическую блокировку" (spin lock) и не переходить в состояние приос-
танова, как в следующем примере:
while (! CP(semaphore));
372
Процесс A/Процессор A Процесс B/Процессор B
+-----------------------------------------------------------
| - +------------------------+ -
| - | Значение семафора = -1 | -
| - +------------------------+ -
| проверяет(значение сема- -
| фора < 0) ? -
| (да) -
| V(семафор) -
| - -
| - +------------------------+ -
| - | Значение семафора = 0 | -
| - +------------------------+ -
| проверяет(значение сема- -
| фора < 0) ? -
| - -
| - P(семафор)
| - Значение семафора = -1
| -
| (нет)
| НЕВЕРНО !!
v
Время
Рисунок 12.10. Неудачное имитация функции wakeup при исполь-
зовании операции V
Операция повторяется в цикле до тех пор, пока значение семафора не превысит
0; программа обработки прерываний не приостанавливается и цикл завершается
только тогда, когда значение семафора станет положительным, после чего это
значение будет уменьшено операцией CP.
Чтобы предотвратить ситуацию взаимной блокировки, ядру нужно запретить
все прерывания, выполняющие "циклическую блокировку". Иначе выполнение про-
цесса, захватившего семафор, будет прервано еще до того, как он сможет осво-
бодить семафор; если программа обработки прерываний попытается захватить
этот семафор, используя "циклическую блокировку", ядро заблокирует само се-
бя. В качестве примера обратимся к Рисунку 12.13. В момент возникновения
Процесс A/Процессор A Процесс B/Процессор B
+-----------------------------------------------------------
| P(семафор SA); -
| - -
| - -
| - -
| - P(семафор SB);
| - -
| - -
| - -
| - P(семафор SA);
| - приостанавливается
| -
| P(семафор SB);
| приостанавливается
|
v Взаимная блокировка !!
Время
Рисунок 12.11. Возникновение тупиковой ситуации
из-за смены очередности блокирования
373
прерывания значение семафора не превышает 0, поэтому результатом выполнения
операции CP всегда будет "ложь". Проблема решается путем запрещения всех
прерываний на то время, пока семафор захвачен процессом.
В данном разделе мы рассмотрим четыре алгоритма ядра, реализованных с
использованием семафоров. Алгоритм выделения буфера иллюстрирует сложную
схему блокирования, на примере алгоритма wait показана синхронизация выпол-
нения процессов, схема блокирования драйверов реализует изящный подход к ре-
шению данной проблемы, и наконец, метод решения проблемы холостой работы
процессора показывает, что нужно сделать, чтобы избежать конкуренции между
процессами.
Обратимся еще раз к алгоритму getblk, рассмотренному нами в главе 3. Ал-
горитм работает с тремя структурами данных: заголовком буфера, хеш-очередью
буферов и списком свободных буферов. Ядро связывает семафор со всеми экземп-
лярами каждой структуры. Другими словами, если у ядра имеются в распоряжении
200 буферов, заголовок каждого из них включает в себя семафор, используемый
для захвата буфера; когда процесс выполняет над семафором операцию P, другие
процессы, тоже пожелавшие захватить буфер, приостанавливаются до тех пор,
пока первый процесс не исполнит операцию V. У каждой хеш-очереди буферов
также имеется семафор, блокирующий доступ к очереди. В однопроцессорной сис-
теме блокировка хеш-оче-
Процесс A/Процессор A Процесс B/Процессор B
+-----------------------------------------------------------
| P(семафор SA); -
| - -
| - P(семафор SB);
| - -
| - -
| - если (! CP(семафор SA))
| - {
| - V(семафор SB);
| - перезапустить алго-
| - ритм
| - }
| P(семафор SB);
| приостанавливается
v
Время
Рисунок 12.12. Использование операции P условного типа для
предотвращения взаимной блокировки
реди не нужна, ибо процесс никогда не переходит в состояние приостанова, ос-
тавляя очередь в несогласованном (неупорядоченном) виде. В многопроцессорной
системе, тем не менее, возможны ситуации, когда с одной и той же хеш-оче-
редью работают два процесса; в каждый момент времени семафор открывает дос-
374
туп к очереди только для одного процесса. По тем же причинам и список сво-
бодных буферов нуждается в семафоре для защиты содержащейся в нем информации
от искажения.
На Рисунке 12.14 показана первая часть алгоритма getblk, реализованная в
многопроцессорной системе с использованием семафоров. Просматривая буферный
кеш в поисках указанного блока, ядро с помощью операции P захватывает сема-
фор, принадлежащий хеш-очереди. Если над семафором уже кем-то произведена
операция данного типа, текущий процесс приостанавливается до тех пор, пока
процесс, захвативший семафор, не освободит его, выполнив операцию V. Когда
текущий процесс получает право исключительного контроля над хеш-очередью, он
приступает к поиску подходящего буфера. Предположим, что буфер находится в
хеш-очереди. Ядро (процесс A) пытается захватить буфер, но если оно исполь-
зует операцию P и если буфер уже захвачен, ядру придется приостановить свою
работу, оставив хеш-очередь заблокированной и не допуская таким образом об-
ращений к ней со стороны других процессов, даже если последние ведут поиск
незахваченных буферов. Пусть вместо этого процесс A захватывает буфер, ис-
пользуя операцию CP; если операция завершается успешно, буфер становится от-
крытым для процесса. Процесс A захватывает семафор, принадлежащий списку
свободных буферов, выполняя операцию CP, поскольку семафор захватывается на
непродолжительное время и, следовательно, приостанавливать свою работу, вы-
полняя операцию P, процесс просто не имеет возможности. Ядро убирает буфер
из списка свободных буферов, снимает блокировку со списка и с хеш-очереди и
возвращает захваченный буфер.
|
| P(семафор);
| (Значение семафора теперь равно 0)
|
| Прерывание
|
| CP(семафор) завершается неудачно ---
| семафор захвачен
|
| Семафор не освобождается до выхода из прерывания.
|
| Выход из прерывания без его обработки невозможен.
|
| Тупиковая ситуация (взаимная блокировка)
v
Время
Рисунок 12.13. Взаимная блокировка при выполнении программы
обработки прерывания
Предположим, что операция CP над буфером завершилась неудачно из-за то-
го, что семафор, принадлежащий буферу, оказался захваченным. Процесс A осво-
бождает семафор, связанный с хеш-очередью, и приостанавливается, пытаясь вы-
полнить операцию P над семафором буфера. Операция P над семафором будет вы-
полняться, несмотря на то, что операция CP уже потерпела неудачу. По завер-
шении выполнения операции процесс A получает власть над буфером. Так как в
оставшейся части алгоритма предполагается, что буфер и хеш-очередь захваче-
ны, процесс A теперь пытается захватить хеш-очередь (*). Поскольку очеред-
---------------------------------------
(*) Вместо захвата хеш-очереди в этом месте можно было бы установить соот-
ветствующий флаг, проверяемый далее перед выполнением операции V, но
чтобы проиллюстрировать схему захвата семафоров в обратной последова-
тельности, в изложении мы будем придерживаться ранее описанного вариан-
та.
375
ность захвата здесь (сначала семафор буфера, потом семафор очереди) обратна
вышеуказанной очередности, над семафором выполняется операция CP. Если по-
пытка захвата заканчивается неудачей, имеет место обычная обработка, требую-
щаяся по ходу задачи. Но если захват удается, ядро не может быть уверено в
+------------------------------------------------------------+
| алгоритм getblk /* многопроцессорная версия */ |
| входная информация: номер файловой системы |
| номер блока |
| выходная информация: захваченный буфер, предназначенный для|
| обработки содержимого блока |
| { |
| выполнять (пока буфер не будет обнаружен) |
| { |
| P(семафор хеш-очереди); |
| если (блок находится в хеш-очереди) |
| { |
| если (операция CP(семафор буфера) завершается не- |
| удачно) /* буфер занят */ |
| { |
| V(семафор хеш-очереди); |
| P(семафор буфера); /* приостанов до момен-|
| * та освобождения |
| */ |
| если (операция CP(семафор хеш-очереди) заверша-|
| ется неудачно) |
| { |
| V(семафор буфера); |
| продолжить; /* выход в цикл "выполнять" |
| */ |
| } |
| в противном случае если (номер устройства или |
| номер блока изменились) |
| { |
| V(семафор буфера); |
| V(семафор хеш-очереди); |
| } |
| } |
| выполнять (пока операция CP(семафор списка свобод-|
| ных буферов) не завершится успешно) |
| ; /* "кольцевой цикл" */ |
| пометить буфер занятым; |
| убрать буфер из списка свободных буферов; |
| V(семафор списка свободных буферов); |
| V(семафор хеш-очереди); |
| вернуть буфер; |
| } |
| в противном случае /* буфер отсутствует в хеш- |
| * очереди |
| */ |
| /* здесь начинается выполнение оставшейся части алго-|
| * ритма |
| */ |
| } |
| } |
+------------------------------------------------------------+
Рисунок 12.14. Выделение буфера с использованием семафоров
376
том, что захвачен корректный буфер, поскольку содержимое буфера могло быть
ранее изменено другим процессом, обнаружившим буфер в списке свободных буфе-
ров и захватившим на время его семафор. Процесс A, ожидая освобождения сема-
фора, не имеет ни малейшего представления о том, является ли интересующий
его буфер тем буфером, который ему нужен, и поэтому прежде всего он должен
убедиться в правильности содержимого буфера; если проверка дает отрицатель-
ный результат, алгоритм запускается сначала. Если содержимое буфера коррект-
но, процесс A завершает выполнение алгоритма.
+------------------------------------------------------------+
| многопроцессорная версия алгоритма wait |
| { |
| для (;;) /* цикл */ |
| { |
| перебор всех процессов-потомков: |
| если (потомок находится в состоянии "прекращения |
| существования") |
| вернуть управление; |
| P(zombie_semaphore); /* начальное значение - 0 */|
| } |
| } |
+------------------------------------------------------------+
Рисунок 12.15. Многопроцессорная версия алгоритма wait
Оставшуюся часть алгоритма можно рассмотреть в качестве упражнения.
Из главы 7 мы уже знаем о том, что во время выполнения системной функции
wait процесс приостанавливает свою работу до момента завершения выполнения
своего потомка. В многопроцессорной системе перед процессом встает задача не
упустить при выполнении алгоритма wait потомка, прекратившего существование
с помощью функции exit; если, например, в то время, пока на одном процессоре
процесс-родитель запускает функцию wait, на другом процессоре его потомок
завершил свою работу, родителю нет необходимости приостанавливать свое вы-
полнение в ожидании завершения второго потомка. В каждой записи таблицы про-
цессов имеется семафор, именуемый zombie_semaphore и имеющий в начале нуле-
вое значение. Этот семафор используется при организации взаимодействия
wait/exit (Рисунок 12.15). Когда потомок завершает работу, он выполняет над
семафором своего родителя операцию V, выводя родителя из состояния приоста-
нова, если тот перешел в него во время исполнения функции wait. Если потомок
завершился раньше, чем родитель запустил функцию wait, этот факт будет обна-
ружен родителем, который тут же выйдет из состояния ожидания. Если оба про-
цесса исполняют функции exit и wait параллельно, но потомок исполняет функ-
цию exit уже после того, как родитель проверил его статус, операция V, вы-
полненная потомком, воспрепятствует переходу родителя в состояние приостано-
ва. В худшем случае процесс-родитель просто повторяет цикл лишний раз.
В многопроцессорной реализации вычислительной системы на базе компьюте-
ров AT&T 3B20 семафоры в структуру загрузочного кода драйверов не включают-
ся, а операции типа P и V выполняются в точках входа в каждый драйвер (см.
[Bach 84]). В главе 10 мы говорили о том, что интерфейс, реализуемый драйве-
рами устройств, характеризуется очень небольшим числом точек входа (на прак-
377
тике их около 20). Защита драйверов осуществляется на уровне точек входа в
них:
P(семафор драйвера);
открыть (драйвер);
V(семафор драйвера);
Если для всех точек входа в драйвер использовать один и тот же семафор,
но при этом для разных драйверов - разные семафоры, критический участок
программы драйвера будет исполняться процессом монопольно. Семафоры могут
назначаться как отдельному устройству, так и классам устройств. Так, напри-
мер, отдельный семафор может быть связан и с отдельным физическим терминалом
и со всеми терминалами сразу. В первом случае быстродействие системы выше,
ибо процессы, обращающиеся к терминалу, не захватывают семафор, имеющий от-
ношение к другим терминалам, как во втором случае. Драйверы некоторых уст-
ройств, однако, поддерживают внутреннюю связь с другими драйверами; в таких
случаях использование одного семафора для класса устройств облегчает понима-
ние задачи. В качестве альтернативы в вычислительной системе 3B20A предос-
тавлена возможность такого конфигурирования отдельных устройств, при котором
программы драйвера запускаются на точно указанных процессорах.
Проблемы возникают тогда, когда драйвер прерывает работу системы и его
семафор захвачен: программа обработки прерываний не может быть вызвана, так
как иначе возникла бы угроза разрушения данных. С другой стороны, ядро не
может оставить прерывание необработанным. Система 3B20A выстраивает прерыва-
ния в очередь и ждет момента освобождения семафора, когда вызов программы
обработки прерываний не будет иметь опасные последствия.
Когда ядро выполняет переключение контекста в однопроцессорной системе,
оно функционирует в контексте процесса, уступающего управление (см. главу
6). Если в системе нет процессов, готовых к запуску, ядро переходит в состо-
яние простоя в контексте процесса, выполнявшегося последним. Получив преры-
вание от таймера или других периферийных устройств, оно обрабатывает его в
контексте того же процесса.
В многопроцессорной системе ядро не может простаивать в контексте про-
цесса, выполнявшегося последним. Посмотрим, что произойдет после того, как
процесс, приостановивший свою работу на процессоре A, выйдет из состояния
приостанова. Процесс в целом готов к запуску, но он запускается не сразу же
по выходе из состояния приостанова, даже несмотря на то, что его контекст
уже находится в распоряжении процессора A. Если этот процесс выбирается для
запуска процессором B, последний переключается на его контекст и возобновля-
ет его выполнение. Когда в результате прерывания процессор A выйдет из прос-
тоя, он будет продолжать свою работу в контексте процесса A до тех пор, пока
не произведет переключение контекста. Таким образом, в течение короткого
промежутка времени с одним и тем же адресным пространством (в частности, со
стеком ядра) будут вести работу (и, что весьма вероятно, производить запись)
сразу два процессора.
Решение этой проблемы состоит в создании некоторого фиктивного процесса;
когда процессор находится в состоянии простоя, ядро переключается на кон-
текст фиктивного процесса, делая этот контекст текущим для бездействующего