Рецепты против взаимных блокировок на сигнальных переменных

в 9:22, , рубрики: deadlocks, Блог компании Нордавинд, многопоточное программирование, Программирование, Проектирование и рефакторинг, метки: , ,

Доброго времени суток, уважаемые читатели!

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

В рамках этого поста мы рассмотрим проблемы, которые возникают при использовании сигнальных переменных, и покажем, как их можно избежать.

С вашего позволения я пропущу долгие вступления, рассчитывая, что вы уже знакомы с предыдущим постом и мы одинаково понимаем:

  1. Что такое взаимная блокировка.
  2. Как строится и как читается «модель переходов» многопоточной программы.
  3. Как избежать взаимных блокировок при использовании мьютексов.

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

Расширение модели переходов многопоточной программы

При описании многопоточной программы, оперирующей только операциями захвата и отпускания мьютексов, нам хватало всего лишь обозначений – L (lock) и U (unlock). Настало время расширить нашу модель переходов новыми операциями:

  • W (wait, ожидание) – переводит субъект (поток), вызвавший эту операцию, в состояние ожидания сигнала от соответствующей сигнальной переменной. Для одной и той же сигнальной переменной может существовать неограниченное количество ожидающих потоков.
  • E (emit, отправка) – отправляет единичный сигнал по сигнальной переменной. Сигнал может получить только один из ожидающих его потоков, независимо от общего числа ожидающих, при этом неважно, какой именно поток выполнил операцию emit.
  • B (broadcast, широковещание) – отправляет сигнал для всех потоков, ожидающих сигнала по соответствующей сигнальной переменной, при этом неважно, какой именно поток выполнил операцию broadcast.

Потоки, получившие сигнал, пробуждаются и продолжают свое выполнение далее по цепочке. Если в момент отправки сигнала нет ни одного ожидающего потока-потребителя, то сигнал просто игнорируется, при этом факт отправки сигнала не запоминается. Поэтому, если какой-либо поток выполнит операцию W, то он будет переведен в состояние ожидания до новой отправки сигнала.

Можно провести аналогию с рассмотренными ранее операциями L и U. Операция W имеет общие черты с операцией захвата мьютекса L, за тем отличием, что L блокирует выполнение потока только в случае попытки повторного захвата уже захваченного мьютекса, а W блокирует выполнение потока всегда. Операции E и B имеют общие черты с операцией освобождения мьютекса U. Таким образом, сигнальная переменная может быть представлена как обычный мьютекс за тем исключением, что операция захвата осуществляется одним потоком, а освобождение другим.

Отметим, что на практике сигнальная переменная часто используется совместно с мьютексом (например, в библиотеке libpthread). При построении модели будем считать, что мьютекс, который неразрывно связан с использованием сигнальной переменной, учитывается в логике выполнения операций W, E и B.

Где же опасность?

Сигнальная переменная может быть причиной возникновения взаимной блокировки в одном из двух случаев.

Сигнальная переменная является причиной возникновения взаимной блокировки 1-го рода, если K-й поток ожидает поступления сигнала на I-й сигнальной переменной, при этом K-м потоком захвачен некоторый мьютекс, который (непосредственно или косвенно) блокирует отправку сигнала для I-й переменной кондиции со стороны других субъектов (рисунок 1).

Сигнальная переменная является причиной возникновения взаимной блокировки 2-го рода, если K-й поток ожидает поступления сигнала на I-й сигнальной переменной, а потоки, которые могут отправить этот сигнал, ожидают поступления сигнала на J-й сигнальной переменной, который должен отправить K-й поток (рисунок 2).

Рецепты против взаимных блокировок на сигнальных переменных
Рисунок 2 – Взаимная блокировка 2-го рода с участием сигнальной переменной.

Два правила безопасного использования сигнальных переменных

По уже сложившейся традиции сформулируем два правила, которые позволят избежать описанных выше ситуаций.

Правило 1

Сигнальная переменная не может являться причиной возникновения взаимной блокировки 2-го рода, если каждый поток, являющийся потоком-источником для какой-либо сигнальной переменной, не является потоком-потребителем ни для какой сигнальной переменной.

Назовем потоком-потребителем для некоторой сигнальной переменной поток, в цепочке выполнения которого содержится хотя бы одна операция W ожидания сигнала для этой сигнальной переменной.

Назовем потоком-источником для некоторой переменной кондиции поток, в цепочке выполнения которого содержится хотя бы одна операция E или B отправки сигнала по этой сигнальной переменной.

Правило 2

Скажу честно, я испытывал некоторые затруднения, формулируя второе правило, т.к. в наших исследованиях в нем фигурировали понятия и определения, которые я для упрощения изложения не вводил в рамках этого поста. Вот что получилось:

Сигнальная переменная не может являться причиной возникновения взаимной блокировки 1-го рода многопоточной программы, соответствующей правилам безопасного использования мьютексов, если при любой динамике любого варианта выполнения каждого потока, где ожидается сигнал от некоторой сигнальной переменной, все мьтексы, захваченные этим потоком к моменту обращения к этой сигнальной переменной, не связаны отношением порядка «больше» ни с одним мьютексом хотя бы одного потока, выполняющего отправку сигнала для этой сигнальной переменной.

Это, по сути, означает, что до того момента, как наш поток «заснул» на вызове W, он не захватил ни одного мьютекса, который может потребоваться для отправки E или B, чтобы нас «разбудить».

Расширение области применения

В заключение позвольте обратить внимание на то, что не стоит сигнальную переменную воспринимать исключительно, как некий языковой примитив, например, pthread_cond (библиотека libpthread). Сигнальная переменная – это функциональная конструкция, которая позволяет организовать ожидание в одном потоке выполнения какого-то условия со стороны другого потока.

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

Скоро «на экране»

Спасибо уважаемым читательам на проявленный интерес к нашей серии постов о многопоточном программировании. Для меня это является очередным подтверждением актуальности проблемы и важности проводимых нами исследований. Это дает силы для написания все новых и новых статей. В наших планах:

  1. Рассмотрение вопросов «динамических блокировок» с использованием «мягких средств синхронизации» (неблокирующая попытка захвата мьютекса, ожидание сигнала на сигнальной переменной с таймаутом и др.).
  2. Рассмотрение математических основ и доказательств тезисов, представленных в предыдущих статьях.
  3. Рассмотрения альтернативных моделей многопоточных программ, помимо «модели переходов», например, автоматов или сетей Петри.

И многое-многое другое, если это по-прежнему будет интересно аудитории Хабра. Спасибо за внимание и интерес! Программируйте безопасно!

Автор: isvirin

Источник

Поделиться

* - обязательные к заполнению поля