進(jìn)程同步與互斥_問(wèn)題.ppt_第1頁(yè)
進(jìn)程同步與互斥_問(wèn)題.ppt_第2頁(yè)
進(jìn)程同步與互斥_問(wèn)題.ppt_第3頁(yè)
進(jìn)程同步與互斥_問(wèn)題.ppt_第4頁(yè)
進(jìn)程同步與互斥_問(wèn)題.ppt_第5頁(yè)
已閱讀5頁(yè),還剩42頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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=

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論