Pull to refresh

Comments 12

Правило 1 это конечно да, всё логично… но вот будет ли им так легко пользоваться на практике? Уж очень сильно оно ограничивает, есть много классических ситуаций, когда два потока обмениваются друг с другом сигналами.
Вы правы, сейчас я привожу максимально сильные правила, которые грантируют потокобезопасность, так скажем, с запасом. Если Вы вынуждены нарушить какое-то из этих правил, то это вовсе не означает, что Вам гарантирован дедлок. Это значит лишь то, что ситуацию надо проанализировать отдельно. Есть алгоритмические способы разрешения опасных ситуаций, о которых я напишу отдельный пост.

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



В данном случае потоки имеют блокировки, не поддающиеся частичному упорядочиванию:
1: L3 → L2 →…
2: L1 → L2 →…
3: L3 → L1 →…

Ну, приведенный Вами пример нарушает правила использования мьютексов и противоречит принципам использования мьютексов совместно с сигнальными переменными.
Если быть точным, то захват L3 в первом потоке должен произойти после L2, а в третьем потоке после L1. В этом случае с частичным упорядочиванием проблем не возникает, а то, что этот L3 сразу же отпускается U3 атомарно с выполнением операции W3, позволяет безболезненно исключить этот третий мьютекс из рассмотрения (это математически доказано, но в принципе, даже умозрительно очевидно).

Поверьте, мы ситуацию исследовали со всех сторон — целую диссертацию написали:)

p.s. Естественно, сказанное верно, если мьютекс, используемый совместно с сигнальной переменной, не используется где-то еще. Правила «совсем от дураков» мы тоже не рассматривали;)
захват L3 в первом потоке должен произойти после L2, а в третьем потоке после L1

Даже если так, имеем цепочки:
1: L2 → L3 →…
2: L1 → L2 →…
3: L1 → L3 →…
что тоже ведёт к взаимоблокировкам, если выполнять потоки сверху вниз.
Ведь после W3 и E3 по логике работы условной переменной выполняется L3.

противоречит принципам использования мьютексов совместно с сигнальными переменными.

Обычно мутекс, связанный с condition variable, захватывается потоком в самом начале (т.к. охраняет ресурс, статус которого сигналит этот variable). Считается, что поток имеет полный доступ к ресурсу, отдавая его иногда другому потоку через эту переменную.

Примеры такого типичного использования есть как на MSDN, так и на c++11 reference
Давайте по порядку;)

1. Описанный Вами фрагмент системы не содержит ситуаций взаимных блокировок, т.к. то, что Вы ошибочно назвали блокировкой, пройдет, когда планировщик вернется к первому потоку и сделает U3 (дав жизнь потоку 3) и U2 (дав жизнь потоку 2) — именно в таком порядке!

2. Видимо, Вы не очень точно трактуете смысл слова «в самом начале»:) Мьютекс, который является спутником сигнальной переменной, должен быть захвачен перед обращением к разделяемому ресурсу, чтобы гарантировать атомарность доступа. Поэтому вполне правомерен захват L3 сразу перед W3 (ребро между ними и есть то самое обращение к разделяемому ресурсу).
Хотя кажется я пишу чушь.
Conditional variable и мутекс при ней не при чём.
Достаточно заменить W1 на ожидание семафора, а E1 — на сигнал семафора, и снова будет deadlock, без всяких лишних мутексов.
Именно эта ситуация и описана в примере дедлока.
Всё же что-то в той моей диаграмме есть.

Если выполнить вышеописанное преобразование (поток захватывает псевдо-лок в начале и отпускает его только на signal или wait), то можно свести задачу к анализу только мутексов.

Неизвестно правда, накладывает ли оно более жёсткие ограничения, чем сформулированные правила 1 и 2 — надо поискать контрпримеры. Если это преобразование эквивалентно (а может даже и лучше описывает ситуацию), то оно полезно.
Вы хотите пройти наш путь, я так полагаю:) На старте исследований у нас тоже была мысль свести все к одному примитиву синхронизации — мы не нашли эквивалентного представления, поэтому строили доказательную базу отдельно для мьютексов и отдельно для сигнальных переменных.
Как уже указали выше, ваши достаточные условия слишком сильные. Было бы здорово минимизировать их до критерия. Пусть даже с горой матана, мне кажется с такими клевыми картинками все понятно будет :)
Вообще, еще интересно было бы все-таки некоторое обоснование несводимости сигнальной переменной к мьютексу или наоборот. Прямо так и чешутся же руки попробовать свести, хотя я даже и понимаю, что вы много времени потратили, вероятно, на это, и все равно не смогли, так что, вероятно, это нельзя сделать.
Ок, я постараюсь в следующих постах дать менее «злые» правила, но сразу предупреждаю, что им будет предшествовать гора определений и вспомогательных утверждений:) Это несколько снижает их практическую применимость в реальных условиях, но раз уж у нас формируется узкий «кружок любителей безопасного многопоточного программирования», то побалуемся теоретическими выкладками:)
Sign up to leave a comment.