Здравствуйте, landerhigh, Вы писали:

BFE>>Если никакая из ниток не пытается одновременно залочить более одного мьютекса, то никакой deadlock невозможен.
L>Если любая нитка может общаться с любой другой ниткой, то дедлок весьма возможен даже в этом случае. Нарисуй картинку

Давайте вы нарисуете картинку, потому что мне очень трудно нарисовать то, чего быть не может

Здравствуйте, sokel, Вы писали:

S>

S>void DeadlockDetector::on_lock(LockLayerImpl& layer, size_t hash) {
S>

Хотя multiple-lock одного слоя можно делать только через один guard, т.е. надо проверку независимо от hash делать, не на уровне lock-layer::lock, а на уровне guard::lock (hash-order блокировок в multiple quard'е проверять не надо).

L>Во-первых, что это за 1000 объектов? Почему они доступны сразу всем потокам? Почему нельзя их разделить и передать потокам в эксклюзивоное пользование? Нельзя ли поручить общение с этим объектами одному потоку? И так далее...

Многопоточный TCP сервер, работающий с неким набором объектов, допустим это счетчики (допустим, их количество фиксировано, для простоты), есть запрос на увеличение значения счетчика(ов) и запрос на чтение, при этом данные должны быть целостными (т.е. вариант — писать все команды на изменение в лог и потом применять — не катит), есть требование sequential consistency.

я напишу обработчики как-то так:

void on_update(Query& q, Response& r) {
    Counter& cnt = counters[q.id];  // shared state, контейнер не меняется, объекты Counter - могут меняться
    std::lock_guard<std::mutex> g(cnt.mutex);
    cnt.add(q.value);
    r.set_result(cnt.value);  // возвращаем обновленное значение
}

void on_read(Query& q, Response& r) {
    Counter const& cnt = counters[q.id];
    std::lock_guard<std::mutex> g(cnt.mutex);
    r.set_result(cnt.value);  // возвращаем содержимое счетчика
}

Обработчики могут вызываться из кучи разных потоков, разными клиентскими соединениями. Объектов Counter у нас много и contention низкий, т.е. как правило разные потоки захватывают разные счетчики не мешая друг другу. Можно ввести небольшой oversubscription (потоков больше чем ядер) и все буедт загружено очень хорошо. Дедлок тут возникнуть не может, по очевидным причинам. Вложенные блокировки могут быть полезны (мы, например, можем захотеть залочить объект — соединение(aka сокет), между получением запроса и отправкой ответа на него, так как в этот сокет могут приходить другие запросы, пока мы обрабатываем текущий и они могут начать обрабатываться в другом потоке (допустим это event based server с пуллом потоков).

L>Почему они доступны сразу всем потокам?
Мы не знаем заранее кому какой объект нужен.

L>Почему нельзя их разделить и передать потокам в эксклюзивоное пользование?
Из-за балансировки нагрузки. Если расшардить счетчики между потоками, можно получить ситуацию, когда один из потков будет загружен (там находится часто используемый счетчик), а другие недогружены.

L>Нельзя ли поручить общение с этим объектами одному потоку?
Лишние накладные расходы — roundtrip между двумя ядрами, вместо того, чтобы захватить uncontended mutex, это раз. Sequential consistency это два (нельзя положить команду на обновление счетчика в очередь, в надежде на то, что этот специальный поток все сделает, так как как за запросом на обновление счетчика может следовать запрос на чтение и он должен вернуть правильный результат).

S>Хотя можно и на месте можно lock-free получать факт deadlock'а потенциального с двумерным массивом. Предположим два потока одновременно регистрируют взаимно невозможные переходы layer1-layer2 и layer2-layer1. Нужно упорядочить регистрацию переходов. Для этого просто будем использовать половину матрицы, т.е. оба перехода фиксируем в переменной transitions[1][2] (упорядочиваем индексы). Прямой переход — значение 1, обратный переход — значение 2. Ну и дальше atomic CAS, допустимы изменения 0-1, 1-1, 0-2, 2-2. При фиксации попыток изменений 1-2 или 2-1 сигнализируем deadlock.


С матрицей есть одна проблема — ее проблематично ресайзить.

Здравствуйте, landerhigh, Вы писали:

L>>>Архитектура, принципиально допускающая образование дедлоков, не может быть правильным решением какой бы то ни было задачи.
BFE>>Я так понимаю, что правильно написанная deadlock-prevention библиотека гарантирует отсутствие дедлоков.
L>Нет. Она не может такого гарантировать. Она не может предотвращать дедлоки. Они может их обнаруживать.
Раз можем обнаружить, значит можем и предотвратить, так как после обнаружения мы можем произвести обработку сложившейся ситуации.

L>В самом лучшем случае, допустим, что мы такую библиотеку написали. Система в продакшене. Допустим, эта библиотека обнаружила дедлок.
L>Что она должна сделать?
Мне очевидно, надеюсь, что и вам тоже (хотя, судя по соседней ветке это не так), что дедлоки возможны только тогда, когда одна нитка должна залочить одновременно два или более мьютексов. Такой алгоритм имеет смысл, только в том случае, когда у нас есть данные, которые должны быть изменены синхронно.
Классический пример — перевод денег:
залочили первый счёт, списали деньги,
залочили второй счёт, добавили туда списанные деньги,
разлочили второй счёт,
разлочили первый счёт.
Очевидно, что здесь возможен классический дедлок.
Если мы обнаружили дедлок в какой либо нитке, то эта нитка должна восстановить предыдущее состояние тех данных, которые были защищены мьютексом, разлочить все мьютексы, после чего повторить попытку. Если мы применяем RAII, то можно бросить исключение и поймать его выше всех локов, после чего повторить попытку.

Замечу, что если у каждого счёта есть свой мьютекс, то мы можем параллельно проводить очень много переводов, которые иногда (редко, при большом числе счётов) будут "откатываться" и проводиться не с первой попытки. Если же мы все операции запишем в одну очередь, то мы сведём нашу многопоточную систему к одному исполняемому потоку, чем сильно замедлим всю систему.

Здравствуйте, Lazin, Вы писали:

S>>Хотя можно и на месте можно lock-free получать факт deadlock'а потенциального с двумерным массивом. Предположим два потока одновременно регистрируют взаимно невозможные переходы layer1-layer2 и layer2-layer1. Нужно упорядочить регистрацию переходов. Для этого просто будем использовать половину матрицы, т.е. оба перехода фиксируем в переменной transitions[1][2] (упорядочиваем индексы). Прямой переход — значение 1, обратный переход — значение 2. Ну и дальше atomic CAS, допустимы изменения 0-1, 1-1, 0-2, 2-2. При фиксации попыток изменений 1-2 или 2-1 сигнализируем deadlock.


L>С матрицей есть одна проблема — ее проблематично ресайзить.

Можно заранее ограничить число слоёв. Либо рассчитывать на вызов первого лока только после создания всех слоёв. Либо держать ссылки на состояния переходов в thread-local контейнере, инициализируя под блокировкой при отсутствии.

L>>Почему нельзя их разделить и передать потокам в эксклюзивоное пользование?
L>>Нельзя ли поручить общение с этим объектами одному потоку?

Мне кажется, lock per object здесь самый простой вариант. Все остальные привносят сложность. Расшардить счсетчики между потоками — добавляем сложность шардирования. Отдельный поток работающий с счетчиками — добавляем сложность взаимодействия между потоком сервера и этим отдельным потоком. Неужели это не очевидно?

Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, landerhigh, Вы писали:

L>>Нет. Она не может такого гарантировать. Она не может предотвращать дедлоки. Они может их обнаруживать.
BFE>Раз можем обнаружить, значит можем и предотвратить, так как после обнаружения мы можем произвести обработку сложившейся ситуации.

Поздно уже предотвращать. Система в продакшене. Дедлок выстрелил, заслонка зависла в открытом положении, самолет упал, электростанция взорвалась.

L>>В самом лучшем случае, допустим, что мы такую библиотеку написали. Система в продакшене. Допустим, эта библиотека обнаружила дедлок.
L>>Что она должна сделать?
BFE>Мне очевидно, надеюсь, что и вам тоже (хотя, судя по соседней ветке это не так), что дедлоки возможны только тогда, когда одна нитка должна залочить одновременно два или более мьютексов.

О чем я и говорю. Гораздо проще архитектурными решениями гарантировать отсутствие локов под локами, нежели пытаться искать черную кошку там, где ее нет.

BFE>Такой алгоритм имеет смысл, только в том случае, когда у нас есть данные, которые должны быть изменены синхронно.
BFE>Классический пример — перевод денег:

Перевод денег делается транзакциями с подтверждениями, а не локами с мьютексами.

BFE>Если мы обнаружили дедлок в какой либо нитке, то эта нитка должна восстановить предыдущее состояние тех данных, которые были защищены мьютексом, разлочить все мьютексы, после чего повторить попытку.

Ты хочешь вернуть систему в предыдущее состояние. Это в общем случае уже невозможно. Файл уже удален, заслонка открыта, газ идет, состояние (текщее и предыдущее) других ниток неизвестно, куда откатываться, непонятно, да и просто так закрыть заслонку нельзя.

BFE>Если мы применяем RAII, то можно бросить исключение и поймать его выше всех локов, после чего повторить попытку.

Единственный более-менее приемлимый вариант — упасть с дампом. Что тоже очень плохо, но лучше зависания.

Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, landerhigh, Вы писали:

BFE>>>Если никакая из ниток не пытается одновременно залочить более одного мьютекса, то никакой deadlock невозможен.
L>>Если любая нитка может общаться с любой другой ниткой, то дедлок весьма возможен даже в этом случае. Нарисуй картинку

BFE>Давайте вы нарисуете картинку, потому что мне очень трудно нарисовать то, чего быть не может

Давай не будем на "вы", ок?

ты совершенно прав, подобная схема сама по себе дедлок вызвать не сможет. Это у меня моск рисовал странные графы в подсознании.
В ней возможно возникновение софт-локов (все треды ломанулись лочить один и тот же мьютекс), что по последствиям может быть примерно столь же катастрофично, как и дедушка лок. Однако, архитектурные ошибки и ошибки разработки (например, религиозное неприятие RAII и как следствие неснятый лок из-за удачного вылета исключения или пренебрежение рекомендацией не пользоваться suspend/terminate thread) выведут даже такую систему в состояние, когда она рано или даже раньше заблокируется. И превентивно отловить это никакими детекторами будет нельзя.
Именно поэтому в вопросе предотвращения дедлоков я ставлю архитектуру на первое, второе и так далее до десятого мест, а детекторы вообще никуда не ставлю.

Здравствуйте, landerhigh, Вы писали:

L>>>Нет. Она не может такого гарантировать. Она не может предотвращать дедлоки. Они может их обнаруживать.
BFE>>Раз можем обнаружить, значит можем и предотвратить, так как после обнаружения мы можем произвести обработку сложившейся ситуации.
L>Поздно уже предотвращать. Система в продакшене. Дедлок выстрелил, заслонка зависла в открытом положении, самолет упал, электростанция взорвалась.
Можно предотвратить заранее. Цена — не оптимальный алгоритм.

L>>>В самом лучшем случае, допустим, что мы такую библиотеку написали. Система в продакшене. Допустим, эта библиотека обнаружила дедлок.
L>>>Что она должна сделать?
BFE>>Мне очевидно, надеюсь, что и вам тоже (хотя, судя по соседней ветке это не так), что дедлоки возможны только тогда, когда одна нитка должна залочить одновременно два или более мьютексов.
L>О чем я и говорю. Гораздо проще архитектурными решениями гарантировать отсутствие локов под локами, нежели пытаться искать черную кошку там, где ее нет.
Да? Вот здесь

Автор: landerhigh
Дата: 27.06.14

вы говорите нечто противоположное.

BFE>>Такой алгоритм имеет смысл, только в том случае, когда у нас есть данные, которые должны быть изменены синхронно.
BFE>>Классический пример — перевод денег:
L>Перевод денег делается транзакциями с подтверждениями, а не локами с мьютексами.
Ну транзакция изнутри как устроена?

BFE>>Если мы обнаружили дедлок в какой либо нитке, то эта нитка должна восстановить предыдущее состояние тех данных, которые были защищены мьютексом, разлочить все мьютексы, после чего повторить попытку.
L>Ты хочешь вернуть систему в предыдущее состояние. Это в общем случае уже невозможно. Файл уже удален, заслонка открыта, газ идет, состояние (текщее и предыдущее) других ниток неизвестно, куда откатываться, непонятно, да и просто так закрыть заслонку нельзя.
Ну так надо с умом программу писать-то. Чем это ситуация отличается от брошенного исключения? Файл уже удален, заслонка открыта, газ идет...

BFE>>Если мы применяем RAII, то можно бросить исключение и поймать его выше всех локов, после чего повторить попытку.
L>Единственный более-менее приемлимый вариант — упасть с дампом. Что тоже очень плохо, но лучше зависания.
Упасть — это не вариант.

Здравствуйте, Lazin, Вы писали:

L>>Во-первых, что это за 1000 объектов? Почему они доступны сразу всем потокам? Почему нельзя их разделить и передать потокам в эксклюзивоное пользование? Нельзя ли поручить общение с этим объектами одному потоку? И так далее...

L>Многопоточный TCP сервер, работающий с неким набором объектов,

Можно сразу вопросы? Почему многопоточный? Один поток на клиента или число потоков равно числу ядер? Какая задача решается? Крайне высокая нагрузка? Если так, то как она соотносится с ограниченной пропускной способностью сети?

L> допустим это счетчики (допустим, их количество фиксировано, для простоты), есть запрос на увеличение значения счетчика(ов) и запрос на чтение, при этом данные должны быть целостными (т.е. вариант — писать все команды на изменение в лог и потом применять — не катит), есть требование sequential consistency.

Ничего необычного, но вот это

   Counter& cnt = counters[q.id];  // shared state, контейнер не меняется, объекты Counter - могут меняться
   std::lock_guard<std::mutex> g(cnt.mutex);
   cnt.add(q.value);

Я бы спрятал внутрь функции за интерфейсом и никому снаружи бы не показывал. Чтобы ничьи шаловливые ручонки не применили этот мьютекс для чего еще.

А еще лучше, я подумал бы об использовании атомиков и выкинул блокировки бы совсем.

L>Обработчики могут вызываться из кучи разных потоков, разными клиентскими соединениями. Объектов Counter у нас много и contention низкий, т.е. как правило разные потоки захватывают разные счетчики не мешая друг другу. Можно ввести небольшой oversubscription (потоков больше чем ядер) и все буедт загружено очень хорошо. Дедлок тут возникнуть не может, по очевидным причинам.

Ну так я же и обозначил это правило — граф вызовов под блокировкой не заходит в другой лок. Более того, там и графа-то никакого нет.

L>Вложенные блокировки могут быть полезны (мы, например, можем захотеть залочить объект — соединение(aka сокет), между получением запроса и отправкой ответа на него, так как в этот сокет могут приходить другие запросы, пока мы обрабатываем текущий и они могут начать обрабатываться в другом потоке (допустим это event based server с пуллом потоков).

Это уже даже звучит некрасиво

L>>Почему нельзя их разделить и передать потокам в эксклюзивоное пользование?
L>Из-за балансировки нагрузки. Если расшардить счетчики между потоками, можно получить ситуацию, когда один из потков будет загружен (там находится часто используемый счетчик), а другие недогружены.

Да неужели нагрузка действительно такая дикая, что ее нужно балансировать? Вот хоть убей, но мне кажется, что со всем этим фестивалем справился бы один поток. Ну а каждое соединение можно в корутину засунуть, чтобы вообще все шоколадно было.

Здравствуйте, B0FEE664, Вы писали:

L>>Поздно уже предотвращать. Система в продакшене. Дедлок выстрелил, заслонка зависла в открытом положении, самолет упал, электростанция взорвалась.
BFE>Можно предотвратить заранее. Цена — не оптимальный алгоритм.

Нельзя. Если система заходит в дедлок, то боржоми пить уже поздно.

BFE>>>Классический пример — перевод денег:
L>>Перевод денег делается транзакциями с подтверждениями, а не локами с мьютексами.
BFE>Ну транзакция изнутри как устроена?

Это неважно. Важно то, что на верхнем уровне мы имеем дело с транзакцией, а не блокировками счетов.

L>>Ты хочешь вернуть систему в предыдущее состояние. Это в общем случае уже невозможно. Файл уже удален, заслонка открыта, газ идет, состояние (текщее и предыдущее) других ниток неизвестно, куда откатываться, непонятно, да и просто так закрыть заслонку нельзя.
BFE>Ну так надо с умом программу писать-то.

Вот именно. Писать надо с умом. В первую очередь так, чтобы статическая структура программы не допускала дедлоков (пресловутые не более одной блокировки в графе вызовов). Потому что обнаруживать их в рантайме уже крайне поздно.

BFE>Чем это ситуация отличается от брошенного исключения? Файл уже удален, заслонка открыта, газ идет...

Примерно всем. Исключение понятно как обработать. А дедлок? Что с ним делать? Вернуться назад? Куда назад? Никакого "назад" уже нет, начатая операция необратима, данные уже нерелевантны, остальные потоки ушли далеко вперед, а реактор уже кипит-с, можно только продолжать, а лок занят и освобождаться не собирается. Да даже если операция и обратима, то откатывать надо не только залипший тред, но надо размотать весь остальной клубок блокировок. разматывалки не хватит, да и исполнительные устройства могут отказаться разматываться на полпути.

BFE>>>Если мы применяем RAII, то можно бросить исключение и поймать его выше всех локов, после чего повторить попытку.
L>>Единственный более-менее приемлимый вариант — упасть с дампом. Что тоже очень плохо, но лучше зависания.
BFE>Упасть — это не вариант.

А заклинившая педаль газа, упавший самолет и взорвавшийся реактор — вариант?

не читал весь стрим, но у java есть такая штука:
http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/util/concurrent/CycleDetectingLockFactory.html

возможно вы захотите реализовать подобное для C++

Здравствуйте, Lazin, Вы писали:

L>Навелосипедил небольшую бибилотеку синхронизации, с целью проверить кое что — https://github.com/Lazin/Syncope
L>Там есть описание на rungilsh-е, идея очень простая на самом деле. Вместо того, чтобы добавлять мьютексы как поля в объекты, можно использовать внешний массив (пулл) мьютексов. Когда мы хотим залочить объект — мы берем его адрес, вычисляем простой хэш и используем его для получения мьютекса из пулла, после чего захватываем его. Для того, чтобы это работало без дедлоков, нужно чтобы была подходящая иерархия локов в программе. Вот такой вот массив может использоваться только на одном уровне иерархии.

Кстати, ошибочка одна вот, массив хэшей в guard many мало отсортировать... Надо ещё повторения выкинуть.

            std::sort(hashes_.begin(), hashes_.end());
            hash_array::iterator it = std::unique(hashes_.begin(), hashes_.end());
            hash_count_ = std::distance(hashes_.begin(), it);

Ну и блокировать только то, что отсеялось:

        void lock() {
            for(int i = 0; i < hash_count_; ++i) {
                std::cout << "lock " << i << std::endl;
                impl_.lock(hashes_[i]);
            }
            owns_lock_ = true;
        }

        void unlock() {
            for(int i = hash_count_ - 1; i >= 0; --i) {
                std::cout << "unlock " << i << std::endl;
                impl_.unlock(hashes_[i]);
            }
            owns_lock_ = false;
        }

L>>Многопоточный TCP сервер, работающий с неким набором объектов,

L>Можно сразу вопросы? Почему многопоточный? Один поток на клиента или число потоков равно числу ядер? Какая задача решается? Крайне высокая нагрузка? Если так, то как она соотносится с ограниченной пропускной способностью сети?

Пулл потоков. Пропускная способность сети — вещь вообще иррелевантная для данного примера. Пропускная способность такого сервера будет зависет от латентностей разных подсистем, в том числе и времени обработки запроса. Когда какой-нибудь программист говорит о том, что сервис упирается в сеть, очень часто он упирается не в ее пропускную способность Но это уже тема для отдельного разговора и отношения к вопросу не имеет.

L>Я бы спрятал внутрь функции за интерфейсом и никому снаружи бы не показывал. Чтобы ничьи шаловливые ручонки не применили этот мьютекс для чего еще.
L>А еще лучше, я подумал бы об использовании атомиков и выкинул блокировки бы совсем.

А что если в одном запросе нужно обновлять сразу несколько счетчиков? Вот сразу и атомики не подходят и в том что мьютекс торчит наружу нет ничего плохого

L>Ну так я же и обозначил это правило — граф вызовов под блокировкой не заходит в другой лок. Более того, там и графа-то никакого нет.

Ну так мы же вроде не это обсуждаем, а твое утверждение о том, что меньше мьютексов тем лучше.

L>Да неужели нагрузка действительно такая дикая, что ее нужно балансировать? Вот хоть убей, но мне кажется, что со всем этим фестивалем справился бы один поток. Ну а каждое соединение можно в корутину засунуть, чтобы вообще все шоколадно было.

Простой пример — один горячий элемент, который обновляют все кому не лень. Есть такая задача в параллельном програмировании — зоопарк Шредингера, есть список животных живущих в зоопарке, клиенты могут запрашивать информацию о них, но почему то чаще всего запрашивают информацию о коте Шредингера

S>Кстати, ошибочка одна вот, массив хэшей в guard many мало отсортировать... Надо ещё повторения выкинуть.

Да, там просто раньше были рекурсивные мьютексы.

S>

S>            std::sort(hashes_.begin(), hashes_.end());
S>            hash_array::iterator it = std::unique(hashes_.begin(), hashes_.end());
S>            hash_count_ = std::distance(hashes_.begin(), it);

S>

S>Ну и блокировать только то, что отсеялось:
S>

S>        void lock() {
S>            for(int i = 0; i < hash_count_; ++i) {
S>                std::cout << "lock " << i << std::endl;
S>                impl_.lock(hashes_[i]);
S>            }
S>            owns_lock_ = true;
S>        }

S>        void unlock() {
S>            for(int i = hash_count_ - 1; i >= 0; --i) {
S>                std::cout << "unlock " << i << std::endl;
S>                impl_.unlock(hashes_[i]);
S>            }
S>            owns_lock_ = false;
S>        }
S>

Может отправишь pull request?

S>Хотя можно и на месте можно lock-free получать факт deadlock'а потенциального с двумерным массивом. Предположим два потока одновременно регистрируют взаимно невозможные переходы layer1-layer2 и layer2-layer1. Нужно упорядочить регистрацию переходов. Для этого просто будем использовать половину матрицы, т.е. оба перехода фиксируем в переменной transitions[1][2] (упорядочиваем индексы). Прямой переход — значение 1, обратный переход — значение 2. Ну и дальше atomic CAS, допустимы изменения 0-1, 1-1, 0-2, 2-2. При фиксации попыток изменений 1-2 или 2-1 сигнализируем deadlock.

Я сейчас начал реализовывать эту идею (после первого прочтения неправильно понял). Можно же сделать достаточно большой массив заранее и не нужно будет ничего ресайзить, ну и там действительно можно обойтись одним CAS-ом.

Здравствуйте, Lazin, Вы писали:

L>Пулл потоков. Пропускная способность сети — вещь вообще иррелевантная для данного примера.

Вобще-то это самый первый вопрос, который возникает при такой разработке.

L>Пропускная способность такого сервера будет зависет от латентностей разных подсистем, в том числе и времени обработки запроса. Когда какой-нибудь программист говорит о том, что сервис упирается в сеть, очень часто он упирается не в ее пропускную способность

А еще нередко какой-нибудь программист норовит применить алгоритм с O(n^n) там, где просится O(1)

L>Но это уже тема для отдельного разговора и отношения к вопросу не имеет.

Имеет, т.к. пока непонятно, из каких требований отросло требование именно многопоточности. Любое решение должно быть обосновано, и часто бывает, что архитектурные решения принимаются из ошибочных исходных данных или ошибочных представлениях о требованиях.

L>>Я бы спрятал внутрь функции за интерфейсом и никому снаружи бы не показывал. Чтобы ничьи шаловливые ручонки не применили этот мьютекс для чего еще.
L>>А еще лучше, я подумал бы об использовании атомиков и выкинул блокировки бы совсем.

L>А что если в одном запросе нужно обновлять сразу несколько счетчиков? Вот сразу и атомики не подходят и в том что мьютекс торчит наружу нет ничего плохого

А в чем проблема? Data continuity никаким образом не нарушается. Хочешь транзакций с изоляциями? А оно тебе надо? (не обижайся, я всегда такие вопросы задаю, в 90% случаев оказывается, что на самом деле не надо. Не следует пытаться сделать больше, чем требуется.) Если надо, то так бы сразу и сказал. Но это уже совсем другая история, не так ли? Я правильно понимаю, что ты хочешь захватить сразу все локи, и только потом обновлять? Ну так это же прямой путь к дедлоку, как только залетит дятел и порядок блокировки будет нарушен.

L>>Ну так я же и обозначил это правило — граф вызовов под блокировкой не заходит в другой лок. Более того, там и графа-то никакого нет.

L>Ну так мы же вроде не это обсуждаем, а твое утверждение о том, что меньше мьютексов тем лучше.

Вообще-то это скорее так, нежели нет. Смотри выше.

L>>Да неужели нагрузка действительно такая дикая, что ее нужно балансировать? Вот хоть убей, но мне кажется, что со всем этим фестивалем справился бы один поток. Ну а каждое соединение можно в корутину засунуть, чтобы вообще все шоколадно было.

L>Простой пример — один горячий элемент, который обновляют все кому не лень. Есть такая задача в параллельном програмировании — зоопарк Шредингера, есть список животных живущих в зоопарке, клиенты могут запрашивать информацию о них, но почему то чаще всего запрашивают информацию о коте Шредингера

Видишь ли в чем дело. Ты пока не обосновал необходимость многопоточности. Если все, что твой сервис должен делать — это на запросы справляться о здоровье кота Шредингера, то вопрос о пропускной способности очереди клиентов нужно рассматривать первым. Учитывая имеющиеся входные данные, я пока вижу, что твой сервис в любом случае будет успевать отработать быстрее, нежели следующий запрос успеет прийти и быть обработанным сетевой подсистемой. Короче, один поток справится только в путь.

S>Хотя можно и на месте можно lock-free получать факт deadlock'а потенциального с двумерным массивом. Предположим два потока одновременно регистрируют взаимно невозможные переходы layer1-layer2 и layer2-layer1. Нужно упорядочить регистрацию переходов. Для этого просто будем использовать половину матрицы, т.е. оба перехода фиксируем в переменной transitions[1][2] (упорядочиваем индексы). Прямой переход — значение 1, обратный переход — значение 2. Ну и дальше atomic CAS, допустимы изменения 0-1, 1-1, 0-2, 2-2. При фиксации попыток изменений 1-2 или 2-1 сигнализируем deadlock.

Правда так можно только deadlock первого порядка отловить, чтобы отловить deadlock N-ого порядка, нужно проверить N^2 таких переходов (если N это глубина стека вызовов).

BFE>Классический пример — перевод денег:
BFE>залочили первый счёт, списали деньги,
BFE>залочили второй счёт, добавили туда списанные деньги,
BFE>разлочили второй счёт,
BFE>разлочили первый счёт.
BFE>Очевидно, что здесь возможен классический дедлок.

элементарно же:
1) лочим оба счета в однозначно определяемом порядке (типа сначала с меньшим номером и т.п.)
2) переводим деньги
3) разлочиваем в обратном порядке

эту странную ситуацию — когда двум тредам нужно залочить два объекта ну обязательно в разном порядке — вряд ли невозможно подобным простым образом исключить