操作系統(tǒng)原理與實(shí)例分析

1、2.6 進(jìn)程互斥與同步 ？采用多道程序設(shè)計(jì)技術(shù)的操作系統(tǒng)，允許多個(gè)進(jìn)程同時(shí)駐留內(nèi)存并發(fā)執(zhí)行。？如何協(xié)調(diào)多個(gè)進(jìn)程對(duì)系統(tǒng)資源，如內(nèi)存空間、外部設(shè)備等的競(jìng)爭(zhēng)和共享？如何解決多個(gè)進(jìn)程因?yàn)楦?jìng)爭(zhēng)資源而出現(xiàn)執(zhí)行結(jié)果異常，甚至導(dǎo)致系統(tǒng)不穩(wěn)定、失效等問(wèn)題？例如，多個(gè)進(jìn)程同時(shí)申請(qǐng)文件打印，如何有效分配打印機(jī)？ 例如銀行的聯(lián)網(wǎng)儲(chǔ)蓄業(yè)務(wù)允許儲(chǔ)戶(hù)同時(shí)用儲(chǔ)蓄卡和存折對(duì)同一帳戶(hù)進(jìn)行存取款操作，如果某儲(chǔ)戶(hù)同時(shí)（在A(yíng)TM機(jī)和營(yíng)業(yè)柜臺(tái)）辦理兩筆存款業(yè)務(wù)（假設(shè)分別為1000和2000元）從系統(tǒng)的角度看，有兩個(gè)進(jìn)程將同時(shí)對(duì)儲(chǔ)戶(hù)余額等數(shù)據(jù)進(jìn)行修改。如果兩個(gè)進(jìn)程同時(shí)讀出原余額（假設(shè)為5000元），兩個(gè)進(jìn)程分別將最新余額修改為6000（5

2、000+1000）和7000（5000+2000）。分析及措施最后，儲(chǔ)戶(hù)余額可能是6000，或者7000，顯然都不正確。原因：兩個(gè)進(jìn)程同時(shí)修改同一數(shù)據(jù)，而沒(méi)有進(jìn)行有效控制。正確的方法：如果有多個(gè)進(jìn)程需要同時(shí)修改某一數(shù)據(jù)，系統(tǒng)必須控制，一次僅允許一個(gè)進(jìn)程完成讀數(shù)據(jù)，并修改數(shù)據(jù)兩件事以后，才允許別的進(jìn)程對(duì)同一數(shù)據(jù)的讀和修改操作。 例假設(shè)系統(tǒng)中有3個(gè)進(jìn)程P1、P2、P3，其中P1和P2是計(jì)算進(jìn)程，P3是打印進(jìn)程，每當(dāng)P1或P2計(jì)算出一個(gè)結(jié)果以后，將計(jì)算結(jié)果送到緩存區(qū)中，以便P3進(jìn)程從中取出數(shù)據(jù)打印。假設(shè)緩沖區(qū)被劃分為0、1、2.n-1共n個(gè)單元。有兩個(gè)指針:in指針用于計(jì)算進(jìn)程存放數(shù)據(jù)，指向緩沖區(qū)中

3、下一個(gè)空閑的單元，out指針用于打印進(jìn)程取數(shù)據(jù)，指向緩沖區(qū)中下一個(gè)將取走數(shù)據(jù)的單元。例假設(shè)某時(shí)刻，0到3號(hào)單元空閑，4到6號(hào)單元被占用，這時(shí)候P1、P2進(jìn)程都準(zhǔn)備將數(shù)據(jù)送入緩沖區(qū)，如圖2.23所示。 0 1 2 3 4 5 6 7 8 n-1：被占用單元：空閑單元inout圖2.23 多個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)共享區(qū)可能發(fā)生的情況進(jìn)程P1需要向緩沖區(qū)存儲(chǔ)數(shù)據(jù)，并知道in指針當(dāng)前指向7號(hào)空閑緩沖單元。若這時(shí)進(jìn)程P1的時(shí)間片用完，被中斷，調(diào)度程序調(diào)度進(jìn)程P2執(zhí)行。P2正好也需要向緩沖區(qū)存放數(shù)據(jù)，首先獲取in指針位置，同樣也是7，于是，P2將數(shù)據(jù)送入7號(hào)單元，并將in指針移動(dòng)一格，指向8號(hào)單元，然后繼續(xù)執(zhí)行其

