計(jì)算機(jī)操作系統(tǒng)模擬測(cè)試題綜合應(yīng)用部分解析

1、綜合應(yīng)用題：關(guān)于PV操作：1、桌上有一空盤，允許存放一只水果，爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一只水果供吃者取用。2、從讀卡機(jī)上讀進(jìn)N張卡片，復(fù)制并打印。要求復(fù)制的信息、打印的卡片與原卡片的信息完全一致。假設(shè)這一工作由3個(gè)進(jìn)程get，copy和put來(lái)完成，它們用了兩個(gè)緩沖區(qū)buffer1和buffer2,緩沖區(qū)只能容納一張卡片的信息。其中，進(jìn)程get的功能是依次將每張卡片上的信息從讀卡機(jī)上讀進(jìn)bufferl；進(jìn)程copy的功能是把bufferl中的信息復(fù)制到buffer2；進(jìn)程put的功能是取出buffer2中的信息并從

2、打印機(jī)上輸出。試用P，V操作描述3個(gè)進(jìn)程間可并發(fā)運(yùn)行的關(guān)系圖（或程序），要求說(shuō)明信號(hào)量的作用及信號(hào)量的初值，盡可能提高并發(fā)性。練習(xí)：某招待所有100個(gè)床位，住宿者入住要先登記（在登記表上填寫(xiě)姓名和床位號(hào)）。離去時(shí)要注銷登記（在登記表上刪去姓名和床位號(hào)）。請(qǐng)給出住宿登記及注銷過(guò)程的算法描述。有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上登記。該表中每個(gè)表項(xiàng)代表閱覽室中的一個(gè)座位。讀者離開(kāi)時(shí)要消掉其登記信息。閱覽室共有50個(gè)座位。登記表每次僅允許一位讀者進(jìn)行登記或注銷。讀者登記時(shí)，發(fā)現(xiàn)登記表滿，他在閱覽室外等待，直至有空位再登記進(jìn)入。試用Wait、Signal操作描述讀者行為。關(guān)于死鎖即銀行家算法，安

3、全算法問(wèn)題（Pll0）3、設(shè)系統(tǒng)中有三類資源Rl、R2、R3和R4,又設(shè)系統(tǒng)中有5個(gè)進(jìn)程Pl，P2，P3，P4和P5.在T0時(shí)刻系統(tǒng)狀態(tài)如下：資源最大需求量已分配資源量剩余資源量進(jìn)程R1R2R3R4R1R2R3R4R1R2R3R4P1864112112113P243313111P3101324132P433313220P554631131系統(tǒng)是否處于安全狀態(tài)？若是，則給出進(jìn)程安全序列。若P2提出申請(qǐng)1112，系統(tǒng)能否分配給他？系統(tǒng)滿足P2要求后，系統(tǒng)是否立即進(jìn)入死鎖？4、（設(shè)有3個(gè)進(jìn)程P、Q、R,它們共享10個(gè)同類資源，P、Q、R進(jìn)程的資源最大需求量依次為4、7和8?，F(xiàn)假定它們對(duì)資源的請(qǐng)示序列

4、如下表所示：進(jìn)程運(yùn)行順序及申請(qǐng)資源情況步驟進(jìn)程申請(qǐng)資源數(shù)1P22Q4為了避免死鎖，系統(tǒng)分配資源時(shí)采用銀行家算法。如果申請(qǐng)資源得不到滿足，進(jìn)程就轉(zhuǎn)入阻塞態(tài)。根據(jù)上述信息，試描述各步驟結(jié)束時(shí)，申請(qǐng)資源的進(jìn)程是得到滿足，還是轉(zhuǎn)入阻塞狀態(tài)，為什么？（起始狀態(tài)：各進(jìn)程均不擁有資源，無(wú)進(jìn)程處于阻塞態(tài)）關(guān)于進(jìn)程調(diào)度算法問(wèn)題：5. 假設(shè)系統(tǒng)有5個(gè)進(jìn)程，他們的到達(dá)時(shí)間和服務(wù)時(shí)間如表，忽略I/O及其他開(kāi)銷采用FCFS、SPF（搶、非搶）、RR（搶、非搶，時(shí)間片為1）、HRRN（搶、非搶）、FB（搶、非搶i的時(shí)間片為2i-1）調(diào)度算法，計(jì)算各進(jìn)程的完成時(shí)間，周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間，平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)

