操作系統(tǒng)進(jìn)程的同步與通信

1、第3章 進(jìn)程的同步與通信3.2 例題解析例 多道程序系統(tǒng)程序的執(zhí)行失去了封閉性和再現(xiàn)性，因此多道程序的執(zhí)行不需要這些特性，這種說法是否正確 ？解 這種說法不正確?？梢韵胂?，如果一個(gè)程序在多道程序系統(tǒng)中，在相同的輸入的情況下，多次執(zhí)行所得結(jié)果是不同的，有誰還敢使用這個(gè)程序？因此，多道程序的執(zhí)行也需要封閉性和再現(xiàn)性，只不過單道程序系統(tǒng)的封閉性和再現(xiàn)性是先天固有的，多道程序系統(tǒng)的程序執(zhí)行要想獲得封閉性和再現(xiàn)性，需通過程序員的精心設(shè)計(jì)才能得到。所使用的方法就是同步和互斥的方法。例3.2.2 多個(gè)進(jìn)程對(duì)信號(hào)量S進(jìn)行了5次 P操作，2次V操作后，現(xiàn)在信號(hào)量的值是 -3，與信號(hào)量S相關(guān)的處于阻塞狀態(tài)的進(jìn)程有

2、幾個(gè)？信號(hào)量的初值是多少？ 解 (1) 因?yàn)镾的當(dāng)前值是-3，因此因?yàn)镾處于阻塞狀態(tài)的進(jìn)程有3個(gè)；(2) 因?yàn)槊窟M(jìn)行一次P(S)操作，S的值都減1，每執(zhí)行1次V操作S的值加1，故信號(hào)量的初值為-3+5-2=0;例3.2.3 如下鎖的實(shí)現(xiàn)方法存在什么缺點(diǎn)？如何改進(jìn)？ LOCK(X) UNLOCK(X) do while X=1 ; X=0; X=1 解 存在的缺點(diǎn)是：當(dāng)鎖是關(guān)閉時(shí)，采用的是循環(huán)等待的方法，這樣的等待還是要占用處理機(jī)的時(shí)間，應(yīng)該采用阻塞等待的方法。 改進(jìn)的鎖實(shí)現(xiàn)如下： LOCK(X) UNLOCK(X) if X.value=1 if not empty(X.L) insert(

3、*, X.L); P=remove(X.L); Block (*) Wakeup(P) else X.Value=1 else X.Value=0 這里X.value是鎖的值，X.L是存放由于鎖X而阻塞的進(jìn)程的隊(duì)列。insert( *, X.L)將當(dāng)前進(jìn)程的進(jìn)程號(hào)插入到X.L，remove(X.L)是從X.L中移出一個(gè)進(jìn)程號(hào)。例3.2.4 使用多個(gè)進(jìn)程計(jì)算Y=F1(X)+F2 (X).解 (1) 確定并發(fā)和順序操作在這個(gè)問題中，F(xiàn)1(X)和F2 (X)的計(jì)算是可以并行處理的，因此F1(X)和F2 (X)可以分別出現(xiàn)在兩個(gè)進(jìn)程中。(2) 確定互斥或同步的規(guī)則在F1(X)+F2 (X)中，必須在F

4、1(X)和F2(X)計(jì)算完畢，才能進(jìn)行加法運(yùn)算，因此本問題是同步問題。(3) 同步的操作流程進(jìn)程main 創(chuàng)立進(jìn)程p1來計(jì)算F1(X)； 創(chuàng)立進(jìn)程p2來計(jì)算F2(X)； F1(X)計(jì)算是否完成？沒有，等待； F2(X)計(jì)算是否完成？沒有，等待； 進(jìn)行加法運(yùn)算。進(jìn)程p1y1= F1(X)； 設(shè)置F1(X)計(jì)算完成標(biāo)志； 進(jìn)程p2 y1= F2(X)； 設(shè)置F2(X)計(jì)算完成標(biāo)志。 (4) 確定信號(hào)量的個(gè)數(shù)和含義根據(jù)同步規(guī)則以及操作流程確定信號(hào)量的個(gè)數(shù)是2個(gè)，S1和S2：S1含義是F1(X)計(jì)算是否完成； S2含義是F2(X)計(jì)算是否完成。 (5) 確定信號(hào)量的初值S1=0；S2=0。 (6) 確

