操作系統(tǒng)原理第4章

14.1分級(jí)調(diào)度4.2作業(yè)調(diào)度4.3進(jìn)程調(diào)度4.4調(diào)度算法4.5算法評(píng)價(jià)4.6實(shí)時(shí)系統(tǒng)調(diào)度方法第4章處理機(jī)調(diào)度24.1分級(jí)調(diào)度4.1.1作業(yè)的狀態(tài)及其轉(zhuǎn)換4.1.2調(diào)度的層次(1)作業(yè)調(diào)度——宏觀調(diào)度或高級(jí)調(diào)度(2)交換調(diào)度——中級(jí)調(diào)度(3)進(jìn)程調(diào)度——微觀調(diào)度或低級(jí)調(diào)度(4)線程調(diào)度4.1.3作業(yè)與進(jìn)程的關(guān)系第4章處理機(jī)調(diào)度3

進(jìn)程狀態(tài)及其轉(zhuǎn)換第4章處理機(jī)調(diào)度RunningTerminateReadyBlockedReadySuspendedBlockedSuspendedEventWaitEventOccursCreateResumeSuspendResumeSuspendDispatchEventOccursTimeout4作業(yè)狀態(tài)及其轉(zhuǎn)換第4章處理機(jī)調(diào)度運(yùn)行就緒等待完成收容提交用戶作業(yè)錄入作業(yè)調(diào)度作業(yè)調(diào)度執(zhí)行54.2作業(yè)調(diào)度4.2.1作業(yè)調(diào)度功能4.2.2作業(yè)調(diào)度目標(biāo)與性能衡量調(diào)度目標(biāo)：(1)對(duì)所有的作業(yè)應(yīng)該是公平合理的；(2)應(yīng)使設(shè)備有高的利用率；(3)執(zhí)行盡可能多的作業(yè)（吞吐量大）；(4)有快的響應(yīng)時(shí)間。性能衡量：1.周轉(zhuǎn)時(shí)間Ti=TeiTsi或Ti=Twi+Tri(Tsi—作業(yè)的提交時(shí)間，Tei—作業(yè)的完成時(shí)間)2.帶權(quán)周轉(zhuǎn)時(shí)間Wi=Ti/Tri第4章處理機(jī)調(diào)度6第4章處理機(jī)調(diào)度4.3進(jìn)程調(diào)度4.3.1進(jìn)程調(diào)度的功能4.3.2進(jìn)程調(diào)度的時(shí)機(jī)4.3.3進(jìn)程上下文切換4.3.4進(jìn)程調(diào)度性能評(píng)價(jià)7第4章處理機(jī)調(diào)度4.4調(diào)度算法1.先來先服務(wù)FCFS——FirstComeFirstServe2.輪轉(zhuǎn)法RR——RoundRobin3.多級(jí)反饋輪轉(zhuǎn)法——RoundRobinwithmultiplefeedback4.優(yōu)先級(jí)法——靜態(tài)法和動(dòng)態(tài)法[例]線性優(yōu)先級(jí)調(diào)度策略圖4.5線性優(yōu)先級(jí)調(diào)度CPU完成新創(chuàng)建進(jìn)程隊(duì)列享受服務(wù)進(jìn)程隊(duì)列8第4章處理機(jī)調(diào)度新創(chuàng)建進(jìn)程隊(duì)列中進(jìn)程的優(yōu)先級(jí)P=a*t(a>0)

享受服務(wù)進(jìn)程隊(duì)列中進(jìn)程的優(yōu)先級(jí)P=b*t(a>b>0)

P(t)=a*(tt1) 進(jìn)程在時(shí)刻t1被創(chuàng)建

P(t)=a*(t1't1)+b*(t

t1') 進(jìn)程在時(shí)刻t1'轉(zhuǎn)入享受服務(wù)隊(duì)列若b>a>0，則為FCFS；若a>b=0，則為RR法。線性優(yōu)先級(jí)調(diào)度策略介于FCFS和RR法之間。圖4.6優(yōu)先級(jí)變化曲線t1t1'

t2t2'tP(t)b(t

t1')a(tt1)9第4章處理機(jī)調(diào)度4.4調(diào)度算法5.最短作業(yè)優(yōu)先法SJF——ShortestJobFirst6.最高響應(yīng)比優(yōu)先法HRN——HighestResponse-ratioNext響應(yīng)比=等待時(shí)間/運(yùn)行時(shí)間[例]9:30開始調(diào)度：作業(yè)A的響應(yīng)比=40/90，作業(yè)B的響應(yīng)比=30/24，作業(yè)C的響應(yīng)比=0/60。9:54調(diào)度：作業(yè)A的響應(yīng)比=64/90，作業(yè)C的響應(yīng)比=24/60。調(diào)度次序：B、A、C。作業(yè)到輸入井時(shí)間執(zhí)行時(shí)間A8:501.5小時(shí)B9:000.4小時(shí)C9:301小時(shí)10第4章處理機(jī)調(diào)度常用的作業(yè)調(diào)度算法(1)先來先服務(wù)(FCFS——FirstComeFirstServe)(2)短作業(yè)優(yōu)先(SJF——ShortestJobFirst)(3)響應(yīng)比高者優(yōu)先(HRN——HighestResponse-ratioNext) 響應(yīng)比=等待時(shí)間/運(yùn)行時(shí)間(4)優(yōu)先級(jí)調(diào)度(5)均衡調(diào)度算法(資源調(diào)度算法)11第4章處理機(jī)調(diào)度試題6（90）從供選擇的答案中，選出應(yīng)填入下列敘述中__n__內(nèi)的正確答案，把編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。假設(shè)某多道程序設(shè)計(jì)系統(tǒng)有供用戶使用的主存空間100K，磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)，系統(tǒng)采用可變分區(qū)方式管理主存，對(duì)磁帶機(jī)和打印機(jī)采用靜態(tài)分配，并假設(shè)輸入輸出操作的時(shí)間忽略不計(jì)?，F(xiàn)有一作業(yè)序列如下：作業(yè)號(hào)進(jìn)輸入井時(shí)間要求計(jì)算時(shí)間要求主存量申請(qǐng)磁帶機(jī)數(shù)申請(qǐng)打印機(jī)數(shù)18:0025分鐘15K1臺(tái)1臺(tái)28:2010分鐘30K0臺(tái)1臺(tái)38:2020分鐘60K1臺(tái)0臺(tái)48:3020分鐘20K1臺(tái)0臺(tái)58:3515分鐘10K1臺(tái)1臺(tái)12第4章處理機(jī)調(diào)度假設(shè)作業(yè)調(diào)度采用先來先服務(wù)算法，優(yōu)先分配主存的低地址區(qū)域且不準(zhǔn)移動(dòng)已在主存中的作業(yè)，在主存中的作業(yè)平分CPU時(shí)間，則作業(yè)調(diào)度選中作業(yè)的次序是__A__，如果把一個(gè)作業(yè)從進(jìn)入輸入井到得到計(jì)算結(jié)果的時(shí)間定義為周轉(zhuǎn)時(shí)間，則在忽略系統(tǒng)工作時(shí)間的情況下，最大的作業(yè)周轉(zhuǎn)時(shí)間是__B__，最小的作業(yè)周轉(zhuǎn)時(shí)間是__C__，作業(yè)的平均周轉(zhuǎn)時(shí)間是__D__，作業(yè)全部執(zhí)行結(jié)束的時(shí)間是__E__。供選擇的答案A：①(1,3,2,4,5) ②(1,2,3,4,5) ③(1,3,4,2,5) ④(1,