進(jìn)程同步與互斥_問(wèn)題.ppt

1、進(jìn)程同步與互斥,例題,進(jìn)程同步,進(jìn)程同步： 并發(fā)進(jìn)程之間相互合作，完成一項(xiàng)工作，它們之間有一定的時(shí)序關(guān)系。 解題步驟： 確定進(jìn)程的個(gè)數(shù)及每個(gè)進(jìn)程的工作； 確定關(guān)鍵工作步（需要控制的）； 確定信號(hào)量表示的含義（開(kāi)始或結(jié)束）； 寫出偽代碼。,進(jìn)程的同步,例：公共汽車中的司機(jī)和售票員。,司機(jī) P1 售票員 P2 while (true) while (true) 啟動(dòng)車輛； 關(guān)門； 正常運(yùn)行； 售票； 到站停車； 開(kāi)門； ,解法一：信號(hào)量表示進(jìn)程能否開(kāi)始。 設(shè)信號(hào)量m1表示司機(jī)進(jìn)程P1能否啟動(dòng)汽車，初值為0，m2表示售票員進(jìn)程p2能否開(kāi)門，初值為0。 int m1=0,m20 ; cobegin p

2、1() / p2() coend,進(jìn)程的同步,p1() while(1) P(m1); 啟動(dòng)汽車； 正常行駛； 到站停車； V(m2); ,p2() while(1) 關(guān)門； V(m1); 售票； (m2); 開(kāi)門； ,解法二：信號(hào)量表示進(jìn)程是否結(jié)束。 設(shè)信號(hào)量m1表示司機(jī)進(jìn)程P1到站停車結(jié)束，初值為0，m2表示售票員進(jìn)程p2關(guān)門結(jié)束，初值為0。 int m1=0,m20 ； cobegin p1() / p2() coend,進(jìn)程的同步,p1() while(1) P(m2)； 啟動(dòng)汽車； 正常行駛； 到站停車； V(m1)； ,p2() while(1) 關(guān)門； V(m2)； 售票； (m

3、1)； 開(kāi)門； ,進(jìn)程的同步,例：吃水果。,父親 P1 兒子 P2 while (true) while (true) 洗水果； 取水果； 放水果； 吃水果； ,0,父親,兒子,水果,分析：父親先放水果，兒子再吃水果；兒子取完水果，父親再放水果，這兩個(gè)進(jìn)程是一個(gè)同步關(guān)系。 解法一：設(shè)信號(hào)量m1表示父親能否放水果，m2表示兒子能否取水果。其初值m1=1,m2=0。 int m1=1,m2=0； cobegin p1()/p2() coend,進(jìn)程的同步,p1() while(1) 洗水果； P(m1) ； 放水果； V(m2) ； ,p2() while(1) P(m2) ； 取水果； V(m1

4、)； 吃水果； ,思考： 假設(shè)盤子能放n個(gè)水果，如何修改同步關(guān)系？,int m1=1,m2=0；,分析：父親先放水果，兒子再吃水果；兒子取完水果，父親再放水果，這兩個(gè)進(jìn)程是一個(gè)同步關(guān)系。 解法二：設(shè)信號(hào)量m1表示父親放完水果，m2表示兒子取完水果。其初值m1=0,m2=1。 int m1=0,m2=1； cobegin p1()/p2() coend,進(jìn)程的同步,p1() while(1) 洗水果； P(m2) ； 放水果； V(m1) ； ,p2() while(1) P(m1) ； 取水果； V(m2)； 吃水果； ,進(jìn)程的同步,例3-2：吃水果。,父親 P1 兒子 P2 女兒 P3 wh

5、ile (true) while (true) while(true) 洗水果； 取桔子； 取蘋果； 放水果； 吃桔子； 吃蘋果； ,桔子,父親,兒子,女兒,0,蘋果,分析：父親先放水果，兒子女兒再吃水果；兒子女兒取完水果，父親再放水果，這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。 解法一：設(shè)信號(hào)量m1表示父親能否放水果，m2表示兒子能否取桔子，m3表示女兒能否取蘋果。 int m1=1,m2=0,m3=0； cobegin p1() / p2() / p3() coend,進(jìn)程的同步,p1() while(1) 洗水果； P(m1) ； 放水果； if (是桔子) V(m2) ； else V(m3)； ,p

