#c #multithreading #thread-safety #binary-tree
#c #многопоточность #безопасность потоков #двоичное дерево
Вопрос:
Я довольно плохо знаком с многопоточностью и синхронизацией, и мне нужно добавить код семафора в заданный псевдокод, который позволит нескольким потокам получать доступ к многопоточному двоичному дереву с максимальным параллелизмом.
Pesudocode предоставляет структуру узла, которая содержит:
int data
node *leftchild, *rightchild, *prev, *next;
и единственная функция insert(node *root, int data) — это функция, которая ищет родительский элемент в текущем дереве, а затем вставляет новый узел (учитывая, что его еще нет в дереве) и изменяет указатели prev and next .
Я не уверен, как лучше всего реализовать семафоры. Мои первоначальные идеи:
- Блокировка / разблокировка каждого узла по мере его поиска. Это делается для предотвращения вставки других потоков во время поиска. Должен ли родительский узел также быть заблокирован?
Затем для вставки:
- Заблокируйте родительский узел и текущий узел, чтобы иметь возможность предотвратить вставку другого потока в одно и то же место в одно и то же время.
Есть ли лучший способ сделать это? (предполагая, что это даже правильно в первую очередь)
Комментарии:
1. Не уверен, что вы имеете в виду, блокируя отдельные узлы в дереве. Вы получаете блокировку для всего дерева, вставляете новое значение и снимаете блокировку. Я бы использовал не семафор, а мьютекс.
2. На ум приходит множество вопросов: насколько велико дерево? Сколько ожидается вставок и операций чтения? Что важнее для быстрого поиска или записи? Существуют ли какие-либо ограничения на высокую скорость, в режиме реального времени, или вы могли бы выполнять пакетную запись?
3. Я имею в виду, что реальный «максимальный параллелизм» обычно достигается не с помощью потоков процессора, а с помощью очередей и «легких» потоков. Примером может служить высокая производительность NodeJS. Но откуда поступают данные (и как быстро поступают новые данные), является ключом к пониманию того, даст ли это вам преимущество.
4. @AndreaLaforgia Я должен использовать семафоры как часть назначения, и я планирую просто использовать двоичный семафор для зеркального отображения блокировки мьютекса.
5. @SomeCallMeTim С данным псевдокодом, который у меня есть, и как сформулирован вопрос, я интерпретирую его как дерево произвольного размера, содержащее целые числа> = 0, неповторяющееся. Единственной функцией является функция вставки, поэтому важны вставки, а поиск выполняется только для предотвращения вставки.
Ответ №1:
В этом случае вы должны использовать блокировку чтения-записи. Блокировка отдельных узлов или частей дерева станет исключительно сложной, если вы позже решите переключить свою реализацию дерева, и тогда потребуется больше работы.
int32_t Tree_insert(Tree *tree, int32_t data) {
pthread_rwlock_wrlock(amp;tree->rwlock);
int32_t ret = insert(amp;tree->root_node, data);
pthread_rwlock_unlock(amp;tree->rwlock);
return ret;
}
Комментарии:
1. Спасибо за информацию. Это скорее гипотетический сценарий, в котором я должен использовать семафоры, чтобы разрешить нескольким потокам доступ к дереву одновременно. Я просто не уверен, является ли то, что я изначально предложил, правильным путем или нет. Я знаю, что было бы возможно (и, вероятно, более эффективно) просто заблокировать / разблокировать все дерево, чтобы вставить узел, но, к сожалению, это не является целью упражнения
2. @Caulay каковы требования к упражнению?
3. @AndreaLaforgia Я должен «использовать семафоры в псевдокоде, чтобы несколько потоков могли совместно использовать доступ к структурам данных. Ваша цель — максимизировать одновременное использование структур данных «.
4. Блокирует все дерево — не максимизирует параллелизм.