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

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

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

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

5、P1322100222112P2613511102P3314211103P4422002420試問：（1）t0時刻是否安全？（2）P2發出請求向量Request2（1，0，1），系統能否將資源分配給它？（3）在P2申請資源后，若P1發出請求向量Request1（1，0，1），系統能否將資源分配給它？（4）在P1申請資源后，若P3發出請求向量Request3（0，0，1），系統能否將資源分配給它？九、 試化簡圖1中的進程資源圖，并利用死鎖定理給出相應的理論。十、 試化簡圖2中的進程資源圖，并利用死鎖定理給出相應的理論。十一、 在銀行家算法中，若出現下述資源分配情況：（5個進程，4類資源）Proc

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

7、滿足嗎？進程AllocationMaxAvailableR1R2R3R4R1R2R3R4R1R2R3R4P0001200122100P120002750P200346656P323544356P403320652十三、 某虛擬存儲器的用戶編程空間有若干個頁面，每頁為1KB，內存為16MB。假定某時刻已將一頁面調入內存，該頁邏輯地址為4062B,已知頁表寄存器中頁表始址為2004B，頁表長度為8，此時刻內存部分數據如下表，求該頁的物理地址，并指出該物理地址中的數據。內存地址數據內存地址數據2000B15352011B782001B6522012B5992003B712013B1112004B21

8、12014B34782005B452015B242006B32016B782007B12017B9622008B572018B77582009B52019B752010B4862020B85十四、 若干個等待訪問磁盤者依次要訪問的柱面為20，44，40，4，80，12，76，假設每移動一個柱面需要3毫秒時間，移動臂當前位于40號柱面，請按下列算法分別計算為完成上述各次訪問總共花費的尋找時間。 （1）先來先服務（FCFS） （2）最短尋找時間優先調度（SSTF）（3）電梯調度法（SCAN）（4）單向掃描（循環掃描CSCAN）十五、 考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3

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

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

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

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

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

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

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

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

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

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

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