第3章 進(jìn)程同步與通信同步

第3章進(jìn)程同步與通信●進(jìn)程同步與互斥

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

●管程

●AND信號(hào)量

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

semaphoremutex=1;

P1:

while(1){

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

V(mutex);

剩余區(qū);

};

P2: while(1){

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

V(mutex);

剩余區(qū);

};10互斥進(jìn)程舉例1－兩個(gè)進(jìn)程共享一臺(tái)打印機(jī)設(shè)信號(hào)量print代表打印機(jī)，初值為1.intmain(void){ intprint=1; cobegin pa();pb(); coend}pa(){ P(print);

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

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

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

p(mutex)； ……

x:=x-1；

v(mutex)；

……

} p2() { ……

p(mutex)； ……

x:=x-1；

v(mutex)；

……

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

Pi();…

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

購(gòu)票；

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

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

≤mutex≤m不同類資源：需要m個(gè)mutex1-n

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

……

開化驗(yàn)單；

……

等化驗(yàn)結(jié)果；

……

繼續(xù)診病；化驗(yàn)員：

……

等化驗(yàn)單；

……

化驗(yàn)；填寫化驗(yàn)結(jié)果；

……

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

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

main(){ints1

=0；

ints2

=1；

cobegindoctor()；test()；

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

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

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

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

化驗(yàn)…

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

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

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

計(jì)算

buf計(jì)算結(jié)果

bufemptyfalse

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

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

buffullfalse

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

計(jì)算

buf計(jì)算結(jié)果

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

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

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

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

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

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

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

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

//P阻塞，等待Consumer發(fā)出的empty信號(hào)思考：還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎？發(fā)生死鎖生產(chǎn)者-消費(fèi)者問題●指有兩組進(jìn)程共享一個(gè)環(huán)形的緩沖池。一組進(jìn)程被稱為生產(chǎn)者，另一組進(jìn)程被稱為消費(fèi)者?！窬彌_池是由若干個(gè)大小相等的緩沖區(qū)組成的，每個(gè)緩沖區(qū)可以容納一個(gè)產(chǎn)品?！裆a(chǎn)者進(jìn)程不斷地將生產(chǎn)的產(chǎn)品放入緩沖池，消費(fèi)者進(jìn)程不斷地將產(chǎn)品從緩沖池中取出。用信號(hào)量解決“生產(chǎn)者-消費(fèi)者”問題voidconsumer()//消費(fèi)者進(jìn)程{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)者進(jìn)程{while(true){produceanitemindata_p;P(empty);P(mutex);buffer[i]=data_p;i=(i+1)%n;V(mutex);V(full);}}讀者-寫者問題●一個(gè)數(shù)據(jù)對(duì)象若被多個(gè)并發(fā)進(jìn)程所共享，且其中一些進(jìn)程只要求讀該數(shù)據(jù)對(duì)象的內(nèi)容，而另一些進(jìn)程則要求寫操作，對(duì)此，我們把只想讀的進(jìn)程稱為“讀者”，而把要求寫的進(jìn)程稱為“寫者”。

●問題描述：●讀者可同時(shí)讀；●讀者讀時(shí)，寫者不可寫；●寫者寫時(shí)，其他的讀者、寫者均不可進(jìn)入。

讀者進(jìn)程： while(true) {

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

‘無人讀了’

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

P(Wmutex); 寫;

V(Wmutex);

}

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