山東大學操作系統(tǒng)復習題計算題

1、操作系統(tǒng)計算題、假定在單CPU條件下有下列要執(zhí)行的作業(yè):作業(yè)到達時間運行時間優(yōu)先級1010221433235 (高)(1)用一個執(zhí)行時間圖描述在采用非搶占優(yōu)先級算法時執(zhí)行這些作業(yè)的情況；(2)對于上述算法，各個作業(yè)的周轉時間是多少？平均周轉時間是多少？(3)對于上述算法，各個作業(yè)的帶權周轉時間是多少？平均帶權周轉時間是多少、有兩個程序，A程序按順序使用 CPU 10S,使用設備甲5S,使用CPU 5S,使用設備乙10S,最 后使用CPU 10S。B程序按順序使用設備甲 10S,使用CPU 10S ,使用設備乙5S,使用CPU 5s , 使用設備乙10S。在順序環(huán)境下先執(zhí)行 A程序再執(zhí)行B程序，

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

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

4、加限制，會發(fā)生什么情況？為什么？(2)為保證進程正確工作，應采用怎樣的資源分配策略？為什么？七、用信號燈及P、V操作來描述右圖1、說明進程的同步關系：2、設置信號燈，說明含義、初值。3、寫出程序描述( 用P、V操作描述 P1、P2、P3)。主函數(shù)如下：main()int s13=0,s23=0;cobeginpl；p2;p3；coend八、假定系統(tǒng)中有 4個進程P1、P2、P3、P4和3種類型的資源 R1、R2、R3,數(shù)量分別為9、3、6,在t0時刻的資源分配情況如表所示。表t0時刻的資源分配表(2) P2發(fā)出請求向量 Request2 (1, 0, 1),系統(tǒng)能否將資源分配給它？(3)在P2

5、申請資源后，若 P1發(fā)出請求向量 Requestl (1, 0, 1),系統(tǒng)能否將資源分配給它？(4)在P1申請資源后，若 P3發(fā)出請求向量 Request3 (0, 0, 1),系統(tǒng)能否將資源分配給它？九、試化簡圖1中的進程一一資源圖，并利用死鎖定理給出相應的理論。圖1資源分配圖十、試化簡圖2中的進程一一資源圖，并利用死鎖定理給出相應的理論。圖2資源分配圖在銀行家算法中，若出現(xiàn)下述資源分配情況：（5個進程，4類資源）ProcessAllocationNeedAvailableA003200121622B10001750C13542356D00320652E01140656試問： 該狀態(tài)是否安

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

7、02750P200346656P323544356P403320652、某虛擬存儲器的用戶編程空間有若干個頁面，每頁為 1KB,內存為16MB。假定某時刻已將一頁面調入內存，該頁邏輯地址為4062B,已知頁表寄存器中頁表始址為2004B ,頁表長度為8,此時刻內存部分數(shù)據如下表，求該頁的物理地址，并指出該物理地址中的數(shù)據。內存地址數(shù)據2000B15352001B6522003B712004B2112005B452006B32007B12008B572009B52010B486內存地址數(shù)據2011B782012B5992013B1112014B34782015B242016B782017B962

8、2018B77582019B752020B十四、若干個等待訪問磁盤者依次要訪問的柱面為20, 44, 40, 4, 80, 12, 76,假設每移動一個柱面需要3毫秒時間，移動臂當前位于40號柱面，請按下列算法分別計算為完成上述各次訪問總共花費的尋找時間。（1）先來先服務（FCFS ）（2）最短尋找時間優(yōu)先調度（SSTF ）（3）電梯調度法（SCAN）（4）單向掃描（循環(huán)掃描 C SCAN）卜五、考慮下述頁面走向：1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 當內存塊數(shù)量分別為 3 時,試問FIFO、LRU這兩種置換算法的

9、缺頁次數(shù)各是多少？（所有內存開始時都是空的，凡第一次用到的頁面都產生一次缺頁中斷）卜六、某移動臂磁盤的柱面由外向里順序編號，假定當前磁頭停在100號柱面且移動臂方向是向里的，現(xiàn)有如下表所示的請求序列在等待訪問磁盤：表訪問磁盤請求序列依次序12345678910主面號190101608090125302014025回答下面的問題：寫出分別采用“最短查找時間優(yōu)先算法”和“電梯調度算法”時，實際處理上述請求的次序。 針對本題比較上述兩種算法，就移動臂所花的時間（忽略移動臂改向時間）而言，哪種算法更合適？簡要說明之。十七、有一個系統(tǒng)其內存容量為 1024KB ,有8個作業(yè)同時到達，各作業(yè)需要的內存量和

10、運行時間如Word資料表所示。作業(yè)編號ABCDEFGH需要內存量(KB )140801006050301520運行時間(S)31321323假定系統(tǒng)初啟時，將內存 1024KB按作業(yè)的編號順序分給各道作業(yè)，并假定是多CPU下，分配到內存的作業(yè)都可以立即運行。試問：(1) 1S后，內存空白區(qū)按首次適應和最佳適應算法的鏈接方式鏈接，將如何鏈接？(2) 2s后，其內存空白區(qū)按上述兩種算法如何鏈接？(3) 在(2)后，此時有一個作業(yè) I要求進入內存，它需要內存量為12KB ,按上述兩種算法，將把哪一塊空白區(qū)分給它？十八、某計算機系統(tǒng)的內存容量為128KB，對存儲器采用可變分區(qū)的存儲管理辦法，現(xiàn)有3個作

11、業(yè)(J1,J2, J3)在內存，其存儲器的分配如圖所示。操作系統(tǒng)J1空閑區(qū)J2空閑區(qū)J3空閑區(qū)0K 5K 20K40K50K90K100K128K(1)現(xiàn)有一個需要25KB存儲空間的作業(yè)J4請求裝入內存，若采用最先適應分配算法來給J4分配空間。請給出裝入J4后的內存分配表。(2)若采用最優(yōu)適應算法來給J4分配空間，給出裝入 J4后的內存分配表。(3)在只有J1 , J2, J3三個作業(yè)的情況下，J2運行結束撤離后，請給出 J2撤離后的內存分配表。十九、某程序在邏輯地址 100處有一條取數(shù)指令 LOAD l , 500 ,而500單元內存放數(shù)據51888。假設程序被分配到內存起始地址5000單元

12、時，試用圖示意，采用下述各種方式下的該指令及數(shù)據地址Word資料的物理地址及相應地址的變換過程。(1)靜態(tài)重定位。(2)采用重定位寄存器實現(xiàn)動態(tài)重定位。采用頁表映像(映射)方式，假定頁面大小為100單元，其負表各頁映射到50, 51、52, 53, 54,55,，59物理頁上。、對于如下的頁面訪問序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。當內存塊數(shù)量分別為3和4時，試問：使用 FIFO、LRU置換算法產生的缺頁中斷是多少(畫出詳細過程)？(所有內存開始時都是空的，凡第一次用到的頁面都產生一次缺頁中斷)1、 給定下面的段表，已知下面的邏輯地址(其中方括號中的第一

13、個元素為段號，第二個元素為段內地址)求其對應的物理地址：(1)0,430 ; (2)3,400 ; (3) 1,10 ; (4) 2,2500 ; (5) 4,42 ; (6) 1,11。段號段長段首地址060021911423002100903580132749619542、 某虛擬存儲器的用戶編程空間共32個頁面，每頁為1KB ,內存為16KB。假定某時刻一用戶頁表中已調入內存的頁面的頁號和物理塊號的對照表如下：頁號物理塊號頁號物理塊號032111738則邏輯地址0A5c (H)所對應的物理地址是什么？要求：寫出主要計算過程。二十三、某磁盤組有6片盤片，每片有兩個記錄面，存儲區(qū)域內徑為22

14、cm ,外徑為33cm ,道存儲密度為40道/cm,內層位存儲密度為 400b/cm ,轉速為3000r/min (轉/分)，問共有多少柱面？盤 組總存儲量為多少？平均等待時間為多少？二十四、假設有一個磁盤組共有 100個柱面，每個柱面上有 8個磁道，每個盤面被分成8個扇區(qū)。現(xiàn)有一個含有 6400邏輯記錄的文件，邏輯記錄的大小與扇區(qū)一致，該文件以順序結構的形式被存儲到磁盤上。柱面、磁道、扇區(qū)的編號從“0”開始，邏輯記錄的編號也從“0”開始。文件信息從0柱面、 0磁道、0扇區(qū)開始存放，試問：(1) 該文彳的3680個邏輯記錄應該存放在什么位置？(2) 78柱面的6磁道的6扇區(qū)中存放了該文件的第幾

15、號邏輯記錄？二十五、假設一個可移動磁頭的磁盤具有200個磁道，其編號為 0199,當它剛剛結束了 125道的存取后，現(xiàn)正在處理 143道的服務請求，假設系統(tǒng)當前I/O請求序列以FIFO順序排列如下：86,147 , 91 , 177 , 94, 150 , 102 , 175 , 130。試問對以下幾種磁盤I/O請求調度算法而言，滿足以上請求序列，磁頭將分別如何移動，請列出磁道訪問次序，并計算出移動距離？(1)先來先服務(FCFS )(2)最短尋找時間優(yōu)先調度(SSTF )(3)電梯調度法(SCAN )(4)單向掃描(循環(huán)掃描 C-SCAN )二十六、有一移動臂磁盤，共 100個磁道，每個磁道

16、分 8個扇區(qū)，磁盤轉速為 500r/s (轉/秒)，磁Word資料頭每移動一個磁道需要 10ms,有一個用戶請求訪問第 25磁道第3扇區(qū)，并立即被系統(tǒng)響應，假設磁頭當日處于15道上，磁頭到達第 25道時正處于1扇區(qū)的開始位置， 試計算該用戶至少需要等待 多長時間？二十七、假定磁盤轉速為 6000r/min (轉/分)，磁盤格式化時每個盤面被分為9個扇區(qū)，現(xiàn)有一個文件共有 A,B,C,D,E,F,G,H, I九個邏輯記錄要存放在同一磁道上供處理程序使用，假設每個記錄的大小與扇區(qū)的大小相同，處理程序每次從磁盤讀出一個記錄后要花2.5ms處理時間。若忽略其他輔助時間，請回答下列問題：(3) 現(xiàn)在假設

17、已經順序存放好這9個記錄，那么讀出該文件需要多少時間？(4) 為了使讀出文件需要的時間最短，請重新調整各個記錄的存放位置，畫出各個記錄的存放位置，計算該文件的讀出時間，并與(1)進行比較說明。二十八、某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。 若把一個購票者看作一個進程，請回答下列問題：(1 )用PV操作管理這些并發(fā)進程時，應怎樣定義信號量，寫出信號量的初值以及信號量各種取 值的含義。(2 )在下列橫線中填入所定義的信號量，并把應執(zhí)行的 PV操作填入橫線中，以保證進程能夠正 確地并發(fā)執(zhí)行。main() int ；

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