У меня есть большая древовидная структура, над которой несколько потоков работают одновременно. Идеально, я хотел бы иметь отдельную взаимоисключающую блокировку для каждой ячейки.
Я посмотрел на определение pthread_mutex_t
в bits/pthreadtypes.h
и это довольно коротко, таким образом, использование памяти не должно быть проблемой в моем случае.
Однако есть ли любая потеря производительности при использовании многих (скажем, несколько тысяч) отличающийся pthread_mutex_t
s только для 8 потоков?
Если вы очень часто блокируете и разблокируете, может возникнуть штраф, поскольку получение и снятие блокировок занимает некоторое время и может занять изрядное количество времени, если замки оспариваются.
При использовании большого количества блокировок в такой структуре вам нужно будет очень точно указать, что именно блокирует каждая блокировка, и позаботиться о взаимоблокировках AB-BA. Например, если вы изменяете структуру дерева во время операции блокировки, вам необходимо заблокировать все узлы, которые будут изменены, в согласованном порядке и убедиться, что потоки, работающие с потомками, не запутались.
Если у вас очень большое количество блокировок, распределенных по памяти, проблемы с кешированием могут вызвать проблемы с производительностью, в зависимости от архитектуры, поскольку операции блокировки обычно делают недействительными по крайней мере некоторую часть кеша.
Лучше всего, вероятно, реализовать простую структуру блокировки, затем профилировать ее, а затем, если необходимо, улучшить ее производительность. Я не уверен, что вы делаете с деревом, но хорошим местом для начала может быть одна блокировка чтения-записи для всего дерева, если вы ожидаете читать гораздо больше, чем обновляете.
«Мы должны забыть о небольшой эффективности, скажем, примерно в 97% случаев: преждевременная оптимизация - корень всех зол». - Дональд Кнут
Чтобы правильно оценить это, необходимо указать ваши схемы блокировки/доступа. Если каждый поток будет держать только одну или несколько блокировок одновременно, и вероятность того, что два или более потока захотят получить одну и ту же блокировку одновременно, мала (либо случайный доступ, либо 8 бегунов на разных позициях на круговой дорожке, бегущих примерно с одинаковой скоростью, либо другие более сложные вещи), то вы в основном избежите худшего случая, когда поток должен спать, чтобы получить блокировку (или в некоторых случаях придется привлекать ОС, чтобы решить, кто победит), потому что у вас так мало потоков и так много блокировок.
Если каждый поток может захотеть получить сотни или тысячи блокировок в любой момент времени, тогда ситуация начнет меняться.
Я не буду касаться предотвращения тупиковых ситуаций, потому что я ничего не знаю о контейнере, который вы используете, но вы должны знать о необходимости их избегать.