第二講 進(jìn)程管理(2)-同步及互斥

3.5進(jìn)程互斥進(jìn)程的并發(fā)執(zhí)行不僅僅是用戶程序的執(zhí)行開(kāi)始時(shí)間的隨機(jī)性和提高資源利用率的結(jié)果，也是資源有限性導(dǎo)致資源的競(jìng)爭(zhēng)與共享對(duì)進(jìn)程的執(zhí)行過(guò)程進(jìn)行制約所造成的。X；=X+1在用匯編語(yǔ)言書(shū)寫(xiě)時(shí)，就變成：

LOADA，X ADDIA，1 STOREA，X3.5進(jìn)程互斥兩種形式的制約關(guān)系3.5.1資源共享所引起的制約（間接制約）設(shè)有兩個(gè)計(jì)算進(jìn)程ＰA，ＰB共享內(nèi)存ＭS。其中ＭS分為三個(gè)領(lǐng)域，即系統(tǒng)區(qū)、進(jìn)程工作區(qū)和數(shù)據(jù)區(qū)。這里數(shù)據(jù)區(qū)被劃分大小相等的塊，每個(gè)塊中既可能放有數(shù)據(jù)，也有可能未放有數(shù)據(jù)。系統(tǒng)區(qū)主要是堆棧Ｓ，其中存放那些空數(shù)據(jù)塊的地址（如圖3.10）。圖3.10多進(jìn)程共享內(nèi)存棧區(qū)示例當(dāng)進(jìn)程ＰA或ＰB要求空數(shù)據(jù)塊時(shí)，從堆棧最頂部（top指針?biāo)傅奈恢茫┤〕鏊钄?shù)據(jù)塊。當(dāng)進(jìn)程ＰA或ＰB釋放數(shù)據(jù)塊時(shí)，則把所釋放數(shù)據(jù)塊的地址放入堆棧頂部。令getspace為取空數(shù)據(jù)塊過(guò)程，release(ad)為釋放數(shù)據(jù)塊過(guò)程。這里，ad為待釋放數(shù)據(jù)塊的地址。

getspace和release(ad)可進(jìn)一步描述為： getspace: begin local g g←stack［top］

top←top-1 end

release(ad): begin top←top+1 stack［top］←ad end

設(shè)時(shí)刻t0時(shí)，top=h0，則getspace和release(ad)可能按以下順序執(zhí)行：

t0：top←top+1

t1：g←stack［top］

t2：top←top-1

t3：stack［top］←ad

結(jié)果：調(diào)用getspace的進(jìn)程取到的是h0+1中的一個(gè)未定義值，而調(diào)用release(ad)的進(jìn)程把所釋放的空塊地址ad重復(fù)放入了h0中。怎樣保證上述執(zhí)行結(jié)果的正確性呢？臨界資源和臨界區(qū)：臨界資源：在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問(wèn)的資源，即僅當(dāng)一個(gè)進(jìn)程訪問(wèn)完并釋放該資源后，才允許另一個(gè)進(jìn)程訪問(wèn)的資源，稱為臨界資源或獨(dú)占資源。

臨界區(qū)：把不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界部分（criticalsection）或臨界區(qū)（criticalregion）。臨界區(qū)也可以被稱為訪問(wèn)臨界資源的那段程序。一般來(lái)說(shuō)，可以把那些不允許交叉執(zhí)行的臨界區(qū)按不同的公用數(shù)據(jù)劃分為不同的集合。上例中，以公用數(shù)據(jù)棧Ｓ劃分的臨界區(qū)集合是{getspace,release}。把這些集合稱為類（class）。顯然，對(duì)類給定一個(gè)唯一的標(biāo)識(shí)名，系統(tǒng)就會(huì)容易地區(qū)分它們。在程序的描述中，可用下列標(biāo)準(zhǔn)形式來(lái)描述臨界區(qū)：

