나는 나무 구조의 데이터를 포함하는 속도가 중요한 다중 스레드 프로그램을 가지고있다.트리 구조와 스레드
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 []가 제어하는 중요 섹션에 들어가고 나가는 프로그램입니다. 그래서 노드 n의 interesting_info_A/B/C를 처리 할 필요가있을 때 그 노드 (node_critsec [n])의 임계 구역에 들어가서 처리를 수행 한 다음에 나가십시오. 이 프로그램은 나무 주위를 순회하면서 부모와 자녀와의 연결을 따라 복잡한 경로를 취합니다. 프로그램은 또한 트리를 성장 시키며, 즉 새로운 노드를 추가하고 그에 따라 다른 노드의 부모/자식 링크를 수정한다 (트리는 결코 줄어들지 않는다). 나는 각 스레드가 교착 상태의 위험을 피하기 위해 한 번에 하나의 노드 만 잠그도록하려고합니다. 그런데 문제가 생깁니다. 새 노드를 추가하는 경우 노드의 부모를 잠궈서 자식 목록을 조정할 수 있습니다. 교착 상태 또는 동일한 노드에서 데이터 수정을 시도하는 두 개의 스레드없이 모두 작업하려면이 작업을 악몽이되고 있습니다. 거기에 따라야 할 지침 원칙이 있습니까? 내가 따라야 할 노드를 잠 그거나 잠금을 해제 할 노드가 있습니까? 아니면 그냥 초능력이 있어야하고 발생할 수있는 모든 순열을 해결해야합니까?
교착 상태가 발생하는 위치를 설명 할 수 있습니까? 즉, 그래프 (나무가 아님)에 루프가 있거나 순회 중에 자물쇠를 가져 오기 전에 부모 자물쇠를 포기하지 않으면 수정하기가 매우 쉽다는 것을 의미합니다. –
내가 이해하는 한, 일부 알고리즘은 상향식으로 진행되는 반면 다른 알고리즘은 하향식으로 진행되는 식으로 진행됩니다. 나는 그가 다른 노드가 새로운 노드를 훔치거나 awry (일관성없는 상태 : parent_node가 이것을 나열하지 않는 노드로 설정 될 수 있기 때문에 부모 노드의 목록에 추가하기 전에 새로운 노드에 잠금을 유지해야한다는 의미라고 생각한다. 자식 노드). 이 데이터 구조가 최적인지는 모르겠지만이 구조와의 동기화 필요성에 대해서는 옳은 것으로 간주합니다. – gimpf
@Tyler McHenry : 저는 과거에도 불구하고 실제로 교착 상태에 빠져있는 것은 아닙니다. 내가 가지고있는 시간은 언제나 동시에 두 개의 다른 노드를 잠그고있는 스레드 중 하나로 떨어졌습니다. 내 문제는 이제 두 개의 다른 스레드가 동일한 노드 데이터를 처리하는 유형입니다. – Mick