1、學習-好資料第三章練習題及答案1. 在單道環境下，某批處理有四道作業，已知它們進入系統的時刻、估計運行時間如下:作業進入時刻（h）運行時間（h）18.002.0028.500.5039.000.1049.500.20設系統每次只選擇一個作業進入主機，分別給出在FCFS,SJF,HRNf法中這組作業的運行順序、平均周轉時間和平均帶權周轉時間。2. 為什么說多級反饋隊列能較好地滿足各種用戶的需要？3. 有一個多道程序系統，有用戶空間100KB,并規定作業相應程序裝入內存連續區域，并不能被移動，作業調度和進程調度均采用FCFSI法。現有一批作業，已知條件如下：作業名進入輸入井時間需計算時間（分）需內

2、存量（KB）A8:064215B8:183060C8:302450D8:362410E8:421220假定所有作業都是計算型作業并且忽略系統調度所化的時間。計算各作業被選中裝入內存的時間、開始執行的時間、結束執行的時間、周轉時間和帶權周轉時間。4. 上例中，其他假設條件不變，僅把作業的調度算法改為按 SF算法，進程仍采用FCFSI法。5. 作業調度的性能評價標準有哪些？這些性能評價在任何情況下都能反映調度策略的優 劣嗎？6. 什么叫無限期圭寸鎖（indefinite blocking） ?它在什么情況下出現？7. 作業調度算法選擇作業的原則，可以是保證系統的吞吐量大、可以是對用戶公平合理、可以

3、是充分發揮系統資源的利用率。請分別指出先來先服務、最短作業優先、I/O量大與CPI量大的作業搭配3種調度算法，體現了那種選擇作業的原則？8. 假定待處理的三個作業的到達時間和運行時間如下，若采用調度算法、，這些 作業的平均周轉時間是多少？作業名到達時間（時）執行時間10.0820.4431.01 FCFS: SJF; 考慮一下如何改善 SJF的性能，并計算新方法的平均周轉時間?9.假定要在一臺處理機上執行下列作業:作業執行時間優先級1103211323414552且假定這些作業達到的次序是1，2，3，4，5。給出Gantt圖來說明分別使用 FCFS, RR（時間片=1），SJF以及非搶占優先調

4、度算法時 這些作業的執行情況；（注：Gantt圖是描述進程/作業執行情況的一種直觀形式，它展 示了作業/進程執行過程中瞬時段或時間片的變化分布情況。）針對上述每一調度算法，給出每個作業的周轉時間；就上述每一調度算法，求出每個作業相應的等待時間；10. 設有5個就緒進程，它們的本次 CPU周期的長度、初始優先數及進入就緒隊列的相對時刻 如下所示：進程CPU 周期(ms)優先數進入時刻（ms）P13250P2430P3850P4260P516416規定：小的優先數表示高的優先級。畫出下列兩種情況的Gantt圖，計算它們的平均等待時間、平均周轉時間和平均帶權周轉時間。非剝奪的靜態設置方式；剝奪式的動

5、態設置方式，不妨設現行進程每連續執行12ms后，其優先數加 1 （即優先級降低），而就緒進程每 40ms后，其優先數減1。11. 有3道作業構成如下，它們在一個系統中運行，該系統有輸入/輸出設備各一臺。A進程：輸入32s,計算8s,輸出5sB進程：輸入21s，計算14s，輸出35sC進程：輸入12s，計算32s，輸出15s問3道程序順序執行時最短需要多少時間？為了充分發揮各設備效能，3道程序并發執行最短需要多少時間？（不計系統開銷時間）12. 在一個實時系統中，有兩個周期性實時任務A和 B,任務A要求每40 ms執行一次，執行時間為20 ms ;任務B要求每100ms執行一次，執行時間為 50

6、 ms。請參考課堂相關知識畫出在200mS寸間內，任務A和B調度情況示意圖。并標出任務 A和B每一次執行的時間。習題解答：1.解：下面我們用一張表幫助理解作業進入時刻運行時間開始時刻完成時刻周轉時間帶權周轉18.002.008.0010.002.001.0028.500.5010.0010.502.004.0039.000.1010.5010.601.6016.0049.500.2010.6010.801.306.50平均周轉時間T=1.725(h) 平均帶權周轉時間 T'=6.875(h)6.9027.50FCFS算法的調度順序為：1宀2宀3 t 4。作業進入時刻運行時間開始時刻完成

7、時刻周轉時間帶權周轉18.002.008.0010.002.001.0028.500.5010.3010.802.304.6039.000.1010.0010.101.1011.0049.500.2010.1010.300.804.00平均周轉時間T=1.55(h) 平均帶權周轉時間T'=5.15(h)6.2020.60SJF算法的調度順序為：1 t 3 t 4t 2。作業進入時刻運行時間開始時刻完成時刻周轉時間帶權周轉18.002.008.0010.002.001.0028.500.5010.1010.602.104.2039.000.1010.0010.101.1011.0049.