when〈類名〉do〈臨界區(qū)〉od設(shè)類{getspace，release}的類名為sp，則getspace和release(ad)可重新描述為：

getspace: whenspdogetspce←stack［top］

top←top-1od release(ad):whenspdotop←top+1 stack［top］←adod間接制約：把這種由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的對(duì)并發(fā)進(jìn)程執(zhí)行速度的間接制約，簡(jiǎn)稱間接制約。

這里，“間接”二字主要是指各并發(fā)進(jìn)程的速度受公有臨界資源制約，而不是進(jìn)程間直接制約的意思。這里，受間接制約的類中各程序段在執(zhí)行順序上是任意的。顯然，對(duì)于每一類，系統(tǒng)應(yīng)有相應(yīng)的分配和釋放相應(yīng)公有資源的管理辦法，以制約并發(fā)進(jìn)程。這就是互斥。

進(jìn)程互斥的定義：一組并發(fā)進(jìn)程中的一個(gè)或多個(gè)程序段，因共享某一公有資源而導(dǎo)致它們必須以一個(gè)不允許交叉執(zhí)行的單位執(zhí)行。也就是說(shuō)，不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)稱為互斥。一組并發(fā)進(jìn)程互斥執(zhí)行時(shí)必須滿足如下準(zhǔn)則：(1)空閑讓進(jìn)：當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以便有效地利用臨界資源。(2)忙則等待：當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪問(wèn)，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問(wèn)。(3)讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”。——不忙碌等待。(4)有限等待：對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證在有限的時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死鎖”狀態(tài)?！凰赖取２换ハ嘧枞?。3.5.2互斥的加鎖實(shí)現(xiàn)如何解決互斥問(wèn)題，實(shí)現(xiàn)并發(fā)進(jìn)程的互斥？一種可能的辦法是對(duì)臨界區(qū)加鎖以實(shí)現(xiàn)互斥。并發(fā)進(jìn)程在申請(qǐng)進(jìn)入臨界區(qū)時(shí)，首先測(cè)試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進(jìn)程要等到該臨界區(qū)開(kāi)鎖之后才有可能獲得臨界區(qū)。設(shè)臨界區(qū)的類名為Ｓ。key［Ｓ］表示該鎖定位屬于類名為Ｓ的臨界區(qū)。加鎖后的臨界區(qū)程序描述如下：

lock(key［Ｓ］) 〈臨界區(qū)〉 unlock(key［Ｓ］)其中key［Ｓ］=1時(shí)表示類名為Ｓ的臨界區(qū)可用，key［Ｓ］=0時(shí)表示類名為Ｓ的臨界區(qū)不可用。則，

unlock(key［Ｓ］)只用一條語(yǔ)句即可實(shí)現(xiàn)。即：

key［Ｓ］←1

lock(key［Ｓ］)必須滿足key［Ｓ］=0時(shí)，不允許任何進(jìn)程進(jìn)入臨界區(qū)，而key［Ｓ］=1時(shí)僅允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)的準(zhǔn)則，因而實(shí)現(xiàn)起來(lái)較為困難。一種簡(jiǎn)便的實(shí)現(xiàn)方法是：

lock(x)

begin

localv repeat v←x until

v=1 x←0 end

不能保證并發(fā)進(jìn)程互斥執(zhí)行所要求的互斥訪問(wèn)原則。同時(shí)有幾個(gè)進(jìn)程調(diào)用lock(key［Ｓ］)時(shí)，在x←0語(yǔ)句執(zhí)行之前，可能已有兩個(gè)以上的多個(gè)進(jìn)程由于key［Ｓ］=1而進(jìn)入臨界區(qū)。3.5.3信號(hào)量和Ｐ，Ｖ原語(yǔ)1.信號(hào)量（semaphore）加鎖機(jī)制：每個(gè)進(jìn)程在申請(qǐng)進(jìn)入臨界區(qū)時(shí)都得對(duì)鎖定位進(jìn)行測(cè)試，這種開(kāi)銷是很大的。另外，使用加鎖法實(shí)現(xiàn)進(jìn)程間互斥時(shí)，還將導(dǎo)致在某些情況下出現(xiàn)不公平現(xiàn)象。3.5.3信號(hào)量和Ｐ，Ｖ原語(yǔ)信號(hào)量（semaphore）試考慮以下進(jìn)程PA和PB反復(fù)使用臨界區(qū)的情況：

