L>Не нужно стараться уменьшать количество используемых мьютексов, мьютексы дешевы, захватываются и освобождаются очень быстро (uncontended lock/unlock мьютекса, находящегося в кэше это десяток наносекунд, если мне память не изменяет, деление 2х интов — дороже), если какой-то код/структуру данных можно сделать потокобезопасной, то часто так и нужно сделать, а потом уже узкие места, в которых может оказаться, что следующее неверно:
Здравствуйте, Lazin, Вы писали:
L>>1. Можно ли обойтись без лока? L>Не нужно стараться уменьшать количество используемых мьютексов,
Нужно. Больше количество мьютексов дают банально больше возможностей для возникновения лока.
L>мьютексы дешевы, захватываются и освобождаются очень быстро (uncontended lock/unlock мьютекса, находящегося в кэше это десяток наносекунд, если мне память не изменяет, деление 2х интов — дороже), если какой-то код/структуру данных можно сделать потокобезопасной, то часто так и нужно сделать, а потом уже узкие места, в которых может оказаться, что следующее неверно:
L>>3. Как минимизировать длительность лока? Желательно до одной операции?
L>Uncontended lock — очень дешев, contended lock — дорог.
Совершенно верно. Но все же рассматривать дороговизну этого лока как такового — это все равно, что жалеть гвоздей на постройку дома. Основной негативный эффект от contended lock заключается вовсе не во внутренней кухне мьютекса, а в вынужденном простое одного или нескольких потоков. Поэтому и нужно стремиться к тому, чтобы максимально меньшее время проводить под локом, чтобы снизить вероятность contended lock.
L>Пример — мы обрабаываем данные в цикле, лок захватывается на каждой итерации на короткое время (несколько сотен наносекунд). Можно захватывать его не на каждой итерации а на каждые N итераций. С ростом N мы будем платить все меньше и меньше за синхронизацию, но при привышении определенного порога — это может начать сказываться на производительности отрицательно.
А почему нельзя одним махом передать сразу все данные для обработки в поток? Один swap и никаких гвоздей. Зачем лочить на каждой итерации? Взял данные, обработал, как закончил — сообщил. Какой юзкейс?
L>2. uncontended lock (мьютекс используется эксклюзивно, одним потоком) захватывать мьютекс часто — сравнительно не дорого, но если мы будем его также захватывать на более длительный интервал времени, то ничего страшного не произойдет, так как поток большую часть времени все равно владеет им в единоличном порядке.
Мьютекс, используемый лишь одним потоком — это какой-то pkunzip.zip.
L>Нужно. Больше количество мьютексов дают банально больше возможностей для возникновения лока.
Какбэ наоборот же чем больше мьютексов, тем меньше шансов что какие-то из них образуют цикл. Чисто с точки зрения теории вероятностей Когда все используют 2 мьютекса, то любой захват в неверном порядке будет приводить к реальному deadlock-у.
L>>мьютексы дешевы, захватываются и освобождаются очень быстро (uncontended lock/unlock мьютекса, находящегося в кэше это десяток наносекунд, если мне память не изменяет, деление 2х интов — дороже), если какой-то код/структуру данных можно сделать потокобезопасной, то часто так и нужно сделать, а потом уже узкие места, в которых может оказаться, что следующее неверно:
L>>>3. Как минимизировать длительность лока? Желательно до одной операции?
L>>Uncontended lock — очень дешев, contended lock — дорог.
L>Совершенно верно. Но все же рассматривать дороговизну этого лока как такового — это все равно, что жалеть гвоздей на постройку дома. Основной негативный эффект от contended lock заключается вовсе не во внутренней кухне мьютекса, а в вынужденном простое одного или нескольких потоков. Поэтому и нужно стремиться к тому, чтобы максимально меньшее время проводить под локом, чтобы снизить вероятность contended lock.
Ну это может быть, например, очередь, в которую поток кладет что-нибудь, для обработки другими потоками. Можно на каждое добавление лочить, можно залочить один раз на длительное время и добавить множество элементов.
L>>2. uncontended lock (мьютекс используется эксклюзивно, одним потоком) захватывать мьютекс часто — сравнительно не дорого, но если мы будем его также захватывать на более длительный интервал времени, то ничего страшного не произойдет, так как поток большую часть времени все равно владеет им в единоличном порядке.
L>Мьютекс, используемый лишь одним потоком — это какой-то pkunzip.zip.
Часто используемый в параллельном программировании паттерн — в fast path захватывается какой-нибудь спин лок, который большую часть времени захватывается только одним потоком, но периодически что-нибудь происходит и какой-нибудь другой поток может залочить этот мьютекс и вмешаться в работу первого потока. Task stealing scheduler может так работать, например. Это нужно для того, чтобы захват лока был почти бесплатным большую часть времени, но при этом нужно иметь возможность обращаться к данным их других потоков иногда.
Здравствуйте, Lazin, Вы писали:
L>(offtopic: очень сложно цитировать человека с ником, начинающимся с той же буквы что и твой)
L>>А вот тут — стоп. Когда я вызываю какой-то код под локом, это означает, что у меня есть потенциальное взаимодействие двух потоков. Если оказывается, что этот код может попытаться получить другой лок, это означает, что взаимодействие распространяется на потенциально неограниченное количество потоков. Это уже само по себе нонсенс и означает, что лок рано или поздно выстрелит. И заранее протестировать динамическую систему на гарантированное отсутствие лока в общем случаее невозможно.
L>Можно, если правильно ее проектировать. (тут должен быть очередной рассказ про иерархии блокировок)
Которые не нужны, если правильно ее проектировать
L>Еще раз — локов не должно быть мало, их должно быть столько, сколько нужно. Впялить мьютекс в каждый объект — нормальная практика.
Это как раз ненормальная, я бы даже сказал, порочная, практика. Вот впаяй мьютекс в map, только чур так, чтобы все алгоритмы работали.
L> Плохо не тогда, когда мьютексов слишком много, плохо становится тогда, когда их мало и они постоянно лочатся/анлочатся из нескольких ядер. Это называется lock contention. Плохо когда локи не организованы в иерархию и могут создать цикл (решается правильным проектированием). Все.
Иными словами, плохо, когда на архитектуру забили. О чем я и говорю
L>>Я одно время копал в этом направлении. Например, если у меня есть подозрение, что некий код содержит потенциальный дедлок, я могу специально организовать юнит-тест, который его вызовет. Но, в общем случае невозможно создать автотест, который будет гарантировать отсутствие дедлока.
L>В общем случае — нет, это сводится к "halting problem". Но у меня не общий случай, я спрашивал о том, как динамически проверить отсутствие циклов на уровне ***LockLayer-ов.
А я же продолжаю утверждать, что эта проблема не стоит того, чтобы ее решать, т.к. гораздо выгоднее решить более высокоуровневую проблему.
L>>Еще раз — я всегда пытаюсь сводить межпоточное взаимодействие исключительно к однонаправленному чтению или записи. Никаких графов вызовов, особенно в другие потоки, из-под локов быть не должно. Мое мнение — наличие такого графа есть признак ошибки проектирования.
L>"Пытаюсь" — подходящее для этого слово, жизнь многогранна
"Пытаюсь" тут скорее потому, что во время code review приходится брать тупые твердые предметы в руки.
L>>Извини. ИМХО это попытка псевдонаучным языком (ака сложно и непонятно) объяснить очевиднейший принцип образования дедлока, который сводится к банальному "цепочка блокировок закольцевалась". Вроде "изучения влияния слабополяризованного монохроматического излучения на изделия из сталепроката".
L>Я пытаюсь о конкретной задаче разговаривать, resource allocation graph — вполне конкретная вещь, которую используют для анализа этих самых "цепочек блокировок".
Предлагаю оставить анализ ученым. Они умные, пусть статьи пишут. А нам код потом поддерживать.
L>>А что, хеш без коллизий? Прямо так уж пара инструкций? А где сам граф хранится? L>Я же говорил уже что хэш с коллизиями. Разные объекты могут хэшироваться на один и тот же мьютекс, отсюда требование к отсутствию рекурсинвых блокировок.
Вот, уже создал себе проблему.
L>>Если же делать, как я обычно делаю, мютексов нужно считанное количество — по одному на каждую точку взаимодействия Один-три на всю систему. L>Ты сам себе противоречишь, то мьютексов должно быть мало — 1-3 (coarse grained locking),
При правильном проектировании никакого coarse grained locking не возникает. Вообще, обычно в правильной многопоточной системе много потоков работают, один ждет внешнего события или результатов. Взаимодействие сводится к коротким эпизодам обмена данными "выполни мне задачу Х" и "вот результаты работы задачи Y"
L>то они должны захватываться часто (fine grained locking). Может у меня сервер с 24-мя ядрами и гипертрейдингом, один-три лока на всю систему нужно использовать?
Если интрефейс, по которому поступают/уходят данные, один, то все в любом случае сведется к одному локу
Здравствуйте, landerhigh, Вы писали:
BFE>>Это как, если команды им следует посылать с разной (не кратной) частотой? Если команда не прошла в заданный промежуток времени, то начинать надо с команд инициализации, время выполнение которых существенно превышает необходимую скорость реакции. L>А в чем проблема? У тебя производительность даже скромного ARMa на десять порядков превышает скорость обмена по последовательному порту. Один тред тут запросто может обслужить несколько портов, а латентность на фоне скорости обмена по интрефейсу будет просто незаметна.
Ну так не в скорости проблема. Проблема в том, что в разные порты надо посылать команды с разными промежутками времени и ждать ответа тоже с разными интервалами.
L>>>и один тред, выдающий информацию во внешний мир — пульты, удаленные терминалы, веб-интрефейсы и так далее. BFE>>Если он один, то как он устроен? Он весит на ожидании пакета из сети или на ожидании пакета на отправку? L>Может, мне и систему за тебя сразу всю написать? Про неблокирующие сокеты слышал?
Неблокирующие сокеты тут ничего не меняют. Что делает нитка, когда нечего посылать и нечего принимать?
L>>>(правда, тогда непонятны требования к согласованности — ведь пока мотор не соизволит ответить, вы ему новую команду выдать не сможете, как ни извернитесь), BFE>>Т.е. вы хотите сказать, что это вообще не возможно? Если мотор не отвечает, значит он отсоединён. В этом случае остальные части системы должны игнорировать отсоединённое оборудование. L>А если мотор отвечает, но с бОльшей задержкой по сравнению с другими моторами?
А так и есть. Частота обмена командами разная с разными моторами.
L>>>то так и быть, на каждый мотор/группу моторов по отдельному потоку. BFE>>ура! L>чего ура-то? Максимум — один тред на один порт.
Это уже 4 потока. И ещё минимум один для взаимодействия с сетью. Но замечу, что этот, пятый поток, ничего не делает, если нет никаких установленных сетевых соединений.
L>>>Вот это и будет тот самый, классический "multiple producers — one consumer". BFE>>кто из них consumer, тот кто потребляет команды или тот, кто потребляет измеренные положения моторов? L>Один консьюмер — эта та часть, которая связывает этот винигрет с внешним миром. Потребляет положения, иногда отдает команды. Потребитель услуг моторов.
Ок. С помощью каких объектов происходит этот обмен?
L>>>Я надеюсь, что вы не напрямую управляете шаговыми моторами из non-realtime OS? Через контроллер ведь, так? Или вы пытаетесь быть этим самым контроллером? BFE>>Я пишу/читаю в несколько последовательных портов, точнее 4 — три группы моторов + пульт управления. Со стороны моторов и пульта стоят контролёры, которые ими управляют. L>Какие-то странные у вас контроллеры. Зачем им постоянная частота обмена с мастером?
Самому интересно. Но что есть, то есть.
L>Что за производитель/модель?
Это самодельные контроллеры, которые разрабатывают простые французские инженеры. Убедить их, что надо делать что-нибудь более удобное в обращении мне не удалось.
L>Опять же, все это не имеет отношения к обсуждаемой теме. Ты можешь создать отдельный тред на мотор/группу моторов/порт, и зачастую это банально удобно с точки зрения организации алгоритма. Но мест взаимодействия потоков у тебя... ровно одно. Там, где фронт-энд этого фестиваля обменивается данными с бек-эндом. Причем, учитывая характер данных, тут может локов вообще не понадобится. Все. Вариантов организовать дед лок просто нет.
Ага. т.е. вы искусственно вводите одну нитку, которая прокачивает через себя все данные. Я правильно понимаю?
Здравствуйте, landerhigh, Вы писали:
L>>>1. Можно ли обойтись без лока? L>>Не нужно стараться уменьшать количество используемых мьютексов, L>Нужно. Больше количество мьютексов дают банально больше возможностей для возникновения лока.
Т.е. если довести это размышление до предела, то на одну программу нужно не более одного мютекса? Идея в этом состоит?
Здравствуйте, B0FEE664, Вы писали:
BFE>Ну так не в скорости проблема. Проблема в том, что в разные порты надо посылать команды с разными промежутками времени и ждать ответа тоже с разными интервалами.
Не вижу проблемы. С этим даже банальный таймер из asio справится. Внутри одного потока.
L>>>>и один тред, выдающий информацию во внешний мир — пульты, удаленные терминалы, веб-интрефейсы и так далее. BFE>>>Если он один, то как он устроен? Он весит на ожидании пакета из сети или на ожидании пакета на отправку? L>>Может, мне и систему за тебя сразу всю написать? Про неблокирующие сокеты слышал? BFE>Неблокирующие сокеты тут ничего не меняют. Что делает нитка, когда нечего посылать и нечего принимать?
Мультики смотрит. Ждет эвента. Пусть что хочет, то и делает.
L>>А если мотор отвечает, но с бОльшей задержкой по сравнению с другими моторами? BFE>А так и есть. Частота обмена командами разная с разными моторами.
Ну и каким образом софт может скомпенсировать это, если требуется полная синхронизация моторов?
BFE>Это уже 4 потока. И ещё минимум один для взаимодействия с сетью. Но замечу, что этот, пятый поток, ничего не делает, если нет никаких установленных сетевых соединений.
Какая разница? Это стандартный паттерн при разработке серверов.
L>>>>Вот это и будет тот самый, классический "multiple producers — one consumer". BFE>>>кто из них consumer, тот кто потребляет команды или тот, кто потребляет измеренные положения моторов? L>>Один консьюмер — эта та часть, которая связывает этот винигрет с внешним миром. Потребляет положения, иногда отдает команды. Потребитель услуг моторов. BFE>Ок. С помощью каких объектов происходит этот обмен?
Какие будет удобно использовать. Или ты имеешь в виду примитивы синхронизации?
L>>Какие-то странные у вас контроллеры. Зачем им постоянная частота обмена с мастером? BFE>Самому интересно. Но что есть, то есть.
L>>Что за производитель/модель? BFE>Это самодельные контроллеры, которые разрабатывают простые французские инженеры. Убедить их, что надо делать что-нибудь более удобное в обращении мне не удалось.
А, французы такие затейники
L>>Опять же, все это не имеет отношения к обсуждаемой теме. Ты можешь создать отдельный тред на мотор/группу моторов/порт, и зачастую это банально удобно с точки зрения организации алгоритма. Но мест взаимодействия потоков у тебя... ровно одно. Там, где фронт-энд этого фестиваля обменивается данными с бек-эндом. Причем, учитывая характер данных, тут может локов вообще не понадобится. Все. Вариантов организовать дед лок просто нет.
BFE>Ага. т.е. вы искусственно вводите одну нитку, которая прокачивает через себя все данные. Я правильно понимаю?
Не искусственно. Она даже логически одна, т.к. все данные рано или поздно должны оказаться на одной мнемосхеме.
Здравствуйте, B0FEE664, Вы писали:
L>>Нужно. Больше количество мьютексов дают банально больше возможностей для возникновения лока.
BFE>Т.е. если довести это размышление до предела, то на одну программу нужно не более одного мютекса? Идея в этом состоит?
Нет. Нужно всего лишь гарантировать, что ни при каких условиях не возникает ситуации, когда в одном стеке вызовов присутствует более одной блокировки.
Здравствуйте, Lazin, Вы писали:
L>>Нужно. Больше количество мьютексов дают банально больше возможностей для возникновения лока. L>Какбэ наоборот же чем больше мьютексов, тем меньше шансов что какие-то из них образуют цикл. Чисто с точки зрения теории вероятностей
На самом деле вероятность больше. т.к. вероятность лока между двумя любыми мьютекасами не зависит от наличия других мьютекосв. Умножай вероятности сам
L>Когда все используют 2 мьютекса, то любой захват в неверном порядке будет приводить к реальному deadlock-у.
А когда один? А если захват их в одной ветке невозможен?
L>>>>3. Как минимизировать длительность лока? Желательно до одной операции?
L>>>Uncontended lock — очень дешев, contended lock — дорог.
L>>Совершенно верно. Но все же рассматривать дороговизну этого лока как такового — это все равно, что жалеть гвоздей на постройку дома. Основной негативный эффект от contended lock заключается вовсе не во внутренней кухне мьютекса, а в вынужденном простое одного или нескольких потоков. Поэтому и нужно стремиться к тому, чтобы максимально меньшее время проводить под локом, чтобы снизить вероятность contended lock.
L>Ну это может быть, например, очередь, в которую поток кладет что-нибудь, для обработки другими потоками. Можно на каждое добавление лочить, можно залочить один раз на длительное время и добавить множество элементов.
Это стандартная задача. Если есть необходимость добавлять сразу много элементов для обработки, можно предусмотреть алгоритм для передачи целого контейнера с помощью одного swap.
А еще гибче передавать не данные, а таски. Тоже один своп, но данных можно сразу передать сколько угодно.
L>>>2. uncontended lock (мьютекс используется эксклюзивно, одним потоком) захватывать мьютекс часто — сравнительно не дорого, но если мы будем его также захватывать на более длительный интервал времени, то ничего страшного не произойдет, так как поток большую часть времени все равно владеет им в единоличном порядке.
L>>Мьютекс, используемый лишь одним потоком — это какой-то pkunzip.zip.
L>Часто используемый в параллельном программировании паттерн — в fast path захватывается какой-нибудь спин лок, который большую часть времени захватывается только одним потоком, но периодически что-нибудь происходит и какой-нибудь другой поток может залочить этот мьютекс и вмешаться в работу первого потока. Task stealing scheduler может так работать, например. Это нужно для того, чтобы захват лока был почти бесплатным большую часть времени, но при этом нужно иметь возможность обращаться к данным их других потоков иногда.
ты же сам только что сказал, что неконкурентный лок — дешев.
оффтопик поскипан, вернёмся к сути BFE>>Ага. т.е. вы искусственно вводите одну нитку, которая прокачивает через себя все данные. Я правильно понимаю? L>Не искусственно. Она даже логически одна, т.к. все данные рано или поздно должны оказаться на одной мнемосхеме.
Ну как же не искусственно? Все нитки могут общаться друг с другом напрямую. Зачем этот оверхед с "логически верной" ниткой?
Здравствуйте, landerhigh, Вы писали:
L>>>Нужно. Больше количество мьютексов дают банально больше возможностей для возникновения лока. BFE>>Т.е. если довести это размышление до предела, то на одну программу нужно не более одного мютекса? Идея в этом состоит? L>Нет. Нужно всего лишь гарантировать, что ни при каких условиях не возникает ситуации, когда в одном стеке вызовов присутствует более одной блокировки.
Что Lazin и пытается сделать с помощью библиотеки из первого поста. А с помощью чего вы собираетесь это гарантировать?
L>На самом деле вероятность больше. т.к. вероятность лока между двумя любыми мьютекасами не зависит от наличия других мьютекосв. Умножай вероятности сам
Я думал что ты говоришь об общем количестве локов, а не о количестве локов в стеке вызовов. С тем, что оптимально, когда у тебя в стеке вызовов всегда только один лок я согласен, это очевидно. Но все же это не всегда очевидно, поэтому ответ — "нужно делать всегда так, чтобы в стеке вызовов был только один лок" — не засчитывается
L>>Ну это может быть, например, очередь, в которую поток кладет что-нибудь, для обработки другими потоками. Можно на каждое добавление лочить, можно залочить один раз на длительное время и добавить множество элементов. L>Это стандартная задача. Если есть необходимость добавлять сразу много элементов для обработки, можно предусмотреть алгоритм для передачи целого контейнера с помощью одного swap. L>
L>А еще гибче передавать не данные, а таски. Тоже один своп, но данных можно сразу передать сколько угодно.
А как же балансировка нагрузки между ядрами? Может же быть такое, что один поток получил намного больше работы чем остальные (и в случае таска и в случае очереди с данными)
Можно привести другой пример, ты ищешь кратчайший путь между двумя узлами в графе, один поток начинает выполнять алгоритм дейкстры из начального узла, а другой — из конечного, пока не встретятся или один из потоков не дойдет до своей цели. Коммуницируют потоки через общую память. Можно захватывать лок часто, при каждом апдейте (посмотрели ноду, посчитали вес, записали в массив), как ты советуешь, а можно посчитать сразу для N-ого количества нод и обновить все за один захват мьютекса. В данном примере у нас contended lock, но при правильном выборе параметров можно все равно получить хороший прирост производительности. Если захватывать на короткий срок для каждой ноды, то получатся тормоза, так как мы захватывать/разхватывать будем дольше чем ходить по графу. Примеров много, на самом деле. Coarse grained vs fine grained это крайности, нам же всегда нужен какой-то подходящий для того или иного случая tradeoff.
L>>>Мьютекс, используемый лишь одним потоком — это какой-то pkunzip.zip.
L>>Часто используемый в параллельном программировании паттерн — в fast path захватывается какой-нибудь спин лок, который большую часть времени захватывается только одним потоком, но периодически что-нибудь происходит и какой-нибудь другой поток может залочить этот мьютекс и вмешаться в работу первого потока. Task stealing scheduler может так работать, например. Это нужно для того, чтобы захват лока был почти бесплатным большую часть времени, но при этом нужно иметь возможность обращаться к данным их других потоков иногда.
L>ты же сам только что сказал, что неконкурентный лок — дешев.
Это я привел пример мьютекса, использующегося одним потоком и объяснил зачем это может быть нужно.
Здравствуйте, B0FEE664, Вы писали:
BFE>оффтопик поскипан, вернёмся к сути BFE>>>Ага. т.е. вы искусственно вводите одну нитку, которая прокачивает через себя все данные. Я правильно понимаю? L>>Не искусственно. Она даже логически одна, т.к. все данные рано или поздно должны оказаться на одной мнемосхеме. BFE>Ну как же не искусственно? Все нитки могут общаться друг с другом напрямую. Зачем этот оверхед с "логически верной" ниткой?
во-первых, ниткам, которые отвечают за управление своим отдельным портом/мотором/группой моторов, не о чем общаться друг с другом. Разрешать им о чем-то болтать — логическая ошибка. Если им разрешить это, то гарантировать отсутствие софт- и дед-локов ты уже в общем случае не сможешь.
Но опять же, ты смотришь с позиции конкретного кода, а я рассуждаю о сферическом коде в вакууме.
BFE>Вот сами же пишите
BFE>Нужно всего лишь гарантировать, что ни при каких условиях не возникает ситуации, когда в одном стеке вызовов присутствует более одной блокировки.
Совершенно верно. Правильный способ это сделать — локализовать и минимизировать межпотоковое взаимодействие. Разрешать всем потокам общаться друг с другом напрямую, во-первых, бессмысленно, во-второых, ведет к серьезным ошибкам.
Здравствуйте, Lazin, Вы писали:
L>>На самом деле вероятность больше. т.к. вероятность лока между двумя любыми мьютекасами не зависит от наличия других мьютекосв. Умножай вероятности сам
L>Я думал что ты говоришь об общем количестве локов, а не о количестве локов в стеке вызовов. С тем, что оптимально, когда у тебя в стеке вызовов всегда только один лок я согласен, это очевидно. Но все же это не всегда очевидно, поэтому ответ — "нужно делать всегда так, чтобы в стеке вызовов был только один лок" — не засчитывается
Я говорил и о первом тоже. Количество объектов синхронизации в программе должно строго соответствовать количеству мест взаимодействия потоков. И их количество должно быть как можно более меньшим.
L>А как же балансировка нагрузки между ядрами? Может же быть такое, что один поток получил намного больше работы чем остальные (и в случае таска и в случае очереди с данными)
tough luck. Если это становится проблемой, то ее нужно решать отдельно.
L>Можно привести другой пример, ты ищешь кратчайший путь между двумя узлами в графе, один поток начинает выполнять алгоритм дейкстры из начального узла, а другой — из конечного, пока не встретятся или один из потоков не дойдет до своей цели.
И какой у меня, пардон, выигрыш от использования двух потоков? А какой геморрой?
L>Коммуницируют потоки через общую память. Можно захватывать лок часто, при каждом апдейте (посмотрели ноду, посчитали вес, записали в массив), как ты советуешь, а можно посчитать сразу для N-ого количества нод и обновить все за один захват мьютекса.
А можно использовать атомики и помечать посещенные ноды. Никаких локов вообще.
L>В данном примере у нас contended lock, но при правильном выборе параметров можно все равно получить хороший прирост производительности.
Больше двух раз все равно не выйдет.
L>Если захватывать на короткий срок для каждой ноды, то получатся тормоза, так как мы захватывать/разхватывать будем дольше чем ходить по графу. Примеров много, на самом деле.
Как я уже сказал, в этом случае можно вообще без локов обойтись.
Coarse grained vs fine grained это крайности, нам же всегда нужен какой-то подходящий для того или иного случая tradeoff.
L>>ты же сам только что сказал, что неконкурентный лок — дешев.
L>Это я привел пример мьютекса, использующегося одним потоком и объяснил зачем это может быть нужно.
Эээ, мьютексы не нужны, если они используются только одинм потоком. Они нужны как раз тогда, когда "иногда" на огонек заходит другой поток. Кстати, критические секции в винде устроены именно так, емнип — неконкурентных захват секции предельно дешев.
Здравствуйте, Lazin, Вы писали:
L>На практике это должно выглядеть как-то так: допустим у нас есть приложение — сервер, оно состоит из сетевой части, которая принимает запросы и новые подключения и (допустим) использует asymmetric lock layer для чтения настроек сетевого стека, white-list допустимых адресов и тд, далее запрос может обрабатываться на урвоне приложения, который использует другой lock layer для того, чтобы защитить доступ к изменяемым данным, далее, в процессе обработки прилоежние должно сохранить данные в БД, там используется еще один lock layer. Блокировки всегда захватываются в порядке, определенном иерархией — server lock layer -> application lock layer -> DB lock layer.
L>Теперь собственно вопрос — хочется специальный дефайн, при определении которого, включались бы проверки корректности порядка захвата и освобождения блокировок. Пока не придумал ничего лучше, нежели строить recourse allocation graph в рантайме, во время вызовов lock/unlock, а потом искать в нем циклы. Еще придумал вариант для бедных — можно сделать массив мьютексов из одного элемента, в этом случае, любой некорректное использование библиотеки будет обязательно приводить к ваимной блокировке и можно будет сравнить стектрейсы разных потоков и понять где ошибка. Может есть еще варианты?
Может как то явно определить для каждого lock layer глубину в иерархии и в lock-unlock складывать её в thread local стек с проверкой на 'больше' при push и на 'равно' при pop?
Здравствуйте, B0FEE664, Вы писали:
L>>Нет. Нужно всего лишь гарантировать, что ни при каких условиях не возникает ситуации, когда в одном стеке вызовов присутствует более одной блокировки.
BFE>Что Lazin и пытается сделать с помощью библиотеки из первого поста. А с помощью чего вы собираетесь это гарантировать?
Разница в том, что Lazin лечит осложнения болезни.
Я же ее просто не допускаю.
Дело в том, что пытаться детектить дедлоки в рантайме бессмысленно. Дедлок в рантайме исправить невозможно. Дедлок — это всегда ошибка проектирования. Тот самый случай, когда пить боржоми уже поздно.
Во время тестирования абсолютно невозможно отловить все возможные варианты, особенно, когда мьютексы создаются на каждый чих. Если детектор выявил Х дедлоков во время тестирования, это вовсе не гарантирует, что нашли их все. Более того, это говорит о том, что код плохо спроектирован с точки зрения межпотокового взаимодействия и скорее всего, в нем притаились другие дедлоки, которые просто ждут своего шанса.
Здравствуйте, Lazin, Вы писали:
L>Так как я заменил их на общий пулл мьютексов, то возможна такая ситуация — адреса объектов a и d хешируются на один мьютекс (MA), а адреса объектов b и c — на другой мьютекс — (MB), в этом случае первый поток попытается захватить мьютексы в порядке MA -> MB, а второй в обратном порядке — MB -> MA. Это приведет к взаимной блокировке.
Выделенное — лютый трындец. Сегодня a и b на один мьютекс попали, на следующем старте a и c попадут — это называется happy debugging. Имхо — изначальная идея порочная, все остальное только следствие из бажной концепции.
_>Выделенное — лютый трындец. Сегодня a и b на один мьютекс попали, на следующем старте a и c попадут — это называется happy debugging. Имхо — изначальная идея порочная, все остальное только следствие из бажной концепции.
Это совершенно обычная вещь, так часто делают. Самый частый юзкейс — это когда у тебя много объектов и каждый нужно лочить отдельно, но пихать невпихуемое^W настоящий мьютекс в каждый объект — дорого. Если ты используешь этот пулл мьютексов не рекурсивно (только один лок в стеке вызовов), то взаимная блокировка возникнуть не может. Это легко можно доказать. Можно использовать несколько разных пуллов мьютексов, если в стеке вызовов всегда все захватывается в одном и том же порядке.
L>Дело в том, что пытаться детектить дедлоки в рантайме бессмысленно. Дедлок в рантайме исправить невозможно. Дедлок — это всегда ошибка проектирования. Тот самый случай, когда пить боржоми уже поздно.
Я не планирую ничего исправлять, у меня в голове такой юзкейс: программист использует библиотеку для создания приложения, вдруг, в каких-нибудь условиях вылезает дедлок, программист делает специальный билд, в котором включен механизм обнаружения взаимных блокировок, запускает приложение, повторяет условия при которых возникала взаимная блокировка, библиотека видит условие возникновение делока, пишет простыню в stderr и вызывает terminate.
L>Во время тестирования абсолютно невозможно отловить все возможные варианты, особенно, когда мьютексы создаются на каждый чих. Если детектор выявил Х дедлоков во время тестирования, это вовсе не гарантирует, что нашли их все. Более того, это говорит о том, что код плохо спроектирован с точки зрения межпотокового взаимодействия и скорее всего, в нем притаились другие дедлоки, которые просто ждут своего шанса.
В том то и дело, что я свожу сложную проблему — детектор дедлоков для N мьютексов — к простой, детектор дедлоков для LockLayer-ов, которых в типичной программе должно быть один или два
чем больше мьютексов, тем меньше шансов что какие-то из них образуют цикл. Чисто с точки зрения теории вероятностей 
Один-три на всю систему.
