5 ms·
> Really, "lock free" programming is just locking critical sections with lower level hardware primitives. I have to disagree, as the more interesting lock free
by scott_s 6y ago
> Really, "lock free" programming is just locking critical sections with lower level hardware primitives.
I have to disagree, as the more interesting lock free algorithms use atomic operations that can fail. Yes, a compare-and-swap is like having a critical section on modifying that particular address. But a compare-and-swap can fail if what is currently there is unexpected. The result of that failure generally means redoing a bunch of work, rather than just trying again. Interesting lock free algorithms tend to have the structure:
1. Read some data.
2. Perform computations on that data.
3. Trying to commit the result of that computation. If someone else committed data to the same location after you read it in step 1, go back to step 1.
That's less like a "critical section," and more like a transaction. For lock free algorithms that just rely on atomic operations that cannot fail (such as an atomic increment), then yes, those are just like having a lower-level critical section. (And, on some architectures, that's exactly what they are.)
- Animats 6y agocompare-and-swap Compare and swap is interesting. It's a tiny transaction. It can even operate across networks - FireWire had hardware compare and swap support. Compare and swap with retry may have to wait and retry, which is effectively waiting for someone else to stop using a resource you want. So it's a form of a critical section lock.
- yencabulator 6y agoOptimistic locking is still locking. The low level compare-and-swap operation still uses CPU cacheline-level locking. https://en.wikipedia.org/wiki/MESI_protocol https://en.wikipedia.org/wiki/MESI_protocol
- scott_s 6y agoWhat's important is that you no longer have a critical section, where mutual exclusion is enforced. The only piece of code that has mutual exclusion is an attempt to commit the transaction. The kind of thinking required to implement such algorithms is quite different than when you can rely on mutual exclusion. (Also, not all architecture use hardware mechanisms to enforce actual mutual exclusion. For example, Power does not, as it uses load-linked, stored-conditional: https://en.wikipedia.org/wiki/Load-link/store-conditional https://en.wikipedia.org/wiki/Load-link/store-conditional. On Power, even things like atomic increments are implemented with LL/SC. Architectures basically have to decide: will they implement atomics through some kind of a lock mechanism, or some kind of LL/SC mechanism.)
- yencabulator 6y agoYou still have a critical section; the cacheline is in an exclusive mode during the change. LL/SC operates on top the cache sharing protocols, just like everything else. Your wikipedia link even refers to that: "Typically, CPUs track the load-linked address at a cache-line or other granularity [...]". MESI and friends are that mechanism. What lock-free means in this case is that an OS level thread freezing doesn't prevent global progress. That's true on the abstraction level of typical programming, but grandparent is very much correct: > Really, "lock free" programming is just locking critical sections with lower level hardware primitives.