第三章進程管理5

1、復(fù)習(xí)n進程間的制約關(guān)系有哪兩種？n什么是進程互斥？什么是進程同步？n什么是私用信號量？什么是公用信號量？各用于何處？n解決進程互斥和同步問題的步驟是什么？第三章 進程管理習(xí)題課生產(chǎn)者-消費者問題n把并發(fā)進程同步和互斥問題一般化，得到一個抽象的模型，即生產(chǎn)者消費者問題n生產(chǎn)者：釋放某一類資源的進程n消費者：使用某一類資源的進程n問題描述：若干個進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)，其中生產(chǎn)者進程不斷寫入，消費者進程不斷讀出，共享緩沖區(qū)共有n個，任一時刻只能有一個進程對整個共享緩沖區(qū)進行操作生產(chǎn)者-消費者問題n分析：n1）同步問題：生產(chǎn)者想寫入時，緩沖區(qū)中至少有一個時空的，消費者想讀出時，緩沖區(qū)中至少

2、有一個是滿的n互斥問題：任一時刻只能有一個進程可以對緩沖區(qū)操作共享緩沖區(qū)共享緩沖區(qū)P 1P 2. PmC 1C 2.Cn用P、V原語實現(xiàn)生產(chǎn)者-消費者問題n解：1）設(shè)私用信號量avail表示緩沖區(qū)中的空單元數(shù)，full表示緩沖區(qū)中的滿單元數(shù)；公用信號量mutex表示整個緩沖區(qū)是否在使用n 2）設(shè)初始值avail=n，full=0，mutex=1n 3）描述生產(chǎn)者-消費者問題n注意:P操作順序很重要：先檢查是否有資源可用，再檢查是否互斥；V操作順序無所謂Producer:P(avail);P(mutex);將數(shù)據(jù)送入緩沖區(qū)某單元將數(shù)據(jù)送入緩沖區(qū)某單元V(mutex);V(full);Consum

3、er:P(full);P(mutex);取緩沖區(qū)中某單元數(shù)據(jù)取緩沖區(qū)中某單元數(shù)據(jù)V(mutex);V(avail);用P、V原語實現(xiàn)哲學(xué)家問題n例1：5個哲學(xué)家在圓桌前進餐，兩個人之間各放一根筷子。哲學(xué)家或者思考或者分別取左右手邊的筷子進餐。請用P、V原語描述每個哲學(xué)家的進餐過程。0123414032用P、V原語實現(xiàn)哲學(xué)家問題n解：1）設(shè)公用信號量si表示是否能取到第i個筷子（i=0,1,2,3,4 ）n 2）設(shè)初始值，si=1 （i=0,1,2,3,4 ）n 3）描述第i個哲學(xué)家Pi：Pi:repeat think P(si) P(s(i+1) mod 5) eat V(si) V (s(i

4、+1) mod 5) Until false用P、V原語實現(xiàn)哲學(xué)家問題(完整)n解：1）設(shè)公用信號量mutex表示哲學(xué)家是否能同時取到2個筷子，si表示是否能取到第I個筷子（i=0,1,2,3,4 ）n 2）設(shè)初始值mutex=1，si=1 （i=0,1,2,3,4 ）n 3）描述第i個哲學(xué)家Pi：Pi:repeat think P(mutex) P(si) P(s(i+1) mod 5) V(mutex) eat V(si) V (s(i+1) mod 5) Until false用P、V原語實現(xiàn)同步n例2 設(shè)公共汽車上，司機和售票員的活動如下。在汽車不斷到站停車、行駛過程中，這兩個活動有什

5、么同步關(guān)系？用P、V原語實現(xiàn)他們的同步。用P、V原語實現(xiàn)同步n1 1）設(shè)）設(shè)closeclose為進程為進程P1P1的私有信號量，表示售票員是否的私有信號量，表示售票員是否關(guān)門，關(guān)門，stopstop為進程為進程P2P2的私有信號量，表示車輛是否停的私有信號量，表示車輛是否停止到站。止到站。n2 2）設(shè)初始值）設(shè)初始值close=1close=1，stop=0stop=0，表示車正在運行。，表示車正在運行。n3 3）描述：）描述：P1: P1: A:P(close) A:P(close) 啟動啟動 行車行車 停車停車 V(stop)V(stop) Goto A Goto AP2: P2: B:

