What is the reason for "locks are an expensive operation" to be uttered so often?

Question

I have read a lot of material on threading, and all the synchronization mechanisms involved. I also understand the dangers of not doing it properly.

I just watched this PDC 2009 video about Parallelism and Concurrency, and here is yet again this mention that "locks are an expensive operation". I've now come across a phrase like this in various texts, books, and I've heard experts in the field say it too.

I was wondering, what exactly is so expensive about obtaining a lock (mutex or semaphore)? Is it the fact that it causes a LOCK# instruction to be emitted at Assembler level?

Is it the fact that obtaining a lock requires a kernel call into the OS?

Why are locks considered to be an expensive operation? "Expensive" is a fairly relative term, so if we compared to creating a new thread (which requires setting up a thread stack, etc), how expensive is obtaining a lock really?

What goes on underneath the covers?

My guess is, that it cannot possibly that expensive, because I'm sure for Windows (for example) to run, hundreds of locks/synch mechanisms have to be used all the time.

Can anyone elaborate?

NOTE: I'm merely curious, I know how threading works, and I'm not looking to do some silly optimization either.

Answer 1

Parallelism

When mutable shared data requires a lock, you could lose the benefits of parallelism.

Let's first make the simplification that context switches are free and locks are cheap (neither of which is exactly true - we will address these points at the end).

• Think about the case of threads that share no data: threads can run independently without worrying about the state of other threads. Having two threads will make your algorithm run twice as fast.

• Next, introduce some piece of shared data which changes over time. By definition, no two threads can be modifying/reading this data at the same time. That means if two threads happen to want access to this data, you no longer have concurrent operation: they must work in a serialized (synchronized) manner. The more frequently this contention happens, the more your application will behave like a single-threaded application than a dual-threaded app.

So when it is said that "locks are an expensive operation", I take it to mean that it is due to the potential loss of parallelism rather than the lock itself being expensive.

Costs

In addition to the loss of parallelism, if you accumulate the small, but non-zero costs of locks and potential synchronization and context switches, having locks can very likely slow down your algorithm.

Also note that the more threads you have trying to access that lock at the same time, the more your algorithm will appear to run serially rather than in parallel. The OS will also have to spend more cycles juggling all the contexts through that small straw created by the lock.

Mitigation

On the other hand, the drawbacks of having locks can be mitigated by not calling them often, not thrashing (locking/unlocking once rather than lock/unlock many times within a tight block), or by the use of pipelines or consumer/producer patterns (signaling with condition variables).

One trick for lockless operations includes doing all your shared data initialization before spawning any threads and only reading from that data after spawning.

Terminology

One last comment: locks are needed to avoid race conditions on a shared resource. Contentions are just a consequence of having locks - it just means one thread can be blocked/waiting on a lock that another thread has locked. How often contentions happen actually depends on many factors: number of threads vs cores, how much time is spent in the lock, luck of the execution (dependent on the scheduling algorithm), the state of your OS during the run, etc...

Answer 2

Is it the fact that it causes a LOCK# instruction to be emitted at Assembler level?

No, since it doesn't always do that.

Is it the fact that obtaining a lock requires a kernel call into the OS?

No, since it typically doesn't do that.

In fact, locks are very, very inexpensive. It's contention that's expensive. If you have to choose between a lock and contention, most of the time the lock is a better option.

Locks, when used properly, are a contention avoidance mechanism. They automatically find threads that contend and de-schedule them such that one winds up primarily with threads that do not contend running concurrently.

For example: Say you have four threads that are ready to run, A, B, C, and D. Say A and B contend with each other (say they manipulate the same collection). And say C and D contend with each other, but A doesn't contend with C. If A and B are running at the same time (contending), the locks will cause one of them to not be ready to run, the scheduler will then schedule C (or D), and the two threads will run without further contention. (At least until the next context switch.)

Usually, when people say "locks are expensive", they mean that contention is expensive. Unfortunately, by phrasing it the way they do, they often encourage people to minimize locks but increase contention in the process. That is a losing proposition in the vast majority of cases. (There are a few exceptions.)

Answer 3

Locks are expensive because they block other threads from obtaining the lock. The delays can be deadly, making a multi-processor system slower than a single-threaded design without locks.