操作系統(tǒng)復(fù)習(xí)題計(jì)算題

1、復(fù)習(xí)題一、 假定在單CPU條件下有下列要執(zhí)行的作業(yè)： 作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先級(jí)1010221433235（高）（1）用一個(gè)執(zhí)行時(shí)間圖描述在采用非搶占優(yōu)先級(jí)算法時(shí)執(zhí)行這些作業(yè)的情況；（2）對(duì)于上述算法，各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間是多少？平均周轉(zhuǎn)時(shí)間是多少？（3）對(duì)于上述算法，各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間是多少？平均帶權(quán)周轉(zhuǎn)時(shí)間是多少二、 有兩個(gè)程序，A程序按順序使用CPU 10S，使用設(shè)備甲5S，使用CPU 5S，使用設(shè)備乙10S，最后使用CPU 10S。B程序按順序使用設(shè)備甲10S，使用CPU 10S，使用設(shè)備乙5S，使用CPU 5S，使用設(shè)備乙10S。在順序環(huán)境下先執(zhí)行A程序再執(zhí)行B程序，CPU的利用率

2、是多少？提示：CPU利用率=CPU運(yùn)行時(shí)間/程序運(yùn)行時(shí)間。三、 在單機(jī)系統(tǒng)中，系統(tǒng)中各個(gè)進(jìn)程到達(dá)就緒隊(duì)列的時(shí)刻、執(zhí)行時(shí)間和優(yōu)先級(jí)如下表所示。假設(shè)進(jìn)程的調(diào)度時(shí)間忽略不計(jì)。請(qǐng)分別給出采用下面不同的進(jìn)程調(diào)度算法時(shí)各個(gè)進(jìn)程的調(diào)度次序，畫出執(zhí)行時(shí)間圖，并計(jì)算平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)就緒隊(duì)列的時(shí)刻執(zhí)行時(shí)間（ms）優(yōu)先級(jí)P1033P2265P3441（高）P4652P5824（1）先來先服務(wù)調(diào)度算法；（2）時(shí)間片輪換調(diào)度算法（時(shí)間片為1ms）；（3）搶占式短進(jìn)程優(yōu)先調(diào)度算法；（4）搶占式優(yōu)先級(jí)調(diào)度算法；（5）非搶占式優(yōu)先級(jí)調(diào)度算法。 四、 假設(shè)在單CPU條件下有下列要執(zhí)行的作業(yè)： 作業(yè)到達(dá)時(shí)

3、間運(yùn)行時(shí)間優(yōu)先級(jí)A0103B111C223D314（高）E452（1）用一個(gè)執(zhí)行時(shí)間圖描述在非搶占優(yōu)先級(jí)算法時(shí)，執(zhí)行這些作業(yè)的情況。（2）用一個(gè)執(zhí)行時(shí)間圖描述在RR算法時(shí)（不考慮優(yōu)先級(jí)），執(zhí)行這些作業(yè)的情況（時(shí)間片為1單位）。五、 設(shè)系統(tǒng)中只有一臺(tái)打印機(jī)，有三個(gè)用戶的程序在執(zhí)行過程中都要使用打印機(jī)輸出計(jì)算結(jié)果。設(shè)每個(gè)用戶程序?qū)?yīng)一個(gè)進(jìn)程。問：這三個(gè)進(jìn)程間有什么樣的制約關(guān)系？試用P、V操作寫出這些進(jìn)程使用打印機(jī)的算法。六、 有三個(gè)進(jìn)程P1，P2和P3并發(fā)工作。進(jìn)程P1需用資源S3和S1；進(jìn)程P2需用資源S1和S2；進(jìn)程P3需用資源S2和S3?；卮穑?1)若對(duì)資源分配不加限制，會(huì)發(fā)生什么情況?為什

4、么?(2)為保證進(jìn)程正確工作，應(yīng)采用怎樣的資源分配策略?為什么?七、 用信號(hào)燈及P、V操作來描述右圖1、說明進(jìn)程的同步關(guān)系：2、設(shè)置信號(hào)燈，說明含義、初值。3、寫出程序描述（ 用P、V操作描述 P1、P2、P3）。主函數(shù)如下： main() int s13=0,s23=0; cobegin p1; p2; p3; coend八、 假定系統(tǒng)中有4個(gè)進(jìn)程P1、P2、P3、P4和3種類型的資源R1、R2、R3，數(shù)量分別為9、3、6，在t0時(shí)刻的資源分配情況如表所示。表 t0時(shí)刻的資源分配表資源情況進(jìn)程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3

