第6章進(jìn)程同步及實(shí)例

舉例銀行的聯(lián)網(wǎng)儲(chǔ)蓄業(yè)務(wù)允許儲(chǔ)戶同時(shí)用儲(chǔ)蓄卡和存折對(duì)同一賬戶進(jìn)行存取款操作，如果某儲(chǔ)戶同時(shí)在ATM機(jī)辦理兩筆取款業(yè)務(wù)（假設(shè)分別為1000元和2000元）。從系統(tǒng)角度看，有兩個(gè)進(jìn)程將同時(shí)對(duì)儲(chǔ)戶余額等數(shù)據(jù)進(jìn)行修改。如果兩個(gè)進(jìn)程同時(shí)讀出原余額（假設(shè)為5000元），兩個(gè)進(jìn)程分別將最新余額修改為4000元和3000元。用戶取錢后，賬戶余額對(duì)不對(duì)？

通過本章學(xué)習(xí)，思考下列問題：如何理解同步？加鎖的軟件方法能不能很好地解決進(jìn)程互斥問題？如何利用信號(hào)量解決進(jìn)程互斥問題？6.0背景1、多道程序系統(tǒng)的特點(diǎn)并發(fā)進(jìn)程、共享資源、相互制約由于資源被進(jìn)程共享，而且調(diào)度程序可以任意地交織在多進(jìn)程之間執(zhí)行，可能導(dǎo)致以下錯(cuò)誤：存儲(chǔ)值被破壞，例如數(shù)據(jù)競(jìng)爭(zhēng)協(xié)議被破壞（例如，A出現(xiàn)在B之前）所以，操作系統(tǒng)必須能夠保護(hù)共享資源，這就需要進(jìn)程之間進(jìn)行協(xié)調(diào)即同步示例：進(jìn)程Pa、Pb共享一臺(tái)打印機(jī)申請(qǐng)、使用、釋放：獨(dú)占打印機(jī)定義：多道程序系統(tǒng)是操作系統(tǒng)的類型之一，其含義指為了提高CPU利用率，在內(nèi)存中同時(shí)保存多個(gè)作業(yè)，其特點(diǎn)是多道程序同時(shí)在內(nèi)存中，宏觀上并行運(yùn)行、微觀上串行運(yùn)行。2、數(shù)據(jù)競(jìng)爭(zhēng)（DataRace）的示例Staticintcn=0;T1.run(){Inty=cn;cn=y+1;}T2.run(){Inty=cn;cn=y+1;}第一種執(zhí)行情況：T1執(zhí)行完第1句后(y=0)，被T2搶占，T2執(zhí)行完畢(cn=1)，之后，T1接著被搶占處從第2條語句開始執(zhí)行，結(jié)果cn=1。第二種執(zhí)行情況：T1從開始執(zhí)行一直到執(zhí)行完備都沒有被中斷，結(jié)果cn=1。之后T2開始執(zhí)行并執(zhí)行完畢,結(jié)果cn=2。并發(fā)進(jìn)程的執(zhí)行順序具有隨機(jī)性，如下是兩種可能的執(zhí)行順序：發(fā)生了什么情況？同樣執(zhí)行兩個(gè)進(jìn)程，但結(jié)果卻不一樣。在第一個(gè)示例中：t1在讀完counter值之后，被保存之前，t1被搶占了。即沒有能夠保存t1執(zhí)行過程的完整性。從而導(dǎo)致，兩次執(zhí)行得到不同的結(jié)果。競(jìng)爭(zhēng)條件(racecondition)：多個(gè)進(jìn)程并發(fā)訪問和操作同一數(shù)據(jù)且操作結(jié)果與訪問發(fā)生的特定順序有關(guān)，稱這種情況為競(jìng)爭(zhēng)條件。為了防止上述競(jìng)爭(zhēng)條件，需要確保一段時(shí)間內(nèi)只有一個(gè)進(jìn)程能操作變量counter。為了實(shí)現(xiàn)這種保證，要求進(jìn)程之間進(jìn)程同步。3、基本概念異步環(huán)境：指各并發(fā)進(jìn)程的起始執(zhí)行時(shí)間的隨機(jī)性和執(zhí)行速度的獨(dú)立性。進(jìn)程同步：在異步環(huán)境下一組并發(fā)進(jìn)程，如果想得到正確的結(jié)果就需要它們互相發(fā)送消息進(jìn)行相互協(xié)作、相互等待，從而使得它們各自按一定的速度前進(jìn)。這個(gè)相互協(xié)作過程稱為進(jìn)程同步。例如公交車司機(jī)與售票員的關(guān)系、計(jì)算進(jìn)程與打印進(jìn)程的關(guān)系合作進(jìn)程：具有同步關(guān)系的一組進(jìn)程稱為合作進(jìn)程。采取同步措施structMutexlock;Mutex_Init(&lock);Mutex_lock(&lock);Mutex_ulock(&lock);第6章

