An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 0:12 UTC (Sat) by mss (subscriber, #138799)
Parent article: An introduction to lockless algorithms

Nice article Paolo, thanks for bringing this subject up.

It is worth noting that the Linux kernel memory model is very similar (or one can say: based on) C11/C++11 memory model - after all, both were based on the underlying behavior of real-world computer systems.

However, since the C/C++ working groups had the benefit of designing an atomic synchronization API from scratch the resulting API seems cleaner and more consistent for me than the kernel API.

I also find Mark John Batty's PhD dissertation called "The C11 and C++11 Concurrency Model" a very good read on the subject.
It not only includes a more formal description of the model but is also rich with examples describing how various CPU architectures behave and why particular model design decisions were (probably) made.

The aforementioned dissertation is available here: https://www.cs.kent.ac.uk/people/staff/mjb211/docs/toc.pdf

to post comments

An introduction to lockless algorithms

Posted Feb 20, 2021 7:11 UTC (Sat) by pbonzini (subscriber, #60935) [Link] (1 responses)

The C11 model has some quirks of its own that make it sometimes harder to use than the Linux kernel memory model. I had a half-baked idea of a sixth article on the topic of C11 atomics for kernel programmers, based on the comments here it seems like there's interest.

An introduction to lockless algorithms

Posted Feb 20, 2021 16:11 UTC (Sat) by mss (subscriber, #138799) [Link]

It's a nice topic bordering between theoretical CS stuff and real world software engineering.

By the way, you said in a comment under the July article to steer clear of the C11 "sequentially consistent" loads and stores since they are incredibly easy to get wrong.
I assume you mean that people have misconceptions about the ordering guarantees that sequentially consistent semantics give?
After all, they provide acquire and release semantics, too, so any algorithm that's valid under acq/rel will be valid under sequentially consistent semantics, too (just maybe slower).

For me personally the most surprising thing with C11 atomics is that a relaxed operation on a variable plus a barrier of X memory order (before or after that operation) is not the same thing as just performing the same operation but with the X memory order, even though the semantics are very close.

In general, the C11 atomics seem to be tailored more for using atomic operations of particular memory order rather than barriers, while most of the kernel code seems to prefer using ordinary memory accesses with barriers instead.