5、P1322100222112P2613511102P3314211103P4422002420試問：（1）t0時(shí)刻是否安全？（2）P2發(fā)出請(qǐng)求向量Request2（1，0，1），系統(tǒng)能否將資源分配給它？（3）在P2申請(qǐng)資源后，若P1發(fā)出請(qǐng)求向量Request1（1，0，1），系統(tǒng)能否將資源分配給它？（4）在P1申請(qǐng)資源后，若P3發(fā)出請(qǐng)求向量Request3（0，0，1），系統(tǒng)能否將資源分配給它？九、 試化簡(jiǎn)圖1中的進(jìn)程資源圖，并利用死鎖定理給出相應(yīng)的理論。十、 試化簡(jiǎn)圖2中的進(jìn)程資源圖，并利用死鎖定理給出相應(yīng)的理論。十一、 在銀行家算法中，若出現(xiàn)下述資源分配情況：（5個(gè)進(jìn)程，4類資源）Proc

6、essAllocationNeedAvailableA003200121622B10001750C13542356D00320652E01140656試問： 該狀態(tài)是否安全，說明理由？ 若某進(jìn)程提出請(qǐng)求Request(1，2，2，2)后，系統(tǒng)能否將資源分配給它，為什么？十二、 考慮某一系統(tǒng)，它有四類資源R1，R2，R3，R4，有五個(gè)并發(fā)進(jìn)程P0，P1，P2，P3，P4。請(qǐng)按照銀行家算法解答下列問題：（1） 各進(jìn)程的最大資源請(qǐng)求和已分配的資源矩陣如表所示，計(jì)算各進(jìn)程仍需要請(qǐng)求的資源向量組成的矩陣。（2） 系統(tǒng)當(dāng)前是處于安全狀態(tài)嗎？（3） 當(dāng)進(jìn)程P2申請(qǐng)的資源分別為（0，1，0，0）時(shí)，系統(tǒng)能立即

7、滿足嗎？進(jìn)程AllocationMaxAvailableR1R2R3R4R1R2R3R4R1R2R3R4P0001200122100P120002750P200346656P323544356P403320652十三、 某虛擬存儲(chǔ)器的用戶編程空間有若干個(gè)頁面，每頁為1KB，內(nèi)存為16MB。假定某時(shí)刻已將一頁面調(diào)入內(nèi)存，該頁邏輯地址為4062B,已知頁表寄存器中頁表始址為2004B，頁表長(zhǎng)度為8，此時(shí)刻內(nèi)存部分?jǐn)?shù)據(jù)如下表，求該頁的物理地址，并指出該物理地址中的數(shù)據(jù)。內(nèi)存地址數(shù)據(jù)內(nèi)存地址數(shù)據(jù)2000B15352011B782001B6522012B5992003B712013B1112004B21

8、12014B34782005B452015B242006B32016B782007B12017B9622008B572018B77582009B52019B752010B4862020B85十四、 若干個(gè)等待訪問磁盤者依次要訪問的柱面為20，44，40，4，80，12，76，假設(shè)每移動(dòng)一個(gè)柱面需要3毫秒時(shí)間，移動(dòng)臂當(dāng)前位于40號(hào)柱面，請(qǐng)按下列算法分別計(jì)算為完成上述各次訪問總共花費(fèi)的尋找時(shí)間。 （1）先來先服務(wù)（FCFS） （2）最短尋找時(shí)間優(yōu)先調(diào)度（SSTF）（3）電梯調(diào)度法（SCAN）（4）單向掃描（循環(huán)掃描CSCAN）十五、 考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3

9、，7，6，3，2，1，2，3，6當(dāng)內(nèi)存塊數(shù)量分別為3時(shí)，試問FIFO、LRU這兩種置換算法的缺頁次數(shù)各是多少？（所有內(nèi)存開始時(shí)都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷）十六、 某移動(dòng)臂磁盤的柱面由外向里順序編號(hào)，假定當(dāng)前磁頭停在100號(hào)柱面且移動(dòng)臂方向是向里的，現(xiàn)有如下表所示的請(qǐng)求序列在等待訪問磁盤：        表 訪問磁盤請(qǐng)求序列請(qǐng)求次序12345678910柱面號(hào)190101608090125302014025回答下面的問題：  寫出分別采用“最短查找時(shí)間優(yōu)先算法”和“電梯調(diào)度算法”時(shí)，實(shí)際處理上述請(qǐng)

10、求的次序。  針對(duì)本題比較上述兩種算法，就移動(dòng)臂所花的時(shí)間（忽略移動(dòng)臂改向時(shí)間）而言，哪種算法更合適？簡(jiǎn)要說明之。十七、 有一個(gè)系統(tǒng)其內(nèi)存容量為1024KB，有8個(gè)作業(yè)同時(shí)到達(dá)，各作業(yè)需要的內(nèi)存量和運(yùn)行時(shí)間如表所示。作業(yè)編號(hào)ABCDEFGH需要內(nèi)存量（KB）140801006050301520運(yùn)行時(shí)間（S）31321323假定系統(tǒng)初啟時(shí)，將內(nèi)存1024KB按作業(yè)的編號(hào)順序分給各道作業(yè)，并假定是多CPU下，分配到內(nèi)存的作業(yè)都可以立即運(yùn)行。試問：（1） 1S后，內(nèi)存空白區(qū)按首次適應(yīng)和最佳適應(yīng)算法的鏈接方式鏈接，將如何鏈接？（2） 2S后，其內(nèi)存空白區(qū)按上述兩種算法如何鏈接？（3） 在（2

11、）后，此時(shí)有一個(gè)作業(yè)I要求進(jìn)入內(nèi)存，它需要內(nèi)存量為12KB，按上述兩種算法，將把哪一塊空白區(qū)分給它？十八、 某計(jì)算機(jī)系統(tǒng)的內(nèi)存容量為128KB，對(duì)存儲(chǔ)器采用可變分區(qū)的存儲(chǔ)管理辦法，現(xiàn)有3個(gè)作業(yè)(J1，J2，J3)在內(nèi)存，其存儲(chǔ)器的分配如圖所示。操作系統(tǒng)J1空閑區(qū)J2空閑區(qū)J3空閑區(qū)0K5K20K40K50K90K100K128K (1)現(xiàn)有一個(gè)需要25KB存儲(chǔ)空間的作業(yè)J4請(qǐng)求裝入內(nèi)存，若采用最先適應(yīng)分配算法來給J4分配空間。請(qǐng)給出裝入J4后的內(nèi)存分配表。 (2)若采用最優(yōu)適應(yīng)算法來給J4分配空間，給出裝入J4后的內(nèi)存分配表。 (3)在只有J1，J2，J3三個(gè)作業(yè)的情況下，J2運(yùn)行結(jié)束撤離后，

12、請(qǐng)給出J2撤離后的內(nèi)存分配表。十九、 某程序在邏輯地址100處有一條取數(shù)指令LOAD l，500，而500單元內(nèi)存放數(shù)據(jù)51888。假設(shè)程序被分配到內(nèi)存起始地址5000單元時(shí)，試用圖示意，采用下述各種方式下的該指令及數(shù)據(jù)地址的物理地址及相應(yīng)地址的變換過程。 (1)靜態(tài)重定位。 (2)采用重定位寄存器實(shí)現(xiàn)動(dòng)態(tài)重定位。 (3)采用頁表映像(映射)方式，假定頁面大小為100單元，其負(fù)表各頁映射到50，51、52，53，54，55，59物理頁上。二十、 對(duì)于如下的頁面訪問序列： 1，2，3，4，1，2，5，1，2，3，4，5。當(dāng)內(nèi)存塊數(shù)量分別為3和4時(shí)，試問：使用FIFO、LRU置換算法產(chǎn)生的缺頁中斷

13、是多少（畫出詳細(xì)過程）？（所有內(nèi)存開始時(shí)都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷）二十一、 給定下面的段表，已知下面的邏輯地址(其中方括號(hào)中的第一個(gè)元素為段號(hào)，第二個(gè)元素為段內(nèi)地址)求其對(duì)應(yīng)的物理地址：(1)0,430；(2)3,400；(3) l,10； (4) 2,2500； (5) 4,42；(6) 1,11。段號(hào)段長(zhǎng)段首地址06002191142300210090358013274961954二十二、 某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁為1KB，內(nèi)存為16KB。假定某時(shí)刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號(hào)和物理塊號(hào)的對(duì)照表如下：頁號(hào)物理塊號(hào)  頁號(hào)物理塊號(hào)03

14、  21117  38則邏輯地址0A5C（H）所對(duì)應(yīng)的物理地址是什么？要求：寫出主要計(jì)算過程。二十三、 某磁盤組有6片盤片，每片有兩個(gè)記錄面，存儲(chǔ)區(qū)域內(nèi)徑為22cm，外徑為33cm，道存儲(chǔ)密度為40道/cm，內(nèi)層位存儲(chǔ)密度為400b/cm，轉(zhuǎn)速為3000r/min（轉(zhuǎn)/分），問共有多少柱面？盤組總存儲(chǔ)量為多少？平均等待時(shí)間為多少？二十四、 假設(shè)有一個(gè)磁盤組共有100個(gè)柱面，每個(gè)柱面上有8個(gè)磁道，每個(gè)盤面被分成8個(gè)扇區(qū)?，F(xiàn)有一個(gè)含有6400邏輯記錄的文件，邏輯記錄的大小與扇區(qū)一致，該文件以順序結(jié)構(gòu)的形式被存儲(chǔ)到磁盤上。柱面、磁道、扇區(qū)的編號(hào)從“0”開始，邏輯記錄的編號(hào)也從“0

