第3章 進程同步與通信同步

第3章進程同步與通信●進程同步與互斥

●經(jīng)典進程同步問題

●管程

●AND信號量

●進程通信本章要點進程同步的基本概念●同步：指多個進程中發(fā)生的事件存在著某種時序關系，它們必須按規(guī)定時序執(zhí)行，以共同完成一項任務?！窕コ猓憾鄠€進程不能同時使用同一資源?！衽R界資源：某段時間內(nèi)僅允許一個進程使用的資源。●臨界區(qū)：每個進程中訪問臨界資源的那段代碼。3信號量(semaphore)管理相應臨界區(qū)的公有資源，它代表可用資源實體。4信號量是一個整型變量?！?：可供并發(fā)進程使用的資源實體數(shù)＜0：正在等待使用臨界區(qū)的進程數(shù)用于互斥的信號量初值應該大于零58.P,V原語信號量的初值只能由P,V原語操作。P:passerenV:verhoogP操作：申請資源操作sem減1若sem減1后仍大于1或等于零，則P返回，進程繼續(xù)；若sem減1后小于零，則該進程阻塞轉(zhuǎn)等待隊列中。信號燈的PV操作voidwait(semaphores){s.value=s.value-1;if(s.value<0)block(s.queue);/*將進程阻塞，并將其投入等待隊列s.queue*/}P操作7V操作：釋放資源操作sem加1若sem加1后結(jié)果大于1，則V停止操作，該進程返回調(diào)用處，繼續(xù)執(zhí)行；若sem加1后小于或等于零，則該進程轉(zhuǎn)就緒隊列，同時進程調(diào)度選取一個等待隊列中的進程轉(zhuǎn)運行或就緒。P,V操作必須用原語實現(xiàn)。信號燈的PV操作voidsignal(semaphores){s.value=s.value+1;if(s.value<=0)wackup(s.queue);/*喚醒阻塞進程，將其從等待隊列s.queue取出，投入就緒隊列*/}V操作用信號燈解決互斥問題

semaphoremutex=1;

P1:

while(1){

P(mutex); 臨界區(qū);

V(mutex);

剩余區(qū);

};

P2: while(1){

P(mutex); 臨界區(qū)

V(mutex);

剩余區(qū);

};10互斥進程舉例1－兩個進程共享一臺打印機設信號量print代表打印機，初值為1.intmain(void){ intprint=1; cobegin pa();pb(); coend}pa(){ P(print);

使用打印機 V(print);}pb(){ P(print);

使用打印機 V(print);}print=1表示沒有進程使用打印機print=0表示一個進程在用，沒有進程等待print=-1表示一個進程在用，另一個在等待11信號量可能的取值范圍假設有N個并發(fā)進程共用一臺打印機，設互斥信號量mutex的初值為1，則：信號量mutex代表什么？mutex的取值范圍為多少？mutex的值分別代表什么含義？12N個并發(fā)進程，互斥信號量mutex的初值為1：mutex的取值范圍為：1～-(N-1)1：表示沒有進程進入臨界區(qū)。有一個資源，無進程等待；0：表示有1個進程進入臨界區(qū)。無資源，無進程等待；-i：表示1個進程進入臨界區(qū)。無資源，且有i(i<=N-1)個進程等待進入。13思考：n個并發(fā)進程，共享m個共享資源：mutex的取值范圍為？互斥問題舉例2[例]假設某飛機定票系統(tǒng)在t0時刻有A、B、C、D四個終端程序同時都要對機票庫中的某航班當前剩余票數(shù)X進行操作。如果每個終端程序的當前定票需求為N，并對共享變量X進行如下操作：在機票數(shù)據(jù)庫中取出當前剩余票數(shù)X；判斷X>0（有票嗎）？如果有，X≥N（票夠嗎）？如果夠，則出票（打印票據(jù)）；X＝X－N（修改剩余票數(shù)）；將X回寫到數(shù)據(jù)庫中；1415針對臨界資源機票數(shù)設置一個信號量mutex，初值為1。每個終端進程中的程序描述如下：P（mutex）；在機票數(shù)據(jù)庫中取出當前剩余票數(shù)X；判斷X>0（有票嗎）？如果有，X≥N（票夠嗎）？如果夠，則出票（打印票據(jù)）；X＝X－N（修改剩余票數(shù)）；將X回寫到數(shù)據(jù)庫中；V（mutex）；16如果有n個終端，則mutex信號量的取值范圍為：