進(jìn)程同步6.1進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系間接相互制約關(guān)系。進(jìn)程間要通過某種中介發(fā)生聯(lián)系，是無意識(shí)安排的，可發(fā)生在相交進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間(2)直接相互制約關(guān)系。進(jìn)程間的相互聯(lián)系是有意識(shí)的安排的，直接作用只發(fā)生在相交進(jìn)程間第6章

進(jìn)程同步6.1進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系進(jìn)程的同步：synchronism（直接作用）

指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。具體說，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)。第6章

進(jìn)程同步6.1進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系進(jìn)程的互斥（間接作用）mutualexclusion

由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競(jìng)爭(zhēng)使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥2.臨界資源(CriticalResouce)臨界資源（Criticalresource）：系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，這樣的資源稱為臨界資源或互斥資源或共享變量。臨界區(qū)（Criticalregion）：把不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界區(qū)或臨界部分。臨界區(qū)就是訪問公用數(shù)據(jù)的那段程序。例如堆棧操作中的get(top)和rel(blk)程序。2.臨界資源(CriticalResouce)

生產(chǎn)者-消費(fèi)者(producer-consumer)問題是一個(gè)著名的進(jìn)程同步問題。它描述的是：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中；消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi)。盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，即不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。

我們可利用一個(gè)數(shù)組來表示上述的具有n個(gè)(0，1，…，n-1)緩沖區(qū)的緩沖池。用輸入指針in來指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)產(chǎn)品后，輸入指針加1；用一個(gè)輸出指針out來指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后，輸出指針加1。由于這里的緩沖池是組織成循環(huán)緩沖的，故應(yīng)把輸入指針加1表示成in∶=(in+1)modn；輸出指針加1表示成out∶=(out+1)modn。當(dāng)(in+1)modn=out時(shí)表示緩沖池滿；而in=out則表示緩沖池空。此外，還引入了一個(gè)整型變量counter,其初始值為0。每當(dāng)生產(chǎn)者進(jìn)程向緩沖池中投放一個(gè)產(chǎn)品后，使counter加1；反之，每當(dāng)消費(fèi)者進(jìn)程從中取走一個(gè)產(chǎn)品時(shí)，使counter減1。生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量：Varn,integer;typeitem=…;varbuffer:array［0,1,…,n-1］ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;

指針in和out初始化為1。在生產(chǎn)者和消費(fèi)者進(jìn)程的描述中，no-op是一條空操作指令，whileconditiondono-op語句表示重復(fù)的測(cè)試條件(condication)，重復(fù)測(cè)試應(yīng)進(jìn)行到該條件變?yōu)閒alse(假)，即到該條件不成立時(shí)為止。在生產(chǎn)者進(jìn)程中使用一局部變量nextp，用于暫時(shí)存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費(fèi)者進(jìn)程中，則使用一個(gè)局部變量nextc,用于存放每次要消費(fèi)的產(chǎn)品。producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer［in］∶=nextp;in∶=in+1modn;counter∶=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc∶=buffer［out］;out∶=(out+1)modn;counter∶=counter-1;consumertheiteminnextc;untilfalse;

雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)，就會(huì)出現(xiàn)差錯(cuò)，問題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對(duì)它做加1操作，消費(fèi)者對(duì)它做減1操作，這兩個(gè)操作在用機(jī)器語言實(shí)現(xiàn)時(shí)，?？捎孟旅娴男问矫枋觯簉egister1∶=counter;register2∶=counter;register1∶=register1+1;register2∶=register2-1;counter∶=register1;counter∶=register2;

假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語言語句，然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語句，則最后共享變量counter的值仍為5；反之，如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語句，然后再讓生產(chǎn)者進(jìn)程執(zhí)行左列的三條語句，counter值也還是5，但是，如果按下述順序執(zhí)行：

register1∶=counter;(register1=5)register1∶=register1+1;(register1=6)register2∶=counter;(register2=5)register2∶=register2-1;(register2=4)counter∶=register1;(counter=6)counter∶=register2;(counter=4)3.

臨界區(qū)(criticalsection)臨界資源（Criticalresource）：系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，這樣的資源稱為臨界資源或互斥資源或共享變量。臨界區(qū)（Criticalregion）：把不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界區(qū)或臨界部分。臨界區(qū)就是訪問公用數(shù)據(jù)的那段程序。例如堆棧操作中的get(top)和rel(blk)程序。3.臨界區(qū)(criticalsection)可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下：repeat

criticalsection;remaindersection;untilfalse;entrysectionexitsection4.同步機(jī)制應(yīng)遵循的規(guī)則空閑讓進(jìn)。(2)忙則等待。(3)有限等待。(4)讓權(quán)等待。6.2信號(hào)量機(jī)制1.整型信號(hào)量最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量，除初始化外，僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。這兩個(gè)操作一直被分別稱為P、V操作。wait和signal操作可描述為：

wait(S):whileS≤0dono-opS∶=S-1;signal(S):S∶=S+1;

2.記錄型信號(hào)量在整型信號(hào)量機(jī)制中的wait操作，只要是信號(hào)量S≤0，就會(huì)不斷地測(cè)試。因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則，而是使進(jìn)程處于“忙等”的狀態(tài)。記錄型信號(hào)量機(jī)制，則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了“讓權(quán)等待”的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表L，用于鏈接上述的所有等待進(jìn)程。記錄型信號(hào)量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為：typesemaphore=recordvalue:integer;L:listofprocess;end相應(yīng)地，wait(S)和signal(S)操作可描述為：procedurewait(S)varS:semaphore;beginS.value∶=S.value-1;ifS.value＜0thenblock(S,L)endproceduresignal(S)varS:semaphore;beginS.value∶=S.value+1;ifS.value≤0thenwakeup(S,L);end