4、他操作。 可能發(fā)生的情況當(dāng)進(jìn)程P1再次被調(diào)度執(zhí)行時(shí)，將從上次的斷點(diǎn)繼續(xù)執(zhí)行，即將數(shù)據(jù)送入7號(hào)單元（覆蓋進(jìn)程P2的數(shù)據(jù)），并移動(dòng)in指針指向8號(hào)單元，然后繼續(xù)執(zhí)行其他操作。進(jìn)程P3不會(huì)發(fā)現(xiàn)上述錯(cuò)誤，繼續(xù)從緩沖區(qū)取數(shù)據(jù)，進(jìn)行打印。顯然，進(jìn)程P2的相應(yīng)計(jì)算結(jié)果不會(huì)被打印輸出。 分析該例中，由于進(jìn)程P1和P2共享緩沖區(qū)和位置指針，而未對(duì)這種共享進(jìn)行有效控制，導(dǎo)致打印數(shù)據(jù)的丟失。如果控制進(jìn)程P1、P2互斥地訪(fǎng)問(wèn)緩沖區(qū)和修改位置指針，將避免這種因?yàn)椴l(fā)執(zhí)行而導(dǎo)致的程序執(zhí)行結(jié)果的不確定性。結(jié)論 通過(guò)上述兩個(gè)例子可見(jiàn)，采用多道程序并發(fā)設(shè)計(jì)技術(shù)的操作系統(tǒng)對(duì)諸進(jìn)程的并發(fā)控制是非常重要和必需的。 并發(fā)控制 - 競(jìng)爭(zhēng)

5、資源 當(dāng)并發(fā)進(jìn)程競(jìng)爭(zhēng)使用同一資源時(shí)，它們之間就會(huì)發(fā)生沖突。如果操作系統(tǒng)將資源分配給其中的某一個(gè)進(jìn)程使用，另一個(gè)進(jìn)程就必須等待，直到申請(qǐng)的資源可用時(shí)，由操作系統(tǒng)分配給它。如果競(jìng)爭(zhēng)某資源的進(jìn)程太多，這些進(jìn)程還必須等待在一個(gè)隊(duì)列中，如就緒隊(duì)列，阻塞隊(duì)列等。一種極端的情況是，被阻塞進(jìn)程永久得不到申請(qǐng)的資源，而死鎖。 并發(fā)控制 - 競(jìng)爭(zhēng)資源進(jìn)程競(jìng)爭(zhēng)資源首先必須解決“互斥”問(wèn)題。某些資源必須互斥使用，如打印機(jī)、共享變量、表格、文件等。這類(lèi)資源又稱(chēng)為臨界資源，訪(fǎng)問(wèn)臨界資源的那段代碼稱(chēng)為臨界區(qū)。任何時(shí)刻，只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)，以此實(shí)現(xiàn)進(jìn)程對(duì)臨界資源的互斥訪(fǎng)問(wèn)。臨界區(qū)進(jìn)入?yún)^(qū)退出區(qū)進(jìn)程喚醒阻塞隊(duì)列圖2.24進(jìn)

6、程互斥進(jìn)入臨界區(qū)互斥使用臨界資源當(dāng)進(jìn)程需要使用臨界資源時(shí)，通過(guò)獲得臨界區(qū)的使用權(quán)實(shí)現(xiàn)的。首先，在“進(jìn)入?yún)^(qū)”判斷是否可以進(jìn)入臨界區(qū)，如果可以進(jìn)入，則必須設(shè)置臨界區(qū)使用標(biāo)志，阻止其它后來(lái)的進(jìn)程進(jìn)入臨界區(qū)。后來(lái)的進(jìn)程通過(guò)查看臨界區(qū)使用標(biāo)志，知道自己不能進(jìn)入臨界區(qū)，就進(jìn)入阻塞隊(duì)列，將自己阻塞。當(dāng)臨界區(qū)內(nèi)的進(jìn)程使用完畢，退出臨界區(qū)時(shí)，即在“退出區(qū)”修改臨界區(qū)使用標(biāo)志，并負(fù)責(zé)喚醒阻塞隊(duì)列中的一個(gè)進(jìn)程，讓其進(jìn)入臨界區(qū)。互斥使用臨界資源由于同一個(gè)臨界資源在多個(gè)共享它的進(jìn)程中將對(duì)應(yīng)多個(gè)臨界區(qū)，那么怎樣才能保證諸進(jìn)程間互斥地執(zhí)行臨界區(qū)呢？這就必須保證“臨界區(qū)使用標(biāo)志”是可被系統(tǒng)中所有進(jìn)程共享的全局變量，而且諸進(jìn)程