PA A：lock(key［Ｓ］)

〈Ｓ〉

unlock(key［Ｓ］)

GotoAPB B：lock(key［Ｓ］)

＜Ｓ＞

unlock(key［Ｓ］)

GotoB

設(shè)進(jìn)程ＰA已通過(guò)lock(key［Ｓ］)過(guò)程而進(jìn)入臨界區(qū)。顯然，在進(jìn)程PA執(zhí)行unlock(key［Ｓ］)過(guò)程之前，key［Ｓ］=0且進(jìn)程PB沒(méi)有進(jìn)入臨界區(qū)的機(jī)會(huì)。然而，當(dāng)進(jìn)程PA執(zhí)行完unlock(key［Ｓ］)過(guò)程之后，由于緊接著是一轉(zhuǎn)向語(yǔ)句，進(jìn)程PA將又立即去執(zhí)行l(wèi)ock(key［Ｓ］)過(guò)程。此時(shí)，由于unlock(key［Ｓ］)過(guò)程已將key［Ｓ］的值置為1，也就是開(kāi)鎖狀態(tài)，從而進(jìn)程PA又可進(jìn)入臨界區(qū)Ｓ。只有在進(jìn)程PA執(zhí)行完unlock(key［Ｓ］)過(guò)程之后、執(zhí)行GotoA語(yǔ)句之前的瞬間發(fā)生進(jìn)程調(diào)度，使進(jìn)程PA把處理機(jī)轉(zhuǎn)讓給進(jìn)程PB，進(jìn)程PB才有可能得到執(zhí)行。然而遺憾的是，這種可能性是非常小的。因此，進(jìn)程PB將處于永久饑餓狀態(tài)（starvation）。原因：一個(gè)進(jìn)程能否進(jìn)入臨界區(qū)是依靠進(jìn)程自己調(diào)用lock過(guò)程去測(cè)試相應(yīng)的鎖定位。每個(gè)進(jìn)程能否進(jìn)入臨界區(qū)是依靠自己的測(cè)試判斷。這樣沒(méi)有獲得執(zhí)行機(jī)會(huì)的進(jìn)程當(dāng)然無(wú)法判斷，從而出現(xiàn)不公平現(xiàn)象。獲得了測(cè)試機(jī)會(huì)的進(jìn)程又因需要測(cè)試而損失一定的CPU時(shí)間。

方法：圖書(shū)管理員這個(gè)管理員就是信號(hào)量。信號(hào)量管理相應(yīng)臨界區(qū)的公有資源，它代表可用資源實(shí)體。信號(hào)量：信號(hào)量的概念和下面所述的Ｐ、Ｖ原語(yǔ)是荷蘭科學(xué)家E.W.Dijkstra提出來(lái)的。

在操作系統(tǒng)中，信號(hào)量sem是一整數(shù)。在sem大于等于零時(shí)代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，但sem小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。顯然，用于互斥的信號(hào)量sem的初值應(yīng)該大于零，而建立一個(gè)信號(hào)量必須經(jīng)過(guò)說(shuō)明（1）所建信號(hào)量所代表的意義（2）賦初值（3）建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以便指向那些等待使用該臨界區(qū)的進(jìn)程。2.Ｐ，Ｖ原語(yǔ)信號(hào)量的數(shù)值僅能由Ｐ，Ｖ原語(yǔ)操作改變。采用Ｐ，Ｖ原語(yǔ)，可以把類名為Ｓ的臨界區(qū)描述為

