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