7、對(duì)該標(biāo)志的修改操作必須互斥進(jìn)行。 臨界區(qū)使用原則（也稱(chēng)為互斥條件） 每次只允許一個(gè)進(jìn)程處于臨界區(qū)（忙則等待）；進(jìn)程只能在臨界區(qū)內(nèi)逗留有限時(shí)間，不得使其它進(jìn)程在臨界外無(wú)限期等待（有限等待）如果臨界區(qū)空閑，則只要有進(jìn)程申請(qǐng)就立即讓其進(jìn)入（空閑讓進(jìn)）；進(jìn)入臨界區(qū)的進(jìn)程，不能在臨界區(qū)內(nèi)長(zhǎng)時(shí)間阻塞等待某事件，必須在一定期限內(nèi)退出臨界區(qū)（讓權(quán)等待）不能限制進(jìn)程的執(zhí)行進(jìn)度及處理機(jī)的數(shù)量競(jìng)爭(zhēng)資源可能引起死鎖例如，兩個(gè)進(jìn)程P1、P2，競(jìng)爭(zhēng)資源R1、R2。假設(shè) ，現(xiàn)在P1已經(jīng)占用了R1，且P2占用了R2，如果此時(shí)P1申請(qǐng)R2，且P2申請(qǐng)R1。會(huì)怎么樣呢？結(jié)果是P1、P2雙方都占用對(duì)方申請(qǐng)的資源而阻塞，誰(shuí)也不讓步地

8、永久等待，這就是死鎖，如圖2.25。 R1P1占用P2R2占用申請(qǐng)申請(qǐng)圖2.25 進(jìn)程因競(jìng)爭(zhēng)資源而死鎖死鎖競(jìng)爭(zhēng)資源 - 饑餓假設(shè)有3個(gè)進(jìn)程P1、P2、P3，每個(gè)進(jìn)程都需要周期性的使用資源R。如果當(dāng)前P1正在使用臨界資源R，P2和P3因?yàn)榈却齊而阻塞。當(dāng)P1退出臨界區(qū)時(shí)，P2立即進(jìn)入臨界區(qū)執(zhí)行，若P2還未退出臨界區(qū)時(shí)，P1又申請(qǐng)使用臨界資源R。假設(shè)P2退出臨界區(qū)后，系統(tǒng)將R分給了P1，然后，當(dāng)R空閑時(shí)，又將其分給P2，如此反復(fù)。競(jìng)爭(zhēng)資源 - 饑餓使P1、P2都能正常執(zhí)行，而P3被長(zhǎng)時(shí)間饑餓。這種情況不是死鎖，但是對(duì)P3不公平，也是系統(tǒng)應(yīng)該避免的。 并發(fā)控制 -共同協(xié)作多個(gè)進(jìn)程常常需要共同修改某些

9、共享變量、表格、文件數(shù)據(jù)庫(kù)等，協(xié)作完成一些功能。必須確保它們對(duì)共享變量的修改是正確的，保證數(shù)據(jù)的完整性。共享協(xié)作同樣涉及到互斥、死鎖和饑餓問(wèn)題，但更強(qiáng)調(diào)對(duì)數(shù)據(jù)的寫(xiě)操作必須互斥地進(jìn)行。 必須保證數(shù)據(jù)的一致性。前面列舉了銀行聯(lián)網(wǎng)儲(chǔ)蓄的例子，除了必須保證儲(chǔ)戶(hù)余額的正確性以外，還必須使銀行儲(chǔ)蓄總余額、當(dāng)日發(fā)生額、流水帳等數(shù)據(jù)得到一致的修改。一般通過(guò)事務(wù)處理來(lái)保證數(shù)據(jù)的一致性，可以將對(duì)儲(chǔ)戶(hù)余額、儲(chǔ)蓄總余額、當(dāng)日發(fā)生額、流水帳等數(shù)據(jù)的修改放到一個(gè)臨界區(qū)中，進(jìn)入臨界區(qū)的進(jìn)程必須一次性完成對(duì)這一系列數(shù)據(jù)的修改操作。只有該進(jìn)程退出臨界區(qū)以后，才允許別的進(jìn)程進(jìn)入臨界區(qū)進(jìn)行數(shù)據(jù)修改，以保證數(shù)據(jù)的一致性。 并發(fā)控制