8、500.2010.6010.801.306.50平均周轉時間T=1.625(h) 平均帶權周轉時間 T'=5.675(h)6.5022.70HRNI法的調度順序為：1 t 3 t 2t 4。2.答：多級反饋隊列是綜合了 FCFS RR HPF三種算法的一種剝奪式的調度算法，它根據 進程運行情況的反饋信息動態地改變進程的優先級，按優先級級別組織設置各就緒隊 列，并規定各就緒隊列不同的 CPU寸間片，對同一隊列中的各就緒進程按FCFS或RF算法調度，因而能較好地滿足各種用戶的需要。3. 解:作業名裝入內存開始執行結束執行周轉(分)帶權周轉A8:068:068:4842(1)42/42B8:

9、188:489:1860(2)60/30D8:369:189:4266(2.75)66/24C9:189:4210:0696(4)96/24E9:1810:0610:1896(8)96/125個作業的平均周轉時間和帶權周轉時間為：T=72(分)，T'3.554. 解：作業名裝入內存開始執行結束執行周轉(分)帶權周轉A8:068:068:4842(1)42/42B8:188:489:1860(2)60/30D8:369:189:4266(2.75)66/24E9:189:429:5472(4)72/24C9:189:5410:18108(8)108/125個作業的平均周轉時間和帶權周轉時

10、間為：T=69.6(分)，T'3.255. 答：對于批處理系統主要以作業的平均周轉時間或平均帶權周轉時間來衡量調度策略的優劣；而對于分時系統，除了要保證系統的吞吐量大、資源利用率高之外，還應保證用戶能容忍的響應時間；實時系統的主要標志則是滿足用戶要求的時限(截止)時間。6. 答:無限期封鎖也叫饑餓(starvation),即一個具有低優先級的進程決無運行的機會。當CPU接連不斷地被較高優先級的作業占用時就可能出現這樣的情況。7. 答：系統的吞吐量大是最短作業優先算法，因為SJF使作業的平均周轉時間有明顯的改善，從而使系統在單位時間內處理的作業數增多。對用戶公平合理是先來先服務算法。因為

11、對用戶按照作業進入輸入井時間的先后調度，先來先服務，對每個用戶都是公平的。發揮系統資源的利用率是I/O量大與CPU!大的作業搭配算法。因為這種算法使I/O與CPU 設備都忙碌，并行性好，系統的效率高。8. 答： FCFS: 10.53(8-0)+(12-0.4)+(13-1)/3注意：應減去達到時間。 SJF: 9.53 分析：由于我們事先并不知道兩個較短的作業將很快到達，所以在時刻0,我們選擇了作業1。如果讓CPU在第一個時間單位空閑，然后使用SJF調度策略，該算法稱為“未來知識調度算法FKS ”。當然在本例中，由于作業1和2在空閑時間處于等待狀態，它們的等待時間會增加。FKS:6.86(2

12、-1)+(6-0.4)+(14-0)/3=6.869. 解：執行情況的Gantt圖如下所示：FCFS:1(10)2(1)3(2)4(1)5(5)RR:123451351515151SJF:24351Priority:25134與這些作業相對應的周轉時間如下:作業FCFSRRSJFPriority110191916211211313741841442195191491與這些作業相對應的等待時間如下:作業FCFSRRSJFPriority1099621010031152164133118514942(注：等待時間指作業在就緒隊列中等待所花費的時間，但有些書等待時間指的是進程 從進入就緒隊列到獲得

13、CPU時所經歷的時間，這樣對于 RR的等待時間就有兩種不同的答 案。) SJF具有最小平均等待時間。10.解:執行情況如下：P2P1P5P3P40436526062平均等待時間 W=(4+0+52+60+(36-16)/5=27.2(ms) 平均周轉時間 T=(36+4+60+62+(52-16)/5=39.6(ms) 平均帶權周轉時間 T' =8.575(ms)執行情況如下：354556P2P1P5P3P4P1041632404262平均等待時間 W=(4+38)+0+32+40+0)/5=22.8(ms)平均周轉時間 T=(62+4+40+42+(32-16)/5=32.8(ms)平均帶權周轉時間 T' =5.99(ms)(分析：當進程P5于相對時刻16ms進入就緒隊列時，因其優先數小于現行進程P1的優先數，故進程剝奪，同時P1因連續執行了 12ms而優先數被加1;在P5和P3相繼執行完后，P4因己連續等待40ms，故其優先數被減 1，此時P4的優先數小于 P1的優先數，于是 P4 先于P1執行。)11.解：3道程序順序執行時最短需要32+8+5+21+14+35+12+32+