5、定P、V操作的位置上面處是一個(gè)P操作，P(S1)；上面處是一個(gè)P操作，P(S2)；上面處是一個(gè)V操作，V(S1)；上面處是一個(gè)V操作，V(S2)。解法1Main ( )Public y, y1, y2,. P1, P2Semaphore S1,S2 S1=0;S2=0;P1=Creat(N-F1, F1,x,);P2=Creat(N-F2, F2, x,);P(S1);P(S2);y=y1+y2;Procedure F1(x)y1= 計(jì)算1;V(S1)；Procedure F2(x)y2=計(jì)算2;V(S2)解法2Main ( )Public y, y1, y2,. P1,xSemaphore

6、S1 input(x);S1=0;P1=Creat(N-F1, F1,x,);Y2=F2(x);P(S1);y=y1+y2;Procedure F1(x)y1= 計(jì)算1;V(S1)采用2個(gè)進(jìn)程和1個(gè)信號(hào)量來實(shí)現(xiàn)Y=F1(X)+F2 (X)的時(shí)候，采用的方法是父進(jìn)程創(chuàng)立子進(jìn)程，F(xiàn)1(X)在子進(jìn)程中計(jì)算，F(xiàn)2 (X)在父進(jìn)程中計(jì)算，因此F1(X)和F2(X)計(jì)算仍然是并發(fā)進(jìn)行的。S1信號(hào)量的含義為F1(X)是否完成。改進(jìn)的方法比原來的方法節(jié)約一個(gè)進(jìn)程和一個(gè)信號(hào)量，但并發(fā)操作的程度并沒有降低。例 生產(chǎn)者消費(fèi)者問題演變。情況1 一個(gè)buffer，一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者只生產(chǎn)一個(gè)東西，消費(fèi)者只進(jìn)

7、行一次消費(fèi)，即：生產(chǎn)者只進(jìn)行一次putdata操作，消費(fèi)者只進(jìn)行一次getdata操作。 解 這是一個(gè)同步問題，生產(chǎn)者和消費(fèi)者分別是2個(gè)并發(fā)的進(jìn)程。（1）操作規(guī)則如果buffer為空，則消費(fèi)者只能等待。（2）操作流程<生產(chǎn)者> putdata； 設(shè)置Buffer有數(shù)據(jù)標(biāo)志 V(S) <消費(fèi)者> 判斷buffer是否有產(chǎn)品，沒有則等待； getdata； (3) 信號(hào)量設(shè)置1個(gè)信號(hào)量full，full表示buffer是否有數(shù)據(jù)，初值為0。(4) P、V操作實(shí)現(xiàn)var full:semaphore:=0; buffer: array 1 of item; begin par

8、begin producer: begin putdata； V(full); end consumer:begin P(full); getdata; end parend end情況2 一個(gè)buffer，一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者不斷地進(jìn)行putdata操作，消費(fèi)者不斷地進(jìn)行g(shù)etdata操作，即：生產(chǎn)者不斷地生產(chǎn)，消費(fèi)者不斷地消費(fèi)(1) 操作規(guī)則只有buffer為空時(shí)才能進(jìn)行putdata操作；只有buffer有數(shù)據(jù)時(shí)才能進(jìn)行putdata操作。(2) 操作流程 <生產(chǎn)者> repeat判斷buffer是否為空，不空則等待； putdata ； 設(shè)置buffer有數(shù)據(jù)的標(biāo)

9、志； until false<消費(fèi)者>repeat判斷buffer是否有數(shù)據(jù)，沒有數(shù)據(jù)則等待； getdata； 設(shè)置buffer為空標(biāo)志；until false (3) 信號(hào)量 設(shè)置2個(gè)信號(hào)量full和empty。full表示buffer是否有數(shù)據(jù)。因?yàn)檫M(jìn)程在初始狀態(tài)時(shí)，buffer 中沒有數(shù)據(jù)，故初值為0，變化范圍-11。 empty表示buffer是否為空。因?yàn)檫M(jìn)程在初始狀態(tài)時(shí)，buffer為空，故初值為0初值為1，變化范圍-11。(4) P、V操作實(shí)現(xiàn) var full:semaphore:=0; emptyl:semaphore:=1; buffer: array 1 o

10、f item; begin parbegin producer： begin repeat P(empty)； putdata； V(full); until false end consumer：begin repeat P(full)； getdata； V(empty)； until false. end parend end情況3 一個(gè)buffer，多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，多個(gè)生產(chǎn)者和消費(fèi)者都在不斷地存取buffer，即生產(chǎn)者不斷地進(jìn)行putdata操作，消費(fèi)者不斷地進(jìn)行g(shù)etdata操作。(1) 操作規(guī)則只有buffer為空時(shí)才能進(jìn)行putdata操作；只有buffer有數(shù)據(jù)時(shí)才能進(jìn)

