Пример 7.1. Наивная реализация взаимного исключения на основе флаговой переменной

program флаг;
var flag: Boolean;
procedure процессодин;
begin
while True do begin
while flag do;
flag:= True;
критическаясекция!;
flag:= False;
...
end
end;
procedure процессдва; begin
while True do begin
while flag do;
flag:= True;
критическаясекция2;
flag:= False;
end
end;
oegin
flag:= False;
parbegin
процессодин;
процессдва;
parend
еnd.

Примитивы взаимоисключения

В классической работе Г. М. Дейтела [Дейтел 1987] предлагается несколько последовательных усовершенствований механизма взаимоисключений, основанного на флаговых переменных, и как завершающий этап этого анализа приводится алгоритм взаимоисключений Деккера (пример 7.2).

Пример 7.2. Алгоритм Деккера (цит. по [Дейтел 1987])

program АлгоритмДеккера;
var
избранныйпроцесс: (первый, второй); п!хочетвойти, п2хочетвойти: Boolean; procedure процессодин;
begin
while true do begin
п1хочетвойти:= True;
while п2хочетвойти do
if избранныйпроцесс=второй then
begin
п1хочетвойти:= False;
while избранныйпроцесс=второй do;
п!хочетвойти:= True;
end
критическийучасток1;
избранныйпроцесс:= второй;
п!хочетвойти:= False;
...
end
end
procedure процессдва;
begin
while true do
begin
п2хочетвойти:= True;
while п1хочетвойти do
if избранныйпроцесс=первый then
begin
п2хочетвойти:= False;
while избранныйпроцесс=первый do;
п2хочетвойти:= True;
end
критическийучасток2;
избранныйпроцесс:= первый;
п2хочетвойти:= False;
...
end
end D
begin
п1хочетвойти:= False;
п2хочетвойти:= False;
избранныйпроцесс:= первый;
parbegin процессодин;
процессдва;
parend
end.

Недостатки этого решения очевидны. Первый из них — для доступа к одной и той же критической секции из третьей нити мы должны значительно сложнить код обеих нитей.
Нa практике, для решения проблемы работы с флаговыми и другими ска-ярными переменными в многопроцессорных конфигурациях большинство овременных процессоров предоставляют аппаратные примитивы взаимоисключения: средства, позволяющие процессору монопольно захватить шину: выполнить несколько операций над памятью. Реализации этих примитивов различны у разных процессоров. Например, у х86 это специальный код операции, префикс захвата шины, который сам по себе не совершает никаких действий, но зато исполняет следующую за ним операцию в монопольном режиме.
Благодаря этому мы можем одновременно получить старое значение флаговой переменной и установить новое командой xchg (eXCHanGe, обменять — операнды обмениваются значениями между собой — пример 7.3)- Если память модифицируется только одним процессором, исполняющим программу, префикс блокировки шины не нужен — зато, если процессоров (или других задатчиков шины) в системе несколько, префикс гарантирует взаимоисключение и для модификаций флага с их стороны.

Пример 7.3. Реализация примитива testandset через блокировку шины

.globl flag
; 0 = False, I = True
flag:.db 0
proc process1
tryagain:
move eax, 1
lock xchg eax, flag
tst eax
bnz tryagain
критическая секция
; в данном случае о взаимоисключении можно не заботиться
xor eax, eax
move flag, eax
ret
endp

Другие процессоры, например VAX, предоставляют отдельные команды, исполняющиеся в режиме монопольного захвата шины. В частности, Именно так этот процессор исполняет команды вставки в очередь и исключения из нее.
Имея возможность произвести атомарно исполняющуюся операцию над скалярной переменной, мы можем реализовать более сложные схемы взаимоисключения, используя эту переменную в качестве флаговой, при помощи относительно простого кода (пример 7.4). В отличие от алгоритма Деккера этот код легко распространяется на случай более чем двух нитей.

Пример 7.4. Реализация взаимоисключения при помощи атомарной операции testandset (ЦИТ. ПО [Дейтел 1987])