－（n－1）≤mutex≤1其物理含義為：當機票數(shù)空閑時，mutex=1。當有一個終端進入，對機票進行處理，其它終端進程還沒有到來時，mutex=0。當所有終端進程都到來，且有一個正在對機票進行處理時，mutex=－（n－1）。它表示有n－1個進程在等待隊列上等待。x代表某航班的可用座位數(shù)，p1和p2兩個售票進程，售票工作是對變量x減1。試用信號量的P、V操作實現(xiàn)這兩個進程的互斥。設：mutex為互斥信號量,p1() { ……

p(mutex)； ……

x:=x-1；

v(mutex)；

……

} p2() { ……

p(mutex)； ……

x:=x-1；

v(mutex)；

……

} 互斥問題舉例3某車站售票廳有20個窗口，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在廳外等待。若把一個購票者看作一個進程，請用P、V操作管理這些并發(fā)進程，要求如下：⑴．在主函數(shù)中給出信號量的定義和初值。⑵．給出一個購票者進程的算法。⑶．給出當購票者最多不超過n(設n>20)個時，信號量可能的變化范圍。18分析共享臨界資源：20個同類的售票窗口先來者先進入⑴．主函數(shù)算法：main(){ intmutex=20; cobegin P1();…

Pi();…

Pn(); coend}⑵．購票者i的算法：Pi(){ P(mutex);

購票；

V(mutex);}算法描述⑶．信號量mutex的取值范圍：

－(n－20)≤mutex≤20其物理含義是：當mutex=20時，表示售票廳內(nèi)沒有購票者進入，20個窗口都是空閑的，表示可用資源個數(shù)；當mutex=0時，表示售票廳內(nèi)已經(jīng)進入了20個購票者，每個窗口都被分配，沒有等待的購票者，可用資源為0；當mutex=－(n－20)時，表示一共有n個購票者，其中20個購票者已經(jīng)進入廳內(nèi)，分別占有一個窗口，還有n－20個購票者在廳外等待，絕對值表示等待進程個數(shù)。結(jié)論：當mutex≥0時其值表示可用資源個數(shù)；當mutex＜0時其絕對值表示等待進程的個數(shù)。22思考：n個并發(fā)進程，共享m個共享資源：mutex的取值范圍為？答同一類資源：m-n

≤mutex≤m不同類資源：需要m個mutex1-n

≤mutex≤1同步進程舉例直接制約同步定義私用信號量PV原語實現(xiàn)進程同步生產(chǎn)者－消費者問題哲學家進餐問題241.同步進程舉例1-病人就診門診醫(yī)生：

……

開化驗單；

……

等化驗結(jié)果；

……

繼續(xù)診??；化驗員：

……

等化驗單；

……

化驗；填寫化驗結(jié)果；

……

等待等待喚醒后喚醒后化驗單化驗結(jié)果繼續(xù)診病27對于醫(yī)生的操作步驟：有病人時：開化驗單（化驗單多一個）等待化驗結(jié)果（有化驗結(jié)果）繼續(xù)診病28對于化驗員的操作步驟：等化驗單（有化驗單時）進行化驗

（未化驗的化驗單少一個）出化驗結(jié)果（化驗結(jié)果多一個）等待下一化驗單需要兩個信號量s1:表示化驗結(jié)果是否出來,初值為0.s2：表示醫(yī)生是否開化驗單，初值為0.程序描述

main(){ints1

=0；

ints2

=1；

cobegindoctor()；test()；

coend}31對于化驗員的操作步驟：test{ wait(化驗單);

化驗… 出化驗結(jié)果… signal(有化驗結(jié)果);}32對于醫(yī)生的操作步驟：doctor{

給病人看病… signal(化驗單); wait(化驗結(jié)果);

繼續(xù)診病…}信號燈的PV操作voidwait(semaphores){s.value=s.value-1;if(s.value<0)block(s.queue);/*將進程阻塞，并將其投入等待隊列s.queue*/}P操作信號燈的PV操作voidsignal(semaphores){s.value=s.value+1;if(s.value<=0)wackup(s.queue);/*喚醒阻塞進程，將其從等待隊列s.queue取出，投入就緒隊列*/}V操作35對于化驗員的操作步驟：test{ P(s2);

化驗…

出化驗結(jié)果… V(s1);}36對于醫(yī)生的操作步驟：doctor{

給病人看病… V(s2); P(s1);

繼續(xù)診病…}37同步進程舉例2PcPpbuffer38利用過程wait和signal可簡單地描述計算進程Pc和打印進程Pp的同步關系：設消息名bufempty表示buf空，消息名buffull表示buf中裝滿了數(shù)據(jù)。bufempty=true，buffull=false39描述：Pc: A:wait(bufempty)

