Chapter+6+進(jìn)程同步與互斥應(yīng)用例子

1、進(jìn)程同步與互斥進(jìn)程同步與互斥 例題 進(jìn)程互斥 進(jìn)程互斥進(jìn)程互斥： 并發(fā)進(jìn)程之間相互競(jìng)爭(zhēng)臨界資源的排他性關(guān)系。并發(fā)進(jìn)程之間相互競(jìng)爭(zhēng)臨界資源的排他性關(guān)系。 解題步驟解題步驟： n 確定臨界資源及確定臨界資源及個(gè)數(shù)個(gè)數(shù)； n 確定進(jìn)程的確定進(jìn)程的關(guān)鍵工作步關(guān)鍵工作步（使用臨界資源的）；（使用臨界資源的）； n 確定信號(hào)量的初值確定信號(hào)量的初值(臨界資源的個(gè)數(shù)臨界資源的個(gè)數(shù))； n 寫出寫出偽代碼偽代碼。 使用使用P(wait)操作和操作和V(signal)操作對(duì)進(jìn)程互斥進(jìn)操作對(duì)進(jìn)程互斥進(jìn) 行控制。行控制。 例例1：過獨(dú)木橋。：過獨(dú)木橋。 進(jìn)程的互斥進(jìn)程的互斥 P1 P2 由西向東過獨(dú)木橋；由西向東過

2、獨(dú)木橋； 由東向西過獨(dú)木橋；由東向西過獨(dú)木橋； P1 P2 分析分析：進(jìn)程：進(jìn)程P1、P2因競(jìng)爭(zhēng)獨(dú)木橋這個(gè)資源而成為互斥關(guān)系。因競(jìng)爭(zhēng)獨(dú)木橋這個(gè)資源而成為互斥關(guān)系。 設(shè)設(shè)：信號(hào)量：信號(hào)量m表示獨(dú)木橋資源，初值為表示獨(dú)木橋資源，初值為1表示資源可用。表示資源可用。 int m=1; cobegin p1() / p2() coend 進(jìn)程的互斥進(jìn)程的互斥 練習(xí)練習(xí)：過十字路口（單道）。：過十字路口（單道）。 進(jìn)程的互斥進(jìn)程的互斥 P1 P2 P3 P4 通過路口；通過路口； 通過路口；通過路口； 通過路口；通過路口； 通過路口；通過路口； P2 P3 P4 P1 分析分析：進(jìn)程：進(jìn)程P1、P2、P

3、3、P4因競(jìng)爭(zhēng)十字路口這個(gè)資源而成因競(jìng)爭(zhēng)十字路口這個(gè)資源而成 為互斥關(guān)系。為互斥關(guān)系。 設(shè)設(shè)：信號(hào)量：信號(hào)量m表示十字路口資源，初值為表示十字路口資源，初值為1表示資源可用。表示資源可用。 int m=1; cobegin p1() / p2() /p3() / p4() coend 進(jìn)程的互斥進(jìn)程的互斥 有一個(gè)閱覽室，共有有一個(gè)閱覽室，共有100100個(gè)座位。讀者進(jìn)入閱覽室個(gè)座位。讀者進(jìn)入閱覽室 時(shí)必須在入口處進(jìn)行登記；離開閱覽室時(shí)必須進(jìn)時(shí)必須在入口處進(jìn)行登記；離開閱覽室時(shí)必須進(jìn) 行注銷。試用行注銷。試用PVPV操作描述讀者進(jìn)入操作描述讀者進(jìn)入/ /離開閱覽室的離開閱覽室的 同步與互斥關(guān)系同

4、步與互斥關(guān)系。 ReaderReader進(jìn)程進(jìn)程 登記登記 進(jìn)入閱覽室進(jìn)入閱覽室 讀書讀書 離開閱覽室離開閱覽室 注銷注銷 進(jìn)程的互斥進(jìn)程的互斥 分析：分析： 在入口和出口處讀者應(yīng)該在入口和出口處讀者應(yīng)該互斥互斥進(jìn)行登記和注銷，進(jìn)行登記和注銷， 100100個(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)量Sout