10、-通信協(xié)作當(dāng)進(jìn)程進(jìn)行通信合作時(shí)，各個(gè)進(jìn)程之間需要建立連接，進(jìn)程通信需要同步和協(xié)調(diào)。進(jìn)程通信的方式很多，包括消息傳遞、管道、共享存儲(chǔ)區(qū)等。通過(guò)消息傳遞實(shí)現(xiàn)進(jìn)程通信時(shí)，由于沒(méi)有共享資源，故無(wú)須互斥，但仍可能出現(xiàn)死鎖和饑餓。并發(fā)控制 -通信協(xié)作例如，兩個(gè)進(jìn)程相互等待對(duì)方發(fā)來(lái)的數(shù)據(jù)而永久阻塞，即死鎖。又如，3個(gè)進(jìn)程P1、P2、P3，其中P1不斷嘗試與P2或P3通信，P2和P3又不斷嘗試與P1通信，如果P1與P2總能成功建立連接進(jìn)行通信，而P3一直阻塞等待P1，這樣P3被長(zhǎng)時(shí)間饑餓。 互斥與同步的解決策略軟件方法硬件方法信號(hào)量方法管程方法消息傳遞方法軟件方法軟件方法是指由進(jìn)程自己，通過(guò)執(zhí)行相應(yīng)的程序指令

11、，實(shí)現(xiàn)與別的進(jìn)程的同步與互斥，無(wú)須專(zhuān)門(mén)的程序設(shè)計(jì)語(yǔ)言或操作系統(tǒng)的支持。實(shí)踐證明，該方法很難正確控制進(jìn)程間的同步與互斥，而且可能會(huì)大大地增加系統(tǒng)的額外開(kāi)銷(xiāo)， 硬件方法為了解決軟件方法存在的不足，有人提出了硬件解決方法，通過(guò)屏蔽中斷或采用專(zhuān)門(mén)的機(jī)器指令控制同步與互斥。與軟件解決方法比較，這種方法減少了系統(tǒng)額外開(kāi)銷(xiāo)，但由于需要太強(qiáng)的硬件約束條件，以及可能導(dǎo)致進(jìn)程饑餓與死鎖現(xiàn)象，一直沒(méi)有成為通用的解決方法。 另一類(lèi)解決方法是由操作系統(tǒng)，或?qū)ｉT(mén)的程序設(shè)計(jì)語(yǔ)言提供的特別支持，包括信號(hào)量方法、管程方法和消息傳遞方法。其中，信號(hào)量方法已經(jīng)成為控制進(jìn)程同步與互斥的通用方法 互斥與同步解決方法之一：軟件方法 軟件

12、解決方法有很多種，比較有代表性的軟件方法有荷蘭數(shù)學(xué)家Dekker提出的Dekker算法和科學(xué)家G.L.Peterson提出的Peterson算法。為了說(shuō)明設(shè)計(jì)并發(fā)程序時(shí)可能出現(xiàn)的典型錯(cuò)誤，下面以Dekker算法為例，分析如何設(shè)計(jì)并改進(jìn)一個(gè)互斥算法的過(guò)程。 互斥與同步解決方法之一：軟件方法-初步設(shè)想 為了控制兩個(gè)進(jìn)程互斥進(jìn)入臨界區(qū)，可以讓兩個(gè)進(jìn)程輪流進(jìn)入臨界區(qū)。當(dāng)一個(gè)進(jìn)程正在臨界區(qū)執(zhí)行時(shí)，另一個(gè)進(jìn)程就不能進(jìn)入臨界區(qū)，而在臨界區(qū)外等待。程序?qū)崿F(xiàn)的偽代碼如圖2.26所示。 var turn: 0.1; /*共享的全局變量*/ P0 P 1 while turn 0 do nothing; while

