第3章進程同步及通信-同步

1、第第3 3章章 進程同步與通信進程同步與通信進程同步與互斥進程同步與互斥 經(jīng)典進程同步問題經(jīng)典進程同步問題 管程管程 AND信號量信號量 進程通信進程通信 進程同步的基本概念進程同步的基本概念同步：同步：指多個進程中發(fā)生的事件存在著某種時指多個進程中發(fā)生的事件存在著某種時序關(guān)系，它們必須按規(guī)定時序執(zhí)行，以共同完成序關(guān)系，它們必須按規(guī)定時序執(zhí)行，以共同完成一項任務(wù)一項任務(wù) ?；コ猓憾鄠€進程不能同時使用同一資源?；コ猓憾鄠€進程不能同時使用同一資源。臨界資源：某段時間內(nèi)僅允許一個進程使用的臨界資源：某段時間內(nèi)僅允許一個進程使用的資源。資源。臨界區(qū)：每個進程中訪問臨界資源的那段代碼。臨界區(qū)：每個進程中

2、訪問臨界資源的那段代碼。3信號量信號量(semaphore)(semaphore)管理相應(yīng)臨界區(qū)的公有資源，它代管理相應(yīng)臨界區(qū)的公有資源，它代表可用資源實體。表可用資源實體。4信號量是一個整型變量。信號量是一個整型變量。0 0：可供并發(fā)進程使用的資源實體數(shù)：可供并發(fā)進程使用的資源實體數(shù)0 0：正在等待使用臨界區(qū)的進程數(shù)：正在等待使用臨界區(qū)的進程數(shù)用于互斥的信號量初值應(yīng)該大于零用于互斥的信號量初值應(yīng)該大于零5信號燈的信號燈的PV操作操作void wait(semaphore s) s.value = s.value - 1; if (s.value 0) block(s.queue); /* 將

3、進程阻塞，并將其投入等待隊列將進程阻塞，并將其投入等待隊列s.queue */P操作操作7信號燈的信號燈的PV操作操作void signal(semaphore s) s.value = s.value + 1; if (s.value = 0) wackup(s.queue); /* 喚醒阻塞進程，將其從等待隊列喚醒阻塞進程，將其從等待隊列s.queue 取出，投入就緒隊列取出，投入就緒隊列*/V操作操作用信號燈解決互斥問題用信號燈解決互斥問題semaphore mutex=1;P1: while (1)P(mutex);臨界區(qū)臨界區(qū);V(mutex);剩余區(qū)剩余區(qū); ; P2: while

4、 (1)P(mutex);臨界區(qū)臨界區(qū)V(mutex);剩余區(qū)剩余區(qū); ;10互斥進程舉例互斥進程舉例1 1兩個進程共享一臺打印機兩個進程共享一臺打印機設(shè)信號量設(shè)信號量printprint代表打印機，初值為代表打印機，初值為1.1.int main(void)int main(void) int print=1;int print=1;cobegincobeginpa(); pb();pa(); pb();coendcoend pa()pa() P(print);P(print);使用打印機使用打印機V(print);V(print); pb()pb() P(print);P(print);使

5、用打印機使用打印機V(print);V(print); 11信號量可能的取值范圍信號量可能的取值范圍假設(shè)有假設(shè)有N N個并發(fā)進程個并發(fā)進程共用共用一臺一臺打印機打印機，設(shè)互斥信號量，設(shè)互斥信號量mutexmutex的初值為的初值為1 1，則，則：J信號量信號量mutexmutex代表什么？代表什么？Jmutexmutex的取值范圍為多少？的取值范圍為多少？Jmutexmutex的值分別代表什么含義？的值分別代表什么含義？12N N個并發(fā)進程，互斥信號量個并發(fā)進程，互斥信號量mutexmutex的的初值為初值為1 1：mutexmutex的取值范圍為：的取值范圍為：1 1-(N-1)-(N-1)

6、1 1：表示沒有進程進入臨界區(qū)。有一個資源，無：表示沒有進程進入臨界區(qū)。有一個資源，無進程等待；進程等待；0 0：表示有：表示有1 1個進程進入臨界區(qū)。無資源，無進程個進程進入臨界區(qū)。無資源，無進程等待；等待；-i -i：表示：表示1 1個進程進入臨界區(qū)。無資源，且有個進程進入臨界區(qū)。無資源，且有i i (i=N-1)(i0（有票嗎）？（有票嗎）？如果有，如果有， XN（票夠嗎）？（票夠嗎）？如果夠，則出票（打印票據(jù)）；如果夠，則出票（打印票據(jù)）；XXN（修改剩余票數(shù)）；（修改剩余票數(shù)）；將將X回寫到數(shù)據(jù)庫中；回寫到數(shù)據(jù)庫中；141516某車站售票廳有某車站售票廳有20個窗口，任何時刻最多可容

7、個窗口，任何時刻最多可容納納20名購票者進入，當(dāng)售票廳中少于名購票者進入，當(dāng)售票廳中少于20名購票名購票者時，則廳外的購票者可立即進入，否則需在者時，則廳外的購票者可立即進入，否則需在廳外等待。若把一個購票者看作一個進程，請廳外等待。若把一個購票者看作一個進程，請用用P、V操作管理這些并發(fā)進程，要求如下：操作管理這些并發(fā)進程，要求如下：在主函數(shù)中給出信號量的定義和初值。在主函數(shù)中給出信號量的定義和初值。給出一個購票者進程的算法。給出一個購票者進程的算法。給出當(dāng)購票者最多不超過給出當(dāng)購票者最多不超過n (設(shè)設(shè)n20)個時，個時，信號量可能的變化范圍。信號量可能的變化范圍。18分析分析n共享臨界資

8、源：共享臨界資源：20個同類的售票窗口個同類的售票窗口n先來者先進入先來者先進入主函數(shù)算法：主函數(shù)算法：main()int mutex=20;cobeginP1(); Pi();Pn();coend購票者購票者i的算法：的算法：Pi()P(mutex);購票；購票；V(mutex); 信號量信號量mutex的的取值范圍取值范圍： (n20) mutex 20其其物理含義物理含義是：是：當(dāng)當(dāng)mutex=20時，表示售票廳內(nèi)沒有購票者進入，時，表示售票廳內(nèi)沒有購票者進入，20個窗口都是個窗口都是空閑的，表示可用資源個數(shù)；空閑的，表示可用資源個數(shù)；當(dāng)當(dāng)mutex=0時，表示售票廳內(nèi)已經(jīng)進入了時，表示

9、售票廳內(nèi)已經(jīng)進入了20個購票者，每個窗口個購票者，每個窗口都被分配，沒有等待的購票者，可用資源為都被分配，沒有等待的購票者，可用資源為0；當(dāng)當(dāng)mutex=(n20)時，表示一共有時，表示一共有n個購票者，其中個購票者，其中20個購票者個購票者已經(jīng)進入廳內(nèi)，分別占有一個窗口，還有已經(jīng)進入廳內(nèi)，分別占有一個窗口，還有n20個購票者在廳個購票者在廳外等待，絕對值表示等待進程個數(shù)。外等待，絕對值表示等待進程個數(shù)。結(jié)論結(jié)論：當(dāng)當(dāng)mutex0時其值表示可用資源個數(shù)；時其值表示可用資源個數(shù)；當(dāng)當(dāng)mutex0時其絕對值表示等待進程的個數(shù)。時其絕對值表示等待進程的個數(shù)。22思考：思考：n n個并發(fā)進程，共享個并

10、發(fā)進程，共享mm個共享資源：個共享資源：mutexmutex的取值范圍為？的取值范圍為？答n同一類資源：同一類資源： m-n mutex mn不同類資源：不同類資源： 需要需要m個個mutex 1-n mutex 1同步進程舉例同步進程舉例直接制約直接制約同步定義同步定義私用信號量私用信號量PV原語實現(xiàn)進程同步原語實現(xiàn)進程同步生產(chǎn)者消費者問題生產(chǎn)者消費者問題哲學(xué)家進餐問題哲學(xué)家進餐問題24門診醫(yī)生：門診醫(yī)生： 開開化驗單；化驗單； 等等化驗結(jié)果；化驗結(jié)果； 繼續(xù)診??；繼續(xù)診?。换瀱T：化驗員： 等等化驗單；化驗單； 化驗；化驗； 填寫化驗結(jié)果；填寫化驗結(jié)果； 等等待待等等待待喚喚醒醒后后喚喚醒

11、醒后后繼續(xù)診病繼續(xù)診病2728n需要兩個信號量需要兩個信號量ns1: 表示化驗結(jié)果是否出來表示化驗結(jié)果是否出來,初值為初值為0.ns2：表示醫(yī)生是否開化驗單，初值為：表示醫(yī)生是否開化驗單，初值為0.程序描述程序描述main( ) int s1 =0； int s2 =1； cobegin doctor( )；test( )； coend3132信號燈的信號燈的PV操作操作void wait(semaphore s) s.value = s.value - 1; if (s.value 0) block(s.queue); /* 將進程阻塞，并將其投入等待隊列將進程阻塞，并將其投入等待隊列s.q

12、ueue */P操作操作信號燈的信號燈的PV操作操作void signal(semaphore s) s.value = s.value + 1; if (s.value buf;one unit-buf;V(mutex);V(mutex);V(full);V(full);P(full);P(full);P(mutex);P(mutex);/進入?yún)^(qū)進入?yún)^(qū) one unit-buf;one unit-buf;V(mutex);V(mutex);V(empty);V(empty);/退出區(qū)退出區(qū)分析：分析：當(dāng)當(dāng)full=0, mutex = 1full=0, mutex = 1時，執(zhí)行順序：時，執(zhí)

