Использование многих взаимных блокировок

Question

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

Я посмотрел на определение pthread_mutex_t в bits/pthreadtypes.h, и оно довольно короткое, поэтому использование памяти не должно быть проблемой в моем случае.

Однако, есть ли какое-то снижение производительности при использовании множества (скажем, нескольких тысяч) разных pthread_mutex_t с только для 8 потоков?

Answer 1

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

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

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

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

«Мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация - корень всего зла». - Дональд Кнут

Answer 2

Ваши шаблоны блокировки / доступа должны быть указаны, чтобы правильно оценить это. Если каждый поток будет удерживать только одну или несколько блокировок за раз, и вероятность того, что любые два или более потока захотят одну и ту же блокировку одновременно, мала (либо скороговорка произвольного доступа, либо 8 участников на разных позициях на круговой дорожке работает примерно с той же скоростью или другими более сложными вещами), тогда вы в основном избежите наихудшего случая, когда поток должен спать, чтобы получить блокировку (или в некоторых случаях задействовать ОС, чтобы решить, кто победит), потому что несколько тем и столько замков.

Если каждому потоку могут понадобиться сотни или тысячи блокировок одновременно, все начнет меняться.

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