progam npimeptestandset
var активный: Boolean;
procedure процессодин;
var первомувходитьнельзя: Boolean;
begin
while true do
begin
первомувходитьнельзя:= True;
while первомувходитьнельзя do
testandset(первомувходитьнельзя, активный);
критический участокодин;
активный:= False;
....
end
end;
procedure процессдва;
var второмувходитьнельзя: Boolean; begin
while true do
begin
второмувходитьнельзя:= True;
while второмувходитьнельзя do
testandset(второмувходитьнельзя, активный);
критический участокдва;
активный:= False;
.....
end
end;

В том случае, если одной из нитей является обработчик прерывания, можно воспользоваться сервисом, который предоставляют все современные процессоры: запретить прерывания на время нахождения основной нити программы в критической секции. Впрочем, указанным способом необходимо пользоваться с осторожностью — это приводит к увеличению времени обработки прерывания, что не всегда допустимо, особенно в задачах реального времени.

Мертвые и живые блокировки

Потом ударили морозы. Замерзло все, лиса ушла в кредит. Медведь же вмерз в дупло И до сих пор глядит. Б. Гребенщиков.

Решив проблему взаимоисключения для одиночных разделяемых ресурсов, мы еще не можем расслабляться. Дело в том, что если мы используем любые механизмы взаимоисключения для доступа к нескольким различным ресурсам, может возникнуть специфическая проблема, называемая мертвой блокировкой (dead lock).
Рассмотрим две нити, каждая из которых работает с двумя различными ресурсами одновременно. Например, одна нить копирует данные со стриммера на кассету Exabyte, а другая — в обратном направлении. Доступ к стриммеру контролируется флаговой переменной flag1, а к кассете — flag2 (вместо флаговых переменных могут использоваться и более сложные средства взаимоисключения).
Первая нить сначала устанавливает flag1, затем fiag2, вторая поступает наоборот. Поэтому, если вторая нить получит управление и защелкнет flag2 в промежутке между соответствующими операциями первой нити, то мы получим мертвую блокировку (рис. 7.1) — первая нить никогда не освободит flag1, потому что стоит в очереди у переменной flag2, занятой второй нитью, которая стоит в очереди у flagi, занятой первой.

Рис. 7.1. Мертвая блокировка

Все остальные нити, пытающиеся получить доступ к стриммеру или кассете, также будут становиться в соответствующие очереди и ждать, пока администратор не снимет одну из "защелкнувшихся" задач.
Цикл взаимного ожидания может состоять и из большего количества нитей Возможна также мертвая блокировка с участием только одной нити и одного ресурса: для этого достаточно попытаться захватить одну и ту же флаговую переменную два раза. Критерием блокировки является образование замкнутого цикла в графе ожидающих друг друга задач.
Эта проблема может быть решена несколькими способами. Часто применяемое решение, обладающее, впрочем, серьезными недостатками — это отправка сообщения программе о том, что попытка установить примитив взаимоисключения приведет к мертвой блокировке. Это решение опасно во-первых, тем, что сильно усложняет кодирование: теперь мы вынуждены принимать во внимание не только возможность захвата примитива другой нитью, но и более сложные ситуации. Во-вторых, получив ошибку установки флага, программист испытывает сильный соблазн сделать именно то, чего делать в данном случае нельзя: повторить попытку захвата ресурса.
Рассмотрим ситуацию, когда две нити пытаются захватить необходимые им ресурсы, получают сообщение о возможности мертвой блокировки, и тут же повторяют попытку захвата того же ресурса. Поскольку освобождения ресурсов не происходит, взаимозависимость между этими нитями не устраняется, и повторный захват также приводит к сообщению о возможности мертвой блокировки. Если нити будут циклически повторять попытки захвата, мы получим состояние, которое называется живой блокировкой (livelock) (рис. 7.2). Это состояние реже рассматривается в учебниках, но теоретически оно ничуть не лучше мертвой блокировки. Практически же оно гораздо хуже — если нити, зацепившиеся намертво, тихо висят и причиняют вред только тем нитям, которым могли бы понадобиться занятые ими ресурсы, то нити, зацепившиеся заживо, непродуктивно расходуют время центрального процессора.

Рис. 7.2. Живая блокировка

Как живая, так и мертвая блокировки возможны и в ситуации, когда ресурс только один, но примитив взаимоисключения не атомарен, т. е. операция захвата выполняется в несколько этапов.