13、 turn 1 do nothing; turn:=1; turn:=0; 圖2.26 互斥算法：初步設(shè)想分析：初步設(shè)想保證了互斥問(wèn)題1：“忙等”現(xiàn)象問(wèn)題2：進(jìn)程嚴(yán)格交替進(jìn)入臨界區(qū)。如果進(jìn)程需要多次使用臨界區(qū)，那么，使用臨界區(qū)頻率低的進(jìn)程嚴(yán)重制約著使用臨界區(qū)頻率高的進(jìn)程的執(zhí)行進(jìn)度。分析：初步設(shè)想例如，P0需要每10分鐘使用一次臨界區(qū)，P1需要每1分鐘使用一次臨界區(qū)。假設(shè)turn的初值為0，進(jìn)程P0正好先請(qǐng)求進(jìn)入臨界區(qū)，并成功進(jìn)入臨界區(qū)執(zhí)行，這時(shí)，如果P1申請(qǐng)進(jìn)入臨界區(qū)，循環(huán)檢測(cè)turn=0，不可以進(jìn)入，只能“空”循環(huán)，等待。當(dāng)P0退出臨界區(qū)時(shí)，修改turn的值為1。P1循環(huán)檢測(cè)到turn =

14、1時(shí)，就可以進(jìn)入臨界區(qū)執(zhí)行，退出臨界區(qū)時(shí)，修改turn=0。分析：初步設(shè)想例如（續(xù)）根據(jù)假設(shè)，P1很快又需要進(jìn)入臨界區(qū)，但是P0卻只能在10分鐘之后，按照turn規(guī)定的順序，進(jìn)入臨界區(qū)執(zhí)行，退出時(shí)修改turn=1。即，P1必須在臨界區(qū)空閑的情況下，等待10分鐘，才能使用臨界區(qū)。這不符和互斥原則，降低了系統(tǒng)性能。分析：初步設(shè)想問(wèn)題3：任何進(jìn)程在臨界區(qū)內(nèi)或外失敗，其他進(jìn)程將可能因?yàn)榈却褂门R界區(qū)，而無(wú)法向前推進(jìn)。因?yàn)閮蓚€(gè)進(jìn)程相互依賴(lài)對(duì)方將臨界區(qū)的使用權(quán)（順序）進(jìn)行修改，一旦這種修改不能進(jìn)行，對(duì)方都將因?yàn)榈却R界區(qū)而無(wú)法推進(jìn)。 互斥與同步解決方法之一：軟件方法-第一次改進(jìn)可以為臨界區(qū)設(shè)置一個(gè)狀態(tài)標(biāo)志

15、，標(biāo)明臨界區(qū)是否可用。當(dāng)臨界區(qū)空閑時(shí)，任何一個(gè)進(jìn)程都能進(jìn)入，但此時(shí)必須修改臨界區(qū)標(biāo)志為“被占用”，別的進(jìn)程就不能進(jìn)入臨界區(qū)。當(dāng)臨界區(qū)使用完畢，必需修改該標(biāo)志為“空閑”。這樣就不再使諸進(jìn)程嚴(yán)格交替使用臨界區(qū)，而且，如果某進(jìn)程在臨界區(qū)外失敗，也不會(huì)影響其它進(jìn)程。其算法描述如圖2.27所示。 var flag : array 0.1 of boolean :false ; /*共享的全局變量*/ P0 P1 while flag1 do nothing; while flag0 do nothing;flag0:=true; flag1:=true; flag0:=false; flag1:=fal

16、se; 圖2.27 互斥算法：第一次改進(jìn)分析：第一次改進(jìn)如果進(jìn)程在臨界區(qū)外失敗，其他進(jìn)程不會(huì)阻塞。問(wèn)題1：“忙等”問(wèn)題2：若進(jìn)程在臨界區(qū)內(nèi)失敗且相應(yīng)的flag為true，則其他進(jìn)程永久阻塞。問(wèn)題3：不能保證進(jìn)程互斥進(jìn)入臨界區(qū)。請(qǐng)?jiān)囍匆韵马樞驁?zhí)行： P0If flag1=falsewhile flag1中斷P1If flag0=falsewhile flag0flag0=true中斷中斷flag1=true臨界區(qū)互斥與同步解決方法之一：軟件方法-第二次改進(jìn)互斥算法的第一次改進(jìn)不能實(shí)現(xiàn) “互斥” 。因?yàn)?，進(jìn)程首先檢測(cè)臨界區(qū)狀態(tài)，若“被占用”，則“忙等”，否則就直接進(jìn)入臨界區(qū)。從而，可能出現(xiàn)同時(shí)進(jìn)

