Tree structures and threads

Question

I have a speed critical multithreaded program which involves data in a tree structure. Implemented as follows:

Click to copy

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];

The program enters and leaves critical sections controlled by node_critsec[]. So when I need to process interesting_info_A/B/C of node n then I enter the critical section of that node (node_critsec[n]), do my processing and then leave. The program meanders around the tree taking all sorts of complex paths following links to parents and children. The program will also grow the tree, i.e. add new nodes and modify the parent/children links of other nodes accordingly (the tree never shrinks). I try and ensure that each thread only ever locks one node at a time to avoid the risk of deadlocks. But then I have a problem- if I'm adding a new node then I may want to lock the node's parent so that I can adjust its list of children. Getting this to all to work without either deadlocks or two threads attempting to modify data in the same node is getting to be a bit of a nightmare. Is there some guiding principle I should be following about when and which nodes to lock/unlock that I should be following - or do I just have to be super-smart and work out every permutation of events that can occur?

Answer 1

A simple rule: to avoid deadlock when locking multiple items always lock them in the same order everywhere. So if you have items A, B, C, and D you should always lock them in, say, alphabetical order and no other. If you've locked C and decide that you need B, then you have to release C and then lock B and re-lock C.

In a tree, I suppose, you could always lock from the top, down. If you need to lock a parent then release and re-acquire the locks as needed.

There are other schemes that work just as well, but this one's straightforward.

Edit: You can read a little about it here.

Answer 2

If growing the tree is relatively uncommon, one possibility would be to use a read/write lock that allows multiple readers but only one writer. Use a single R/W lock to lock the tree itself during traversal (acquire the read lock). Any number of threads could do this. When a thread needed to add a new node, it would acquire the write lock. This would block all readers for the duration of the update. Note that you would probably need to set up the read/write lock to give precedence to writers to avoid starving them.

Using that mechanism would eliminate the need for a single thread to acquire multiple critical sections for individual nodes and thus simplify the process.