Beware of a simple list in thread programming?

Question

I am reading a POSIX multi-threaded book for some practice, and I was trying to figure out where I would need the mutex guards in a simple single list as a little practice problem. For example, if I had a list of node structures:

template <typename T> struct Node { Node<T>* next; T data; }; Node<T>* head = NULL; //Populate list starting at head... [HEAD] --> [NEXT] --> [NEXT] --> [NEXT] --> [...] --> [NULL] 

and I had two or more threads. Any stream can insert, delete, or read anywhere in the list.

It seems that if you just try to protect individual elements of the list (and not the entire list), you can never guarantee that another thread will not change the one pointed to by the following pointer *, so you cannot guarantee the safety and maintenance of invariants.

Is there a more effective way to protect this list than to do all operations with it with the same mutex? I would think that there is, but I really can’t think about it.

Also, if it was a doubly linked list, has the situation changed?

Answer 1

If you want to make a fine-grained locking approach with a singly linked list (i.e., one lock per node), you will need to do the following:

• Add two lists of sentinel elements to the list for head and tail . Both of these nodes have locks associated with them, and each new node will be added between the two of them.
• For a function that moves through the list, you need to get a lock on the next node before assigning it to the current pointer. You also cannot release the lock on the current node until you get the lock on the next node. If you also use the prev pointer to bypass, you will retain the lock on this “previous” node until you reset the prev pointer to the current pointer.
• To add a node, you need to block two nodes that will be located on both sides of the added node. For example, you will have a prev node pointer and a current node pointer. You must first lock the mutexes on the prev node, and then lock the mutexes on the current node and add a new node between prev and current node.
• If you delete the node, you again block the mutex in prev and current node (in that order), and then you can delete the current node.

Keep in mind that steps # 3 and # 4 work because of step # 2, where blocking on nodes is required to move through the list. If you skip this step, you will create dangling pointers and other problems associated with incorrectly assigned pointers, as another thread changes the list topology under the current thread.

Answer 2

Since locking one node is not thread safe (one thread may try to insert after it, and the other is busy deleting the next node), none of them block a subset of nodes. It is best to use a global mutex for the entire list, unless you want to make some effort to develop a read-write lock that will at least allow multiple threads to read the list at the same time.

Since a doubly linked list is an even more complex structure, I would support the same advice.