11、行putdata操作。這時(shí)buffer變成了臨界資源，不允許多個(gè)進(jìn)程同時(shí)操作buffer，即不允許多個(gè)消費(fèi)者同時(shí)進(jìn)行g(shù)edata，不允許多個(gè)生產(chǎn)者同時(shí)進(jìn)行putdata操作。(2) 操作流程 <生產(chǎn)者> repeat判斷buffer是否為空，不則等待； 是否可操作buffer；putdata； 設(shè)置buffer可操作標(biāo)志； 設(shè)置buffer有數(shù)據(jù)的標(biāo)志； until false <消費(fèi)者> repeat判斷buffer是否有數(shù)據(jù)，沒有則等待； 是否可操作buffer；getdata ；設(shè)置buffer可操作標(biāo)志； 設(shè)置buffer為空標(biāo)志；until false (3)

12、 信號(hào)量 設(shè)置3個(gè)信號(hào)量full、empty和B-M。full表示buffer是否有數(shù)據(jù)，初值為0； empty表示buffer是否為空，初值為1； B-M 表示 buffer是否可操作，初值為1。由于buffer只有一個(gè)，full和empty可以保證對(duì)buffer的正確操作，故B-M 是多余的，可以省略。(4) P、V操作實(shí)現(xiàn) <生產(chǎn)者> <消費(fèi)者> repeat repeat P(empty)； P(full)； P(B-M)； P(B-M)； putdata； getdata； V(B-M)； V(B-M)； V(full)； V(empty)； until fa

13、lse. until false 情況4 多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，N個(gè)buffer，多次循環(huán)存取buffer，即，即多個(gè)生產(chǎn)者不斷地進(jìn)行putdata操作，多個(gè)消費(fèi)者不斷地進(jìn)行g(shù)etdata操作。(1) 操作規(guī)則只有buffer有空間才能進(jìn)行putdata操作；只有buffer有數(shù)據(jù)才能進(jìn)行putdata操作；這時(shí)buffer變成了臨界資源，不允許多個(gè)消費(fèi)者和生產(chǎn)者同時(shí)對(duì)同一個(gè)buffer 進(jìn)行g(shù)edata和putdata操作。(2) 操作流程 <生產(chǎn)者> repeat判斷buffer是否有空間，沒有則等待； 是否可操作buffer；putdata； 設(shè)置buffer可操作標(biāo)志；

14、設(shè)置buffer有數(shù)據(jù)的標(biāo)志； until false <消費(fèi)者> repeat判斷buffer是否有數(shù)據(jù)，沒有則等待； 是否可操作buffer；getdata； 設(shè)置buffer可操作標(biāo)志； 設(shè)置buffer有空間標(biāo)志；until false (3) 信號(hào)量 full表示buffer是否有數(shù)據(jù)，初值為0; empty表示buffer是否為空，初值為N；B-M 表示 buffer是否可操作，初值為1。(4) P、V操作實(shí)現(xiàn) <生產(chǎn)者> <消費(fèi)者> repeat repeat P(empty)； P(full)； P(B-M)； P(B-M)； putdata

15、； getdata； V(B-M)； V(B-M)； V(full)； V(empty)； until false until false (5) 改進(jìn)的P、V操作實(shí)現(xiàn) 在上述的實(shí)現(xiàn)中，putdata和getdata操作都在臨界區(qū)中，因此多個(gè)進(jìn)程對(duì)多個(gè)buffer的操作是不能并發(fā)進(jìn)行的，進(jìn)程間并行操作的程度很低。實(shí)際上只要保證多個(gè)進(jìn)程同時(shí)操作不同buffer就可以實(shí)現(xiàn)對(duì)整個(gè)buffer的并行操作。因此，只要保證為不同的進(jìn)程分配不同buffer，putdata和getdata操作是可以同時(shí)進(jìn)行。這樣互斥不是發(fā)生在對(duì)buffer的存取操作上，而是發(fā)生在對(duì)buffer的分配上，這個(gè)時(shí)間與存取buff

16、er的時(shí)間相比是較短的，因此減少了進(jìn)程處于臨界區(qū)的時(shí)間。這里引入個(gè)函數(shù):getE_buffer()，返回值是空的buffer號(hào)；getD_buffer()，返回值是有數(shù)據(jù)的buffer號(hào)。getE_buffer()和getD_buffer()通過將buffer轉(zhuǎn)換成循環(huán)隊(duì)列的方法來實(shí)現(xiàn)對(duì)buffer的分配。buffer設(shè)有Pbuff，Pdata兩個(gè)指針，分別指向空閑buffer和有數(shù)據(jù)buffer 的頭，每進(jìn)行一次getE_buffer()和getD_buffer()，Pbuff和Pdata兩個(gè)指針分別向后移動(dòng)一個(gè)位置。 GetE_buffer( ) c=Pbuff Pbuff=(P

17、buff+1)MOD N; Return( c) getD_data( ) c=Pdata; Pdata=(pdata+1)MOD N; Return(c) 改進(jìn)的程序描述如下： var mutex.empty,full:semaphore:=1,n,0; buffer: array 0,n-1 of item; Pbuff，Pdata: integer:=0,0; begin parbegin producer: begin repeat P(empty); P(B_M); in:=getE_buffer(); V(B_M) putdata(in); V(full); until false

18、; end consumer:begin repeat P(full); P(B_M); out:=getD_buffer(); V(B_M); Getdata(out); V(empty); until false end parend end例 設(shè)公共汽車上，司機(jī)和售票員的活動(dòng)分別為：司機(jī)的活動(dòng)為啟動(dòng)車輛，正常行車，到站停車；售票員的活動(dòng)為關(guān)車門，售票，開車門。試問：(1) 在汽車不斷地到站、停車、行駛過程中，司機(jī)和售票員的活動(dòng)是同步關(guān)系還是互斥關(guān)系？(2) 用信號(hào)量和P、V操作實(shí)現(xiàn)他們間的協(xié)調(diào)操作。解(1) 確定并發(fā)和順序操作在這個(gè)問題中，司機(jī)與售票員間是并行操作的，司機(jī)和售票員本身的操

19、作是順序進(jìn)行的。因此司機(jī)是一個(gè)進(jìn)程，售票員是一個(gè)進(jìn)程，它們之間是同步關(guān)系。(2) 確定同步的規(guī)則根據(jù)一般常識(shí)，司機(jī)和售票員在車上的操作規(guī)則如下：1) 售票員操作的規(guī)則是只有司機(jī)停車后，售票員才能開門讓乘客上下車；2) 司機(jī)操作的規(guī)則是只有售票員關(guān)門后，司機(jī)才能啟動(dòng)開始行駛汽車?？梢?，售票員關(guān)車門后，要向司機(jī)發(fā)開車信號(hào)，司機(jī)接到開車信號(hào)后才能啟動(dòng)車輛。在汽車正常行駛過程中售票員售票，到站時(shí)司機(jī)停車，售票員在車停后開車門，讓乘客上下車。因此司機(jī)啟動(dòng)車輛的動(dòng)作必須與售票員的動(dòng)作取得同步；售票員開車門的動(dòng)作也必須同司機(jī)停車取得同步。（3）進(jìn)程的操作流程 <售票員進(jìn)程>do while T關(guān)

20、車門；設(shè)立車門已關(guān)標(biāo)志;售票；是否停車？沒停則等待;開車門；上下乘客； enddo <司機(jī)進(jìn)程> do while T是否關(guān)門？沒關(guān)則等待; 啟動(dòng)車輛；正常行車；到站停車；設(shè)立車停標(biāo)志; enddo (4) 確定信號(hào)量的個(gè)數(shù)和含義根據(jù)同步規(guī)則以及操作流程確定信號(hào)量的個(gè)數(shù)是2個(gè)，S1和S2。S1的含義是否關(guān)門；S2的含義是否停車。(5) 確定信號(hào)量的初值S1=0；S2=1。(6) 確定P、V操作的位置司機(jī)操作中，是否關(guān)門？沒關(guān)則等待，這是一個(gè)P操作，P(S1)；司機(jī)操作中，設(shè)立停車標(biāo)志，這是一個(gè)V操作，V(S2)；售票員操作中，是否停車？沒停則等待，這是一個(gè)P操作，P(S2)；售票員

21、操作中，設(shè)立關(guān)門標(biāo)志，這是一個(gè)V 操作，V(S1)。(7) P、V操作實(shí)現(xiàn) int S1=0;int S2=1;main()cobegindriver(); busman(); coenddriver() do while T P(S1)；啟動(dòng)車輛；正常行車；到站停車；V(S2)； busserver () do while T 關(guān)車門；V(S1)；售票；P(S2)；開車門；上下乘客；例 在OS中引入管程的目的是什么？解 在OS中引入管程的目的是為了更簡(jiǎn)便、更可靠地解決進(jìn)程之間的同步、互斥問題。在未引入管程之間，進(jìn)程間的同步、互斥問題是由程序員處理的。例如，在臨界區(qū)的前后插入P、V操作。但是，

