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

    Доброго времени суток, уважаемые Хабраюзеры!

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

    Рисунок 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. Рассмотрения альтернативных моделей многопоточных программ, помимо «модели переходов», например, автоматов или сетей Петри.

    И многое-многое другое, если это по-прежнему будет интересно аудитории Хабра. Спасибо за внимание и интерес! Программируйте безопасно!
    Нордавинд
    44,00
    Компания
    Поделиться публикацией

    Комментарии 12

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

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



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

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

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

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

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

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

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

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

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

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

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

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

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое