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

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

2、程狀態(tài)及其轉(zhuǎn)換第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度RunningTerminateReadyBlockedReadySuspendedBlockedSuspendedEvent WaitEvent OccursCreateResumeSuspendResumeSuspendDispatchEvent OccursTimeout4n 作業(yè)狀態(tài)及其轉(zhuǎn)換作業(yè)狀態(tài)及其轉(zhuǎn)換第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度運(yùn)行運(yùn)行就緒就緒等待等待完成完成收容收容提交提交用戶用戶作業(yè)錄入作業(yè)錄入作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度執(zhí)行執(zhí)行54.2 作業(yè)調(diào)度作業(yè)調(diào)度4.2.1 作業(yè)調(diào)度功能作業(yè)調(diào)度功能4.2.2 作業(yè)調(diào)度目標(biāo)

3、與性能衡量作業(yè)調(diào)度目標(biāo)與性能衡量n 調(diào)度目標(biāo)：調(diào)度目標(biāo)： (1) 對所有的作業(yè)應(yīng)該是公平合理的；對所有的作業(yè)應(yīng)該是公平合理的； (2) 應(yīng)使設(shè)備有高的利用率；應(yīng)使設(shè)備有高的利用率； (3) 執(zhí)行盡可能多的作業(yè)（吞吐量大）；執(zhí)行盡可能多的作業(yè)（吞吐量大）； (4) 有快的響應(yīng)時(shí)間。有快的響應(yīng)時(shí)間。n 性能衡量：性能衡量： 1. 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間Ti=Tei Tsi或或Ti=Twi+Tri (Tsi作業(yè)的提交時(shí)間，作業(yè)的提交時(shí)間，Tei作業(yè)的完成時(shí)間作業(yè)的完成時(shí)間) 2. 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間Wi=Ti/Tri第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度6第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.3 進(jìn)

4、程調(diào)度進(jìn)程調(diào)度4.3.1 進(jìn)程調(diào)度的功能進(jìn)程調(diào)度的功能4.3.2 進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度的時(shí)機(jī)4.3.3 進(jìn)程上下文切換進(jìn)程上下文切換4.3.4 進(jìn)程調(diào)度性能評價(jià)進(jìn)程調(diào)度性能評價(jià)7第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.4 調(diào)度算法調(diào)度算法 1. 先來先服務(wù)先來先服務(wù)FCFSFirst Come First Serve 2. 輪轉(zhuǎn)法輪轉(zhuǎn)法RRRound Robin 3. 多級反饋輪轉(zhuǎn)法多級反饋輪轉(zhuǎn)法Round Robin with multiple feedback 4. 優(yōu)先級法優(yōu)先級法靜態(tài)法和動(dòng)態(tài)法靜態(tài)法和動(dòng)態(tài)法 例例 線性優(yōu)先級調(diào)度策略線性優(yōu)先級調(diào)度策略圖圖 4.5 線性優(yōu)先級調(diào)度線性優(yōu)

5、先級調(diào)度CPU完成完成新創(chuàng)建進(jìn)程隊(duì)列新創(chuàng)建進(jìn)程隊(duì)列享受服務(wù)進(jìn)程隊(duì)列享受服務(wù)進(jìn)程隊(duì)列8第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度l 新創(chuàng)建進(jìn)程隊(duì)列中進(jìn)程的優(yōu)先級新創(chuàng)建進(jìn)程隊(duì)列中進(jìn)程的優(yōu)先級P=a*t (a0)l 享受服務(wù)進(jìn)程享受服務(wù)進(jìn)程隊(duì)列中進(jìn)程的優(yōu)先級隊(duì)列中進(jìn)程的優(yōu)先級P=b*t (ab0) P(t)=a*(t t1)進(jìn)程在時(shí)刻進(jìn)程在時(shí)刻t1被創(chuàng)建被創(chuàng)建 P(t)=a*(t1 t1)+b*(t t1)進(jìn)程在時(shí)刻進(jìn)程在時(shí)刻t1轉(zhuǎn)入轉(zhuǎn)入享受服務(wù)享受服務(wù)隊(duì)列隊(duì)列 若若ba0，則為，則為FCFS； 若若ab=0，則為，則為RR法。法。 線性優(yōu)先級調(diào)度策略介于線性優(yōu)先級調(diào)度策略介于FCFS和和RR法之間。法之

6、間。圖圖 4.6 優(yōu)先級變化曲線優(yōu)先級變化曲線t1 t1 t2 t2 t P(t)b(t t1)a(t t1)9第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.4 調(diào)度算法調(diào)度算法 5. 最短作業(yè)優(yōu)先法最短作業(yè)優(yōu)先法SJFShortest Job First 6. 最高響應(yīng)比優(yōu)先法最高響應(yīng)比優(yōu)先法HRNHighest Response-ratio Next 響應(yīng)比響應(yīng)比=等待時(shí)間等待時(shí)間/運(yùn)行時(shí)間運(yùn)行時(shí)間 例例9:30開始調(diào)度：作業(yè)開始調(diào)度：作業(yè)A的響應(yīng)比的響應(yīng)比=40/90，作業(yè)，作業(yè)B的響應(yīng)比的響應(yīng)比=30/24，作業(yè)，作業(yè)C的響應(yīng)比的響應(yīng)比=0/60。9:54調(diào)度：作業(yè)調(diào)度：作業(yè)A的響應(yīng)比的響應(yīng)

7、比=64/90，作業(yè)，作業(yè)C的響應(yīng)比的響應(yīng)比=24/60。調(diào)度次序：調(diào)度次序：B、A、C。作業(yè)作業(yè)到輸入井時(shí)間到輸入井時(shí)間執(zhí)行時(shí)間執(zhí)行時(shí)間A8:501.5小時(shí)小時(shí)B9:000.4小時(shí)小時(shí)C9:301小時(shí)小時(shí)10第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度n 常用的作業(yè)調(diào)度算法常用的作業(yè)調(diào)度算法 (1) 先來先服務(wù)先來先服務(wù)(FCFSFirst Come First Serve) (2) 短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJFShortest Job First) (3) 響應(yīng)比高者優(yōu)先響應(yīng)比高者優(yōu)先(HRNHighest Response-ratio Next)響應(yīng)比響應(yīng)比=等待時(shí)間等待時(shí)間/運(yùn)行時(shí)間運(yùn)行時(shí)間

8、(4) 優(yōu)先級調(diào)度優(yōu)先級調(diào)度 (5) 均衡調(diào)度算法均衡調(diào)度算法(資源調(diào)度算法資源調(diào)度算法)11第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度試題試題6 （90） 從供選擇的答案中，選出應(yīng)填入下列敘述中從供選擇的答案中，選出應(yīng)填入下列敘述中_n_內(nèi)的正確答案，把編號內(nèi)的正確答案，把編號寫在答卷的對應(yīng)欄內(nèi)。寫在答卷的對應(yīng)欄內(nèi)。 假設(shè)某多道程序設(shè)計(jì)系統(tǒng)有供用戶使用的主存空間假設(shè)某多道程序設(shè)計(jì)系統(tǒng)有供用戶使用的主存空間100K，磁帶機(jī)，磁帶機(jī)2臺，臺，打印機(jī)打印機(jī)1臺，系統(tǒng)采用可變分區(qū)方式管理主存，對磁帶機(jī)和打印機(jī)采用靜態(tài)分臺，系統(tǒng)采用可變分區(qū)方式管理主存，對磁帶機(jī)和打印機(jī)采用靜態(tài)分配，并假設(shè)輸入輸出操作的時(shí)間