6、2() while(1) P(m2) ； 取桔子； V(m1)； 吃桔子； ,p3() while(1) P(m3) ； 取蘋果； V(m1)； 吃蘋果； ,分析：父親先放水果，兒子女兒再吃水果；兒子女兒取完水果，父親再放水果，這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。 解法二：設(shè)信號(hào)量m1表示父親放完桔子，m2表示父親放完蘋果，m3表示兒子女兒取完水果。 int m1=0,m2=0,m3=1； cobegin p1() / p2() / p3() coend,進(jìn)程的同步,p1() while(1) 洗水果； P(m3) ； 放水果； if (是桔子) V(m1) ； else V(m2)； ,p2() wh

7、ile(1) P(m1) ； 取桔子； V(m3)； 吃桔子； ,p3() while(1) P(m2) ； 取蘋果； V(m3)； 吃蘋果； ,進(jìn)程的同步,例3-3：吃水果。,父親 P1 母親 P2 兒子 P3 while (true) while (true) while(true) 洗桔子； 洗蘋果； 取水果； 放桔子； 放蘋果； 吃水果； ,0,父親,兒子,母親,桔子,蘋果,分析：父母親先放水果，兒子再取水果吃；父親與兒子，母親與兒子是一個(gè)同步關(guān)系，父親與母親要競(jìng)爭(zhēng)空盤子。 解法一：設(shè)信號(hào)量m1表示是否有空盤子，信號(hào)量m2表示兒子能否取水果。 int m1=1,m2=0； cobegi

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

9、 while(1) 洗桔子； P(m2) ； 放桔子； V(m1) ； ,p2() while(1) 洗蘋果 ； P(m2)； 放蘋果； V(m1)； ,p3() while(1) P(m1) ； 取水果； V(m2)； 吃水果； ,0,進(jìn)程的同步,例3-4：吃水果。,父親 P1 母親 P2 兒子 P3 女兒P4 while(true) while (true) while(true) while(true) 洗桔子； 洗蘋果； 取蘋果； 取桔子； 放桔子； 放蘋果； 吃蘋果； 吃桔子； ,桔子,父親,女兒,母親,蘋果,兒子,分析：父母親先放水果，兒子女兒再取水果；父親與女兒，母親與兒子是一個(gè)

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

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

12、取桔子； V(m3)； 吃桔子； ,進(jìn)程的同步,例4：打印文件。,P1 P2 P3 while (true) while (true) while(true) 從磁盤取文件； 從緩沖1取文件； 從緩沖2取文件； 放入緩沖1； 放入緩沖2； 打印文件； ,緩沖1,磁盤,打印機(jī),緩沖2,P1,P2,P3,分析：P1做完，P2才能做，P2做完，P3才能做。這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。 解法一：設(shè)信號(hào)量m1表示P1能否把文件放入緩沖1，m2表示P2能否從緩沖1取文件，m3表示P2能否把文件放入緩沖2，m4表示P3能否從緩沖2取文件。 int m1=1,m2=0,m3=1,m4=0； cobegin p1

13、() / p2() / p3() coend,進(jìn)程的同步,p1() while(1) 從磁盤讀文件； P(m1) ； 放入緩沖1； V(m2) ； ,p2() while(1) P(m2) ； 從緩沖1取文件； V(m1)； P(m3); 放入緩沖2； V(m4)； ,p3() while(1) P(m4) ； 從緩沖2取文件； V(m3)； 打印文件； ,思考： 1.緩沖1可以存放n個(gè)文件，緩沖2可以存放 m個(gè)文件，如何修改同步關(guān)系？ 2.如果P2改為如下形式，會(huì)有何影響？,int m1=n,m2=0,m3=m,m4=0；,P(m2) ； P(m3); 從緩沖1取文件； 放入緩沖2； V(m

14、1)； V(m4)；,進(jìn)程的并發(fā)性不如修改前,分析：P1做完，P2才能做，P2做完，P3才能做。這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。 解法二：設(shè)信號(hào)量m1表示P1是否把文件放入緩沖1，m2表示P2是否從緩沖1取完文件，m3表示P2是否把文件放入緩沖2，m4表示P3是否從緩沖2取完文件。 int m1=0,m2=1,m3=0,m4=1； cobegin p1() / p2() / p3() coend,進(jìn)程的同步,p1() while(1) 從磁盤讀文件； P(m2) ； 放入緩沖1； V(m1) ； ,p2() while(1) P(m1) ； 從緩沖1取文件； V(m2)； P(m4); 放入緩沖2；

