when will peterson's mutual exclusion algorithm fail?

Silbershatz 作業系統課本第 6 章同步介紹 Peterson 雙行程演算法前，有提到如下適用但書。

"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."

到底是什麼現代電腦架構會造成 Peterson 演算法失效?

上網查了一下,有兩種可能性,如下,其中第一種可能性比較大,

1️⃣ 多 CPU + 弱記憶體存取模式（Weak Memory Access Model）電腦架構

此弱存取模式特徵是和傳統程式師假設的強存取模式不同,
CPU(讀或寫)存取兩記憶體內容之順序,假設先變數X,再變數Y,
實際存取順序卻視快取存在與否,而可能先變數Y,再變數X,
即有關記憶體存取之指令順序(program order)可能和實際資料存取順序(data order)不同.

以Peterson演算法來看,其出錯情況如下,
兩者原始指令順序

CPU_A: flag[A]=true  →  turn=B  → flag[B]==false  → turn==A 

CPU_B: flag[B]=true  →  turn=A  → flag[A]==false  → turn==B

假設
CPU_A正有flag[B]快取為false,但無flag[A],turn快取,
CPU_B正有flag[A]快取為false,但無flag[B],turn快取,
則雙方會在各自認為自己指令結果不衝突之下,
調整資料讀取順序如下,

兩者實際資料順序

CPU_A: flag[B]==false → flag[A]=true → turn=B → turn==A 

CPU_B: flag[A]==false → flag[B]=true → turn=A → turn==B

於是雙方都會認為對方旗標測試為假,而同時進入重要區段.

至於單CPU且記憶體採弱循序存取模式(weak memory access model)的電腦架構下,
Peterson演算法有沒有問題,我猜測應該沒有問題,
因為將兩者原始指令作任意組合後,在沒有衝突情況下調整順序,皆似乎不會造成兩者同進.
但這點文獻上尚未獲得佐證.

2️⃣ 多 CPU + 強記憶體存取模式（Strong Memory Access Model）但無快取一致性管理
各CPU有獨立快取記憶體,而未作快取一致性管理的電腦架構,

所謂強存取模式特徵是
某一顆CPU(讀或寫)存取兩記憶體內容之順序,假設先變數X,再變數Y,
其他CPU觀察到實際存取順序一定也是先變數X,再變數Y,
即有關記憶體存取之指令順序一定和實際存取順序相同.

以 Peterson 演算法來看,其出錯情況為 CPU 快取管理出現不一致時,如下,
若CPU A執行A緒欲進入重要區段,分享資源,先設定A使用旗標為真,及輪用者為B緒,
但兩設定皆只寫入A的快取記憶體,尚未反應到實際記憶體;
同時間,CPU B執行B緒,亦欲進入重要區段,分享資源,遂設定B使用旗標為真,及輪用者為A緒,同樣,兩設定亦皆只寫入B的快取記憶體,而尚未反應到實際記憶體;
則接下來A,B雙方測試讀取對方使用旗標時,若其值皆尚未進入快取,而自實際記憶體取得,將得值為假,
雙方就會誤以為只有自己想進入重要區段而同時進入.

故在記憶體採強循序存取模式(strong memory access model),即指令及資料順序相同下
若電腦架構為單CPU,或
雙CPU但共用快取記憶體,或
雙CPU未共用快取但有作快取一致性管理時,Peterson演算法就不會失效.

Reference:

1. Wiki: Peterson's_algorithm
2. bhattacharya-dcc-02-issues in multiprocessor memory consistency protocol design and verification
3. ridge-springer-07-operatinal reasoning for concurrent caml programs and weak memory models
4. holzmann-iel-07-the design of a multicore extension of the spin model checker
5. higham---implementing sequentially consistent programs on processor consistent platforms
6. Muller: Weak Memory Models are a Strong Reminder for Programmers to use Synchronization Primitives
   Thus any algorithm that is based on a strong ordering assumption may fail in a system that is allowed to reorder memory request, Dijkstra’s and Peterson’s synchronization algorithms fail [1,2,5], for example.
7. Wiki: Out of order execution
8. YouTube: The 80’s Algorithm to Avoid Race Conditions (and Why It Failed)