Навелосипедил небольшую бибилотеку синхронизации, с целью проверить кое что — https://github.com/Lazin/Syncope
Там есть описание на rungilsh-е, идея очень простая на самом деле. Вместо того, чтобы добавлять мьютексы как поля в объекты, можно использовать внешний массив (пулл) мьютексов. Когда мы хотим залочить объект — мы берем его адрес, вычисляем простой хэш и используем его для получения мьютекса из пулла, после чего захватываем его. Для того, чтобы это работало без дедлоков, нужно чтобы была подходящая иерархия локов в программе. Вот такой вот массив может использоваться только на одном уровне иерархии.
Выглядит это примерно вот так:
syncope::SymmetricLockLayer lock_layer(STATIC_STRING("layer name"));
...
auto guard = lock_layer.synchronize(&obj1, &obj2, ptr3);
...do anything with obj1, obj2 and ptr3
Все будет залочено до тех пор, пока область видимости переменной guard не закончится. Порядок аргументов в вызове synchronize не важен. Помимо симметричных блокировок, реализованы не симметричные.
read блокировку можно проапгрейдить до write блокировки при желании. Моя реализация R/W Lock сильно смещена в сторону читателей и предназначена для случаев, когда запись происходить на несколько порядков реже чем чтение (например для защиты настроек программы). В этом случае read_lock работает в 2-3 раза быстрее чем pthread_rwlock_rdlock. Также возможно, что pthread_rwlock_rdlock лучше масштабируется с ростом количества ядер/процессоров, чем моя реализация.
Архитектурно, с этой штукой нужно работать следующим образом — все блокировки разделяются на уровни и для каждого уровня создается свой LockLayer (один или несколько). Каждый LockLayer — не рекурсивен, что значит, что вы не можете захватить лок под другим локом одного и того же уровня.
auto guard = lock_layer.synchronize(&obj1);
{
// inner scope or function call under lockauto guard = lock_layer.synchronize(&obj2);
}
тут вы должны просто заранее захватить оба объекта, в противном случае возможны взаимные блокировки.
На практике это должно выглядеть как-то так: допустим у нас есть приложение — сервер, оно состоит из сетевой части, которая принимает запросы и новые подключения и (допустим) использует asymmetric lock layer для чтения настроек сетевого стека, white-list допустимых адресов и тд, далее запрос может обрабатываться на урвоне приложения, который использует другой lock layer для того, чтобы защитить доступ к изменяемым данным, далее, в процессе обработки прилоежние должно сохранить данные в БД, там используется еще один lock layer. Блокировки всегда захватываются в порядке, определенном иерархией — server lock layer -> application lock layer -> DB lock layer.
Теперь собственно вопрос — хочется специальный дефайн, при определении которого, включались бы проверки корректности порядка захвата и освобождения блокировок. Пока не придумал ничего лучше, нежели строить recourse allocation graph в рантайме, во время вызовов lock/unlock, а потом искать в нем циклы. Еще придумал вариант для бедных — можно сделать массив мьютексов из одного элемента, в этом случае, любой некорректное использование библиотеки будет обязательно приводить к ваимной блокировке и можно будет сравнить стектрейсы разных потоков и понять где ошибка. Может есть еще варианты?
в одной из предыдущих контор, у нас был кроссплатформенный мутекс (де-факто обертка над виндовым/pthread мутексами). в дебажной версии он (мутекс) регил себя в специальном механизме, который держал внутри себя граф блокировок. этот граф писался на диск, в случае обнаружения дедлока девелопер получал сразу граф — что с чем пересеклось. при этом никаких особых танцев с бубном и особенной организации кода не требуется, думаю что тебе стоит попробовать копнуть в эту сторону.
Здравствуйте, John1979, Вы писали:
J>Здравствуйте, Lazin, Вы писали:
J>в одной из предыдущих контор, у нас был кроссплатформенный мутекс (де-факто обертка над виндовым/pthread мутексами). в дебажной версии он (мутекс) регил себя в специальном механизме, который держал внутри себя граф блокировок. этот граф писался на диск, в случае обнаружения дедлока девелопер получал сразу граф — что с чем пересеклось. при этом никаких особых танцев с бубном и особенной организации кода не требуется, думаю что тебе стоит попробовать копнуть в эту сторону.
Здравствуйте, Lazin, Вы писали:
L>Навелосипедил небольшую бибилотеку синхронизации, с целью проверить кое что — https://github.com/Lazin/Syncope L>Там есть описание на rungilsh-е, идея очень простая на самом деле. Вместо того, чтобы добавлять мьютексы как поля в объекты, можно использовать внешний массив (пулл) мьютексов. Когда мы хотим залочить объект
Вот сколько занимаюсь многопоточной чертовщиной, ни разу не возникло необходимости выдумывать первентеров дедлоков.
ИМХО все проблемы многопоточного программирования вырастают из выделенного. "Когда мы хотим залочить".
Залочить объект нельзя "хотеть". Его может быть необходимо залочить. Так вот, всякий раз, когда программист сталкивается с необходимостью использования лока того или иного вида, он должен ответить на следующие вопросы:
1. Можно ли обойтись без лока?
2. Какие побочные эффекты у данного лока могуть быть и как их можно избежать?
3. Как минимизировать длительность лока? Желательно до одной операции?
Если ответ на первый вопрос отрицательный, то следует безотлагательно проанализировать архитектуру на предмет минимизации мест коллизий, т.е. мест, где требуется взаимодействие между потоками с блокировками.
Обычно, если следовать этим нехитрым правилам, все межпоточное взаимодействие сводится к коротким эпизодам исключительного чтения или исключительной записи. При этом объект, находящийся под локом, никаких операций сам обычно не совершает и посему организовать дедлок не может.
L>На практике это должно выглядеть как-то так: допустим у нас есть приложение — сервер, оно состоит из сетевой части, которая принимает запросы и новые подключения и (допустим) использует asymmetric lock layer для чтения настроек сетевого стека, white-list допустимых адресов и тд, далее запрос может обрабатываться на урвоне приложения, который использует другой lock layer для того, чтобы защитить доступ к изменяемым данным, далее, в процессе обработки прилоежние должно сохранить данные в БД, там используется еще один lock layer. Блокировки всегда захватываются в порядке, определенном иерархией — server lock layer -> application lock layer -> DB lock layer.
Это какой-то
грубо говоря, когда блокировки разбросаны по всему коду по типу "хотим залочить — лочим, и никаких гвоздей", от дедлоков и прочих напастей ничего уже не спасет, ибо это лишь следствие болезни
L>Вот сколько занимаюсь многопоточной чертовщиной, ни разу не возникло необходимости выдумывать первентеров дедлоков.
См. первый ответ в этом топике. Меня интересуют такие алгоритмы, а вовсе не то, что они не нужны. Т.е. все то, что идет дальше, это немного оффтопик.
L>ИМХО все проблемы многопоточного программирования вырастают из выделенного. "Когда мы хотим залочить". L>Залочить объект нельзя "хотеть". Его может быть необходимо залочить. Так вот, всякий раз, когда программист сталкивается с необходимостью использования лока того или иного вида, он должен ответить на следующие вопросы:
Придрался к формулировке. Понятно, что нет смысла лочить то, что лочить не нужно. Я здесь просто способ использования библиотеки старался написать, а вовсе даже не универсальный tutorial по многопоточному программированию.
L>1. Можно ли обойтись без лока? L>2. Какие побочные эффекты у данного лока могуть быть и как их можно избежать? L>3. Как минимизировать длительность лока? Желательно до одной операции?
Задав себе такие вопросы, он гарантировано сделает deadlock
2-й пункт я бы изменил на проверку корректности порядка захвата локов разными потоками. Если я захватываю лок, а под локом вызываю коллбэк, который захватывает другой лок — я могу получить взаимную блокировку. Иерархии блокировок, это не то, что я выдумал перепив белого сухого. Вот, например, древняя статья Саттера на эту тему в Dr. Dobbs — http://www.drdobbs.com/parallel/use-lock-hierarchies-to-avoid-deadlock/204801163
Перечисленные тобой 3 пункта не являются достаточными, так как ты не анализируешь resource allocation graph, который при испльзовании блокировок неизбежно возникает.
L>Если ответ на первый вопрос отрицательный, то следует безотлагательно проанализировать архитектуру на предмет минимизации мест коллизий, т.е. мест, где требуется взаимодействие между потоками с блокировками.
Это может быть реальность, данная нам в ощущениях. В общем, это становится похоже на разговор о том что нужно делать хорошо и не нужно делать плохо
L>>На практике это должно выглядеть как-то так: допустим у нас есть приложение — сервер, оно состоит из сетевой части, которая принимает запросы и новые подключения и (допустим) использует asymmetric lock layer для чтения настроек сетевого стека, white-list допустимых адресов и тд, далее запрос может обрабатываться на урвоне приложения, который использует другой lock layer для того, чтобы защитить доступ к изменяемым данным, далее, в процессе обработки прилоежние должно сохранить данные в БД, там используется еще один lock layer. Блокировки всегда захватываются в порядке, определенном иерархией — server lock layer -> application lock layer -> DB lock layer.
L>Это какой-то
Это пример.
L>грубо говоря, когда блокировки разбросаны по всему коду по типу "хотим залочить — лочим, и никаких гвоздей", от дедлоков и прочих напастей ничего уже не спасет, ибо это лишь следствие болезни
"Я читаю то, что хочу прочитать" Еще раз, это пример. Никто не утверждает, что нужно лочить все подряд. Данная библиотека появилась в результате того, что я придумал новый алгоритм для R/W мьютекса. Он требует пулл мьютетксов и не может быть реализован как индивидуальный мьютекс (точнее может, но накладные расходы будут велики). Поэтому я решил сделать такой объект, который бы хранил этот пулл мьютексов и умел бы лочить другие объекты (получился AsymmetricLockLayer). Потом я начал анализировать корректность и пришел к выводу о том, что нужно явно энфорсить правильный порядок использования нескольких уровней блокировки, так как из-за того, что я использую пуллы мьютексов, у меня могут быть конфликты, а конфликты могут приводить к взаимным блокировкам, если пользователь использует отдельный LockLayer как рекурсивный мьютекс, либо он использует несколько LockLayer-ов, но не соблюдает порядок (в одном потоке использует LockLayers в одном порядке, а в другом потоке — в другом порядке), даже если юзер лочит разные объекты. Если бы не этот факт, можно было бы возложить ответственность за корректность порядка захвата мьютексов на юзера. Но у юзера моей библиотеки нет мьютексов в явном виде
Как пллюс — lock hierarchy появляется в коде явным образом и анализ на дедлоки упрощается, так как нужно строить граф захвата ресурсов не для отдельных мьютексов а только для разных уровней (объектов ***LockLayer). Как я уже писал, сейчас у меня можно задать один define и получить deadlock гарантированно, если он возможен — poor man's deadlock prevention algorithm
Здравствуйте, Lazin, Вы писали:
L>>Вот сколько занимаюсь многопоточной чертовщиной, ни разу не возникло необходимости выдумывать первентеров дедлоков.
L>См. первый ответ в этом топике. Меня интересуют такие алгоритмы, а вовсе не то, что они не нужны. Т.е. все то, что идет дальше, это немного оффтопик.
Дело в том, что эти алгоритмы действительно не нужны. Т.к. это ни что иное, как заметание проблемы под ковер.
L>>ИМХО все проблемы многопоточного программирования вырастают из выделенного. "Когда мы хотим залочить". L>>Залочить объект нельзя "хотеть". Его может быть необходимо залочить. Так вот, всякий раз, когда программист сталкивается с необходимостью использования лока того или иного вида, он должен ответить на следующие вопросы:
L>Придрался к формулировке. Понятно, что нет смысла лочить то, что лочить не нужно. Я здесь просто способ использования библиотеки старался написать, а вовсе даже не универсальный tutorial по многопоточному программированию.
Нет, не придрался. Вот ты и я понимаем, что нет смысла лочить то, что лочить не нужно. Но ты забываешь о 80% программистов-ковбоев, которые делают это, не включая моск. Дай им библиотеку, которая якобы предотвращает дедлоки, и они залочат все к такой-то матери. И тормознут крутейший суперкомпьютер, а то и создадут-таки дед лок.
L>>1. Можно ли обойтись без лока? L>>2. Какие побочные эффекты у данного лока могуть быть и как их можно избежать? L>>3. Как минимизировать длительность лока? Желательно до одной операции?
L>Задав себе такие вопросы, он гарантировано сделает deadlock
Нет. Правильно ответив на эти вопросы, он гарантированно напишет код, в котором дедлок будет невозможен.
L>2-й пункт я бы изменил на проверку корректности порядка захвата локов разными потоками. Если я захватываю лок, а под локом вызываю коллбэк, который захватывает другой лок — я могу получить взаимную блокировку.
Для этого нужно в первую очередь иметь этот другой лок. Два лока подряд означает, что в одно и то же время могут взаимодействовать три и более потоков. Это уже очень, очень плохой сигнал и повод к пересмотру архитектуры. Как правило, обычно многопоточные программы можно свести к паттерну "one producer — multiple consumers/multiple producers — one consumer". При этом, за счет того, что все взаимодействие идет лишь между продьюсером и консьюмером, точек взаимодействия потоков обычно мало, а зачастую она всего лишь одна и лок требуется ровно один.
L>Иерархии блокировок, это не то, что я выдумал перепив белого сухого. Вот, например, древняя статья Саттера на эту тему в Dr. Dobbs — http://www.drdobbs.com/parallel/use-lock-hierarchies-to-avoid-deadlock/204801163
ИМХО это рассуждение на тему поиска решения проблемы, которой не должно существовать. То есть иерархиями блокировок пользоваться можно. Но гораздо лучше сделать так, чтобы в них не было необходимости.
L>Перечисленные тобой 3 пункта не являются достаточными, так как ты не анализируешь resource allocation graph, который при испльзовании блокировок неизбежно возникает.
resource allocation сам по себе не вызовет дедлока. Опустим вырожденные случаи вроде DLLMain
L>>Если ответ на первый вопрос отрицательный, то следует безотлагательно проанализировать архитектуру на предмет минимизации мест коллизий, т.е. мест, где требуется взаимодействие между потоками с блокировками.
L>Это может быть реальность, данная нам в ощущениях. В общем, это становится похоже на разговор о том что нужно делать хорошо и не нужно делать плохо
Ну так если что-то нужно сделать, то это нужно сделать хорошо. Иначе — зачем вообще шевелиться?
L>>Это какой-то
L>Это пример.
Это какой-то пример.
L>>грубо говоря, когда блокировки разбросаны по всему коду по типу "хотим залочить — лочим, и никаких гвоздей", от дедлоков и прочих напастей ничего уже не спасет, ибо это лишь следствие болезни
L>"Я читаю то, что хочу прочитать" Еще раз, это пример. Никто не утверждает, что нужно лочить все подряд. Данная библиотека появилась в результате того, что я придумал новый алгоритм для R/W мьютекса.
А ты оверхед от всего этого фестиваля оценивал уже?
L>>См. первый ответ в этом топике. Меня интересуют такие алгоритмы, а вовсе не то, что они не нужны. Т.е. все то, что идет дальше, это немного оффтопик. L>Дело в том, что эти алгоритмы действительно не нужны. Т.к. это ни что иное, как заметание проблемы под ковер.
Буржуйский форум программистов, вопрос: у меня есть вот такая вот проблема, ответ: у этой проблемы есть такое решение. Скука.
Пост-советский форум программистов, вопрос: у меня есть вот такая вот проблема, ответ: это вообще не проблема, ты просто делаешь все не правильно, а теперь давай я поучу тебя программировать!
А если серьезно, проблема все же есть, в golang, например, есть deadlock-detector из коробки, он работает для каналов, которые по сути — просто ограниченые межпоточные очереди. Если поискать в каком нибудь поисковике по научным статьям по запросу "deadlock detection", то можно обнаружить, что проблема активно исследуется, следовательно, это нужно. Софт бывает разным, часто, разные части пишут разные люди, или разные команды, или вообще — разные компании. В этих случаях сложно посмотреть на код "с высоты птичьего полета". Довольно очевидно, что когда ты вызываешь какой-то код под локом, этот код может вызывать другой код, который тоже может что-нибудь лочить внутри себя и так далее.
L>>Придрался к формулировке. Понятно, что нет смысла лочить то, что лочить не нужно. Я здесь просто способ использования библиотеки старался написать, а вовсе даже не универсальный tutorial по многопоточному программированию. L>Нет, не придрался. Вот ты и я понимаем, что нет смысла лочить то, что лочить не нужно. Но ты забываешь о 80% программистов-ковбоев, которые делают это, не включая моск. Дай им библиотеку, которая якобы предотвращает дедлоки, и они залочат все к такой-то матери. И тормознут крутейший суперкомпьютер, а то и создадут-таки дед лок.
Не нужно относиться к другим так. Любая книга по многопоточному программированию описывает взаимные блокировки и как правило там говорится о том, что локи в программе должны быть организованы в иерархическую структуру. Я уже писал о том, что по причине того, что моя библиотека прячет мьютексы за своим интерфесом, она должна предоставлять механизм проверки корректности. Т.е. если у нас есть 4 объекта — Foo a, b, c, d; Пользователь может написать код:
// thread A
{
lock_layer.synchronize(&a);
...
{
lock_layer.synchronize(&b);
}
}
// thread A
{
lock_layer.synchronize(&c);
...
{
lock_layer.synchronize(&d);
}
}
Хороший программист (не ковбой от программирования) будет доумать так: я лочу в одном потоке сначала а, а потом b, а во втором потоке — сначала c а потом d, но здесь нет цикла, так как объекты разные, следовательно дедлок невозможен. Это было бы справедливо, если бы каждому из объектов а b c d соответстовал отдельный мьютекс.
Так как я заменил их на общий пулл мьютексов, то возможна такая ситуация — адреса объектов a и d хешируются на один мьютекс (MA), а адреса объектов b и c — на другой мьютекс — (MB), в этом случае первый поток попытается захватить мьютексы в порядке MA -> MB, а второй в обратном порядке — MB -> MA. Это приведет к взаимной блокировке. Отсюда — запрет на рекурсивные блокировки одним lock layer-ом. Но это сложно контролировать и это не интуитивно, поэтому я хочу сделать механизм, для автоматического обнаружения этой ситуации в дебажном режиме.
L>>>1. Можно ли обойтись без лока? L>>>2. Какие побочные эффекты у данного лока могуть быть и как их можно избежать? L>>>3. Как минимизировать длительность лока? Желательно до одной операции? L>>Задав себе такие вопросы, он гарантировано сделает deadlock L>Нет. Правильно ответив на эти вопросы, он гарантированно напишет код, в котором дедлок будет невозможен.
Нужно аргументы приводить, иначе я тоже могу еще раз сказать — "задав себе эти вопросы он гарантировано сделает deadlock"
Длительность локов и взаимные блокировки — иррелевантны. Мы не можем всегда контролировать длительность локов. А что если нужно лочить долгую процедуру? А что если она еще и callback на вход получает? Ты тоже вот эти вот три вопроса себе задашь и все? Или все же подумаешь о том — не лочит ли мой callback что-нибудь, он же будет вызываться под другим локом, каким будет порядок захвата мьютексов в моей программе в этом случае?
L>>2-й пункт я бы изменил на проверку корректности порядка захвата локов разными потоками. Если я захватываю лок, а под локом вызываю коллбэк, который захватывает другой лок — я могу получить взаимную блокировку. L>Для этого нужно в первую очередь иметь этот другой лок. Два лока подряд означает, что в одно и то же время могут взаимодействовать три и более потоков. Это уже очень, очень плохой сигнал и повод к пересмотру архитектуры. Как правило, обычно многопоточные программы можно свести к паттерну "one producer — multiple consumers/multiple producers — one consumer". При этом, за счет того, что все взаимодействие идет лишь между продьюсером и консьюмером, точек взаимодействия потоков обычно мало, а зачастую она всего лишь одна и лок требуется ровно один.
Вот опять — я говорю о корректности, ты говоришь о других вещах. Но раз ты так хочешь поговорить об этом, то переменную под мьютексом можно вполне рассматривать как ограниченую блокирующую очередь в которую можно положить только один элемент. Есть такой изоморфизм, между мьютексами и передачей сообщений, в параллельном программировании. Ты будешь утверждать, что producer/consumer система должна всегда обходиться одной очередью сообщений?
L>>Перечисленные тобой 3 пункта не являются достаточными, так как ты не анализируешь resource allocation graph, который при испльзовании блокировок неизбежно возникает. L>resource allocation сам по себе не вызовет дедлока. Опустим вырожденные случаи вроде DLLMain
resource allocation graph это вот — http://siber.cankaya.edu.tr/OperatingSystems/ceng328/node156.html
L>>"Я читаю то, что хочу прочитать" Еще раз, это пример. Никто не утверждает, что нужно лочить все подряд. Данная библиотека появилась в результате того, что я придумал новый алгоритм для R/W мьютекса. L>А ты оверхед от всего этого фестиваля оценивал уже?
Мой R/W мьтекс быстрее R/W мьютекса из pthread на тех нагрузках, для которых он создавался, я же об этом в первом сообщении написал
Пуллы мьютексов тоже вещь не новая, их часто используют, оверхед почти нулевой, вычисление индекса мьютекса — пара asm иснтрукций а дальше все так же как и в случае просто мьютекса, если объектов много, то пулл даже дешевле, так как требует создаваать меньше объектов ядра (меньше жрется nonpaged память ядра) и меньше памяти под сами мьютексы (std mutex это не только объект ядра но и какой-то state и еще padding, всего 64 байта).
Здравствуйте, landerhigh, Вы писали:
L>Для этого нужно в первую очередь иметь этот другой лок. Два лока подряд означает, что в одно и то же время могут взаимодействовать три и более потоков. Это уже очень, очень плохой сигнал и повод к пересмотру архитектуры. Как правило, обычно многопоточные программы можно свести к паттерну "one producer — multiple consumers/multiple producers — one consumer". При этом, за счет того, что все взаимодействие идет лишь между продьюсером и консьюмером, точек взаимодействия потоков обычно мало, а зачастую она всего лишь одна и лок требуется ровно один.
Извините, но вот это "one producer — multiple consumers/multiple producers — one consumer" — простой вырожденный случай. Его вообще не имеет смысла рассматривать.
Вот, например, описание проекта над которым я сейчас работаю: есть восемь 11 моторов организованные в группы по 3, 3, 5 моторов. Каждая группа моторов может быть в любой момент подключена или отключена физически оператором с помощью кабеля. Каждая группа моторов принимает команды позиционирования мотора и передаёт текущую позицию моторов. Частота обмена информацией с группой в 5 моторов, отличается от частоты обмена информации с группами по 3 мотора. Далее, имеется пуль управления, обмен информацией с которым идёт со своей частотой отличной от частоты обмена информации с моторами. Пульт управления должен отправлять команды моторам и отображать текущую информацию. Пуль может физически отсоединятся оператором в любой момент. Это не всё: есть ещё интернет соединения разного вида, которые эта установка должна поддерживать: web интерфейс отображающий текущую информацию, удалённые пульты управления соединённые по ethernet или по wi-fi, который встроен прямо в установку. Одновременно может быть подключено несколько пультов управления управляющих некоторыми из моторов одновременно и независимо друг от друга. Характерные периоды работы с моторами и с физически подсоединённым пультом составляет десятки миллисекунд. Каждый из пультов управления помимо текущего положения моторов должен отображать выданные команды (моторы имеют свою скорость, причем она разная у разных моторов). Положения некоторых моторов должны быть согласованы и синхронизированы. Давайте, попробуйте нарисовать здесь архитектуру с одним producer'ом или одним consumer'ом, учитывая, что всё это работает на одноядерном арме.
Кстати, вот это вот:
L>1. Можно ли обойтись без лока?
... L>3. Как минимизировать длительность лока? Желательно до одной операции?
... L>Обычно, если следовать этим нехитрым правилам, все межпоточное взаимодействие сводится к коротким эпизодам исключительного чтения или исключительной записи. При этом объект, находящийся под локом, никаких операций сам обычно не совершает и посему организовать дедлок не может.
ошибочно, в некоторых случаях с точностью до наоборот
Здравствуйте, B0FEE664, Вы писали:
BFE>Извините, но вот это "one producer — multiple consumers/multiple producers — one consumer" — простой вырожденный случай. Его вообще не имеет смысла рассматривать. BFE>Вот, например, описание проекта над которым я сейчас работаю: есть восемь 11 моторов организованные в группы по 3, 3, 5 моторов.
Честно говоря, я не вижу тут врожденной необходимости в многопоточности вообще.
Максимум — один тред для общения с моторами и один тред, выдающий информацию во внешний мир — пульты, удаленные терминалы, веб-интрефейсы и так далее.
Если моторы/группы моторов сидят каждый на своем физическом интрефейсе и работа с ним возможна только в блокирующем режиме (правда, тогда непонятны требования к согласованности — ведь пока мотор не соизволит ответить, вы ему новую команду выдать не сможете, как ни извернитесь), то так и быть, на каждый мотор/группу моторов по отдельному потоку. Вот это и будет тот самый, классический "multiple producers — one consumer".
BFE>Положения некоторых моторов должны быть согласованы и синхронизированы.
Я надеюсь, что вы не напрямую управляете шаговыми моторами из non-realtime OS? Через контроллер ведь, так? Или вы пытаетесь быть этим самым контроллером?
Здравствуйте, Lazin, Вы писали:
L>>Дело в том, что эти алгоритмы действительно не нужны. Т.к. это ни что иное, как заметание проблемы под ковер.
L>Буржуйский форум программистов, вопрос: у меня есть вот такая вот проблема, ответ: у этой проблемы есть такое решение. Скука.
У любой проблемы есть два решения
L>Пост-советский форум программистов, вопрос: у меня есть вот такая вот проблема, ответ: это вообще не проблема, ты просто делаешь все не правильно, а теперь давай я поучу тебя программировать!
Дело в том, что лучше не создавать ситуаций, в которых возможен дедлок, нежели искать возможность создать детекторы для них.
L>А если серьезно, проблема все же есть, в golang, например, есть deadlock-detector из коробки, он работает для каналов, которые по сути — просто ограниченые межпоточные очереди. Если поискать в каком нибудь поисковике по научным статьям по запросу "deadlock detection", то можно обнаружить, что проблема активно исследуется, следовательно, это нужно.
Наука вообще изучает много чего, но она далеко не всегда изучает то, что реально нужно. Мое мнение — это просто такая удобная для изучения тема, на которой можно зарабатывать PhD, ничего особо не делая.
L>Софт бывает разным, часто, разные части пишут разные люди, или разные команды, или вообще — разные компании. В этих случаях сложно посмотреть на код "с высоты птичьего полета". Довольно очевидно, что когда ты вызываешь какой-то код под локом, этот код может вызывать другой код, который тоже может что-нибудь лочить внутри себя и так далее.
А вот тут — стоп. Когда я вызываю какой-то код под локом, это означает, что у меня есть потенциальное взаимодействие двух потоков. Если оказывается, что этот код может попытаться получить другой лок, это означает, что взаимодействие распространяется на потенциально неограниченное количество потоков. Это уже само по себе нонсенс и означает, что лок рано или поздно выстрелит. И заранее протестировать динамическую систему на гарантированное отсутствие лока в общем случаее невозможно.
Я одно время копал в этом направлении. Например, если у меня есть подозрение, что некий код содержит потенциальный дедлок, я могу специально организовать юнит-тест, который его вызовет. Но, в общем случае невозможно создать автотест, который будет гарантировать отсутствие дедлока.
Еще раз — я всегда пытаюсь сводить межпоточное взаимодействие исключительно к однонаправленному чтению или записи. Никаких графов вызовов, особенно в другие потоки, из-под локов быть не должно. Мое мнение — наличие такого графа есть признак ошибки проектирования.
Хороший пример такой ошибки из реальной жизни — несколько близко расположенных подряд несинхронизированных светофоров. Хороший пример исправления такой ошибки — перепроектировать близко расположенные перекрестки и светофоры так, чтобы рассматривать их как единый домен коллизий и иметь единую систему управления ими.
L>>>Придрался к формулировке. Понятно, что нет смысла лочить то, что лочить не нужно. Я здесь просто способ использования библиотеки старался написать, а вовсе даже не универсальный tutorial по многопоточному программированию. L>>Нет, не придрался. Вот ты и я понимаем, что нет смысла лочить то, что лочить не нужно. Но ты забываешь о 80% программистов-ковбоев, которые делают это, не включая моск. Дай им библиотеку, которая якобы предотвращает дедлоки, и они залочат все к такой-то матери. И тормознут крутейший суперкомпьютер, а то и создадут-таки дед лок.
L>Не нужно относиться к другим так.
Нужно. Во время code review отменяются все женевские соглашения. Во время code review допускается даже харрасмент и геноцид. Иначе и педали газа клинят и самолеты падают и электростанции взрываются. Думаю, в недалеком будущем я напишу книгу об ужасных примерах "многопоточного ковбойского" программирования.
L>Любая книга по многопоточному программированию описывает взаимные блокировки и как правило там говорится о том, что локи в программе должны быть организованы в иерархическую структуру. Я уже писал о том, что по причине того, что моя библиотека прячет мьютексы за своим интерфесом, она должна предоставлять механизм проверки корректности. Т.е. если у нас есть 4 объекта — Foo a, b, c, d; Пользователь может написать код:
Про то, что любые книги говорят, мне известно. Только дело в том, что такой код у нас не пройдет ревью. Это ошибка.
L>>Нет. Правильно ответив на эти вопросы, он гарантированно напишет код, в котором дедлок будет невозможен.
L>Нужно аргументы приводить, иначе я тоже могу еще раз сказать — "задав себе эти вопросы он гарантировано сделает deadlock"
Какие тебе нужны аргументы? У нас меня , нет, все же у нас есть четкое правило — лок должен быть обоснованным и в цепочке вызовов из-под лока не должно быть других локов.
L>Длительность локов и взаимные блокировки — иррелевантны.
Не всегда.
L>Мы не можем всегда контролировать длительность локов.
Мы всегда можем их оценить.
L>А что если нужно лочить долгую процедуру?
Зачем? В смысле, так ли уж нам надо запускать долгую операцию под локом? Нельзя ли переработать архитектуру так, чтобы этого избежать?
L>А что если она еще и callback на вход получает?
Это уже нонсенс. Запускать асинхронную операцию (колбек как бы намекает) под локом? Зачем?
L>Ты тоже вот эти вот три вопроса себе задашь и все?
Мои вопросы рекурсивны, ибо вот тут
L>Или все же подумаешь о том — не лочит ли мой callback что-нибудь, он же будет вызываться под другим локом, каким будет порядок захвата мьютексов в моей программе в этом случае?
все начинается сначала.
L>>Для этого нужно в первую очередь иметь этот другой лок. Два лока подряд означает, что в одно и то же время могут взаимодействовать три и более потоков. Это уже очень, очень плохой сигнал и повод к пересмотру архитектуры. Как правило, обычно многопоточные программы можно свести к паттерну "one producer — multiple consumers/multiple producers — one consumer". При этом, за счет того, что все взаимодействие идет лишь между продьюсером и консьюмером, точек взаимодействия потоков обычно мало, а зачастую она всего лишь одна и лок требуется ровно один.
L>Вот опять — я говорю о корректности, ты говоришь о других вещах. Но раз ты так хочешь поговорить об этом, то переменную под мьютексом можно вполне рассматривать как ограниченую блокирующую очередь в которую можно положить только один элемент. Есть такой изоморфизм, между мьютексами и передачей сообщений, в параллельном программировании. Ты будешь утверждать, что producer/consumer система должна всегда обходиться одной очередью сообщений?
Их может быть сколько тебе нужно. Для обеспечения корректности работы такой системы достаточно обеспечить отсутствие возможности взаимоблокировки этих очередей.
L>>resource allocation сам по себе не вызовет дедлока. Опустим вырожденные случаи вроде DLLMain
L> resource allocation graph это вот — http://siber.cankaya.edu.tr/OperatingSystems/ceng328/node156.html
Извини. ИМХО это попытка псевдонаучным языком (ака сложно и непонятно) объяснить очевиднейший принцип образования дедлока, который сводится к банальному "цепочка блокировок закольцевалась". Вроде "изучения влияния слабополяризованного монохроматического излучения на изделия из сталепроката".
L>>А ты оверхед от всего этого фестиваля оценивал уже?
L>Пуллы мьютексов тоже вещь не новая, их часто используют, оверхед почти нулевой, вычисление индекса мьютекса — пара asm иснтрукций а дальше все так же как и в случае просто мьютекса, если объектов много, то пулл даже дешевле, так как требует создаваать меньше объектов ядра (меньше жрется nonpaged память ядра) и меньше памяти под сами мьютексы (std mutex это не только объект ядра но и какой-то state и еще padding, всего 64 байта).
А что, хеш без коллизий? Прямо так уж пара инструкций? А где сам граф хранится?
Если же делать, как я обычно делаю, мютексов нужно считанное количество — по одному на каждую точку взаимодействия Один-три на всю систему.
Здравствуйте, Lazin, Вы писали:
L>>Всегда можно прочитать инструкцию и сделать с точностью до наоборот. Какой именно из пунктов ошибочен?
L>практически все процитированное
Здравствуйте, landerhigh, Вы писали:
BFE>>Извините, но вот это "one producer — multiple consumers/multiple producers — one consumer" — простой вырожденный случай. Его вообще не имеет смысла рассматривать. BFE>>Вот, например, описание проекта над которым я сейчас работаю: есть восемь 11 моторов организованные в группы по 3, 3, 5 моторов.
L>Честно говоря, я не вижу тут врожденной необходимости в многопоточности вообще. L>Максимум — один тред для общения с моторами
Это как, если команды им следует посылать с разной (не кратной) частотой? Если команда не прошла в заданный промежуток времени, то начинать надо с команд инициализации, время выполнение которых существенно превышает необходимую скорость реакции.
L>и один тред, выдающий информацию во внешний мир — пульты, удаленные терминалы, веб-интрефейсы и так далее.
Если он один, то как он устроен? Он весит на ожидании пакета из сети или на ожидании пакета на отправку?
L>Если моторы/группы моторов сидят каждый на своем физическом интрефейсе и работа с ним возможна только в блокирующем режиме
какой режим выберете, такой и будет.
L>(правда, тогда непонятны требования к согласованности — ведь пока мотор не соизволит ответить, вы ему новую команду выдать не сможете, как ни извернитесь),
Т.е. вы хотите сказать, что это вообще не возможно? Если мотор не отвечает, значит он отсоединён. В этом случае остальные части системы должны игнорировать отсоединённое оборудование.
L>то так и быть, на каждый мотор/группу моторов по отдельному потоку.
ура!
L>Вот это и будет тот самый, классический "multiple producers — one consumer".
кто из них consumer, тот кто потребляет команды или тот, кто потребляет измеренные положения моторов?
BFE>>Положения некоторых моторов должны быть согласованы и синхронизированы. L>Я надеюсь, что вы не напрямую управляете шаговыми моторами из non-realtime OS? Через контроллер ведь, так? Или вы пытаетесь быть этим самым контроллером?
Я пишу/читаю в несколько последовательных портов, точнее 4 — три группы моторов + пульт управления. Со стороны моторов и пульта стоят контролёры, которые ими управляют.
И это не realtime комплекс, это near real-time комплекс.
Здравствуйте, B0FEE664, Вы писали:
BFE>Это как, если команды им следует посылать с разной (не кратной) частотой? Если команда не прошла в заданный промежуток времени, то начинать надо с команд инициализации, время выполнение которых существенно превышает необходимую скорость реакции.
А в чем проблема? У тебя производительность даже скромного ARMa на десять порядков превышает скорость обмена по последовательному порту. Один тред тут запросто может обслужить несколько портов, а латентность на фоне скорости обмена по интрефейсу будет просто незаметна.
L>>и один тред, выдающий информацию во внешний мир — пульты, удаленные терминалы, веб-интрефейсы и так далее. BFE>Если он один, то как он устроен? Он весит на ожидании пакета из сети или на ожидании пакета на отправку?
Может, мне и систему за тебя сразу всю написать? Про неблокирующие сокеты слышал?
L>>(правда, тогда непонятны требования к согласованности — ведь пока мотор не соизволит ответить, вы ему новую команду выдать не сможете, как ни извернитесь), BFE>Т.е. вы хотите сказать, что это вообще не возможно? Если мотор не отвечает, значит он отсоединён. В этом случае остальные части системы должны игнорировать отсоединённое оборудование.
А если мотор отвечает, но с бОльшей задержкой по сравнению с другими моторами?
L>>то так и быть, на каждый мотор/группу моторов по отдельному потоку. BFE>ура!
чего ура-то? Максимум — один тред на один порт.
L>>Вот это и будет тот самый, классический "multiple producers — one consumer". BFE>кто из них consumer, тот кто потребляет команды или тот, кто потребляет измеренные положения моторов?
Один консьюмер — эта та часть, которая связывает этот винигрет с внешним миром. Потребляет положения, иногда отдает команды. Потребитель услуг моторов.
L>>Я надеюсь, что вы не напрямую управляете шаговыми моторами из non-realtime OS? Через контроллер ведь, так? Или вы пытаетесь быть этим самым контроллером? BFE>Я пишу/читаю в несколько последовательных портов, точнее 4 — три группы моторов + пульт управления. Со стороны моторов и пульта стоят контролёры, которые ими управляют.
Какие-то странные у вас контроллеры. Зачем им постоянная частота обмена с мастером? Что за производитель/модель?
Опять же, все это не имеет отношения к обсуждаемой теме. Ты можешь создать отдельный тред на мотор/группу моторов/порт, и зачастую это банально удобно с точки зрения организации алгоритма. Но мест взаимодействия потоков у тебя... ровно одно. Там, где фронт-энд этого фестиваля обменивается данными с бек-эндом. Причем, учитывая характер данных, тут может локов вообще не понадобится. Все. Вариантов организовать дед лок просто нет.
L>1. Можно ли обойтись без лока?
Не нужно стараться уменьшать количество используемых мьютексов, мьютексы дешевы, захватываются и освобождаются очень быстро (uncontended lock/unlock мьютекса, находящегося в кэше это десяток наносекунд, если мне память не изменяет, деление 2х интов — дороже), если какой-то код/структуру данных можно сделать потокобезопасной, то часто так и нужно сделать, а потом уже узкие места, в которых может оказаться, что следующее неверно: L>3. Как минимизировать длительность лока? Желательно до одной операции?
Uncontended lock — очень дешев, contended lock — дорог. Взаимодействие между ядрами процессора в рамках сокета, это величина порядка 50ns, если сокетов несколько — то в несколько раз больше. Если код в hot path захватывает лок, то возможны такие варианты:
1. contended lock (мьютекс используется несколькими потоками и захват освобождение приводят к возникновению cache coherency трафика), латентность большая, захватывая лок на короткое время мы плаим за это тем, что вынуждены захватывать его часто (fine grained locking), намного лучше скомбинировать несколько критических секций в одну и захватывать лок на более длительное время (coarse grained lock). Пример — мы обрабаываем данные в цикле, лок захватывается на каждой итерации на короткое время (несколько сотен наносекунд). Можно захватывать его не на каждой итерации а на каждые N итераций. С ростом N мы будем платить все меньше и меньше за синхронизацию, но при привышении определенного порога — это может начать сказываться на производительности отрицательно.
2. uncontended lock (мьютекс используется эксклюзивно, одним потоком) захватывать мьютекс часто — сравнительно не дорого, но если мы будем его также захватывать на более длительный интервал времени, то ничего страшного не произойдет, так как поток большую часть времени все равно владеет им в единоличном порядке.
(offtopic: очень сложно цитировать человека с ником, начинающимся с той же буквы что и твой)
L>А вот тут — стоп. Когда я вызываю какой-то код под локом, это означает, что у меня есть потенциальное взаимодействие двух потоков. Если оказывается, что этот код может попытаться получить другой лок, это означает, что взаимодействие распространяется на потенциально неограниченное количество потоков. Это уже само по себе нонсенс и означает, что лок рано или поздно выстрелит. И заранее протестировать динамическую систему на гарантированное отсутствие лока в общем случаее невозможно.
Можно, если правильно ее проектировать. (тут должен быть очередной рассказ про иерархии блокировок)
Еще раз — локов не должно быть мало, их должно быть столько, сколько нужно. Впялить мьютекс в каждый объект — нормальная практика. Плохо не тогда, когда мьютексов слишком много, плохо становится тогда, когда их мало и они постоянно лочатся/анлочатся из нескольких ядер. Это называется lock contention. Плохо когда локи не организованы в иерархию и могут создать цикл (решается правильным проектированием). Все.
L>Я одно время копал в этом направлении. Например, если у меня есть подозрение, что некий код содержит потенциальный дедлок, я могу специально организовать юнит-тест, который его вызовет. Но, в общем случае невозможно создать автотест, который будет гарантировать отсутствие дедлока.
В общем случае — нет, это сводится к "halting problem". Но у меня не общий случай, я спрашивал о том, как динамически проверить отсутствие циклов на уровне ***LockLayer-ов.
L>Еще раз — я всегда пытаюсь сводить межпоточное взаимодействие исключительно к однонаправленному чтению или записи. Никаких графов вызовов, особенно в другие потоки, из-под локов быть не должно. Мое мнение — наличие такого графа есть признак ошибки проектирования.
"Пытаюсь" — подходящее для этого слово, жизнь многогранна
L>Извини. ИМХО это попытка псевдонаучным языком (ака сложно и непонятно) объяснить очевиднейший принцип образования дедлока, который сводится к банальному "цепочка блокировок закольцевалась". Вроде "изучения влияния слабополяризованного монохроматического излучения на изделия из сталепроката".
Я пытаюсь о конкретной задаче разговаривать, resource allocation graph — вполне конкретная вещь, которую используют для анализа этих самых "цепочек блокировок".
L>А что, хеш без коллизий? Прямо так уж пара инструкций? А где сам граф хранится?
Я же говорил уже что хэш с коллизиями. Разные объекты могут хэшироваться на один и тот же мьютекс, отсюда требование к отсутствию рекурсинвых блокировок.
L>Если же делать, как я обычно делаю, мютексов нужно считанное количество — по одному на каждую точку взаимодействия Один-три на всю систему.
Ты сам себе противоречишь, то мьютексов должно быть мало — 1-3 (coarse grained locking), то они должны захватываться часто (fine grained locking). Может у меня сервер с 24-мя ядрами и гипертрейдингом, один-три лока на всю систему нужно использовать?
L>>А где сам граф хранится?
Пока нигде. Я думал хранить отдельные ноды графа в TLS и строить его динамически, но пока не придумал как конкретно это делать.
resource allocation graph это вот — http://siber.cankaya.edu.tr/OperatingSystems/ceng328/node156.html
