Chapter進(jìn)程同步與互斥應(yīng)用例子解析實(shí)用實(shí)用教案

1、進(jìn)程(jnchng)互斥進(jìn)程互斥：并發(fā)進(jìn)程之間相互競爭臨界資源的排他性關(guān)系。解題步驟：確定臨界資源及個(gè)數(shù)；確定進(jìn)程的關(guān)鍵工作步（使用臨界資源的）；確定信號(hào)量的初值(臨界資源的個(gè)數(shù))；寫出偽代碼。使用P(wait)操作和V(signal)操作對進(jìn)程互斥進(jìn)行(jnxng)控制。第1頁/共29頁第一頁，共30頁。例1：過獨(dú)木橋。進(jìn)程進(jìn)程(jnchng)(jnchng)的互斥的互斥P1 P2 由西向東過獨(dú)木橋； 由東向西過獨(dú)木橋； P1P2第2頁/共29頁第二頁，共30頁。分析：進(jìn)程P1、P2因競爭獨(dú)木橋這個(gè)資源而成為互斥關(guān)系(gun x)。設(shè)：信號(hào)量m表示獨(dú)木橋資源，初值為1表示資源可用。 int

2、m=1; cobegin p1() / p2() coend進(jìn)程進(jìn)程(jnchng)(jnchng)的互斥的互斥第3頁/共29頁第三頁，共30頁。練習(xí)(linx)：過十字路口（單道）。進(jìn)程進(jìn)程(jnchng)(jnchng)的互斥的互斥P1 P2 P3 P4 通過(tnggu)路口； 通過(tnggu)路口； 通過(tnggu)路口； 通過(tnggu)路口； P2P3P4P1第4頁/共29頁第四頁，共30頁。分析：進(jìn)程P1、P2、P3、P4因競爭(jngzhng)十字路口這個(gè)資源而成為互斥關(guān)系。設(shè)：信號(hào)量m表示十字路口資源，初值為1表示資源可用。 int m=1; cobegin p1()

3、/ p2() /p3() / p4() coend進(jìn)程進(jìn)程(jnchng)(jnchng)的互斥的互斥第5頁/共29頁第五頁，共30頁。 有一個(gè)閱覽室，共有有一個(gè)閱覽室，共有100100個(gè)座位。讀者進(jìn)入閱覽個(gè)座位。讀者進(jìn)入閱覽室時(shí)必須在入口處進(jìn)行登記；離開閱覽室時(shí)必須室時(shí)必須在入口處進(jìn)行登記；離開閱覽室時(shí)必須進(jìn)行注銷。試用進(jìn)行注銷。試用PVPV操作描述操作描述(mio sh)(mio sh)讀者進(jìn)讀者進(jìn)入入/ /離開閱覽室的同步與互斥關(guān)系。離開閱覽室的同步與互斥關(guān)系。 ReaderReader進(jìn)程進(jìn)程 登記登記 進(jìn)入閱覽室進(jìn)入閱覽室 讀書讀書 離開閱覽室離開閱覽室 注銷注銷 進(jìn)程進(jìn)程(jnch

4、ng)(jnchng)的互斥的互斥第6頁/共29頁第六頁，共30頁。 分析：分析：在入口和出口處讀者應(yīng)該在入口和出口處讀者應(yīng)該(ynggi)(ynggi)互斥進(jìn)互斥進(jìn)行登記和注銷，行登記和注銷， 100 100個(gè)座位，個(gè)座位，100100個(gè)互斥資源個(gè)互斥資源 設(shè)置信號(hào)量設(shè)置信號(hào)量 教室內(nèi)空座位數(shù)量，教室內(nèi)空座位數(shù)量，seatseat，初值，初值100100 為入口處進(jìn)行登記設(shè)置互斥信號(hào)量為入口處進(jìn)行登記設(shè)置互斥信號(hào)量SinSin，初值，初值 1 1，表示當(dāng)前可用表示當(dāng)前可用 為出口處進(jìn)行注銷設(shè)置互斥信號(hào)量為出口處進(jìn)行注銷設(shè)置互斥信號(hào)量SoutSout，初值，初值 1 1，表示當(dāng)前可用表示當(dāng)前可

