Comments 50
Подскажите пожалуйста каким образом вы находите все возможные мьютексы и порядок их захвата?
И каким именно образом строится этот граф? Все делается вручную?
И каким именно образом строится этот граф? Все делается вручную?
Применительно к данной статье к графу надо относиться скорее как к некоторой нотации, на которой я наглядно поясняю ситуации блокировок. Если соблюдать правила использования средств синхронизации в процессе программирования (этих правил, несколько больше, чем рассмотрено в статье, т.к. есть еще одно, принципиально иное средство синхронизации — сигнальная переменная), то граф строить не придется.
Но, как Вы правильно догадались, можно попытаться по уже написанной программе построить граф и выявить наличие (или подтвердить отсутствие) нарушений правил. Для небольшой программы это можно сделать и вручную. С другой стороны, для небольшой программы можно и без этого обнаружить нарушения (построив модель в голове).
Для более сложных программ мы сделали библиотеку, которая подменяет вызовы libpthread по созданию и удалению потоков, а также по обращению к средствам синхронизации, сбрасывая в run-time информацию о структуре графа в файл виде xml-ки. Очевидный недостаток: в ходе run-time выполнения мы не можем гарантировать, что программа прошла по всем веткам, а следовательно, не можем гарантировать, что модель полна. Этот недостаток компенсируется тем, что в ходе такого формирования модели мы стараемся прогнать программу по самым часто используемым веткам (задействуя ветки, соответствующие наиболее востребованным функциям и use case-ам), а следовательно, модель позволяет проверить deadlock-о безопасность этих наиболее вероятных веток.
Поиск deadlock-ов реально настолько сложен, что даже такой не-100% вариант покрытия ситуаций существенно облегчает жизнь и придает уверенности в завтрешнем дне;)
Мы исследовали вариант построения модели по исходникам, но в случае наших систем он оказался неприменим, т.к. разрабатываемое нами ПО имеет компонентную архитектуру, при этом компоненты связываются в единое целое в run-time на основе xml-спецификаций — слишком сложно это автоматическим способом связать в целостную модель использования средств синхронизации. Так что эта инженерная задача остается открытой.
Но, как Вы правильно догадались, можно попытаться по уже написанной программе построить граф и выявить наличие (или подтвердить отсутствие) нарушений правил. Для небольшой программы это можно сделать и вручную. С другой стороны, для небольшой программы можно и без этого обнаружить нарушения (построив модель в голове).
Для более сложных программ мы сделали библиотеку, которая подменяет вызовы libpthread по созданию и удалению потоков, а также по обращению к средствам синхронизации, сбрасывая в run-time информацию о структуре графа в файл виде xml-ки. Очевидный недостаток: в ходе run-time выполнения мы не можем гарантировать, что программа прошла по всем веткам, а следовательно, не можем гарантировать, что модель полна. Этот недостаток компенсируется тем, что в ходе такого формирования модели мы стараемся прогнать программу по самым часто используемым веткам (задействуя ветки, соответствующие наиболее востребованным функциям и use case-ам), а следовательно, модель позволяет проверить deadlock-о безопасность этих наиболее вероятных веток.
Поиск deadlock-ов реально настолько сложен, что даже такой не-100% вариант покрытия ситуаций существенно облегчает жизнь и придает уверенности в завтрешнем дне;)
Мы исследовали вариант построения модели по исходникам, но в случае наших систем он оказался неприменим, т.к. разрабатываемое нами ПО имеет компонентную архитектуру, при этом компоненты связываются в единое целое в run-time на основе xml-спецификаций — слишком сложно это автоматическим способом связать в целостную модель использования средств синхронизации. Так что эта инженерная задача остается открытой.
принципиально иное средство синхронизации — сигнальная переменная
А можно здесь подробнее? в чем принципиальное отличие?
Механизм вроде бы тотже… или вы имеете ввиду что не используются механизмы синхронизации ядра?
Механизмы синхронизации ядра нам тут, как раз, совершенно не важны!
Интересует именно прикладной аспект использования средства синхронизации. В отличие от мьютексов тут имеет место быть, скажем так, несимметричность потоков, являющихся участниками блокировки. Я уже понял, что тема интересна, поэтому ждите еще один пост, который будет целиком посвящен именно сигнальным переменным. Там будет рассмотрено два типовых deadlock-а:
1. Сигнальная переменная + Сигнальная переменная
2. Сигнальная переменная + Мьютекс
Интересует именно прикладной аспект использования средства синхронизации. В отличие от мьютексов тут имеет место быть, скажем так, несимметричность потоков, являющихся участниками блокировки. Я уже понял, что тема интересна, поэтому ждите еще один пост, который будет целиком посвящен именно сигнальным переменным. Там будет рассмотрено два типовых deadlock-а:
1. Сигнальная переменная + Сигнальная переменная
2. Сигнальная переменная + Мьютекс
Для более сложных программ мы сделали библиотеку, которая подменяет вызовы libpthread по созданию и удалению потоков, а также по обращению к средствам синхронизации
Вот это уже интересно надо будет попробовать :)
Ну, подменить libpthread каким-нибудь wrapper-ом вокруг нее — это дело нехитрое:)
Более хитрое дело — это формирование в run-time модели обращения к средствам синхронизации. Учтите, что они в потоках часто носят циклический характер, т.е. по фрагменту кода:
должна получиться модель 0-L-U-0, а не 0-L-U-L-U-L-U-L-U-L-U-L-U-L-U-L-U-.... :)
Более хитрое дело — это формирование в 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-.... :)
Хм я как раз думаю что можно записывать и 2-ю последовательность а приводить к нормальной форме как один из этапов обработки графа, разве нет?
Иначе механизм сбора долен быть очень сложным сам по себе
Иначе механизм сбора долен быть очень сложным сам по себе
И у Вас ошибка в записи 2-й последовательности. Должно быть:
0-L-U-0-L-U-0-L-U-0-L-U-0...
0-L-U-0-L-U-0-L-U-0-L-U-0...
Это не у меня ошибка, а я как раз предостерегаю Вас от такой ошибки;) Но, судя по всему, это было лишним:)
Чтобы понять, что там в серединке «0» есть, как раз и надо выполнить обработку накопленной последовательности. Это не сложно, но надо не забыть. Просто такой цикл может за несколько секунд выполниться сотню, а то и тысячу раз и оставлять это на какую-то постобработку графа нельзя. Таких потоков могут быть десятки, они просто утопят все в своей raw информации.
Чтобы понять, что там в серединке «0» есть, как раз и надо выполнить обработку накопленной последовательности. Это не сложно, но надо не забыть. Просто такой цикл может за несколько секунд выполниться сотню, а то и тысячу раз и оставлять это на какую-то постобработку графа нельзя. Таких потоков могут быть десятки, они просто утопят все в своей raw информации.
А сколько у вас вообще различных mutex'ов в типичной программе используется? И на каком языке пишите?
Пишем на C++. В боевой системе в зависимости от конфигурации около сотни различных средств синхронизации (мутексов и сигнальных переменных). Для анализа разбивали ее на непересекающиеся с точки зрения средств синхронизации фрагменты, а то анализ полученной автоматизированным способом модели занимает дни вычислений.
Все-таки поиск deadlock-ов в существующей программе — это несколько другая задача. В этом посте акцент все-таки делается на том, как писать программы так, чтобы deadlock-и не пришлось искать;)
Надо сказать, что соблюсти эти простые правила не всегда оказывается просто. Пример ситуации мы показали в одном из предыдущих постов — habrahabr.ru/company/nordavind/blog/175401/.
Все-таки поиск deadlock-ов в существующей программе — это несколько другая задача. В этом посте акцент все-таки делается на том, как писать программы так, чтобы deadlock-и не пришлось искать;)
Надо сказать, что соблюсти эти простые правила не всегда оказывается просто. Пример ситуации мы показали в одном из предыдущих постов — habrahabr.ru/company/nordavind/blog/175401/.
А почему так много мьютексов и потоков? Не кажется ли вам что гораздо эффективнее было бы пересмотреть архитектуру приложения? И кстати если не секрет что делает ваше ПО, что ему требуется столько потоков? Ведь переключение между потоками тоже очень затратная операция
Мы занимаемся разработкой программного обеспечения для цифровых систем видеонаблюдения (http://nordavind.ru/node/118).
Насчет пересмотра архитектуры приложения Вы совершенно правы! И в новой версии софта эта архитектура существенно пересмотрена в сторону уменьшения числа потоков за счет выполнения большинства некритичных (non-real-time) операций последовательно в рамках неких eventloop-ов. Количество потоков уменьшилось, сопровождение упростилось, но систему все равно трудно назвать простой или маленькой:)
Но в любом случае перед нами стоит и будет еще несколько лет стоять задача сопровождения и легкой докрутки старой версии софта, которая благополучно эксплуатируется на многих объектах. Там за архитектурные недоработки приходится отвечать сполна.
Насчет пересмотра архитектуры приложения Вы совершенно правы! И в новой версии софта эта архитектура существенно пересмотрена в сторону уменьшения числа потоков за счет выполнения большинства некритичных (non-real-time) операций последовательно в рамках неких eventloop-ов. Количество потоков уменьшилось, сопровождение упростилось, но систему все равно трудно назвать простой или маленькой:)
Но в любом случае перед нами стоит и будет еще несколько лет стоять задача сопровождения и легкой докрутки старой версии софта, которая благополучно эксплуатируется на многих объектах. Там за архитектурные недоработки приходится отвечать сполна.
Почему то я сразу так и подумал :) Даже не заглядывая в ваш профиль)
Какое-то время тоже работал в компании занимающейся видеонаблюдением, анализом видеоданных и комплексными системами безопасности. Там проблема многопоточности решалась с помощью потокобезопасных очередей и все модули между собой общались через сигал-слот подобный механизм. Рядовой программист, который работал например над распознаванием видео и ему не надо было вносить какие-либо изменения в ядро, вообще не задумывался как оно там все внутри устроено, какие модули в каких потоках работают и т.д.
Какое-то время тоже работал в компании занимающейся видеонаблюдением, анализом видеоданных и комплексными системами безопасности. Там проблема многопоточности решалась с помощью потокобезопасных очередей и все модули между собой общались через сигал-слот подобный механизм. Рядовой программист, который работал например над распознаванием видео и ему не надо было вносить какие-либо изменения в ядро, вообще не задумывался как оно там все внутри устроено, какие модули в каких потоках работают и т.д.
А здорово вы перевели проблему синхронизации в топологию. Очень интересная аналогия, хотелось бы продолжения банкета.
Спасибо за интерес! Следующий пост сделаем по ситуациям блокировок с сигнальными переменными, ну и конечно, дадим практические рекомендации, как их не допускать.
Модель действительно получилась неплохая, а самое главное, наглядная. Но тут надо понимать, что в конечном счете эта модель описывается достаточно суровой математикой, иначе просто оказалось невозможно построить непротиворечивые доказательства.
Модель действительно получилась неплохая, а самое главное, наглядная. Но тут надо понимать, что в конечном счете эта модель описывается достаточно суровой математикой, иначе просто оказалось невозможно построить непротиворечивые доказательства.
Идеально было бы, если бы этот граф строился и анализировался автоматически.
Автоматический анализ графа — задача вполне решаемая и у нас есть небольшой инструмент, которым мы такой анализ проводим. Нужно понимать, конечно, что полным перебором на модели реальной мало-мальски большой системы (сотни потоков, десятки средств синхронизации) такой обсчет займет недели даже на современной технике. Вобщем, алгоритм анализа со всеми его оптимизациями — потенциальная тема для еще одного поста:)
Что касается автоматического построения модели (графа), то как уже писал выше, мы строим ее по run-time маршрутам, жертвуя, конечно, при этом полнотой модели. Но в случае deadlock-ов лучше так, чем никак вообще.
Построение по исходникам — идеальный вариант, но нереализуемый в случае наших сильно компонентных систем, собирающихся в единую программу в run-time на основе xml-ки, описывающей порядок загрузки компонентов.
Что касается автоматического построения модели (графа), то как уже писал выше, мы строим ее по run-time маршрутам, жертвуя, конечно, при этом полнотой модели. Но в случае deadlock-ов лучше так, чем никак вообще.
Построение по исходникам — идеальный вариант, но нереализуемый в случае наших сильно компонентных систем, собирающихся в единую программу в run-time на основе xml-ки, описывающей порядок загрузки компонентов.
Спасибо, было интересно, продолжайте!
Кажется, что если второе правило соблюдается, то первое правило не нужно. Не важно в каком порядке отпускать блокировки (потому что отпускание блокировки никогда не блокируется), если берутся они всегда в одном и том же порядке.
Первое правило, больше подстраховка от случая, когда вы будите выполнять вот так: L1 — L2 — U1 — L1 — … Если строго придерживаться правила, что захват всегда в одном и том же порядке, то т.к. у вас уже захвачен L2, вы не имеете права захватывать L1. Но, кто же об этом будет помнить. Поэтому и вводится правило об освобождении в порядке обратном захвату.
Мне приходится много работать с многопточным кодом из явы и конечно неприятностей избежать этими 2мя простыми правилами не выходит.
Во первых зависимости не обязаны быть мутексами, это могут быть абсолютно разнообразные межнитевые взаимодействия, скажем спинлоки, может просто волатильный флаг стоять как такой барьер.
Дальше, даже один поток может сам себя залочить, хотя формально это и не дедлок. Скажем если тред разбирающий очередь попытается блокирующе записать в нее же, а она полна.
Дальше, есть проблемы с сторонним кодом или со своим же кодом, но других уровней. Скажем нам надо вызвать некий листенер несколько раз не допустив реордеринга. Для этого обычно все вызовы листенера оборачивают в локи. Но этот листенер ничего не знает об этом и могут быть сюрпризы. Скажем если на событие из сети мы вызывваем листенер, а он посылает нам назад команду послать чтото в сеть. Вот тут часто влетаешь в то, что листенер был вызван под тем же локом, который требуется для того, чтобы чтото послать. А то сложно гарантировать порядок транспортной библиотеке. Ну вот это тоже готовый дедлок.
Сильно упрощает ситуацию с дедлокам паттерн с перекидыванием команд в сингл тред. Шанс словить бяк резко падает, на практике. Все тяжелые операции можно кидать в тредпулы через теже очереди. Если аккуратно прописать тред модель, резко упрощает разработку.
Также хорошо работает правило, никогда не вызывать «чужой» код под своими локами. Реордеринг тут увы придется решать скажем сиквенс намберами.Опять же, вшнешние либы не перепишешь.
Так же есть финт, с превращением дедлоков в лив локи. То есть по таймауту из ожидания лока вываливаться, ресетить транзакцию и с небольшой паузой попытаться еще раз. Тут дедлок превращается в приличную потерю по перформансу, так что стоит мониторить кол-во таких вот откатов и следить, что их немного. Но обычно это всеже лучше.
Тут еще такой момент, можно при вызове некоего кода, которые требует лок2 из кода который требует лок1 можно делать в другом потоке. Скажем, отдать в некий тред команду на исполнение. Но тут это неизбежно отсроченные вызов и легко может привести к ситуации, когда вместо дедлока мы получаем OOME, если же сделать очередь конечной то в момент ее заполненности у нас 2 варианта. Либо выбросить задачу нафиг с ошибкой в лог, либо ждать. Второе очевидно опять же может привести к дедлоку.
Также с дедлоками проблема, что они часто незаметны. Ну померло пару тредов в тредпуле, все вроде и работает. Т.е. полезно мониторить такие ситуации. В яве скажем можно следить, чтобы поток долго в блокинг не проводил. Но вообще-то проще всего пытатся захватить всевозможные локи в отдельном потоке и еще одним потоком мониторить, не сдох ли первый. Проблема тут опять же, что способов завязаться на другой тред довольно много и сложно отследить все.
В общем, можно про дедлоки долго писать, тема богатая.
Во первых зависимости не обязаны быть мутексами, это могут быть абсолютно разнообразные межнитевые взаимодействия, скажем спинлоки, может просто волатильный флаг стоять как такой барьер.
Дальше, даже один поток может сам себя залочить, хотя формально это и не дедлок. Скажем если тред разбирающий очередь попытается блокирующе записать в нее же, а она полна.
Дальше, есть проблемы с сторонним кодом или со своим же кодом, но других уровней. Скажем нам надо вызвать некий листенер несколько раз не допустив реордеринга. Для этого обычно все вызовы листенера оборачивают в локи. Но этот листенер ничего не знает об этом и могут быть сюрпризы. Скажем если на событие из сети мы вызывваем листенер, а он посылает нам назад команду послать чтото в сеть. Вот тут часто влетаешь в то, что листенер был вызван под тем же локом, который требуется для того, чтобы чтото послать. А то сложно гарантировать порядок транспортной библиотеке. Ну вот это тоже готовый дедлок.
Сильно упрощает ситуацию с дедлокам паттерн с перекидыванием команд в сингл тред. Шанс словить бяк резко падает, на практике. Все тяжелые операции можно кидать в тредпулы через теже очереди. Если аккуратно прописать тред модель, резко упрощает разработку.
Также хорошо работает правило, никогда не вызывать «чужой» код под своими локами. Реордеринг тут увы придется решать скажем сиквенс намберами.Опять же, вшнешние либы не перепишешь.
Так же есть финт, с превращением дедлоков в лив локи. То есть по таймауту из ожидания лока вываливаться, ресетить транзакцию и с небольшой паузой попытаться еще раз. Тут дедлок превращается в приличную потерю по перформансу, так что стоит мониторить кол-во таких вот откатов и следить, что их немного. Но обычно это всеже лучше.
Тут еще такой момент, можно при вызове некоего кода, которые требует лок2 из кода который требует лок1 можно делать в другом потоке. Скажем, отдать в некий тред команду на исполнение. Но тут это неизбежно отсроченные вызов и легко может привести к ситуации, когда вместо дедлока мы получаем OOME, если же сделать очередь конечной то в момент ее заполненности у нас 2 варианта. Либо выбросить задачу нафиг с ошибкой в лог, либо ждать. Второе очевидно опять же может привести к дедлоку.
Также с дедлоками проблема, что они часто незаметны. Ну померло пару тредов в тредпуле, все вроде и работает. Т.е. полезно мониторить такие ситуации. В яве скажем можно следить, чтобы поток долго в блокинг не проводил. Но вообще-то проще всего пытатся захватить всевозможные локи в отдельном потоке и еще одним потоком мониторить, не сдох ли первый. Проблема тут опять же, что способов завязаться на другой тред довольно много и сложно отследить все.
В общем, можно про дедлоки долго писать, тема богатая.
Если позволите, я в ответ напишу лишь несколько тезисов, коль скоро, вопросов Вы не задали, а просто поделились тем, как тяжело жить программисту многопоточных приложений:)
1. Данный пост рассматривает программы, в которых вся синхронизация выстроена на мьютексах. Тогда соблюдения этих двух правил достаточно, чтобы не знать проблем.
2. При всем многообразии названий средств синхронизации на разных платформах (windows/mac.linux/др), разных языках программирования, разном уровне программирования (user/kernel) все они могут быть отнесены к простой классификации
3. Правилам использования других средств синхронизации я посвящу отдельный пост.
Но! Даже знание этих правил не всегда помогает, т.к. возможны такие архитектурные коллизии, при которых нельзя не нарушить правила, чтобы при сохранении общей архитектуры программы обеспечить требуемую функциональность. В этом случае выход один — менять архитектуру во имя исключения потенциальной ситуации взаимной блокировки.
1. Данный пост рассматривает программы, в которых вся синхронизация выстроена на мьютексах. Тогда соблюдения этих двух правил достаточно, чтобы не знать проблем.
2. При всем многообразии названий средств синхронизации на разных платформах (windows/mac.linux/др), разных языках программирования, разном уровне программирования (user/kernel) все они могут быть отнесены к простой классификации
3. Правилам использования других средств синхронизации я посвящу отдельный пост.
Но! Даже знание этих правил не всегда помогает, т.к. возможны такие архитектурные коллизии, при которых нельзя не нарушить правила, чтобы при сохранении общей архитектуры программы обеспечить требуемую функциональность. В этом случае выход один — менять архитектуру во имя исключения потенциальной ситуации взаимной блокировки.
В Яве все сильно сложнее, примитивов синхронизации очень много и некоторые довольно навороченные.
В ответ приведу фрагмент нашего исследования (такой у нас есть по всем распространенным платформам и языкам). Данные по средствам синхронизации 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 – критическая секция.
Представляет собой нерекурсивный исключающий семафор (может быть блокирующий или неблокирующий).
Все перечисленное прекрасно укладывается в приведенную выше классификацию. Если что-то забыл, пишите — будем разбираться;)
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 – критическая секция.
Представляет собой нерекурсивный исключающий семафор (может быть блокирующий или неблокирующий).
Все перечисленное прекрасно укладывается в приведенную выше классификацию. Если что-то забыл, пишите — будем разбираться;)
Так непривычно читать русские переводы явовских примитивов синхронизации, особенно:
— Замок (Lock)
— Рекурсивный замок чтения/записи (ReentrantReadWrite lock)
— Переменная кондиции (Condition)
— Защелка обратного отсчета (CountDownLatch)
:)
— Замок (Lock)
— Рекурсивный замок чтения/записи (ReentrantReadWrite lock)
— Переменная кондиции (Condition)
— Защелка обратного отсчета (CountDownLatch)
:)
Ну это не совсем так. Все высокоуровневые примитивы в конечном итоге упирается в Unsafe.park().
Дальше, кроме директивы synchronized есть еще wait и Thread.sleep. Дальше, локи между потоками могут подниматься в нативном коде и это довольно частая ситуация. Кроме того, есть еще спин-лок, когда живой тред крутит касы, пока не получится. То есть даже задиагностировать на живой системе по тред дампу ситуацию дедлока довольно сложно. Так же, всегда можно придумать высокоуровневый примитив, который будет подвисать совершенно неожиданным образом. Например, поток который будет периодически просыпаться, но проверять какие-то условия и снова засыпать, технически это будет live-lock, но по сути дедлок, ибо потоки будут почти все время спать. Например, некая задача просто лежит в очереди в тред пул, но изза нечестной очереди, она никогда не будет этим тредпулом обработана. Формально эта задача вообще не имеет никаких технчиеских блокировок, а на деле она может создать одно из ребер дедлока. Скажем, если она состоит из нескольких частей и одна из частей возьмет лок. Это я к тому, что даже задача диагностики реального дед лока на живой системе крайне нетривиальна.
Дальше, кроме директивы synchronized есть еще wait и Thread.sleep. Дальше, локи между потоками могут подниматься в нативном коде и это довольно частая ситуация. Кроме того, есть еще спин-лок, когда живой тред крутит касы, пока не получится. То есть даже задиагностировать на живой системе по тред дампу ситуацию дедлока довольно сложно. Так же, всегда можно придумать высокоуровневый примитив, который будет подвисать совершенно неожиданным образом. Например, поток который будет периодически просыпаться, но проверять какие-то условия и снова засыпать, технически это будет live-lock, но по сути дедлок, ибо потоки будут почти все время спать. Например, некая задача просто лежит в очереди в тред пул, но изза нечестной очереди, она никогда не будет этим тредпулом обработана. Формально эта задача вообще не имеет никаких технчиеских блокировок, а на деле она может создать одно из ребер дедлока. Скажем, если она состоит из нескольких частей и одна из частей возьмет лок. Это я к тому, что даже задача диагностики реального дед лока на живой системе крайне нетривиальна.
С чем соглашусь, так это с тем, что возможны алгоритмические локи, когда программа крутится где-то в ожидании чего-то, что алгоритмически никогда не наступит. Это отдельная сложная задача — верификация алгоритмов. Но это далеко от классического понимания deadlock-a…
Не скажу за других, но в Яве все локи такие, они довольно сложные и алгоритмические. Поэтому тут нет существенной разницы со «своим» алгоритмом. Наружу он точно также может выглядеть базовым перимитивом, а внутри иметь очень неочевидную логику. Тот же synchronized имеет очень много ньюансов и режимов работы, которые еще и конфигурируются на уровне JVM.
Дальше, есть еще одна проблема. Скажем, нас вызывает некая библиотека, чужой код, как коллбек. Причем, коллбек вызывает под своим локом. А надо вызвать эту библиотеку с неким ответом, причем этот вызов идет под тем же самым локом. Причем, поток в котором вызывается коллбек не наш, а чужой и его надо побыстрее освободить, то есть библиотеку вызывать должен другой (наш) поток. Но, также требуется, чтобы наши вызовы с ответом должны идти в томже самом порядке, что и их нашего коллбека. И все это должно иметь фиксированные ограничения по памяти, чтобы не схлопотать под нагрузкой ООМ.
Я вот просто не знаю решения этой задачи в принципе. Всегда приходится чемто пожертвовать, либо остается некий шанс на дедлок, либо всегда можно представить сценарий, когда любые (конечные) требования по памяти будут нарушены.
Я вот просто не знаю решения этой задачи в принципе. Всегда приходится чемто пожертвовать, либо остается некий шанс на дедлок, либо всегда можно представить сценарий, когда любые (конечные) требования по памяти будут нарушены.
Тут рецепт только один — не надо смешивать свои блокировки с блокировками внешних (тем более закрытых) библиотек. Если мы не можем их учесть в нашей модели, а следовательно, не можем гарантировать потокобезопасность использующего их кода, то надо их «гальванически развязать», например, через какую-нибудь очередь, наполняемую сторонней библиотекой, а вычитываемой нашей программой. Так мы четко локализуем место соприкосновения нашего прекрасного кода с небезопасным сторонним:)
С очередью, как я уже дважды писал есть проблема с неконтролируемым ее ростом и ограниченной памятью. А притормозить листенер, если очередь полна чревато как раз таки дедлоком по вышеописанной схеме. Сделать, как я понимаю, тут принципиально ничего нельзя в общем случае.
Проблема всех очередей всегда состоит в том, что, если на другом конце ее не успевают опустошать также интенсивно, как набивают на другом, то в какой-то момент придется что-нибудь drop-нуть;)
Не совсем. Более цивилизованный способ это както донести этой библиотеке, что мы не справляемся. Както ее притормозить. Обычно для этого просто подвешивают листенер, а дальше часто этой библиотеке проще както дропнутые данные восстановить. Скажем перезапросить из сети или еще как. Но вот есть и обратка такая, в виде шанса на дедлок.
Причем, беда в том, что тут ничего и не придумать лучше. Я вот дедлоки не люблю, поэтому листенеры неизбежно могут вызывать одновременно, переставленные итп. Ну либо дизайнить эти локи очень аккурартно, чтобы гарантировать, что их можно получить лишь предсказуемыми трассами и снаружи никто до них доступится не сможет. Это редко удается. Да и еще реже удается поработать с чужим кодом настолько продуманным.
Я пришел к выводу, что дедлоки неизбежны, а избыточная борьба с ними, просто делает код сложнее в поддержке. Значительно сложнее. Взаимодействие между уровнями превращается просто в яростную боль. Еще не придумал идеальную стратегию, но если приложение живет не больше недели-месяца, то проще просто детектировать такие ситуации и поднимать резервные потоки для той же логики. Вот только, как я выше писал, даже с детектированием таких патологий есть сильные проблемы. Ну, или действительно дропать, тоже вариант. Тем более, что как правило потерянное данное можно таки восстановить и пересчитать. Но тут очень уже важен мониторинг, чтобы эти ситуации оставались редкими исключениями.
Ну и разумен вариант, когда каждый слой приложения имеет 3 звена. Для инпута, для аутпута и собсна бизнесс логики. И все три звена обязаны иметь независимые потоки. Не снимает проблему дедлоков (или как вы верно написали дропов) полностью, но значительно снижает такие риски. Но и цену имеет значительную.
Причем, беда в том, что тут ничего и не придумать лучше. Я вот дедлоки не люблю, поэтому листенеры неизбежно могут вызывать одновременно, переставленные итп. Ну либо дизайнить эти локи очень аккурартно, чтобы гарантировать, что их можно получить лишь предсказуемыми трассами и снаружи никто до них доступится не сможет. Это редко удается. Да и еще реже удается поработать с чужим кодом настолько продуманным.
Я пришел к выводу, что дедлоки неизбежны, а избыточная борьба с ними, просто делает код сложнее в поддержке. Значительно сложнее. Взаимодействие между уровнями превращается просто в яростную боль. Еще не придумал идеальную стратегию, но если приложение живет не больше недели-месяца, то проще просто детектировать такие ситуации и поднимать резервные потоки для той же логики. Вот только, как я выше писал, даже с детектированием таких патологий есть сильные проблемы. Ну, или действительно дропать, тоже вариант. Тем более, что как правило потерянное данное можно таки восстановить и пересчитать. Но тут очень уже важен мониторинг, чтобы эти ситуации оставались редкими исключениями.
Ну и разумен вариант, когда каждый слой приложения имеет 3 звена. Для инпута, для аутпута и собсна бизнесс логики. И все три звена обязаны иметь независимые потоки. Не снимает проблему дедлоков (или как вы верно написали дропов) полностью, но значительно снижает такие риски. Но и цену имеет значительную.
> Не совсем. Более цивилизованный способ это както донести этой библиотеке, что мы не справляемся. Както ее притормозить. Обычно для этого просто подвешивают листенер, а дальше часто этой библиотеке проще както дропнутые данные восстановить. Скажем перезапросить из сети или еще как.
Т.е. предлагаете, чтобы сама библиотека drop-нула то, что вы не успеваете обрабатывать?:)
> Я пришел к выводу, что дедлоки неизбежны, а избыточная борьба с ними, просто делает код сложнее в поддержке.
Простите, я адепт другой веры;) Я считаю, что дедлоки недопустимы и даже если существует лишь потенциальная угроза их возникновения при какой-то невероятной динамике, то с этой потенциальной ситуацией уже надо бороться!
Т.е. предлагаете, чтобы сама библиотека drop-нула то, что вы не успеваете обрабатывать?:)
> Я пришел к выводу, что дедлоки неизбежны, а избыточная борьба с ними, просто делает код сложнее в поддержке.
Простите, я адепт другой веры;) Я считаю, что дедлоки недопустимы и даже если существует лишь потенциальная угроза их возникновения при какой-то невероятной динамике, то с этой потенциальной ситуацией уже надо бороться!
А почему порядок отпускания важен? (первое правило)
Допустим на множестве мьютексов определено отношение строгово порядка.
Пусть L — множество блокировок, удерживаемых потоком в настоящий момент.
Утверждается, что допустимо захватывать любой мьютекс, который следует после всех мьютексов в L согласно используемому отношению, а порядок отпускания не важен.
Допустим на множестве мьютексов определено отношение строгово порядка.
Пусть L — множество блокировок, удерживаемых потоком в настоящий момент.
Утверждается, что допустимо захватывать любой мьютекс, который следует после всех мьютексов в L согласно используемому отношению, а порядок отпускания не важен.
Все верно. Этот вопрос уже поднимался чуть выше, поэтому процитирую:
> Первое правило, больше подстраховка от случая, когда вы будите выполнять вот так: L1 — L2 — U1 — L1 — … Если строго придерживаться правила, что захват всегда в одном и том же порядке, то т.к. у вас уже захвачен L2, вы не имеете права захватывать L1. Но, кто же об этом будет помнить. Поэтому и вводится правило об освобождении в порядке обратном захвату.
> Первое правило, больше подстраховка от случая, когда вы будите выполнять вот так: L1 — L2 — U1 — L1 — … Если строго придерживаться правила, что захват всегда в одном и том же порядке, то т.к. у вас уже захвачен L2, вы не имеете права захватывать L1. Но, кто же об этом будет помнить. Поэтому и вводится правило об освобождении в порядке обратном захвату.
спасибо, тема интересна,
ждем продолжения про условные переменные
ждем продолжения про условные переменные
Продолжение можно прочитать здесь.
Так Вы непосредственно в самой статье укажите ссылку на продолжение.Почему-то уверен, что комментарий потеряется
Спасибо! Так и сделал,
Про юзабилити: название ссылки «здесь» ни о чем не говорит и лучше называть статьей. Лаконичное и ясное название ссылки даст возможность читателю быстрее принять решение стоит ли ему переходить по ссылке. + ко всему, если Вы планируете писать цикл статей, то рекомендую указывать и номер статьи в этом цикле. Это позволит быстрее ориентироваться по прочитанному циклу.
Спасибо! Отличная статья, отличные правила.
Скажите, может вы знаете решение покрасивее для задачи с двумя мьютексами A и B:
Поток типа 1 должен захватить мьютекс A, совершить какую-то работу и захватить мьютекс B, не отпуская A, совершить работу и отпустить оба мьютекса
Поток типа 2 должен захватить мьютекс B, проверить условия и в зависимости от результатов проверки возможно потребуется захватить и мьютекс A
Потоков типа1 и типа2 может быть сколько угодно. Производительность критична. Есть что-нибудь лучше, чем в потоке типа 2 сразу захватывать мьютексы A и B?
Скажите, может вы знаете решение покрасивее для задачи с двумя мьютексами A и B:
Поток типа 1 должен захватить мьютекс A, совершить какую-то работу и захватить мьютекс B, не отпуская A, совершить работу и отпустить оба мьютекса
Поток типа 2 должен захватить мьютекс B, проверить условия и в зависимости от результатов проверки возможно потребуется захватить и мьютекс A
Потоков типа1 и типа2 может быть сколько угодно. Производительность критична. Есть что-нибудь лучше, чем в потоке типа 2 сразу захватывать мьютексы A и B?
Если задача ставится именно так, как описано в Вашем комментарии, то ничего «покрасивее» придумать нельзя — мьютексы надо захватывать обязательно в одном порядке во всех потоках и никак иначе. Решение можно попробовать поискать в другой плоскости, проанализировав прикладную задачу, можно попытаться уйти от проектного решения, когда требуется захватывать мьютексы в разном порядке в разных потоках.
На самом деле, захват мьютекса не так уж критичен с точки зрения производительности. Вряд ли весь остальной код настолько вылизан и оптимизирован, чтоб был заметен захват мьютекса:) Хотя, тут Вам виднее.
На самом деле, захват мьютекса не так уж критичен с точки зрения производительности. Вряд ли весь остальной код настолько вылизан и оптимизирован, чтоб был заметен захват мьютекса:) Хотя, тут Вам виднее.
Sign up to leave a comment.
Два простых правила для предотвращения взаимных блокировок на мьютексах