處理機調度教學提綱

1、處理機調度精品文檔1 .在批處理系統(tǒng)中,一個作業(yè)從提交給系統(tǒng)到運行結束退出系統(tǒng),通常有哪些作業(yè)狀態(tài)？你能說出這些狀態(tài)轉換的原因嗎？由哪些程序負責這些狀態(tài)之間的轉換？2 .簡述作業(yè)調度程序、中級調度程序和進程調度程序的功能,并指出這些調度程序通常配置于 什么操作系統(tǒng)中？3 .以下問題應由哪一級調度程序負責？(1)發(fā)生時間片中斷后,決定將處理機分給哪一個就緒進程？(2)在短期繁重負荷情況下,應將哪個進程掛起？3 3) 一個作業(yè)運行結束后,從后備作業(yè)隊列中選具備能夠裝入內存的作業(yè)？4 .在分時系統(tǒng)內部有必要設立作業(yè)調度程序嗎？為什么？5 .有三道程序其構成如下所示,它們在一個系統(tǒng)中運行,該系統(tǒng)有輸入

2、設備、輸出設備各一臺.A進程：輸入32秒,計算8秒,輸出5秒.B進程：輸入21秒,計算14秒,輸出35秒.C進程：輸入12秒,計算32秒,輸出15秒.試問：(1)三道程序順序執(zhí)行時需要最短時間多少？(2)為了充分發(fā)揮各設備效能,三道程序并發(fā)執(zhí)行,最短需要多少時間？(不計系統(tǒng)開銷時間)6 .進程調度方式有哪兩種？各適用于什么場合？7 .試述搶占調度方式中的三種搶占原那么.8 .調度隊列模型主要有哪三種？各適用于什么場合？9 .什么是作業(yè)周轉時間？請寫出作業(yè)平均周轉時間和作業(yè)帶權周轉時間的計算公式,并指出公 式中參數(shù)的含義.10 .什么是響應時間？分別寫出分時系統(tǒng)和實時系統(tǒng)對響應時間的要求.11

3、.舉例說明,為什么 FCFS算法對交互式用戶而言,并不是一種恰當?shù)倪M程調度模式.12 .什么是短作業(yè)(短進程)優(yōu)先調度？為什么 SJF(SPF)調度算法對長作業(yè)(長進程)不 利？13 .作業(yè)調度算法選擇作業(yè)的原那么,可以是保證系統(tǒng)吞吐量大,可以是對用戶公平合理,可以 是充分發(fā)揮系統(tǒng)資源的利用率.請分別指出先來先效勞、最短作業(yè)優(yōu)先表達了哪種選擇作業(yè)的 原那么.14 .優(yōu)先級調度算法有什么優(yōu)點？它適用于什么系統(tǒng)？15 .假定在一個多道批處理系統(tǒng)中,道數(shù)不受限制.當?shù)?1個作業(yè)進入輸入井后或內存中有 道程序完成后立即進行作業(yè)調度.現(xiàn)在有四道都是僅作計算而沒有請求設備輸入輸出的作業(yè), 它們進入輸入井的

4、時間、需要計算的時間及優(yōu)先級如下所示：作業(yè)名進入輸入井時間需要計算時間(分 鐘)優(yōu)先級(數(shù)大級 高)A8: 00601rB8: 1040121|C8: 20304D8: 30103(1)作業(yè)調度和進程調度均采用FCFS算法時,計算這批作業(yè)的T和W(2)作業(yè)調度采用SJF和進程調度采用 SPF算法時,計算這批作業(yè)的T和W,收集于網絡,如有侵權請聯(lián)系治理員刪除精品文檔(3)作業(yè)調度和進程調度均采用優(yōu)先級高者優(yōu)先算法時,計算這批作業(yè)的T和W約定,作業(yè)優(yōu)先級與進程優(yōu)先級相一致.16 .試比擬以下作業(yè)調度算法,對短作業(yè)的優(yōu)待程度,對長作業(yè)的虐待程度,哪些算法有可能 發(fā)生長作業(yè)挨餓(總得不到調度)現(xiàn)象？(

5、1)先來先效勞FCFS短作業(yè)優(yōu)先SJF17 .什么是時間片輪轉調度算法？它適用于什么場合？18 .假設某系統(tǒng)的調度如以下圖所示,其中時間片q=50ms,假定系統(tǒng)中只有 A、B兩個合作進程,它們的同步信號量S的初值為0.進程A的循環(huán)體是：執(zhí)行計算 20ms后,調用P(S)操作,然后11算30ms后返回起點循環(huán).進程B的循環(huán)體是：開始執(zhí)行計算30ms后,調用V ( S)操作,再計算20ms后返回起點循環(huán).假定 t=0時刻,A, B都在就緒隊列中,A在B之前,且忽略進程切換和PV操作本身所花的時間.試按以下表格寫出A、B兩進程,從t=0時刻開始,到t=170ms為止的狀態(tài)變化.時刻執(zhí)行態(tài)進程就序態(tài)進

