Если позволите, я в ответ напишу лишь несколько тезисов, коль скоро, вопросов Вы не задали, а просто поделились тем, как тяжело жить программисту многопоточных приложений:)
1. Данный пост рассматривает программы, в которых вся синхронизация выстроена на мьютексах. Тогда соблюдения этих двух правил достаточно, чтобы не знать проблем.
2. При всем многообразии названий средств синхронизации на разных платформах (windows/mac.linux/др), разных языках программирования, разном уровне программирования (user/kernel) все они могут быть отнесены к простой классификации
3. Правилам использования других средств синхронизации я посвящу отдельный пост.
Но! Даже знание этих правил не всегда помогает, т.к. возможны такие архитектурные коллизии, при которых нельзя не нарушить правила, чтобы при сохранении общей архитектуры программы обеспечить требуемую функциональность. В этом случае выход один — менять архитектуру во имя исключения потенциальной ситуации взаимной блокировки.
Мы занимаемся разработкой программного обеспечения для цифровых систем видеонаблюдения (http://nordavind.ru/node/118).
Насчет пересмотра архитектуры приложения Вы совершенно правы! И в новой версии софта эта архитектура существенно пересмотрена в сторону уменьшения числа потоков за счет выполнения большинства некритичных (non-real-time) операций последовательно в рамках неких eventloop-ов. Количество потоков уменьшилось, сопровождение упростилось, но систему все равно трудно назвать простой или маленькой:)
Но в любом случае перед нами стоит и будет еще несколько лет стоять задача сопровождения и легкой докрутки старой версии софта, которая благополучно эксплуатируется на многих объектах. Там за архитектурные недоработки приходится отвечать сполна.
Автоматический анализ графа — задача вполне решаемая и у нас есть небольшой инструмент, которым мы такой анализ проводим. Нужно понимать, конечно, что полным перебором на модели реальной мало-мальски большой системы (сотни потоков, десятки средств синхронизации) такой обсчет займет недели даже на современной технике. Вобщем, алгоритм анализа со всеми его оптимизациями — потенциальная тема для еще одного поста:)
Что касается автоматического построения модели (графа), то как уже писал выше, мы строим ее по run-time маршрутам, жертвуя, конечно, при этом полнотой модели. Но в случае deadlock-ов лучше так, чем никак вообще.
Построение по исходникам — идеальный вариант, но нереализуемый в случае наших сильно компонентных систем, собирающихся в единую программу в run-time на основе xml-ки, описывающей порядок загрузки компонентов.
Механизмы синхронизации ядра нам тут, как раз, совершенно не важны!
Интересует именно прикладной аспект использования средства синхронизации. В отличие от мьютексов тут имеет место быть, скажем так, несимметричность потоков, являющихся участниками блокировки. Я уже понял, что тема интересна, поэтому ждите еще один пост, который будет целиком посвящен именно сигнальным переменным. Там будет рассмотрено два типовых deadlock-а:
1. Сигнальная переменная + Сигнальная переменная
2. Сигнальная переменная + Мьютекс
Это не у меня ошибка, а я как раз предостерегаю Вас от такой ошибки;) Но, судя по всему, это было лишним:)
Чтобы понять, что там в серединке «0» есть, как раз и надо выполнить обработку накопленной последовательности. Это не сложно, но надо не забыть. Просто такой цикл может за несколько секунд выполниться сотню, а то и тысячу раз и оставлять это на какую-то постобработку графа нельзя. Таких потоков могут быть десятки, они просто утопят все в своей raw информации.
Спасибо за интерес! Следующий пост сделаем по ситуациям блокировок с сигнальными переменными, ну и конечно, дадим практические рекомендации, как их не допускать.
Модель действительно получилась неплохая, а самое главное, наглядная. Но тут надо понимать, что в конечном счете эта модель описывается достаточно суровой математикой, иначе просто оказалось невозможно построить непротиворечивые доказательства.
Ну, подменить 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-.... :)
Пишем на C++. В боевой системе в зависимости от конфигурации около сотни различных средств синхронизации (мутексов и сигнальных переменных). Для анализа разбивали ее на непересекающиеся с точки зрения средств синхронизации фрагменты, а то анализ полученной автоматизированным способом модели занимает дни вычислений.
Все-таки поиск deadlock-ов в существующей программе — это несколько другая задача. В этом посте акцент все-таки делается на том, как писать программы так, чтобы deadlock-и не пришлось искать;)
Надо сказать, что соблюсти эти простые правила не всегда оказывается просто. Пример ситуации мы показали в одном из предыдущих постов — habrahabr.ru/company/nordavind/blog/175401/.
Применительно к данной статье к графу надо относиться скорее как к некоторой нотации, на которой я наглядно поясняю ситуации блокировок. Если соблюдать правила использования средств синхронизации в процессе программирования (этих правил, несколько больше, чем рассмотрено в статье, т.к. есть еще одно, принципиально иное средство синхронизации — сигнальная переменная), то граф строить не придется.
Но, как Вы правильно догадались, можно попытаться по уже написанной программе построить граф и выявить наличие (или подтвердить отсутствие) нарушений правил. Для небольшой программы это можно сделать и вручную. С другой стороны, для небольшой программы можно и без этого обнаружить нарушения (построив модель в голове).
Для более сложных программ мы сделали библиотеку, которая подменяет вызовы libpthread по созданию и удалению потоков, а также по обращению к средствам синхронизации, сбрасывая в run-time информацию о структуре графа в файл виде xml-ки. Очевидный недостаток: в ходе run-time выполнения мы не можем гарантировать, что программа прошла по всем веткам, а следовательно, не можем гарантировать, что модель полна. Этот недостаток компенсируется тем, что в ходе такого формирования модели мы стараемся прогнать программу по самым часто используемым веткам (задействуя ветки, соответствующие наиболее востребованным функциям и use case-ам), а следовательно, модель позволяет проверить deadlock-о безопасность этих наиболее вероятных веток.
Поиск deadlock-ов реально настолько сложен, что даже такой не-100% вариант покрытия ситуаций существенно облегчает жизнь и придает уверенности в завтрешнем дне;)
Мы исследовали вариант построения модели по исходникам, но в случае наших систем он оказался неприменим, т.к. разрабатываемое нами ПО имеет компонентную архитектуру, при этом компоненты связываются в единое целое в run-time на основе xml-спецификаций — слишком сложно это автоматическим способом связать в целостную модель использования средств синхронизации. Так что эта инженерная задача остается открытой.
Погуглил эту тему и наткнулся на некоторое недопонимание: чем отличается CLOCK_MONOTONIC_RAW от CLOCK_MONOTONIC? И самое главное, почему именно CLOCK_MONOTONIC_RAW «спасает от NTP»? От любого перевода времени должен спасать любой monotonic ход времени.
Также немного смущает информация из другого Хабрапоста (http://habrahabr.ru/post/111234/), где автор указывает, что CLOCK_MONOTONIC_RAW «не смог протестировать ни на одной машине из доступных — везде они возвращали нули». Это non-portable?
Прочитал — задумался. На самом деле деле, действительно, с академической точки зрения небезопасно, но на практике компиллятор (по крайней мере известные мне версии gcc3 и 4) как-то догадывались сами, что оптимизировать это поле не стоит.
Согласен на 100%, что полагаться на догадки компилятора не следует, ибо надо писать true portable код, поэтому volatile нам в руки!
Да, о spurious wakeup, действительно, мало кто подозревает. Одним из use cases для сигнальных переменных является «управляемый sleep», когда мы хотим усыпить какой-нибудь поток на какое-то длительное время, но при этом хотим оставить себе возможность разбудить его «досрочно», например, чтобы завершить. Вот тут spurious wakeup может внести свои коррективы в наши планы.
Поделитесь, как Вы решали проблему «перевода времени назад»?
Очереди — это хорошо. Но иногда (как в нашем случае), требуется обеспечить синхронную отработку, т.е. после возврата из unregisterCallback мы гарантированно должны быть уверены в том, что нас уже отписали, а не просто поместили в какую-то очередь.
Паттерн с очередями мы активно используем там, где это можно. Мы его называем «гальванической развязкой»:)
Очень важное пояснение: дедлок может образоваться не только из мутексов — это наиболее очевидный и распространенный вариант, о котором уже много написано и сказано. Участником цепочки дедлока может быть любая операция, которая предполагает ожидание чего-либо в другом потоке, например, ожидание завершения другого потока (pthread_join или QThread::wait — кому как привычнее) или ожидание переменной кондиции, как в рассмотренном нами примере.
Deadlock-и являются одной из самых неприятных проблем программирования, т.к. их появление зависит от динамики. В данной статье мы привели пример далеко не самого тривиального дедлока и, как показывает обсуждение ниже, далеко не все даже поняли, где тут может возникнуть ситуация взаимной блокировки. Мы решили поделиться опытом, чтобы другие не наступали на грабли. Если Вам это кажется тривиальным, то респект и уважуха:)
1. Данный пост рассматривает программы, в которых вся синхронизация выстроена на мьютексах. Тогда соблюдения этих двух правил достаточно, чтобы не знать проблем.
2. При всем многообразии названий средств синхронизации на разных платформах (windows/mac.linux/др), разных языках программирования, разном уровне программирования (user/kernel) все они могут быть отнесены к простой классификации
3. Правилам использования других средств синхронизации я посвящу отдельный пост.
Но! Даже знание этих правил не всегда помогает, т.к. возможны такие архитектурные коллизии, при которых нельзя не нарушить правила, чтобы при сохранении общей архитектуры программы обеспечить требуемую функциональность. В этом случае выход один — менять архитектуру во имя исключения потенциальной ситуации взаимной блокировки.
Насчет пересмотра архитектуры приложения Вы совершенно правы! И в новой версии софта эта архитектура существенно пересмотрена в сторону уменьшения числа потоков за счет выполнения большинства некритичных (non-real-time) операций последовательно в рамках неких eventloop-ов. Количество потоков уменьшилось, сопровождение упростилось, но систему все равно трудно назвать простой или маленькой:)
Но в любом случае перед нами стоит и будет еще несколько лет стоять задача сопровождения и легкой докрутки старой версии софта, которая благополучно эксплуатируется на многих объектах. Там за архитектурные недоработки приходится отвечать сполна.
Что касается автоматического построения модели (графа), то как уже писал выше, мы строим ее по run-time маршрутам, жертвуя, конечно, при этом полнотой модели. Но в случае deadlock-ов лучше так, чем никак вообще.
Построение по исходникам — идеальный вариант, но нереализуемый в случае наших сильно компонентных систем, собирающихся в единую программу в run-time на основе xml-ки, описывающей порядок загрузки компонентов.
Интересует именно прикладной аспект использования средства синхронизации. В отличие от мьютексов тут имеет место быть, скажем так, несимметричность потоков, являющихся участниками блокировки. Я уже понял, что тема интересна, поэтому ждите еще один пост, который будет целиком посвящен именно сигнальным переменным. Там будет рассмотрено два типовых deadlock-а:
1. Сигнальная переменная + Сигнальная переменная
2. Сигнальная переменная + Мьютекс
Чтобы понять, что там в серединке «0» есть, как раз и надо выполнить обработку накопленной последовательности. Это не сложно, но надо не забыть. Просто такой цикл может за несколько секунд выполниться сотню, а то и тысячу раз и оставлять это на какую-то постобработку графа нельзя. Таких потоков могут быть десятки, они просто утопят все в своей raw информации.
Модель действительно получилась неплохая, а самое главное, наглядная. Но тут надо понимать, что в конечном счете эта модель описывается достаточно суровой математикой, иначе просто оказалось невозможно построить непротиворечивые доказательства.
Более хитрое дело — это формирование в run-time модели обращения к средствам синхронизации. Учтите, что они в потоках часто носят циклический характер, т.е. по фрагменту кода:
должна получиться модель 0-L-U-0, а не 0-L-U-L-U-L-U-L-U-L-U-L-U-L-U-L-U-.... :)
Все-таки поиск deadlock-ов в существующей программе — это несколько другая задача. В этом посте акцент все-таки делается на том, как писать программы так, чтобы deadlock-и не пришлось искать;)
Надо сказать, что соблюсти эти простые правила не всегда оказывается просто. Пример ситуации мы показали в одном из предыдущих постов — habrahabr.ru/company/nordavind/blog/175401/.
Но, как Вы правильно догадались, можно попытаться по уже написанной программе построить граф и выявить наличие (или подтвердить отсутствие) нарушений правил. Для небольшой программы это можно сделать и вручную. С другой стороны, для небольшой программы можно и без этого обнаружить нарушения (построив модель в голове).
Для более сложных программ мы сделали библиотеку, которая подменяет вызовы libpthread по созданию и удалению потоков, а также по обращению к средствам синхронизации, сбрасывая в run-time информацию о структуре графа в файл виде xml-ки. Очевидный недостаток: в ходе run-time выполнения мы не можем гарантировать, что программа прошла по всем веткам, а следовательно, не можем гарантировать, что модель полна. Этот недостаток компенсируется тем, что в ходе такого формирования модели мы стараемся прогнать программу по самым часто используемым веткам (задействуя ветки, соответствующие наиболее востребованным функциям и use case-ам), а следовательно, модель позволяет проверить deadlock-о безопасность этих наиболее вероятных веток.
Поиск deadlock-ов реально настолько сложен, что даже такой не-100% вариант покрытия ситуаций существенно облегчает жизнь и придает уверенности в завтрешнем дне;)
Мы исследовали вариант построения модели по исходникам, но в случае наших систем он оказался неприменим, т.к. разрабатываемое нами ПО имеет компонентную архитектуру, при этом компоненты связываются в единое целое в run-time на основе xml-спецификаций — слишком сложно это автоматическим способом связать в целостную модель использования средств синхронизации. Так что эта инженерная задача остается открытой.
Погуглил эту тему и наткнулся на некоторое недопонимание: чем отличается CLOCK_MONOTONIC_RAW от CLOCK_MONOTONIC? И самое главное, почему именно CLOCK_MONOTONIC_RAW «спасает от NTP»? От любого перевода времени должен спасать любой monotonic ход времени.
Также немного смущает информация из другого Хабрапоста (http://habrahabr.ru/post/111234/), где автор указывает, что CLOCK_MONOTONIC_RAW «не смог протестировать ни на одной машине из доступных — везде они возвращали нули». Это non-portable?
Согласен на 100%, что полагаться на догадки компилятора не следует, ибо надо писать true portable код, поэтому volatile нам в руки!
Поделитесь, как Вы решали проблему «перевода времени назад»?
Паттерн с очередями мы активно используем там, где это можно. Мы его называем «гальванической развязкой»:)