22、由程序員處理同步、互斥問題有可能引入種種人為的錯(cuò)誤。管程主要是管理對(duì)共享數(shù)據(jù)的操作和使用，即把對(duì)共享數(shù)據(jù)互斥使用的控制這一任務(wù)從程序員身上，交由編譯程序去處理，這樣既方便了編程，又不會(huì)產(chǎn)生人為的同步、互斥上的錯(cuò)誤。例 說明管程中條件變量的含義及作用。解 管程中的條件變量（類型為Condition）是供調(diào)用管程中外部過程的進(jìn)程執(zhí)行Wait和Signal操作將自己掛起和解掛的變量?？赏ㄟ^與信號(hào)量的比較來認(rèn)識(shí)條件變量：(1) 信號(hào)量要賦初值而條件變量不賦初值，它只是一個(gè)隊(duì)首指針；(2) 在信號(hào)量上執(zhí)行P操作的進(jìn)程不一定會(huì)被阻塞，而在條件變量上執(zhí)行Wait操作的進(jìn)程肯定被掛起；(3) 在信號(hào)量上的V操

23、作將導(dǎo)致信號(hào)量值加1，若增加后的值小于等于0，則要喚醒在信號(hào)量上等待的進(jìn)程，但喚醒者不受什么影響；而在條件變量上的Signal操作卻有兩種處理方式：P等待，直到Q離開管程，或等待另一條件；Q等待，直到P離開管程，或等待另一條件。P、Q是兩個(gè)進(jìn)程。例3.2.9如果信號(hào)量的初值是，現(xiàn)在信號(hào)量的值是 -，那么系統(tǒng)中的相關(guān)進(jìn)程至少執(zhí)行了幾個(gè)(S)操作？ 與信號(hào)量S相關(guān)的處于阻塞狀態(tài)的進(jìn)程有幾個(gè)？如果要使信號(hào)量S的值大于0，應(yīng)該進(jìn)行怎樣的操作？ 解 (1) 因?yàn)槊繄?zhí)行一次P操作S的值減1，5-（-5）=10，在這期間有可能有進(jìn)程執(zhí)行V操作，使S的值加1，所以至少執(zhí)行了10 次P(S)；(2) 5個(gè)；(3

24、) 6個(gè)V(S) 或 5個(gè)以上。例3.2.10 如下圖所示，有多個(gè)PUT操作同時(shí)向BUFF1放數(shù)據(jù)，有一個(gè)MOVE操作不斷地將BUFF1的數(shù)據(jù)移到Buff2，有多個(gè)GET操作不斷地從Buff2中將數(shù)據(jù)取走。BUFF1的容量為m，BUFF2的容量是n, PUT、 MOVE、 GET每次操作一個(gè)數(shù)據(jù)，在操作的過程中要保證數(shù)據(jù)不丟失。試用、原語協(xié)調(diào)PUT、 MOVE的操作，并說明每個(gè)信號(hào)量的含義和初值。 GETPUTBuff1Buff2MOVE 圖 4.2 進(jìn)程操作圖解(1) 確定并發(fā)的操作 本問題是把2個(gè)消費(fèi)者和生產(chǎn)者問題綜合在一起。多個(gè)PUT操作與一個(gè)MOVE操作并發(fā)進(jìn)行，多個(gè)GET操作與一個(gè)M

25、OVE操作并發(fā)進(jìn)行。因此本題涉及三類進(jìn)程：PUT類進(jìn)程，有多個(gè)；GET類進(jìn)程，有多個(gè)；MOVE類進(jìn)程，有1個(gè)。(2) 操作規(guī)則1) 只有buff1有空間才能進(jìn)行PUT操作；2) 只有buff1有數(shù)據(jù)，buff2有空間才能進(jìn)行MOVE操作；3) 只有buff2有數(shù)據(jù)才能進(jìn)行GET操作；4) 不允許多個(gè)進(jìn)程同時(shí)操作buff1；5) 不允許多個(gè)進(jìn)程同時(shí)操作buff2。(3) 操作流程<PUT類進(jìn)程> repeat判斷buff1是否有空間，沒有則等待； 是否可操作buff1；PUT； 設(shè)置buff1可操作標(biāo)志； 設(shè)置buff1有數(shù)據(jù)的標(biāo)志； until false <MOVE類進(jìn)程&

26、gt; repeat判斷buff1是否有數(shù)據(jù)，沒有則等待；判斷buff2是否有空間，沒有則等待； 是否可操作buff1；是否可操作buff2；MOVE； 設(shè)置buff1可操作標(biāo)志； 設(shè)置buff2可操作標(biāo)志； 設(shè)置buff1有空間標(biāo)志； 設(shè)置buff2有數(shù)據(jù)標(biāo)志； until false <GET類進(jìn)程> repeat判斷buff2是否有數(shù)據(jù)，沒有則等待； 是否可操作buff2；GET；設(shè)置buff1可操作標(biāo)志； 設(shè)置buff1有空間標(biāo)志；until false (4) 信號(hào)量 設(shè)置6個(gè)信號(hào)量full1、empty1、B-M1、full2、empty2、B-M2，它們的含義和初值如

