Два простых правила для предотвращения взаимных блокировок на мьютексах

    Здравствуйте, уважаемые Хабраюзеры!

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

    При написании своих предыдущих постов мы совершили непростительную ошибку, начав рассматривать взаимные блокировки со сложных, но, как нам казалось, наиболее интересных случаев. Этого уважаемая аудитория Хабра, к сожалению, не оценила. Спешим исправиться, и, пусть не с первого раза, но все-таки подойти к рассмотрению проблемы блокировок с самого начала. Однако мы все же рассчитываем, что вы знаете, зачем нужны и какие бывают средства синхронизации при написании многопоточных программ.

    Рецепты, описанные в этом посте весьма просты, но далеко не все даже профессиональные программисты используют осознанно, руководствуясь скорее ощущениями «почему-то кажется, что не стоит захватывать тот мьютекс из под захваченного этого». Так жили и мы долгие-долгие годы, когда в один ужасно ответственный момент не обнаружили, что на «железке», которую нужно срочно отправить заказчику, наш любимый софт не может и часа прожить без дедлока. Убив на решение этой задачи несколько дней работы своих ведущих программистов, мы приняли решение, которое изменило нашу жизнь – мы занялись суровой формализацией ситуаций взаимных блокировок, включающей строгие математические доказательства того, почему так можно делать, а так нельзя. Надо сказать, что исследование наше выродилось в кандидатскую диссертацию одного из сотрудников, но я не уверен, что использованный там формат изложения будет интересен здесь…

    Итак, о блокировках с самого начала…

    Природа взаимных блокировок


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

    Традиционно принято считать, что причиной блокировок всегда являются мьютексы (mutex), однако это не совсем точно. Причиной блокировок могут являться любые средства и механизмы синхронизации, которые предполагают ожидание чего-либо одного потока со стороны другого, например, ожидание сигнала на переменной кондиции (condition variable) или, что значительно менее очевидно, ожидание завершение другого потока (wait/join thread). В теории, на самом деле, второй случай является тем же самым «ожиданием сигнала», однако ввиду неявности этой операции синхронизации, при поиске дедлоков о ней просто забывают, как о потенциальном источнике угрозы и часто не замечают в коде.

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

    Несколько слов о модели многопоточных программ


    Мы назвали эту модель – «моделью переходов» и представляет она собой совокупность ориентированных графов, где каждый граф представляет собой поток (субъект). Каждый граф имеет одну начальную вершину, соответствующую состоянию, когда ни одно средство синхронизации еще не задействовано, и имеет одну конечную вершину, соответствующую состоянию, когда ни одно средство синхронизации уже не задействовано. Предполагается, что при достижении конечной вершины поток автоматически начинается сначала. Все другие вершины графов представляют собой операцию в отношении того или иного средства синхронизации, например, L (lock) – захват мьютекса, U (unlock) – отпускание мьютекса и т.д. Для доказательств утверждений важно, что модель игнорирует время между выполнениями отдельных операций в отношении средств синхронизации, расширяя тем самым возможный диапазон динамик до бесконечности. Если аудитории Хабра интересна математическая и физическая суть модели, то я готов написать отдельный пост на эту тему, а здесь… всего лишь начало долгой, но интересной истории о многопоточном программировании.

    Пример модели, состоящей из одного потока (субъекта):

    Рисунок 1.

    В соответствии с данным рисунком, субъект может пройти по двум веткам: 0, L1, U1, 0 или 0, L1, L2, U2, U1, 0. Эта схема может рассматриваться, как конечный автомат, грамматика которого включает две фразы {0, L1, U1, 0} и {0, L1, L2, U2, U1, 0}. Будем считать, что время перехода между действиями в отношении средств синхронизации конечно, т.е. алгоритмически корректно. Не будем считать ошибкой синхронизации захват и удержание мьютекса в течение ожидания какого-либо действия пользователя, которое потенциально может никогда не наступить.
    Для исследования программы на потенциальную возможность возникновения ситуации взаимной блокировки необходимо составить цепочки выполнения всех возможных субъектов в программе.

    Простейшая взаимная блокировка с участием мьютексов


    Пусть в нашей программе помимо потока (субъекта), приведенного на рисунке 1, есть еще один:

    Рисунок 2.

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

    Рисунок 3.

    Ничего не мешает нашим двух независимым потокам выполниться так: поток 1 успел захватить мьютекс 1, затем планировщик переключил выполнение на поток 2, который захватил мьютекс 2, и после этого оба наших потока пытаются захватить мьютексы, которые уже захвачены – deadlock!

    Назовем систему потоков (субъектов) несовместимой, если существуют хотя бы один вариант наложения цепочек их выполнения, при котором наступает ситуация взаимной блокировки. Соответственно, совместимой является такая система субъектов, для которой не существует динамики, при которой возможно возникновение ситуации взаимной блокировки.
    Рассмотренные два субъекта являются несовместимыми, т.к. существует вариант наложения, приведенный на рисунке 3, при котором возникает ситуация взаимной блокировки. Отметим, что такие субъекты не обязательно будут приводить к блокировке (зависанию) программы. Динамика конкретной работы (время переходов между обращениями к средствам синхронизации) может быть такова, что найденный вариант наложения никогда не проявится в реальности. В любом случае, программный код, описываемый такой моделью, является потенциально опасным и блокировки могут проявиться при портировании на другую программную или аппаратную платформу, а также просто при изменении условий функционирования.

    Рисунок 4

    Важно помнить, что потоки могут быть попарно совместимы между собой, но не совместимы в большей комбинации. На рисунке 5 показана модель программы, где все субъекты попарно совместимы между собой, но все вместе приводят к ситуации взаимной блокировки.

    Рисунок 5

    На рисунке 6 показан другой вариант совмещения цепочек выполнения для модели, представленной на рисунке 5, при котором возникает взаимная блокировка.

    Рисунок 6

    Прямо так и хочется сказать: Как страшно жить!

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

    Первое правило

    Всегда отпускайте захваченные мьютексы в обратном захвату порядке, т.е. руководствуйтесь логикой «первый захвачен – последний отпущен».

    Второе правило

    Всегда соблюдайте один и тот же порядок захвата мьютексов.
    Если вы в одном потоке захватываете мьютекс 1, а затем мьютекс 2, то недопустимо захватывать их в ином порядке в другом потоке.
    На самом деле, правило не так просто, как кажется на первый взгляд. Еще раз посмотрим внимательно на Рисунок 6. Там это правило нарушено, но это несколько неочевидно. Глядя на первый поток, мы фиксируем, что мьютекс 2 мы захватываем после мьютекса 1. Глядя на второй поток, мы фиксируем, что мьютекс 3 мы захватываем после мьютекса 2. Объединение этих наблюдений означает, что мьютекс 3 мы захватываем после мьютекса 1, что не выполняется в потоке 3. Результатом этого невыполнения является deadlock, который и показан на рисунке.

    Несмотря на всю простоту данных правил, смею утверждать, что если ваша программа в качестве средств синхронизации использует только мьютексы и вы соблюли эти правила, то взаимные блокировки вам не страшны! Мы, конечно, не берем в расчет ситуацию попытки двойного захвата нерекурсивного мьютекса одним потоком, но это скорее глупость, чем deadlock.

    В заключение хотелось бы задать вопрос: интересна ли эта тема аудитории Хабра? Если да, то есть желание и возможность рассказать о чуть более интересных ситуациях, возникающих при использовании сигнальных переменных и, может быть, немного глубже окунуться в доказательную базу – это уже для искушенных программистов многопоточных приложений.

    Надеюсь, этот пост был полезен.

    Читайте продолжение — Рецепты против взаимных блокировок на сигнальных переменных.
    Нордавинд
    43.30
    Company
    Share post

    Comments 50

      +3
      Подскажите пожалуйста каким образом вы находите все возможные мьютексы и порядок их захвата?
      И каким именно образом строится этот граф? Все делается вручную?
        +2
        Применительно к данной статье к графу надо относиться скорее как к некоторой нотации, на которой я наглядно поясняю ситуации блокировок. Если соблюдать правила использования средств синхронизации в процессе программирования (этих правил, несколько больше, чем рассмотрено в статье, т.к. есть еще одно, принципиально иное средство синхронизации — сигнальная переменная), то граф строить не придется.

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

        Для более сложных программ мы сделали библиотеку, которая подменяет вызовы libpthread по созданию и удалению потоков, а также по обращению к средствам синхронизации, сбрасывая в run-time информацию о структуре графа в файл виде xml-ки. Очевидный недостаток: в ходе run-time выполнения мы не можем гарантировать, что программа прошла по всем веткам, а следовательно, не можем гарантировать, что модель полна. Этот недостаток компенсируется тем, что в ходе такого формирования модели мы стараемся прогнать программу по самым часто используемым веткам (задействуя ветки, соответствующие наиболее востребованным функциям и use case-ам), а следовательно, модель позволяет проверить deadlock-о безопасность этих наиболее вероятных веток.

        Поиск deadlock-ов реально настолько сложен, что даже такой не-100% вариант покрытия ситуаций существенно облегчает жизнь и придает уверенности в завтрешнем дне;)

        Мы исследовали вариант построения модели по исходникам, но в случае наших систем он оказался неприменим, т.к. разрабатываемое нами ПО имеет компонентную архитектуру, при этом компоненты связываются в единое целое в run-time на основе xml-спецификаций — слишком сложно это автоматическим способом связать в целостную модель использования средств синхронизации. Так что эта инженерная задача остается открытой.
          0
          принципиально иное средство синхронизации — сигнальная переменная

          А можно здесь подробнее? в чем принципиальное отличие?
          Механизм вроде бы тотже… или вы имеете ввиду что не используются механизмы синхронизации ядра?
            +4
            Механизмы синхронизации ядра нам тут, как раз, совершенно не важны!

            Интересует именно прикладной аспект использования средства синхронизации. В отличие от мьютексов тут имеет место быть, скажем так, несимметричность потоков, являющихся участниками блокировки. Я уже понял, что тема интересна, поэтому ждите еще один пост, который будет целиком посвящен именно сигнальным переменным. Там будет рассмотрено два типовых deadlock-а:
            1. Сигнальная переменная + Сигнальная переменная
            2. Сигнальная переменная + Мьютекс
              +2
              Конечно, пишите. Тема интересна.
            0
            Для более сложных программ мы сделали библиотеку, которая подменяет вызовы libpthread по созданию и удалению потоков, а также по обращению к средствам синхронизации

            Вот это уже интересно надо будет попробовать :)
              0
              Ну, подменить libpthread каким-нибудь wrapper-ом вокруг нее — это дело нехитрое:)
              Более хитрое дело — это формирование в run-time модели обращения к средствам синхронизации. Учтите, что они в потоках часто носят циклический характер, т.е. по фрагменту кода:

              while(!_finished)
              {
                  pthread_mutex_lock(&_mutex);
                  
                  // do something
              
                  pthred_mutex_unlock(&_mutex);
              }
              


              должна получиться модель 0-L-U-0, а не 0-L-U-L-U-L-U-L-U-L-U-L-U-L-U-L-U-.... :)
                0
                Хм я как раз думаю что можно записывать и 2-ю последовательность а приводить к нормальной форме как один из этапов обработки графа, разве нет?
                Иначе механизм сбора долен быть очень сложным сам по себе
                  0
                  И у Вас ошибка в записи 2-й последовательности. Должно быть:
                  0-L-U-0-L-U-0-L-U-0-L-U-0...
                    0
                    Это не у меня ошибка, а я как раз предостерегаю Вас от такой ошибки;) Но, судя по всему, это было лишним:)

                    Чтобы понять, что там в серединке «0» есть, как раз и надо выполнить обработку накопленной последовательности. Это не сложно, но надо не забыть. Просто такой цикл может за несколько секунд выполниться сотню, а то и тысячу раз и оставлять это на какую-то постобработку графа нельзя. Таких потоков могут быть десятки, они просто утопят все в своей raw информации.
                      0
                      Спасибо, теперь я лучше понял Вашу мысль и то как именно вы строите такой граф, действительно можно обрабатывать такую информацию сразу.
          +1
          А сколько у вас вообще различных mutex'ов в типичной программе используется? И на каком языке пишите?
            0
            Пишем на C++. В боевой системе в зависимости от конфигурации около сотни различных средств синхронизации (мутексов и сигнальных переменных). Для анализа разбивали ее на непересекающиеся с точки зрения средств синхронизации фрагменты, а то анализ полученной автоматизированным способом модели занимает дни вычислений.

            Все-таки поиск deadlock-ов в существующей программе — это несколько другая задача. В этом посте акцент все-таки делается на том, как писать программы так, чтобы deadlock-и не пришлось искать;)

            Надо сказать, что соблюсти эти простые правила не всегда оказывается просто. Пример ситуации мы показали в одном из предыдущих постов — habrahabr.ru/company/nordavind/blog/175401/.
              +2
              А почему так много мьютексов и потоков? Не кажется ли вам что гораздо эффективнее было бы пересмотреть архитектуру приложения? И кстати если не секрет что делает ваше ПО, что ему требуется столько потоков? Ведь переключение между потоками тоже очень затратная операция
                0
                Мы занимаемся разработкой программного обеспечения для цифровых систем видеонаблюдения (http://nordavind.ru/node/118).

                Насчет пересмотра архитектуры приложения Вы совершенно правы! И в новой версии софта эта архитектура существенно пересмотрена в сторону уменьшения числа потоков за счет выполнения большинства некритичных (non-real-time) операций последовательно в рамках неких eventloop-ов. Количество потоков уменьшилось, сопровождение упростилось, но систему все равно трудно назвать простой или маленькой:)

                Но в любом случае перед нами стоит и будет еще несколько лет стоять задача сопровождения и легкой докрутки старой версии софта, которая благополучно эксплуатируется на многих объектах. Там за архитектурные недоработки приходится отвечать сполна.
                  +1
                  Почему то я сразу так и подумал :) Даже не заглядывая в ваш профиль)

                  Какое-то время тоже работал в компании занимающейся видеонаблюдением, анализом видеоданных и комплексными системами безопасности. Там проблема многопоточности решалась с помощью потокобезопасных очередей и все модули между собой общались через сигал-слот подобный механизм. Рядовой программист, который работал например над распознаванием видео и ему не надо было вносить какие-либо изменения в ядро, вообще не задумывался как оно там все внутри устроено, какие модули в каких потоках работают и т.д.
            +6
            А здорово вы перевели проблему синхронизации в топологию. Очень интересная аналогия, хотелось бы продолжения банкета.
              +1
              Спасибо за интерес! Следующий пост сделаем по ситуациям блокировок с сигнальными переменными, ну и конечно, дадим практические рекомендации, как их не допускать.

              Модель действительно получилась неплохая, а самое главное, наглядная. Но тут надо понимать, что в конечном счете эта модель описывается достаточно суровой математикой, иначе просто оказалось невозможно построить непротиворечивые доказательства.
                +1
                Я люблю суровую математику, так что был бы рад и этой части, хотя бы в обзорном виде.
                +2
                Идеально было бы, если бы этот граф строился и анализировался автоматически.
                  +2
                  Автоматический анализ графа — задача вполне решаемая и у нас есть небольшой инструмент, которым мы такой анализ проводим. Нужно понимать, конечно, что полным перебором на модели реальной мало-мальски большой системы (сотни потоков, десятки средств синхронизации) такой обсчет займет недели даже на современной технике. Вобщем, алгоритм анализа со всеми его оптимизациями — потенциальная тема для еще одного поста:)

                  Что касается автоматического построения модели (графа), то как уже писал выше, мы строим ее по run-time маршрутам, жертвуя, конечно, при этом полнотой модели. Но в случае deadlock-ов лучше так, чем никак вообще.
                  Построение по исходникам — идеальный вариант, но нереализуемый в случае наших сильно компонентных систем, собирающихся в единую программу в run-time на основе xml-ки, описывающей порядок загрузки компонентов.
                0
                Спасибо, было интересно, продолжайте!
                  0
                  Кажется, что если второе правило соблюдается, то первое правило не нужно. Не важно в каком порядке отпускать блокировки (потому что отпускание блокировки никогда не блокируется), если берутся они всегда в одном и том же порядке.
                    +2
                    Первое правило, больше подстраховка от случая, когда вы будите выполнять вот так: L1 — L2 — U1 — L1 — … Если строго придерживаться правила, что захват всегда в одном и том же порядке, то т.к. у вас уже захвачен L2, вы не имеете права захватывать L1. Но, кто же об этом будет помнить. Поэтому и вводится правило об освобождении в порядке обратном захвату.
                      0
                      Бинго! Именно так.
                    +2
                    Мне приходится много работать с многопточным кодом из явы и конечно неприятностей избежать этими 2мя простыми правилами не выходит.
                    Во первых зависимости не обязаны быть мутексами, это могут быть абсолютно разнообразные межнитевые взаимодействия, скажем спинлоки, может просто волатильный флаг стоять как такой барьер.
                    Дальше, даже один поток может сам себя залочить, хотя формально это и не дедлок. Скажем если тред разбирающий очередь попытается блокирующе записать в нее же, а она полна.
                    Дальше, есть проблемы с сторонним кодом или со своим же кодом, но других уровней. Скажем нам надо вызвать некий листенер несколько раз не допустив реордеринга. Для этого обычно все вызовы листенера оборачивают в локи. Но этот листенер ничего не знает об этом и могут быть сюрпризы. Скажем если на событие из сети мы вызывваем листенер, а он посылает нам назад команду послать чтото в сеть. Вот тут часто влетаешь в то, что листенер был вызван под тем же локом, который требуется для того, чтобы чтото послать. А то сложно гарантировать порядок транспортной библиотеке. Ну вот это тоже готовый дедлок.

                    Сильно упрощает ситуацию с дедлокам паттерн с перекидыванием команд в сингл тред. Шанс словить бяк резко падает, на практике. Все тяжелые операции можно кидать в тредпулы через теже очереди. Если аккуратно прописать тред модель, резко упрощает разработку.
                    Также хорошо работает правило, никогда не вызывать «чужой» код под своими локами. Реордеринг тут увы придется решать скажем сиквенс намберами.Опять же, вшнешние либы не перепишешь.
                    Так же есть финт, с превращением дедлоков в лив локи. То есть по таймауту из ожидания лока вываливаться, ресетить транзакцию и с небольшой паузой попытаться еще раз. Тут дедлок превращается в приличную потерю по перформансу, так что стоит мониторить кол-во таких вот откатов и следить, что их немного. Но обычно это всеже лучше.

                    Тут еще такой момент, можно при вызове некоего кода, которые требует лок2 из кода который требует лок1 можно делать в другом потоке. Скажем, отдать в некий тред команду на исполнение. Но тут это неизбежно отсроченные вызов и легко может привести к ситуации, когда вместо дедлока мы получаем OOME, если же сделать очередь конечной то в момент ее заполненности у нас 2 варианта. Либо выбросить задачу нафиг с ошибкой в лог, либо ждать. Второе очевидно опять же может привести к дедлоку.

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

                    В общем, можно про дедлоки долго писать, тема богатая.
                      +1
                      Если позволите, я в ответ напишу лишь несколько тезисов, коль скоро, вопросов Вы не задали, а просто поделились тем, как тяжело жить программисту многопоточных приложений:)
                      1. Данный пост рассматривает программы, в которых вся синхронизация выстроена на мьютексах. Тогда соблюдения этих двух правил достаточно, чтобы не знать проблем.
                      2. При всем многообразии названий средств синхронизации на разных платформах (windows/mac.linux/др), разных языках программирования, разном уровне программирования (user/kernel) все они могут быть отнесены к простой классификации

                      3. Правилам использования других средств синхронизации я посвящу отдельный пост.

                      Но! Даже знание этих правил не всегда помогает, т.к. возможны такие архитектурные коллизии, при которых нельзя не нарушить правила, чтобы при сохранении общей архитектуры программы обеспечить требуемую функциональность. В этом случае выход один — менять архитектуру во имя исключения потенциальной ситуации взаимной блокировки.
                        0
                        В Яве все сильно сложнее, примитивов синхронизации очень много и некоторые довольно навороченные.
                          +1
                          В ответ приведу фрагмент нашего исследования (такой у нас есть по всем распространенным платформам и языкам). Данные по средствам синхронизации JAVA получены из материалов ресурса www.sun.com (раздел «API & Docs»). Встроенные средства синхронизации синхронизируют выполнение потоков. Выполнение процессов регулируется средствами синхронизации операционной системы.
                          1. Замок (Lock) – исключающий семафор, обладающий возможностями:
                          — неблокирующего захвата;
                          — функцией захвата до прерывания (поток захватывает исключающий замок или ожидает его захвата до прерывания, если замок был захвачен, то во время прерывания он отпускается);
                          — функцией неблокирующего захвата до прерывания (ожидание здесь может идти до срабатывания таймера).
                          Замок представляет собой нерекурсивный исключающий семафор (может быть блокирующий или неблокирующий).
                          Следующие три класса замков наследуются от этого и обладают его функциональными возможностями.
                          2. Рекурсивный замок (Reentrant lock) – рекурсивный исключающий семафор (может быть блокирующий или неблокирующий).
                          3. Замок чтения/записи (ReadWrite lock) – средство синхронизации, позволяющее одновременно обращаться к ресурсу группе читающих потоков или одному пишущему. Состоит из читающих и пишущих замков. По умолчанию приоритет доступа не задан, однако, существует большое количество политик доступа. Пишущий замок может быть заменен читающим и наоборот. Данное средство синхронизации предоставляет возможность неблокирующего захвата, но на нее не распространяются правила политик доступа. Читающий или пишущий замок может быть ассоциирован с переменной кондиции.
                          Возможна реализация замка чтения/записи с помощью одного блокирующего исключающего семафора нерекурсивного типа и двух блокирующих сигнальных переменных без памяти.
                          4. Рекурсивный замок чтения/записи (ReentrantReadWrite lock) – является рекурсивным аналогом замка чтения/записи.
                          Возможна реализация рекурсивного замка чтения/записи с помощью одного блокирующего исключающего семафора рекурсивного типа и двух блокирующих сигнальных переменных без памяти.
                          5. Переменная кондиции (Condition) – сигнальная переменная, которая обладает методами:
                          — прерываемого ожидания сигнала;
                          — прерываемого ожидания сигнала до истечения заданного времени;
                          — прерываемого ожидания до наступления заданного момента времени;
                          — непрерываемого ожидания.
                          Сигнал сбрасывается, если нет ожидающих потоков. Возможно оповещение всех потоков, находящиеся в состоянии ожидания.
                          Переменная кондиции представляет собой сигнальную переменную без памяти (может быть блокирующей и неблокирующей).
                          6. Семафор (Semaphore) – сигнальная переменная, которая имеет счетчик, фиксирующий количество свободных пропусков на доступ к ресурсу. Поток перед получением доступа к ресурсу должен получить пропуск (можно получить несколько пропусков за один запрос). Если счетчик пропусков не положителен, запрашивающий поток переходит в состояние ожидания. Ожидание получения пропуска может быть прекращено по истечении заданного периода времени или в результате прерывания.
                          Операции получения и освобождения пропуска не связаны: можно освободить пропуск, предварительно ничего не получая.
                          Семафор представляет собой сигнальную переменную с памятью (может быть блокирующей или неблокирующей).
                          7. Защелка обратного отсчета (CountDownLatch) – средство синхронизации, позволяющее потокам ожидать выполнения некоторого заданного набора операций. В основе защелки обратного отсчета лежит счетчик и операция, уменьшающая счетчик на 1. Когда счетчик достигает 0, все потоки, находящиеся в состоянии ожидания, освобождаются. Счетчик нельзя переустановить. Ожидание счетчика может быть прекращено по истечении заданного периода времени или в результате прерывания.
                          Защелка обратного отсчета представляет собой сигнальную переменную с памятью (может быть блокирующей или неблокирующей).
                          8. Циклический барьер (CyclicBarrier) – средство синхронизации группы потоков. Каждый поток в этой группе выполняется до определенной точки, называемой барьером. После достижения барьера поток переходит в состояние ожидания, которое прекращается, когда все потоки достигнут барьера (каждый своего). Барьер можно разрушить. Если поток пришел в точку барьера не последним, то он ожидает одного из следующих событий:
                          — последний поток пришел в точку барьера;
                          — истекло заданное время ожидания одного из потоков;
                          — произошло прерывание одного из потоков;
                          — барьер был разрушен одним из потоков.
                          Циклический барьер может быть реализован на основе сигнальной переменной с памятью (может быть блокирующей или неблокирующей).
                          9. Обменник (Exchanger) – средство синхронизации, которое позволяет потокам обмениваться данными. Если поток достигает точки обмена, он переходит в состояние ожидания, до одного из следующих событий:
                          — истек заданный период времени;
                          — произошло прерывание;
                          — другой поток пришел в точку обмена, где произойдет обмен данными.
                          Это средство синхронизации может быть реализовано на основе сигнальной переменной с памятью (может быть блокирующей или неблокирующей).
                          10. Директива synchronized – критическая секция.
                          Представляет собой нерекурсивный исключающий семафор (может быть блокирующий или неблокирующий).

                          Все перечисленное прекрасно укладывается в приведенную выше классификацию. Если что-то забыл, пишите — будем разбираться;)
                            0
                            Так непривычно читать русские переводы явовских примитивов синхронизации, особенно:
                            — Замок (Lock)
                            — Рекурсивный замок чтения/записи (ReentrantReadWrite lock)
                            — Переменная кондиции (Condition)
                            — Защелка обратного отсчета (CountDownLatch)
                            :)
                              0
                              Ну это не совсем так. Все высокоуровневые примитивы в конечном итоге упирается в Unsafe.park().
                              Дальше, кроме директивы synchronized есть еще wait и Thread.sleep. Дальше, локи между потоками могут подниматься в нативном коде и это довольно частая ситуация. Кроме того, есть еще спин-лок, когда живой тред крутит касы, пока не получится. То есть даже задиагностировать на живой системе по тред дампу ситуацию дедлока довольно сложно. Так же, всегда можно придумать высокоуровневый примитив, который будет подвисать совершенно неожиданным образом. Например, поток который будет периодически просыпаться, но проверять какие-то условия и снова засыпать, технически это будет live-lock, но по сути дедлок, ибо потоки будут почти все время спать. Например, некая задача просто лежит в очереди в тред пул, но изза нечестной очереди, она никогда не будет этим тредпулом обработана. Формально эта задача вообще не имеет никаких технчиеских блокировок, а на деле она может создать одно из ребер дедлока. Скажем, если она состоит из нескольких частей и одна из частей возьмет лок. Это я к тому, что даже задача диагностики реального дед лока на живой системе крайне нетривиальна.
                                0
                                С чем соглашусь, так это с тем, что возможны алгоритмические локи, когда программа крутится где-то в ожидании чего-то, что алгоритмически никогда не наступит. Это отдельная сложная задача — верификация алгоритмов. Но это далеко от классического понимания deadlock-a…
                                  0
                                  Не скажу за других, но в Яве все локи такие, они довольно сложные и алгоритмические. Поэтому тут нет существенной разницы со «своим» алгоритмом. Наружу он точно также может выглядеть базовым перимитивом, а внутри иметь очень неочевидную логику. Тот же synchronized имеет очень много ньюансов и режимов работы, которые еще и конфигурируются на уровне JVM.
                                0
                                Дальше, есть еще одна проблема. Скажем, нас вызывает некая библиотека, чужой код, как коллбек. Причем, коллбек вызывает под своим локом. А надо вызвать эту библиотеку с неким ответом, причем этот вызов идет под тем же самым локом. Причем, поток в котором вызывается коллбек не наш, а чужой и его надо побыстрее освободить, то есть библиотеку вызывать должен другой (наш) поток. Но, также требуется, чтобы наши вызовы с ответом должны идти в томже самом порядке, что и их нашего коллбека. И все это должно иметь фиксированные ограничения по памяти, чтобы не схлопотать под нагрузкой ООМ.

                                Я вот просто не знаю решения этой задачи в принципе. Всегда приходится чемто пожертвовать, либо остается некий шанс на дедлок, либо всегда можно представить сценарий, когда любые (конечные) требования по памяти будут нарушены.
                                  0
                                  Тут рецепт только один — не надо смешивать свои блокировки с блокировками внешних (тем более закрытых) библиотек. Если мы не можем их учесть в нашей модели, а следовательно, не можем гарантировать потокобезопасность использующего их кода, то надо их «гальванически развязать», например, через какую-нибудь очередь, наполняемую сторонней библиотекой, а вычитываемой нашей программой. Так мы четко локализуем место соприкосновения нашего прекрасного кода с небезопасным сторонним:)
                                    0
                                    С очередью, как я уже дважды писал есть проблема с неконтролируемым ее ростом и ограниченной памятью. А притормозить листенер, если очередь полна чревато как раз таки дедлоком по вышеописанной схеме. Сделать, как я понимаю, тут принципиально ничего нельзя в общем случае.
                                      0
                                      Проблема всех очередей всегда состоит в том, что, если на другом конце ее не успевают опустошать также интенсивно, как набивают на другом, то в какой-то момент придется что-нибудь drop-нуть;)
                                        0
                                        Не совсем. Более цивилизованный способ это както донести этой библиотеке, что мы не справляемся. Както ее притормозить. Обычно для этого просто подвешивают листенер, а дальше часто этой библиотеке проще както дропнутые данные восстановить. Скажем перезапросить из сети или еще как. Но вот есть и обратка такая, в виде шанса на дедлок.

                                        Причем, беда в том, что тут ничего и не придумать лучше. Я вот дедлоки не люблю, поэтому листенеры неизбежно могут вызывать одновременно, переставленные итп. Ну либо дизайнить эти локи очень аккурартно, чтобы гарантировать, что их можно получить лишь предсказуемыми трассами и снаружи никто до них доступится не сможет. Это редко удается. Да и еще реже удается поработать с чужим кодом настолько продуманным.

                                        Я пришел к выводу, что дедлоки неизбежны, а избыточная борьба с ними, просто делает код сложнее в поддержке. Значительно сложнее. Взаимодействие между уровнями превращается просто в яростную боль. Еще не придумал идеальную стратегию, но если приложение живет не больше недели-месяца, то проще просто детектировать такие ситуации и поднимать резервные потоки для той же логики. Вот только, как я выше писал, даже с детектированием таких патологий есть сильные проблемы. Ну, или действительно дропать, тоже вариант. Тем более, что как правило потерянное данное можно таки восстановить и пересчитать. Но тут очень уже важен мониторинг, чтобы эти ситуации оставались редкими исключениями.

                                        Ну и разумен вариант, когда каждый слой приложения имеет 3 звена. Для инпута, для аутпута и собсна бизнесс логики. И все три звена обязаны иметь независимые потоки. Не снимает проблему дедлоков (или как вы верно написали дропов) полностью, но значительно снижает такие риски. Но и цену имеет значительную.
                                          0
                                          > Не совсем. Более цивилизованный способ это както донести этой библиотеке, что мы не справляемся. Както ее притормозить. Обычно для этого просто подвешивают листенер, а дальше часто этой библиотеке проще както дропнутые данные восстановить. Скажем перезапросить из сети или еще как.

                                          Т.е. предлагаете, чтобы сама библиотека drop-нула то, что вы не успеваете обрабатывать?:)

                                          > Я пришел к выводу, что дедлоки неизбежны, а избыточная борьба с ними, просто делает код сложнее в поддержке.
                                          Простите, я адепт другой веры;) Я считаю, что дедлоки недопустимы и даже если существует лишь потенциальная угроза их возникновения при какой-то невероятной динамике, то с этой потенциальной ситуацией уже надо бороться!
                          0
                          А почему порядок отпускания важен? (первое правило)

                          Допустим на множестве мьютексов определено отношение строгово порядка.
                          Пусть L — множество блокировок, удерживаемых потоком в настоящий момент.
                          Утверждается, что допустимо захватывать любой мьютекс, который следует после всех мьютексов в L согласно используемому отношению, а порядок отпускания не важен.
                            +1
                            Все верно. Этот вопрос уже поднимался чуть выше, поэтому процитирую:

                            > Первое правило, больше подстраховка от случая, когда вы будите выполнять вот так: L1 — L2 — U1 — L1 — … Если строго придерживаться правила, что захват всегда в одном и том же порядке, то т.к. у вас уже захвачен L2, вы не имеете права захватывать L1. Но, кто же об этом будет помнить. Поэтому и вводится правило об освобождении в порядке обратном захвату.
                              +1
                              Чукча писатель :)

                              А вобще есть отличная задача на понимание: реализовать thread-safe B-tree с блокировками на уровне узлов (точнее, описать последовательность захвата блокировок при различных операциях с деревом и показать отсутствие взаимных блокировок). Ответ — сверху вниз и слева на право.
                            0
                            спасибо, тема интересна,
                            ждем продолжения про условные переменные
                              0
                              Продолжение можно прочитать здесь.
                                0
                                Так Вы непосредственно в самой статье укажите ссылку на продолжение.Почему-то уверен, что комментарий потеряется
                                  0
                                  Спасибо! Так и сделал,
                                    0
                                    Про юзабилити: название ссылки «здесь» ни о чем не говорит и лучше называть статьей. Лаконичное и ясное название ссылки даст возможность читателю быстрее принять решение стоит ли ему переходить по ссылке. + ко всему, если Вы планируете писать цикл статей, то рекомендую указывать и номер статьи в этом цикле. Это позволит быстрее ориентироваться по прочитанному циклу.
                                0
                                Спасибо! Отличная статья, отличные правила.
                                Скажите, может вы знаете решение покрасивее для задачи с двумя мьютексами A и B:
                                Поток типа 1 должен захватить мьютекс A, совершить какую-то работу и захватить мьютекс B, не отпуская A, совершить работу и отпустить оба мьютекса

                                Поток типа 2 должен захватить мьютекс B, проверить условия и в зависимости от результатов проверки возможно потребуется захватить и мьютекс A

                                Потоков типа1 и типа2 может быть сколько угодно. Производительность критична. Есть что-нибудь лучше, чем в потоке типа 2 сразу захватывать мьютексы A и B?

                                  0
                                  Если задача ставится именно так, как описано в Вашем комментарии, то ничего «покрасивее» придумать нельзя — мьютексы надо захватывать обязательно в одном порядке во всех потоках и никак иначе. Решение можно попробовать поискать в другой плоскости, проанализировав прикладную задачу, можно попытаться уйти от проектного решения, когда требуется захватывать мьютексы в разном порядке в разных потоках.

                                  На самом деле, захват мьютекса не так уж критичен с точки зрения производительности. Вряд ли весь остальной код настолько вылизан и оптимизирован, чтоб был заметен захват мьютекса:) Хотя, тут Вам виднее.
                                    0
                                    Спасибо!

                                Only users with full accounts can post comments. Log in, please.