3 ms·

Exactly. 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 ki

by exDM69 3y ago

Exactly. 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 ago
So 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.

3 ms·

Exactly. 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 ki

by exDM69 3y ago

Exactly. 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 ago
So 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.