6、P(stop) B:P(stop) 開門開門 關(guān)門關(guān)門 V(close)V(close) 售票售票 Goto BGoto Bn例3 設(shè)有一個作業(yè)由四個進程組成，這四個進程在運行時必須按圖所示的順序，用P、V原語操作表達四個進程的同步關(guān)系。T1T3T2T4n解：1）設(shè)同步（私有）信號量 s12，s13，s24，s34分別用于T1與T2，T1與T3，T2與T4，T3與T4之間進行同步n2）設(shè)初始值s12=0，s13=0，s24=0，s34=0n3）PV原語描述：T1( ) begin T1; V(s12); V(s13); endT2() begin P(s12); T2; V(s24); end

7、T3() begin P(s13); T3; V(s34); endT4( ) begin P(s24); P(s34); T4; end用P、V原語實現(xiàn)進程同步和互斥n例4：某寺廟，有小、老和尚若干。寺廟有一水缸，可容10桶水，由小和尚提水入缸、取水出缸供老和尚飲用，每次入水、取水僅為1桶，且不可同時進行。水取自同一井中，口窄，每次只能容一個桶取水。水桶總數(shù)為3個。用P、V原語給出取水入水的算法描述井缸入水出水用P、V原語實現(xiàn)進程同步和互斥n解：1）設(shè)公用信號量mutex1，mutex2分別控制井和缸的互斥，count表示空閑的水桶數(shù)；私用信號量empty表示缸中還可以入幾桶水，full表示

8、缸中已入幾桶水n 2）設(shè)初始值mutex1=1，mutex2=1，empty=10，full=0，count=3n 3）描述用P、V原語實現(xiàn)進程同步和互斥n入水：nL1:P(empty)n P(count)n P(mutex1)n 從井中取水n V(mutex1)n P(mutex2)n 送水入缸n V(mutex2)n V(count)n V(full)n Goto L1n取水：nL2:P(full)n P(count)n P(mutex2)n 從缸中取水n V(mutex2)n V(count)n V(empty)n Goto L2用P、V原語實現(xiàn)進程同步和互斥n例5：某車站售票廳有20個

9、窗口，任何時刻最多可容納20名購票者進入，當(dāng)售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在廳外等待。若把購票者看做一個進程，請用P，V操作管理這些進程，要求如下：(1)在主函數(shù)中給出信號量的定義和初值。(2)給出一個購票者進程的算法(3)給出當(dāng)購票者最多不超過n(設(shè)n20)個時，信號量可能的變化范圍。用P、V原語實現(xiàn)進程同步和互斥(1)主函數(shù)算法 (2)購票者i的算法main() pi() int mutex=20; p(mutex); cobegin 進入售票廳 占有一個窗口購票; p1();p2();pi();pn(); v(mutex); coend （3）信號量最大值為

10、20，最小值為20-n用P、V原語實現(xiàn)進程同步和互斥 例例6：桌上有一空盤，允許存放一只水果。爸：桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時一次只能放一只水果供吃者取用，規(guī)定當(dāng)盤空時一次只能放一只水果供吃者取用，請用請用P，V原語實現(xiàn)爸爸，兒子，女兒原語實現(xiàn)爸爸，兒子，女兒3個并發(fā)個并發(fā)進程的同步。進程的同步。解答n1）設(shè)同步信號量empty表示盤子是否為空，orange和apple分別表示盤子中放了橘子或蘋果n2）設(shè)初值empty

11、=1， orange=apple=0，表示盤子為空父親進程父親進程()： while(1) P(empty); 往盤中放水果往盤中放水果; if(水果水果=橘子橘子) V(orange); else V(apple); 兒子進程兒子進程()： while(沒吃夠沒吃夠)P(orange); 從盤中取橘子從盤中取橘子;V(empty); 女兒進程女兒進程()： while(沒吃夠沒吃夠) P(apple);從盤中取蘋果從盤中取蘋果; V(empty); 用P、V原語實現(xiàn)進程互斥與同步n例7：圖書館閱覽室有100個座位，一張登記表，要求閱讀者進入時登記，取得座位號，出來時注銷座位號。登記表同時只能

12、由一個人使用，用P、V原語描述一個讀者進入和出來的過程。n分析：n1）互斥問題：登記表同時只能由一個人使用n2）同步問題：讀者進入時，100個座位至少由 一個是空的，出來時，要釋放所占有的座位用P、V原語實現(xiàn)進程互斥與同步n解：1）設(shè)私用信號量avail表示閱覽室中的空座位數(shù)，公用信號量mutex表示登記表是否正在使用n 2）設(shè)初始值avail=100，mutex=1n 3）描述：Enter: P(avail) P(mutex) 登記 V(mutex)Leave: P(mutex) 注銷 V(mutex) V(avail)用P、V原語實現(xiàn)進程同步和互斥n例8：某理發(fā)師，當(dāng)沒有顧客時，理發(fā)師去睡

