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

Решив проблему взаимоисключения для одиночных разделяемых ресурсов, мы еще не можем расслабляться. Дело в том, что если мы используем любые механизмы взаимоисключения для доступа к нескольким различным ресурсам, может возникнуть специфическая проблема, называемая мертвой блокировкой (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. Голодный философ