如何更好理解Peterson算法？
如何更好理解Peterson算法？
1 Peterson算法提出的背景
在我們講述Peterson算法之間，我們先了解一下Peterson算法提出前的背景（即：在這個算法提出之前，前人們都做了哪些工作）這對於我們之後理解Peterson算法有很大的裨益。
Peterson 算法是基於雙線程互斥訪問的LockOne與LockTwo算法而來。LockOne算法使用一個 flag 布爾數組，LockTwo 使用一個 turn的整型量，都實現了互斥，但是都存在死鎖的可能。Peterson 算法把這兩種算法結合起來，完美地用軟件實現了雙線程互斥問題。
2 Peterson算法
首先，我們來看看下面這兩段代碼：
Pi進程：
flag[i] = True;
while(flag[j]);
critical section;
flag[i] = False;
remainder section;
Pj進程：
flag[j] = True;
while(flag[i]);
critical section;
flag[j] = False;
remainder section;
以上是用來實現兩個進程互斥訪問臨界區的兩端代碼，我們可以這樣來理解這兩段代碼，其中flag[i]表示進程Pi表示想要進入臨界區，while(flag[j])可以理解為Pi在自己進臨界區之前，先問問Pj是否想要進入臨界區，如果Pj想進的話它就等待（Pi品德高尚）；類似的，Pj也是同樣的。雙方互相謙讓的結果是，最終兩個進程誰也進不了臨界區。（可以想像這樣一個生活場景，兩個人同時想進屋，結果在門口謙讓了了半天，過了很久都沒進去）
Peterson算法就是在上面代碼的基礎之上，又引入了一個變量turn，打破了這種因為謙讓而導致「飢餓」的現象。下面我們先來看看Peterson算法的代碼：
Pi進程：
flag[i] = True;
turn = j;
while(flag[j] && turn == j);
critical section;
flag[i] = False;
remainder section;
Pj進程：
flag[j] = True;
turn = i;
while(flag[i] && turn == i);
critical section;
flag[j] = False;
remainder section;
怎麼理解變量turn呢？可以將turn變量理解成輪到誰進入臨界區了。舉個例子：turn = i，表示輪到Pi進入臨界區。那麼上面這個代碼就可以理解為：首先，Pi想進入臨界區（flag[i] = True），然後，還是和前面的代碼一樣，Pi會先把進入臨界區的機會讓給Pj（turn = j），同樣地，當Pj想進入臨界區時，也會將進入臨界區的權利先讓給Pi。緊接着，變量turn的作用就顯現出來了，當Pj把進入臨界區的機會又讓給Pi的時候（注意：這是發生在Pi將進入臨界區的優先權讓給Pj之後），Pi這次就會直接進入臨界區。就不會再次出現一直互相謙讓，最終導致均無法進入臨界區的情況了。
關於為什麼當進入臨界區的權利（即turn = i）又回到Pi手裡時，Pi會直接進入臨界區的分析？我們可以分析一下Pi能夠成功進入臨界區的條件（即：while(flag[j] && turn == j)語句）：
總的分為以下兩種情況：
-
Pj不想進入臨界區（flag[j] = False）
當Pj不想進入臨界區時，自然也就不存在Pi和Pj衝突的情況，Pi當然就直接進入臨界區。
-
Pj想進入臨界區（flag[j] = True）
當Pj想進入臨界區，又分為以下兩種情況：
-
當 turn = i
turn = i說明當前輪到i進入臨界區了 ，這個時候i就直接進入臨界區了，不再謙讓。（其實這個挺合理的，根據Peterson算法的代碼我們不難發現因為turn的值是根據先後想要進入臨界區的順序排列的）
-
當 turn != i
turn != i 說明當前輪到i進入臨界區了沒有輪到Pi進入臨界區，Pi自然需要等待。
僅過上面的分析，我們就不難理解，當Pi和Pj經過一輪謙讓之後，就會直接根據turn的值（即：該輪到誰進臨界區了）來直接決定誰該進入臨界區。現在回過頭回顧整個算法，其實我們會發現，Peterson算法的思想會更貼近於生活中的真實情況，大家一般都是略微謙讓一下，然後直奔主題，難道不是嗎？哈哈
3 參考資料
[1]維基百科編者. Peterson算法[G/OL]. 維基百科, 2021(20210501)[2021-05-01]. //zh.wikipedia.org/w/index.php?title=Peterson%E7%AE%97%E6%B3%95&oldid=65429794.