6、程阻塞態(tài)進程發(fā)生何種事件T=019.指出下述各說法,為什么是不正確的？(1)短作業(yè)優(yōu)先是公平的.(2)越短的作業(yè)應該享受越好的效勞.(3)由于最短作業(yè)優(yōu)先調度是優(yōu)先選擇短作業(yè),故可用于分時系統(tǒng).20.為什么說多級反應隊列能較好地滿足各種用戶的需要？1 .參考答案作業(yè)通常有四種狀態(tài).提交狀態(tài),是程序員把存儲有作業(yè)實體信息的介質交給機房或用戶 通過終端鍵盤向計算機鍵入其作業(yè)實體信息時所處狀態(tài).后備狀態(tài),是作業(yè)實體信息已被輸入 到硬盤的輸入井中,建立了相應的JCB等,等待作業(yè)調度時所處狀態(tài).運行狀態(tài),是作業(yè)已被調度到裝入內存,創(chuàng)立了相應的進程、投入運行時的狀態(tài).完成狀態(tài),是作業(yè)運行結束或因錯 誤而終

7、止時,釋放所占全部資源,準備離開系統(tǒng)時的狀態(tài).提交狀態(tài)-后備狀態(tài),是系統(tǒng)操作員啟動作業(yè)注冊過程的結果.這過程中涉及脫機輸入程 序或聯(lián)機spooling系統(tǒng)的輸入進程,將作業(yè)實體信息轉儲到硬盤的輸入井中.另外,主要涉及 到作業(yè)注冊程序,創(chuàng)立作業(yè)限制塊JCB.后備狀態(tài)-運行狀態(tài),是由作業(yè)調度程序調度選中,裝入內存創(chuàng)立相應進程及有關表格投 入運行.這過程中涉及作業(yè)調度程序,裝入作業(yè)到內存時涉及內存治理程序和設備治理程序中 的某些功能程序.運行狀態(tài)-完成狀態(tài),是由進程調度、進程限制原語、及OS中各種資源治理程序的幫助下,使作業(yè)的進程正常運行結束,或出錯無法運行下去時,由作業(yè)終止程序處理,做作業(yè)結束 的

8、善后處理工作.2 .參考答案：作業(yè)調度程序的功能是根據(jù)某種調度算法從后備作業(yè)隊列中選擇作業(yè),為它們分配內存和 其他資源,創(chuàng)立相應就緒進程,掛入就緒進程隊列.作業(yè)調度程序配置于具有批處理作業(yè)功能 的OS中.進程調度程序是根據(jù)某種調度算法從就緒狀態(tài)的進程中選擇一個進程,將CPU分配給它,讓其執(zhí)行.進程調度程序在任何一種操作系統(tǒng)中均有配置,它是一種處理機調度程序.收集于網絡,如有侵權請聯(lián)系治理員刪除精品文檔中級調度程序的功能是根據(jù)系統(tǒng)負荷太重,將有些暫不具備運行的進程掛起,并將它們從 內存調至外存上等待；當這些進程又具備執(zhí)行條件,且內存有空閑時,將它們激活從外存重新 裝入內存,等待進程調度.中級調度