15、 V(m3)； ,p3() while(1) P(m3) ； 從緩沖2取文件； V(m4)； 打印文件； ,小結(jié) 進(jìn)程同步有一定的時(shí)序關(guān)系。 信號(hào)量表示進(jìn)程的關(guān)鍵工作是否可以開(kāi)始或已經(jīng)結(jié)束。 信號(hào)量的個(gè)數(shù)與進(jìn)程的個(gè)數(shù)一致，有時(shí)可以省略部分信號(hào)量。 對(duì)同一個(gè)信號(hào)量的PV操作不在一個(gè)進(jìn)程中。 表示開(kāi)始：P自己，V別人 表示結(jié)束：P別人，V自己,進(jìn)程的同步,進(jìn)程互斥,進(jìn)程互斥： 并發(fā)進(jìn)程之間相互競(jìng)爭(zhēng)臨界資源的排他性關(guān)系。 解題步驟： 確定臨界資源及個(gè)數(shù)； 確定進(jìn)程的關(guān)鍵工作步（使用臨界資源的）； 確定信號(hào)量的初值； 寫出偽代碼。,例1：過(guò)獨(dú)木橋。,進(jìn)程的互斥,P1 P2 由西向東過(guò)獨(dú)木橋； 由東向西

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

17、1; cobegin p1() / p2() /p3() / p4() coend,進(jìn)程的互斥,p1() P(m) ； 通過(guò)路口； V(m) ； ,p2() P(m) ； 通過(guò)路口； V(m)； ,p3() P(m) ； 通過(guò)路口； V(m) ； ,p4() P(m) ； 通過(guò)路口； V(m)； ,練習(xí)2：過(guò)十字路口（雙道）。,進(jìn)程的互斥,P1 P2 P3 P4 通過(guò)路口； 通過(guò)路口； 通過(guò)路口； 通過(guò)路口； ,P1,P2,P3,P4,例2：讀寫數(shù)據(jù)庫(kù)。某數(shù)據(jù)庫(kù)有一個(gè)寫進(jìn)程、多個(gè)讀進(jìn)程，它們之間讀、寫操作的互斥要求是：寫進(jìn)程運(yùn)行時(shí)，其他讀、寫進(jìn)程不能對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作。讀進(jìn)程之間不互斥，可以同時(shí)

18、讀數(shù)據(jù)庫(kù)。請(qǐng)用信號(hào)量及PV操作描述這一組進(jìn)程的工作過(guò)程。（讀者-寫者問(wèn)題）,進(jìn)程的互斥,數(shù)據(jù)庫(kù),寫 者,讀 者,寫者 讀者 寫數(shù)據(jù)庫(kù)； 讀數(shù)據(jù)庫(kù)； ,分析：寫進(jìn)程writer、讀進(jìn)程reader因競(jìng)爭(zhēng)數(shù)據(jù)庫(kù)這個(gè)資源而成為互斥關(guān)系。因?yàn)閷戇M(jìn)程執(zhí)行時(shí)，不能執(zhí)行其他讀寫進(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)程，就釋放數(shù)據(jù)庫(kù)。因計(jì)數(shù)器是一個(gè)臨界資源，所以多個(gè)讀進(jìn)程對(duì)計(jì)數(shù)器的操作又是互斥操作。 設(shè)：信號(hào)量rmutex表示數(shù)據(jù)庫(kù)資源，初值為1表示資源可用；wmutex表示計(jì)數(shù)器count資源，初值為1表示可用。 int rmutex=1

19、，wmutex=1; cobegin reader() / writer() coend,進(jìn)程的互斥,例3：哲學(xué)家就餐問(wèn)題。有4位哲學(xué)家圍著一個(gè)圓桌在討論問(wèn)題和進(jìn)餐，在討論時(shí)每人手中什么都不拿，當(dāng)需要進(jìn)餐時(shí)，每人需要用刀和叉各一把。餐桌上的布置如圖所示，共有兩把刀和兩把叉，每把刀或叉供相鄰的兩個(gè)人使用。請(qǐng)用信號(hào)量及PV操作說(shuō)明4位哲學(xué)家的同步過(guò)程。,進(jìn)程的互斥,哲學(xué)家 進(jìn)餐； 討論問(wèn)題； ,分析：進(jìn)程pa、pb、pc、pd因競(jìng)爭(zhēng)刀和叉而成為互斥關(guān)系。 設(shè)：4個(gè)互斥信號(hào)量fork1，fork2，knife1，knife2，其初值均為“1”，分別表示叉1、叉2、刀1、刀2是可用的。其工作流程如圖所

