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

1、14.1 分級調(diào)度分級調(diào)度4.2 作業(yè)調(diào)度作業(yè)調(diào)度4.3 進程調(diào)度進程調(diào)度4.4 調(diào)度算法調(diào)度算法4.5 算法評價算法評價4.6 實時系統(tǒng)調(diào)度方法實時系統(tǒng)調(diào)度方法第第4 4章章 處理機調(diào)度處理機調(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) 進程調(diào)度進程調(diào)度微觀調(diào)度或低級調(diào)度微觀調(diào)度或低級調(diào)度 (4) 線程調(diào)度線程調(diào)度4.1.3 作業(yè)與進程的關系作業(yè)與進程的關系第第4 4章章 處理機調(diào)度處理機調(diào)度3n 進程狀態(tài)及其轉(zhuǎn)換進

2、程狀態(tài)及其轉(zhuǎn)換第第4 4章章 處理機調(diào)度處理機調(diào)度RunningTerminateReadyBlockedReadySuspendedBlockedSuspendedEvent WaitEvent OccursCreateResumeSuspendResumeSuspendDispatchEvent OccursTimeout4n 作業(yè)狀態(tài)及其轉(zhuǎn)換作業(yè)狀態(tài)及其轉(zhuǎn)換第第4 4章章 處理機調(diào)度處理機調(diào)度運行運行就緒就緒等待等待完成完成收容收容提交提交用戶用戶作業(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)度目標

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

4、程調(diào)度進程調(diào)度4.3.1 進程調(diào)度的功能進程調(diào)度的功能4.3.2 進程調(diào)度的時機進程調(diào)度的時機4.3.3 進程上下文切換進程上下文切換4.3.4 進程調(diào)度性能評價進程調(diào)度性能評價7第第4 4章章 處理機調(diào)度處理機調(diào)度4.4 調(diào)度算法調(diào)度算法 1. 先來先服務先來先服務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)法和動態(tài)法靜態(tài)法和動態(tài)法 例例 線性優(yōu)先級調(diào)度策略線性優(yōu)先級調(diào)度策略圖圖 4.5 線性優(yōu)先級調(diào)度線性優(yōu)

5、先級調(diào)度CPU完成完成新創(chuàng)建進程隊列新創(chuàng)建進程隊列享受服務進程隊列享受服務進程隊列8第第4 4章章 處理機調(diào)度處理機調(diào)度l 新創(chuàng)建進程隊列中進程的優(yōu)先級新創(chuàng)建進程隊列中進程的優(yōu)先級P=a*t (a0)l 享受服務進程享受服務進程隊列中進程的優(yōu)先級隊列中進程的優(yōu)先級P=b*t (ab0) P(t)=a*(t t1)進程在時刻進程在時刻t1被創(chuàng)建被創(chuàng)建 P(t)=a*(t1 t1)+b*(t t1)進程在時刻進程在時刻t1轉(zhuǎn)入轉(zhuǎn)入享受服務享受服務隊列隊列 若若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章章 處理機調(diào)度處理機調(diào)度4.4 調(diào)度算法調(diào)度算法 5. 最短作業(yè)優(yōu)先法最短作業(yè)優(yōu)先法SJFShortest Job First 6. 最高響應比優(yōu)先法最高響應比優(yōu)先法HRNHighest Response-ratio Next 響應比響應比=等待時間等待時間/運行時間運行時間 例例9:30開始調(diào)度：作業(yè)開始調(diào)度：作業(yè)A的響應比的響應比=40/90，作業(yè)，作業(yè)B的響應比的響應比=30/24，作業(yè)，作業(yè)C的響應比的響應比=0/60。9:54調(diào)度：作業(yè)調(diào)度：作業(yè)A的響應比的響應

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

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

9、忽略不計。現(xiàn)有一作業(yè)序列如下：配，并假設輸入輸出操作的時間忽略不計?，F(xiàn)有一作業(yè)序列如下：作業(yè)號作業(yè)號進輸入井時間進輸入井時間要求計算時間要求計算時間要求主存量要求主存量申請磁帶機數(shù)申請磁帶機數(shù)申請打印機數(shù)申請打印機數(shù)18:0025分鐘分鐘15K1臺臺1臺臺28:2010分鐘分鐘30K0臺臺1臺臺38:2020分鐘分鐘60K1臺臺0臺臺48:3020分鐘分鐘20K1臺臺0臺臺58:3515分鐘分鐘10K1臺臺1臺臺12第第4 4章章 處理機調(diào)度處理機調(diào)度 假設作業(yè)調(diào)度采用先來先服務算法，優(yōu)先分配主存的低地址區(qū)域且假設作業(yè)調(diào)度采用先來先服務算法，優(yōu)先分配主存的低地址區(qū)域且不準移動已在主存中的作業(yè)，

10、在主存中的作業(yè)平分不準移動已在主存中的作業(yè)，在主存中的作業(yè)平分CPU時間，則作業(yè)調(diào)時間，則作業(yè)調(diào)度選中作業(yè)的次序是度選中作業(yè)的次序是_A_，如果把一個作業(yè)從進入輸入井到得到計算，如果把一個作業(yè)從進入輸入井到得到計算結(jié)果的時間定義為周轉(zhuǎn)時間，則在忽略系統(tǒng)工作時間的情況下，最大的結(jié)果的時間定義為周轉(zhuǎn)時間，則在忽略系統(tǒng)工作時間的情況下，最大的作業(yè)周轉(zhuǎn)時間是作業(yè)周轉(zhuǎn)時間是_B_，最小的作業(yè)周轉(zhuǎn)時間是，最小的作業(yè)周轉(zhuǎn)時間是_C_，作業(yè)的平均周轉(zhuǎn)，作業(yè)的平均周轉(zhuǎn)時間是時間是_D_，作業(yè)全部執(zhí)行結(jié)束的時間是，作業(yè)全部執(zhí)行結(jié)束的時間是_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章章 處理機調(diào)度處理機調(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章章 處理機調(diào)

12、度處理機調(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)時間：周轉(zhuǎn)時間：J1(30分鐘分鐘)、 J2(55分鐘分鐘)、 J3(40分鐘分鐘)、 J4(40分鐘分鐘)、 J5(55分鐘分鐘)5分鐘分鐘5分鐘分鐘5分鐘分鐘15分鐘分鐘15第第4 4章章 處理機調(diào)度處理機調(diào)度4.6 實時系統(tǒng)調(diào)度方法實時系統(tǒng)調(diào)度方法4.6.1 實時系統(tǒng)的特點實時系統(tǒng)的特點 (1) 有限等待時間有限等待時間 (2) 有限響應時間有限響應時間 (3) 用戶控制用戶控制 (4) 可靠性高可靠性高 (5) 系

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

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

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

16、任務周期為T，任務的執(zhí)行時間為，任務的執(zhí)行時間為C，則使用頻率單，則使用頻率單調(diào)調(diào)度算法的必要條件是調(diào)調(diào)度算法的必要條件是CT。圖圖 4.12 時限調(diào)度算法的調(diào)度順序時限調(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章章 處理機調(diào)度處理機調(diào)度 設有設有A、B、C三個作業(yè)，執(zhí)行情況如下表所示。請三個作業(yè)，執(zhí)行情況如下表所示。請?zhí)顚懼苻D(zhuǎn)時間欄，并回答下列問題：填寫周轉(zhuǎn)時間欄，并回答下列問題： (1) 作業(yè)的平均周轉(zhuǎn)時間是多少？作業(yè)的平均周轉(zhuǎn)時間是多少？ (2) 采

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

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