互斥與同步的解決策略 當(dāng)前，利用軟件方法、硬件方法、信號(hào)量方法、管程方法、消息傳遞方法都可以有效地解決進(jìn)程間的互斥與同步，其中信號(hào)量的方法更具有優(yōu)勢(shì)（目前已經(jīng)通用）。

1. 軟件方法：

軟件方法是指由進(jìn)程自己，通過執(zhí)行相應(yīng)的程序指令，實(shí)現(xiàn)與別的進(jìn)程的同步與互斥，無須專門的程序設(shè)計(jì)語言或操作系統(tǒng)的支持。實(shí)踐證明，該方法很難正確控制進(jìn)程間的同步與互斥，而且可能會(huì)大大地增加系統(tǒng)的額外開銷。?

軟件解決方法有很多種，比較有代表性的軟件方法有荷蘭數(shù)學(xué)家Dekker提出的Dekker算法和科學(xué)家G.L.Peterson提出的Peterson算法。為了說明設(shè)計(jì)并發(fā)程序時(shí)可能出現(xiàn)的典型錯(cuò)誤，下面以Dekker算法為例，分析如何設(shè)計(jì)并改進(jìn)一個(gè)互斥算法的過程。

1.1 初步設(shè)想

suppose1：控制兩個(gè)進(jìn)程互斥進(jìn)入臨界區(qū)，可以讓兩個(gè)進(jìn)程輪流進(jìn)入臨界區(qū)。
suppose2：當(dāng)一個(gè)進(jìn)程正在臨界區(qū)執(zhí)行時(shí)，另一個(gè)進(jìn)程就不能進(jìn)入臨界區(qū)，而在臨界區(qū)外等待。

評(píng)價(jià)： 1.該方法可以保證互斥。【相互依賴對(duì)方賦予使用的權(quán)限】 2.會(huì)造成忙等現(xiàn)象，此時(shí)互斥的進(jìn)程并不是處于阻塞狀態(tài)，而是在不斷的循環(huán)檢測(cè)。 3.進(jìn)程嚴(yán)格交替進(jìn)入臨界區(qū)。如果進(jìn)程需要多次使用臨界區(qū)，那么使用臨界區(qū)頻率低的進(jìn)程嚴(yán)重制約著使用臨界區(qū)使用頻率高的進(jìn)程的執(zhí)行。【也就是說，如果不交替執(zhí)行一次，A進(jìn)程無法持續(xù)的推進(jìn)】 實(shí)例： suppose：P0需要每10分鐘使用一次臨界區(qū)，P1需要每1分鐘使用一次臨界區(qū)。
A. 假設(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)，等待。
B. 當(dāng)P0退出臨界區(qū)時(shí)，修改turn的值為1。P1循環(huán)檢測(cè)到turn = 1時(shí)，就可以進(jìn)入臨界區(qū)執(zhí)行，退出臨界區(qū)時(shí)，修改turn=0。
C. 根據(jù)假設(shè)，P1很快又需要進(jìn)入臨界區(qū)，但是P0卻只能在10分鐘之后，按照turn規(guī)定的順序，進(jìn)入臨界區(qū)執(zhí)行，退出時(shí)修改turn=1。
即P1必須在臨界區(qū)空閑的情況下，等待10分鐘，才能使用臨界區(qū)。這不符和互斥原則，降低了系統(tǒng)性能。

1.2 第一次改進(jìn)

可以為臨界區(qū)設(shè)置一個(gè)狀態(tài)標(biāo)志，標(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)程。其算法描述如圖所示:


分析： 1. 如果進(jìn)程在臨界區(qū)外失敗，其他進(jìn)程不會(huì)阻塞。
2.?問題1：“忙等” 3.?問題2：若進(jìn)程在臨界區(qū)內(nèi)失敗且相應(yīng)的flag為true，則其他進(jìn)程永久阻塞。 4. 問題3：不能保證進(jìn)程互斥進(jìn)入臨界區(qū)。試按以下順序執(zhí)行：

1.3 第二次改進(jìn)

互斥算法的第一次改進(jìn)不能實(shí)現(xiàn) “互斥” 。因?yàn)?#xff0c;進(jìn)程首先檢測(cè)臨界區(qū)狀態(tài)，若“被占用”，則“忙等”，否則就直接進(jìn)入臨界區(qū)。從而，可能出現(xiàn)同時(shí)進(jìn)入臨界區(qū)的現(xiàn)象。能否讓進(jìn)程預(yù)先表明“希望進(jìn)入臨界區(qū)的態(tài)度”，然后，再檢測(cè)臨界區(qū)狀態(tài)。第二次改進(jìn)。

分析： 1.?假設(shè)P0需要進(jìn)入臨界區(qū)，首先執(zhí)行flag[0]:=true，再執(zhí)行while flag[1]，若P1正在占用臨界區(qū)，則P0忙等；否則，P0進(jìn)入臨界區(qū)。 2.?但是，如果此時(shí)P1未占用臨界區(qū)，而與P0幾乎同時(shí)需要使用臨界區(qū)，如下圖示：

