How can we use multi-threading while working with linked lists

Question

I am fairly new to the concept of multi-threading and was exploring to see some interesting problems in order to get a better idea.

One of my friends suggested the following:

"It is fairly straight-forward to have a linked-list and do the regular insert, search and delete operations. But how would you do these operations if multiple threads need to work on the same list. How many locks are required minimum. How many locks can we have to have optimized linked list functions?"

Giving some thought, I feel that a single lock should be sufficient to work with. We acquire the lock for every single read and write operation. By this I mean when we are accessing a node data in a list we acquire the lock. When we are inserting/deleting elements, we acquire lock for the complete series of steps.

But I was not able to think of a way where using more locks will give us more optimized performance.

Any help/pointers?

Answer 1

Using one lock for the entire list would completely defeat most reasons for multithreading in the first place. By locking the entire list down, you guarantee that only one thread can use the list at a time.

This is certainly safe in the sense that you will have no deadlocks or races, but it is naive and inefficient because you serialize access to the entire list.

A better approach would be to have a lock for each item in the list, and another one for the list itself. The latter would be needed when appending to the list, depending on how the list is implemented (eg, if it maintains a node count seperate from the nodes themselves).

However this might also be less than optimal depending on a number of factors. For instance, on some platforms mutexes might be expensive in terms of resources and time when instantiating the mutex. If space is at a premium, another approach might be to have a fixed-size pool of mutexes from which you draw whenever you need to access an item. These mutexes would have some kind of ownership flag which indicates which node they are allocated to, so that no other mutex would be allocated to that node at the same time.

Another technique is to use reader/write locks, which will allow read access to any thread, but write access to only one, the two being mutually exclusive. However it has been suggested in the literature that in many cases using a reader/write lock is actually less efficient than simply using a plain mutex. This will depend on your actual usage pattern and how the lock is implemented.

Answer 2

The logical extension of "one lock per list" would be "one lock per item".

The case when this would be useful would e.g. be if you're often only modifying a single item of the list.

For deletion and insertion, acquiring the proper locks gets more complicated, though. You'd have to acquire the lock for the item before and after, and you'd have to make sure to always acquire them in the same order (to prevent deadlocks). And there's of course also special cases to be considered if the root element has to be modified (and possibly also if it's a double-linked list or a circular linked list). This overhead resulting from the more complicated locking logic might lead to your implementation being slower again, especially if you often have to insert and delete from the list. So I would only consider this if the majority of accesses is the modification of a single node.

If you're searching for peak performance for a specific use case, then in the end, it boils down to implementing both, and running performance comparisons for a typical scenario.

Answer 3

If you're new to multi-threading, embrace the notion that premature optimization is a waste of time. Linked lists are a very straight-forward data structure, and you can make it thread-safe by putting a critical section on all reads and writes. These will lock the thread into the CPU for the duration of the execution of the read/insert/delete operation, and ensure thread-safety. They also don't consume the overhead of a mutex lock, or more complicated locking mechanism.

If you want to optimize after the fact, only do so with a valid profiling tool that gives you raw numbers. The linked list operations will never end up being the biggest source of application slowdown, and it will probably never be worth your while to add in the node-level locking being discussed.

Answer 4

You definitely need at least one semaphore/lock to ensure list integrity.

But, presumably any operation on the list changes at most two nodes: The node being insert/changed/deleted and the adjacent node which points to it. So you could implement locking on a per-node basis, locking at most two nodes for a given operation. This would allow for a degree of concurrency when different threads accesses the list, though you'd need to distinguish between read and write locks to the get full benefit of this approach I think.

Answer 5

You only need to lock when you're writing and you say there's usually only one write, so try read/write locks.