處理機(jī)調(diào)度教學(xué)提綱

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、10/10作業(yè)平均周轉(zhuǎn)時(shí)間T=60+90=110=110/4=92.5分作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間W=1+9/4+11/3+11/4=4.25收集于網(wǎng)絡(luò),如有侵權(quán)請(qǐng)聯(lián)系治理員刪除精品文檔(2)短作業(yè)(短進(jìn)程)優(yōu)先算法調(diào)度的次序是A, D, C, Bo作業(yè) 名輸入時(shí) 間運(yùn)行時(shí)間 (分)開(kāi)始執(zhí)行時(shí) 間結(jié)束執(zhí)行 時(shí)間周轉(zhuǎn)時(shí)間 (分)帶權(quán)周轉(zhuǎn)時(shí)間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)先級(jí)高者優(yōu)先算法調(diào)度的次序是A, C, D, Bo作業(yè) 名輸入時(shí) 間運(yùn)行時(shí)間 (分)開(kāi)始執(zhí)行時(shí) 間結(jié)束執(zhí)行 時(shí)間周轉(zhuǎn)時(shí)間 (分)帶權(quán)周轉(zhuǎn)時(shí)間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è)運(yùn)行時(shí)間的長(zhǎng)短,僅按作

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