13、行順序： / C / C阻塞，等待阻塞，等待Producer Producer 發(fā)出的發(fā)出的fullfull信號信號 / P / P 阻塞，等待阻塞，等待ConsumerConsumer發(fā)出的發(fā)出的emptyempty信號信號生產(chǎn)者生產(chǎn)者-消費者消費者問題ji滿空指有兩組進程共享一個環(huán)形的緩沖池。一組進程被稱為指有兩組進程共享一個環(huán)形的緩沖池。一組進程被稱為生產(chǎn)者，另一組進程被稱為消費者。生產(chǎn)者，另一組進程被稱為消費者。緩沖池是由若干個大小相等的緩沖區(qū)組成的，每個緩沖緩沖池是由若干個大小相等的緩沖區(qū)組成的，每個緩沖區(qū)可以容納一個產(chǎn)品。區(qū)可以容納一個產(chǎn)品。生產(chǎn)者進程不斷地將生產(chǎn)的產(chǎn)品放入緩沖池，

14、消費者進生產(chǎn)者進程不斷地將生產(chǎn)的產(chǎn)品放入緩沖池，消費者進程不斷地將產(chǎn)品從緩沖池中取出。程不斷地將產(chǎn)品從緩沖池中取出。 用信號量解決用信號量解決“生產(chǎn)者生產(chǎn)者-消費者消費者”問問題題void consumer()/消費者進程消費者進程while (true) P(full); P(mutex); data_c = bufferj; j = (j + 1) % n; V(mutex); V(empty); consume the item in data_c; semaphore mutex =1; semaphore empty = n;semaphore full = 0;int i,j;IT

15、EM buffern;ITEM data_p, data_c; void producer() /生產(chǎn)者進程生產(chǎn)者進程 while (true) produce an item in data_p; P(empty); P(mutex); bufferi = data_p; i = (i + 1) % n; V(mutex); V(full); 讀者讀者-寫者問題寫者問題一個數(shù)據(jù)對象若被多個并發(fā)進程所共享，一個數(shù)據(jù)對象若被多個并發(fā)進程所共享，且其中一些進程只要求讀該數(shù)據(jù)對象的內(nèi)且其中一些進程只要求讀該數(shù)據(jù)對象的內(nèi)容，而另一些進程則要求寫操作，對此，容，而另一些進程則要求寫操作，對此，我們把只想

16、讀的進程稱為我們把只想讀的進程稱為“讀者讀者”，而把，而把要求寫的進程稱為要求寫的進程稱為“寫者寫者”。 問題描述：問題描述：讀者可同時讀；讀者可同時讀；讀者讀時，寫者不可寫；讀者讀時，寫者不可寫；寫者寫時，其他的讀者、寫者均不可寫者寫時，其他的讀者、寫者均不可進入。進入。讀者進程：讀者進程：while(true) 有人要讀有人要讀 P(Wmutex); 讀讀; 無人讀了無人讀了 V(Wmutex);寫者進程：寫者進程：while(true) P(Wmutex);寫寫;V(Wmutex); semaphore Wmutex=1;用信號量用信號量解決讀者讀者-寫者寫者問題void reader(

17、) /*讀者進程讀者進程*/while (true) P(Rmutex); if (Rcount = 0) P(Wmutex); Rcount = Rcount + 1; V(Rmutex);read; /* 執(zhí)行讀操作執(zhí)行讀操作 */P(Rmutex); Rcount = Rcount - 1; if (Rcount = 0) V(Wmutex); V(Rmutex); Semaphore Wmutex,Rmutex=1,1; int Rcount;用信號量用信號量解決讀者讀者-寫者寫者問題void writer() /*寫者進程寫者進程*/while (true) P(Wmutex);wr

