Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
Подобный материал:
1   ...   47   48   49   50   51   52   53   54   55

│ } │

│ в противном случае │

│ { │

│ Vprim(semaphore.lock); │

│ longjmp; │

│ } │

│ } │

│ } │

│ поставить процесс в конец списка приостановленных по се-│

│ мафору; │

│ Vprim(semaphore.lock); │

│ выполнить переключение контекста; │

│ проверить сигналы (см. выше); │

│ вернуть (0); │

│ } │

L-------------------------------------------------------------

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

чить и такую возможность, что сразу после того, как процесс A при

тестировании семафора на одноименном процессоре обнаружил нулевое

значение семафора, процесс B на своем процессоре выполняет опера-

цию P, уменьшая значение семафора до -1 (Рисунок 12.10). Процесс

A продолжит свое выполнение, думая, что им возобновлены все при-

остановленные по семафору процессы. Таким образом, цикл выполне-

ния операции не дает гарантии возобновления всех приостановленных

процессов, поскольку он не является элементарным.

-------------------------------------------------------------┐

│ алгоритм V /* операция над семафором типа V */ │

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

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

│ { │

│ Pprim(semaphore.lock); │

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

│ если (semaphore.value <= 0) │

│ { │

│ удалить из списка процессов, приостановленных по се-│

│ мафору, первый по счету процесс; │

│ перевести его в состояние готовности к запуску; │

│ } │

│ Vprim(semaphore.lock); │

│ } │

L-------------------------------------------------------------

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


Рассмотрим еще один феномен, связанный с использованием сема-

форов в однопроцессорной системе. Предположим, что два процесса,

A и B, конкурируют за семафор. Процесс A обнаруживает, что сема-

фор свободен и что процесс B приостановлен; значение семафора

равно -1. Когда с помощью операции V процесс A освобождает сема-

фор, он выводит тем самым процесс B из состояния приостанова и

вновь делает значение семафора нулевым. Теперь предположим, что

процесс A, по-прежнему выполняясь в режиме ядра, пытается снова

заблокировать семафор. Производя операцию P, процесс приостано-

вится, поскольку семафор имеет нулевое значение, несмотря на то,

что ресурс пока свободен. Системе придется "раскошелиться" на до-

полнительное переключение контекста. С другой стороны, если бы

блокировка была реализована на основе однопроцессорной схемы

(sleep-lock), процесс A получил бы право на повторное использова-

ние ресурса, поскольку за это время ни один из процессов не смог

бы заблокировать его. Для этого случая схема sleep-lock более

подходит, чем схема с использованием семафоров.

Когда блокируются сразу несколько семафоров, очередность бло-

кирования должна исключать возникновение тупиковых ситуаций. В

качестве примера рассмотрим два семафора, A и B, и два алгоритма,

требующих одновременной блокировки семафоров. Если бы алгоритмы

устанавливали блокировку на семафоры в обратном порядке, как сле-

дует из Рисунка 12.11, последовало бы возникновение тупиковой си-

туации; процесс A на одноименном процессоре захватывает семафор

SA, в то время как процесс B на своем процессоре захватывает се-

мафор SB. Процесс A пытается захватить и семафор SB, но в резуль-

тате операции P переходит в состояние приостанова, поскольку зна-

чение семафора SB не превышает 0. То же самое происходит с про-

цессом B, когда последний пытается захватить семафор SA. Ни тот,

ни другой процессы продолжаться уже не могут.

Для предотвращения возникновения подобных ситуаций использу-

ются соответствующие алгоритмы обнаружения опасности взаимной

блокировки, устанавливающие наличие опасной ситуации и ликвидиру-

ющие ее. Тем не менее, использование таких алгоритмов "утяжеляет"

ядро. Поскольку число ситуаций, в которых процесс должен одновре-

менно захватывать несколько семафоров, довольно ограничено, легче

было бы реализовать алгоритмы, предупреждающие возникновение ту-

пиковых ситуаций еще до того, как они будут иметь место. Если,

к примеру, какой-то набор семафоров всегда блокируется в одном и

том же порядке, тупиковая ситуация никогда не возникнет. Но в том

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


Процесс A/Процессор A Процесс B/Процессор B

------------------------------------------------------------

│ -------------------------┐

│ │ Значение семафора = -1 │

│ L-------------------------

│ проверяет(значение сема-

│ фора < 0) ?

│ (да)

│ V(семафор)

│

│ -------------------------┐

│ │ Значение семафора = 0 │

│ L-------------------------

│ проверяет(значение сема-

│ фора < 0) ?

│

│ P(семафор)

│ Значение семафора = -1

│

│ (нет)

│ НЕВЕРНО !!

v

Время

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

зовании операции V

удается, операция CP предотвратит возникновение тупиковой ситуа-

ции (см. Рисунок 12.12): если операция завершится неудачно, про-

цесс B освободит свои ресурсы, дабы избежать взаимной блокировки,

