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 CPU_B
flag[A]=true flag[B]=true
turn=B turn=A
flag[B]==false flag[A]==false
turn==A turn==B
假設
CPU_A正有flag[B]快取為false,但無flag[A],turn快取,
CPU_B正有flag[A]快取為false,但無flag[B],turn快取,
則雙方會在各自認為自己指令結果不衝突之下,
調整資料讀取順序如下,
兩者實際資料順序
CPU_A CPU_B
flag[B]==false flag[A]==false
flag[A]=true flag[B]=true
turn=B turn=A
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.http://en.wikipedia.org/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.http://cis.poly.edu/muller/CS623/weakmemory.htm
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.http://docs.sun.com/app/docs/doc/801-6659/6i116aqnb?l=zh_TW&a=view
8.http://en.wikipedia.org/wiki/Out-of-order_execution