20、示。 int fork1=fork2=knife1=knife2=1 ; cobegin pa() / pb() /pc() / pd() coend,進(jìn)程的互斥,pa() while(1) P(knife1); P(fork1); 進(jìn)餐; V(knife1); V(fork1); 討論問(wèn)題; ,pb() while(1) P(fork1); P(knife2); 進(jìn)餐; V(knife2); V(fork1); 討論問(wèn)題; ,pc() while(1) P(knife2); P(fork2); 進(jìn)餐; V(knife2); V(fork2); 討論問(wèn)題; ,pd() while(1) P(f

21、ork2); P(knife1); 進(jìn)餐； V(knife1); V(fork2); 討論問(wèn)題; ,思考： 四位哲學(xué)家同時(shí)拿起右手的餐具，再 拿左手的餐具，會(huì)出現(xiàn)什么問(wèn)題？,P(knife1); P(fork2);,P(knife2); P(fork1);,例4：連續(xù)過(guò)獨(dú)木橋。在南開(kāi)大學(xué)和天津大學(xué)之間有一條彎曲的小路，其中從S到T有一段路每次只允許一輛自行車通過(guò)。但是，其中有一個(gè)小的安全島M（同時(shí)允許兩輛自行車停留），可以供兩輛自行車錯(cuò)車時(shí)使用，如圖所示。試設(shè)計(jì)一個(gè)算法以確保來(lái)往自行車的順利通過(guò)。,進(jìn)程的互斥,tonan 通過(guò)TL； 上安全島M； 通過(guò)KS; ,totian 通過(guò)KS; 上安全

22、島M； 通過(guò)TL； ,分析：此圖可以簡(jiǎn)化為： 在本題中，需要控制路段T到L，S到K及安全島M的使用。路段T到L，S到K都只允許一輛自行車通過(guò)，而安全島允許兩輛自行車使用，兩個(gè)路段和安全島相當(dāng)于臨界資源。通過(guò)該路段的兩個(gè)進(jìn)程沒(méi)有必然的先后次序，因此，本題屬于互斥問(wèn)題。另外，為了保證安全島上最多有兩輛自行車，需要對(duì)相向行駛的兩個(gè)方向進(jìn)行控制，在每個(gè)方向上一次只允許一輛自行車通過(guò)。 設(shè)：5個(gè)信號(hào)量ST、TS、K、L、M，ST表示是否允許自行車從南大到天大，TS表示是否允許自行車從天大到南大，K表示是否允許自行車通過(guò)路段SK，L表示是否允許自行車通過(guò)路段TL，M表示安全島上還可以停放自行車的數(shù)目 。其

23、工作流程如圖所示。 int fork1=fork2=knife1=knife2=1 ; cobegin totian() / tonan() coend,進(jìn)程的互斥,思考： 在totian()中，P(ST)與P(K) 互換位置，會(huì)對(duì)進(jìn)程產(chǎn)生 什么影響？若P(M)與V(K)， P(L)與V(M)，V(L)與V(ST) 互換位置呢？,小結(jié) 進(jìn)程互斥：進(jìn)程之間要競(jìng)爭(zhēng)臨界資源。 信號(hào)量表示臨界資源是否可用，或臨界資源的數(shù)量。 信號(hào)量的個(gè)數(shù)與臨界資源的個(gè)數(shù)一致。 對(duì)同一個(gè)信號(hào)量的PV操作要在同一個(gè)進(jìn)程中完成。 P操作：進(jìn)入臨界區(qū)前 V操作：離開(kāi)臨界區(qū)后,進(jìn)程的互斥,進(jìn)程的同步與互斥,解題步驟： 確定各個(gè)

24、進(jìn)程的工作步； 確定進(jìn)程的哪些工作是同步關(guān)系，哪些工作是互斥關(guān)系； 同步：有時(shí)序關(guān)系的 互斥：競(jìng)爭(zhēng)臨界資源的 確定信號(hào)量含義及初值； 寫出偽代碼。,例1：讀寫環(huán)形緩沖區(qū)。設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū)（如圖所示），A進(jìn)程順序地把信息寫進(jìn)緩沖區(qū)，B進(jìn)程依次從緩沖區(qū)中讀出信息，請(qǐng)用PV操作描述A、B進(jìn)程的同步。（生產(chǎn)者-消費(fèi)者問(wèn)題）,進(jìn)程的同步與互斥,進(jìn)程A 寫數(shù)據(jù)； ,進(jìn)程B 讀數(shù)據(jù)； ,分析：這是一個(gè)具有多個(gè)緩沖空間的生產(chǎn)者消費(fèi)者問(wèn)題，也是一個(gè)同步加互斥的問(wèn)題。A、B 兩個(gè)進(jìn)程對(duì)緩沖區(qū)的訪問(wèn)必須互斥。并且當(dāng)緩沖區(qū)滿時(shí)，A進(jìn)程不能寫入，必須等待；當(dāng)緩沖區(qū)空時(shí)，B進(jìn)程不能讀，必須等待，讀寫進(jìn)