13、覺；若有顧客進來時理發(fā)師正在睡覺，則這個顧客會叫醒他。試用P、V操作描述協(xié)調(diào)理發(fā)師和顧客之間的同步問題（假設(shè)理發(fā)店里等候服務(wù)的隊伍可以無限長）用P、V原語實現(xiàn)進程同步和互斥n解：1）設(shè)私用信號量customers表示等候服務(wù)的顧客數(shù)，barber表示已經(jīng)做好理發(fā)準備的理發(fā)師個數(shù)n 2）設(shè)初始值customers=0， barber=0，表示沒有顧客，理發(fā)師正在睡覺n 3）描述：用P、V原語實現(xiàn)進程同步和互斥n理發(fā)師：nrepeatn P(customers)n V(barber)n 給顧客理發(fā)nUntil falsen顧客：nV(customers)nP(barber)n獲得理發(fā)服務(wù)用P、V原

14、語實現(xiàn)進程同步和互斥n例9：某工廠有兩個生產(chǎn)車間和一個裝配車間。兩個生產(chǎn)車間分別生產(chǎn)A、B兩種零件，每生產(chǎn)一個零件后都要分別把它們送到裝配車間的貨架F1、F2上，F(xiàn)1上放零件A，F(xiàn)2上放零件B， F1和 F2的容量均為10個零件，裝配工人每次從架上取一個零件A和一個零件B，然后組裝成產(chǎn)品，請用P、V原語進行正確管理。A車間B車間F1F2裝配工人ABBA用P、V原語實現(xiàn)進程同步和互斥n解：1）設(shè)公用信號量mutex1、mutex2控制進程對F1、F2的互斥操作；私用信號量empty1、empty2、full1、full2分別表示F1空位數(shù)，F(xiàn)2空位數(shù)，F(xiàn)1上零件數(shù)，F(xiàn)2上零件數(shù)n 2）初始化mu

15、tex1=1，mutex2=1，empty1=10，empty2=10，full1=0，full2=0n 3）描述：用P、V原語實現(xiàn)進程同步和互斥nA車間nL1:生產(chǎn)一個An P(empty1)n P(mutex1)n 放入F1上n V(mutex1)n V(full1)n Goto L1n B車間nL2:生產(chǎn)一個Bn P(empty2)n P(mutex2)n 放入F2上n V(mutex2)n V(full2)n Goto L2l裝配工人lL3:P(full1)l P(full2)l P(mutex1)l P(mutex2)l 取AB零件裝配l V(mutex1)l V(mutex2)l

16、V(empty1)l V(empty2)l Goto L3用P、V原語實現(xiàn)進程同步和互斥n兩個進程PA和PB通過兩個FIFO緩沖區(qū)隊列連接（設(shè)緩沖區(qū)隊列的緩沖區(qū)個數(shù)都為n個），每個緩沖區(qū)長度等于傳送消息長度。進程PA和PB之間的通信滿足如下條件：n至少有一個空緩沖區(qū)存在時，相應(yīng)的發(fā)送進程才能發(fā)送一個消息。n當(dāng)緩沖隊列中至少存在一個非空緩沖區(qū)時，相應(yīng)的接收進程才能接收一個消息。PAPB緩沖區(qū)隊列1緩沖區(qū)隊列2n試描述對第1個緩沖隊列操作的發(fā)送過程send(1 , m)和接收過程receive(1 , m)。對第2個緩沖隊列操作的發(fā)送過程send(2 , m)和接收過程receive(2 , m)

17、。這里1和2分別代表緩沖隊列1和緩沖隊列2，m代表消息。PAPB緩沖區(qū)隊列1緩沖區(qū)隊列2n解：n1）設(shè)私有信號量bufempty1,buffull1, bufempty2,buffull2用于進程PA和PB之間進行同步n2）設(shè)初始值bufempty1=n,buffull1=0, bufempty2=n,buffull2=0n3）描述PA調(diào)用 PB調(diào)用nSend(1,m)nBeginn Local xn P (bufempty1)n 按FIFO方式選擇一個空緩沖區(qū)buf(x)n Buf(x) 消息mn buf(x)置滿標記n V(buffull1)nEndnreceive(1,m)nBeginn Local xn P (buffull1)n 按FIFO方式選擇一個滿緩沖區(qū)buf(x)n