操作系統(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*(tt1') 進(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(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)比=等待時(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,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)時(shí)間：J1(30分鐘)、J2(55分鐘)、J3(40分鐘)、J4(40分鐘)、J5(55分鐘)5分鐘5分鐘5分鐘15分鐘15第4章處理機(jī)調(diào)度4.6實(shí)時(shí)系統(tǒng)調(diào)度方法4.6.1實(shí)時(shí)系統(tǒng)的特點(diǎn)(1)有限等待時(shí)間(2)有限響應(yīng)時(shí)間(3)用戶控制(4)可靠性高(5)系統(tǒng)出錯(cuò)處理能力強(qiáng)4.6.2實(shí)時(shí)調(diào)度算法的分類(1)靜態(tài)表格驅(qū)動(dòng)類(2)靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶先式調(diào)度算法類(3)動(dòng)態(tài)計(jì)劃調(diào)度算法類(4)盡力而為調(diào)度算法類16第4章處理機(jī)調(diào)度4.6.3時(shí)限調(diào)度算法與頻率單調(diào)調(diào)度算法開始時(shí)限——startingdeadline結(jié)束時(shí)限——endingdeadline時(shí)限調(diào)度算法所需要的相關(guān)輸入信息：(1)任務(wù)就緒時(shí)間或事件到達(dá)時(shí)間(2)開始時(shí)限(3)完成時(shí)限(4)處理時(shí)間(5)資源需求(6)優(yōu)先級(jí)17第4章處理機(jī)調(diào)度[例]設(shè)實(shí)時(shí)系統(tǒng)從兩個(gè)不同的數(shù)據(jù)源DA和DB周期性地收集數(shù)據(jù)并進(jìn)行處理，其中DA的時(shí)限要求以30ms為周期，DB的時(shí)限要求以75ms為周期。設(shè)DA所需處理時(shí)限為15ms，DB所需處理時(shí)限為38ms，則與DA和DB有關(guān)進(jìn)程的事件發(fā)生時(shí)限（就緒時(shí)限）、執(zhí)行時(shí)限以及結(jié)束時(shí)限如下圖所示。進(jìn)程事件發(fā)生時(shí)限執(zhí)行時(shí)限結(jié)束時(shí)限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)度算法是一種被廣泛用于多周期性實(shí)時(shí)處理的調(diào)度算法。頻率單調(diào)調(diào)度算法的基本原理是頻率越低（周期越長(zhǎng)）的任務(wù)的優(yōu)先級(jí)越低。設(shè)任務(wù)周期為T，任務(wù)的執(zhí)行時(shí)間為C，則使用頻率單調(diào)調(diào)度算法的必要條件是C≤T。圖4.12時(shí)限調(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三個(gè)作業(yè)，執(zhí)行情況如下表所示。請(qǐng)?zhí)顚懼苻D(zhuǎn)時(shí)間欄，并回答下列問題：(1)作業(yè)的平均周轉(zhuǎn)時(shí)間是多少？(2)采用了什么作業(yè)調(diào)度算法？

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