5、程名到達(dá)時(shí)間服務(wù)時(shí)間A03B26C44D65E82練習(xí)有五個(gè)批處理的作業(yè)（A、B、C、D和E）幾乎同時(shí)到達(dá)一個(gè)計(jì)算中心，估計(jì)的運(yùn)行時(shí)間分別為2min、4min、6min、8min、10min,它們的優(yōu)先數(shù)分別為1、2、3、4、5（1為最低優(yōu)先級(jí)）。對(duì)下面的每種調(diào)度算法，分別計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間。（1）最高優(yōu)先級(jí)優(yōu)先（2）時(shí)間片輪轉(zhuǎn)（時(shí)間片為2min）FCFS（作業(yè)到達(dá)的順序?yàn)镃,D,B,E,A）（4）短作業(yè)優(yōu)先關(guān)于頁(yè)面置換算法問(wèn)題：6、在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，加入一個(gè)作業(yè)的頁(yè)面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5，目前他還沒(méi)有任何頁(yè)面裝入內(nèi)存，當(dāng)分配給該作業(yè)的物理塊數(shù)分別為3、

6、4時(shí)，請(qǐng)分別計(jì)算采用OPT、LRU、FIFO頁(yè)面淘汰算法時(shí)訪問(wèn)過(guò)程中的缺頁(yè)次數(shù)和缺頁(yè)率關(guān)于移臂調(diào)度問(wèn)題：7、假設(shè)磁盤有200個(gè)磁道，磁盤請(qǐng)求隊(duì)列中是一些隨機(jī)請(qǐng)求，他們按照到達(dá)的次序分別處于55、58、39、18、90、160、150、38、184號(hào)磁道上，當(dāng)前磁頭在80號(hào)磁道上，并向磁道號(hào)增加的方向上移動(dòng)。請(qǐng)給出按FCFS、SSTF、SCAN、CSCAN算法進(jìn)行磁盤調(diào)度時(shí)滿足請(qǐng)求的次序，畫(huà)出移臂調(diào)度圖。關(guān)于地址變換問(wèn)題：8、某計(jì)算機(jī)系統(tǒng)主存采用請(qǐng)求分頁(yè)管理技術(shù)，主存容量為1MB，被劃分為256塊，每塊大小為4KB。假設(shè)某個(gè)作業(yè)共有5個(gè)頁(yè)面，其中0，1,2三個(gè)頁(yè)面已分別裝入到主存4,9,11三個(gè)

7、物理塊中，另外兩個(gè)頁(yè)面沒(méi)有裝入主存。該作業(yè)的頁(yè)面變換表（PMT）如下表所示。表中的狀態(tài)為0表示頁(yè)面已經(jīng)裝入到內(nèi)存中，為1表示沒(méi)有裝入內(nèi)存。問(wèn)題： 若給定一個(gè)邏輯地址為9016，其物理地址是多少？畫(huà)出地址變換圖。 若給定一個(gè)邏輯地址為12388，其物理地址是多少？地址變換過(guò)程中會(huì)出現(xiàn)什么問(wèn)題？出現(xiàn)問(wèn)題應(yīng)如何解決？ 若給定一個(gè)邏輯地址，頁(yè)號(hào)為3，頁(yè)內(nèi)地址為714，求其物理地址是多少？畫(huà)出地址變換圖。 若給定一個(gè)邏輯地址為10256，其物理地址是多少？地址變換過(guò)程中會(huì)出現(xiàn)什么問(wèn)題？其他：10、圖中將一組進(jìn)程分為4類，假定各類進(jìn)程之間采用優(yōu)先級(jí)調(diào)度，每類進(jìn)程內(nèi)部采用時(shí)間答：優(yōu)先級(jí)1（最低）11、某系統(tǒng)

