Древовидные структуры и потоки
У меня есть скорость критическая многопоточная программа, которая вовлекает данные в древовидную структуру. Реализованный следующим образом:
typedef struct
{
// data pertaining to linkages, defining the architecture of the tree
int parent_node;
int child_node[MAX_CHILD_NODES];
int number_of_children;
// data pertaining to info at each node
float interesting_info_A;
char interesting_info_B[STRING_LEN];
long interesting_info_C;
}
node_type;
node_type node[MAX_NUMBER_OF_NODES];
CRITICAL_SECTION node_critsec[MAX_NUMBER_OF_NODES];
Программа вводит и оставляет критические разделы управляемыми node_critsec []. Таким образом, когда я должен обработать interesting_info_A/B/C узла n затем, я ввожу критический раздел того узла (node_critsec [n]), сделайте мою обработку и затем уезжайте. Извилины программы вокруг дерева, берущего все виды следующих ссылок сложных контуров на родителей и детей. Программа также вырастит дерево, т.е. добавит новые узлы и изменит ссылки родителя/детей других узлов соответственно (дерево никогда не уменьшается). Я пытаюсь удостовериться, что каждый поток только когда-либо блокирует один узел за один раз для предотвращения риска мертвых блокировок. Но затем у меня есть проблема - если я добавляю новый узел затем, я могу хотеть заблокировать родителя узла так, чтобы я мог скорректировать его список детей. Получение этого ко всем для работы или без мертвых блокировок или без двух потоков, пытающихся изменить данные в том же узле, добирается, чтобы быть определенным кошмаром. Есть ли некоторый руководящий принцип, за которым я должен неотступно следовать, за когда и какими узлами блокировать/разблокировать это я должен следовать - или я должен просто быть суперумным и разработать каждую перестановку событий, которые могут произойти?
3 ответа
Простое правило: чтобы избежать взаимоблокировки при блокировке нескольких элементов, всегда блокируйте их везде в одном и том же порядке. Поэтому, если у вас есть элементы A, B, C и D, вы всегда должны блокировать их, скажем, в алфавитном порядке, а не в другом. Если вы заблокировали C и решили, что вам нужен B, то вы должны отпустить C, а затем заблокировать B и повторно заблокировать C.
Я полагаю, что в дереве вы всегда можете заблокировать сверху вниз. Если вам нужно заблокировать родителя, отпустите и повторно установите блокировки по мере необходимости.
Есть и другие схемы, которые работают так же хорошо, но эта простая.
Правка : Вы можете немного прочитать об этом здесь .
Если рост дерева относительно редок, то можно использовать блокировку чтения/записи, которая позволяет нескольким читателям, но только одному писателю. Используйте одну блокировку R/W для блокировки самого дерева во время обхода (получение блокировки на чтение). Это может делать любое количество потоков. Когда потоку нужно добавить новый узел, он получает блокировку на запись. Это блокировало бы всех читателей на время обновления. Обратите внимание, что вам, вероятно, придется настроить блокировку чтения/записи так, чтобы приоритет отдавался писателям, чтобы избежать их голодания.
Использование этого механизма устранит необходимость в получении одним потоком нескольких критических секций для отдельных узлов и, таким образом, упростит процесс.
Это напоминает блокировку узлов в файловых системах. Если вы ищете справочный материал, вы можете проверить слои VFS в linux, BSD, open solaris, .... Однако будьте осторожны, это может быть сложный материал и, следовательно, может быть не лучшим примером для справки.
Я хотел бы добавить несколько моментов в дополнение к тем, что сделал clintp (внимательно прислушайтесь к его словам).
Возможно, стоит использовать мьютекс, чтобы заблокировать доступ ко всему дереву, когда он вам нужен, а затем разблокировать его, когда вы закончите. Хотя этот единственный поток приложения в этом критическом разделе может быть полезен для быстрого и безопасного запуска и работы. Кто знает, производительность, которую предлагает этот вариант, может быть достаточно хорошей. Если это не так, по крайней мере, это поможет вам двигаться вперед. Узкие места можно немного ослабить, если использовать семафор чтения-записи вместо мьютекса; все становится однопоточным для записи, в то время как чтение может быть одновременным.
Составьте список всех операций, которые вы хотите выполнить со своим деревом, и распределите их по категориям (чтение, запись, обновление, перемещение, переименование, удаление и т. Д.) И выясните, какую степень параллелизма вы хотите. Из того, что вы написали, вам нужно нечто большее, чем просто чтение. Вы хотите, чтобы поток A мог читать узлы, которые не заблокированы для записи потоком B? Я по своему опыту говорю, что пропуск этого шага может стоить вам много времени.
Надеюсь, это поможет.