操作系統(tǒng)PV操作習(xí)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、用P、V操作描述前趨關(guān)系。P1、P2、P3、P4、P5、P6為一組合作進(jìn)程，其前趨圖如圖23所示，試用P、V操作描述這6個(gè)進(jìn)程的同步。p23 圖23說明任務(wù)啟動(dòng)后P1先執(zhí)行，當(dāng)它結(jié)束后P2、P3可以開始執(zhí)行，P2完成后P4、P5可以開始執(zhí)行，僅當(dāng)P3、P4、P5都執(zhí)行完后，P6才能開始執(zhí)行。為了確保這一執(zhí)行順序，設(shè)置5個(gè)同步信號(hào)量n、攝、f3、f4、g分別表示進(jìn)程P1、P2、P3、P4、P5是否執(zhí)行完成，其初值均為0。這6個(gè)進(jìn)程的同步描述如下：                 

2、0;         圖23 描述進(jìn)程執(zhí)行先后次序的前趨圖 int f1=0; /*表示進(jìn)程P1是否執(zhí)行完成* int f2=0; /*表示進(jìn)程P2是否執(zhí)行完成* int f3=0; /*表示進(jìn)程P3是否執(zhí)行完成* int f4=0; /*表示進(jìn)程P4是否執(zhí)行完成* int f5=0; /*表示進(jìn)程P5是否執(zhí)行完成* main() cobegin P1( ); P2( ); P3( ); P4( ); P5( ); P6( ); coend P1 ( ) v(f1); v(f1)： P2 ( ) p(f1); v(f2); v(f2); ) P3 ( )

3、 p(f1); v(f3); P4( ) p(f2); v(f4); P5 ( ) p(f2); v(f5); P6( ) p(f3); p(f4); p(f5); 二、生產(chǎn)者-消費(fèi)者問題 p25 生產(chǎn)者-消費(fèi)者問題是最著名的進(jìn)程同步問題。它描述了一組生產(chǎn)者向一組消費(fèi)者提供產(chǎn)品，它們共享一個(gè)有界緩沖區(qū)，生產(chǎn)者向其中投放產(chǎn)品，消費(fèi)者從中取得產(chǎn)品。生產(chǎn)者-消費(fèi)者問題是許多相互合作進(jìn)程的一種抽象。例如，在輸入時(shí)，輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者;在輸出時(shí)，計(jì)算進(jìn)程是生產(chǎn)者，打印進(jìn)程是消費(fèi)者。因此，該問題具有很大實(shí)用價(jià)值。 我們把一個(gè)長(zhǎng)度為n的有界緩沖區(qū)(n>0)與一群生產(chǎn)者進(jìn)程P、P、Pm和

4、一群消費(fèi)者進(jìn)程C、C、Ck聯(lián)系起來，如圖24所示。假定這些生產(chǎn)者和消費(fèi)者是互相等效的。只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，類似地，只要緩沖區(qū)未空，消費(fèi)者便可以從緩沖區(qū)中取走物品并消耗它。生產(chǎn)者和消費(fèi)者的同步關(guān)系將禁止生產(chǎn)者向滿的緩沖區(qū)輸送產(chǎn)品，也禁止消費(fèi)者從空的緩沖區(qū)中提取物品。               圖24 生產(chǎn)者-消費(fèi)者問題 為解決這一類生產(chǎn)者-消費(fèi)者問題，應(yīng)該設(shè)置兩個(gè)同步信號(hào)量，一個(gè)說明空緩沖單元的 數(shù)目，用empty表示，其初值為有界緩沖區(qū)的大小n，另一個(gè)說明滿緩沖單元的數(shù)目，用 full表示，其初值

5、為0。在本例中有P、P、Pm個(gè)生產(chǎn)者和C、C、Ck個(gè)消費(fèi)者，它們?cè)趫?zhí)行生產(chǎn)活動(dòng)和消費(fèi)活動(dòng)中要對(duì)有界緩沖區(qū)進(jìn)行操作。由于有界緩沖區(qū)是一個(gè)臨界資源，必須互斥使用，所以，另外還需設(shè)置一個(gè)互斥信號(hào)量mutex，其初值為1。生產(chǎn)者-消費(fèi)者問題的同步描述如下： int full=O; /*滿緩沖單元的數(shù)目* int empty=n; /*空緩沖單元的數(shù)目* int mutex=1; /*對(duì)有界緩沖區(qū)進(jìn)行操作的互斥信號(hào)量* main() cobegin produceri();/*i=1，2，m;j=l，2，k* consumerj(); coend produceri() /*i=1，2，m* while

6、(生產(chǎn)未完成) 生產(chǎn)一個(gè)產(chǎn)品; p(empty); p(mutex); 送一個(gè)產(chǎn)品到有界緩沖區(qū); v(mutex); v(full); ) consumerj() /*j=1，2，k* while(還要繼續(xù)消費(fèi)) p (full); p(mutex); 從有界緩沖區(qū)中取產(chǎn)品; v (mutex); v (empty); 消費(fèi)一個(gè)產(chǎn)品; 三、在操作系統(tǒng)中，進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序在某個(gè)數(shù)據(jù)集上的一次 。 A等待活動(dòng) B運(yùn)行活動(dòng) C單獨(dú)操作 D關(guān)聯(lián)操作 答：B 四、多道程序環(huán)境下，操作系統(tǒng)分配資源以為基本單位。 A程序 B指令 C進(jìn)程 D作業(yè) 答：C 五、對(duì)于兩個(gè)并發(fā)進(jìn)程，設(shè)互斥信號(hào)量為m

7、utex，若mutex=O，則。 A.表示沒有進(jìn)程進(jìn)入臨界區(qū) B.表示有一個(gè)進(jìn)程進(jìn)入臨界區(qū) C.表示有一個(gè)進(jìn)程進(jìn)入臨界區(qū)，另一個(gè)進(jìn)程等待進(jìn)入 D.表示有兩個(gè)進(jìn)程進(jìn)入臨界區(qū) 答：B 六、兩個(gè)進(jìn)程合作完成一個(gè)任務(wù)。在并發(fā)執(zhí)行中，一個(gè)進(jìn)程要等待其合作伙伴發(fā)來消 息，或者建立某個(gè)條件后再向前執(zhí)行，這種制約性合作關(guān)系被稱為進(jìn)程的。 A.同步 B互斥 C. 調(diào)度 D執(zhí)行 答：A 七、為了進(jìn)行進(jìn)程協(xié)調(diào)，進(jìn)程之間應(yīng)當(dāng)具有一定的聯(lián)系，這種聯(lián)系通常采用進(jìn)程間交換數(shù)據(jù)的方式進(jìn)行，這種方式稱為。 A.進(jìn)程互斥 B進(jìn)程同步 C進(jìn)程制約 D進(jìn)程通信 答：D 八、在測(cè)量控制系統(tǒng)中，數(shù)據(jù)采集任務(wù)把所采集的數(shù)據(jù)送入一單緩沖區(qū);

8、計(jì)算任務(wù)從該單緩沖區(qū)中取出數(shù)據(jù)進(jìn)行計(jì)算。試寫出利用信號(hào)量機(jī)制實(shí)現(xiàn)兩者共享單緩沖區(qū)的同步算法。P33 分析及相關(guān)知識(shí) 在本題中采集任務(wù)與計(jì)算任務(wù)共用一個(gè)單緩沖區(qū)當(dāng)采集 任務(wù)采集到一個(gè)數(shù)據(jù)后，只有當(dāng)緩沖區(qū)為空時(shí)才能將數(shù)據(jù)送入緩沖區(qū)中存放，否則應(yīng)等待緩沖區(qū)騰空;當(dāng)緩沖區(qū)中有數(shù)據(jù)時(shí)，計(jì)算任務(wù)才能從緩沖區(qū)中取出數(shù)據(jù)進(jìn)行計(jì)算，否則也應(yīng)等待。 本題實(shí)際上是一個(gè)生產(chǎn)者消費(fèi)者問題。將生產(chǎn)者消費(fèi)者問題抽象出來，以另外 一種形式描述是一種常見的試題形式只要對(duì)生產(chǎn)者消費(fèi)者問題有了深入的理 解，就不難解決此類試題。 解;在本題中，應(yīng)設(shè)置兩個(gè)信號(hào)量Sf,Se，信號(hào)量Sf表示緩沖區(qū)中是否有可供打印的計(jì)算結(jié)果，其初值為0;信

9、號(hào)量Se用于表示緩沖區(qū)有無空位置存放新的信息，其初值為1。 本題的同步描述如下： int Se=l; int Sf=0; main() cobegin get(); compute(); coend get() while (采集工作未完成) 采集一個(gè)數(shù)據(jù)： p(Se); 將數(shù)據(jù)送入緩沖區(qū)中; v(Sf); compute() while(計(jì)算工作未完成) p(Sf); 從緩沖區(qū)中取出數(shù)據(jù); v(Se); 進(jìn)行數(shù)據(jù)計(jì)算; 九、圖27給出了四個(gè)進(jìn)程合作完成某一任務(wù)的前趨圖，試說明這四個(gè)進(jìn)程間的同步關(guān)系，并用P、V操作描述它。P35         

10、0;           圖27 四個(gè)合作進(jìn)程的前趨圖 解：圖27說明任務(wù)啟動(dòng)后S1先執(zhí)行。當(dāng)S1結(jié)束后，S2、S3可以開始執(zhí)行。S2、S3 完成后，S4才能開始執(zhí)行。為了確保這一執(zhí)行順序，設(shè)三個(gè)同步信號(hào)量b2、b3、b4分別 表示進(jìn)程S2、S3、S4是否可以開始執(zhí)行，其初值均為0。這四個(gè)進(jìn)程的同步描述如下： int b2=0; /*表示進(jìn)程S2是否可以開始執(zhí)行* int b3=0; /*表示進(jìn)程S3是否可以開始執(zhí)行* int b4=0; /*表示進(jìn)程S4是否可以開始執(zhí)行* main() cobegin S1 ( ); S2 ( ); S3 (

11、 ); S4 ( ); coend S1 ( ) v(b2); v(b3); S2 ( ) p(b2); v(b4); S3 ( ) p(b3)： v(b4); S4 ( ) p(b4); p(b4); /*因在S2及S3完成時(shí)均對(duì)b4做了v操作，因此這里要用兩個(gè)p操作* 十、桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一只水果供吃者取用，請(qǐng)用P、V原語實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。P37 分析及相關(guān)知識(shí) 在本題中，爸爸、兒子、女兒共用一個(gè)盤子，且盤中一次只能放一個(gè)水果當(dāng)盤子為空時(shí)，爸爸可將一

12、個(gè)水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待;若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。本題實(shí)際上是生產(chǎn)者消費(fèi)者問題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)的產(chǎn)品有兩類，消費(fèi)者也有兩類，每類消費(fèi)者只消費(fèi)其中固定的一類產(chǎn)品。 解：在本題中，應(yīng)設(shè)置三個(gè)信號(hào)量S、So、Sa，信號(hào)量S表示盤子是否為空，其初值 為1;信號(hào)量So表示盤中是否有桔子，其初值為0;信號(hào)量Sa表示盤中是否有蘋果，其初 值為0。同步描述如下： int S=1; int Sa=O： int So=O： main( ) cobegin father(); son(); daughter()： coend fa

13、ther() while (1) p(S); 將水果放入盤中; if(放入的是桔子) v(So)： else v(Sa); ) son( ) while(1) p(So); 從盤中取出桔子; v(S); 吃桔子; daushter() while(1) p(Sa); 從盤中取出蘋果; v(S)： 吃蘋果; 答 十一、(華中理工大學(xué)1999年試題)設(shè)公共汽車上，司機(jī)和售票員的活動(dòng)分別是：p41 司機(jī)的活動(dòng)：?jiǎn)?dòng)車輛： 正常行車; 到站停車; 售票員的活動(dòng)：關(guān)車門; 售票： 開車門; 在汽車不斷地到站、停車、行駛過程中，這兩個(gè)活動(dòng)有什么同步關(guān)系?用信號(hào)量和P、 V操作實(shí)現(xiàn)它們的同步。 解

14、;在汽車行駛過程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為：售票員關(guān)車門后， 向司機(jī)發(fā)開車信號(hào)，司機(jī)接到開車信號(hào)后啟動(dòng)車輛，在汽車正常行駛過程中售票員售票，到站時(shí)司機(jī)停車，售票員在車停后開車門讓乘客上下車。因此司機(jī)啟動(dòng)車輛的動(dòng)作必須與售票員關(guān)車門的動(dòng)作取得同步;售票員開車門的動(dòng)作也必須與司機(jī)停車取得同步。 在本題中，應(yīng)設(shè)置兩個(gè)信號(hào)量：s1、s2，s1表示是否允許司機(jī)啟動(dòng)汽車，其初值為0; s2表示是否允許售票員開門，其初值為0。用P、V原語描述如下： int s1=O; int s2=O; main() cobegin driver(); busman(); coend driver() whi

15、le(1) p(s1); 啟動(dòng)車輛; 正常行車; 到站停車; v(s2); busman() while(1) 關(guān)車門; v(s1); 售票; p(s2); 開車門; 上下乘客; 用P、V操作來控制現(xiàn)實(shí)生活中的操作流程是一類常見的試題。這類試題要求解題者 能將生活中的控制流程用形式化的方式表達(dá)出來。 十二、設(shè)有一個(gè)發(fā)送者進(jìn)程和一個(gè)接收者進(jìn)程，其流程圖如圖210所示。s是用于實(shí)現(xiàn)進(jìn)程同步的信號(hào)量，mutex是用于實(shí)現(xiàn)進(jìn)程互斥的信號(hào)量。試問流程圖中的A、B、C、D四框中應(yīng)填寫什么?假定緩沖區(qū)有無限多個(gè)，s和mutex的初值應(yīng)為多少? p42 分析及相關(guān)知識(shí) 由圖210可以看出，發(fā)送者進(jìn)程與接收者進(jìn)

16、程之間的同步關(guān)系是：發(fā)送者進(jìn)程生成的信息送入消息鏈中，接收者進(jìn)程從消息鏈中接收信息;由于發(fā)送者進(jìn)程產(chǎn)生一個(gè)消息并鏈入消息鏈后用V操作增加消息計(jì)數(shù)并喚醒接收者進(jìn)程，這表示發(fā)送者進(jìn)程和接收者進(jìn)程是通過信號(hào)量s實(shí)現(xiàn)同步的，因此接收者進(jìn)程應(yīng)該在取信息之前先使用一個(gè)P操作來查看消息鏈上是否有消息，若無消息則阻塞自己;另外，發(fā)送者和接收者對(duì)消息鏈的訪問應(yīng)使用信號(hào)量進(jìn)行互斥，即在訪問前使用P操作，在訪問后使用V操作。                            

17、;               圖210 發(fā)送者及接收者工作流程圖 解：由上述分析可知，A、B、C、D四框應(yīng)分別填入： A框 P(mutex) B框 V(mutex) C框 P(s) D框 P(mutex)開始時(shí)，消息鏈上沒有可供接收的信息，所以s的初值為0;互斥信號(hào)量mutex的初值應(yīng)為1。 十三、(北京大學(xué)1990年試題)p46 寫出P、V操作的定義。 有三個(gè)進(jìn)程PA、PB和PC合作解決文件打印問題：PA將文件記錄從磁盤讀入主存 的緩沖區(qū)1，每執(zhí)行一次讀一個(gè)記錄;PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一次 復(fù)制一個(gè)記

18、錄：PC將緩沖區(qū)2的內(nèi)容打印出來，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大小等于一個(gè)記錄大小。請(qǐng)用P、V操作來保證文件的正確打印。 分析及相關(guān)知識(shí) 信號(hào)量是一個(gè)確定的二元組(s，q)，其中s是一個(gè)具有非負(fù)初值的整型變量，q是一個(gè)與s相關(guān)聯(lián)的初始狀態(tài)為空的隊(duì)列整型變量s表示系統(tǒng)中某類資源的數(shù)目，當(dāng)其值大于0時(shí)，表示系統(tǒng)中當(dāng)前可用資源的數(shù)目; 當(dāng)其值小于0時(shí)，其絕對(duì)值表示系統(tǒng)中因請(qǐng)求誼類資源而被阻塞的進(jìn)程數(shù)目除信號(hào)量的初值外，信號(hào)量的值僅能由P操作和V操作改變。 解：P、V操作是兩條原語，它們的定義如下： P操作 P操作記為P(S)，其中S為一信號(hào)量，它執(zhí)行時(shí)主要完成下述動(dòng)作： S=S-1 若S0，則進(jìn)

19、程繼續(xù)運(yùn)行。 若S<0，則該進(jìn)程被阻塞，并將它插入該信號(hào)量的等待隊(duì)列中。 V操作 V操作記為V(S)，S為一信號(hào)量，它執(zhí)行時(shí)主要完成下述動(dòng)作： S=S+1 若S>0，則進(jìn)程繼續(xù)執(zhí)行。 若S0，則從信號(hào)量等待隊(duì)列中移出隊(duì)首進(jìn)程，使其變?yōu)榫途w狀態(tài)。 在本題中，進(jìn)程PA、PB、PC之間的關(guān)系為：PA與pB共用一個(gè)單緩沖區(qū)，而PB 又與PC共用一個(gè)單緩沖區(qū)，其合作方式可用圖212表示。當(dāng)緩沖區(qū)1為空時(shí)，進(jìn)程PA可將一個(gè)記錄讀入其中;若緩沖區(qū)1中有數(shù)據(jù)且緩沖區(qū)2為空，則進(jìn)程PB可將記錄從緩沖區(qū)1復(fù)制到緩沖區(qū)2中;若緩沖區(qū)2中有數(shù)據(jù)，則進(jìn)程PC可以打印記錄。在其他條件 下，相應(yīng)進(jìn)程必須等待。事

20、實(shí)上，這是一個(gè)生產(chǎn)者-消費(fèi)者問題。         圖212 進(jìn)程間的合作方式 為遵循這一同步規(guī)則。應(yīng)設(shè)置四個(gè)信號(hào)量emptyl、empty2、full1、full2，信號(hào)量emptyl 及empty2分別表示緩沖區(qū)1及緩沖區(qū)2是否為空，其初值為1;信號(hào)量full1及full2分別表示緩沖區(qū)1及緩沖區(qū)2是否有記錄可供處理，其初值為0。其同步描述如下： int emptyl=l; int empty2=l; int fulll=O; int full2=O; main() cobegin PA ( ); PB ( ); PC ( ); coend PA (

21、 ) while (1) 從磁盤讀一個(gè)記錄： p(emptyl); 將記錄存入緩沖區(qū)1; v(fulll)： PB ( ) while(1) p(fulll); 從緩沖區(qū)1中取出記錄; v(emptyl); p(empty2); 將記錄存入緩沖區(qū)2; v(full2); PC ( ) while(1) p(full2); 從緩沖區(qū)2中取出記錄; v(empty2); 打印記錄; 本題也是一個(gè)典型的生產(chǎn)者。消費(fèi)者問題。其中的難點(diǎn)在于PB既是個(gè)生產(chǎn)者又是一個(gè)消費(fèi)者。 十四、設(shè)有8個(gè)程序progl、prog2、prog8。它們?cè)诓l(fā)系統(tǒng)中執(zhí)行時(shí)有如圖213所示的制約關(guān)系，試用P、V操作實(shí)現(xiàn)這些程序間

22、的同步。P48                     解：由圖213表明開始時(shí)，progl及prog2先執(zhí)行。當(dāng)progl和prog2都執(zhí)行完后，prog3、 prog4、prog5才可以開始執(zhí)行。prog3完成后，prog6才能開始執(zhí)行。prog5完成后，prog7 才能開始執(zhí)行。prog6、prog4、prog7都結(jié)束后，prog8才可以開始執(zhí)行。為了確保這一執(zhí)行順序，設(shè)7個(gè)同步信號(hào)量f1、f7分別表示程序progl、prog7是否執(zhí)行完，其初值均為0。這8個(gè)進(jìn)程的同步描述如下： int

23、fi=0; /*表示程序progl是否執(zhí)行完* int f2=0; int f3=0： int f4=O; int f5=0; int f6=0; int f7=0; main() cobegin progl(); prog2(); prog3(); prog4(); prog5(); prog6(); prog7(); prog8(); coend progl() v(f1); v(f1); v(f1); ) prog2() v(f2); v(f2); v(f2); ) prog3() p(f1); p(f2); v(f3); ) prog4() p(f1); p(f2); v(f4); p

24、rog5() p(f1); p(f2); v(f5); ) prog6() p(f3); v(f6); prog7() p(f5); v(f7); prog8() p(f4); p(f6); p(f7); 十五、(北京大學(xué)1991年試題)有一個(gè)倉庫，可以存放A和B兩種產(chǎn)品，但要求： (1)每次只能存入一種產(chǎn)品(A或B);p50 (2)-N<(A產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量)<M。 其中，N和M是正整數(shù)。試用P、V操作描述產(chǎn)品A與產(chǎn)品B韻入庫過程。 分析及相關(guān)知識(shí) 本題給出的第一個(gè)條件是臨界資源的訪問控制，可用一個(gè)互斥信號(hào)量解決該問題。第二個(gè)條件可以分解為： -N<A產(chǎn)品數(shù)量一B產(chǎn)品數(shù)

25、量 A產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量<M 也就是說，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量少N個(gè)以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個(gè)以上 解;在本題中，我們可以設(shè)置兩個(gè)信號(hào)量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當(dāng)前 允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和B產(chǎn)品不入庫的情況下，還可以允 許sa個(gè)A產(chǎn)品入庫;sb表示當(dāng)前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和 A產(chǎn)品不入庫的情況下，還可以允許sb個(gè)B產(chǎn)品入庫。初始時(shí)，sa為M一1，sb為N一1， 當(dāng)往庫中存放入一個(gè)A產(chǎn)品時(shí)，則允許存入B產(chǎn)品的數(shù)量也增加1;當(dāng)往庫中存放入一個(gè)B產(chǎn)品時(shí)，則允許存入A產(chǎn)品的數(shù)量也增加1。 產(chǎn)品A、B的入庫過

26、程描述如下： int mutex=1; /*互斥信號(hào)量* int sa=M-1; int sb=N-1; main( ) while(1) 取一個(gè)產(chǎn)品; if(取的是A產(chǎn)品) p(sa); p(mutex); 將產(chǎn)品入庫; v(mutex); v(sb)： else /*取的產(chǎn)品是B* p(sb); p(mutex); 將產(chǎn)品入庫; v(mutex); v(pa); 從本題的解法可以看出，當(dāng)有比較復(fù)雜條件出現(xiàn)時(shí)，可以把復(fù)雜條件分解成一組簡(jiǎn)單條件，這樣就能很容易地寫出對(duì)應(yīng)的程序流程了。 十六、(南開大學(xué)1997年試題)在南開大學(xué)和天津大學(xué)之間有一條彎曲的小路，其中從S到T一段路每次只允許一輛自行

27、車通過，但其中有一個(gè)小的安全島M(同時(shí)允許兩輛自行車停留)，可供兩輛自行車已從兩端進(jìn)入小路情況下錯(cuò)車使用，如圖214所示。試設(shè)計(jì)一個(gè)算法使來往的自行車均可順利通過。p53   錯(cuò)                分析及相關(guān)知識(shí) 在本題中，需要控制路段T到L，路段S到K及安全島M的使用。路段T到L及路段S到K同時(shí)只允許一輛自行車通過，而安全島M允許兩輛自行車使用，因此可以用三個(gè)信號(hào)量來管理它們。另一方面，同一方向上的自行車最多只能有一輛通過這段路(兩個(gè)方向上有兩輛)，因此還應(yīng)該用兩個(gè)信號(hào)量來控制 解：在本題中

28、，應(yīng)設(shè)置5個(gè)信號(hào)量ST，TS，K，L，M，信號(hào)量ST表示是否允許自行 車從南開大學(xué)去天津大學(xué)，其初值為1;信號(hào)量TS表示是否允許自行車從天津大學(xué)去南開 大學(xué)，其初值為1;信號(hào)量K表示是否允許自行車通過路段S到K，其初值為1;信號(hào)量L表示是否允許自行車通過路段T到L，其初值為1;信號(hào)量M表示安全島上還可停放自行車的數(shù)目，其初值為2。其控制過程描述如下： int ST=1; int TS=1; int K=1; int L=1; int M=2; totian( ) /*從南開大學(xué)去天津大學(xué)* p(ST); p(K); 從S走到K; p(M); 進(jìn)入安全島; v(K); p(L); 從L走到T;

29、v(M); v(L); v(ST); tonan() /*從天津大學(xué)去南開大學(xué)* p(TS); p(L); 從T走到L; p(M); 進(jìn)入安全島; v(L); p(K); 從K走到S; v(M); v(K); v(TS);   另一題 在南開大學(xué)和天津大學(xué)之間有一條彎曲的小路，其中從S到T一段路每次只允許一輛自行車通過，但中間有一個(gè)小的“安全島”M(同時(shí)允許兩輛自行車停留)，可供兩輛自行車已從兩端進(jìn)入小路情況下錯(cuò)車使用，如圖3-28所示。試設(shè)計(jì)一個(gè)算法使來往的自行車均可順利通過。L3.46  p129  正確        

30、            解答 由于小路中間的安全島M僅允許兩輛自行車停留，本應(yīng)該作為臨界資源而設(shè)置信號(hào)量， 但仔細(xì)分析可以發(fā)現(xiàn)：在任何時(shí)刻進(jìn)入小路的自行車最多不會(huì)超過兩輛(南開和天大方向各一輛)，因此，無需為安全島M設(shè)置信號(hào)量。在路口S處，南開出發(fā)的若干自行車應(yīng)進(jìn)行進(jìn)入小路權(quán)的爭(zhēng)奪，以決定誰能夠進(jìn)入小路SK段，為此，設(shè)置信號(hào)量S(初值為1)來控制南 開路口資源的爭(zhēng)奪。同理，設(shè)置信號(hào)量T(初值為1)來控制天大路口資源的爭(zhēng)奪。此外， 小路SK段僅允許一輛自行車通過，所以設(shè)置信號(hào)量SK(初值為1)來進(jìn)行控制，而對(duì)于LT 段則設(shè)置信號(hào)量LT(

31、初值為1)進(jìn)行控制。 begin S：=1；T：=1； SK：=1；LT：=1； cobegin 進(jìn)程i (i為南開方向的自行車，i=1，2，)： begin P(S)； /*與其他南開方向的自行車爭(zhēng)奪路口S的使用權(quán)* P(SK)； /*同對(duì)面(天大)來的自行車爭(zhēng)奪SK路段的使用權(quán)* 通過SK路段； 進(jìn)入安全島M； V(SK)； /*一旦進(jìn)入安全島M便可釋放路段SK的使用權(quán)* P(LT)； /*同對(duì)面(天大)來的自行車爭(zhēng)奪LT路段的使用權(quán)* 通過LT路段： V(LT)； *已通過LT路段，釋放路段LT的使用權(quán)* V(S) /*已經(jīng)通過小路，則允許在路口S等待的自行車爭(zhēng)奪再次進(jìn)入S的 使用權(quán)*

32、end； 進(jìn)程j (j為天大方向的自行車，j=1，2，)： begin P(T)； /*與其他天大方向的自行車爭(zhēng)奪路口T的使用權(quán)* P(LT)； /*同對(duì)面(南開)來的白行車爭(zhēng)奪LT路段的使用權(quán)* 通過LT路段； 進(jìn)入安全島M； V(LT)： /*旦進(jìn)入安全島M便可釋放路段LT的使用權(quán)* P(SK)： *同對(duì)面(南開)來的自行車爭(zhēng)奪SK路段的使用權(quán)* 通過SK路段： V(SK)； /*已通過SK路段，釋放路段SK的使用權(quán)* V(T) /*已經(jīng)通過小路，則允許在路口 T等待的臼行車爭(zhēng)奪再次進(jìn) 入T的使用權(quán)* end coend end； 注意：如果在進(jìn)程i進(jìn)入安全島M后，在釋放路段SK的同時(shí)釋放

33、了路口S，而此時(shí)進(jìn)程i 也進(jìn)入安全島，同樣在釋放路段LT的同時(shí)釋放路口T，那么，南開、天大方向?qū)⒏饔幸蛔孕熊囉诌M(jìn)入路段SK和路段LT，這使得在安全島M中的兩輛自行車都無法繼續(xù)前進(jìn)，而在SK路段和LT路段的自行車也無法進(jìn)入安全島M，從而造成死鎖。因此，進(jìn)程i在進(jìn)入安全島M后是為對(duì)面<天大)來的自行車釋放路段SK的使用權(quán)，而進(jìn)程j在進(jìn)入安全島M后也是為對(duì)面(南開)來的自行車釋放路段LT的使用權(quán)。 十七、(中國科學(xué)院軟件研究所1995年試題)多個(gè)進(jìn)程共享一個(gè)文件，其中只讀文件的 稱為讀者，只寫文件的稱為寫者。讀者可以同時(shí)讀，但寫者只能獨(dú)立寫。請(qǐng)： 說明進(jìn)程間的相互制約關(guān)系，應(yīng)設(shè)置哪些信號(hào)量?

34、用P、V操作寫出其同步算法。 修改上述的同步算法，使得它對(duì)寫者優(yōu)先，即一旦有寫者到達(dá)，后續(xù)的讀者必須等 待。而無論是否有讀者在讀文件。 解：本題前兩問是經(jīng)典讀者寫者問題，第三問對(duì)讀者寫者問題加了一些限制，即使算 法對(duì)寫者優(yōu)先。 進(jìn)程間的相互制約關(guān)系有三類：一是讀者之間允許同時(shí)讀;二是讀者與寫者之間須 互斥;三是寫者之間須互斥。 為了解決讀者、寫者之間的同步，應(yīng)設(shè)置兩個(gè)信號(hào)量和一個(gè)共享變量;讀互斥信號(hào)量 rmutex，用于使讀者互斥地訪問共享變量count，其初值為1;寫互斥信號(hào)量wmutex，用于實(shí)現(xiàn)寫者與讀者的互斥及寫者與寫者的互斥，其初值為1;共享變量count，用于記錄當(dāng)前正在讀文件的讀

35、者數(shù)目，初值為0。 進(jìn)程間的控制算法如下所示： int rmutex=l; int wmutcx=l; int count=0; main( ) cobegin reader( ); writer( ); coend reader( ) while (1) p(rmutex); if(count=0) p(wmutex); /*當(dāng)?shù)谝粋€(gè)讀者讀文件時(shí)，阻止寫者寫* count+; v(rmutex); 讀文件; p(rmutex); count -; if(coun=)v(wmutex); /*當(dāng)最后一個(gè)讀者讀完文件時(shí)，允許寫者寫* v(rmutex); writer( ) while(1) p

36、(wmutex); 寫文件; v(wmutex); 為了提高寫者的優(yōu)先級(jí)，增加一個(gè)信號(hào)量s，用于在寫進(jìn)程到達(dá)后封鎖后續(xù)的讀者。 其控制流程如下： int rmutex=1; int wmutex=l; int count=0; int s=1; main() cobegin reader(); writer(); coend reader() while (1) p(s); p(rmutex); if(coun=0) p(wmutex); /*當(dāng)?shù)谝粋€(gè)讀者讀文件時(shí)，阻止寫者寫* count+; v(rmutex); v(s); 讀文件; p(rmutex); count-; if(count=

37、0)v(wmutex); /*當(dāng)最后一個(gè)讀者讀完文件時(shí)，允許寫者寫* v(rmutex); writer() while(1) p(s); p(wmutex); 寫文件; v(wmutex); v(S);     十八、既考慮作業(yè)等待時(shí)間，又考慮作業(yè)執(zhí)行時(shí)間的調(diào)度算法是 。 A. 響應(yīng)比高者優(yōu)先 B短作業(yè)優(yōu)先 p91 C優(yōu)先級(jí)調(diào)度 D先來先服務(wù) 答：A 十九、是指從作業(yè)提交給系統(tǒng)到作業(yè)完成的時(shí)間間隔。p91 A周轉(zhuǎn)時(shí)間 B響應(yīng)時(shí)間 C. 等待時(shí)間 D運(yùn)行時(shí)間 答：A 二十、作業(yè)從進(jìn)入后備隊(duì)列到被調(diào)度程序選中的時(shí)間間隔稱為。p91 A周轉(zhuǎn)時(shí)間 B響應(yīng)時(shí)間 C. 等待時(shí)間 D觸

38、發(fā)時(shí)間 答：C 二十一、假設(shè)下述四個(gè)作業(yè)同時(shí)到達(dá)，當(dāng)使用最高優(yōu)先數(shù)優(yōu)先調(diào)度算法時(shí)，作業(yè)的平均周轉(zhuǎn)時(shí)間為小時(shí)。 P91 作業(yè) 所需運(yùn)行時(shí)間 優(yōu)先數(shù) 1 2 4 2 5 9 3 8 1 4 3 8   A4.5 B10.5 C4.75 D10.25 答：D 二十二、系統(tǒng)在，發(fā)生從目態(tài)到管態(tài)的轉(zhuǎn)換。P92 A. 發(fā)出P操作時(shí) B發(fā)出V操作時(shí) C執(zhí)行系統(tǒng)調(diào)用時(shí) D. 執(zhí)行置程序狀態(tài)字時(shí) 答：C 二十三、操作系統(tǒng)為用戶提供兩個(gè)接口。一個(gè)是，用戶利用它來組織和控制作業(yè)的執(zhí)行或管理計(jì)算機(jī)系統(tǒng)。另一個(gè)是，編程人員使用它們來請(qǐng)求操作系統(tǒng)提供服務(wù)。p92 答：命令接口 程序接口 二十四、設(shè)有一組作業(yè)，它

39、們的提交時(shí)間及運(yùn)行時(shí)間如下：p93 作業(yè)號(hào) 提交時(shí)間 運(yùn)行時(shí)間(分鐘) 1 9:00 70 2 9:40 30 3 9:50 10 4 10:10 5 在單道方式下，采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)的執(zhí)行順序是。 答：1、4、3、2 二十五、設(shè)有4道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間如下：p93 作業(yè)號(hào) 提交時(shí)間 執(zhí)行時(shí)間 1 10.0 2.0 2 10.2 1.0 3 10.4 0.5 4 10.5 0.3 試計(jì)算在單道程序環(huán)境下，采用先來先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，并指出它們的調(diào)度順序。(時(shí)間單位：小時(shí)，以十進(jìn)制進(jìn)行計(jì)算。) 解：若采用先來先服務(wù)調(diào)度算法

40、，則其調(diào)度順序?yàn)?、2、3、4。 作業(yè)號(hào) 提交時(shí)間 執(zhí)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 10.0 2.0 10.0 12.0 2.0 1.0 2 10.2 1.0 12.0 13.0 2.8 2.8 3 10.4 0.5 13.0 13.5 3.1 6.2 4 10.5 0.3 13.5 13.8 3.3 11.0 平均周轉(zhuǎn)時(shí)間 T=(2.0+2.8+3.1+3.3)4=2.8 平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+2.8+6.2+11)4=5.25 若采用短作業(yè)優(yōu)先調(diào)度算法，則其調(diào)度順序?yàn)?、4、3、2。 作業(yè)號(hào) 提交時(shí)間 執(zhí)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1

41、 10.0 2.0 10.0 12.0 2.0 1.0 4 10.5 0.3 12.0 12.3 1.8 6.0 3 10.4 0.5 12.3 12.8 2.4 4.8 2 10.2 1.0 12.8 13.8 3.6 3.6 平均周轉(zhuǎn)時(shí)間 T=(2.0+1.8+2.4+3.6)4=2.45 平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+6+4.8+3.6)4=3.85 二十六、下表給出作業(yè)1、2、3的到達(dá)時(shí)間和運(yùn)行時(shí)間。采用短作業(yè)優(yōu)先調(diào)度算法和先來先服務(wù)調(diào)度算法，試問平均周轉(zhuǎn)時(shí)間各為多少?是否還有更好的調(diào)度策略存在?(時(shí)間單位：小時(shí)，以十進(jìn)制進(jìn)行計(jì)算。) p94 作業(yè)號(hào) 到達(dá)時(shí)間 運(yùn)行時(shí)間 1 0.0 8.

42、0 2 0.4 4.0 3 1.0 1.0 解：采用先來先服務(wù)調(diào)度策略，則調(diào)度順序?yàn)?、2、3。 作業(yè)號(hào) 到達(dá)時(shí)間 運(yùn)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 1 0.0 8.0 0.0 8.0 8.0 2 0.4 4.0 8.0 12.0 11.6 3 1.0 1.0 12.0 13.0 12.0 平均周轉(zhuǎn)時(shí)間T=(8+11.6+12)3=10.53 采用短作業(yè)優(yōu)先調(diào)度策略，則調(diào)度順序?yàn)?、3、2。 作業(yè)號(hào) 到達(dá)時(shí)間 運(yùn)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 1 0.0 8.0 0.0 8.0 8.0 3 1.0 1.0 8.0 9.0 8.0 2 0.4 4.0 9.0 13.0 12.6 平均周轉(zhuǎn)時(shí)間T=(8+8+12.6)3=9.53 存在縮短平均周轉(zhuǎn)時(shí)間的策略，如知道后面將來兩個(gè)短作業(yè)，因此在作業(yè)1到達(dá)后暫不投入運(yùn)行，等所有作業(yè)到齊后再按短作業(yè)優(yōu)先調(diào)度算法調(diào)度，其調(diào)度順序?yàn)?、2、1。 作業(yè)號(hào) 到達(dá)時(shí)間 運(yùn)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 3 1.0 1.0 1.0 2.0 1.0 2 0.4 4.0 2.0 6.0 5.6 1 0.0 8.0 6.0 14.0