Живая блокировка при арбитраже шины
Рассмотрим процесс арбитража шины: два устройства соревнуются за доступ к среде передачи. Устройство начинает передачу и при этом сравнивает передаваемый сигнал с принимаемым из шины. Возникновение расхождений между этими сигналами интерпретируется как коллизия (collision) — предполагается, что расхождения обусловлены работой другого передатчика. Обнаружив коллизию, устройство прекращает передачу. Сигнал распространяется по шине с конечной скоростью, поэтому прекратить передачу будут вынуждены оба устройства (в разд. Устройства графического выхода мы увидим пример того, как в низкоскоростных локальных шинах это ограничение можно обойти). Таким образом, оба устройства не могут начать передачу сразу же после того, как в шине "установится тишина": это приведет к живой блокировке. Схема разрешения коллизий CSMA/CD (Carrier Sence Multiple Access/Collision Detection, множественный доступ с прослушиванием несущей и обнаружением коллизий), используемая в протоколах локальных сетей семейства Ethernet, требует от устройства, обнаружившего коллизию, ожидания в течение случайного интервала времени.

Единственно правильная реакция на получение сообщения о мертвой блокировке — это освободить все занятые нитью ресурсы и подождать в течение случайного промежутка времени. Таким образом, поиск возможных блокировок сильно усложняет и логику работы самих примитивов взаимоисключения (нужно поддерживать граф, описывающий, кто кого ждет), и код, использующий эти примитивы.
Простейшее альтернативное решение — разрешить каждой нити в каждый момент времени держать захваченным только один объект — прост и решает проблему в корне, но часто оказывается неприемлемым. Больше подходит соглашение о том, что захваты ресурсов должны всегда происходить в определенном порядке. Этот порядок может быть любым, важно только, чтобы он всегда соблюдался.
Еще один вариант решения состоит в предоставлении возможности объединять примитивы и/или операции над ними в группы. При этом программа может выполнить операцию захвата флагов fiag1 и fiag2 единой командой, во время исполнения которой никакая другая программа не может получить доступ к этим переменным. Групповая операция выполняется как транзакция, т. е. либо происходит вся целиком, либо не происходит вообще. Если хотя бы одна из операций группы приводит к ожиданию, групповой примитив снимает все флаги, которые успел поставить до этого.
Ожидание с освобождением ресурсов, впрочем, порождает ряд более специфических проблем. Рассмотрим одну из них: нити А нужны ресурсы X и Y, которые она разделяет, соответственно, с нитями В и С. Если нить А захватывает ресурсы в соответствии с предложенным протоколом (освобождая их при неудачной попытке захвата), возможен такой сценарий исполнения нитей В и С, при котором нить А не получит доступа к ресурсам никогда. Напротив, захват ресурсов по мере их освобождения другими нитями может (если В и С сцеплены по каким-то другим ресурсам) привести к мертвой блокировке. Общего решения задачи разрешения блокировок и родственных им ситуаций при взаимоисключении доступа ко многим ресурсам на сегодня не предложено.
Описанное выше явление иногда называют "проблемой голодного философа". История этого колоритного названия восходит к модели, которую использовал для демонстрации описанного этого феномена.
Некоторое количество (у Э. Дейкстры — пять) философов сидят вокруг стола, на котором стоит блюдо спагетти (вместо спагетти можно взять, например, блины). Спагетти едят двумя вилками. В нашем случае, количество вилок равно количеству философов, так что соседи за столом разделяют вилку (гигиенический аспект проблемы мы опускаем).
Каждый философ некоторый (переменный) промежуток времени размышляет, затем пытается взять лежащие рядом с ним вилки (рис. 7.3). Если ему это удается, он принимается за еду. Ест он также переменный промежуток времени, после этого откладывает вилки и вновь погружается в размышления. Проблемы возникают, когда философ не может взять одну из вилок.

Рис. 7.3. Обедающие философы

Возможны несколько вариантов разрешения происходящих при этом коллизий. Если, например, каждый из философов всегда берет ту вилку, которая свободна, и не отпускает ее, пока не насытится, мы можем получить (хотя и не обязательно получим) классическую мертвую блокировку, в которую будут включены все философы, сидящие вокруг стола (рис. 7.4). Вариант, при котором философ сначала всегда дожидается правой вилки, и лишь взяв ее, начинает дожидаться левой, только повысит вероятность образования цикла.

Рис. 7.4. Мертвая блокировка в исполнении пяти философов