5、用第7頁/共29頁第七頁，共30頁。begin Sin, Sout, seat：semaphore; seat :=100; Sin := 1; Sout := 1;cobeginprocess Reader-i ( i = 1,2,n );beginP(seat);P(Sin);登記;V(Sin);進(jìn)入閱覽室;讀書(d sh);離開閱覽室;P(Sout);注銷;V(Sout);V（seat）;endcoend;end;第8頁/共29頁第八頁，共30頁。問題(wnt) 若有一售票廳只能容納300人，當(dāng)少于300人時(shí)，可以進(jìn)入。否則(fuz)，需在外等候，若將每一個(gè)購票者作為一個(gè)進(jìn)程，請用P、V

6、操作編程。第9頁/共29頁第九頁，共30頁。例2：讀寫數(shù)據(jù)庫。某數(shù)據(jù)庫有一個(gè)寫進(jìn)程(jnchng)、多個(gè)讀進(jìn)程(jnchng)，它們之間讀、寫操作的互斥要求是：寫進(jìn)程(jnchng)運(yùn)行時(shí)，其他讀、寫進(jìn)程(jnchng)不能對數(shù)據(jù)庫進(jìn)行操作。讀進(jìn)程(jnchng)之間不互斥，可以同時(shí)讀數(shù)據(jù)庫。請用信號(hào)量及PV操作描述這一組進(jìn)程(jnchng)的工作過程。（讀者-寫者問題） 進(jìn)程進(jìn)程(jnchng)(jnchng)的互斥的互斥數(shù)據(jù)庫寫者讀者寫者 讀者(dzh) 寫數(shù)據(jù)庫； 讀數(shù)據(jù)庫； 第10頁/共29頁第十頁，共30頁。分析：寫進(jìn)程writer、讀進(jìn)程reader因競爭數(shù)據(jù)庫這個(gè)資源而成為互斥關(guān)

7、系。因?yàn)閷戇M(jìn)程執(zhí)行時(shí)，不能執(zhí)行其他讀寫進(jìn)程，所以還必須設(shè)置一個(gè)計(jì)數(shù)器統(tǒng)計(jì)(tngj)讀進(jìn)程的個(gè)數(shù)。如果是第一個(gè)讀進(jìn)程，就與寫進(jìn)程競爭數(shù)據(jù)庫。如果是最后一個(gè)讀進(jìn)程，就釋放數(shù)據(jù)庫。因計(jì)數(shù)器是一個(gè)臨界資源，所以多個(gè)讀進(jìn)程對計(jì)數(shù)器的操作又是互斥操作。 設(shè)：信號(hào)量rmutex表示數(shù)據(jù)庫資源，初值為1表示資源可用；wmutex表示計(jì)數(shù)器count資源，初值為1表示可用。 int rmutex=1，wmutex=1; cobegin reader() / writer() coend進(jìn)程進(jìn)程(jnchng)(jnchng)的互斥的互斥第11頁/共29頁第十一頁，共30頁。小結(jié)進(jìn)程互斥：進(jìn)程之間要競爭臨界資源

8、。信號(hào)量表示臨界資源是否(sh fu)可用，或臨界資源的數(shù)量。信號(hào)量的個(gè)數(shù)與臨界資源的個(gè)數(shù)一致。對同一個(gè)信號(hào)量的PV操作要在同一個(gè)進(jìn)程中完成。P操作：進(jìn)入臨界區(qū)前V操作：離開臨界區(qū)后進(jìn)程進(jìn)程(jnchng)(jnchng)的互斥的互斥第12頁/共29頁第十二頁，共30頁。進(jìn)程同步進(jìn)程同步：并發(fā)進(jìn)程之間相互合作，完成一項(xiàng)工作，它們之間有一定的時(shí)序關(guān)系。解題步驟：確定進(jìn)程的個(gè)數(shù)及每個(gè)進(jìn)程的工作；確定關(guān)鍵工作步（需要控制的）；確定信號(hào)量表示的含義，當(dāng)信號(hào)量的值為0時(shí)，表示期望的消息尚未產(chǎn)生(chnshng)；當(dāng)信號(hào)量的值非0時(shí)，表示期望的消息已經(jīng)存在。 寫出偽代碼。在同步關(guān)系的控制中，同一信號(hào)量的P