5、Sout，初值，初值 1 1，表，表 示當(dāng)前可用示當(dāng)前可用 begin Sin, Sout, seat：semaphore; seat :=100; Sin := 1; Sout := 1; cobegin process Reader-i ( i = 1,2,n ); begin P(seat); P(Sin); 登記登記; V(Sin); 進(jìn)入閱覽室進(jìn)入閱覽室; 讀書讀書; 離開閱覽室離開閱覽室; P(Sout); 注銷注銷; V(Sout); V（seat）; end coend; end; 問題 若有一售票廳只能容納300人，當(dāng)少于300 人時(shí)，可以進(jìn)入。否則，需在外等候， 若將每一個(gè)

6、購(gòu)票者作為一個(gè)進(jìn)程，請(qǐng)用P、 V操作編程。 例例2：讀寫數(shù)據(jù)庫(kù)：讀寫數(shù)據(jù)庫(kù)。某數(shù)據(jù)庫(kù)有一個(gè)寫進(jìn)程、多個(gè)讀進(jìn)程，它們之間某數(shù)據(jù)庫(kù)有一個(gè)寫進(jìn)程、多個(gè)讀進(jìn)程，它們之間 讀、寫操作的互斥要求是：寫進(jìn)程運(yùn)行時(shí)，其他讀、寫進(jìn)程不能對(duì)數(shù)讀、寫操作的互斥要求是：寫進(jìn)程運(yùn)行時(shí)，其他讀、寫進(jìn)程不能對(duì)數(shù) 據(jù)庫(kù)進(jìn)行操作。讀進(jìn)程之間不互斥，可以同時(shí)讀數(shù)據(jù)庫(kù)。請(qǐng)用信號(hào)量據(jù)庫(kù)進(jìn)行操作。讀進(jìn)程之間不互斥，可以同時(shí)讀數(shù)據(jù)庫(kù)。請(qǐng)用信號(hào)量 及及PV操作描述這一組進(jìn)程的工作過程。（操作描述這一組進(jìn)程的工作過程。（讀者讀者-寫者問題寫者問題） 進(jìn)程的互斥進(jìn)程的互斥 數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù) 寫寫 者者 讀讀 者者 寫者寫者 讀者讀者 寫數(shù)據(jù)庫(kù)；寫

7、數(shù)據(jù)庫(kù)； 讀數(shù)據(jù)庫(kù)；讀數(shù)據(jù)庫(kù)； 分析分析：寫進(jìn)程寫進(jìn)程writer、讀進(jìn)程、讀進(jìn)程reader因競(jìng)爭(zhēng)數(shù)據(jù)庫(kù)這個(gè)資源因競(jìng)爭(zhēng)數(shù)據(jù)庫(kù)這個(gè)資源 而成為互斥關(guān)系。因?yàn)閷戇M(jìn)程執(zhí)行時(shí)，不能執(zhí)行其他讀寫而成為互斥關(guān)系。因?yàn)閷戇M(jìn)程執(zhí)行時(shí)，不能執(zhí)行其他讀寫 進(jìn)程，所以還必須設(shè)置一個(gè)計(jì)數(shù)器統(tǒng)計(jì)讀進(jìn)程的個(gè)數(shù)。如進(jìn)程，所以還必須設(shè)置一個(gè)計(jì)數(shù)器統(tǒng)計(jì)讀進(jìn)程的個(gè)數(shù)。如 果是第一個(gè)讀進(jìn)程，就與寫進(jìn)程競(jìng)爭(zhēng)數(shù)據(jù)庫(kù)。如果是最后果是第一個(gè)讀進(jìn)程，就與寫進(jìn)程競(jìng)爭(zhēng)數(shù)據(jù)庫(kù)。如果是最后 一個(gè)讀進(jìn)程，就釋放數(shù)據(jù)庫(kù)。因計(jì)數(shù)器是一個(gè)臨界資源，一個(gè)讀進(jìn)程，就釋放數(shù)據(jù)庫(kù)。因計(jì)數(shù)器是一個(gè)臨界資源， 所以多個(gè)讀進(jìn)程對(duì)計(jì)數(shù)器的操作又是互斥操作。所以多個(gè)讀進(jìn)程