Цикл можно разомкнуть, пронумеровав вилки и потребовав, чтобы каждый философ брат сначала вилку с меньшим номером, и только потом — с большим. Если вилки пронумерованы по часовой стрелке, для всех философов, кроме одного, это требование совпадает с высказанным в предыдущем абзаце — сначала брать правую вилку, и лишь потом дожидаться левой. Однако для того, кто попал между пятой и первой вилками, это правило обращается — он должен сначала дождаться левой вилки, и только потом правую. Легко продемонстрировать, что этот философ в среднем будет своих вилок дольше, чем остальные четверо.
Если же философ берет вилки тогда и только тогда, когда они доступны обе одновременно, это может привести к проблеме голодного философа-согласовав свои действия, соседи бедняги могут неограниченно долгое время оставлять его голодным (рис. 7.5).

Рис. 7.5. Голодный философ

Примитивы синхронизации

Я слышу крик в темноте Наверное, это сигнал. В. Бутусов

Посмотрев на примеры 7.2 и 7.4, внимательный читатель должен отметить, что используемая конструкция подозрительно похожа на работу с внешними устройствами в режиме опроса. Действительно, опрос флаговой переменном в цикле хотя и обеспечивает гарантию взаимоисключения, но обладает всеми недостатками, которые мы указывали для опроса внешнего устройства.
g случае исполнения параллельных нитей на одном процессоре, данный метод имеет еще один недостаток: пока одна из нитей занимается опросом, никакая другая нить не может исполняться, потому что процессор загружен непродуктивной работой.
Легко видеть, что в данном случае использование прерываний или какого-то их аналога проблемы не решит: в лучшем случае, "прерывание" будет вызываться не в той нити, в которой нужно, сводя задачу взаимоисключения к предыдущей, только с уже новой флаговой переменной, а в худшем — приведет к возникновению еще одной нити. Задача взаимодействия между асинхронными нитями, таким образом, сводится к требованию того, чтобы нити в какие-то моменты переставали быть асинхронными, синхронизовались.
Если у нас уже есть примитив взаимного исключения, мы можем решить задачу синхронизации, предоставив еще один примитив, который позволяет активному процессу остановиться, ожидая, пока флаговая переменная не примет "правильное" значение, и продолжить исполнение после этого. При обработке прерываний роль такого примитива может исполнять команда остановки процессора: у всех современных процессоров прерывание останавливает "исполнение" этой команды, а возврат из обработчика передает управление на следующую команду, таким образом выводя процессор из спящего состояния. В многопроцессорной конфигурации можно ввести средство, при помощи которого один процессор может вызывать прерывание другого — и тогда каждый из процессоров системы сможет ожидать другого, переходя в режим сна. При реализации же многопоточностп на одном процессоре (см. разд. Вытесняющая многозадачность) примитив засыпания (блокировки) нити должен предоставляться модулем, ответственным за переключение потоков.
Впрочем, если операции над флагом, засыпание потока и его пробуждение реализованы разными примитивами, мы рискуем получить новую проблему (пример 7.5). Она состоит в том, что если пробуждающий сигнал поступит в промежутке между операторами testandset и pause, мы его не получим. В результате операция pause приведет к засыпанию нашей нити навсегда.

Пример 7.5. Ошибка потерянного пробуждения (lost wake-up bug)

program пауза
var flag: Boolean;
procedure процесс1
var myflag: Boolean
while True do
begin
myflag:= True;
testandset(myflag, flag);
if myflag then
(* Обратите внимание, что проверка флага *
* и засыпание — это разные операторы! *)
pause;
критическаясекция();
flag:= False;
end
end;

Одно из решений состоит в усложнении примитива pause: он должен засыпать, если и только если сигнал еще не приходил. Усложнение получается значительное: мало того, что перед засыпанием надо проверять нетривиальное условие, необходимо еще предусмотреть какой-то способ сброса этого условия, если мы предполагаем многократное использование нашего примитива.
Если писать на ассемблере или родственных ему языках, можно пойти и более изощренным путем (пример 7.6). Подмена адреса возврата в обработчике прерывания гарантирует нам, что если прерывание по установке флага произойдет в промежутке между метками label и ok, мы перейдем на метку label и, вместо того, чтобы заснуть навеки, благополучно проверим флаг и войдем в критическую секцию.