在記錄型信號(hào)量機(jī)制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目，因而又稱為資源信號(hào)量，對(duì)它的每次wait操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源，因此描述為S.value∶=S.value-1；當(dāng)S.value＜0時(shí)，表示該類資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號(hào)量鏈表S.L中?？梢姡摍C(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。此時(shí)S.value的絕對(duì)值表示在該信號(hào)量鏈表中已阻塞進(jìn)程的數(shù)目。對(duì)信號(hào)量的每次signal操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位資源，故S.value∶=S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value≤0，則表示在該信號(hào)量鏈表中，仍有等待該資源的進(jìn)程被阻塞，故還應(yīng)調(diào)用wakeup原語，將S.L鏈表中的第一個(gè)等待進(jìn)程喚醒。如果S.value的初值為1，表示只允許一個(gè)進(jìn)程訪問臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量。3.AND型信號(hào)量在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和Emutex的操作，即processA: processB:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若進(jìn)程A和B按下述次序交替執(zhí)行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1A阻塞processB:wait(Dmutex);于是Dmutex=-1B阻塞AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作，即Swait(Simultaneouswait)定義如下：Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1thenfori∶=1tondoSi∶=Si-1;endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori∶=1tondoSi=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor;4.信號(hào)量集Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…andSn≥tnthenfori∶=1tondoSi∶=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi＜tiandsetitsprogramcountertothebeginningoftheSwaitOperation.endifsignal(S1,d1,…,Sn,dn)fori∶=1tondoSi∶=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor;

一般“信號(hào)量集”的幾種特殊情況：

(1)Swait(S,d,d)。此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S，但允許它每次申請(qǐng)d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配。

(2)Swait(S,1,1)。此時(shí)的信號(hào)量集已蛻化為一般的記錄型信號(hào)量(S＞1時(shí))或互斥信號(hào)量(S=1時(shí))。

(3)Swait(S,1,0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S≥1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開關(guān)。6.3信號(hào)量的應(yīng)用1.利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的進(jìn)程可描述如下：Varmutex:semaphore∶=1;beginparbeginprocess1:begin repeat wait(mutex); criticalsection signal(mutex); remainderseetion untilfalse; endprocess2:begin repeat wait(mutex); criticalsection signal(mutex); remaindersection untilfalse; endparend2.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系圖2-10前趨圖舉例Vara,b,c,d,e,f,g;semaphore∶=0,0,0,0,0,0,0;beginparbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end; beginwait(d);S5;signal(g);end; beginwait(e);wait(f);wait(g);S6;end;parendend2023/1/31第三章進(jìn)程的描述與控制366.4經(jīng)典的進(jìn)程同步問題

6.4.1生產(chǎn)者/消費(fèi)者問題

6.4.2哲學(xué)家進(jìn)餐問題6.4.3讀者/寫者問題

2023/1/31第三章進(jìn)程的描述與控制376.4.1生產(chǎn)者/消費(fèi)者問題生產(chǎn)者消費(fèi)者問題是一種同步問題的抽象描述。計(jì)算機(jī)系統(tǒng)中的每個(gè)進(jìn)程都可以消費(fèi)（使用）或生產(chǎn)（釋放）某類資源。這些資源可以是硬件資源，也可以是軟件資源。當(dāng)某一進(jìn)程使用某一資源時(shí)，可以看作是消費(fèi)，稱該進(jìn)程為消費(fèi)者。而當(dāng)某一進(jìn)程釋放某一資源時(shí)，它就相當(dāng)于生產(chǎn)者。2023/1/31第三章進(jìn)程的描述與控制38問題描述通過一個(gè)有界緩沖區(qū)可以把一群生產(chǎn)者p1,p2…,pm，和一群消費(fèi)者Q1,Q2,…,Qn聯(lián)系起來。如圖

只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū);只要緩沖區(qū)未空，消費(fèi)者就可以從緩沖區(qū)中取走物品。2023/1/31第三章進(jìn)程的描述與控制39有n個(gè)緩沖區(qū)的緩沖池放產(chǎn)品取產(chǎn)品2023/1/31第三章進(jìn)程的描述與控制40問題分析為解決生產(chǎn)者消費(fèi)者問題，應(yīng)該設(shè)兩個(gè)同步信號(hào)量:一個(gè)說明空緩沖區(qū)的數(shù)目，用empty表示，初值為有界緩沖區(qū)的大小N，另一個(gè)說明已用緩沖區(qū)的數(shù)目，用full表示，初值為０。由于在此問題中有M個(gè)生產(chǎn)者和N個(gè)消費(fèi)者，它們?cè)趫?zhí)行生產(chǎn)活動(dòng)和消費(fèi)活動(dòng)中要對(duì)有界緩沖區(qū)進(jìn)行操作。由于有界緩沖區(qū)是一個(gè)臨界資源，必須互斥使用，所以，另外還需要設(shè)置一個(gè)互斥信號(hào)量mutex，其初值為１。2023/1/31第三章進(jìn)程的描述與控制41問題的解Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;//緩沖區(qū)in,out:integer:=0,0;//輸入、輸出指針