18、ite; /* 執(zhí)行寫操作執(zhí)行寫操作 */V(Wmutex); 60哲學(xué)家進餐問題哲學(xué)家進餐問題問題描述問題描述：v有有五個哲學(xué)家五個哲學(xué)家共用一張圓桌，分別坐在周圍的五張椅子上，共用一張圓桌，分別坐在周圍的五張椅子上，v圓桌上有五個碗和圓桌上有五個碗和五只筷子五只筷子，每兩個哲學(xué)家之間放一支，每兩個哲學(xué)家之間放一支v哲學(xué)家的動作包括哲學(xué)家的動作包括思考思考和和進餐進餐v進餐進餐時需要同時拿起他左邊和右邊的兩支筷子時需要同時拿起他左邊和右邊的兩支筷子; ;v思考思考時則同時將兩支筷子放回原處時則同時將兩支筷子放回原處哲學(xué)家進餐問題61(the dining philosophers probl

19、em)(the dining philosophers problem)條件條件：v 只有在拿到兩只筷子時才能進餐；只有在拿到兩只筷子時才能進餐；v 如果筷子已在他人手上，必須等于其他哲學(xué)家進餐如果筷子已在他人手上，必須等于其他哲學(xué)家進餐完畢才能拿到筷子；完畢才能拿到筷子；v 任一哲學(xué)家在拿到兩只筷子吃飯前，決不放下手中任一哲學(xué)家在拿到兩只筷子吃飯前，決不放下手中的筷子。的筷子。哲學(xué)家進餐問題 3/662問題問題：描述一個保證不會出現(xiàn)兩個鄰座同時要求吃飯的描述一個保證不會出現(xiàn)兩個鄰座同時要求吃飯的通信算法。通信算法。描述一個既沒有兩鄰座同時吃飯，又沒有人永遠(yuǎn)描述一個既沒有兩鄰座同時吃飯，又沒有

20、人永遠(yuǎn)拿不到筷子的算法。拿不到筷子的算法。 在什么情況下，在什么情況下，5 5個哲學(xué)家全部吃不上飯？個哲學(xué)家全部吃不上飯？設(shè)設(shè)5個信號量個信號量c1c5，初值均為，初值均為1，分別表示第，分別表示第i號筷子被拿號筷子被拿(i=1,2,3,4,5)。eat(i): 第第i個哲學(xué)家要吃飯個哲學(xué)家要吃飯beginP(ci);P(ci+1 mod 5);eating;V(ci);V(ci+1 mod 5);end注：注：這個過程能保證兩鄰座不同時吃飯，但這個過程能保證兩鄰座不同時吃飯，但會出現(xiàn)會出現(xiàn)5個哲學(xué)家一人（左手）拿一只筷子，個哲學(xué)家一人（左手）拿一只筷子，誰也吃不到飯的死鎖情況。誰也吃不到飯的

21、死鎖情況。解決的思路如下：解決的思路如下：讓奇數(shù)號哲學(xué)家先取右手的筷子，讓偶數(shù)號哲學(xué)讓奇數(shù)號哲學(xué)家先取右手的筷子，讓偶數(shù)號哲學(xué)家先取左手的筷子。這樣就防止相鄰座位的哲學(xué)家先取左手的筷子。這樣就防止相鄰座位的哲學(xué)家同時拿筷子的可能。除非某位哲學(xué)家一直吃下家同時拿筷子的可能。除非某位哲學(xué)家一直吃下去，否則不會有人會餓死。去，否則不會有人會餓死。eat(i):beginif (i mod 2 = 0)thenP(ci);P(ci+1 mod 5);eating;V(ci);V(ci+1 mod 5);elseP(ci+1 mod 5);P(ci);eating;V(ci+1 mod 5);V(ci)

22、;end哲學(xué)家進餐哲學(xué)家進餐問題五個哲學(xué)家，他們的生活方式是交替地思考和五個哲學(xué)家，他們的生活方式是交替地思考和進餐進餐。哲學(xué)家們共用一張圓桌，圍繞著圓桌而坐，在哲學(xué)家們共用一張圓桌，圍繞著圓桌而坐，在圓桌上有五個碗和五支筷子，平時哲學(xué)家進行思圓桌上有五個碗和五支筷子，平時哲學(xué)家進行思考，饑餓時拿起其左、右的兩支筷子，試圖進餐，考，饑餓時拿起其左、右的兩支筷子，試圖進餐，進餐完畢又進行思考。進餐完畢又進行思考。這里的這里的問題是問題是哲學(xué)家只有拿到靠近他的兩支筷哲學(xué)家只有拿到靠近他的兩支筷子才能進餐，而拿到兩支筷子的條件是他的左、子才能進餐，而拿到兩支筷子的條件是他的左、右鄰居此時都沒有進餐。

23、右鄰居此時都沒有進餐。semaphore chopstick5 =1,1,1,1,1;void philosopher (int i ) /*哲學(xué)家進程哲學(xué)家進程*/while (true) P(chopsticki); P(chopstick(i + 1) % 5); eating; /* 進餐進餐 */ V(chopsticki); V(chopstick(i + 1) % 5); thinking; /* 思考思考 */用信號量用信號量解決哲學(xué)家進餐哲學(xué)家進餐問題哲學(xué)家能順利地吃到飯嗎哲學(xué)家能順利地吃到飯嗎打磕睡的理發(fā)師問題打磕睡的理發(fā)師問題 理發(fā)店有一名理發(fā)師，一把理發(fā)椅，還有理發(fā)店有一名理