8、的進(jìn)程狀態(tài)轉(zhuǎn)換如下圖所示，請(qǐng)問(wèn)：(1)引起各種狀態(tài)轉(zhuǎn)換的的典型事件。(2)當(dāng)一個(gè)進(jìn)程的狀態(tài)變化會(huì)引起另一個(gè)進(jìn)程的狀態(tài)變換，說(shuō)明下列因果變遷是否可能發(fā)生，其原因是什么？1)3-12)3-23)2-1答案：綜合應(yīng)用題：1、intS=1;/S表示盤子是否為空intSa=O;/Sa表示盤中是否有蘋果；intSb=0;/Sb表示盤中是否有桔子；父親while(TRUE)Wait(S);將水果放入盤中;if(放入的是桔子)Signal(Sb);ElseSignal(Sa);兒子while(TRUE)Wait(Sb);從盤中取出桔子；Signal(S);吃桔子;女兒while(TRUE)Wait(Sa);從

9、盤中取出蘋果；Signal(S);吃蘋果;父親-母親-兒子-女兒一個(gè)蘋果或桔子信號(hào)量：s=l(空盤);sl=O(蘋果);s2=0(桔子)；爸爸：while(true)wait(s);放蘋果;signal(s1);媽媽：while(true)wait(s);放桔子;signal(s2);兒子：while(true)wait(s2);取桔子;signal(s);女兒：while(true)wait(sl);取蘋果;signal(s);父親-母親-兒子-女兒兩個(gè)蘋果或桔子信號(hào)量：s=2(可用);s1=0(蘋果);s2=0(桔子);mutex=1;爸爸：wait(s);wait(mutex);放蘋果;

10、signal(sl);signal(mutex);媽媽：wait(s);wait(mutex);放桔子;signal(s2);signal(mutex);兒子：wait(s2);wait(mutex);取桔子;signal(s);signal(mutex);女兒：wait(s1);wait(mutex);取蘋果;signal(s);signal(mutex);2、設(shè)互斥信號(hào)量S1,S2初值為1,分別用于對(duì)bufferl和buffer2的互斥訪問(wèn)；同步信號(hào)量Sn1,Sn2初值為1，分別表示bufferl和buffer2初始狀態(tài)為空閑，可以放一張卡片信息；同步信號(hào)量Sm1,Sm2初值為0,分別表示

11、bufferl和buffer2中的信息還沒(méi)有(或已被取用了)。用P，V操作完成這3個(gè)并發(fā)進(jìn)程間能正確運(yùn)行的程序如下：BEGINS1,S2,Sn1,Sn2,Sm1,Sm2:semaphore;S1=S2=1;Sn1=Sn2=1;Sm1=Sm2=0;CobeginProcessproducegetBeginL1:從讀卡機(jī)讀進(jìn)一張卡片信息；P(Sn1);P(S1);將信息放入buffer1;V(Sm1);V(S1);GotoL1EndProcessproducecopyBeginL2:P(Sm1);P(S1)；從buffer1復(fù)制信息；V(Sn1);V(S1);P(Sn2);P(S2);將復(fù)制的信息

12、放入buffer2;V(Sm2);V(S2);GotoL2EndProcessproduceputBeginL3:P(Sm2);P(S2);從buffer2取信息；V(Sn2);V(S2);把信息從打印機(jī)輸出；GotoL3EndCoend;END3、過(guò)程略經(jīng)驗(yàn)證該系統(tǒng)處于安全狀態(tài)，安全的序列是p4,p5,p3,p2,p14、步驟1、P申請(qǐng)2滿足步驟2、Q申請(qǐng)2滿足步驟3、R申請(qǐng)2步驟4、Q申請(qǐng)2滿足進(jìn)入阻塞隊(duì)列步驟5、R申請(qǐng)2步驟6、P申請(qǐng)2進(jìn)入阻塞隊(duì)列滿足5、略，見(jiàn)第三章作業(yè)6、OPT:最佳置換算法，頁(yè)數(shù)3頁(yè)面走向432143543215缺頁(yè)VVVVV以后最長(zhǎng)不用21115443321233

