5 ms·
> Even if this read and write are not atomic, the system still works This statement is not really true for modern computers, especially ARM and other architect
by exDM69 3y ago
> Even if this read and write are not atomic, the system still works
This statement is not really true for modern computers, especially ARM and other architectures which are more sensitive to memory orderings than x86 CPUs.
The reason is the lack of memory barriers.
The CPU and the compiler are free to reorder loads and stores. Memory barriers are inserted in between to enforce specific ordering.
You need an acquire memory barrier after acquiring a lock to make sure that any loads and stores inside the critical section do not get reordered to before the lock was grabbed.
So while the algorithm may work for acquiring a critical section without atomics, it does not enforce that the stuff inside the critical section stays inside the critical section within the same thread.
In fact most normal loads and stores in ARM are "atomic" but to achieve consistency in concurrent programming they are followed or preceded by an appropriate memory barrier instruction e.g. in std::atomic_load or _store.
- arter4 3y ago>You need an acquire memory barrier after acquiring a lock to make sure that any loads and stores inside the critical section do not get reordered to before the lock was grabbed. What do you mean? That loads and stores inside a critical section could, in fact, be reordered by the CPU and be executed before grabbing a lock?
- exDM69 3y agoExactly. A load from or store to memory protected by a mutex could be executed before the store that sets the mutex as locked. Unless there is an appropriate kind of memory barrier in between.
- arter4 3y agoSo even the Lamport bakery algorithm requires memory barriers, because modern processors can reorder instructions? Does this mean that modern CPU architectures necessarily require hardware-supported atomic instructions for proper concurrency? Also, is there any evidence as to how common this memory re-ordering is?
- exDM69 3y ago> So even the Lamport bakery algorithm requires memory barriers, because modern processors can reorder instructions? Yes, that is correct. Memory ordering needs to be enforced with barriers for correctness. > Does this mean that modern CPU architectures necessarily require hardware-supported atomic instructions for proper concurrency? A non-tearing word size write and appropriate memory barriers are enough. Atomic read modify write instructions like compare and swap are useful but not strictly necessary. I think it would be possible to implement the Lamport's Bakery algorithm from this article correctly with a lot of barriers, but its performance would be awful. > Also, is there any evidence as to how common this memory re-ordering is? It is very common (almost all loads and stores get grouped by the CPU) but its effect is so small that it rarely manifests in practice. A reordering would only move a load or store by a few dozen nanoseconds in wall clock time. I have some practical experience from stress testing high contention memory ordering sensitive code. It would often take a minutes of CPU time to make a bug manifest. That's somewhere between one in a million to one in a billion odds of an unfortunate memory ordering ruining your day.
- gpderetta 3y agoActually acquire/release barriers or operations are not enough. I'm pretty sure you also need a #StoreLoad for example between Step 1 and Step 2 in the lock algorithm, to prevent the loads from other thread state in step 2 to be reordered before the stores to the own thread state in step 1. Generally #StoreLoad is required when you need bidirectional synchronization between two or more threads. Re atomics, I think the algorithm still requires word sized operations to be atomic, but I think that was considered a given. What the algorithm doesn't require is atomic load/stores (or more complex RMW) across more than one word.
- Vecr 3y agoCould you implement it using AtomicUsize (using only relaxed operations) in Rust? With AtomicUsize representing the words. You aren't allowed to put pointers in those.
- gpderetta 3y agoIf atomicusize is sequentially consistent, then yes.
- exDM69 3y agoNo, it can not use relaxed memory ordering. Looking at disassembly of relaxed atomic operations, they are just normal loads and stores with no memory barriers or special instructions. That is not enough to make this algorithm guard a critical section.
- contravariant 3y agoI tried to think how this might go wrong. The part that I can see going wrong is with the 'choosing' array, an optimizer may choose to combine the two writes and just write 'false' immediately. I feel like that breaks a lot of reasonable guarantees, but let's run with it. So basically the problem is that two processes might pick the same number, see the other process with an (outdated) lower number and choosing=false, and go ahead into the critical section. So basically you need a guarantee that the write to the choosing array lands before picking a number. You can simplify things a bit by simply setting 'number' high instead of using 2 arrays, but still.
- exDM69 3y agoEven if the algorithm "works", it does not guard the critical section correctly. The code that is supposed to go between lock() and unlock() may be executed before the lock is acquired or after it is released because CPU is allowed to reorder anything as it wishes in the absence of memory barriers. Other replies here go further and suggest that the implementation of the algorithm is also broken without barriers, which is probably true as well.