9、忽略不計(jì)?，F(xiàn)有一作業(yè)序列如下：配，并假設(shè)輸入輸出操作的時(shí)間忽略不計(jì)。現(xiàn)有一作業(yè)序列如下：作業(yè)號作業(yè)號進(jìn)輸入井時(shí)間進(jìn)輸入井時(shí)間要求計(jì)算時(shí)間要求計(jì)算時(shí)間要求主存量要求主存量申請磁帶機(jī)數(shù)申請磁帶機(jī)數(shù)申請打印機(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 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 假設(shè)作業(yè)調(diào)度采用先來先服務(wù)算法，優(yōu)先分配主存的低地址區(qū)域且假設(shè)作業(yè)調(diào)度采用先來先服務(wù)算法，優(yōu)先分配主存的低地址區(qū)域且不準(zhǔn)移動(dòng)已在主存中的作業(yè)，

10、在主存中的作業(yè)平分不準(zhǔn)移動(dòng)已在主存中的作業(yè)，在主存中的作業(yè)平分CPU時(shí)間，則作業(yè)調(diào)時(shí)間，則作業(yè)調(diào)度選中作業(yè)的次序是度選中作業(yè)的次序是_A_，如果把一個(gè)作業(yè)從進(jìn)入輸入井到得到計(jì)算，如果把一個(gè)作業(yè)從進(jìn)入輸入井到得到計(jì)算結(jié)果的時(shí)間定義為周轉(zhuǎn)時(shí)間，則在忽略系統(tǒng)工作時(shí)間的情況下，最大的結(jié)果的時(shí)間定義為周轉(zhuǎn)時(shí)間，則在忽略系統(tǒng)工作時(shí)間的情況下，最大的作業(yè)周轉(zhuǎn)時(shí)間是作業(yè)周轉(zhuǎn)時(shí)間是_B_，最小的作業(yè)周轉(zhuǎn)時(shí)間是，最小的作業(yè)周轉(zhuǎn)時(shí)間是_C_，作業(yè)的平均周轉(zhuǎn)，作業(yè)的平均周轉(zhuǎn)時(shí)間是時(shí)間是_D_，作業(yè)全部執(zhí)行結(jié)束的時(shí)間是，作業(yè)全部執(zhí)行結(jié)束的時(shí)間是_E_。供選擇的答案供選擇的答案 A： (1, 3, 2, 4, 5) (1

11、, 2, 3, 4, 5) (1, 3, 4, 2, 5) (1, 2, 4, 3, 5) BD： 30分鐘分鐘 36分鐘分鐘 40分鐘分鐘 44分鐘分鐘 55分鐘分鐘 64分鐘分鐘 E： 9:20 9:30 9:40 9:50A： B： C： D： E：13第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度內(nèi)存分配圖內(nèi)存分配圖J115K空閑空閑85KJ115KJ360K空閑空閑25K空閑空閑15KJ360KJ420K空閑空閑5KJ230KJ420K空閑空閑5K空閑空閑45KJ230K空閑空閑70KJ510K空閑空閑90K8:00 8:20 8:30 9:00 9:10 9:1514第第4 4章章 處理機(jī)調(diào)

12、度處理機(jī)調(diào)度 8:00 8:20 8:30 8:35 9:00 9:10 9:15 9:30 J1J2J3J4J55分鐘分鐘15分鐘分鐘20分鐘分鐘15分鐘分鐘5分鐘分鐘周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間：J1(30分鐘分鐘)、 J2(55分鐘分鐘)、 J3(40分鐘分鐘)、 J4(40分鐘分鐘)、 J5(55分鐘分鐘)5分鐘分鐘5分鐘分鐘5分鐘分鐘15分鐘分鐘15第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.6 實(shí)時(shí)系統(tǒng)調(diào)度方法實(shí)時(shí)系統(tǒng)調(diào)度方法4.6.1 實(shí)時(shí)系統(tǒng)的特點(diǎn)實(shí)時(shí)系統(tǒng)的特點(diǎn) (1) 有限等待時(shí)間有限等待時(shí)間 (2) 有限響應(yīng)時(shí)間有限響應(yīng)時(shí)間 (3) 用戶控制用戶控制 (4) 可靠性高可靠性高 (5) 系

13、統(tǒng)出錯(cuò)處理能力強(qiáng)系統(tǒng)出錯(cuò)處理能力強(qiáng)4.6.2 實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類 (1) 靜態(tài)表格驅(qū)動(dòng)類靜態(tài)表格驅(qū)動(dòng)類 (2) 靜態(tài)優(yōu)先級驅(qū)動(dòng)搶先式調(diào)度算法類靜態(tài)優(yōu)先級驅(qū)動(dòng)搶先式調(diào)度算法類 (3) 動(dòng)態(tài)計(jì)劃調(diào)度算法類動(dòng)態(tài)計(jì)劃調(diào)度算法類 (4) 盡力而為調(diào)度算法類盡力而為調(diào)度算法類16第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.6.3 時(shí)限調(diào)度算法與頻率單調(diào)調(diào)度算法時(shí)限調(diào)度算法與頻率單調(diào)調(diào)度算法 開始時(shí)限開始時(shí)限starting deadline 結(jié)束時(shí)限結(jié)束時(shí)限ending deadline 時(shí)限調(diào)度算法所需要的相關(guān)輸入信息：時(shí)限調(diào)度算法所需要的相關(guān)輸入信息： (1) 任務(wù)就緒時(shí)間或事件到達(dá)時(shí)間

14、任務(wù)就緒時(shí)間或事件到達(dá)時(shí)間 (2) 開始時(shí)限開始時(shí)限 (3) 完成時(shí)限完成時(shí)限 (4) 處理時(shí)間處理時(shí)間 (5) 資源需求資源需求 (6) 優(yōu)先級優(yōu)先級17第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度例例 設(shè)實(shí)時(shí)系統(tǒng)從兩個(gè)不同的數(shù)據(jù)源設(shè)實(shí)時(shí)系統(tǒng)從兩個(gè)不同的數(shù)據(jù)源DA和和DB周期性地收集數(shù)據(jù)并進(jìn)周期性地收集數(shù)據(jù)并進(jìn)行處理，其中行處理，其中DA的時(shí)限要求以的時(shí)限要求以30ms為周期，為周期， DB的時(shí)限要求以的時(shí)限要求以75ms為為周期。設(shè)周期。設(shè)DA所需處理時(shí)限為所需處理時(shí)限為15ms， DB所需處理時(shí)限為所需處理時(shí)限為38ms，則與，則與DA和和DB有關(guān)進(jìn)程的事件發(fā)生時(shí)限（就緒時(shí)限）、執(zhí)行時(shí)限以及結(jié)束

15、有關(guān)進(jìn)程的事件發(fā)生時(shí)限（就緒時(shí)限）、執(zhí)行時(shí)限以及結(jié)束時(shí)限如下圖所示。時(shí)限如下圖所示。進(jìn)進(jìn) 程程事件發(fā)生時(shí)限事件發(fā)生時(shí)限執(zhí)行時(shí)限執(zhí)行時(shí)限結(jié)束時(shí)限結(jié)束時(shí)限D(zhuǎn)A(1)01530DA(2)301560DA(3)601590DB(1)03875DB(2)7538150DB(3)1503822518第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 頻率單調(diào)調(diào)度算法是一種被廣泛用于多周期性實(shí)時(shí)處理頻率單調(diào)調(diào)度算法是一種被廣泛用于多周期性實(shí)時(shí)處理的調(diào)度算法。的調(diào)度算法。 頻率單調(diào)調(diào)度算法的基本原理是頻率越低（周期越長）頻率單調(diào)調(diào)度算法的基本原理是頻率越低（周期越長）的任務(wù)的優(yōu)先級越低。的任務(wù)的優(yōu)先級越低。 設(shè)任務(wù)周期為設(shè)

16、任務(wù)周期為T，任務(wù)的執(zhí)行時(shí)間為，任務(wù)的執(zhí)行時(shí)間為C，則使用頻率單，則使用頻率單調(diào)調(diào)度算法的必要條件是調(diào)調(diào)度算法的必要條件是CT。圖圖 4.12 時(shí)限調(diào)度算法的調(diào)度順序時(shí)限調(diào)度算法的調(diào)度順序15 30 45 60 75 90 105 130 tDA(1) DB(1) DA(2) DB(1) DB(1) DA(3) DA(4) DB(2) 19第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 設(shè)有設(shè)有A、B、C三個(gè)作業(yè)，執(zhí)行情況如下表所示。請三個(gè)作業(yè)，執(zhí)行情況如下表所示。請?zhí)顚懼苻D(zhuǎn)時(shí)間欄，并回答下列問題：填寫周轉(zhuǎn)時(shí)間欄，并回答下列問題： (1) 作業(yè)的平均周轉(zhuǎn)時(shí)間是多少？作業(yè)的平均周轉(zhuǎn)時(shí)間是多少？ (2) 采

