山東大學(xué)操作系統(tǒng)復(fù)習(xí)題計(jì)算題

1、操作系統(tǒng)計(jì)算題、假定在單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

2、程序，CPU的利用率是多少？提示： 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條件下有下列要

3、執(zhí)行的作業(yè)：作業(yè)到達(dá)時(shí)間運(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ì)資源分配

4、不加限制，會(huì)發(fā)生什么情況？為什么？(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;cobeginp1；p2;p3;coendR1、R2、R3,數(shù)量分別為 9、3、6,八、假定系統(tǒng)中有 4個(gè)進(jìn)程P1、P2、P3、P4和3種類型的資源在t0時(shí)刻的資源分配情況如表所示。表t0時(shí)刻的資源分配表源情進(jìn)況程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R

5、3R1R2R3P1322100222112P2613511102P3314211103P4422002420試問：(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)能否將資源分配 給它？九、試化簡圖1中的進(jìn)程一一資源圖，并利用死鎖定理給出相應(yīng)的理論。十、試化簡圖2中的進(jìn)程一一資源圖，并利用死鎖定理給出相應(yīng)的理論。圖2資源分配圖在銀行家算法

6、中，若出現(xiàn)下述資源分配情況：(5個(gè)進(jìn)程，4類資源)ProcessAllocationNeedAvailableA003200121622B10001750C13542356D00320652E01140656試問： 該狀態(tài)是否安全，說明理由？ 若某進(jìn)程提出請(qǐng)求 Request。，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)前是處于安全

7、狀態(tài)嗎？(3) 當(dāng)進(jìn)程P2申請(qǐng)的資源分別為(0, 1, 0, 0)時(shí)，系統(tǒng)能立即滿足嗎？內(nèi)存地址數(shù)據(jù)2000B15352001B6522003B712004B2112005B452006B32007B12008B572009B52010B486內(nèi)存地址數(shù)據(jù)2011B782012B5992013B1112014B34782015B242016B782017B9622018B77582019B752020B進(jìn) 程AllocationMaxAvailableR1R2R3R4R1R2R3R4R1R2R3R4P0001200122100P120002750P200346656P323544356P403

8、320652、某虛擬存儲(chǔ)器的用戶編程空間有若干個(gè)頁面，每頁為 1KB,內(nèi)存為16MB。假定某時(shí)刻已將一頁面調(diào)入內(nèi)存，該頁邏輯地址為4062B,已知頁表寄存器中頁表始址為2004B,頁表長度為8 ,此時(shí)刻內(nèi)存部分?jǐn)?shù)據(jù)如下表，求該頁的物理地址，并指出該物理地址中的數(shù)據(jù)。十四、若干個(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)掃描

9、 C - SCAN )十五、考慮下述頁面走向：1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 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)先算法”和“電

10、梯調(diào)度算法”時(shí)，實(shí)際處理上述請(qǐng)求的次序。 針對(duì)本題比較上述兩種算法，就移動(dòng)臂所花的時(shí)間(忽略移動(dòng)臂改向時(shí)間) 而言，哪種算法更合適?簡要說明之。十七、有一個(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ū)按上述兩種算法如

11、何鏈接？(3) 在(2)后，此時(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ū)0K 5K 20K40K50K90K100K128K(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è)

12、作業(yè)的情況下，J2運(yùn)行結(jié)束撤離后，請(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ù)

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

14、頁號(hào)和物理塊號(hào)的對(duì)照表如下：頁號(hào)物理塊號(hào)頁號(hào)物理塊號(hào)032111738則邏輯地址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ū)。現(xiàn)有一個(gè)含有 6400邏輯記錄的文件，邏輯記錄的大小與扇區(qū)一致，該文件以順序結(jié)構(gòu)的形式被存 儲(chǔ)到磁盤上。柱面、磁道

15、、扇區(qū)的編號(hào)從“0”開始，邏輯記錄的編號(hào)也從“ 0”開始。文件信息從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)列出磁道訪問次序

16、，并計(jì)算出移動(dòng)距離？(1)先來先服務(wù)(FCFS)(2)最短尋找時(shí)間優(yōu)先調(diào)度(SSTF(3)電梯調(diào)度法(SCAN )(4)單向掃描(循環(huán)掃描 C - SCAN )二十六、有一移動(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)日處于15道上，磁頭到達(dá)第25道時(shí)正處于1扇區(qū)的開始位置，試計(jì)算該用戶至少需要等待 多長時(shí)間？二十七、假定磁盤轉(zhuǎn)速為 6000r/min (轉(zhuǎn)/分)，磁盤格式化時(shí)每個(gè)盤面被分為9個(gè)扇區(qū)，現(xiàn)有一個(gè)文件共有A, B, C, D, E, F

17、, G, H, I九個(gè)邏輯記錄要存放在同一磁道上供處理程序使用，假設(shè)每個(gè)記錄的大小與扇區(qū)的大小相同，處理程序每次從磁盤讀出一個(gè)記錄后要花2.5ms處理時(shí)間。若忽略其他輔助時(shí)間，請(qǐng)回答下列問題：Word資料(3) 現(xiàn)在假設(shè)已經(jīng)順序存放好這 9個(gè)記錄，那么讀出該文件需要多少時(shí)間？(4) 為了使讀出文件需要的時(shí)間最短，請(qǐng)重新調(diào)整各個(gè)記錄的存放位置，畫出各個(gè)記錄的存放位置，計(jì)算該文件的讀出時(shí)間，并與(1)進(jìn)行比較說明。二十八、某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時(shí),則廳外的購票者可立即進(jìn)入，否則需在外面等待。 若把一個(gè)購票者看作一個(gè)進(jìn)程，請(qǐng)回答下列問題:(1 )

18、用PV操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號(hào)量，寫出信號(hào)量的初值以及信號(hào)量各種取 值的含義。(2 )在下列橫線中填入所定義的信號(hào)量，并把應(yīng)執(zhí)行的PV操作填入橫線中，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。main() int ；進(jìn)入售票廳；購票；退出；(3 )若欲購票者最多為 n個(gè)人，寫出信號(hào)量可能的變化范圍(最大值和最小值)。二十九、設(shè)有三個(gè)人，M, Q, R,其中M負(fù)責(zé)采購原材料并放到房間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 ()cobegin /*下列進(jìn)程將并發(fā)執(zhí)行*/M ()；Q ()；R();c