25、程之間又是同步問(wèn)題。 設(shè)：3個(gè)信號(hào)量：互斥信號(hào)量S = 1（表示對(duì)緩沖區(qū)的互斥使用）；同步信號(hào)量Sw（代表緩沖區(qū)是否有空閑，即寫進(jìn)程能否寫）、Sr（代表緩沖區(qū)是否有數(shù)據(jù)，即讀進(jìn)程能否讀），假設(shè)初始時(shí)緩沖區(qū)沒(méi)有任何數(shù)據(jù)，則Sw = N，Sr = 0。設(shè)一個(gè)數(shù)組array表示緩沖區(qū)，兩個(gè)整型變量in、out表示寫入和讀出的位置。其工作流程如圖所示。 #define N 10; int arrayN，in=0，out=0; int S=1，Sw=N，Sr=0; cobegin PA() / PB() coend,進(jìn)程的同步與互斥,例2：理發(fā)師理發(fā)。理發(fā)師理發(fā)問(wèn)題。有一個(gè)理發(fā)師、一把理發(fā)椅和n把等候理

26、發(fā)顧客坐的椅子。如果沒(méi)有顧客，則理發(fā)師在理發(fā)椅上睡覺(jué)；當(dāng)一個(gè)顧客到來(lái)時(shí)，必須喚醒理發(fā)師，進(jìn)行理發(fā)；當(dāng)理發(fā)師正在理發(fā)，又有顧客來(lái)到時(shí)，如果有空椅子，顧客就可以坐下來(lái)等候，如果沒(méi)有空椅子，他就離開(kāi)。請(qǐng)為理發(fā)師和顧客各編一個(gè)程序表述他們的行為。,進(jìn)程的同步與互斥,barber 給顧客理發(fā)； ,customer 坐下等候； 理發(fā)； ,分析：本題涉及兩個(gè)進(jìn)程：理發(fā)師和顧客。當(dāng)有顧客時(shí)理發(fā)師就可以理發(fā)，理完發(fā)后，從等候的顧客中選一位顧客繼續(xù)理發(fā)。當(dāng)理發(fā)師正在理發(fā)時(shí)，顧客要等待，若沒(méi)有座位就離開(kāi)，顧客與理發(fā)師的工作是同步關(guān)系。有多少顧客在等候，需設(shè)計(jì)一個(gè)計(jì)數(shù)器來(lái)記錄，顧客和理發(fā)師對(duì)計(jì)數(shù)器的操作是互斥的。所以

27、，這是一個(gè)同步加互斥的問(wèn)題。 設(shè)：3個(gè)信號(hào)量：S1表示理發(fā)師是否可以開(kāi)始理發(fā)，即是否有顧客；S2表示顧客是否可以被理發(fā)，即是否有理發(fā)師；S3是對(duì)計(jì)數(shù)器waiting的互斥操作；waiting表示等待顧客的人數(shù)。其工作流程如圖所示。 #define CHAIR 10; int S1=0，S2=0，S3=1，waiting=0; cobegin barber() / customer() coend,進(jìn)程的同步與互斥,例3：?jiǎn)涡兴淼绬?wèn)題。對(duì)一個(gè)單行的隧道進(jìn)行模擬，為了避免死鎖，必須防止汽車同時(shí)從兩端進(jìn)入隧道。如果一次只允許一輛車通過(guò)隧道，兩個(gè)方向按車輛到達(dá)的先后順序依次通過(guò)，請(qǐng)用pv操作設(shè)計(jì)一個(gè)算

28、法實(shí)現(xiàn)這個(gè)控制。,進(jìn)程同步與互斥的綜合例題,P1() 通過(guò)隧道； ,P2() 通過(guò)隧道； ,分析：本題涉及兩個(gè)進(jìn)程：P1和P2。隧道是一個(gè)臨界資源，一次只能被一輛車占有，可以把它看作互斥問(wèn)題。 設(shè)：一個(gè)互斥信號(hào)量sd=1，表示隧道是否可用。 int sd=1; cobegin P1() / P2() coend,進(jìn)程同步與互斥的綜合例題,P1() P(sd); 通過(guò)隧道； V(sd); ,P2() P(sd); 通過(guò)隧道； V(sd); ,問(wèn)題： 兩個(gè)方向車輛通過(guò)隧道的交換比較平凡， 系統(tǒng)效率不高,分析：為了提高效率，把問(wèn)題改為：一旦一輛車進(jìn)入，則同一方向的車可以立即跟進(jìn)。寫出用信號(hào)量解決此問(wèn)

