經典進程同步問題

2.4經典進程同步問題

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

其中較有代表性的是“生產者——消費者問題”、“讀者——寫者問題”、“哲學家進餐問題”等。12.4.1生產者——消費者問題問題的描述：有一群生產者進程生產消息，并將此消息提供給消費者進程消費。為使生產者進程和消費者進程并發(fā)執(zhí)行，在它們之間設置一個具有n個緩沖區(qū)的公共緩沖池。生產者進程將它所生產的消息放入一個緩沖區(qū)中，消費者進程可以從一個緩沖區(qū)中取得一個消息消費。不允許消息費者進程到一個空緩沖區(qū)中去取消息，也不允許生產者進程向一個已裝有消息且尚未被取走消息的緩沖區(qū)中投放消息。2需要解決的問題：1、對緩沖池的互斥訪問，即只有一個進程訪問緩沖區(qū)。2、對生產、消費進程的同步，即：有產品時才能消費，無產品時，必須先生產后消費；有空間時才能生產，空間滿時，必須先消費再生產。3信號量的設置：1、一個互斥信號量mutex，用于實現(xiàn)對共享緩沖區(qū)的互斥訪問，初始值為1。2、兩個同步信號量，分別表示可用資源數(shù)：Empty：表示空緩沖區(qū)的個數(shù)，初始值為nFull：表示裝有消息的緩沖區(qū)的個數(shù)，初始值為0，（一個緩沖區(qū)中放一條消息）4一、利用記錄型信號量 解決生產者——消費者問題數(shù)據結構：Varmutex,empty,full：semaphore∶=1，n，0；//定義信號量并賦初值

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

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：//消費者進程beginrepeat

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

signal(mutex);signal(empty);消費這件產品;untilfalse;endfull:=full-1;iffull<0thenblock;mutex:=mutex-1;ifmutex<0thenblock;empty:=empty+1;ifempty<=0thenwakeup;mutex:=mutex+1;ifmutex<=0thenwakeup;7例：有生產者P1、P2和消費者C1，利用3個信號量和對它們的wait和signal操作實現(xiàn)同步與互斥。初始條件：記錄型信號量mutex.value=1,empty=2,full=0執(zhí)行序列mutexemptyfullempty隊列full隊列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在生產者—消費者問題中應注意：

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

wait(full)P阻塞在empty隊列中，等待一個空緩沖C阻塞在mutex隊列中，等待公共緩沖池訪問權由于wait操作順序不當，會造成死鎖，因此wait操作順序不能顛倒。10二、利用AND信號量 解決生產者——消費者問題數(shù)據結構：Varmutex,empty,full：semaphore∶=1，n，0；//定義信號量并賦初值

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

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：//消費者進程beginrepeat

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

