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

14.1分級調(diào)度4.2作業(yè)調(diào)度4.3進(jìn)程調(diào)度4.4調(diào)度算法4.5算法評價4.6實時系統(tǒng)調(diào)度方法第4章處理機(jī)調(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)進(jìn)程調(diào)度——微觀調(diào)度或低級調(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)對所有的作業(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章處理機(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)度的時機(jī)4.3.3進(jìn)程上下文切換4.3.4進(jìn)程調(diào)度性能評價7第4章處理機(jī)調(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)建進(jìn)程隊列享受服務(wù)進(jìn)程隊列8第4章處理機(jī)調(diào)度新創(chuàng)建進(jìn)程隊列中進(jìn)程的優(yōu)先級P=a*t(a>0)

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

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

P(t)=a*(t1't1)+b*(tt1') 進(jìn)程在時刻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(tt1')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)比=等待時間/運(yùn)行時間[例]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章處理機(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)比=等待時間/運(yùn)行時間(4)優(yōu)先級調(diào)度(5)均衡調(diào)度算法(資源調(diào)度算法)11第4章處理機(jī)調(diào)度試題6（90）從供選擇的答案中，選出應(yīng)填入下列敘述中__n__內(nèi)的正確答案，把編號寫在答卷的對應(yīng)欄內(nèi)。假設(shè)某多道程序設(shè)計系統(tǒng)有供用戶使用的主存空間100K，磁帶機(jī)2臺，打印機(jī)1臺，系統(tǒng)采用可變分區(qū)方式管理主存，對磁帶機(jī)和打印機(jī)采用靜態(tài)分配，并假設(shè)輸入輸出操作的時間忽略不計?，F(xiàn)有一作業(yè)序列如下：作業(yè)號進(jìn)輸入井時間要求計算時間要求主存量申請磁帶機(jī)數(shù)申請打印機(jī)數(shù)18:0025分鐘15K1臺1臺28:2010分鐘30K0臺1臺38:2020分鐘60K1臺0臺48:3020分鐘20K1臺0臺58:3515分鐘10K1臺1臺12第4章處理機(jī)調(diào)度假設(shè)作業(yè)調(diào)度采用先來先服務(wù)算法，優(yōu)先分配主存的低地址區(qū)域且不準(zhǔn)移動已在主存中的作業(yè)，在主存中的作業(yè)平分CPU時間，則作業(yè)調(diào)度選中作業(yè)的次序是__A__，如果把一個作業(yè)從進(jìn)入輸入井到得到計算結(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,2,4,3,5)B~D：①30分鐘 ②36分鐘 ③40分鐘 ④44分鐘 ⑤55分鐘 ⑥64分鐘E：①9:20 ②9:30 ③9:40 ④9:50A：③B：⑤C：①D：④E：②13第4章處理機(jī)調(diào)度內(nèi)存分配圖J1—15K空閑85KJ1—15KJ3—60K空閑25K空閑15KJ3—60KJ4—20K空閑5KJ2—30KJ4—20K空閑5K空閑45KJ2—30K空閑70KJ5—10K空閑90K8:008:208:309:009:109:1514第4章處理機(jī)調(diào)度8:008:208:308:359:009:109:159:30J1J2J3J4J55分鐘15分鐘20分鐘15分鐘5分鐘周轉(zhuǎn)時間：J1(30分鐘)、J2(55分鐘)、J3(40分鐘)、J4(40分鐘)、J5(55分鐘)5分鐘5分鐘5分鐘15分鐘15第4章處理機(jī)調(diào)度4.6實時系統(tǒng)調(diào)度方法4.6.1實時系統(tǒng)的特點(1)有限等待時間(2)有限響應(yīng)時間(3)用戶控制(4)可靠性高(5)系統(tǒng)出錯處理能力強(qiáng)4.6.2實時調(diào)度算法的分類(1)靜態(tài)表格驅(qū)動類(2)靜態(tài)優(yōu)先級驅(qū)動搶先式調(diào)度算法類(3)動態(tài)計劃調(diào)度算法類(4)盡力而為調(diào)度算法類16第4章處理機(jī)調(diào)度4.6.3時限調(diào)度算法與頻率單調(diào)調(diào)度算法開始時限——startingdeadline結(jié)束時限——endingdeadline時限調(diào)度算法所需要的相關(guān)輸入信息：(1)任務(wù)就緒時間或事件到達(dá)時間(2)開始時限(3)完成時限(4)處理時間(5)資源需求(6)優(yōu)先級17第4章處理機(jī)調(diào)度[例]設(shè)實時系統(tǒng)從兩個不同的數(shù)據(jù)源DA和DB周期性地收集數(shù)據(jù)并進(jìn)行處理，其中DA的時限要求以30ms為周期，DB的時限要求以75ms為周期。設(shè)DA所需處理時限為15ms，DB所需處理時限為38ms，則與DA和DB有關(guān)進(jìn)程的事件發(fā)生時限（就緒時限）、執(zhí)行時限以及結(jié)束時限如下圖所示。進(jìn)程事件發(fā)生時限執(zhí)行時限結(jié)束時限D(zhuǎn)A(1)01530DA(2)301560DA(3)601590…………DB(1)03875DB(2)7538150DB(3)15038225…………18第4章處理機(jī)調(diào)度頻率單調(diào)調(diào)度算法是一種被廣泛用于多周期性實時處理的調(diào)度算法。頻率單調(diào)調(diào)度算法的基本原理是頻率越低（周期越長）的任務(wù)的優(yōu)先級越低。設(shè)任務(wù)周期為T，任務(wù)的執(zhí)行時間為C，則使用頻率單調(diào)調(diào)度算法的必要條件是C≤T。圖4.12時限調(diào)度算法的調(diào)度順序153045607590105130tDA(1)DB(1)DA(2)DB(1)DB(1)DA(3)DA(4)DB(2)…19第4章處理機(jī)調(diào)度設(shè)有A、B、C三個作業(yè)，執(zhí)行情況如下表所示。請?zhí)顚懼苻D(zhuǎn)時間欄，并回答下列問題：(1)作業(yè)的平均周轉(zhuǎn)時間是多少？(2)采用了什么作業(yè)調(diào)度算法？

作業(yè)名到達(dá)時間開始執(zhí)行時間執(zhí)行結(jié)束時間周轉(zhuǎn)時間(小時)A10:0010:0012:00B10:1012:2513:25C10:2512:0012:2520第4章處理機(jī)調(diào)度(1)作業(yè)的平均周轉(zhuǎn)時間是2.42小時。(2)采用的作業(yè)調(diào)度算法是SJF。作業(yè)名到達(dá)時間開始執(zhí)行時間執(zhí)行結(jié)束時間周轉(zhuǎn)時間(小時)A10:0010:0012:002.00B10:1012:2513:253.25C10:2512:0012:252.0021k個進(jìn)程共享某種資源r，該資源共有m個可分配單位，每個進(jìn)程一次申請和釋放資源單位一個。假設(shè)每個進(jìn)程對該資源的最大需求量均小于m，且各進(jìn)程最大需求量之和小于m+k，試證明這個系統(tǒng)中不可能產(chǎn)生死鎖。反證法：假設(shè)系統(tǒng)已發(fā)生死鎖M(i)——第i個進(jìn)程的最大資源需求量N(i)——第i個進(jìn)程還需要的資源量U(i)——第i個進(jìn)程已分配的資源量M(1)+M(2)+…+M(k)=(N(1)+N(2)+…+N(