第三章進(jìn)程管理5

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

2、有一個(gè)是滿的n互斥問題：任一時(shí)刻只能有一個(gè)進(jìn)程可以對(duì)緩沖區(qū)操作共享緩沖區(qū)共享緩沖區(qū)P 1P 2. PmC 1C 2.Cn用P、V原語實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問題n解：1）設(shè)私用信號(hào)量avail表示緩沖區(qū)中的空單元數(shù)，full表示緩沖區(qū)中的滿單元數(shù)；公用信號(hào)量mutex表示整個(gè)緩沖區(qū)是否在使用n 2）設(shè)初始值avail=n，full=0，mutex=1n 3）描述生產(chǎn)者-消費(fèi)者問題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原語實(shí)現(xiàn)哲學(xué)家問題n例1：5個(gè)哲學(xué)家在圓桌前進(jìn)餐，兩個(gè)人之間各放一根筷子。哲學(xué)家或者思考或者分別取左右手邊的筷子進(jìn)餐。請(qǐng)用P、V原語描述每個(gè)哲學(xué)家的進(jìn)餐過程。0123414032用P、V原語實(shí)現(xiàn)哲學(xué)家問題n解：1）設(shè)公用信號(hào)量si表示是否能取到第i個(gè)筷子（i=0,1,2,3,4 ）n 2）設(shè)初始值，si=1 （i=0,1,2,3,4 ）n 3）描述第i個(gè)哲學(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原語實(shí)現(xiàn)哲學(xué)家問題(完整)n解：1）設(shè)公用信號(hào)量mutex表示哲學(xué)家是否能同時(shí)取到2個(gè)筷子，si表示是否能取到第I個(gè)筷子（i=0,1,2,3,4 ）n 2）設(shè)初始值mutex=1，si=1 （i=0,1,2,3,4 ）n 3）描述第i個(gè)哲學(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原語實(shí)現(xiàn)同步n例2 設(shè)公共汽車上，司機(jī)和售票員的活動(dòng)如下。在汽車不斷到站停車、行駛過程中，這兩個(gè)活動(dòng)有什

5、么同步關(guān)系？用P、V原語實(shí)現(xiàn)他們的同步。用P、V原語實(shí)現(xiàn)同步n1 1）設(shè)）設(shè)closeclose為進(jìn)程為進(jìn)程P1P1的私有信號(hào)量，表示售票員是否的私有信號(hào)量，表示售票員是否關(guān)門，關(guān)門，stopstop為進(jìn)程為進(jìn)程P2P2的私有信號(hào)量，表示車輛是否停的私有信號(hào)量，表示車輛是否停止到站。止到站。n2 2）設(shè)初始值）設(shè)初始值close=1close=1，stop=0stop=0，表示車正在運(yùn)行。，表示車正在運(yùn)行。n3 3）描述：）描述：P1: P1: A:P(close) A:P(close) 啟動(dòng)啟動(dòng) 行車行車 停車停車 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è)有一個(gè)作業(yè)由四個(gè)進(jìn)程組成，這四個(gè)進(jìn)程在運(yùn)行時(shí)必須按圖所示的順序，用P、V原語操作表達(dá)四個(gè)進(jìn)程的同步關(guān)系。T1T3T2T4n解：1）設(shè)同步（私有）信號(hào)量 s12，s13，s24，s34分別用于T1與T2，T1與T3，T2與T4，T3與T4之間進(jìn)行同步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原語實(shí)現(xiàn)進(jìn)程同步和互斥n例4：某寺廟，有小、老和尚若干。寺廟有一水缸，可容10桶水，由小和尚提水入缸、取水出缸供老和尚飲用，每次入水、取水僅為1桶，且不可同時(shí)進(jìn)行。水取自同一井中，口窄，每次只能容一個(gè)桶取水。水桶總數(shù)為3個(gè)。用P、V原語給出取水入水的算法描述井缸入水出水用P、V原語實(shí)現(xiàn)進(jìn)程同步和互斥n解：1）設(shè)公用信號(hào)量mutex1，mutex2分別控制井和缸的互斥，count表示空閑的水桶數(shù)；私用信號(hào)量empty表示缸中還可以入幾桶水，full表示

8、缸中已入幾桶水n 2）設(shè)初始值mutex1=1，mutex2=1，empty=10，full=0，count=3n 3）描述用P、V原語實(shí)現(xiàn)進(jì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原語實(shí)現(xiàn)進(jìn)程同步和互斥n例5：某車站售票廳有20個(gè)

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

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

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

12、由一個(gè)人使用，用P、V原語描述一個(gè)讀者進(jìn)入和出來的過程。n分析：n1）互斥問題：登記表同時(shí)只能由一個(gè)人使用n2）同步問題：讀者進(jìn)入時(shí)，100個(gè)座位至少由 一個(gè)是空的，出來時(shí)，要釋放所占有的座位用P、V原語實(shí)現(xiàn)進(jìn)程互斥與同步n解：1）設(shè)私用信號(hào)量avail表示閱覽室中的空座位數(shù)，公用信號(hào)量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原語實(shí)現(xiàn)進(jìn)程同步和互斥n例8：某理發(fā)師，當(dāng)沒有顧客時(shí)，理發(fā)師去睡

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

14、語實(shí)現(xiàn)進(jìn)程同步和互斥n例9：某工廠有兩個(gè)生產(chǎn)車間和一個(gè)裝配車間。兩個(gè)生產(chǎn)車間分別生產(chǎn)A、B兩種零件，每生產(chǎn)一個(gè)零件后都要分別把它們送到裝配車間的貨架F1、F2上，F(xiàn)1上放零件A，F(xiàn)2上放零件B， F1和 F2的容量均為10個(gè)零件，裝配工人每次從架上取一個(gè)零件A和一個(gè)零件B，然后組裝成產(chǎn)品，請(qǐng)用P、V原語進(jìn)行正確管理。A車間B車間F1F2裝配工人ABBA用P、V原語實(shí)現(xiàn)進(jìn)程同步和互斥n解：1）設(shè)公用信號(hào)量mutex1、mutex2控制進(jìn)程對(duì)F1、F2的互斥操作；私用信號(hào)量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原語實(shí)現(xiàn)進(jìn)程同步和互斥nA車間nL1:生產(chǎn)一個(gè)An P(empty1)n P(mutex1)n 放入F1上n V(mutex1)n V(full1)n Goto L1n B車間nL2:生產(chǎn)一個(gè)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原語實(shí)現(xiàn)進(jìn)程同步和互斥n兩個(gè)進(jìn)程PA和PB通過兩個(gè)FIFO緩沖區(qū)隊(duì)列連接（設(shè)緩沖區(qū)隊(duì)列的緩沖區(qū)個(gè)數(shù)都為n個(gè)），每個(gè)緩沖區(qū)長(zhǎng)度等于傳送消息長(zhǎng)度。進(jìn)程PA和PB之間的通信滿足如下條件：n至少有一個(gè)空緩沖區(qū)存在時(shí)，相應(yīng)的發(fā)送進(jìn)程才能發(fā)送一個(gè)消息。n當(dāng)緩沖隊(duì)列中至少存在一個(gè)非空緩沖區(qū)時(shí)，相應(yīng)的接收進(jìn)程才能接收一個(gè)消息。PAPB緩沖區(qū)隊(duì)列1緩沖區(qū)隊(duì)列2n試描述對(duì)第1個(gè)緩沖隊(duì)列操作的發(fā)送過程send(1 , m)和接收過程receive(1 , m)。對(duì)第2個(gè)緩沖隊(duì)列操作的發(fā)送過程send(2 , m)和接收過程receive(2 , m)

17、。這里1和2分別代表緩沖隊(duì)列1和緩沖隊(duì)列2，m代表消息。PAPB緩沖區(qū)隊(duì)列1緩沖區(qū)隊(duì)列2n解：n1）設(shè)私有信號(hào)量bufempty1,buffull1, bufempty2,buffull2用于進(jìn)程PA和PB之間進(jìn)行同步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方式選擇一個(gè)空緩沖區(qū)buf(x)n Buf(x) 消息mn buf(x)置滿標(biāo)記n V(buffull1)nEndnreceive(1,m)nBeginn Local xn P (buffull1)n 按FIFO方式選擇一個(gè)滿緩沖區(qū)buf(x)n