9、通常配置于具有掛起、激活功能原語的OS中.3 .參考答案：(1)應由進程調度程序負責.(2)應由中級調度程序負責.(3)應由作業(yè)調度程序負責.4 .參考答案：在分時系統(tǒng)中不必設立作業(yè)調度程序,由于分時的作業(yè)是用戶從終端設備上輸入 的命令和數(shù)據(jù)都直接進入主存,而不是進入磁盤輸入并等待.5 .參考答案：(1)三道程序順序執(zhí)行時沒有并行操作,所以總需要的最短執(zhí)行時間是各道程序執(zhí)行時間之和為 174 秒,即 T=32+8+5+21+14+35+12+32+15=174 (秒).(2)三道程序并發(fā)執(zhí)行,可使輸入、輸出和計算盡量并行操作,縮短了三道作業(yè)的總周轉時間,調度最理想時只需90秒.其并行操作如下所

10、示：A進程.B進程C進程21IN14C12TXI35fM ITYLIM15mrrRrnTrT從示意圖可知進程 A,B,C需要的最短時間 T=21 + 14+35+15+5=90 (秒)6 .參照答案：進程調度方式主要有搶占方式和非搶占方式兩種.非搶占方式適用于大多數(shù)的批 處理系統(tǒng),而搶占方式適用于分時系統(tǒng)和大多數(shù)實時系統(tǒng).7 .參考答案：時間片原那么：當前進程用完一個時間片時,系統(tǒng)馬上停止當前進程的執(zhí)行,而將cpu分給下一個就緒進程.優(yōu)先級原那么：當新到達作業(yè)的進程的運行時間小于當前進程的運行時間時,立即將cpu分配給新進程.8 .參考答案：調度隊列模型主要有三種：第1種是只具有進程調度的調度

11、隊列模型1,主要適用于分時操作系統(tǒng)中；第2種是具有作業(yè)調度和進程調度的調度隊列模型2,主要適用具有批處理作業(yè)功能的批處理OS中；第3種是具有作業(yè)調度、進程調度和中級調度的調度隊列模型3,它主要適用于同時具有批處理作業(yè)功能和分時功能,并且具有掛起功能的OS中.9 .參考答案：周轉時間有作業(yè)周轉時間和進程周轉時間之分.作業(yè)周轉時間是從用戶提交的作業(yè)實體信息全 部進入輸入井時刻開始,到作業(yè)完成時刻這段時間間隔.它包括作業(yè)在后備隊列中等待時間、收集于網絡,如有侵權請聯(lián)系治理員刪除精品文檔進程在就緒隊列、阻塞隊列等待時間和在CPU上執(zhí)行的時間之和.進程周轉時間是相應作業(yè)周轉時間中去掉作業(yè)在后備隊列中的等

12、待時間.作業(yè)平均周轉時間公式為：群j -i其中,n為作業(yè)數(shù),Tci是第i個作業(yè)完成時刻,Tsi是第i個作業(yè)提交作業(yè)完成時刻,i是1, 2n中之一.10 .參考答案：響應時間是用戶從提交一個請求開始,直到系統(tǒng)在屏幕上顯示出結果或提示信 息這一段時間.分時系統(tǒng)的響應時間通常是3 S-5 S,而實時系統(tǒng)對響應時間的要求差異很 大,一般為秒級、毫秒級甚至要求時間更小.11 .參考答案：交互式的用戶通常是在分時系統(tǒng)和實時信息處理系統(tǒng)中.用戶通過聯(lián)機的終端設備發(fā)命令,系統(tǒng)以分時的形式及時為他們效勞,通常響應時間為35秒.但FCFS調度算法,為先來的進程分配處理機后讓它一直運行,直到運行完畢或因等待某事件發(fā)

13、生不能繼續(xù)運行時,才調度另一交 互式進程運行.如某交互型用戶從鍵盤上發(fā)命令運行他的一分鐘算題程序后,由于它前面的十 個其他用戶程序約需運行 1個小時,他要等1個小時才能得到響應處理,這是不能容忍的.所 以FCFS算法對交互式用戶而言是不恰當?shù)倪M程調度模式.12 .參考答案：所謂短作業(yè)優(yōu)先調度是指作業(yè)運行時間、進程運行的時間最短的先調度.因此 往往主存在長作業(yè)、長進程被推遲調度的情況,所以這種調度算法對長作業(yè)、長進程不利.13 .參考答案：吞吐量大的是最短作業(yè)優(yōu)先算法,由于SJF使作業(yè)的平均周轉時間有明顯的改善,從而使系統(tǒng)在單位時間內處理的作業(yè)數(shù)增多.公平合理的是先來先效勞算法.由于對用戶而言根

