Take the 2-minute tour ×

I'm wondering what is the "best" way to make data thread-safe.

Specifically, I need to protect a linked-list across multiple threads -- one thread might try to read from it while another thread adds/removes data from it, or even frees the entire list. I've been reading about locks; they seem to be the most commonly used approach, but apparently they can be problematic (deadlocks). I've also read about atomic-operations as well as thread-local storage.

In your opinion, what would be my best course of action? What's the approach that most programmers use, and for what reason?

share|improve this question
best approach depends on the language you are using. For example in erlang this is a non-issue –  Sam Saffron Jun 15 '09 at 2:36
yep, erlang's intrinsically message-passing (so multiprocessing is the sweetest thing in it) -- in my answer I sketched how to build that happy state in other languages such as Python. –  Alex Martelli Jun 15 '09 at 2:59
add comment

4 Answers

up vote 5 down vote accepted

One approach that is not heavily used, but quite sound, is to designate one special purpose thread to own every "shared" structure. That thread generally sits waiting on a (thread-safe;-) queue, e.g. in Python a Queue.Queue instance, for work requests (reading or changing the shared structure), including both ones that request a response (they'll pass their own queue on which the response is placed when ready) and ones that don't. This approach entirely serializes all access to the shared resource, remaps easily to a multi-process or distributed architecture (almost brainlessly, in Python, with multiprocessing;-), and absolutely guarantees soundness and lack of deadlocks as well as race conditions as long as the underlying queue object is well-programmed once and for all.

It basically turns the hell of shared data structures into the paradise of message-passing concurrency architectures.

OTOH, it may be a tad higher-overhead than slugging it out the hard way with locks &c;-).

share|improve this answer
agree. I'd much rather move to a message passing based interface than support concurrent adds / removes AND traversal on a linked list. –  Rick Jun 15 '09 at 2:51
You do still have to be careful about deadlocks in a pure message passing system though... if process A is waiting on message b from process B before it sends message a to process C -AND- process B will only send message b when it receives message c from process C -AND- process C only emits message c when it receives message a. Same basic problem as a deadlock only contingent on messaging dependencies instead of locked resources. –  D.Shawley Jun 15 '09 at 3:12
In the Windows API, this is the difference between SendMessage (which is synchronous and which blocks the sender until the send has been received and processed) and PostMessage (which is asynchronous). Asynchronous message-passing isn't liable to deadlock (but might instead have might you wondering whether your post was ever actually received and processed). –  ChrisW Jun 15 '09 at 3:21
Thanks for the idea! –  beepboopbopbop Jun 18 '09 at 15:21
add comment

You could consider an immutable collection. Much like how a string in .net has methods such as Replace, Insert, etc. It doesn't modify the string but instead creates a new one, a LinkedList collection can be designed to be immutable as well. In fact, a LinkedList is actually fairly simple to implement this way as compared to some other collection data structures.

Here's a link to a blog post discussing immutable collections and a link to some implementations in .NET.


share|improve this answer
These sorts of data structures are often known as "persistent" data structures (and there is a persistent-data-structures tag on SO for discussions of this). These can often share memory cells with earlier versions of the data structures, reducing copying (and memory usage, if you keep the previous versions of the data structures). –  Curt Sampson Jun 15 '09 at 8:07
add comment

Always remember the most important rule of thread safety. Know all the critical sections of your code inside out. And by that, know them like your ABCs. Only if you can identify them at go once asked will you know which areas to operate your thread safety mechanisms on.

After that, remember the rules of thumb:

  • Look out for all your global variables / variables on the heap.
  • Make sure your subroutines are re-entrant.
  • Make sure access to shared data is serialized.
  • Make sure there are no indirect accesses through pointers.

(I'm sure others can add more.)

share|improve this answer
add comment

The "best" way, from a safety point of view, is to put a lock on the entire data structure, so that only one thread can touch it at a time.

Once you decide to lock less than the entire structure, presumably for performance reasons, the details of doing this are messy and differ for every data structure, and even variants of the same structure.

My suggestion is to

  1. Start with a global lock on your data structure. Profile your program to see if it's really a problem.

  2. If it is a problem, consider whether there's some other way to distribute the problem. Can you minimize the amount of data in the data structure in question, so that it need not be accessed so often or for so long? If it's a queuing system, for example, perhaps you can keep a local queue per thread, and only move things into or out of a global queue when a local queue becomes over- or under-loaded.

  3. Look at data structures designed to help reduce contention for the particular type of thing you're doing, and implement them carefully and precisely, erring on the side of safety. For the queuing example, work-stealing queues might be what you need.

share|improve this answer
This approach also assumes that an "entire structure" is self contained and that you never need to lock more than one object at a time. Normally the problem with global to the structure locks occurs when data in one structure points to data in another structure. Then deadlocks become common place. –  jmucchiello Jun 15 '09 at 2:50
Indeed, if you need to lock multiple structures and you use multiple locks, rather than one lock to lock all of them at once, you are in the same position as if you use multiple locks to lock different parts of a data structure. –  Curt Sampson Jun 15 '09 at 8:04
add comment

Your Answer