計算

buf計算結(jié)果

bufemptyfalse

signal(buffull) GotoAPp: B:wait(buffull)

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

buffullfalse

signal(bufempty) GotoBwait等待合作進程發(fā)來的消息signal向合作進程發(fā)送消息40main(){ intbufempty=1,buffull=0; cobegin Pc(); Pp(); coend}41描述：Pc: A:P(bufempty)

計算

buf計算結(jié)果

V(buffull) GotoAPp: B:P(buffull)

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

V(bufempty) GotoB返回42直接制約一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程稱為并發(fā)進程間的直接制約。返回43同步的定義異步環(huán)境下，一組并發(fā)進程，因直接制約而互相發(fā)送消息而進行相互合作，互相等待，使得各進程按一定的速度執(zhí)行的過程稱為進程間同步。返回44合作進程：具有同步關系的一組并發(fā)進程稱為合作進程。消息：合作進程間互相發(fā)送的信號稱為消息或事件。返回45私用信號量把進程間發(fā)送的消息看作信號量，則這種信號量只與制約進程及被制約進程有關而不是整組并發(fā)進程有關(如進程互斥)，稱這種信號量為私用信號量。返回互斥時使用的是公用信號量46用P,V原語操作實現(xiàn)同步用P,V原語操作實現(xiàn)進程同步的方法：為各并發(fā)進程設置私用信號量為私用信號量賦初值利用P,V原語和私用信號量規(guī)定各進程的執(zhí)行順序。返回●生產(chǎn)者——消費者問題●讀者——寫者問題●哲學家進餐問題●打磕睡的理發(fā)師問題●3.2經(jīng)典進程同步問題48生產(chǎn)者-消費問題消費者：系統(tǒng)中使用某一類資源的進程稱為該資源的消費者。生產(chǎn)者：釋放同類資源的進程稱為該資源的生產(chǎn)者。計算進程和打印進程共享緩沖區(qū)的例子中，計算進程把數(shù)據(jù)送入緩沖區(qū)，打印進程從緩沖區(qū)中取數(shù)據(jù)，則計算進程可看作數(shù)據(jù)資源的生產(chǎn)者，打印進程可看作是消費者。4950它們之間滿足：消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的；生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的。生產(chǎn)者-消費者問題是同步關系51當有進程在寫數(shù)據(jù)時（如生產(chǎn)者進程）則同時不允許對該緩沖區(qū)進行讀操作（如消費者進程）。故有界緩沖區(qū)是臨界資源，進程必須互斥訪問。生產(chǎn)者-消費者問題同時也具有互斥關系52設信號量mutex：用于訪問緩沖區(qū)時的互斥，初值是1empty：為生產(chǎn)者進程的私用信號量，表示有界緩沖區(qū)中的空單元數(shù)，初值為n；full：為消費者進程的私用信號量，表示緩沖區(qū)中非空單元數(shù)，初值為0。empty+full=n53consumer(data):begin P(full) P(mutex)

取緩沖區(qū)某單元數(shù)據(jù) V(mutex)

V(empty)endproducer(data):begin P(empty) P(mutex)

送數(shù)據(jù)入緩沖區(qū)某單元 V(mutex)

V(full)end每個進程中各個P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥――否則可能死鎖！分析：P操作的順序----很重要P操作的順序不當會產(chǎn)生死鎖。例：假定執(zhí)行順序如下Consumer：Producer：P(empty);P(mutex);

oneunit-->buf;V(mutex);V(full);P(full);P(mutex);//進入?yún)^(qū)

oneunit<--buf;V(mutex);V(empty);//退出區(qū)分析：當full=0,mutex=1時，執(zhí)行順序：

Consumer.P(mutex);Consumer.P(full);mutex=0

//C阻塞，等待Producer發(fā)出的full信號

Producer.P(empty);Producer.P(mutex);