Ssignal(mutex，empty); 消費這件產品;untilfalse;endiffull>=1andmutex>=1thenfull:=full-1;mutex:=mutex-1;mutex:=mutex+1;empty:=empty+1;133．利用管程解決生產者—消費者問題在利用管程方法來解決生產者—消費者問題時，首先便是為它們建立一個管程，并命名為ProclucerConsumer，或簡稱為PC。其中包括兩個過程：(1)put(item)過程。生產者利用該過程將自己生產的產品投放到緩沖池中，并用整型變量count來表示在緩沖池中已有的產品數(shù)目，當count≥n時，表示緩沖池已滿，生產者須等待。(2)get(item)過程。消費者利用該過程從緩沖池中取出一個產品，當count≤0時，表示緩沖池中已無可取用的產品，消費者應等待。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在利用管程解決生產者—消費者問題時，其中的生產者和消費者可描述為：producer:beginrepeatproduceaniteminnextp；PC.put(item)；untilfalse；endconsumer:beginrepeatPC.get(item)；consumetheiteminnextc；untilfalse；end172.4.2哲學家進餐問題1、問題描述：設有5個哲學家圍坐在一張圓桌前吃飯。桌上有5支筷子和5個碗。哲學家要吃飯時，只有從左、右兩邊都拿到筷子時，才能吃飯。如果筷子已在他人手上，則該哲學家必須等待到他人吃完后才能拿到筷子；任何一個哲學家在自己未拿到兩只筷子吃飯之前，決不放下自己手里的筷子。182、問題分析：放在桌子上的筷子是臨界資源，在一段時間內只允許一位哲學家使用。為了實現(xiàn)對筷子的互斥使用，可以為每一只筷子設置一個信號量，由這五個信號量構成信號量數(shù)組：Varchopstick:array［0,…,4］ofsemaphore;設初始條件下，所有哲學家都未吃，故所有信號量均被初始化為1。19假設每一位哲學家拿筷子的方法都是：先拿起左邊的筷子，再拿起右邊的筷子，則第i位哲學家的活動可描述為：一、利用記錄型信號量 解決哲學家進餐問題20第i位哲學家的活動可描述為：repeatwait(chopstick[i]);wait(chopstick[i+1]mod5);….eat;….signal(chopstick[i]);signal(chopstick[i+1]mod5);….think;untilfalse;21以上算法存在一個問題：假設5個哲學家同時拿起左邊的筷子，就會使五個信號量chopstick均為0；那么當他們再去拿右邊的筷子時，就會因無機筷子而無限期地等待，這就會產生死鎖。22下面給出幾種解決方法：（1）至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。（2）僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。（3）規(guī)定奇數(shù)號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學家則相反。最后總會有一位哲學家能獲得兩只筷子而進餐。23二、利用AND信號量機制 解決哲學家進餐問題即要求每個哲學家先獲得兩個臨界資源（筷子）后，才能進餐。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讀者—寫者問題1．問題的提出一個數(shù)據文件Ｆ可以被多個并發(fā)進程共享，將這些訪問該文件的進程按訪問方式分為兩類：一類只能讀共享對象的內容，把這類進程稱為讀進程或讀者；另一類進程則要更新（寫）共享對象文件F，將這些進程稱為寫進程或寫者。試用Wait、Signal操作解決各進程間的同步問題。252．問題的分析顯然，多個讀者同時讀一個共享對象是可以的，然而一個寫者不能與其它任何讀者或寫者同時共享該文件。亦即：在使用共享文件時，一個寫進程與其它所有進程都是互斥的。但多個讀進程之間不存在互斥的現(xiàn)象。26一、利用記錄型信號量 解決讀者——寫者問題信號量的設置：Wmutex：互斥使用該共享文件信號量。如：寫進程write與讀進程reader在使用文件時是互斥的；共享文件只有一個，設初始情況未被使用，則初值為1。readcount：整型變量，表示正在讀的進程個數(shù)，初值為0。該變量屬臨界資源。rmutex：計數(shù)器readcount的信號量。因為readcount是一個可被多個reader進程訪問的臨界資源，為此設一信號量。設初始狀態(tài)下無進程讀和寫，故rmutex的初值設為1。27由于多個進程可以同時讀，因此只要有一個reader進程在讀，其它reader進程便不必申請該共享文件，直接讀即可；若無文件在讀，則第一個讀文件的進程必須做申請該文件的操作。只要有read進程在執(zhí)行，則不允許writer進程去寫。因此，僅當readcount=0,即無reader進程在讀時，reader進程才需要執(zhí)行wait(wmutex)操作。若wait(wmutex)操作成功，reader進程便可去讀，相應地，做readcount+1操作。同理，僅當reader進程在執(zhí)行了readcount減1操作后其值為0時，才須執(zhí)行signal(wmutex)操作，以便讓writer進程寫。28數(shù)據結構：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第一個讀者要檢查文件的訪問權是否空閑最后一個讀進程要負責釋放對文件的訪問權申請對readcount的訪問權釋放對readcount的訪問權讀操作完畢，要修改readcount的值30writer:beginrepeat

wait(wmutex);……writingoperation;……

signal(wmutex);

untilfalse;end申請對文件的訪問權釋放文件的訪問權31舉例：文件Fr1,r2,w1三個進程并發(fā)執(zhí)行初始：readcount=0,rmutex=1,wmutex=1執(zhí)行過程readcountrmutexwmutex011r1:wait(rmutex);ifreadcount=0thenwait(wmutex)00readcount+11signal(rmutex)1開始讀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:開始寫signal(wmutex)1讀結束讀結束32二、利用信號量集機制 解決讀者——寫者問題問題描述：這里的讀者—寫者問題，增加了一條限制，即最多只允許RN個讀者同時讀。為此，引入一個信號量L，初始值為RN，通過執(zhí)行wait（L，1，1）操作來控制讀者的數(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