beginparbeginproducer：begin repeat

…

生產(chǎn)一個(gè)產(chǎn)品nextp;

… wait(empty);//等待空緩沖區(qū)的數(shù)目非0 wait(mutex);//等待無進(jìn)程操作緩沖區(qū)

Buffer(in):=nextp;//往Buffer[in]放產(chǎn)品 in=(in+1)modn; signal(mutex);

//允許其它進(jìn)程操作緩沖區(qū) signal(full);//增加已用緩沖區(qū)的數(shù)目

untilfalseend2023/1/31第三章進(jìn)程的描述與控制42 consumer：begin repeat wait(full);//等待已用緩沖區(qū)的數(shù)目非0 wait(mutex);//等待無進(jìn)程操作緩沖區(qū)

nextc:=Buffer(out)//從Buffer[out]取產(chǎn)品 out=(out+1)modn; signal(mutex);//允許其它進(jìn)程操作緩沖區(qū) signal(empty);//增加空緩沖區(qū)的數(shù)目消費(fèi)nextc產(chǎn)品;

untilfalseendparendend2023/1/31第三章進(jìn)程的描述與控制43采用AND信號(hào)量集解決生產(chǎn)者-消費(fèi)者問題Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;//緩沖區(qū)in,out:integer:=0,0;//輸入、輸出指針

beginparbeginproducer：begin repeat

…

生產(chǎn)一個(gè)產(chǎn)品nextp;

… swait(empty,mutex);

Buffer(in):=nextp;//往Buffer[in]放產(chǎn)品 in=(in+1)modn; ssignal(mutex,full);

untilfalseend等待空緩沖區(qū)的數(shù)目非0;等待無進(jìn)程操作緩沖區(qū);允許其它進(jìn)程操作緩沖區(qū);增加已用緩沖區(qū)的數(shù)目;2023/1/31第三章進(jìn)程的描述與控制44 consumer：begin repeat swait(full,mutex);

nextc:=Buffer(out)//從Buffer[out]取產(chǎn)品 out=(out+1)modn; signal(mutex,empty); 消費(fèi)nextc產(chǎn)品;

untilfalseendparendend等待已用緩沖區(qū)的數(shù)目非0;等待無進(jìn)程操作緩沖區(qū);允許其它進(jìn)程操作緩沖區(qū);增加空緩沖區(qū)的數(shù)目;2023/1/31第三章進(jìn)程的描述與控制45【思考題】如果生產(chǎn)者消費(fèi)者問題中的緩沖區(qū)是無界的，又該如何解呢？2023/1/31第三章進(jìn)程的描述與控制46思考題的解Varmutex,full:semaphore:=1,0;//因無界，無需

empty信號(hào)量buffer:array[0,…]ofitem;//無界緩沖區(qū)in,out:integer:=0,0;//輸入、輸出指針

beginparbeginproducer：begin repeat

…

生產(chǎn)一個(gè)產(chǎn)品nextp;

…

//因無界，不必等待空緩沖區(qū)的數(shù)目非0！ wait(mutex);//等待無進(jìn)程操作緩沖區(qū)

Buffer(in):=nextp;//往Buffer[in]放產(chǎn)品 in=in+1;//因無界，無需考慮輸入指針出界 signal(mutex);

//允許其它進(jìn)程操作緩沖區(qū) signal(full);//增加已用緩沖區(qū)的數(shù)目

untilfalseend2023/1/31第三章進(jìn)程的描述與控制47 consumer：begin repeat

wait(full);//等待已用緩沖區(qū)的數(shù)目非0 wait(mutex);//等待無進(jìn)程操作緩沖區(qū)

nextc:=Buffer(out)//從Buffer[out]取產(chǎn)品 out=out+1;

//因無界，無需考慮輸出指針出界 signal(mutex);//允許其它進(jìn)程操作緩沖區(qū)

//因無界，不必增加空緩沖區(qū)的數(shù)目消費(fèi)nextc產(chǎn)品;