WhenＳ

do

Ｐ(sem)臨界區(qū)Ｖ(sem)

od

2.Ｐ，Ｖ原語(yǔ)

sem是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號(hào)量。一次Ｐ原語(yǔ)操作使得信號(hào)量sem減1，而一次Ｖ原語(yǔ)操作將使得信號(hào)量sem加1。強(qiáng)調(diào)：當(dāng)某個(gè)進(jìn)程正在臨界區(qū)內(nèi)執(zhí)行時(shí)，其他進(jìn)程如果執(zhí)行了Ｐ原語(yǔ)操作，則該進(jìn)程并不像調(diào)用lock時(shí)那樣因進(jìn)不了臨界區(qū)而返回到lock的起點(diǎn)，等以后重新執(zhí)行測(cè)試，而是在等待隊(duì)列中等待有其他進(jìn)程做Ｖ原語(yǔ)操作釋放資源后，進(jìn)入臨界區(qū)，這時(shí)，Ｐ原語(yǔ)的執(zhí)行才算真正結(jié)束。另外，當(dāng)有好幾個(gè)進(jìn)程執(zhí)行Ｐ原語(yǔ)未通過(guò)而進(jìn)入等待狀態(tài)之后，如有某進(jìn)程作了Ｖ原語(yǔ)操作，則等待進(jìn)程中的一個(gè)可以進(jìn)入臨界區(qū)，但其他進(jìn)程必須等待。Ｐ原語(yǔ)操作的主要?jiǎng)幼魇牵?1)sem減1；(2)若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；(3)若sem減1后小于零，則該進(jìn)程被阻塞后與該信號(hào)相對(duì)應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。Ｐ原語(yǔ)操作的功能框圖如圖3.11。Ｖ原語(yǔ)的操作主要?jiǎng)幼魇牵?1)sem加1；(2)若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3)若相加結(jié)果小于或等于零，則從該信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。Ｖ原語(yǔ)操作的功能框圖如圖3.12。圖3.11Ｐ原語(yǔ)操作功能 圖3.12Ｖ原語(yǔ)操作功能

需要一個(gè)用于代表臨界資源數(shù)目的整型變量value；還要一個(gè)在該資源上阻塞的隊(duì)列（鏈表）指針L。故信號(hào)量應(yīng)采用記錄型（C語(yǔ)言中為結(jié)構(gòu)型）的結(jié)構(gòu)：

structsemaphore{intvalue；

structsemphore*L；

}；信號(hào)量除初始化外，只能通過(guò)兩個(gè)原子操作(稱為原語(yǔ))wait(S)和signal(S)來(lái)訪問(wèn)。它們以前被稱為P、V操作。下頁(yè)介紹wait和signal操作。圖3.11Ｐ原語(yǔ)操作功能 圖3.12Ｖ原語(yǔ)操作功能wait和signal操作可用C/C++語(yǔ)言描述如下：voidwait(semaphoreS){S.value=S.value–1;if(S.value<0)block(S.L);

/*讓權(quán)等待*/}voidsignal(semaphoreS){S.value=S.value+1;if(S.value<=0)wakeup(S.L);/*喚醒第一個(gè)等待的進(jìn)程*/}S.value的初值表示系統(tǒng)中某類資源的數(shù)目。wait和signal操作的物理意義：對(duì)信號(hào)量S的每次wait操作，意味著進(jìn)程請(qǐng)求一個(gè)該類臨界資源，因此描述為S.value=S.value-1；當(dāng)S.value<0時(shí)，表示該類資源已分配完，因此進(jìn)程應(yīng)調(diào)用block原語(yǔ)進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號(hào)量鏈表S.L(阻塞隊(duì)列)中?？梢?jiàn)該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。類似地，可以解釋signal操作……S.value的初值表示系統(tǒng)中某類資源的數(shù)目?！Y源信號(hào)量。S.value的初值為1，表示只允許一個(gè)進(jìn)程訪問(wèn)，此時(shí)信號(hào)量轉(zhuǎn)化為互斥信號(hào)量。關(guān)于Ｐ，Ｖ原語(yǔ)的實(shí)現(xiàn)，有許多方法。這里介紹一種使用加鎖法的軟件實(shí)現(xiàn)方法，實(shí)現(xiàn)過(guò)程描述如下： Ｐ（sem）：