27、下：1) full1表示buff1是否有數(shù)據(jù)，初值為0；2) empty1表示buff1有空間，初值為m；3) B-M1表示buff1是否可操作，初值為1；4) Full2表示buff2是否有數(shù)據(jù)，初值為0；5) Empty2表示buff2有空間，初值為n；6) B-M2表示buff2是否可操作，初值為1；(5) P、V操作實(shí)現(xiàn) <PUT類進(jìn)程> repeatP(empty1)； /*判斷buff1是否有空間，沒有則等待 */ P(B-M1)； /*是否可操作buff1*/PUT； V(B-M1)； /*設(shè)置buff1可操作標(biāo)志 */ V(full1)； /*設(shè)置buff1有數(shù)據(jù)的

28、標(biāo)志 */ until false <MOVE類進(jìn)程> repeatP(full1)； /*判斷buff1是否有數(shù)據(jù)，沒有則等待*/P(empty2)； /*判斷buff2是否有空間，沒有則等待*/ P(B-M1)； /*是否可操作buff1 */P(B-M2)； /*是否可操作buff2 */MOVE； V(B-M1)； /*設(shè)置buff1可操作標(biāo)志*/ V(B-M2)； /*設(shè)置buff2可操作標(biāo)志*/ V(empty1)； /*設(shè)置buff1有空間標(biāo)志*/ V(full2)； /*設(shè)置buff2有數(shù)據(jù)標(biāo)志*/ until false <GET類進(jìn)程> repeat

29、P(empty2)； /*判斷buff2是否有空間，沒有則等待 */ P(B-M2)； /*是否可操作buff2*/GET； V(B-M2)； /*設(shè)置buff2可操作標(biāo)志 */ V(full2)； /*設(shè)置buff2有數(shù)據(jù)的標(biāo)志 */ until false 例3.2.11 一售票廳只能容納300人，當(dāng)少于300人時(shí)，可以進(jìn)入；否則，需在外等候。若將每一個(gè)購票者作為一個(gè)進(jìn)程，請(qǐng)用P、V操作編程，并寫出信號(hào)量的初值。解 購票者進(jìn)程 P(S)； 進(jìn)入售票廳； 購票； 退出售票廳； V(S)； 信號(hào)量的初值 S=300P(S1)CSBV(S2)例3.2.12 設(shè)A、B為兩個(gè)并發(fā)進(jìn)程，它們共享一個(gè)臨

30、界資源，其執(zhí)行臨界區(qū)的算法框圖如下圖所示。試判斷該算法是否有錯(cuò)？請(qǐng)說明理由。如果有錯(cuò)，請(qǐng)改正。S1、S1的初值為0，CSA、CSB為臨界區(qū)。CSAV(S1)P(S2) A進(jìn)程 B進(jìn)程 圖 4.3 進(jìn)程操作圖分析 咋一看， 好像是A進(jìn)程開始未執(zhí)行P操作，便直接進(jìn)入臨界區(qū)，以為問題出在這里。從圖中可分析出A、B兩進(jìn)程的執(zhí)行思路：A進(jìn)程對(duì)臨界資源操作結(jié)束后，將其釋放給B進(jìn)程，而B進(jìn)程對(duì)臨界資源操作結(jié)束后，將釋放給進(jìn)程A。系統(tǒng)初啟時(shí)，S1、S2初值為0，則B執(zhí)行P(S1)被阻塞，而A進(jìn)程可直接訪問臨界資源。故A、B兩個(gè)并發(fā)進(jìn)程不可能同時(shí)操作臨界資源，該算法是可以保證互斥的。按本題的要求，兩個(gè)進(jìn)程對(duì)臨界

31、資源的操作是沒有先后順序的，但是，在上面的實(shí)現(xiàn)中，只有A進(jìn)程先操作完臨界資源后，B進(jìn)程才能操作。解 該算法有錯(cuò)。若A進(jìn)程永不要求訪問臨界資源，則不會(huì)執(zhí)行V(S1)，意味著B進(jìn)程的申請(qǐng)永遠(yuǎn)得不到操作臨界資源的機(jī)會(huì)；同理，若B進(jìn)程不要求訪問臨界資源，則不會(huì)執(zhí)行V(S2)，意味著A進(jìn)程下次也得不到操作臨界資源的機(jī)會(huì)。所以問題在于本應(yīng)進(jìn)行互斥控制而使用的卻是同步控制。實(shí)現(xiàn)改正：設(shè)置信號(hào)mutexmutex:=1;cobeginA進(jìn)程：Begin repeatP(mutex);CSA;V(mutex); until falseEndB進(jìn)程：BeginrepeatP(mutex);CSB;V(mutex)