untilfalseendparendend2023/1/31第三章進(jìn)程的描述與控制48【思考題】桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個(gè)蘋果或放一個(gè)桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。 試用P、V操作實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。提示：設(shè)置一個(gè)信號(hào)量表示可否向盤中放水果，一個(gè)信號(hào)量表示可否取桔子，一個(gè)信號(hào)量表示可否取蘋果。2023/1/31第三章進(jìn)程的描述與控制49解:設(shè)置三個(gè)信號(hào)量S,So,Sa，初值分別為1，0，0。S表示可否向盤中放水果;So可否取桔子;Sa可否取蘋果;VarS,So,Sa:semaphore:=1,0,0;beginparbegin

Father：begin repeat

wait(S);//等待水果盤中有空位置將水果放入盤中;

if(是桔子)thensignal(So);//置盤中放了桔子標(biāo)志elsesignal(Sa);//置盤中放了蘋果標(biāo)志

untilfalseend

2023/1/31第三章進(jìn)程的描述與控制50Son：begin repeat

wait(So);//等待水果盤中放了桔子取盤中桔子;signal(S);//置盤中已無水果標(biāo)志吃桔子;

untilfalseendDaughter：begin repeat

wait(Sa);//等待水果盤中放了蘋果取盤中蘋果;signal(S);//置盤中已無水果標(biāo)志吃蘋果;

untilfalseendparendend2023/1/31第三章進(jìn)程的描述與控制51【思考題】若把問題改為:爸爸只向盤中放蘋果，媽媽只向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。

如何用P、V操作實(shí)現(xiàn)爸爸、兒子、女兒4個(gè)并發(fā)進(jìn)程的同步?2023/1/31第三章進(jìn)程的描述與控制52解:信號(hào)量設(shè)置、兒子、女兒進(jìn)程不變。只需修改父親進(jìn)程，并增加母親進(jìn)程。

Father：begin repeat

wait(S);//等待水果盤中有空位置將蘋果放入盤中;

signal(Sa);//置盤中放了蘋果標(biāo)志

untilfalseendMother：begin repeat

wait(S);//等待水果盤中有空位置將桔子放入盤中;signal(So);//置盤中放了桔子標(biāo)志

untilfalseend

2023/1/31第三章進(jìn)程的描述與控制53【思考題】銀行的人民幣存取業(yè)務(wù)問題某銀行的人民幣存取業(yè)務(wù)由

n個(gè)柜臺(tái)工作人員負(fù)責(zé)。每個(gè)顧客進(jìn)入銀行后先從抽號(hào)機(jī)中取一個(gè)號(hào)，并且等著叫號(hào)。當(dāng)一個(gè)柜臺(tái)工作人員空閑下來，就叫下一個(gè)號(hào)。

試用P，V操作編寫柜臺(tái)工作人員進(jìn)程和顧客進(jìn)程的程序。2023/1/31第三章進(jìn)程的描述與控制54問題分析1可把“顧客號(hào)數(shù)”看成是一個(gè)單緩沖區(qū)，顧客和柜員必須互斥訪問;CUSTOMER_NUM--單緩沖區(qū)

Semaphorecounter;//柜臺(tái)人員數(shù)，初值為nSemaphorecustomer;//當(dāng)前等待的顧客數(shù)；初值為0；Semaphoremutex;//互斥對(duì)顧客號(hào)數(shù)的訪問。初值為1

2023/1/31第三章進(jìn)程的描述與控制55思考題的解1

Semaphorecounter;//柜臺(tái)人員數(shù)，初值為nSemaphorecustomer;//當(dāng)前等待的顧客數(shù)；初值為0；Semaphoremutex;//互斥對(duì)顧客號(hào)數(shù)的訪問。初值為1顧客進(jìn)程：{intnum;//取號(hào)碼P(mutex);num=CUSTOMER_NUM++;V(mutex);//等待叫號(hào)V(customer);//請(qǐng)求服務(wù)

