2.4經(jīng)典進(jìn)程同步問(wèn)題

在多道程序環(huán)境下，進(jìn)程同步問(wèn)題是十分重要的，也是相當(dāng)有趣的問(wèn)題，因而吸引了不少學(xué)者對(duì)它進(jìn)行研究。

其中較有代表性的是“生產(chǎn)者——消費(fèi)者問(wèn)題”、“讀者——寫者問(wèn)題”、“哲學(xué)家進(jìn)餐問(wèn)題”等。12.4.1生產(chǎn)者——消費(fèi)者問(wèn)題問(wèn)題的描述：有一群生產(chǎn)者進(jì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)的消息放入一個(gè)緩沖區(qū)中，消費(fèi)者進(jìn)程可以從一個(gè)緩沖區(qū)中取得一個(gè)消息消費(fèi)。不允許消息費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)中去取消息，也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝有消息且尚未被取走消息的緩沖區(qū)中投放消息。2需要解決的問(wèn)題：1、對(duì)緩沖池的互斥訪問(wèn)，即只有一個(gè)進(jìn)程訪問(wèn)緩沖區(qū)。2、對(duì)生產(chǎn)、消費(fèi)進(jìn)程的同步，即：有產(chǎn)品時(shí)才能消費(fèi)，無(wú)產(chǎn)品時(shí)，必須先生產(chǎn)后消費(fèi)；有空間時(shí)才能生產(chǎn)，空間滿時(shí)，必須先消費(fèi)再生產(chǎn)。3信號(hào)量的設(shè)置：1、一個(gè)互斥信號(hào)量mutex，用于實(shí)現(xiàn)對(duì)共享緩沖區(qū)的互斥訪問(wèn)，初始值為1。2、兩個(gè)同步信號(hào)量，分別表示可用資源數(shù)：Empty：表示空緩沖區(qū)的個(gè)數(shù)，初始值為nFull：表示裝有消息的緩沖區(qū)的個(gè)數(shù)，初始值為0，（一個(gè)緩沖區(qū)中放一條消息）4一、利用記錄型信號(hào)量 解決生產(chǎn)者——消費(fèi)者問(wèn)題數(shù)據(jù)結(jié)構(gòu)：Varmutex,empty,full：semaphore∶=1，n，0；//定義信號(hào)量并賦初值

buffer：array［0,…,n-1］ofitem;//定義緩沖區(qū)in,out:integer∶=0,0;//定義存取指針的初始位置5Proceduer：//生產(chǎn)者進(jìn)程beginrepeat…生產(chǎn)一件產(chǎn)品;…

wait(empty);wait(mutex);buffer[in]:=nextp;in∶=(in+1)modn;

signal(mutex);

signal(full);untilfalse;endempty:=empty-1;ifempty<0thenblock;mutex:=mutex-1;ifmutex<0thenblock;full:=full+1;iffull<=0thenwakeup;mutex:=mutex+1;ifmutex<=0thenwakeup;6consumer：//消費(fèi)者進(jìn)程beginrepeat

wait(full);wait(mutex);nextc:=buffer[out];out∶=(out+1)modn;

signal(mutex);signal(empty);消費(fèi)這件產(chǎn)品;untilfalse;endfull:=full-1;iffull<0thenblock;mutex:=mutex-1;ifmutex<0thenblock;empty:=empty+1;ifempty<=0thenwakeup;mutex:=mutex+1;ifmutex<=0thenwakeup;7例：有生產(chǎn)者P1、P2和消費(fèi)者C1，利用3個(gè)信號(hào)量和對(duì)它們的wait和signal操作實(shí)現(xiàn)同步與互斥。初始條件：記錄型信號(hào)量mutex.value=1,empty=2,full=0執(zhí)行序列mutexemptyfullempty隊(duì)列full隊(duì)列P1:wait(empty),wait(m),CS01signal(m),signal(f)11P1:wait(empty),wait(m),CS00signal(m),signal(f)12P2:wait(empty)－1p2P1:wait(empty)－2p1C1:wait(full),wait(m),CS01signal(m),signal(empty)1－1（喚醒p2）P2:wait(m)0CSC1:wait(full),wait(m)－10C1P2:signal(m),signal(full)01(喚醒C1)C1:CS,signal(m),signal(e)10（喚醒p1)P1:wait(m)08在生產(chǎn)者—消費(fèi)者問(wèn)題中應(yīng)注意：

