An introduction to lockless algorithms (2021)
lwn.net
lwn.net
Mutexes are very cheap in the uncontended case, and in the contended case they have some nice properties. You should only consider going for a lockless algorithm if you can prove it is better than just using a mutex. Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost.
Another problem with lockless is that you can't turn every algorithm into a lockless one, it's actually only a handful of them that are practical to implement locklessly. Of course, the ones that are practical, like some queue and linked list algorithms, can give very nice benefits if used correctly.
You can make every data structure lock-free, even wait-free, there are universal constructions [1]. The resulting performance may however be prohibitive.
[1] https://www.researchgate.net/publication/221343511_Impossibi...
For what it's worth, on macOS profiling audio apps shows that the OS itself is using mutexes on audio thread and it doesn't seem to be a problem. The popular JUCE libraries add another set of mutexes.
> If you’re less lucky, you’ll have to switch your audio effect to bypass mode, or perhaps fade out, or some similar fallback strategy. It’s probably not ideal, but in many cases still better than a glitch.
In applications where you're willing to trade throughput for latency (like RTOS schedulers, drivers, audio processing), it can often make sense to go for a wait-free data structure.
[0] https://arxiv.org/pdf/1701.00854.pdf
It was a while ago I was deep into this mess so forgive any ignorance–but–iirc the thread-mutex dogma[1] has many pitfalls despite being so widely used. Primarily they’re easy to misuse (deadlocks, holding a lock across a suspend point), and have unpredictable performance because they span so far into compiler, OS and CPU territory (instruction reordering, cache line invalidation, mode switches etc). Also on Arm it’s unclear if mutices are as cheap because of the relaxed memory order(?). Finally code with mutices are hard to test exhaustively, and are prone to heisenbugs.
Now, many if not most of the above apply to anything with atomics, so lock-free/wait-free won’t help either. There’s a reason why a lot of concurrency is ~phd level on the theoretical side, as well as deeply coupled with the gritty realities of hardware/compilers/os on the engineering side.
That said, I still think there’s room for a slightly expanded concurrency toolbox for mortals. For instance, a well implemented concurrent queue can be a significant improvement for many workflows, perhaps even with native OS support (io_uring style)?. Another exciting example is concurrency permutation test frameworks[2] for atomics that reorder operations in order to synthetically trigger rare logical race conditions. I’ve also personally had great experience with the Golang race detector. I hope we see some convergence on some of this stuff within a few years. Concurrency is still incredibly hard to get right.
[1]: I say this only because CS degrees has preached mutices to as the silver bullet for decades.
Mutexes are a solution to the mutual exclusion problem, no more no less. Sometimes this problem can be solved by a queue, but that opens other large cans of worms like asynchronicity.
I write more lock-less [1] code than most, but I will often fall back to a mutex as the right solution for a problem given a complexity and performance budget.
[1] by that I mean code without standard use of mutexes, not necessarily non-blocking.
It can be made somewhat tractable to experienced concurrency wizards; I think Rust's "cross-thread shared ^ mutable" rule is a good starting point, but have less experience with Go, JS, or Erlang-style approaches.
My perception is that other comparably dangerous mechanisms are taught with appropriate caveats-- you WILL typically be admonished to keep variables as local as possible, learn how to encapsulate state, and probably be instructed to ALWAYS use proper loops, conditionals and function calls instead of wild gotos-- it does not even matter if you learn programming in university or on your own.
But with threading this is not the case, you'll typically get handed threading primitives without much prejudice, with predictable results.
Note I’m not talking about an isolated case of analyzing a concurrent snippet of code for happens-before relationships, but rather how to write highly concurrent code within large scale applications, without runaway complexity.
[1]: https://bholley.net/blog/2015/must-be-this-tall-to-write-mul...
I'm still settling in to the horrors of memory ordering on ARM. The one thing I know for sure, is that my oeuvre contains a trail of code that will work fine on Intel processors, but won't work on ARM (or any other processor with weak memory ordering). :-/
If you are writing atomic based code, you should be using something like C++11 and C11 atomics that will take care of fencing on all platforms.
More importantly, if you've read a value then that value should stay alive (not be destructed/collected) until you explicitly release it or re-read that "cell".
Then what you do is publish immutable data to the "cell".
Unlike rw locks there's neither the risk of readers blocking behind writers nor writers being starved, and it's highly concurrent.
Clojure has a `ref` for this. Linux has RCU, which is a bit like this.
I've implemented just that in a lockless way twice (see elsewhere in this thread) with this C API:
typedef struct thread_safe_var *thread_safe_var; /* TSV */
typedef void (*thread_safe_var_dtor_f)(void *); /* Value destructor */
/* Initialize a TSV with a given value destructor */
int thread_safe_var_init(thread_safe_var *, thread_safe_var_dtor_f);
/* Destroy a TSV */
void thread_safe_var_destroy(thread_safe_var);
/* Get the current value of the TSV and a version number for it */
int thread_safe_var_get(thread_safe_var, void **, uint64_t *);
/* Release the reference to the last value read by this thread from the TSV */
void thread_safe_var_release(thread_safe_var);
/* Wait for a value to be set on the TSV */
int thread_safe_var_wait(thread_safe_var);
/* Set a new value on the TSV (outputs the new version) */
int thread_safe_var_set(thread_safe_var, void *, uint64_t *);In the LWN series about lockless algorithms, there is a lot of detail about the atomic primitives used in them, but apart from ringbuffers, linked lists and RCU, I actually didn't see any mention of higher level lockless algorithms. For single-producer, single-consumer queues and for linked lists, lockless algorithms are known and performant, but many others are either not that performant, or they come with severe restrictions. For example, RCU sounds great, but you have to worry about grace periods, and you should only use it when you read much more often than you modify.
The only bugs found by TSAN (as noted in another reply) were the one you found and two assert()s that didn't use atomics. Those two asserts could be a big problem if one ran a non-NDEBUG build in production.
So now this is TSAN- and Helgrind-clean.
Thanks for prompting me to do this extra work!
If you reference N twice and M zero times, why did you define M? Did you make a typo in the O() or is this intentional?
> Most threads only ever need to call thread_safe_var_get().
> reference count the data.
Does getting a new value automatically release a reference to the old one (so it's no longer safe to read)?
That was a typo. It should have read `O(N log(M))`.
> Does getting a new value automatically release a reference to the old one (so it's no longer safe to read)?
Correct. Every read (get) of the variable causes the previous value to no longer be safe to use in that thread.
You'll need to expand on this, since mutex acquisition also requires similar atomic read-modify-write operations. I think what you may be trying to say is that lockless algorithms require more of these operations as they scale to more processors?
If there are only two threads at most, you can sometimes use a different algorithm than if you have an arbitrary number of threads (for example, for single-producer, single-consumer queues, lockless is typically better than with a mutex).
You should of course benchmark your particular problem to see what solution is actually faster.
> Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost.
Not interested in getting into a pedantic argument about the definition of "lockless" or "lockfree."
I'm with you. If you aren't benchmarking your datastructure changes, you probably shouldn't be messing around with lock-free code to begin with.
This is why some common locking advice does not really apply to kernel code. Another example would be "avoid using spinlocks, prefer a mutex" - spinlocks are widely used in the kernel since they're the most straightforward alternative to mutexes.
Not disagreeing with the parent post, just wanted to add some context why LWN likes to talk about lockless algorithms.
[1] Actually, the kernel differentiates between hardirqs and softirqs, but that's not important here.
In the kernel, spinlocks are typically taken at the same time IRQs for the current core are disabled, which avoids this issue (and deadlocks of course).
The reason lockless data structures are popular is performance and scalability, and they're popular in user-land as much as in kernel-land, and in the Linux kernel as much as in any other OS.
The idea is to make sure that you don't block because context switches are expensive, but also not to spin for a long time either because that can be even worse than blocking. Along the way you want to make sure that contention is not a problem and that the algorithm scales to many CPUs and lots of racing, and that it's free of race condition bugs.
I would, in fact, give precisely the reverse advice for one reason:
Mutexs don't compose.
Mutexs are really good at putting subtle bugs into your code that are ridiculously difficult to figure out.
Lockless algorithms may be slower or cause performance issues, but they don't malfunction because you got the release order backwards.
The don't compose because (as you hinted) lock taking/releasing order has to be the same for all callers, but if mutexes are being taken behind the scenes then API usage order becomes critical, and it is trivial to screw that up.
> Lockless algorithms may be slower or cause performance issues, but they don't malfunction because you got the release order backwards.
And they may scale better. Scalability is important.
For me the classic case is rw locks vs. RCU-ish schemes. I think there's no case where rw locks are ever appropriate if you have an RCU-ish alternative. For example, OpenSSL uses only rw locks -- nuts!
Here's some of mine: https://github.com/cryptonector/ctp/
This is true for all optimizations: optimizations should be chosen based on profiling, not based on reasoning about the programs. Reasoning can give you ideas of what to profile, but modern programs, including the environments in which they run, are complex enough that you can never really be sure that the assumptions you're basing your reasoning on are true.
So I fully agree with this, but I have some questions about the rest of your post.
> Mutexes are very cheap in the uncontended case, and in the contended case they have some nice properties. Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost.
My (very limited) experience in this area is mostly with optimistic lock-free algorithms, so maybe there's something that I'm missing. But my understanding of optimistic lock-free algorithms is that they make use of the idea that the uncontended case is the most common case, and try to optimize that case heavily. On Intel processors, a compare-and-exchange operation should literally be a single instruction (CMPXCHG[1]). So I'm wondering how the uncontested case using a mutex could be seen as a positive?
> Another problem with lockless is that you can't turn every algorithm into a lockless one, it's actually only a handful of them that are practical to implement locklessly.
How could "you can't turn every algorithm into a lockless one" could be true? It seems to me that you can "simulate" an atomic compare and swap using mutexes--although I can't find a reference easily, I believe this is what GCC's __sync_X_compare_and_swap does on architectures which don't have a compare-and-exchange instruction. Likewise you can implement a mutex fairly easily using a compare-and-swap operation.
Whether this is practical would of course depend on the situation--implementing a mutex in terms of compare-and-exchange or vice-versa are likely not the optimal ways to implement either. But it seems to me that if compare-and-exchange and mutexes can be implemented in terms of each other, isn't that a trivial proof that any mutex algorithm can be implemented as a lock-free algorithm and vice-versa?
The point of a lock free algorithm is to avoid having a thread wait on a resource and not do any work. It may do useless work that needs to be reverted, but it's not sleeping or spinning until something happens. It's not guaranteed that you can do that for every algorithm in a way that makes sense performance wise.
Here's a nice resource I used on my thesis for an adequate but not perfect spinlock with atomic instructions: https://rigtorp.se/spinlock/
Sure, but that seems like a much narrower statement than "you can't turn every algorithm into a lockless one".
Maybe I'm just being pedantic and the person intended something more like what you said, though.
Specifically, a lock-free algorithm is appropriate if it would be considered an error for one thread to stall and cause any other threads to stall.
An example of this would be a concurrent garbage collector. These are used when you do not want garbage collection to stop a program from executing. The way that the GC thread communicates with the rest of the program therefore must be lock-free.
That's not to say a stop-the-world GC could be faster: just that its lack of performance guarantees would be considered a bug.
I've been working on other projects for the last number of years, but I'm finally back to liblfds and making progress toward the next release.
https://www.linuxjournal.com/content/lock-free-multi-produce...
I liked this whitepaper https://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf
I am a beginner at this kind of thing but I created an array of integers that each thread owns an index. They write to the array at their index that they want access to the critical section.
We scan the array forwards and backwards to see if there is any thread that has claim to the critical section.
I even TRIED to write a model checker https://github.com/samsquire/multithreaded-model-checker
This is inspired by left-right concurrency control whitepaper Left-Right: A Concurrency Control Technique with Wait-Free Population Oblivious Reads
> In this article, I concentrate on x86, as it is the most widespread architecture rather than write generic (but slower) code.
Any reasonable C++ compiler will generate simple loads and stores for atomic r&a. There's no penalty for writing generic code.
- Dmitry Vyukov's Lockless Algorithms: https://www.1024cores.net/home/lock-free-algorithms
- Jeff Preshing's blog (worth exploring all adjacent articles): https://preshing.com/20120612/an-introduction-to-lock-free-p...
- Bartosz Milewski: https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-...
- Memory Barriers: a Hardware View for Software Hackers—P.McKenney: https://www.researchgate.net/publication/228824849_Memory_Ba...
I hope you find some of these useful. I've re-read Paul McKenney's paper every 2-3 months in an attempt to get this stuff to stick! :)
I’m also new to a lot of these topics but recently read Rust Atomics and Locks which has helped my understanding quite a bit - at least keeping me above water reading all the discussion in this post. The examples are in Rust but the concepts are at the kernel/cpu level and apply beyond the language. I recommend it.