An introduction to lockless algorithms

Posted Feb 21, 2021 20:52 UTC (Sun) by pbonzini (subscriber, #60935)
In reply to: An introduction to lockless algorithms by andresfreund
Parent article: An introduction to lockless algorithms

Looks like you want to read part 3 indeed! :)

An introduction to lockless algorithms

Posted Feb 21, 2021 22:29 UTC (Sun) by andresfreund (subscriber, #69562) [Link] (1 responses)

Awesome, looking forward to it.

I don't know how many times I've now spent several hours staring at the read barrier + write barrier != full barrier thing swapping it back into my brain. And how often I couldn't find anything good to tell people to read.

An introduction to lockless algorithms

Posted Feb 25, 2021 18:25 UTC (Thu) by Alan.Stern (subscriber, #12437) [Link]

Here's one way to think about it: A read barrier will order two reads with respect to each other, and a write barrier will order two writes. But not even the combination of a read barrier plus a write barrier will order a write with respect to a read. A full barrier, on the other hand, will.

Example: Suppose the source code says:

write(x)
wmb()
rmb()
read(y)

Then the CPU has to execute the write before the wmb, and it has to execute the read after the rmb. But (depending on the architecture) nothing prevents it from reordering the operations to:

rmb()
read(y)
write(x)
wmb()

(In fact this actually happens on x86, where rmb and wmb are both no-ops and reads can be executed before earlier writes.)

However, with a full barrier:

write(x)
mb()
read(y)

no reordering is possible, and the write *must* be executed before the read.
There are other ways in which a full barrier is stronger than the combination of a read barrier plus a write barrier -- but at least this gets the point across.