begin lock(lockbit)；封鎖中斷

val［sem］=val［sem］-1 ifval［sem］<0

保護(hù)當(dāng)前進(jìn)程CPU現(xiàn)場(chǎng) 當(dāng)前進(jìn)程狀態(tài)置為″等待″

將當(dāng)前進(jìn)程插入信號(hào)sem等待隊(duì)列 轉(zhuǎn)進(jìn)程調(diào)度

fi unlock(lockbit)；開(kāi)放中斷

endＶ（sem）：

begin lock(lockbit)；封鎖中斷

val［sem］=val［sem］+1 ifval［sem］≤0 localk

從sem等待隊(duì)列中選取一等待進(jìn)程，將其指針置入k中 將k插入就緒隊(duì)列 進(jìn)程狀態(tài)置“就緒”

fi unlock(lockbit)；開(kāi)放中斷end3.5.4用Ｐ，Ｖ原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥利用Ｐ，Ｖ原語(yǔ)和信號(hào)量，可以方便地解決并發(fā)進(jìn)程的互斥問(wèn)題，而且不會(huì)產(chǎn)生使用加鎖法解決互斥問(wèn)題時(shí)所出現(xiàn)的問(wèn)題。3.5.4用Ｐ，Ｖ原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥設(shè)信號(hào)量sem是用于互斥的信號(hào)量，且其初值為1表示沒(méi)有并發(fā)進(jìn)程使用該臨界區(qū)。顯然，由上面幾節(jié)的討論可知，只要把臨界區(qū)置于Ｐ(sem)和Ｖ(sem)之間，即可實(shí)現(xiàn)進(jìn)程間的互斥。當(dāng)一個(gè)進(jìn)程想要進(jìn)入臨界區(qū)時(shí)，它必須先執(zhí)行Ｐ原語(yǔ)操作以將信號(hào)量sem減1。在一個(gè)進(jìn)程完成對(duì)臨界區(qū)的操作之后，它必須執(zhí)行Ｖ原語(yǔ)操作以釋放它所占用的臨界區(qū)。由于信號(hào)量初始值為1，所以，任一進(jìn)程在執(zhí)行Ｐ原語(yǔ)操作之后將sem的值變?yōu)?，表示該進(jìn)程可以進(jìn)入臨界區(qū)。在該進(jìn)程未執(zhí)行Ｖ原語(yǔ)操作之前如有另一進(jìn)程想進(jìn)入臨界區(qū)的話，它也應(yīng)先執(zhí)行Ｐ原語(yǔ)操作，從而使sem的值變?yōu)?1，因此，第二個(gè)進(jìn)程將被阻塞。直到第一個(gè)進(jìn)程執(zhí)行Ｖ原語(yǔ)操作之后，sem的值變?yōu)?，從而可喚醒第二個(gè)進(jìn)程進(jìn)入就緒隊(duì)列，經(jīng)調(diào)度后再進(jìn)入臨界區(qū)。在第二個(gè)進(jìn)程執(zhí)行完Ｖ原語(yǔ)操作之后，如果沒(méi)有其他進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)的話，則sem又恢復(fù)到初始值。用信號(hào)量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述如下：1)設(shè)sem為互斥信號(hào)量，其取值范圍為(1,0,-1)。其中sem=1表示進(jìn)程PA和PB都未進(jìn)入類名為Ｓ的臨界區(qū)，sem=0表示進(jìn)程PA或PB已進(jìn)入類名為Ｓ的臨界區(qū)，sem=-1表示進(jìn)程PA和PB中，一個(gè)進(jìn)程已進(jìn)入臨界區(qū)，而另一個(gè)進(jìn)程等待進(jìn)入臨界區(qū)。2)描述：