P(counter);//等待號(hào)接受服務(wù)；離開；P(mutex);COSTOMER_NUM--;V(mutex);}柜臺(tái)人員進(jìn)程：{

intnum;

REPEAT//叫號(hào)

P(customer);//等待顧客請(qǐng)求服務(wù)

叫號(hào)為顧客服務(wù);V(counter);//服務(wù)完成UNTILfalse;}2023/1/31第三章進(jìn)程的描述與控制56問題分析2可把“顧客號(hào)數(shù)”看成是一個(gè)單緩沖區(qū)，顧客和柜員必須互斥訪問;CUSTOMER_NUM--單緩沖區(qū)顧客號(hào)數(shù)COUNTER_NUM--單緩沖區(qū)柜臺(tái)人員編號(hào)

Semaphorecounter;//柜臺(tái)人員數(shù)，初值為nSemaphorecustomer;//當(dāng)前等待的顧客數(shù)；初值為0；Semaphoremutex;//互斥對(duì)顧客號(hào)數(shù)的訪問。初值為1

Semaphoremutex2;//互斥對(duì)柜臺(tái)人員編號(hào)的訪問。初值為12023/1/31第三章進(jìn)程的描述與控制57思考題的解2

Semaphorecounter;//柜臺(tái)人員數(shù)，初值為nSemaphorecustomer;//當(dāng)前等待的顧客數(shù)；初值為0；Semaphoremutex,mutex2;//互斥對(duì)顧客號(hào)數(shù),柜臺(tái)人員編號(hào)的訪問。初值為1顧客進(jìn)程：{intx;//取號(hào)碼P(mutex);x=CUSTOMER_NUM++;V(mutex);//等待叫號(hào)V(customer);//請(qǐng)求服務(wù)

P(counter);//等待叫號(hào)ACTION_CUSTOMER(x);//接受服務(wù)；}柜臺(tái)人員進(jìn)程：{

intx;

REPEAT//叫號(hào)

P(customer);//等待顧客請(qǐng)求服務(wù)P(mutex2);x=COUNTER_NUM;V(mutex2);ACTION_COUNTER(x);//為顧客服務(wù)V(counter);//服務(wù)完成UNTILfalse;}2023/1/31第三章進(jìn)程的描述與控制58問題分析3可把抽號(hào)機(jī)中記錄顧客抽號(hào)信息的內(nèi)存區(qū)域看成是一個(gè)共享緩沖區(qū)，顧客抽取一個(gè)號(hào),就如同在緩沖區(qū)中占了一個(gè)位子（放了一個(gè)“產(chǎn)品”），柜員叫一個(gè)號(hào)，就如同從緩沖區(qū)中空了一個(gè)位子（取走一個(gè)“產(chǎn)品”），如果抽號(hào)數(shù)目不限，則可把該緩沖區(qū)看做是一個(gè)無界緩沖區(qū)；如果抽號(hào)數(shù)目有限(如50個(gè))，則可把該緩沖區(qū)看做是一個(gè)有界緩沖區(qū)；我們以無界緩沖區(qū)為例。通過該無界緩沖區(qū)可以把一群顧客（生產(chǎn)者）p1,p2…,pm，和一群柜臺(tái)工作人員（消費(fèi)者）Q1,Q2,…,Qn聯(lián)系起來。如圖，于是，該問題就變成了一個(gè)無界緩沖區(qū)情況下生產(chǎn)者-消費(fèi)者問題；

2023/1/31第三章進(jìn)程的描述與控制59思考題的解3Varmutex,full:semaphore:=1,0;buffer:array[0,…]ofitem;//無界緩沖區(qū)in,out:integer:=0,0;//輸入、輸出指針

beginparbegin

顧客：begin repeat

…

抽取一個(gè)號(hào)number1;

wait(mutex);//等待柜員不在叫號(hào)

Buffer(in):=number1;//往Buffer[in]放號(hào) in=in+1; signal(mutex);

//允許柜員叫號(hào) signal(full);//增加可叫號(hào)碼的數(shù)目

