引用自 計(jì)算機(jī)系統(tǒng) 核心概念及軟硬件實(shí)現(xiàn)
第一次嘗試實(shí)現(xiàn)互斥
#嘗試編程實(shí)現(xiàn)互斥
#進(jìn)程1
do
while (turn != 1)
; //nothing
cirtical section
turn = 2;
remainder section
while ( ! done1);
#進(jìn)程2
do
while (turn != 2)
; //nothing
critical section
turn = 1;
remainder section
while (! done2);
此算法保證了互斥，但要求進(jìn)程嚴(yán)格交替執(zhí)行do循環(huán)，存在問題：如果一直想執(zhí)行進(jìn)程1而不執(zhí)行進(jìn)程2，那么此實(shí)現(xiàn)時(shí)無法做到的
第二次嘗試實(shí)現(xiàn)互斥
#編程實(shí)現(xiàn)互斥的另一次嘗試
#進(jìn)程1
do
enter1 = TRUE;
while (enter2)
; //nothing
critical section
enter1 = FALSE;
remainder section
while (! done1);
#進(jìn)程2
do
enter2 = TRUE;
while (enter1)
; //nothing
critical section
enter2 = FALSE;
remainder section
while (! done2);
此算法保證了互斥，也能夠?qū)崿F(xiàn)：某一進(jìn)程多次執(zhí)行而另一線程不被執(zhí)行绳泉。
但，此算法有死鎖：進(jìn)程1設(shè)置enter1為TRUE后陈轿，調(diào)度進(jìn)程2圈纺，進(jìn)程2設(shè)置enter2為TRUE，然后進(jìn)程2判斷while (enter1)麦射，此循環(huán)耗盡時(shí)間片（進(jìn)程2無法進(jìn)入臨界區(qū)蛾娶、后續(xù)執(zhí)行代碼），調(diào)度進(jìn)程1潜秋，進(jìn)程1判定while (enter2)條件也成立蛔琅，循環(huán)而無法進(jìn)入臨界區(qū)、執(zhí)行后續(xù)代碼峻呛，死鎖形成罗售。
Perterson互斥算法
#Perterson互斥算法
#進(jìn)程1
do
enter1 = TRUE;
turn = 2;
while (enter2 && (turn == 2))
; //nothing
critical section
enter1 = FALSE;
remainder section
while (! dine1);
#進(jìn)程2
do
enter2 = TRUE;
turn = 1;
while (enter1 && (turn == 1))
; //nothing
critical section
enter2 = FALSE;
remainder section
while (! done2);
直接理解Peterson算法，可能略顯晦澀钩述，不好區(qū)分enter和turn的含義寨躁，梳理Peterson算法的邏輯含義。
怎么理解Perterson算法呢牙勘？我們給出一個(gè)與上述算法類似的編碼實(shí)現(xiàn)职恳，對比方便理解：
#Perterson算法的類比編碼實(shí)現(xiàn)
/*此實(shí)現(xiàn)直觀地結(jié)合了“第一次嘗試實(shí)現(xiàn)互斥”和“第二次嘗試實(shí)現(xiàn)互斥”*/
#進(jìn)程1
do
enter1 = TRUE;
while (enter2 && (turn == 2))
; //nothing
critical section
enter1 = FALSE;
turn = 2;
remainder section
while ( !done1);
#進(jìn)程2
do
enter2 = TRUE;
while (enter1 && (turn == 1))
; //nothing
critical section
enter2 = FALSE;
turn = 1;
remainder section
while (! done2)
上面這個(gè)編碼實(shí)現(xiàn)，結(jié)合了前兩種編碼實(shí)現(xiàn)方式（第一次嘗試實(shí)現(xiàn)互斥方面、第二次嘗試實(shí)現(xiàn)互斥）放钦，可以達(dá)到互斥、某一線程持續(xù)調(diào)度恭金、無死鎖的設(shè)計(jì)【不具體分析各場景操禀，可參考計(jì)算機(jī)系統(tǒng) 核心概念及軟硬件實(shí)現(xiàn)】。
我們的編碼實(shí)現(xiàn)是什么含義呢横腿？
-
enter1 = TRUE表示進(jìn)程1準(zhǔn)備進(jìn)入臨界區(qū)颓屑，enter1 = FALSE；turn = 2表示進(jìn)程1離開臨界區(qū)耿焊，進(jìn)程2可以進(jìn)去臨界區(qū)揪惦。 - 進(jìn)程2在臨界區(qū)中時(shí)，進(jìn)程1無法進(jìn)入臨界區(qū)（
while (enter2 && (turn == 2)）搀别。 - 進(jìn)程1執(zhí)行完畢臨界區(qū)代碼后丹擎，才允許進(jìn)程2進(jìn)入臨界區(qū)（
turn = 2）尾抑。
基于上面的理解歇父，我們這樣理解Peterson算法：
- enter理解為蒂培，進(jìn)程有進(jìn)入臨界區(qū)的意圖（
enter1 = TRUE表示進(jìn)程1有意圖進(jìn)入臨界區(qū)）； - turn理解為榜苫，并發(fā)系統(tǒng)允許進(jìn)入臨界區(qū)的進(jìn)程（
turn = 1表示并發(fā)控制系統(tǒng)判定進(jìn)程1可以進(jìn)入臨界區(qū)）护戳； - 進(jìn)程有進(jìn)入臨界區(qū)的意圖，并且垂睬，系統(tǒng)允許其進(jìn)入臨界區(qū)的進(jìn)程媳荒，才可以進(jìn)入臨界區(qū)（
enter1 && (turn == 1)）； - 對進(jìn)程1驹饺，如果互斥的進(jìn)程（進(jìn)程2）滿足上述第3點(diǎn)钳枕，那么進(jìn)程1循環(huán)等待，以禮讓進(jìn)程2先進(jìn)入臨界區(qū)（
while (enter2 && (turn == 2); //nothing）赏壹。 - 進(jìn)程1是這樣禮讓進(jìn)程2的鱼炒，
turn = 2，turn是可以理解為并發(fā)控制系統(tǒng)允許進(jìn)入臨界區(qū)的進(jìn)程蝌借。
最后昔瞧，比較我們編寫的實(shí)現(xiàn)方式和Peterson算法，我們編寫的方式雖然效果與Perterson算法相同菩佑，但有缺陷：
- 系統(tǒng)最初運(yùn)行時(shí)自晰，需要一個(gè)turn值，此turn值即并發(fā)系統(tǒng)允許運(yùn)行的第一個(gè)進(jìn)程（不具體分析場景）稍坯，此設(shè)計(jì)可以理解為硬編碼酬荞，人為干預(yù)并發(fā)系統(tǒng)調(diào)度，不好劣光；
- 進(jìn)程離開臨界區(qū)后修改turn值袜蚕，這個(gè)turn值決定了下一次進(jìn)程并發(fā)時(shí)哪一個(gè)進(jìn)程可以繼續(xù)執(zhí)行，這就導(dǎo)致了绢涡，并發(fā)調(diào)度結(jié)果取決于上一次并發(fā)執(zhí)行的順序牲剃，每次并發(fā)調(diào)度不是獨(dú)立的，不好雄可。