13、34335以后馬上可能用44443443555缺頁(yè)7次，缺頁(yè)率為7/12OPT：最佳置換算法，頁(yè)數(shù)4頁(yè)面走向432143543215缺頁(yè)VVVV以后最長(zhǎng)不用111544343212322222533343325以后馬上可能用444434432555缺頁(yè)6次，缺頁(yè)率為6/12LRU：3：缺頁(yè)10次，缺頁(yè)率10/124：缺頁(yè)8次，缺頁(yè)率8/12FIFO：3：缺頁(yè)9次，缺頁(yè)率9/124：缺頁(yè)10次，缺頁(yè)率10/128、在請(qǐng)求分頁(yè)的存儲(chǔ)管理系統(tǒng)中，系統(tǒng)是通過(guò)查頁(yè)表來(lái)進(jìn)行地址轉(zhuǎn)換的。對(duì)于本題中采用的頁(yè)面大小為4KB,即頁(yè)內(nèi)相對(duì)地址為12位。首先從虛擬地址中分離出頁(yè)號(hào)和頁(yè)內(nèi)地址。9016/4096=2，所

14、以頁(yè)號(hào)為2,頁(yè)內(nèi)地址為824。查頁(yè)表知道2號(hào)頁(yè)對(duì)應(yīng)的物理塊號(hào)為11,即物理地址為：11*4096=45056，再加上頁(yè)內(nèi)地址后其真正的物理地址為：45880。頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)頁(yè)04192113411824首先從虛擬地址中分離出頁(yè)號(hào)和頁(yè)內(nèi)地址。12388/4096=3，所以頁(yè)號(hào)為3，頁(yè)內(nèi)地址為100。查頁(yè)表知道3號(hào)頁(yè)對(duì)應(yīng)的物理塊號(hào)，發(fā)現(xiàn)其物理塊號(hào)不在內(nèi)存，此時(shí)可能發(fā)生缺頁(yè)中斷，從磁盤把對(duì)應(yīng)的頁(yè)號(hào)裝入到內(nèi)存物理塊。假設(shè)此時(shí)物理內(nèi)存還有足夠的空閑塊，則不需要淘汰已經(jīng)裝入的頁(yè)面。設(shè)找到的空閑塊號(hào)為7，則邏輯地址12385所對(duì)應(yīng)的的物理地址為：7*4096+100=28772。9、在分頁(yè)的存儲(chǔ)管理系統(tǒng)中，頁(yè)面大小是2Kb系統(tǒng)是通過(guò)查頁(yè)表來(lái)進(jìn)行地址轉(zhuǎn)換的。虛擬地址頁(yè)號(hào)為3,頁(yè)內(nèi)地址為714。查頁(yè)表知道3號(hào)頁(yè)對(duì)應(yīng)的物理塊號(hào)為2,即物理地址為：2*2048=4096，再加上頁(yè)內(nèi)地址后其真正的物理地址為：4810。首先從虛擬地址中分離出頁(yè)號(hào)和頁(yè)內(nèi)地址。10256/2048=5,所以頁(yè)號(hào)為5,頁(yè)內(nèi)地址為16。查頁(yè)表知道5號(hào)頁(yè)沒(méi)有，所以此時(shí)發(fā)生越界中斷。10、答:各類類進(jìn)程之間采用優(yōu)先級(jí)調(diào)度,而同類進(jìn)程內(nèi)部采用時(shí)間片輪轉(zhuǎn)調(diào)度。先進(jìn)行優(yōu)先級(jí)4的進(jìn)程調(diào)度，P1,P2,P3按時(shí)間片進(jìn)行輪轉(zhuǎn)；等P1,P2,P3均執(zhí)行