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

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

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

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

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

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

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

t2t2'tP(t)b(t

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