PA： Ｐ(sem) 〈Ｓ〉

Ｖ(sem)： ： ：

PB： Ｐ(sem) 〈Ｓ〉

Ｖ(sem)∷

： ：3.6進(jìn)程同步3.6.1同步的概念除了對(duì)公有資源的競(jìng)爭(zhēng)而引起的間接制約之外，并發(fā)進(jìn)程之間是否還存在著其他制約關(guān)系影響執(zhí)行速度呢？來(lái)看下面的例子。3.6進(jìn)程同步例：計(jì)算進(jìn)程和打印進(jìn)程共同使用同一緩沖區(qū)Buf。計(jì)算進(jìn)程反復(fù)地把每次計(jì)算結(jié)果放入Buf中，而打印進(jìn)程則把計(jì)算進(jìn)程每次放入Buf中的數(shù)據(jù)通過(guò)打印機(jī)打印輸出。如果不采取任何制約措施，這兩個(gè)進(jìn)程的執(zhí)行起始時(shí)間和執(zhí)行速度都是彼此獨(dú)立的，其相應(yīng)的控制段可以描述為：PC ：

: A: localBuff Repeat Buff←Buf Until Buff=空 計(jì)算 得到計(jì)算結(jié)果

Buf←計(jì)算結(jié)果

Goto APP: ：

: B: localPri Repeat Pri←Buf Until Pri≠空 打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù)

Goto BPC和PP的執(zhí)行互相制約。PC的輸出結(jié)果是PP的執(zhí)行條件，反過(guò)來(lái)，PP的執(zhí)行結(jié)果也是PC的執(zhí)行條件。CPU時(shí)間的浪費(fèi)

一組在異步環(huán)境下的并發(fā)進(jìn)程，。各自的執(zhí)行結(jié)果互為對(duì)方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過(guò)程稱為并發(fā)進(jìn)程間的直接制約。

這與上節(jié)中講述的進(jìn)程互斥是不同的，進(jìn)程互斥時(shí)它們的執(zhí)行順序可以是任意的。這里異步環(huán)境主要指各并發(fā)進(jìn)程的執(zhí)行起始時(shí)間的隨機(jī)性和執(zhí)行速度的獨(dú)立性。

一種最為簡(jiǎn)單和直觀的方法是直接制約的進(jìn)程互相給對(duì)方進(jìn)程發(fā)送執(zhí)行條件已經(jīng)具備的信號(hào)。這樣，被制約進(jìn)程即可省去對(duì)執(zhí)行條件的測(cè)試，只要收到了制約進(jìn)程發(fā)來(lái)的信號(hào)便開(kāi)始執(zhí)行，而在未收到制約進(jìn)程發(fā)來(lái)的信號(hào)時(shí)便進(jìn)入等待狀態(tài)。把異步環(huán)境下的一組并發(fā)進(jìn)程，因直接制約而互相發(fā)送消息而進(jìn)行互相合作、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過(guò)程稱為進(jìn)程間的同步。具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程，合作進(jìn)程間互相發(fā)送的信號(hào)稱為消息或事件。

如果對(duì)一個(gè)消息或事件賦以唯一的消息名，則可用過(guò)程

wait(消息名）表示進(jìn)程等待合作進(jìn)程發(fā)來(lái)的消息，而用過(guò)程

signal（消息名）表示向合作進(jìn)程發(fā)送消息。利用過(guò)程wait和signal，可以簡(jiǎn)單地描述上面例子中的計(jì)算進(jìn)程PC和打印進(jìn)程PP的同步關(guān)系如下：(1)設(shè)消息名Bufempty表示Buf空，消息名Buffull表示Buf中裝滿了數(shù)據(jù)。(2)初始化Bufempty=true，Buffull=false。(3)描述：

PC

：

A: wait(Bufempty)

計(jì)算

Buf←計(jì)算結(jié)果

Bufempty←false signal(Buffull) Goto A PP ：

B: wait(Buffull)

打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù)