9、(wait)、V(signal)操作成對出現(xiàn)，但它們分別在不同的進(jìn)程代碼中。 第13頁/共29頁第十三頁，共30頁。 例1：假設(shè)有三個(gè)并發(fā)進(jìn)程P，Q，R，其中P負(fù)責(zé)(fz)從輸入設(shè)備上讀入信息并傳送給Q，Q將信息加工后傳送給R，R則負(fù)責(zé)(fz)將信息打印輸出。進(jìn)程P、Q共享一個(gè)緩沖區(qū)，進(jìn)程Q、R共享另一個(gè)緩沖區(qū)。 進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步3個(gè)進(jìn)程P、Q、RP進(jìn)程：從輸入(shr)設(shè)備上讀入信息將信息放入緩沖區(qū)1Q進(jìn)程：從緩沖區(qū)1取出信息將信息放入緩沖區(qū)2中R進(jìn)程：從緩沖區(qū)2取出信息將信息打印輸出第14頁/共29頁第十四頁，共30頁。 確定(qudng)進(jìn)程的同步、互

10、斥關(guān)系 同步：P當(dāng)緩存區(qū)1無數(shù)據(jù)時(shí)，才可以向緩沖區(qū)1寫入信息 同步：Q當(dāng)緩存區(qū)1有數(shù)據(jù)時(shí)，才可以從緩沖區(qū)1讀取信息 同步：Q當(dāng)緩存區(qū)2無數(shù)據(jù)時(shí)，才可以向緩沖區(qū)2寫入信息 同步：R當(dāng)緩存區(qū)2有數(shù)據(jù)時(shí)，才可以從緩沖區(qū)2讀取信息 設(shè)置信號(hào)量 緩存區(qū)1無數(shù)據(jù)，empty1，初值1 緩存區(qū)1有數(shù)據(jù)，full1，初值0 緩存區(qū)2無數(shù)據(jù)，empty2，初值1 緩存區(qū)2有數(shù)據(jù)，full2，初值0第15頁/共29頁第十五頁，共30頁。process P ( ) while(1) 從輸入設(shè)備(shbi)上讀入信息; P（empty1）; 將信息放入緩沖區(qū)1； V（full1）; process Q ( ) whi

11、le(1) P（full1）;從緩沖區(qū)1取出信息(xnx); V（empty1）; P（empty2）;將信息(xnx)放入緩沖區(qū)2； V（full2）; process R ( ) while(1) P（full2）;從緩沖區(qū)2取出信息(xnx); V（empty2）;將信息(xnx)打印輸出 ; 第16頁/共29頁第十六頁，共30頁。進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步例2 2：公共汽車(gnggngqch)(gnggngqch)中的司機(jī)和售票員。 司機(jī) P1 P1 售票員 P2 P2 while (true) while (true) while (true) while

12、 (true) 啟動(dòng)車輛； 關(guān)門(gun(gunmn)mn)； 正常運(yùn)行； 售票； 到站停車； 開門； 第17頁/共29頁第十七頁，共30頁。 解法：信號(hào)量表示進(jìn)程能否開始(kish)。 設(shè)信號(hào)量m1表示司機(jī)進(jìn)程P1能否啟動(dòng)汽車，初值為0，m2表示售票員進(jìn)程p2能否開門，初值為0。 int m1=0,m20 ; cobegin p1() / p2() coend進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步第18頁/共29頁第十八頁，共30頁。進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步例3-23-2：吃水果。 父親 P1 P1 兒子 P2 P2 女兒 P3 P3 while (

13、true) while (true) while(true) while (true) while (true) while(true) 洗水果(shugu)(shugu)； 取桔子； 取蘋果； 放水果(shugu)(shugu)； 吃桔子； 吃蘋果； 桔子父親(f qn)兒子女兒0蘋果第19頁/共29頁第十九頁，共30頁。 分析(fnx)：父親先放水果，兒子女兒再吃水果；兒子女兒取完水果，父親再放水果，這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。 解法：設(shè)信號(hào)量m1表示父親能否放水果，m2表示兒子能否取桔子，m3表示女兒能否取蘋果。 int m1=1,m2=0,m3=0； cobegin p1() / p2(

14、) / p3() coend進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步第20頁/共29頁第二十頁，共30頁。進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步例3-33-3：吃水果。 父親 P1 P1 母親(m qn) P2 (m qn) P2 兒子 P3 P3 while (true) while (true) while(true) while (true) while (true) while(true) 洗桔子； 洗蘋果； 取水果； 放桔子； 放蘋果； 吃水果； 0父親(f qn)兒子母親桔子蘋果第21頁/共29頁第二十一頁，共30頁。 分析：父母親先放水果，兒子再取水果吃