(１)在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)。(２)對(duì)資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的進(jìn)程中，這樣保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程的同步及交替執(zhí)行。(３)在每個(gè)進(jìn)程中，多個(gè)wait操作順序不能顛倒，而signal操作的次序是無(wú)關(guān)緊要的。9Wait操作不能顛倒！！P：wait(empty)wait(mutex)C：wait(full)wait(mutex)如果顛倒P：wait(mutex)mutexl.value=0wait(empty)如果此時(shí)緩沖池滿empty=－1，P阻塞C：wait(mutex)mutex.value=－1，C阻塞

wait(full)P阻塞在empty隊(duì)列中，等待一個(gè)空緩沖C阻塞在mutex隊(duì)列中，等待公共緩沖池訪問(wèn)權(quán)由于wait操作順序不當(dāng)，會(huì)造成死鎖，因此wait操作順序不能顛倒。10二、利用AND信號(hào)量 解決生產(chǎn)者——消費(fèi)者問(wèn)題數(shù)據(jù)結(jié)構(gòu)：Varmutex,empty,full：semaphore∶=1，n，0；//定義信號(hào)量并賦初值

buffer：array［0,…,n-1］ofitem;//定義緩沖區(qū)in,out:integer∶=0,0;//定義存取指針的初始位置11Proceduer：//生產(chǎn)者進(jìn)程beginrepeat…生產(chǎn)一件產(chǎn)品;…

Swait(empty，mutex);buffer[in]:=nextp;in∶=(in+1)modn;

Ssignal(mutex，full);untilfalse;endifempty>=1

andmutex>=1thenempty:=empty-1;mutex:=mutex-1;mutex:=mutex+1;full:=full+1;12consumer：//消費(fèi)者進(jìn)程beginrepeat

Swait(full，mutex);nextc:=buffer[out];out∶=(out+1)modn;

