Мертвые и живые блокировки
Рассмотрим ситуацию, когда две нити пытаются захватить необходимые им ресурсы, получают сообщение о возможности мертвой блокировки, и тут же повторяют попытку захвата того же ресурса. Поскольку освобождения ресурсов не происходит, взаимозависимость между этими нитями не устраняется, и повторный захват также приводит к сообщению о возможности мертвой блокировки. Если нити будут циклически повторять попытки захвата, мы получим состояние, которое называется живой блокировкой (livelock) (рис. 7.2). Это состояние реже рассматривается в учебниках, но теоретически оно ничуть не лучше мертвой блокировки. Практически же оно гораздо хуже – если нити, зацепившиеся намертво, тихо висят и причиняют вред только тем нитям, которым могли бы понадобиться занятые ими ресурсы, то нити, зацепившиеся заживо, непродуктивно расходуют время центрального процессора.
Рис. 7.2. Живая блокировка
Как живая, так и мертвая блокировки возможны и в ситуации, когда ресурс только один, но примитив взаимоисключения не атомарен, т. е. операция захвата выполняется в несколько этапов.
Живая блокировка при арбитраже шины
Рассмотрим процесс арбитража шины: два устройства соревнуются за доступ к среде передачи. Устройство начинает передачу и при этом сравнивает передаваемый сигнал с принимаемым из шины. Возникновение расхождений между этими сигналами интерпретируется как коллизия (collision) – предполагается, что расхождения обусловлены работой другого передатчика. Обнаружив коллизию, устройство прекращает передачу. Сигнал распространяется по шине с конечной скоростью, поэтому прекратить передачу будут вынуждены оба устройства (в разд. "Устройства графического выхода" мы увидим пример того, как в низкоскоростных локальных шинах это ограничение можно обойти).
Таким образом, оба устройства не могут начать передачу сразу же после того, как в шине "установится тишина": это приведет к живой блокировке. Схема разрешения коллизий CSMA/CD (Carrier Sence Multiple Access/Collision Detection, множественный доступ с прослушиванием несущей и обнаружением коллизий), используемая в протоколах локальных сетей семейства Ethernet, требует от устройства, обнаружившего коллизию, ожидания в течение случайного интервала времени.
Единственно правильная реакция на получение сообщения о мертвой блокировке – это освободить все занятые нитью ресурсы и подождать в течение случайного промежутка времени. Таким образом, поиск возможных блокировок сильно усложняет и логику работы самих примитивов взаимоисключения (нужно поддерживать граф, описывающий, кто кого ждет), и код, использующий эти примитивы.
Простейшее альтернативное решение – разрешить каждой нити в каждый момент времени держать захваченным только один объект – прост и решает проблему в корне, но часто оказывается неприемлемым. Больше подходит соглашение о том, что захваты ресурсов должны всегда происходить в определенном порядке. Этот порядок может быть любым, важно только, чтобы он всегда соблюдался.
Еще один вариант решения состоит в предоставлении возможности объединять примитивы и/или операции над ними в группы. При этом программа может выполнить операцию захвата флагов fiag1 и fiag2 единой командой, во время исполнения которой никакая другая программа не может получить доступ к этим переменным. Групповая операция выполняется как транзакция, т. е. либо происходит вся целиком, либо не происходит вообще. Если хотя бы одна из операций группы приводит к ожиданию, групповой примитив снимает все флаги, которые успел поставить до этого.
Ожидание с освобождением ресурсов, впрочем, порождает ряд более специфических проблем. Рассмотрим одну из них: нити А нужны ресурсы X и Y, которые она разделяет, соответственно, с нитями В и С. Если нить А захватывает ресурсы в соответствии с предложенным протоколом (освобождая их при неудачной попытке захвата), возможен такой сценарий исполнения нитей В и С, при котором нить А не получит доступа к ресурсам никогда. Напротив, захват ресурсов по мере их освобождения другими нитями может (если В и С сцеплены по каким-то другим ресурсам) привести к мертвой блокировке. Общего решения задачи разрешения блокировок и родственных им ситуаций при взаимоисключении доступа ко многим ресурсам на сегодня не предложено.