17、入臨界區(qū)的現(xiàn)象。能否讓進(jìn)程預(yù)先表明“希望進(jìn)入臨界區(qū)的態(tài)度”，然后，再檢測(cè)臨界區(qū)狀態(tài)。第二次改進(jìn)，如圖2.28。var flag : array 0.1 of boolean :false ; /*共享的全局變量*/P0 P1 flag0:=true; flag1:=true;while flag1 do nothing; while flag0 do nothing; flag0:=false; flag1:=false; 圖2.28 互斥算法：第二次改進(jìn)分析：第二次改進(jìn)假設(shè)P0需要進(jìn)入臨界區(qū)，首先執(zhí)行flag0:=true，再執(zhí)行while flag1，若P1正在占用臨界區(qū)，則P0忙等；否則

18、，P0進(jìn)入臨界區(qū)。但是，如果此時(shí)P1未占用臨界區(qū)，而與P0幾乎同時(shí)需要使用臨界區(qū)， P0flag0=true中斷P1flag1=true中斷while flag1while flag0忙等忙等死鎖互斥與同步解決方法之一：軟件方法-第三次改進(jìn)互斥算法的第二次改進(jìn)可能導(dǎo)致死鎖，因?yàn)镻0、P1都“堅(jiān)持自己的權(quán)利，執(zhí)意進(jìn)入臨界區(qū)，且互不謙讓”?？梢钥紤]，允許進(jìn)程既表明需要進(jìn)入臨界區(qū)的“態(tài)度”，又能相互“謙讓”。即首先表示自己需要使用臨界區(qū)，再檢測(cè)臨界區(qū)的狀態(tài)，若臨界區(qū)“被占用”，可以等一小段時(shí)間再申請(qǐng)。算法如圖2.29所示var flag : array 0.1 of boolean :false ;

19、 /*共享的全局變量*/P0 P1 flag0:=true; flag1:=true;while flag1 do while flag0 do begin begin flag0 :=false; flag1 :=false; ; ; flag0:=true; flag1:=true;end; end; flag0:=false; flag1:=false; 圖2.29 互斥算法：第三次改進(jìn)分析：第三次改進(jìn)P0、P1的“謙讓”可能使它們都不能進(jìn)入臨界區(qū)。這種現(xiàn)象不是死鎖，因?yàn)檫@種僵局不會(huì)是永久行為，某一時(shí)刻可能會(huì)自動(dòng)解除。但是，這種現(xiàn)象也是不希望出現(xiàn)的。 P0flag0=true中斷P1fl

20、ag1=true中斷while flag1中斷while flag0中斷flag0：=false延遲一段時(shí)間中斷flag1：=false延遲一段時(shí)間中斷flag0=trueflag1=true中斷中斷互斥與同步解決方法之一：軟件方法-Dekker互斥算法 該算法既允許進(jìn)程“謙讓地”申請(qǐng)進(jìn)入臨界區(qū)，又通過(guò)給定序號(hào)避免“過(guò)分謙讓”。偽代碼描述如圖2.30 所示。var flag : array 0.1 of boolean :false ; /*共享的全局變量，表示臨界區(qū)狀態(tài)*/turn : 0.1; /*共享的全局變量，表示進(jìn)入臨界區(qū)的順序*/procedure P0; procedure P1

21、 begin begin repeat repeat flag0:=true; flag1:=true; while flag1 do if turn = 1 then while flag0 do if turn = 0 then begin begin flag0 :=false; flag1 :=false; while turn = 1 do nothing; while turn = 0 do nothing ; flag0:=true; flag1:=true; end; end; ; turn := 1; turn := 0; flag0:=false; flag1:=false

22、; forever foreverend; end;begin /* 主程序 */ flag0 := false; flag1 := false; turn := 1; parbegin P0; P1; parendend.flag0:=trueflag0:=falseturn01turn01flag0:=trueflag1falseP0進(jìn)入臨界區(qū)退出臨界區(qū)turn:=1flag0:=false其余部分true圖2.31 P0的執(zhí)行流程圖procedure P0; begin repeat flag0:=true; while flag1 do if turn = 1 then begin f