//P阻塞，等待Consumer發(fā)出的empty信號思考：還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎？發(fā)生死鎖生產(chǎn)者-消費者問題●指有兩組進程共享一個環(huán)形的緩沖池。一組進程被稱為生產(chǎn)者，另一組進程被稱為消費者?！窬彌_池是由若干個大小相等的緩沖區(qū)組成的，每個緩沖區(qū)可以容納一個產(chǎn)品?！裆a(chǎn)者進程不斷地將生產(chǎn)的產(chǎn)品放入緩沖池，消費者進程不斷地將產(chǎn)品從緩沖池中取出。用信號量解決“生產(chǎn)者-消費者”問題voidconsumer()//消費者進程{while(true){P(full);P(mutex);data_c=buffer[j];j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c;}}semaphoremutex=1;

semaphoreempty=n;

semaphorefull=0;inti,j;

ITEMbuffer[n];

ITEMdata_p,data_c;

voidproducer()//生產(chǎn)者進程{while(true){produceanitemindata_p;P(empty);P(mutex);buffer[i]=data_p;i=(i+1)%n;V(mutex);V(full);}}讀者-寫者問題●一個數(shù)據(jù)對象若被多個并發(fā)進程所共享，且其中一些進程只要求讀該數(shù)據(jù)對象的內(nèi)容，而另一些進程則要求寫操作，對此，我們把只想讀的進程稱為“讀者”，而把要求寫的進程稱為“寫者”。

●問題描述：●讀者可同時讀；●讀者讀時，寫者不可寫；●寫者寫時，其他的讀者、寫者均不可進入。

讀者進程： while(true) {

‘有人要讀’P(Wmutex); 讀;

‘無人讀了’

V(Wmutex); }寫者進程：while(true){

P(Wmutex); 寫;

V(Wmutex);

}

semaphoreWmutex=1;用信號量解決讀者-寫者問題voidreader()/*讀者進程*/{while(true){P(Rmutex);

if(Rcount==0)P(Wmutex);

Rcount=Rcount+1; V(Rmutex); read;/*執(zhí)行讀操作*/

P(Rmutex); Rcount=Rcount-1; if(Rcount==0)V(Wmutex); V(Rmutex);}}SemaphoreWmutex,Rmutex=1,1;intRcount;用信號量解決讀者-寫者問題voidwriter()/*寫者進程*/{while(true){P(Wmutex); write;/*執(zhí)行寫操作*/V(Wmutex);}}60哲學家進餐問題問題描述：有五個哲學家共用一張圓桌，分別坐在周圍的五張椅子上，圓桌上有五個碗和五只筷子，每兩個哲學家之間放一支哲學家的動作包括思考和進餐進餐時需要同時拿起他左邊和右邊的兩支筷子;思考時則同時將兩支筷子放回原處哲學家進餐問題61(thediningphilosophersproblem)條件：只有在拿到兩只筷子時才能進餐；如果筷子已在他人手上，必須等于其他哲學家進餐完畢才能拿到筷子；任一哲學家在拿到兩只筷子吃飯前，決不放下手中的筷子。哲學家進餐問題3/662問題：描述一個保證不會出現(xiàn)兩個鄰座同時要求吃飯的通信算法。描述一個既沒有兩鄰座同時吃飯，又沒有人永遠拿不到筷子的算法。在什么情況下，5個哲學家全部吃不上飯？⑴設5個信號量c[1]～c[5]，初值均為1，分別表示第i號筷子被拿(i=1,2,3,4,5)。eat(i):第i個哲學家要吃飯begin P(c[i]); P(c[i+1mod5]); eating; V(c[i]); V(c[i+1mod5]);end注：這個過程能保證兩鄰座不同時吃飯，但會出現(xiàn)5個哲學家一人（左手）拿一只筷子，誰也吃不到飯的死鎖情況。⑵解決的思路如下：讓奇數(shù)號哲學家先取右手的筷子，讓偶數(shù)號哲學家先取左手的筷子。這樣就防止相鄰座位的哲學家同時拿筷子的可能。除非某位哲學家一直吃下去，否則不會有人會餓死。eat(i):begin if(imod2==0) then { P(c[i]); P(c[i+1mod5]); eating; V(c[i]); V(c[i+1mod5]); } else { P(c[i+1mod5]); P(c[i]); eating; V(c[i+1mod5]); V(c[i]); }end哲學家進餐問題●五個哲學家，他們的生活方式是交替地思考和進餐?！裾軐W家們共用一張圓桌，圍繞著圓桌而坐，在圓桌上有五個碗和五支筷子，平時哲學家進行思考，饑餓時拿起其左、右的兩支筷子，試圖進餐，進餐完畢又進行思考?！襁@里的問題是哲學家只有拿到靠近他的兩支筷