17、用了什么作業(yè)調(diào)度算法？采用了什么作業(yè)調(diào)度算法？ 作業(yè)名作業(yè)名到達(dá)時(shí)間到達(dá)時(shí)間開始執(zhí)行時(shí)間開始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間執(zhí)行結(jié)束時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間(小時(shí)小時(shí))A10:0010:0012:00B10:1012:2513:25C10:2512:0012:2520第第4 4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度(1) 作業(yè)的平均周轉(zhuǎn)時(shí)間是作業(yè)的平均周轉(zhuǎn)時(shí)間是2.42小時(shí)。小時(shí)。(2) 采用的作業(yè)調(diào)度算法是采用的作業(yè)調(diào)度算法是SJF。作業(yè)名作業(yè)名到達(dá)時(shí)間到達(dá)時(shí)間開始執(zhí)行時(shí)間開始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間執(zhí)行結(jié)束時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間(小時(shí)小時(shí))A10:0010:0012:002.00B10:1012:2513:253.25C1

18、0:2512:0012:252.0021 k個(gè)進(jìn)程共享某種資源個(gè)進(jìn)程共享某種資源r，該資源共有，該資源共有m個(gè)可分配單位，每個(gè)進(jìn)程個(gè)可分配單位，每個(gè)進(jìn)程一次申請和釋放資源單位一個(gè)。假設(shè)每個(gè)進(jìn)程對該資源的最大需求量一次申請和釋放資源單位一個(gè)。假設(shè)每個(gè)進(jìn)程對該資源的最大需求量均小于均小于m，且各進(jìn)程最大需求量之和小于，且各進(jìn)程最大需求量之和小于m+k，試證明這個(gè)系統(tǒng)中不，試證明這個(gè)系統(tǒng)中不可能產(chǎn)生死鎖?？赡墚a(chǎn)生死鎖。 反證法：假設(shè)系統(tǒng)已發(fā)生死鎖反證法：假設(shè)系統(tǒng)已發(fā)生死鎖 M(i)第第i個(gè)進(jìn)程的最大資源需求量個(gè)進(jìn)程的最大資源需求量 N(i)第第i個(gè)進(jìn)程還需要的資源量個(gè)進(jìn)程還需要的資源量 U(i)第第i個(gè)進(jìn)程已分配的資源量個(gè)進(jìn)程已分配的資源量 M(1)+M(2)+ M(k) =(N(1)+N(2)+N(k)+(U(1)+U(2)+U(k)m+k 因?yàn)橐寻l(fā)生死鎖，所以資源