8、對(duì)計(jì)數(shù)器的操作又是互斥操作。 設(shè)設(shè)：信號(hào)量信號(hào)量rmutex表示數(shù)據(jù)庫(kù)資源，初值為表示數(shù)據(jù)庫(kù)資源，初值為1表示資源可用；表示資源可用； wmutex表示計(jì)數(shù)器表示計(jì)數(shù)器count資源，初值為資源，初值為1表示可用。表示可用。 int rmutex=1，wmutex=1; cobegin reader() / writer() coend 進(jìn)程的互斥進(jìn)程的互斥 小結(jié)小結(jié) n 進(jìn)程互斥：進(jìn)程之間要競(jìng)爭(zhēng)臨界資源。進(jìn)程互斥：進(jìn)程之間要競(jìng)爭(zhēng)臨界資源。 n 信號(hào)量表示臨界資源是否可用，或臨界資源信號(hào)量表示臨界資源是否可用，或臨界資源 的數(shù)量。的數(shù)量。 n 信號(hào)量的個(gè)數(shù)與臨界資源的個(gè)數(shù)一致。信號(hào)量的個(gè)數(shù)與臨

9、界資源的個(gè)數(shù)一致。 n 對(duì)同一個(gè)信號(hào)量的對(duì)同一個(gè)信號(hào)量的PV操作要在同一個(gè)進(jìn)程中操作要在同一個(gè)進(jìn)程中 完成。完成。 P操作：進(jìn)入臨界區(qū)前操作：進(jìn)入臨界區(qū)前 1. V操作：離開臨界區(qū)后操作：離開臨界區(qū)后 進(jìn)程的互斥進(jìn)程的互斥 進(jìn)程同步 進(jìn)程同步進(jìn)程同步： 并發(fā)進(jìn)程之間相互合作，完成一項(xiàng)工作，它們之并發(fā)進(jìn)程之間相互合作，完成一項(xiàng)工作，它們之 間有一定的時(shí)序關(guān)系。間有一定的時(shí)序關(guān)系。 解題步驟解題步驟： n確定進(jìn)程的確定進(jìn)程的個(gè)數(shù)個(gè)數(shù)及每個(gè)進(jìn)程的及每個(gè)進(jìn)程的工作工作； n確定確定關(guān)鍵工作步關(guān)鍵工作步（需要控制的）；（需要控制的）； n確定信號(hào)量表示的確定信號(hào)量表示的含義，含義，當(dāng)信號(hào)量的值為當(dāng)信號(hào)量

10、的值為0時(shí)，表時(shí)，表 示期望的消息尚未產(chǎn)生；當(dāng)信號(hào)量的值非示期望的消息尚未產(chǎn)生；當(dāng)信號(hào)量的值非0時(shí)，表時(shí)，表 示期望的消息已經(jīng)存在。示期望的消息已經(jīng)存在。 1.寫出寫出偽代碼偽代碼。在同步關(guān)系的控制中，同一信號(hào)量。在同步關(guān)系的控制中，同一信號(hào)量 的的P(wait)、V(signal)操作成對(duì)出現(xiàn)，但它們分別操作成對(duì)出現(xiàn)，但它們分別 在不同的進(jìn)程代碼中。在不同的進(jìn)程代碼中。 例例1：假設(shè)有三個(gè)并發(fā)進(jìn)程假設(shè)有三個(gè)并發(fā)進(jìn)程P，Q，R，其中，其中P負(fù)責(zé)從輸入設(shè)負(fù)責(zé)從輸入設(shè) 備上讀入信息并傳送給備上讀入信息并傳送給Q，Q將信息加工后傳送給將信息加工后傳送給R，R則負(fù)則負(fù) 責(zé)將信息打印輸出。進(jìn)程責(zé)將信息打

