進程同步與互斥_問題.ppt

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

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

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

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

5、ile (true) while (true) while(true) 洗水果； 取桔子； 取蘋果； 放水果； 吃桔子； 吃蘋果； ,桔子,父親,兒子,女兒,0,蘋果,分析：父親先放水果，兒子女兒再吃水果；兒子女兒取完水果，父親再放水果，這三個進程是一個同步關系。 解法一：設信號量m1表示父親能否放水果，m2表示兒子能否取桔子，m3表示女兒能否取蘋果。 int m1=1,m2=0,m3=0； cobegin p1() / p2() / p3() coend,進程的同步,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)； 吃蘋果； ,分析：父親先放水果，兒子女兒再吃水果；兒子女兒取完水果，父親再放水果，這三個進程是一個同步關系。 解法二：設信號量m1表示父親放完桔子，m2表示父親放完蘋果，m3表示兒子女兒取完水果。 int m1=0,m2=0,m3=1； cobegin p1() / p2() / p3() coend,進程的同步,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)； 吃蘋果； ,進程的同步,例3-3：吃水果。,父親 P1 母親 P2 兒子 P3 while (true) while (true) while(true) 洗桔子； 洗蘋果； 取水果； 放桔子； 放蘋果； 吃水果； ,0,父親,兒子,母親,桔子,蘋果,分析：父母親先放水果，兒子再取水果吃；父親與兒子，母親與兒子是一個同步關系，父親與母親要競爭空盤子。 解法一：設信號量m1表示是否有空盤子，信號量m2表示兒子能否取水果。 int m1=1,m2=0； cobegi

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

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

10、同步關系，父親與母親要競爭空盤子。 解法一：設信號量m1表示是否有空盤子，信號量m2表示兒子能否取蘋果，m3表示女兒能否取桔子。 int m1=1,m2=0,m3=0； cobegin p1() / p2() / p3() / p4() coend,進程的同步,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、水果，兒子再取水果吃；父親與兒子，母親與兒子是一個同步關系，父親與母親要競爭空盤子。 解法二：設信號量m1表示父親放完桔子，m2表示母親放完蘋果，信號量m3表示兒子或女兒取完水果。 int m1=0,m2=0,m3=1； cobegin p1() / p2() / p3() / p4() coend,進程的同步,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)； 吃桔子； ,進程的同步,例4：打印文件。,P1 P2 P3 while (true) while (true) while(true) 從磁盤取文件； 從緩沖1取文件； 從緩沖2取文件； 放入緩沖1； 放入緩沖2； 打印文件； ,緩沖1,磁盤,打印機,緩沖2,P1,P2,P3,分析：P1做完，P2才能做，P2做完，P3才能做。這三個進程是一個同步關系。 解法一：設信號量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,進程的同步,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個文件，緩沖2可以存放 m個文件，如何修改同步關系？ 2.如果P2改為如下形式，會有何影響？,int m1=n,m2=0,m3=m,m4=0；,P(m2) ； P(m3); 從緩沖1取文件； 放入緩沖2； V(m

14、1)； V(m4)；,進程的并發(fā)性不如修改前,分析：P1做完，P2才能做，P2做完，P3才能做。這三個進程是一個同步關系。 解法二：設信號量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,進程的同步,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īng)結(jié)束。 信號量的個數(shù)與進程的個數(shù)一致，有時可以省略部分信號量。 對同一個信號量的PV操作不在一個進程中。 表示開始：P自己，V別人 表示結(jié)束：P別人，V自己,進程的同步,進程互斥,進程互斥： 并發(fā)進程之間相互競爭臨界資源的排他性關系。 解題步驟： 確定臨界資源及個數(shù)； 確定進程的關鍵工作步（使用臨界資源的）； 確定信號量的初值； 寫出偽代碼。,例1：過獨木橋。,進程的互斥,P1 P2 由西向東過獨木橋； 由東向西

16、過獨木橋； ,P1,P2,分析：進程P1、P2因競爭獨木橋這個資源而成為互斥關系。 設：信號量m表示獨木橋資源，初值為1表示資源可用。 int m=1; cobegin p1() / p2() coend,進程的互斥,p1() P(m) ； 通過獨木橋； V(m) ； ,p2() P(m) ； 通過獨木橋； V(m)； ,練習：過十字路口（單道）。,進程的互斥,P1 P2 P3 P4 通過路口； 通過路口； 通過路口； 通過路口； ,P2,P3,P4,P1,分析：進程P1、P2、P3、P4因競爭十字路口這個資源而成為互斥關系。 設：信號量m表示十字路口資源，初值為1表示資源可用。 int m=

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

18、讀數(shù)據(jù)庫。請用信號量及PV操作描述這一組進程的工作過程。（讀者-寫者問題）,進程的互斥,數(shù)據(jù)庫,寫 者,讀 者,寫者 讀者 寫數(shù)據(jù)庫； 讀數(shù)據(jù)庫； ,分析：寫進程writer、讀進程reader因競爭數(shù)據(jù)庫這個資源而成為互斥關系。因為寫進程執(zhí)行時，不能執(zhí)行其他讀寫進程，所以還必須設置一個計數(shù)器統(tǒng)計讀進程的個數(shù)。如果是第一個讀進程，就與寫進程競爭數(shù)據(jù)庫。如果是最后一個讀進程，就釋放數(shù)據(jù)庫。因計數(shù)器是一個臨界資源，所以多個讀進程對計數(shù)器的操作又是互斥操作。 設：信號量rmutex表示數(shù)據(jù)庫資源，初值為1表示資源可用；wmutex表示計數(shù)器count資源，初值為1表示可用。 int rmutex=1

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

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

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

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

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

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

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

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

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

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

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

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

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

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