Комментарии 14
На этапе статического анализа исходного кода или компиляции.
В рантайме.
Есть ещё такой "промежуточный" способ, как: deadlock-free model + runtime проверка соответствия программы модели (разумеется имеет смысл если проверка имеет преимущество перед поиском циклов в RAG \ WFG).
Любопытно. А есть ссылка с более подробным описанием / пример продукта с таким подходом?
В основном это гуглится по lock global order (+ какие-то дополнительные условия, поскольку сам lock global order - это слишком строгая и весьма простая модель).
Когда занимался этим были и другие (кроме lock global order) модели, но нам не подошли.
ПС
Вот ссылка (судя по абстракту примерно то, статью не читал): делают глобальный порядок на блокировках и доказывают что благодаря этому всё хорошо.
https://link.springer.com/chapter/10.1007/978-3-642-11957-6_22
Автору - в сообщении о дедлоке неправильно писать "1970256th", так как это не порядковый номер потока, а просто некий сгенерированный id.
Как видно, для защиты доступа к графу используется обычный Lock
Не получится-ли так, что порядок исполнения кода, использующего SmartLock'и с этим вот обычным локом в глобальном графе зависимостей, окажется через него дополнительно синхронизированным/упорядоченным на глобальном уровне? Если так, то это существенно меняет поведение программы вцелом (как если бы вы хотели записаться к парикмахеру, но теперь вынуждены ждать пока это сделают все остальные во всех парикмахерских вашего города).
Значимо влиять не должно.
1. SmartLock не задает порядок, в котором его берут потоки, он лишь сохраняет его. Пока один поток берет блокировку, остальные, которые тоже хотели взять или отпустить любую другую блокировку, подвисают. Однако тот порядок, в котором они подвисли и потом выйдут из глобальной блокировки, остается нетронутым.
2. Многопоточные программы обычно пишутся с учетом, что другие потоки относительно данного могут выполнять свои задачи в любом порядке, если только мы не решим их дополнительно синхронизировать. Любой спонтанный порядок в соседних потоках, даже если он каким-то чудом возникнет (а не должен), входит во множество "любой порядок", а значит не должен оказаться неожиданностью. Он будет эквивалентен редкой флуктуации в поведении других потоков, то есть является в принципе ожидаемым поведением.
К слову, в CPython используется GIL — очень похожая сущность. На семантику многопоточного программирования она практически никак не влияет, только на производительность.
К слову, в CPython используется GIL — очень похожая сущность. На семантику многопоточного программирования она практически никак не влияет, только на производительность.
В самом деле, ваше решение похоже на GIL, ну или этакий conditional brake point в дебагере при отладке многопоточного кода (просто в другом масштабе времени). Если бы это ни как не влияло не семантику, то GIL был бы уже давно выпилен в угоду производительности, а отладка многопоточного кода была приятным времяпрепровождением.
Я не критикую саму идею, просто хочу обратить внимание на сайд эффект у конкретной реализации (будь здесь все настолько просто, этот подход был уже реализован за 30 лет развития питона, хотя бы даже в отладочных целях).
Я видел реализации WFG в других языках, плюс этот подход активно используется в сложных многопоточных системах типа СУБД. Так что, мне кажется, причина отсутствия реализации на Python за 30 лет заключается в чем-то другом. Моя гипотеза: из-за ограничений интерпретатора питонисты крайне редко используют многопоточность, и в среднем понимают ее хуже, чем программисты на других языках. Поэтому некоторые элементы инфраструктуры находятся просто в зачаточном состоянии.
Библиотека threading одна из старейших в питоне, так что проблема не в отсутствии понимания. Интересную точку зрения на многопоточность, чисто на уровне архитектуры, высказал Raymond Hettinger в своем докладе https://m.youtube.com/watch?v=9zinZmE3Ogk. tldr; это интересно только геймерам).
Условно есть две модели работы с многопоточностью: shared memory и message passing. Исторически так сложилось, что модуль threading в основном ориентирован на первую, а multiprocessing на вторую (сюда же относится новомодный async/await). Написать приложение, корректно работающее в условиях первой модели это крайне нетривиальная задача - вам надо обеспечить глобальную согласованность всех актов, которые локально могут творить любую дичь, находясь в общем контексте. Даже если у вас это получится, то какое-то локальное изменение, глобальные последствия которого сложно отследить на код ревью, может все легко поломать.
Соблюдая определенную дисциплину, можно писать thead-safe код. Например стараться не использовать глобальное состояние вообще (но это как бы противоречит основной идее, зачем вообще были нужны были потоки). Либо использовать lock-free структуры данных, CRDT и т.п. трюки, что не является мейнстримом. Тем не менее все это можно позволить себе, находясь в рамках одного конкретного приложения, с четко описанными архитектурными ограничениями и компромиссами. Но такой подход не работает в общем случае, иначе проблема с deadlock'ами решалась бы на уровне операционной системы или стандартных библиотек.
Как в случае с парикмахерскими города, в исходной модели у каждого Lock своя очередь ожидания. Они ни чего не знают друг про друга и ни как не синхронизированы. Поэтому народ идёт толпами. Но есть вероятность, что кто-то из посетителей запишется в разные на одно и то же время, чем вызовет неминуемый простой у остальных. Вводя глобальный лок для синхронизации общего реестра (читай - общую очередь), вы тем самым увеличиваете время отклика. Самые нетерпеливые посетители начнут отваливается так и не дождавшись ответа, чего в нормальных условиях бы не происходило.
Возможно в условиях ваших тестов эффект не заметен. Но это не значит, что в подходе отсутствуют негативные эффекты. Вопрос лишь вероятности и масштаба, когда проблему получится стабильно воспроизвести.
Насколько я знаю, WFG используются в т.ч. и на уровне OS, для разного рода ресурсов.
Про задержки согласен, но в чем здесь собственно отличие от моего поинта про производительность? Она да, проседает, потоки начинают больше ждать. Однако я не вижу, как это аффектит собственно семантику программы. Крайне нежелательно писать программу, как-то закладываясь на продолжительность этих задержек, и учитывая их в коде. А иного влияния, кроме как на продолжительность этих задержек, я не вижу.
Замечу, что цикл в Resource Allocation Graph => WFG создаётся не только на mutex но и на других способах синхронизации.
1 Чтобы предотвратить deadlock надо учесть ещё:
1.а) другие примитивы синхронизации
1.б) блокирующие системные вызовы (мы, к стати ловили такой deadlock - блокирующий системный вызов в потоке A, завершению которого мешал другой поток B захвативший ресурс и уснувший на mutex захваченном потоком A).
2. Есть ещё livelock и livelock-like проблема: у вас может быть ещё и самописная синхронизация, типа активного ожидания события. Тут вообще сложно и 8 лет назад были только частные решения:
2.а) Если такое ожидание не завязано на бизнес-логику (а только на техническую, изолируемую часть) - называете эту функцию "ожиданием на примитиве" и включаете её в вашу модель (у вас - детекция циклов в WFG), с соответствующими обёртками.
2.б) Если такое ожидание завязано на всю вашу безнес-логику - то это уже другая высокоуровневая модель синхронизации по избеганию livelock ну и соответственно тема другой статьи (цикла статей) на хабре.
Согласен, за пределами мьютексов есть еще куча способов словить дедлок. Я бы в ваш список добавил еще дедлоки в распределенных системах.
Если вдруг решите написать об этом статью - я бы почитал с удовольствием.
Если вдруг решите написать об этом статью - я бы почитал с удовольствием.
Это было на предыдущей работе, сейчас уже техническую часть не собрать. А "общие рассуждения" - их в интернете и без меня полно.
Я бы в ваш список добавил еще дедлоки в распределенных системах.
Да согласен.
Раз уж зашла об этом речь (проверка высокоуровнего состояния на отсутствие блокировок) - вы не знаете ПО, для представления \ верификации небольших протоколов и\или state-machine (на 10-20 переменных состояния)?
Многопоточный Python на примерах: избавляемся от дедлоков