11、印輸出。進(jìn)程P、Q共享一個(gè)緩沖區(qū)，進(jìn)程共享一個(gè)緩沖區(qū)，進(jìn)程Q、R 共享另一個(gè)緩沖區(qū)。共享另一個(gè)緩沖區(qū)。 進(jìn)程的同步進(jìn)程的同步 3個(gè)進(jìn)程P、Q、R P進(jìn)程： 從輸入設(shè)備上讀入信息 將信息放入緩沖區(qū)1 Q進(jìn)程： 從緩沖區(qū)1取出信息 將信息放入緩沖區(qū)2中 R進(jìn)程： 從緩沖區(qū)2取出信息 將信息打印輸出 確定進(jìn)程的同步、互斥關(guān)系確定進(jìn)程的同步、互斥關(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)量設(shè)置信號(hào)量 緩存區(qū)1無數(shù)據(jù)，

12、empty1，初值1 緩存區(qū)1有數(shù)據(jù)，full1，初值0 緩存區(qū)2無數(shù)據(jù)，empty2，初值1 緩存區(qū)2有數(shù)據(jù)，full2，初值0 process P ( ) while(1) 從輸入設(shè)備上讀入信息從輸入設(shè)備上讀入信息; P（empty1）; 將信息放入緩沖區(qū)將信息放入緩沖區(qū)1； V（full1）; process Q ( ) while(1) P（full1）; 從緩沖區(qū)從緩沖區(qū)1取出信息取出信息; V（empty1）; P（empty2）; 將信息放入緩沖區(qū)將信息放入緩沖區(qū)2； V（full2）; process R ( ) while(1) P（full2）; 從緩沖區(qū)從緩沖區(qū)2取出信息

13、取出信息; V（empty2）; 將信息打印輸出將信息打印輸出 ; 進(jìn)程的同步進(jìn)程的同步 例例2 2：公共汽車中的司機(jī)和售票員。：公共汽車中的司機(jī)和售票員。 司機(jī)司機(jī) P1 P1 售票員售票員 P2P2 while (true) while (true) while (true) while (true) 啟動(dòng)車輛啟動(dòng)車輛； 關(guān)門關(guān)門； 正常運(yùn)行；正常運(yùn)行； 售票；售票； 到站停車到站停車； 開門開門； 解法解法：信號(hào)量表示進(jìn)程能否開始。：信號(hào)量表示進(jìn)程能否開始。 設(shè)信號(hào)量設(shè)信號(hào)量m1表示司機(jī)進(jìn)程表示司機(jī)進(jìn)程P1能否啟動(dòng)汽車，初值為能否啟動(dòng)汽車，初值為0， m2表示售票員進(jìn)程表示售票員進(jìn)程p2

14、能否開門，初值為能否開門，初值為0。 int m1=0,m20 ; cobegin p1() / p2() coend 進(jìn)程的同步進(jìn)程的同步 進(jìn)程的同步進(jìn)程的同步 例例3-23-2：吃水果。：吃水果。 父親父親 P1 P1 兒子兒子 P2 P2 女兒女兒 P3P3 while (true) while (true) while(true) while (true) while (true) while(true) 洗水果；洗水果； 取桔子取桔子； 取蘋果取蘋果； 放水果放水果； 吃桔子；吃桔子； 吃蘋果；吃蘋果； 桔子桔子 父親父親 兒子兒子 女兒女兒 0蘋果蘋果 分析分析：父親先放水果，兒子