32、; until falseEndCoend 例3.2.13 何謂純代碼，它有什么用途？解 純代碼是可以為多個(gè)進(jìn)程共享的程序段，代碼不因程序的執(zhí)行而改變，又稱為可重入碼。并不是所有的程序段都能被多個(gè)進(jìn)程共享，如果多個(gè)進(jìn)程共享不可重入的代碼，就可能會(huì)出現(xiàn)錯(cuò)誤。純代碼的主要用途就是讓多個(gè)進(jìn)程共享它。例3.2.14 某高校計(jì)算機(jī)系開設(shè)網(wǎng)絡(luò)課并安排上機(jī)實(shí)習(xí)，假設(shè)機(jī)房共有2m臺(tái)機(jī)器，有2n名學(xué)生選該課，規(guī)定：(1) 每?jī)蓚€(gè)學(xué)生組成一組，各占一臺(tái)機(jī)器，協(xié)同完成上機(jī)實(shí)習(xí)；(2) 只有湊夠兩個(gè)學(xué)生，并且此時(shí)機(jī)房有空閑機(jī)器，門衛(wèi)才允許該組學(xué)生進(jìn)入機(jī)房；(3) 上機(jī)實(shí)習(xí)由一名教師檢查，檢查完畢，一組學(xué)生才可以離開機(jī)

33、房。試用P、V操作模擬上機(jī)實(shí)習(xí)過程。解 (1) 確定并發(fā)和順序操作在這個(gè)問題中，學(xué)生(student)、檢查教師(teacher)和門衛(wèi)(gategard)是并行操作的，因此, 有多個(gè)學(xué)生(student)進(jìn)程、一個(gè)檢查教師(teacher)進(jìn)程和一個(gè)門衛(wèi)(gategard)進(jìn)程。 (2) 確定互斥和同步的規(guī)則 gateguard：只有湊夠兩個(gè)學(xué)生，并且此時(shí)機(jī)房有空閑機(jī)器時(shí)，門衛(wèi)才分配計(jì)算機(jī)給學(xué)生，允許該組學(xué)生進(jìn)入機(jī)房； student：只有門衛(wèi)分配完計(jì)算機(jī)后，學(xué)生才能進(jìn)入機(jī)房上機(jī)操作。只有老師檢查完畢才能離開。 Teacher：只有老師檢查完學(xué)生的實(shí)習(xí)，才準(zhǔn)許學(xué)生離開。(3) 每個(gè)進(jìn)程的操作

34、流程 <student>設(shè)立有學(xué)生到達(dá)標(biāo)志，通知gateguard進(jìn)程；學(xué)生是否可進(jìn)入？上機(jī)實(shí)習(xí)；設(shè)立實(shí)習(xí)完成標(biāo)志，通知教師；教師是否可檢查，等待教師檢查完畢；學(xué)生釋放一臺(tái)計(jì)算機(jī)資源； <teacher> repeat 是否有學(xué)生實(shí)習(xí)完成？是否有學(xué)生實(shí)習(xí)完成？（是否有一組學(xué)生實(shí)習(xí)完成） 檢查學(xué)生實(shí)習(xí)結(jié)果； 檢查完成，允許學(xué)生1離開； 檢查完成，允許學(xué)生2離開； until false <gateguard> repeat 等待學(xué)生1到達(dá); 等待學(xué)生2到達(dá); 是否有可用的計(jì)算機(jī)1; 是否有可用的計(jì)算機(jī)2; 分配計(jì)算機(jī)； 設(shè)置學(xué)生1可進(jìn)入標(biāo)志; 設(shè)置學(xué)生2可進(jìn)入

35、標(biāo)志; until false(4) 確定信號(hào)量的個(gè)數(shù)和含義student：是否有學(xué)生;computer：是否有可用的計(jì)算機(jī)；enter：學(xué)生是否可以進(jìn)入機(jī)房；finish：是否有學(xué)生完成實(shí)習(xí)；test： 老師是否檢查完一組學(xué)生。(5) 確定信號(hào)量的初值在初始狀態(tài)，各信號(hào)量的初值如下：student=0 學(xué)生沒有到達(dá);compute=2m 有2m個(gè)可用的計(jì)算機(jī)；enter=0 不允許學(xué)生進(jìn)入機(jī)房，因?yàn)樾枰玫介T衛(wèi)允許；finish=0 沒有學(xué)生實(shí)習(xí)完成；test=0 老師沒有檢查學(xué)生。(6) 確定P、V操作的位置<student>設(shè)立有學(xué)生到達(dá)標(biāo)志，通知gateguard進(jìn)程 =&

