An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 4:04 UTC (Sat) by itsmycpu (guest, #139639)
In reply to: An introduction to lockless algorithms by pebolle
Parent article: An introduction to lockless algorithms

Practically it means that if (step1) the first thread updates data, and then (step2) does a store-release of a value that indicates that the data was written, and then (step3) the second thread does a load-acquire of that value, it will (step4) see all the updates that the first thread has done before step2.

As long as the value read in step3 is the value written in step2 (or a value written after that). Because then you know that step3 > step2, and because of that, step4 > step1.

to post comments

An introduction to lockless algorithms

Posted Feb 20, 2021 6:15 UTC (Sat) by itsmycpu (guest, #139639) [Link] (3 responses)

>Practically it means that if (step1) the first thread updates data, and then (step2) does a store-release of a value that indicates that the data was written, and then (step3) the second thread does a load-acquire of that value, it will (step4) see all the updates that the first thread has done before step2.
>
> As long as the value read in step3 is the value written in step2 (or a value written after that). Because then you know that step3 > step2, and because of that, step4 > step1.

To clarify the not-so-obvious part:

From the point of view of the first thread, step2 > step1 is always true, but without using acquire/release, this doesn't transfer to the second thread. Without that, the second thread may not see step4 > step1.

Why not? For example, the compiler is allowed to produce code for step2 that affects memory before step1, as long as that doesn't change the outcome of the first thread's local computations. The compiler does not have to consider the possible side effect on the second thread, which therefore might see the memory affected by step2 before it is affected by step1.

Only the use of acquire/release requires the compiler to produce code where the update of step1 is written to memory, and therefore visible to other threads, before step2. (Memory or shared cache). So without that, the second thread cannot assume step4 > step1, even if it thinks it can assume step3 > step2.

I think this is the same thing as the article says, just highlighting the practical aspects.

An introduction to lockless algorithms

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

Yes, it's exactly the last ASCII art graph. Thanks for explaining it in words; even if a picture is worth a thousand words, sometimes writing them down still helps!

An introduction to lockless algorithms

Posted Feb 20, 2021 9:47 UTC (Sat) by pebolle (guest, #35204) [Link]

> Thanks for explaining it in words

And that goes for everyone taking time to answering my grumpy questions.

When you're not versed in the vocabulary and habits of a certain field it is very to hard determine whether you're reading something profound, something trivial or just plain nonsense. (I've just finished a book of nearly 300 pages explaining that even physicists can be happily employed while apparently only producing hot air.)

I'll restart the article and hope that I won't get stuck on one of my many, many pet peeves again.

An introduction to lockless algorithms

Posted Dec 10, 2021 9:48 UTC (Fri) by Lurchi (guest, #38509) [Link]

    a.x = 1;                            datum = message;
       |                                    |
       |   happens before                   |
       v                                    v
    message = &a;                       datum->x

I think the left "happens before" arrow should not be there (the right one of course is correct, due to the data dependency).