и позже запустит алгоритм на выполнение повторно, скорее всего

тогда, когда процесс A завершит работу с ресурсом.

Чтобы предупредить одновременное обращение процессов к ресур-

су, программа обработки прерываний, казалось бы, могла воспользо-

ваться семафором, но из-за того, что она не может приостанавли-

вать свою работу (см. главу 6), использовать операцию P в этой

программе нельзя. Вместо этого можно использовать "циклическую

блокировку" (spin lock) и не переходить в состояние приостанова,

как в следующем примере:

while (! CP(semaphore));

Операция повторяется в цикле до тех пор, пока значение семафора

не превысит 0; программа обработки прерываний не приостанавлива-

ется и цикл завершается только тогда, когда значение семафора

станет положительным, после чего это значение будет уменьшено

операцией CP.

Чтобы предотвратить ситуацию взаимной блокировки, ядру нужно

запретить все прерывания, выполняющие "циклическую блокировку".

Иначе выполнение процесса, захватившего семафор, будет прервано

еще до того, как он сможет освободить семафор; если программа об-

работки прерываний попытается захватить этот семафор, используя

"циклическую блокировку", ядро заблокирует само себя. В качестве

примера обратимся к Рисунку 12.13. В момент возникновения преры-

Процесс A/Процессор A Процесс B/Процессор B

------------------------------------------------------------

│ P(семафор SA);

│

│

│

│ P(семафор SB);

│

│

│

│ P(семафор SA);

│ приостанавливается

│

│ P(семафор SB);

│ приостанавливается

│

v Взаимная блокировка !!

Время

Рисунок 12.11. Возникновение тупиковой ситуации из-за смены

очередности блокирования

вания значение семафора не превышает 0, поэтому результатом вы-

полнения операции CP всегда будет "ложь". Проблема решается путем

запрещения всех прерываний на то время, пока семафор захвачен

процессом.

12.3.3 Примеры алгоритмов


В данном разделе мы рассмотрим четыре алгоритма ядра, реали-

зованных с использованием семафоров. Алгоритм выделения буфера

иллюстрирует сложную схему блокирования, на примере алгоритма

wait показана синхронизация выполнения процессов, схема блокиро-

вания драйверов реализует изящный подход к решению данной пробле-

мы, и наконец, метод решения проблемы холостой работы процессора

показывает, что нужно сделать, чтобы избежать конкуренции между

процессами.

12.3.3.1 Выделение буфера

Обратимся еще раз к алгоритму getblk, рассмотренному нами в

главе 3. Алгоритм работает с тремя структурами данных: заголовком

буфера, хеш-очередью буферов и списком свободных буферов. Ядро

связывает семафор со всеми экземплярами каждой структуры. Другими

словами, если у ядра имеются в распоряжении 200 буферов, заголо-

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

вата буфера; когда процесс выполняет над семафором операцию P,

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

ются до тех пор, пока первый процесс не исполнит операцию V. У

каждой хеш-очереди буферов также имеется семафор, блокирующий

доступ к очереди. В однопроцессорной системе блокировка хеш-оче-


Процесс A/Процессор A Процесс B/Процессор B

------------------------------------------------------------

│ P(семафор SA);

│

│

│ P(семафор SB);

│

│

│

│ если (! CP(семафор SA))

│ {

│ V(семафор SB);

│ перезапустить алго-

│ ритм

│ }

│

│ P(семафор SB);

│ приостанавливается

v

Время

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

предотвращения взаимной блокировки

реди не нужна, ибо процесс никогда не переходит в состояние при-

останова, оставляя очередь в несогласованном (неупорядоченном)

виде. В многопроцессорной системе, тем не менее, возможны ситуа-

ции, когда с одной и той же хеш-очередью работают два процесса; в

каждый момент времени семафор открывает доступ к очереди только

для одного процесса. По тем же причинам и список свободных буфе-

ров нуждается в семафоре для защиты содержащейся в нем информации

от искажения.

На Рисунке 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 теперь пытается захватить хеш-очередь (*).

Поскольку очередность захвата здесь (сначала семафор буфера, по-

том семафор очереди) обратна вышеуказанной очередности, над сема-

фором выполняется операция CP. Если попытка захвата заканчивается

неудачей, имеет место обычная обработка, требующаяся по ходу за-

дачи. Но если захват удается, ядро не может быть уверено в том,

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

быть ранее изменено другим процессом, обнаружившим буфер в списке

свободных буферов и захватившим на время его семафор. Процесс A,

ожидая освобождения семафора, не имеет ни малейшего представления

о том, является ли интересующий его буфер тем буфером, который

ему нужен, и поэтому прежде всего он должен убедиться в правиль-

ности содержимого буфера; если проверка дает отрицательный ре-

зультат, алгоритм запускается сначала. Если содержимое буфера

корректно, процесс A завершает выполнение алгоритма.

---------------------------------------

(*) Вместо захвата хеш-очереди в этом месте можно было бы устано-