14、據(jù)作業(yè)進入輸入井時間的先后調度,先來的 先效勞,后來的自然后效勞,對每個用戶都是公平的.14 .參考答案：優(yōu)先級調度算法的主要優(yōu)點是能使最緊迫的作業(yè)、進程盡快調度到執(zhí)行.可適 應于批處理系統(tǒng)、分時系統(tǒng)、實時系統(tǒng).一定要擁有優(yōu)先級調度算法.15 .參考答案：FCFS算法調度的次序是 A, B, C, Db作業(yè) 名輸入時 間運行時間 分開始執(zhí)行時 間結束執(zhí)行 時間周轉時間 分帶權周轉時間A8: 00608 : 009: 006060/60B8: 10409 : 009: 409090/40C8: 20309 : 4010 : 10110110/30D8: 301010: 1010 : 201101

15、10/10作業(yè)平均周轉時間T=60+90=110=110/4=92.5分作業(yè)平均帶權周轉時間W=1+9/4+11/3+11/4=4.25收集于網絡,如有侵權請聯(lián)系治理員刪除精品文檔(2)短作業(yè)(短進程)優(yōu)先算法調度的次序是A, D, C, Bo作業(yè) 名輸入時 間運行時間 (分)開始執(zhí)行時 間結束執(zhí)行 時間周轉時間 (分)帶權周轉時間A8: 00608 : 009: 006060/60D8: 30109 : 009: 104040/10C8: 20309 : 109: 408080/30B8: 10409 : 4010 : 20130130/40T=(60+40+80+130)/4=77.5(分

16、)W=(1+4+8/3+13/4)/4 弋 2.73(3)優(yōu)先級高者優(yōu)先算法調度的次序是A, C, D, Bo作業(yè) 名輸入時 間運行時間 (分)開始執(zhí)行時 間結束執(zhí)行 時間周轉時間 (分)帶權周轉時間A8: 00608 : 009: 006060/60C8: 20309 : 009: 307070/30D8: 30109 : 309: 407070/10B8: 10409 : 4010 : 20130130/40T=(60+70+70+130)/4=82.5(分)W=(1+7/3+7+13/4)/4=167/48 弋 3.48 16參考答案：(1) FCFS算法不考慮作業(yè)運行時間的長短,僅按作

17、業(yè)進入輸入井時間的先后進行調度,因此對 所有的作業(yè)是公平合理的.(2)短作業(yè)優(yōu)先SJF算法對短作業(yè)非常有利,而對長作業(yè)非常不利.由于,即使很遲進入輸入 井的短作業(yè)能先被調度,而很早進入輸入井的長作業(yè),可能由于進入一大批短作業(yè)后得不到調 度而挨餓.17參考答案：時間片輪轉算法主要用于進程調度,此調度算法將進程就緒隊列按進程進入隊列 的先后排列,調度時只要將CPU分給隊列首進程一個時間片,當用完時間片后當前進程從隊 列首移到隊列尾,并將CPU分配隊列新隊列首進程.18.參考答案:時刻執(zhí)行態(tài) 進程就緒態(tài) 進程阻塞態(tài) 進程發(fā)生的事件T=0AA, BA被調度選中T=20BAA執(zhí)行P (S)后,S= -1而阻塞T=50BAB執(zhí)行V (S) , S=0喚醒AT=70ABB時間片到時,B為就緒T=120BAA時間片到時,A執(zhí)行P (S) , S=-1轉為阻塞收集于網絡,如有侵權請聯(lián)系治理員刪除精品文檔T=150BAB執(zhí)行V (S) , S=0,喚醒AT=170ABB時間片到時19.參考答案：(1)短作業(yè)優(yōu)先算法是優(yōu)先照顧運行時間短的作業(yè),雖然它有利減少作業(yè)平均周轉時間和作業(yè)平均帶權周轉時間,但對長作業(yè)用戶而言感到很不公平.長作業(yè)常常因連續(xù)不斷進入輸入井的 短作業(yè)而長時間得不到調度.(2)越短的作業(yè)不一定應該享受越好的效勞,要看該短作業(yè)的