Buffull←false signal(Bufempty) Goto B過(guò)程wait的功能是等待到合作進(jìn)程發(fā)來(lái)的消息,消息值為true,進(jìn)程繼續(xù)執(zhí)行;而signal的功能則是向合作進(jìn)程發(fā)送合作進(jìn)程所需要的消息名，并將其值置為true。3.6.2私用信號(hào)量使用信號(hào)量的方法也可實(shí)現(xiàn)進(jìn)程間的同步。

可以把各進(jìn)程之間發(fā)送的消息作為信號(hào)量看待。與進(jìn)程互斥時(shí)不同的是，這里的信號(hào)量只與制約進(jìn)程及被制約進(jìn)程有關(guān)而不是與整組并發(fā)進(jìn)程有關(guān)。因此，稱該信號(hào)量為私用信號(hào)量。（PrivateSemaphvre）。

一個(gè)進(jìn)程Pi的私用信號(hào)量Semi是從制約進(jìn)程發(fā)送來(lái)的進(jìn)程Pi的執(zhí)行條件所需要的消息。與私用信號(hào)量相對(duì)應(yīng)，稱互斥時(shí)使用的信號(hào)量為公用信號(hào)量。3.6.3用Ｐ，Ｖ原語(yǔ)操作實(shí)現(xiàn)同步有了私用信號(hào)量的概念，可以使用Ｐ，Ｖ原語(yǔ)操作實(shí)現(xiàn)進(jìn)程間的同步。利用Ｐ，Ｖ原語(yǔ)實(shí)現(xiàn)進(jìn)程同步的方法與利用wait和signal過(guò)程時(shí)相同，也是分為三步。首先為各并發(fā)進(jìn)程設(shè)置私用信號(hào)量，然后為私用信號(hào)量賦初值，最后利用Ｐ，Ｖ原語(yǔ)和私用信號(hào)量規(guī)定各進(jìn)程的執(zhí)行順序。圖3.13緩沖區(qū)隊(duì)列例：設(shè)進(jìn)程PA和PB通過(guò)緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)（如圖3.13）。PA為發(fā)送進(jìn)程，PB為接收進(jìn)程。PA發(fā)送數(shù)據(jù)時(shí)調(diào)用發(fā)送過(guò)程deposit(data)，PB接收數(shù)據(jù)時(shí)調(diào)用過(guò)程remove(data)。且數(shù)據(jù)的發(fā)送和接收過(guò)程滿足如下條件：(1)在PA至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長(zhǎng)等于緩沖區(qū)長(zhǎng)度）；（2)PA往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí)，至少有一個(gè)緩沖區(qū)是空的；（3)由PA發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出（FIFO）方式排列。描述發(fā)送過(guò)程deposit(data)和接收過(guò)程remove(data)。解：按以下三步描述過(guò)程deposit(data)和remove(data)：（1)設(shè)Bufempty為進(jìn)程PA的私用信號(hào)量，Buffull為進(jìn)程PB的私用信號(hào)量；（2)令Bufempty的初始值為n（n為緩沖隊(duì)列的緩沖區(qū)個(gè)數(shù)），Buffull的初始值為0；（3)描述：PA:deposit(data): beginlocalx P(Bufempty)； 按FIFO方式選擇一個(gè)空緩沖區(qū)Buf(x)；

Buf(x)←data Buf(x)置滿標(biāo)記 Ｖ（Buffull）

endPB:remove(data): Beginlocalx

Ｐ（Buffull）； 按FIFO方式選擇一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)Buf(x) data←Buf(x) Buf(x)置空標(biāo)記 Ｖ（Bufempty）

end這里，局部變