23、lag0 :=false; while turn = 1 do nothing; flag0:=true; end; turn := 1; flag0:=false; foreverend;互斥與同步解決方法之一：軟件方法- Peterson互斥算法Peterson互斥算法與Dekker互斥算法的設(shè)計(jì)思想類(lèi)似，但代碼更簡(jiǎn)潔，如圖2.32所示。算法中同樣用到兩個(gè)全局共享的狀態(tài)變量flag0和flag1，表示臨界區(qū)狀態(tài)及哪個(gè)進(jìn)程正在占用臨界區(qū)。全局共享變量turn（值為1或0）表示能進(jìn)入臨界區(qū)的進(jìn)程序號(hào)。互斥與同步解決方法之一：軟件方法- Peterson互斥算法分析P0的執(zhí)行：置flag0:=t

24、rue;阻止P1進(jìn)入臨界區(qū)執(zhí)行while flag1 false, P0進(jìn)入臨界區(qū)，執(zhí)行完成，置 flag0:=false; true, P0循環(huán)等待，只要P1退出，即可 進(jìn)入互斥與同步解決方法之二：硬件方法 采用軟件方法實(shí)現(xiàn)進(jìn)程互斥使用臨界資源是很困難的，它們通常能實(shí)現(xiàn)兩個(gè)進(jìn)程的互斥，很難控制多個(gè)進(jìn)程的互斥。算法設(shè)計(jì)需要非常小心，否則可能出現(xiàn)死鎖，或互斥失敗等嚴(yán)重問(wèn)題。軟件方法始終不能解決“忙等”現(xiàn)象，降低系統(tǒng)效率。硬件方法包括屏蔽中斷和專(zhuān)用機(jī)器指令?；コ馀c同步解決方法之二：硬件方法-屏蔽中斷由于進(jìn)程切換需要依賴(lài)中斷來(lái)實(shí)現(xiàn)，如果屏蔽中斷，則不會(huì)出現(xiàn)進(jìn)程切換。因此，為了實(shí)現(xiàn)對(duì)臨界資源的互斥使用

25、，可以在進(jìn)程進(jìn)入臨界區(qū)之前，屏蔽中斷,當(dāng)進(jìn)程退出臨界區(qū)時(shí)，打開(kāi)系統(tǒng)中斷。中斷被屏蔽以后，系統(tǒng)時(shí)鐘中斷也被屏蔽。處理機(jī)將不會(huì)被切換到其他進(jìn)程。于是，一旦屏蔽中斷，進(jìn)程就可以檢查和修改共享內(nèi)存區(qū)中的數(shù)據(jù)，而不必?fù)?dān)心其他進(jìn)程介入。其偽代碼如下： 互斥與同步解決方法之二：硬件方法-屏蔽中斷repeat ; ; ; forever.互斥與同步解決方法之二：硬件方法-屏蔽中斷這種方法約束條件太強(qiáng)，付出的代價(jià)太大因?yàn)橹袛啾黄帘我院?，系統(tǒng)將無(wú)法響應(yīng)任何外部請(qǐng)求，也不會(huì)響應(yīng)當(dāng)前執(zhí)行進(jìn)程的任何異常及系統(tǒng)故障，嚴(yán)重地降低了處理機(jī)性能。這種方法僅對(duì)單處理機(jī)系統(tǒng)有效，如果系統(tǒng)有兩個(gè)或多個(gè)共享內(nèi)存的處理機(jī)，屏蔽中斷僅僅對(duì)

26、執(zhí)行本指令的處理機(jī)有效，其它處理機(jī)仍將繼續(xù)運(yùn)行，并可以訪(fǎng)問(wèn)共享內(nèi)存空間。 互斥與同步解決方法之二：硬件方法-專(zhuān)用機(jī)器指令利用一些專(zhuān)用機(jī)器指令也能實(shí)現(xiàn)互斥，機(jī)器指令在一個(gè)指令周期內(nèi)執(zhí)行，不會(huì)受到其它指令的干擾，也不會(huì)被中斷。Test and Set指令就是較常用的一種機(jī)器指令，其定義如下： 互斥與同步解決方法之二：硬件方法- testset指令function testset ( var i:integer ) : boolean ; begin if i = 0 then begin i := 1; testset := true; end else testset :=false; gram mutualexclusion;const n=; /*進(jìn)程數(shù)*/var bolt:integer;procedure P(i:integer);begin repeatrepeat nothing until testset (bolt); ; bolt :=0; foreverend;begin /* 主程序*/ bolt :=0; parbegin P(1); P(2); P(n