Locks, Deadlocks, and Evil

Tuesday, November 9, 2010 by darco
Posted in ,

I have a firm belief that locking primitives (Often called mutexes, or just "locks") are evil, and should be avoided if at all possible. I realize this may sound like blasphemy, but in practice I've found that in most cases a race condition is better resolved using a more disciplined strategy than carelessly adding another lock.

There is nothing inherently wrong with the concept of a lock. Sometimes their use is unavoidable—a necessary evil. If we all used locks properly and were fully aware of all consequences of using them in a given context then there would be no problems at all. The problem is us: we are human, not omnipotent—correct concurrent programming is hard.

Whether we are talking about semaphores, mutexes, recursive locks, or read-write locks, all are ultimately attempting to accomplish what at first appears to be a very simple goal: serialize access to a resource. I've been programming multithreaded code for ten years now, and in my experience this is one of the most widely overused, abused, and confusing aspects of concurrent programing.

To make things easier, I've come up with the following guidelines for resolving serialized access problems which may tempt me to just throw in a lock and be done with it. It might be a good idea to use this as a checklist to force you to think about all of the options and consequences.

  • You should only use an explicit lock when no other alternative is reasonable. Possible alternatives to locks include (in order of desirability):
    1. Atomic operators.
    2. Limiting access to the resource to a specific process, thread, or serial dispatch queue. (This is, in my opinion, the best overall strategy)
    3. Language-level synchronization primitives.
  • Use atomic operators (like OSAtomicIncrement32(), or OSAtomicCompareAndSwap32()) instead of serializing writes to simple variables. This is both faster and less error-prone. Reads do not need a lock in this case.
  • FIFOs with a static size can be implemented as a circular buffer without any locks.
  • If you are using MacOS X and need a LIFO, consider using OSAtomicEnqueue()/OSAtomicDequeue().
  • Avoid nesting locks—situations which might tempt you to do this are almost always better resolved using a different strategy. If unavoidable for some reason, be aware that the locks must ALWAYS be locked in the same order and unlocked in reverse order. Failure to do this WILL result in deadlocks.
  • A lock should be unlocked as quickly as possible after being locked. Lock and unlock calls should not be more than 20 lines apart.
  • Avoid nested for loops while a lock is locked. This impairs readability, and is often avoidable.
  • return and goto should not be allowed while the lock is locked.
  • In C++ and ObjC (or any other language with exceptions), be very careful to ensure that no code can throw an exception while the lock is locked. (Use of synchronization primitives can help avoid exception-related mistakes like this)
  • If the contention case is predicted to be rare, consider using simple spinlock (Like OSSpinLock on MacOS X) instead of a pthreadmutext or an NSLock.
  • Lock-copy-unlock: For serializing reads, consider only using a lock to make a copy the information in question and then do processing on the copy (while the lock is unlocked) instead of the original. Spinlocks work great in this case.
  • If performance is not an issue, consider using any synchronization primitives that may be supported by the language you are using. For example, ObjC has a keyword that makes serializing access to objects very simple: @synchronized. However, make sure you read up on this keyword before using it.
  • If you are using ObjC, consider using NSLock or NSRecursiveLock instead of pthread_mutex_t. This makes the code more friendly for garbage collection.
  • Avoid read/write locks. In my experience they cause more problems than they solve, and make maintaining the code base more difficult.
  • If you need to use a recursive lock, then chances are you need to re-think your synchronization strategy.

Keep in mind that these are just guidelines—there are occasional exceptions. The point is that if you choose to make an exception, you need to know what you are doing.