29、題的代碼，不考慮“饑餓”的情況。(按照讀者-寫者問(wèn)題處理) 設(shè)：3個(gè)信號(hào)量：c表示計(jì)數(shù)器，m表示對(duì)臨界資源計(jì)數(shù)器的控制，sd表示對(duì)臨界資源隧道的控制，即隧道是否可用。 int c=0,m=1,sd=1; cobegin P1() / P2() coend,進(jìn)程同步與互斥的綜合例題,P2() P(sd); 通過(guò)隧道； V(sd); ,P1() P(m); /* m1控制計(jì)數(shù)器c1 */ if (c= 0 ) P(sd); /*p1第一輛車通過(guò)時(shí)占有隧道*/ c=c+1; V(m); 通過(guò)隧道； P(m); c=c-1; if(c=0) V(sd); /*p1最后一輛車通過(guò)后釋放隧道 */ V(m

30、); ,問(wèn)題： 若P1過(guò)隧道，則后續(xù)車輛可以跟進(jìn)； 若p2過(guò)隧道，一次只能過(guò)一輛； P1不會(huì)產(chǎn)生“饑餓”的現(xiàn)象，而p2會(huì)產(chǎn)生“饑餓”的現(xiàn)象。,分析：解決p2“饑餓”現(xiàn)象的方法：再設(shè)一個(gè)信號(hào)量k，讓p1、p2排隊(duì)，可以做到p1方向比p2方向晚來(lái)的車輛被k阻止。 int c=0,m=1,sd=1,k=1; cobegin P1() / P2() coend,進(jìn)程同步與互斥的綜合例題,P2() P(k); P(sd); 通過(guò)隧道； V(sd); V(k); ,P1() P(k); /* 與P2一起排隊(duì) */ P(m); /* m1控制計(jì)數(shù)器c */ if (c= 0 ) P(sd); /*P1第一輛

31、車通過(guò)時(shí)占有隧道*/ c=c+1; V(m); V(k); 通過(guò)隧道； P(m); c=c-1; if(c=0) V(sd); /*P1最后一輛車通過(guò)后釋放隧道 */ V(m); ,問(wèn)題： 若P1過(guò)隧道，則后續(xù)車輛可以跟進(jìn)； 若p2過(guò)隧道，一次只能過(guò)一輛 。,分析：解決p2可以過(guò)多輛車的方法：按照讀者-讀者問(wèn)題處理。即：p1為讀者，p2為讀者，但兩個(gè)讀者不能同時(shí)讀 。 int c1=c2=0,m1=m2=1,sd=1; /c1、c2為計(jì)數(shù)器，m1、m2為互斥信號(hào)量 cobegin P1() / P2() coend,進(jìn)程同步與互斥的綜合例題,P1() P(m1); if (c1= 0 ) P(

32、sd); c1=c1+1; V(m1); 通過(guò)隧道； P(m1); c1=c1-1; if(c1=0) V(sd); V(m1); ,問(wèn)題： 若P1過(guò)隧道，則后續(xù)車輛可以跟進(jìn)，有可能使p2“饑餓” 若P2過(guò)隧道，則后續(xù)車輛也可以跟進(jìn)，有可能使p1“饑餓”,P2() P(m2); if (c2= 0 ) P(sd); c2=c2+1; V(m2); 通過(guò)隧道； P(m2); c2=c2-1; if(c2=0) V(sd); V(m2); ,假設(shè)：?jiǎn)栴}改為：一旦一輛車進(jìn)入，則同一方向的車可以立即跟進(jìn)，隧道最多只能過(guò)4輛車，如何修改算法？ int c1=c2=0,m1=m2=1,sd=1,k1=4,k2=4 ; /c1、c2為計(jì)數(shù)器，m1、m2為互斥信號(hào)量 cobegin /k1、k2為控制各自方向上通過(guò)的車輛數(shù) P1() / P2() coend,進(jìn)程同步與互斥的綜合例題,P1() P(k1); P(m1); if (c1= 0 ) P(sd); c1=