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

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

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

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

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

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

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

t2t2'tP(t)b(t

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