Ssignal(mutex，empty); 消費(fèi)這件產(chǎn)品;untilfalse;endiffull>=1andmutex>=1thenfull:=full-1;mutex:=mutex-1;mutex:=mutex+1;empty:=empty+1;133．利用管程解決生產(chǎn)者—消費(fèi)者問(wèn)題在利用管程方法來(lái)解決生產(chǎn)者—消費(fèi)者問(wèn)題時(shí)，首先便是為它們建立一個(gè)管程，并命名為ProclucerConsumer，或簡(jiǎn)稱為PC。其中包括兩個(gè)過(guò)程：(1)put(item)過(guò)程。生產(chǎn)者利用該過(guò)程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量count來(lái)表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)count≥n時(shí)，表示緩沖池已滿，生產(chǎn)者須等待。(2)get(item)過(guò)程。消費(fèi)者利用該過(guò)程從緩沖池中取出一個(gè)產(chǎn)品，當(dāng)count≤0時(shí)，表示緩沖池中已無(wú)可取用的產(chǎn)品，消費(fèi)者應(yīng)等待。14PC管程可描述如下：typeproducer-consumer=monitorVarin,out,count:integer；buffer:array[0,…,n-1]ofitem；notfull，notempty:condition；procedureentryput(item)beginifcount>=nthennotfull.wait；buffer(in):=nextp；in:=(in+1)modn；count:=count+1；ifnotempty.queuethennotempty.signal；end15procedureentryget(item)beginifcount<=0thennotempty.wait；nextc:=buffer(out)；out:=(out+1)modn；count:=count-1；ifnotfull.quenethennotfull.signal；endbeginin:=out:=0；count:=0end16在利用管程解決生產(chǎn)者—消費(fèi)者問(wèn)題時(shí)，其中的生產(chǎn)者和消費(fèi)者可描述為：producer:beginrepeatproduceaniteminnextp；PC.put(item)；untilfalse；endconsumer:beginrepeatPC.get(item)；consumetheiteminnextc；untilfalse；end172.4.2哲學(xué)家進(jìn)餐問(wèn)題1、問(wèn)題描述：設(shè)有5個(gè)哲學(xué)家圍坐在一張圓桌前吃飯。桌上有5支筷子和5個(gè)碗。哲學(xué)家要吃飯時(shí)，只有從左、右兩邊都拿到筷子時(shí)，才能吃飯。如果筷子已在他人手上，則該哲學(xué)家必須等待到他人吃完后才能拿到筷子；任何一個(gè)哲學(xué)家在自己未拿到兩只筷子吃飯之前，決不放下自己手里的筷子。182、問(wèn)題分析：放在桌子上的筷子是臨界資源，在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對(duì)筷子的互斥使用，可以為每一只筷子設(shè)置一個(gè)信號(hào)量，由這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組：Varchopstick:array［0,…,4］ofsemaphore;設(shè)初始條件下，所有哲學(xué)家都未吃，故所有信號(hào)量均被初始化為1。19假設(shè)每一位哲學(xué)家拿筷子的方法都是：先拿起左邊的筷子，再拿起右邊的筷子，則第i位哲學(xué)家的活動(dòng)可描述為：一、利用記錄型信號(hào)量 解決哲學(xué)家進(jìn)餐問(wèn)題20第i位哲學(xué)家的活動(dòng)可描述為：repeatwait(chopstick[i]);wait(chopstick[i+1]mod5);….eat;….signal(chopstick[i]);signal(chopstick[i+1]mod5);….think;untilfalse;21以上算法存在一個(gè)問(wèn)題：假設(shè)5個(gè)哲學(xué)家同時(shí)拿起左邊的筷子，就會(huì)使五個(gè)信號(hào)量chopstick均為0；那么當(dāng)他們?cè)偃ツ糜疫叺目曜訒r(shí)，就會(huì)因無(wú)機(jī)筷子而無(wú)限期地等待，這就會(huì)產(chǎn)生死鎖。22下面給出幾種解決方法：（1）至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過(guò)的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。（2）僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。（3）規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。23二、利用AND信號(hào)量機(jī)制 解決哲學(xué)家進(jìn)餐問(wèn)題即要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源（筷子）后，才能進(jìn)餐。Varchopstick:array[0,…,4]ofsemaphore:=（1,1,1,1,1）;ProcessirepeatthinkSwait（chopstick[i+1]mod5，chopstick[i]）；eat;Ssignal（chopstick[i+1]mod5，chopstick[i]）；untilfalse;242.4.3讀者—寫者問(wèn)題1．問(wèn)題的提出一個(gè)數(shù)據(jù)文件Ｆ可以被多個(gè)并發(fā)進(jìn)程共享，將這些訪問(wèn)該文件的進(jìn)程按訪問(wèn)方式分為兩類：一類只能讀共享對(duì)象的內(nèi)容，把這類進(jìn)程稱為讀進(jìn)程或讀者；另一類進(jìn)程則要更新（寫）共享對(duì)象文件F，將這些進(jìn)程稱為寫進(jìn)程或?qū)懻?。試用Wait、Signal操作解決各進(jìn)程間的同步問(wèn)題。252．問(wèn)題的分析顯然，多個(gè)讀者同時(shí)讀一個(gè)共享對(duì)象是可以的，然而一個(gè)寫者不能與其它任何讀者或?qū)懻咄瑫r(shí)共享該文件。亦即：在使用共享文件時(shí)，一個(gè)寫進(jìn)程與其它所有進(jìn)程都是互斥的。但多個(gè)讀進(jìn)程之間不存在互斥的現(xiàn)象。26一、利用記錄型信號(hào)量 解決讀者——寫者問(wèn)題信號(hào)量的設(shè)置：Wmutex：互斥使用該共享文件信號(hào)量。如：寫進(jìn)程write與讀進(jìn)程reader在使用文件時(shí)是互斥的；共享文件只有一個(gè)，設(shè)初始情況未被使用，則初值為1。readcount：整型變量，表示正在讀的進(jìn)程個(gè)數(shù)，初值為0。該變量屬臨界資源。rmutex：計(jì)數(shù)器readcount的信號(hào)量。因?yàn)閞eadcount是一個(gè)可被多個(gè)reader進(jìn)程訪問(wèn)的臨界資源，為此設(shè)一信號(hào)量。設(shè)初始狀態(tài)下無(wú)進(jìn)程讀和寫，故rmutex的初值設(shè)為1。27由于多個(gè)進(jìn)程可以同時(shí)讀，因此只要有一個(gè)reader進(jìn)程在讀，其它reader進(jìn)程便不必申請(qǐng)?jiān)摴蚕砦募?，直接讀即可；若無(wú)文件在讀，則第一個(gè)讀文件的進(jìn)程必須做申請(qǐng)?jiān)撐募牟僮?。只要有read進(jìn)程在執(zhí)行，則不允許writer進(jìn)程去寫。因此，僅當(dāng)readcount=0,即無(wú)reader進(jìn)程在讀時(shí)，reader進(jìn)程才需要執(zhí)行wait(wmutex)操作。若wait(wmutex)操作成功，reader進(jìn)程便可去讀，相應(yīng)地，做readcount+1操作。同理，僅當(dāng)reader進(jìn)程在執(zhí)行了readcount減1操作后其值為0時(shí)，才須執(zhí)行signal(wmutex)操作，以便讓writer進(jìn)程寫。28數(shù)據(jù)結(jié)構(gòu)：Varrmutex,wmutex：semaphore：=1，1;readcount：integer：=0;29reader:repeat