вить соответствующий флаг, проверяемый далее перед выполнени-

ем операции V, но чтобы проиллюстрировать схему захвата сема-

форов в обратной последовательности, в изложении мы будем

придерживаться ранее описанного варианта.

-------------------------------------------------------------┐

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

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

│ номер блока │

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

│ обработки содержимого блока │

│ { │

│ выполнять (пока буфер не будет обнаружен) │

│ { │

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

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

│ { │

│ если (операция CP(семафор буфера) завершается не- │

│ удачно) /* буфер занят */ │

│ { │

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

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

│ * та освобождения │

│ */ │

│ если (операция CP(семафор хеш-очереди) заверша-│

│ ется неудачно) │

│ { │

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

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

│ */ │

│ } │

│ в противном случае если (номер устройства или │

│ номер блока изменились) │

│ { │

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

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

│ } │

│ } │

│ выполнять (пока операция CP(семафор списка свобод-│

│ ных буферов) не завершится успешно) │

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

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

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

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

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

│ вернуть буфер; │

│ } │

│ в противном случае /* буфер отсутствует в хеш- │

│ * очереди │

│ */ │

│ /* здесь начинается выполнение оставшейся части алго-│

│ * ритма │

│ */ │

│ } │

│ } │

L-------------------------------------------------------------

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


-------------------------------------------------------------┐

│ многопроцессорная версия алгоритма wait │

│ { │

│ для (;;) /* цикл */ │

│ { │

│ перебор всех процессов-потомков: │

│ если (потомок находится в состоянии "прекращения │

│ существования") │

│ вернуть управление; │

│ P(zombie_semaphore); /* начальное значение - 0 */│

│ } │

│ } │

L-------------------------------------------------------------

Рисунок 12.15. Многопроцессорная версия алгоритма wait


Оставшуюся часть алгоритма можно рассмотреть в качестве уп-

ражнения.

12.3.3.2 Wait

Из главы 7 мы уже знаем о том, что во время выполнения сис-

темной функции wait процесс приостанавливает свою работу до мо-

мента завершения выполнения своего потомка. В многопроцессорной

системе перед процессом встает задача не упустить при выполнении

алгоритма wait потомка, прекратившего существование с помощью

функции exit; если, например, в то время, пока на одном процессо-

ре процесс-родитель запускает функцию wait, на другом процессоре

его потомок завершил свою работу, родителю нет необходимости при-

останавливать свое выполнение в ожидании завершения второго по-

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

мый zombie_semaphore и имеющий в начале нулевое значение. Этот

семафор используется при организации взаимодействия wait/exit

(Рисунок 12.15). Когда потомок завершает работу, он выполняет над

семафором своего родителя операцию V, выводя родителя из состоя-

ния приостанова, если тот перешел в него во время исполнения

функции wait. Если потомок завершился раньше, чем родитель запус-

тил функцию wait, этот факт будет обнаружен родителем, который

тут же выйдет из состояния ожидания. Если оба процесса исполняют

функции exit и wait параллельно, но потомок исполняет функцию

exit уже после того, как родитель проверил его статус, операция

V, выполненная потомком, воспрепятствует переходу родителя в сос-

тояние приостанова. В худшем случае процесс-родитель просто пов-

торяет цикл лишний раз.

12.3.3.3 Драйверы


В многопроцессорной реализации вычислительной системы на базе

компьютеров AT&T 3B20 семафоры в структуру загрузочного кода

драйверов не включаются, а операции типа P и V выполняются в точ-

ках входа в каждый драйвер (см. [Bach 84]). В главе 10 мы говори-

ли о том, что интерфейс, реализуемый драйверами устройств, харак-


теризуется очень небольшим числом точек входа (на практике их

около 20). Защита драйверов осуществляется на уровне точек входа

в них:

P(семафор драйвера);

открыть (драйвер);

V(семафор драйвера);


Если для всех точек входа в драйвер использовать один и тот

же семафор, но при этом для разных драйверов - разные семафоры,

критический участок программы драйвера будет исполняться процес-

сом монопольно. Семафоры могут назначаться как отдельному уст-

ройству, так и классам устройств. Так, например, отдельный сема-

фор может быть связан и с отдельным физическим терминалом и со

всеми терминалами сразу. В первом случае быстродействие системы

выше, ибо процессы, обращающиеся к терминалу, не захватывают се-

мафор, имеющий отношение к другим терминалам, как во втором слу-

чае. Драйверы некоторых устройств, однако, поддерживают внутрен-

нюю связь с другими драйверами; в таких случаях использование

одного семафора для класса устройств облегчает понимание задачи.

В качестве альтернативы в вычислительной системе 3B20A предостав-

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

котором программы драйвера запускаются на точно указанных процес-

сорах.

Проблемы возникают тогда, когда драйвер прерывает работу сис-

темы и его семафор захвачен: программа обработки прерываний не

может быть вызвана, так как иначе возникла бы угроза разрушения