untilfalseend2023/1/31第三章進(jìn)程的描述與控制60

柜員：begin repeat

wait(full);//等待有可叫的號(hào)碼 wait(mutex);//等待顧客不在抽號(hào)

number2:=Buffer(out)//從Buffer[out]取號(hào) out=out+1;

signal(mutex);//允許顧客抽號(hào) 叫number2號(hào)顧客；為該顧客辦理存取業(yè)務(wù);

untilfalseendparendend2023/1/31第三章進(jìn)程的描述與控制61【思考題】在一個(gè)銀行帳號(hào)上存取款問題.父親存款,兒子來取;等等單緩沖區(qū)問題2023/1/31第三章進(jìn)程的描述與控制62【思考題】火車站的排隊(duì)購買車票問題。第一種情況：售票停內(nèi)最多允許100個(gè)購票者在里面；第二種情況：售票停內(nèi)能允許的購票者不限（可排到外面）；2023/1/31第三章進(jìn)程的描述與控制636.4.2哲學(xué)家就餐問題有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子2023/1/31第三章進(jìn)程的描述與控制64筷子是臨界資源，一段時(shí)間只允許一位哲學(xué)家使用，為互斥使用，可用一個(gè)信號(hào)量表示一只筷子。5個(gè)信號(hào)量用數(shù)組描述如下：

varchopstick:array[0,…,4]ofsemaphore;所有信號(hào)量初值均為1，第i位哲學(xué)家的活動(dòng)可描述如下：repeat

wait(chopstick[i]);//拿左邊的筷子wait(chopstick[(i+1)mod5])；//拿右邊的筷子

進(jìn)食；

signal(chopstick[i]);//放左邊的筷子signal(chopstick[(i+1)mod5])；//放右邊的筷子

思考；untilfalse1、采用記錄型信號(hào)量集解決哲學(xué)家就餐問題2023/1/31第三章進(jìn)程的描述與控制65以上解法會(huì)出現(xiàn)死鎖:如5個(gè)哲學(xué)家同時(shí)去拿左邊的筷子后,又要同時(shí)去拿右邊的筷子時(shí);為防止死鎖發(fā)生可采取下列措施之一：最多允許4個(gè)哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過的兩只筷子；僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子；給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，然后去拿右邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之；由此，最后總會(huì)有一個(gè)哲學(xué)家能獲得兩只筷子而進(jìn)餐；分析2023/1/31第三章進(jìn)程的描述與控制662、采用AND信號(hào)量集解決哲學(xué)家就餐問題哲學(xué)家就餐問題本質(zhì)上就是AND同步問題，故用AND信號(hào)量機(jī)制可獲得最簡潔的解法。

varchopstick:array[0,…,4]ofsemaphore：=(1,1,1,1,1);processirepeat

思考；

Swait(chopstick[(i+1)mod5],chopstick[i]);

進(jìn)食；

Ssignal(chopstick[(i+1)mod5],chopstick[i]);

untilfalse

采取措施:僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子；2023/1/31第三章進(jìn)程的描述與控制676.4.3讀者/寫者問題

有兩組并發(fā)進(jìn)程:讀者(Reader)和寫者(Writer),共享一組數(shù)據(jù)區(qū)或一個(gè)共享文件;要求：允許多個(gè)Reader同時(shí)執(zhí)行讀操作不允許Reader、Writer同時(shí)操作不允許多個(gè)Writer同時(shí)操作2023/1/31第三章進(jìn)程的描述與控制681、采用記錄型信號(hào)量集解決讀者-寫者問題如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等待，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等待如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待2023/1/31第三章進(jìn)程的描述與控制69讀者寫者問題的解法設(shè)有兩個(gè)信號(hào)量wmutex=1，rmutex=1另設(shè)一個(gè)全局變量readcount=0，表示正在讀的讀者數(shù)目wmutex用于讀者和寫者、寫者和寫者之間的互斥rmutex用于對(duì)readcount這個(gè)