1.3?第三次改進(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)。算法如圖所示：

分析： P0、P1的“謙讓”可能使它們都不能進(jìn)入臨界區(qū)。這種現(xiàn)象不是死鎖，因?yàn)檫@種僵局不會(huì)是永久行為，某一時(shí)刻可能會(huì)自動(dòng)解除。但是，這種現(xiàn)象也是不希望出現(xiàn)的。

1.4?Dekker互斥算法?

該算法既允許進(jìn)程“謙讓地”申請(qǐng)進(jìn)入臨界區(qū)，又通過給定序號(hào)避免“過分謙讓”。偽代碼描述如下：

1.5?Peterson互斥算法

分析P0的執(zhí)行：
置flag[0]:=true;{阻止P1進(jìn)入臨界區(qū)}
執(zhí)行while flag[1]
?false, P0進(jìn)入臨界區(qū)，執(zhí)行完成，置
? ? ? ? flag[0]:=false;
?true, P0循環(huán)等待，只要P1退出，即可 ? ??
? ? ? ? ?進(jìn)入

2. 硬件方法：

為了解決軟件方法存在的不足，有人提出了硬件解決方法，通過屏蔽中斷或采用專門的機(jī)器指令控制同步與互斥。與軟件解決方法比較，這種方法減少了系統(tǒng)額外開銷，但由于需要太強(qiáng)的硬件約束條件，以及可能導(dǎo)致進(jìn)程饑餓與死鎖現(xiàn)象，一直沒有成為通用的解決方法。?
采用軟件方法實(shí)現(xiàn)進(jìn)程互斥使用臨界資源是很困難的，它們通常能實(shí)現(xiàn)兩個(gè)進(jìn)程的互斥，很難控制多個(gè)進(jìn)程的互斥。算法設(shè)計(jì)需要非常小心，否則可能出現(xiàn)死鎖，或互斥失敗等嚴(yán)重問題。軟件方法始終不能解決“忙等”現(xiàn)象，降低系統(tǒng)效率。硬件方法包括屏蔽中斷和專用機(jī)器指令。

2.1 屏蔽中斷

由于進(jìn)程切換需要依賴中斷來實(shí)現(xiàn)，如果屏蔽中斷，則不會(huì)出現(xiàn)進(jìn)程切換。
因此，為了實(shí)現(xiàn)對(duì)臨界資源的互斥使用，可以在進(jìn)程進(jìn)入臨界區(qū)之前，屏蔽中斷,當(dāng)進(jìn)程退出臨界區(qū)時(shí)，打開系統(tǒng)中斷。中斷被屏蔽以后，系統(tǒng)時(shí)鐘中斷也被屏蔽。處理機(jī)將不會(huì)被切換到其他進(jìn)程。于是，一旦屏蔽中斷，進(jìn)程就可以檢查和修改共享內(nèi)存區(qū)中的數(shù)據(jù)，而不必?fù)?dān)心其他進(jìn)程介入。其偽代碼如下： repeat
<屏蔽中斷>;
<臨界區(qū)>;
<打開中斷>;
<其余部分>
forever.
分析： 這種方法約束條件太強(qiáng)，付出的代價(jià)太大；因?yàn)橹袛啾黄帘我院?#xff0c;系統(tǒng)將無法響應(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ì)執(zhí)行本指令的處理機(jī)有效，其它處理機(jī)仍將繼續(xù)運(yùn)行，并可以訪問共享內(nèi)存空間。

2.2?專用機(jī)器指令

利用一些專用機(jī)器指令也能實(shí)現(xiàn)互斥，機(jī)器指令在一個(gè)指令周期內(nèi)執(zhí)行，不會(huì)受到其它指令的干擾，也不會(huì)被中斷。Test and Set指令就是較常用的一種機(jī)器指令，其定義如下：?
function testset ( var i:integer ) : boolean ;beginif i = 0 thenbegini := 1;testset := true;endelse testset :=false;end.program mutualexclusion; const n=…; /*進(jìn)程數(shù)*/ var bolt:integer; procedure P(i:integer); beginrepeat repeat {nothing} until testset (bolt);<臨界區(qū)>;bolt :=0;<其余部分>forever end; begin /* 主程序*/bolt :=0;parbeginP(1);P(2);…P(n)parend end.

2.3?exchange指令

procedure exchange ( var r :register; var m :memory ); var temp; begintemp := m;m := r;r := temp; end. program mutualexclusion; const n=…; /*進(jìn)程數(shù)*/ var bolt:integer; procedure P(i:integer); var key:integer; beginrepeatkey:=1;repeat exchange(key,bolt) until key=0;<臨界區(qū)>;exchange(key,bolt);<其余部分>foreverend; begin /* 主程序*/bolt :=0;parbeginP(1);P(2);…P(n)parend end.

2.4?機(jī)器指令優(yōu)點(diǎn)

