Is the C# "lock" construct rendered obsolete by Interlocked.CompareExchange<T>?

Question

Summary:

It seems to me that:

1. wrapping fields representing a logical state into a single immutable consumable object
2. updating the object's authoritative reference with a call to Interlocked.CompareExchange<T>
3. and handling update failures appropriately

provides a kind of concurrency that renders the "lock" construct not only unnecessary, but a truly misleading construct that dodges certain realities about concurrency and introduces a host of new problems as a result.

Problem Discussion:

First, let's consider the main problems with using a lock:

1. Locks cause a performance hit, and must be used in tandem for reading and writing.
2. Locks block thread execution, hindering concurrency and risking deadlocks.

Consider the ridiculous behavior inspired by the "lock". When the need arises to update a logical set of resources concurrently, we "lock" the set of resources, and we do so via a loosely associated, but dedicated locking object, which otherwise serves no purpose (red flag #1).

We then use the "lock" pattern to mark-off a region of code where a logically consistent state change on a SET of data fields occurs, and yet we shoot ourselves in the foot by mixing the fields with unrelated fields in the same object, while leaving them all mutable and then forcing ourselves into a corner (red flag #2) where we have to also use locks when reading these various fields, so we don't catch them in an inconsistent state.

Clearly, there's a serious problem with that design. It's somewhat unstable, because it requires careful management of the lock objects (locking order, nested locks, coordination among threads, blocking/waiting on a resource in use by another thread that's waiting for you to do something, etc.), which depends on the context. We also hear people talk about how avoiding deadlock is "hard", when it's actually very straightforward: don't steal the shoes of a person you plan on asking to run a race for you!

Solution:

Stop using "lock" altogether. Properly roll your fields into an incorruptible/immutable object representing a consistent state or schema. Perhaps it's simply a pair of dictionaries for converting to and from display-names and internal-identifiers, or maybe it's a head node of a queue containing a value and a link to the next object; whatever it is, wrap it into it's own object and seal it for consistency.

Recognize write or update failure as a possibility, detect it when it occurs, and make a contextually informed decision to retry immediately (or later) or do something else instead of blocking indefinitely.

While blocking seems like a simple way to queue a task that seems like it must be done, not all threads are so dedicated and self-serving that they can afford to do such a thing at the risk of compromising the entire system. Not only is it lazy to serialize things with a "lock", but as a side affect of trying to pretend a write shouldn't fail, you block/freeze your thread, so it sets there unresponsive and useless, forsaking all other responsibilities in its stubborn wait to accomplish what it set out to do some time earlier, ignorant of the fact that assisting others is sometimes necessary for fulfilling it's own responsibilities.

Race conditions are normal when independent, spontaneous actions are occurring simultaneously, but unlike uncontrolled Ethernet collisions, as programmers we have total control over our "system" (i.e. deterministic digital hardware) and its inputs (no matter how random, and how random can a zero or one really be?) and outputs, and the memory that stores our system's state, so livelock should be a non-issue; furthermore, we have atomic operations with memory barriers that resolve the fact that there may be many processors operating concurrently.

To summarize:

1. Grab the current state object, consume its data, and construct a new state.
2. Realize that other active threads will be doing the very same thing, and may beat you to it, but all observe an authoritative reference point representing the "current" state.
3. Use Interlocked.CompareExchange to simultaneously see if the state object you based your work on is still the most current state, and replace it with your new one, otherwise fail (because another thread finished first) and take appropriate corrective action.

The most important part is how you handle the failure and get back on your horse. This is where we avoid livelocks, thinking too much and not doing enough or doing the right thing. I would say that locks create the illusion that you'll never fall off your horse, despite riding in a stampede, and while a thread daydreams in such a fantasy land, the rest of the system can fall apart and crash and burn.

---

So, is there something the "lock" construct can do that can't be achieved (better, in a less unstable fashion) with a lock-free implementation using CompareExchange and immutable logical state objects?

All of this is a realization I've come to on my own after dealing with locks intensely, but after some searching, in another thread Is lock free multithreaded programming making anything easier?, someone mentions that lock-free programming is going to be very important when we face highly parallel systems with hundreds of processors, were we cannot afford to use highly contended locks.

Answer 1

The big advantage of a lock over a CAS operation like Interlocked.CompareExchange is that you can modify multiple memory locations within a lock and all the modifications will be visible to other threads / processes at the same time.

With CAS, only a single variable is atomically updated. Lockfree code is usually significantly more complex because not only can you only present the update of a single variable (or two adjacent variables with CAS2) to other threads at a time, you also have to be able to handle "fail" conditions when CAS doesn't succeed. Plus you need to handle ABA issues and other possible complications.

There are a variety of methods like low locking, fine grain locking, striped locks, reader-writer locks, etc. that can make simple locking code much more multicore friendly.

That said, there are plenty of interesting uses for both locking and lockfree code. However, unless you REALLY know what you're doing creating your own lockfree code is not for a beginner. Use either lockfree code or algorithms that have been well proven and test them thoroughly because the edge conditions that cause failure in many lockfree attempts are very hard to find.

Answer 2

I'd like to know how you would perform this task using your lock free programming style? You have a number of worker threads all periodically hitting a shared lists of tasks for the next job to perform. (currently) They lock the list, find the item at the head, remove it, and unlock the list. Please take into account all error conditions and possible data races so that no two threads can end up working on the same task, or that a task is accidentally skipped.

I suspect that the code to do this may suffer from a problem of over-complexity and have a possibility of poor performance in the case of high contention.

Answer 3

Your compare-exchange-suggestion has one big drawback - it is not fair because it favors short tasks. If there are many short tasks in a system, chances for a long task to ever complete may get very low.

Answer 4

There are four conditions for a race to occur.

1. The first condition is that there are memory locations that are accessible from more than one thread. Typically, these locations are global/static variables, or are heap memory reachable from global/static variables.
2. The second condition is that there is a property (often called an invariant), which is associated with these shared memory locations that must be true, or valid, for the program to function correctly. Typically, the property needs to hold true before an update occurs for the update to be correct.
3. The third condition is that the invariant property does not hold during some part of the actual update. (It is transiently invalid or false during some portion of the processing).

4. The fourth and final condition that must occur for a race to happen is that another thread accesses the memory while the invariant is broken, thereby causing inconsistent or incorrect behavior.

   1. If you don't have a shared memory location which is accessible from multiple threads, or you can write your code to either eliminate that shared memory variable, or restrict access to it to only one thread, then there is no possibility of a race condition, and you don't need to worry about anything. Otherwise, the lock statement, or some other synchronization routine is absolutely necessary and cannot be safely ignored.

   2. If there is no invariant (let's say all you do is write to this shared memory location and nothing in the thread operation reads it's value) then again, there is no problem.

   3. If the invariant is never invalid, again no problem. (say the shared memory is a datetime field storing the datetime of the last time the code ran, then it can't be invalid unless a thread fails to write it at all...

   4. To eliminate nbr 4, you have to restrict write access to the block of code that accesses the shared memory from more than one thread at a time, using lock or some comparable synchronization methodology.

The "concurrency hit" is in this case not only unavoidable but absolutely necessary. Intelligent analysis of what exactly is the shared memory, and what exactly is your critical "invariant" allows you to code the system to minimize this concurrency "Hit". (i.e., maximize concurrency safely. )

Answer 5

I would say it is no more obsolete than saying, in general, that pessimistic concurrency is obsolete given optimistic concurrency, or that pattern A is obsolete because of pattern B. I think it's about context. Lock-free is powerful, but there may not be a point in applying it unilaterally because not every problem is perfectly suited to this. There are trade-offs. That said, it would be good to have a general purpose lockless, optimistic approach where it hasn't been realized traditionally. In short, yes, lock can do something that' can't be achieved with the other approach: represent a potentially simpler solution. Then again, it may be that both have the same result, if certain things don't matter. I suppose I'm equivocating just a bit...

Answer 6

In theory, if there is a fixed amount of work to be done, a program which uses Interlocked.CompareExchange will manage to do it all without locking. Unfortunately, in the presence of high contention, a read/compute-new/compareExchange loop can end up thrashing so badly that 100 processors each trying to perform one update to a common data item may end up taking longer--in real time--than would a single processor performing 100 updates in sequence. Parallelism wouldn't improve performance--it would kill it. Using a lock to guard the resource would mean that only one CPU at a time could update it, but would improve performance to match the single-CPU case.

The one real advantage of lock-free programming is that system functionality will not be adversely affected if a thread gets waylaid for an arbitrary amount of time. One can maintain that advantage while avoiding the performance pitfalls of purely-CompareExchange-based programming by using a combination of locks and timeouts. The basic idea is that in the presence of contention, the resource switches to lock-based synchronization, but if a thread holds a lock for too long, the a new lock object will be created and the earlier lock will be ignored. This will mean that if that former thread was still trying to do a CompareExchange cycle, it will fail (and have to start all over again), but later threads will not be blocked nor will correctness be sacrificed.

Note that the code required to arbitrate all of the above will be complicated and tricky, but if one wants to have a system be robust in the presence of certain fault conditions, such code may be required.