Will Peterson's solution work correctly on modern CPU architectures? [closed]

Question

I am studying operating systems from Operating System Concepts by Silberschatz, Galvin, and Gagne.

On page 229, the book states this about Petersons Solution :

Because of the way modern computer architectures perform basic machine language instructions, such as load and store, there are no guarantees that Peterson's solution will work correctly on such architectures.

I looked this up on Wikipedia and found this which appears to be the closest to an explanation :

Most modern CPUs reorder memory accesses to improve execution efficiency. Such processors invariably give some way to force ordering in a stream of memory accesses, typically through a memory barrier instruction. Implementation of Peterson's and related algorithms on processors which reorder memory accesses generally requires use of such operations to work correctly to keep sequential operations from happening in an incorrect order. Note that reordering of memory accesses can happen even on processors that don't reorder instructions

I am having trouble understanding what this means or if this is even the answer.

So, why is Peterson's solution not guaranteed to work on modern architectures ?

Venable

What is Peterson's solution? To what issue is it a solution? And I am not sure your question belongs to StackOverflow, it does not seem related to source code. – Primero

@BasileStarynkevitch Linked to the wikipedia page. There are quite a few questions asking about operating system concepts. Also, software algorithm questions are on-topic as per the faq. – Venable

My understanding of the issue is the same as any other time the lock is released too early: The second process will be granted access, but the first process may still have data to write (or read). This can cause the second process to use stale data. – Barge

@Barge A process wont release the lock until it has completed executing its critical section, in which case any data manipulations it has to perform would have been done. What stale data are you referring to ? – Venable

@AshRj: Think about the lock from an implementation standpoint - 'releasing' the lock is done with a memory write. If I write data and then 'release' the lock, but it's reordered to be in the opposite order, my lock will be released before my data is written. That gives an opportunity for the other process to start doing its own memory accesses. – Barge

@Barge K. Got that. Post that as an answer. – Venable

From the FAQ but if your question generally covers … a software algorithm – Venable

Answer 1

On a system with one CPU, Peterson's algorithm is guaranteed to work, because program's own behavior is observed in program order.

On systems with multiple CPUs the algorithm may fail to work because the program order of events occurring on one CPU may be perceived differently on another.

That may cause early entering into the critical section (while it's still in use by another thread) and early exiting from the critical section (when the work with the shared resource hasn't been finished yet).

For this reason one needs to ensure that the order of events occurring inside the CPU is seen the same outside. Memory barriers can ensure this serialization.

Forficate

what kind of reordering will cause it to not work? – Laid

@Laid Reordering of memory reads/writes w.r.t. other memory reads/writes. If there are two or more CPUs in the system and reordering of memory reads/writes is unconstrained (by e.g. memory barriers/fences), certain algorithms that rely on the order will break. Peterson's algorithm will break. – Forficate