wait(rmutex);

ifreadcount=0thenwait(wmutex);readcount:=readcount+1;

signal(rmutex);……readfile;……

wait(rmutex);readcount:=readcount-1;

ifreadcount=0thensignal(wmutex);

signal(rmutex);untilfalse第一個(gè)讀者要檢查文件的訪問(wèn)權(quán)是否空閑最后一個(gè)讀進(jìn)程要負(fù)責(zé)釋放對(duì)文件的訪問(wèn)權(quán)申請(qǐng)對(duì)readcount的訪問(wèn)權(quán)釋放對(duì)readcount的訪問(wèn)權(quán)讀操作完畢，要修改readcount的值30writer:beginrepeat

wait(wmutex);……writingoperation;……

signal(wmutex);

untilfalse;end申請(qǐng)對(duì)文件的訪問(wèn)權(quán)釋放文件的訪問(wèn)權(quán)31舉例：文件Fr1,r2,w1三個(gè)進(jìn)程并發(fā)執(zhí)行初始：readcount=0,rmutex=1,wmutex=1執(zhí)行過(guò)程readcountrmutexwmutex011r1:wait(rmutex);ifreadcount=0thenwait(wmutex)00readcount+11signal(rmutex)1開(kāi)始讀r2:wait(rmutex);0readcount+12signal(rmutex)1w1:wait(wmutex);－1r1:wait(rmutex);readcount－101signal(rmutex)1r2:wait(rmutex);readcount－100signal(rmutex)1ifreadcount≠0被阻塞ifreadcount≠0ifreadcount=0thensignal(wmutex)0w1:開(kāi)始寫signal(wmutex)1讀結(jié)束讀結(jié)束32二、利用信號(hào)量集機(jī)制 解決讀者——寫者問(wèn)題問(wèn)題描述：這里的讀者—寫者問(wèn)題，增加了一條限制，即最多只允許RN個(gè)讀者同時(shí)讀。為此，引入一個(gè)信號(hào)量L，初始值為RN，通過(guò)執(zhí)行wait（L，1，1）操作來(lái)控制讀者的數(shù)目。VarRN:integer;L,mx:semaphore:Rn,1;33reader:repeat

Swait（L，1，1）;Swait（mx，1，0）；……readfile;……

Ssignal（L，1）；untilfalseifL>=1thenL:=L-1;ifmx>=1thenmx:=mx-0;//即mx值不變L:=L+1;34writer:repeatSwait(mx,1