36、gt;V(student)學(xué)生是否可進(jìn)入？=> P(enter)上機(jī)實(shí)習(xí)；設(shè)立實(shí)習(xí)完成標(biāo)志，通知教師 => V(finish)教師是否可檢查，等待教師檢查完畢 => P(test(i) 學(xué)生釋放一臺(tái)計(jì)算機(jī)資源 => V(computer) <teacher> repeat 是否有學(xué)生實(shí)習(xí)完成？=>P(student)是否有學(xué)生實(shí)習(xí)完成？=>P(student)（是否有一組學(xué)生實(shí)習(xí)完成） 檢查學(xué)生實(shí)習(xí)結(jié)果； 檢查完成，允許學(xué)生1離開 => V(test(i) 檢查完成，允許學(xué)生2離開 => V(test(i) until false &

37、lt;gateguard> repeat 等待學(xué)生1到達(dá) =>P(student) 等待學(xué)生2到達(dá) =>P(student) 是否有可用的計(jì)算機(jī)1 => P(computer) 是否有可用的計(jì)算機(jī)2 => P(computer) 分配計(jì)算機(jī)； 設(shè)置學(xué)生1可進(jìn)入標(biāo)志 => V(enter) 設(shè)置學(xué)生2可進(jìn)入標(biāo)志 => V(enter) until false(7) P、V操作實(shí)現(xiàn) 程序如下：student:=0;computer:=2m;enter:=0;finish:=0;test(i):=0;parbegin Student i: Begin V(s

38、tudent); /*表示有學(xué)生到達(dá)，通知gateguard進(jìn)程 */ P(enter); /*學(xué)生是否可進(jìn)入*/ 上機(jī)實(shí)習(xí)； V(finish); /*實(shí)習(xí)結(jié)束，通知教師,有需要檢查的學(xué)生*/ P(test(i); /*等待教師檢查完畢*/ V(computer); /*釋放計(jì)算機(jī)資源 End; . Teacher:Begin repeat P(finish); /*是否有需要檢查的學(xué)生，等待實(shí)習(xí)完成*/ P(finish); /*是否有需要檢查的學(xué)生，等待實(shí)習(xí)完成*/ 選出可檢查的第i組學(xué)生；檢查第i組學(xué)生實(shí)習(xí)結(jié)果； V(test(i); /*檢查完成*/ V(test(i); /*檢查完

39、成*/ until false End; Gategard:Begin repeat. P(student); /*等待學(xué)生到達(dá)*/ P(student); /*等待另一學(xué)生到達(dá)*/ P(computer); /*是否有可用的計(jì)算機(jī)*/ P(computer); /*是否有可用的計(jì)算機(jī)*/ 分配計(jì)算機(jī)； V(enter); /*設(shè)置學(xué)生1可進(jìn)入標(biāo)志*/ V(enter); /*設(shè)置學(xué)生2可進(jìn)入標(biāo)志*/ untile false End;Parend;在student進(jìn)程中，如果在一個(gè)學(xué)生到達(dá)后，立即向gateguard進(jìn)程發(fā)信號(hào)，在gateguard進(jìn)程為其分配計(jì)算機(jī)后，該學(xué)生才被允許進(jìn)入機(jī)房，因此避免了讓該學(xué)生爭(zhēng)奪計(jì)算機(jī)的使用權(quán)和死鎖的發(fā)生。例3.2.15 針對(duì)如下所示的優(yōu)先圖解答下列問題：S1S4S2S3S5S6 圖 4.4 進(jìn)程優(yōu)先圖（1）僅使用并發(fā)語句能否將其轉(zhuǎn)換成正確的程序？如果能則寫出相應(yīng)程序，如果不能則說明為什么？（2）若可以使用信號(hào)量機(jī)構(gòu)，該優(yōu)先圖將如何轉(zhuǎn)換成正確的程序？解 (1) 如果僅用并發(fā)語句不能將其轉(zhuǎn)換成程序。S2S5S2S4S3S5S12S4 因?yàn)镾5有個(gè)前趨，S4有個(gè)前趨，S6有個(gè)前趨。(2) 使用信號(hào)量機(jī)構(gòu)，就可以將其轉(zhuǎn)換成程序。Var a, b, c, d,