非常簡(jiǎn)單，易于證明；同時(shí)適合于單處理機(jī)系統(tǒng)和共享內(nèi)存的多處理機(jī)系統(tǒng)中多個(gè)進(jìn)程的互斥；可以分別為臨界區(qū)設(shè)置屬于它自己的變量，以實(shí)現(xiàn)對(duì)多個(gè)臨界區(qū)的互斥訪問。
“忙等” 現(xiàn)象仍然存在。進(jìn)程都需要循環(huán)檢測(cè)，等待時(shí)機(jī)進(jìn)入臨界區(qū)。但是，由于采用了機(jī)器指令，這種“忙等”消耗的機(jī)器時(shí)間比軟件方法小，屬于“可接受的忙等”。可能出現(xiàn)饑餓現(xiàn)象。當(dāng)臨界區(qū)空閑時(shí)，執(zhí)行循環(huán)檢測(cè)的若干等待進(jìn)程能進(jìn)入臨界區(qū)的機(jī)率是相等的，有的進(jìn)程可能“運(yùn)氣”非常不好，很難有機(jī)會(huì)進(jìn)入臨界區(qū)，而饑餓。
還有可能導(dǎo)致死鎖。
例如，進(jìn)程P1的優(yōu)先級(jí)低于P2的優(yōu)先級(jí)，若P1通過執(zhí)行專用機(jī)器指令，進(jìn)入臨界區(qū)，且在臨界區(qū)內(nèi)被中斷，P2被調(diào)度執(zhí)行。若P2也需要進(jìn)入該臨界區(qū)，由于臨界區(qū)被P1占用，P2 “忙等” 。由于P1的優(yōu)先級(jí)低于P2，調(diào)度程序不可能強(qiáng)行剝奪P2的執(zhí)行而調(diào)度P1。這樣，P1將一直占用臨界區(qū)被中斷，P2一直“忙等”，如果沒有外力的作用，這種“僵持”狀態(tài)將一直保持下去，即系統(tǒng)出現(xiàn)死鎖。

3.信號(hào)量（semaphores）方法

軟件方法和硬件方法都存在“忙等”問題，浪費(fèi)了處理機(jī)的時(shí)間。信號(hào)量方法能實(shí)現(xiàn)進(jìn)程的互斥與同步，而不必“忙等”。(交通信號(hào)燈：紅燈停，綠燈行就是典型的信號(hào)量實(shí)例)

3.1 原理

兩個(gè)或多個(gè)進(jìn)程可以通過傳遞信號(hào)進(jìn)行合作，可以迫使進(jìn)程在某個(gè)位置暫時(shí)停止執(zhí)行（阻塞等待），直到他收到一個(gè)可以“向前推進(jìn)”的信號(hào)（被喚醒）。像影帝，將實(shí)現(xiàn)信號(hào)燈作用的變量稱為信號(hào)量，常定義為記錄型變量s，其中一個(gè)域?yàn)檎?#xff0c;另一個(gè)域?yàn)殛?duì)列，其元素為等待該信號(hào)量的阻塞進(jìn)程（FIFO）。

3.2 信號(hào)量定義及兩個(gè)原子操作

type semaphore = record conut:integer; queue:list of process end;
var s: semaphore; ======================== wait(s) 和 signal(s) ======================== wait(s) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? signal(s) s.count : = s.count - 1; ? ? ? ? ? ? ? ? ? ? ? ? ? s.count := s.count + 1; if s.count < 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if s.count <=0 then begin ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?then begin 進(jìn)程阻塞 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?喚醒隊(duì)首進(jìn)程 進(jìn)程進(jìn)入s.queue隊(duì)列； ? ? ? ? ? ? ? ? ? ? ? ? 將進(jìn)程從s.queue阻塞隊(duì)列中移除 end; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?end; 進(jìn)程進(jìn)入臨界區(qū)之前，首先執(zhí)行wait(s)原語，若s.count<0,則進(jìn)程調(diào)用阻塞原語，將自己阻塞，并插入到s.queue 隊(duì)列中進(jìn)行排隊(duì)。 注意，阻塞進(jìn)程不會(huì)占用處理機(jī)時(shí)間，不是“忙等”。直到某個(gè)從臨界區(qū)退出的進(jìn)程執(zhí)行signal(s)原語，喚醒它。 一旦其他某各進(jìn)程執(zhí)行了signal（s）原語中的s.count+1操作之后，發(fā)現(xiàn)s.count<=0，即阻塞隊(duì)列中還有被阻塞進(jìn)程，則調(diào)用喚醒原語，把s.queue中第一個(gè)進(jìn)程修改為就緒狀態(tài)，送就緒隊(duì)列，準(zhǔn)備執(zhí)行臨界區(qū)代碼。

3.3 利用信號(hào)量實(shí)現(xiàn)互斥的通用模式

count n=....; //進(jìn)程數(shù) var s:semaphore(:=1); //定義信號(hào)量s,s.count初始化為1 procedure P(i:integer) begin repeat wait(s);// <臨界區(qū)> signal(s); <其余部分>

forever

end;

begin ?//主程序

parbegin

P(1),P(2);......P(n)

parend

end

4.管程方法/*待研究*/

5.消息傳遞方法/*待研究*/

總結(jié)

以上是生活随笔為你收集整理的[OS复习]进程互斥与同步2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。