15、”開始。文件信息從0柱面、0磁道、0扇區(qū)開始存放，試問：（1） 該文件的3680個(gè)邏輯記錄應(yīng)該存放在什么位置？（2） 78柱面的6磁道的6扇區(qū)中存放了該文件的第幾號(hào)邏輯記錄？二十五、 假設(shè)一個(gè)可移動(dòng)磁頭的磁盤具有200個(gè)磁道，其編號(hào)為0199，當(dāng)它剛剛結(jié)束了125道的存取后，現(xiàn)正在處理143道的服務(wù)請(qǐng)求，假設(shè)系統(tǒng)當(dāng)前I/O請(qǐng)求序列以FIFO順序排列如下：86，147，91，177，94，150，102，175，130。試問對(duì)以下幾種磁盤I/O請(qǐng)求調(diào)度算法而言，滿足以上請(qǐng)求序列，磁頭將分別如何移動(dòng)，請(qǐng)列出磁道訪問次序，并計(jì)算出移動(dòng)距離？（1）先來先服務(wù)（FCFS）（2）最短尋找時(shí)間優(yōu)先調(diào)度（SS

16、TF）（3）電梯調(diào)度法（SCAN）（4）單向掃描（循環(huán)掃描CSCAN）二十六、 有一移動(dòng)臂磁盤，共100個(gè)磁道，每個(gè)磁道分8個(gè)扇區(qū)，磁盤轉(zhuǎn)速為500r/s（轉(zhuǎn)/秒），磁頭每移動(dòng)一個(gè)磁道需要10ms，有一個(gè)用戶請(qǐng)求訪問第25磁道第3扇區(qū)，并立即被系統(tǒng)響應(yīng)，假設(shè)磁頭當(dāng)時(shí)處于15道上，磁頭到達(dá)第25道時(shí)正處于1扇區(qū)的開始位置，試計(jì)算該用戶至少需要等待多長(zhǎng)時(shí)間？二十七、 假定磁盤轉(zhuǎn)速為6000r/min（轉(zhuǎn)/分），磁盤格式化時(shí)每個(gè)盤面被分為9個(gè)扇區(qū)，現(xiàn)有一個(gè)文件共有A，B，C，D，E，F(xiàn)，G，H，I九個(gè)邏輯記錄要存放在同一磁道上供處理程序使用，假設(shè)每個(gè)記錄的大小與扇區(qū)的大小相同，處理程序每次從磁盤讀出

17、一個(gè)記錄后要花2.5ms處理時(shí)間。若忽略其他輔助時(shí)間，請(qǐng)回答下列問題：（3） 現(xiàn)在假設(shè)已經(jīng)順序存放好這9個(gè)記錄，那么讀出該文件需要多少時(shí)間？（4） 為了使讀出文件需要的時(shí)間最短，請(qǐng)重新調(diào)整各個(gè)記錄的存放位置，畫出各個(gè)記錄的存放位置，計(jì)算該文件的讀出時(shí)間，并與（1）進(jìn)行比較說明。二十八、 某車站售票廳，任何時(shí)刻最多可容納20名購(gòu)票者進(jìn)入，當(dāng)售票廳中少于20名購(gòu)票者時(shí)，則廳外的購(gòu)票者可立即進(jìn)入，否則需在外面等待。若把一個(gè)購(gòu)票者看作一個(gè)進(jìn)程，請(qǐng)回答下列問題：         （1 ）用PV操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定

18、義信號(hào)量，寫出信號(hào)量的初值以及信號(hào)量各種取值的含義。         （2 ）在下列橫線中填入所定義的信號(hào)量，并把應(yīng)執(zhí)行的PV操作填入橫線中，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。         main() int ；       ；         進(jìn)入售票廳；   &#

19、160;     購(gòu)票；         退出；          ；         （3 ）若欲購(gòu)票者最多為n 個(gè)人，寫出信號(hào)量可能的變化范圍（最大值和最小值）。二十九、 設(shè)有三個(gè)人，M，Q，R，其中M負(fù)責(zé)采購(gòu)原材料并放到房間A中，Q從房間A中取出原材料并加工成產(chǎn)品后，放到房間B中，R從房間B中取出產(chǎn)品并銷售（房間A和B都恰好能放一件原材料）。試用P、V操作描述 M，Q，R三人實(shí)現(xiàn)上述工作的控制流程。(1)在下列橫線中寫出該定義的信號(hào)量及其初值。(2)根據(jù)所定義的信號(hào)量，把應(yīng)執(zhí)行的PV操作填入下列橫線中，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。main（ ） int ， ， ， ； cobegin /*下列進(jìn)程將并發(fā)執(zhí)行*/ M（ ）； Q（ ）； R（