15、女兒再吃水果；兒子女兒取完水：父親先放水果，兒子女兒再吃水果；兒子女兒取完水 果，父親再放水果，這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。果，父親再放水果，這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。 解法：解法：設(shè)信號(hào)量設(shè)信號(hào)量m1表示父親能否放水果，表示父親能否放水果，m2表示兒子能否表示兒子能否 取桔子，取桔子，m3表示女兒能否取蘋果。表示女兒能否取蘋果。 int m1=1,m2=0,m3=0； cobegin p1() / p2() / p3() coend 進(jìn)程的同步進(jìn)程的同步 進(jìn)程的同步進(jìn)程的同步 例例3-33-3：吃水果。：吃水果。 父親父親 P1 P1 母親母親 P2 P2 兒子兒子 P3P3 while (t

16、rue) while (true) while(true) while (true) while (true) while(true) 洗桔子；洗桔子； 洗蘋果；洗蘋果； 取水果取水果； 放桔子放桔子； 放蘋果；放蘋果； 吃水果；吃水果； 0 父親父親 兒子兒子 母親母親 桔子桔子蘋果蘋果 分析分析：父母親先放水果，兒子再取水果吃；父親與兒子，母：父母親先放水果，兒子再取水果吃；父親與兒子，母 親與兒子是一個(gè)同步關(guān)系，父親與母親要競(jìng)爭(zhēng)空盤子。親與兒子是一個(gè)同步關(guān)系，父親與母親要競(jìng)爭(zhēng)空盤子。 解法：解法：設(shè)信號(hào)量設(shè)信號(hào)量m1表示是否有空盤子，信號(hào)量表示是否有空盤子，信號(hào)量m2表示兒子表示兒子 能

17、否取水果。能否取水果。 int m1=1,m2=0； cobegin p1() / p2() / p3() coend 進(jìn)程的同步進(jìn)程的同步 0 進(jìn)程的同步進(jìn)程的同步 例例3-43-4：吃水果。：吃水果。 父親父親 P1 P1 母親母親 P2 P2 兒子兒子 P3P3 女兒女兒P4P4 while(true) while (true) while(true) while(true)while(true) while (true) while(true) while(true) 洗桔子；洗桔子； 洗蘋果；洗蘋果； 取蘋果取蘋果； 取桔子；取桔子； 放桔子放桔子； 放蘋果；放蘋果； 吃蘋果；吃蘋果

18、； 吃桔子；吃桔子； 桔子桔子 父親父親 女兒女兒 母親母親 蘋果蘋果 兒子兒子 分析分析：父母親先放水果，兒子女兒再取水果；父親與女兒，：父母親先放水果，兒子女兒再取水果；父親與女兒， 母親與兒子是一個(gè)同步關(guān)系，父親與母親要競(jìng)爭(zhēng)空盤子。母親與兒子是一個(gè)同步關(guān)系，父親與母親要競(jìng)爭(zhēng)空盤子。 解法一：解法一：設(shè)信號(hào)量設(shè)信號(hào)量m1表示是否有空盤子，信號(hào)量表示是否有空盤子，信號(hào)量m2表示兒表示兒 子能否取蘋果，子能否取蘋果，m3表示女兒能否取桔子。表示女兒能否取桔子。 int m1=1,m2=0,m3=0； cobegin p1() / p2() / p3() / p4() coend 進(jìn)程的同步進(jìn)程

19、的同步 問題 有一只鐵籠子，每次只能放入一只動(dòng)物，獵手有一只鐵籠子，每次只能放入一只動(dòng)物，獵手 向籠中放入老虎，農(nóng)民向籠中放入豬，動(dòng)物園向籠中放入老虎，農(nóng)民向籠中放入豬，動(dòng)物園 等待取籠中的老虎，飯店等待取籠中的豬，試等待取籠中的老虎，飯店等待取籠中的豬，試 用用P、V操作寫出能同步執(zhí)行的程序。操作寫出能同步執(zhí)行的程序。 例例4 4。設(shè)有六個(gè)進(jìn)程設(shè)有六個(gè)進(jìn)程P1P1、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) 程程P1P1執(zhí)行后，進(jìn)程執(zhí)行后，進(jìn)程P2P2、P3P3才能執(zhí)行；當(dāng)進(jìn)程才能執(zhí)行；當(dāng)進(jìn)程P2P2執(zhí)行執(zhí)行 后，進(jìn)程后，進(jìn)程P4P4才能執(zhí)行；當(dāng)進(jìn)程才能執(zhí)行；當(dāng)進(jìn)程P3P3執(zhí)行后，進(jìn)程執(zhí)行后，進(jìn)程P5P5才才 能執(zhí)行；當(dāng)進(jìn)程能執(zhí)行；當(dāng)