15、；父親與兒子，母親與兒子是一個(gè)同步關(guān)系，父親與母親要競爭空盤子。 解法：設(shè)信號(hào)量m1表示是否(sh fu)有空盤子，信號(hào)量m2表示兒子能否取水果。 int m1=1,m2=0； cobegin p1() / p2() / p3() coend進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步第22頁/共29頁第二十二頁，共30頁。0進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步例3-43-4：吃水果。 父親 P1 P1 母親 P2 P2 兒子(r zi) P3 (r zi) P3 女兒P4 P4 while(true) while (true) while(true) while(tr

16、ue)while(true) while (true) while(true) while(true) 洗桔子； 洗蘋果； 取蘋果； 取桔子； 放桔子； 放蘋果； 吃蘋果； 吃桔子； 桔子父親(f qn)女兒母親蘋果兒子第23頁/共29頁第二十三頁，共30頁。 分析：父母親(m qn)先放水果，兒子女兒再取水果；父親與女兒，母親(m qn)與兒子是一個(gè)同步關(guān)系，父親與母親(m qn)要競爭空盤子。 解法一：設(shè)信號(hào)量m1表示是否有空盤子，信號(hào)量m2表示兒子能否取蘋果，m3表示女兒能否取桔子。 int m1=1,m2=0,m3=0； cobegin p1() / p2() / p3() / p4(

17、) coend進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步第24頁/共29頁第二十四頁，共30頁。問題(wnt) 有一只鐵籠子，每次只能放入一只動(dòng)物，獵手向籠中放入老虎，農(nóng)民向籠中放入豬，動(dòng)物園等待取籠中的老虎，飯店等待取籠中的豬，試用P、V操作寫出能同步執(zhí)行(zhxng)的程序。第25頁/共29頁第二十五頁，共30頁。例例4 4。設(shè)有六個(gè)進(jìn)程。設(shè)有六個(gè)進(jìn)程(jnchng)P1(jnchng)P1、P2P2、P3P3、P4P4、P5P5、P6P6，它們并發(fā)執(zhí)行。由，它們并發(fā)執(zhí)行。由P1P1開始執(zhí)行，開始執(zhí)行，P6P6執(zhí)行后結(jié)束。當(dāng)進(jìn)程執(zhí)行后結(jié)束。當(dāng)進(jìn)程(jnchng)P1(jnchng

18、)P1執(zhí)行后，進(jìn)程執(zhí)行后，進(jìn)程(jnchng)P2(jnchng)P2、P3P3才能執(zhí)行；當(dāng)進(jìn)程才能執(zhí)行；當(dāng)進(jìn)程(jnchng)P2(jnchng)P2執(zhí)行后，進(jìn)程執(zhí)行后，進(jìn)程(jnchng)P4(jnchng)P4才能執(zhí)行；當(dāng)進(jìn)程才能執(zhí)行；當(dāng)進(jìn)程(jnchng)P3(jnchng)P3執(zhí)行后，進(jìn)程執(zhí)行后，進(jìn)程(jnchng)P5(jnchng)P5才能執(zhí)行；當(dāng)進(jìn)程才能執(zhí)行；當(dāng)進(jìn)程(jnchng)P4(jnchng)P4、P5P5都執(zhí)行后，進(jìn)程都執(zhí)行后，進(jìn)程(jnchng)P6(jnchng)P6才能執(zhí)行；請用才能執(zhí)行；請用P P、V V操作編程操作編程. .進(jìn)程進(jìn)程(jnchng)(jnchng)的同步的同步第26頁/共29頁第二十六頁，共30頁。解：這是一個(gè)(y )(y )同步問題，信號(hào)量初值：S2=0S2=0，S3=0S3=0，S4=0S4=0，S5=0S5=0，S6=0S6=0 進(jìn)程P1 P1 進(jìn)程P2 P2 進(jìn)程P3P3 執(zhí)行P1 P(S2) P(S3)P1 P(S2) P(S3) V(S2) V(S2) 執(zhí)行P2 P2 執(zhí)