【正文】 第 4周期 ， 而任務(wù) B已進(jìn)入第 2周期 ， 故再調(diào)度 B2執(zhí)行 。 在 t4?=?40 ms時(shí) ， A3的松弛度為 10 ms(即 60??10??40)， 而 B1的松弛度僅為 5 ms(即 50??5??40)，故又應(yīng)重新調(diào)度 B1執(zhí)行 。在 t2?=?10 ms時(shí)， A2的松弛度可按下式算出： A2的松弛度 ?=?必須完成時(shí)間 ??其本身的運(yùn)行時(shí)間 ??當(dāng)前時(shí)間 ?? =?40 ms10 ms10 ms?=?20 ms 第三章 處理機(jī)調(diào)度與死鎖 類似地 ， 可算出 B1的松弛度為 15 ms， 故調(diào)度程序應(yīng)選擇B2運(yùn)行 。為保證不遺漏任何一次截止時(shí)間，應(yīng)采用最低松弛度優(yōu)先的搶占調(diào)度策略。假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù) A和 B，任務(wù) A要求每 20 ms執(zhí)行一次，執(zhí)行時(shí)間為 10 ms；任務(wù) B只要求每 50 ms執(zhí)行一次，執(zhí)行時(shí)間為 25 ms。在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。例如，一個(gè)任務(wù)在 200 ms時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間就有 100 ms，因此，調(diào)度程序必須在 100 ms之前調(diào)度執(zhí)行，該任務(wù)的 緊急程度 (松弛程度 )為100 ms。 第三章 處理機(jī)調(diào)度與死鎖 2． 最低松弛度優(yōu)先即 LLF(Least Laxity First)算法 該算法是根據(jù)任務(wù)緊急 (或松弛 )的程度，來確定任務(wù)的優(yōu)先級(jí)。在 t = 0時(shí)， A1和 B1同時(shí)到達(dá)，由于 A1的截止時(shí)間比 B1早 ，故調(diào)度A1執(zhí)行；在 t = 10時(shí)， A1完成，又調(diào)度 B1執(zhí)行；在 t = 20時(shí)，A2到達(dá) ，由于 A2的截止時(shí)間比 B2早， B1被中斷而調(diào)度 A2執(zhí)行；在 t = 30時(shí)， A2完成，又重新調(diào)度 B1執(zhí)行；在 t = 40時(shí)，A3又到達(dá)，但 B1的截止時(shí)間要比 A3早，仍應(yīng)讓 B1繼續(xù)執(zhí)行直到完成 (t = 45)，然后再調(diào)度 A3執(zhí)行；在 t = 55時(shí)， A3完成，又調(diào)度 B2執(zhí)行。其中任務(wù) A的到達(dá)時(shí)間為 0、 … ；任務(wù) A的最后期限為 60、 … ；任務(wù) B的到達(dá)時(shí)間為 0、 50、 100、 … ；任務(wù) B的最后期限為 50、 100、 150、 … (注：?jiǎn)挝唤詾?ms)。在該例中有兩個(gè)周期性任務(wù)，任務(wù) A的周期時(shí)間為20 ms，每個(gè)周期的處理時(shí)間為 10 ms；任務(wù) B的周期時(shí)間為50 ms，每個(gè)周期的處理時(shí)間為 25 ms。在此期間又到達(dá)作業(yè) 4，其開始截止時(shí)間仍是早于任務(wù) 2的，故在任務(wù) 3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù) 4執(zhí)行，最后才調(diào)度任務(wù) 2執(zhí)行。系統(tǒng)首先調(diào)度任務(wù) 1執(zhí)行，在任務(wù) 1執(zhí)行期間，任務(wù) 3又先后到達(dá)。 1) 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法 2) 立即搶占 (Immediate Preemption)的優(yōu)先權(quán)調(diào)度算法 第三章 處理機(jī)調(diào)度與死鎖 圖 38 實(shí)時(shí)進(jìn)程調(diào)度 ( a ) 非搶占式輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程 實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度實(shí)時(shí)進(jìn)程搶占當(dāng)前進(jìn)程并立即執(zhí)行( d ) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間進(jìn)程 1 進(jìn)程 2實(shí)時(shí)進(jìn)程要求調(diào)度進(jìn)程 n 實(shí)時(shí)進(jìn)程調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行( b ) 非搶占式優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程 實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度 當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時(shí)間當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度 時(shí)鐘中斷到來時(shí)調(diào)度時(shí)間( c ) 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時(shí)間實(shí)時(shí)進(jìn)程?實(shí)時(shí)進(jìn)程加入隊(duì)尾等待下一個(gè)時(shí)間片 實(shí)時(shí)進(jìn)程加入隊(duì)首 阻塞 第三章 處理機(jī)調(diào)度與死鎖 常用的幾種實(shí)時(shí)調(diào)度算法 1． 最早截止時(shí)間優(yōu)先即 EDF(Earliest Deadline First)算法 1) 非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù) 圖 39示出了將該算法用于非搶占調(diào)度方式之例。 第三章 處理機(jī)調(diào)度與死鎖 2． 搶占式調(diào)度算法 在要求較嚴(yán)格的 (響應(yīng)時(shí)間為數(shù) 十毫秒以下 )的實(shí)時(shí)系統(tǒng)中 ，應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法 。 2．系統(tǒng)處理能力強(qiáng) 3．采用搶占式調(diào)度機(jī)制 4．具有快速切換機(jī)制 第三章 處理機(jī)調(diào)度與死鎖 實(shí)時(shí)調(diào)度算法的分類 1． 非搶占式調(diào)度算法 1) 非搶占式輪轉(zhuǎn)調(diào)度算法 數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間 ，可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)中。 (4) 資源要求。 (2) 開始截止時(shí)間和完成截止時(shí)間。請(qǐng)證明采用最短作業(yè)優(yōu)先調(diào)度算法能夠獲得最小平均周轉(zhuǎn)時(shí)間。 第三章 處理機(jī)調(diào)度與死鎖 進(jìn)程調(diào)度算法 優(yōu)先調(diào)度與時(shí)間片調(diào)度相結(jié)合的調(diào)度策略： (1) 當(dāng) CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列非空，則從高優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為 100ms (2) 當(dāng) CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列為空，則從低優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為 500ms 調(diào)度效果 優(yōu)先照顧了 I∕O量大的進(jìn)程； 適當(dāng)照顧了計(jì)算量大的進(jìn)程。 ?低優(yōu)先就緒隊(duì) —— 一個(gè)進(jìn)程如果在運(yùn)行中超過了它的時(shí)間量就進(jìn)入低優(yōu)先就緒隊(duì)列。 ??? 長(zhǎng)批處理作業(yè)用戶：依次在前 N1個(gè)隊(duì)列中執(zhí)行，在第 N個(gè)隊(duì)列中按輪轉(zhuǎn)方式運(yùn)行。如有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列，則剝奪 CPU執(zhí)行新進(jìn)程，舊進(jìn)程放入原隊(duì)列尾 第三章 處理機(jī)調(diào)度與死鎖 3．多級(jí)反饋隊(duì)列調(diào)度 算法性能 ??? 終端型用戶：在第一隊(duì)列中完成，作業(yè)短，交互型。 ?當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先放在第一隊(duì)列尾，按FCFS原則調(diào)度；如果該時(shí)間片內(nèi)未結(jié)束，轉(zhuǎn)入第二隊(duì)列尾；直到最后的第 N隊(duì)列，在第 N隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式執(zhí)行（不在轉(zhuǎn)下一個(gè)隊(duì)列了，因?yàn)闆]有了）。隊(duì)列按 FCFS原則排列。圖 37是多級(jí)反饋隊(duì)列算法的示意。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同， 在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小 。 第三章 處理機(jī)調(diào)度與死鎖 圖 35 q=1和 q=4時(shí)的進(jìn)程運(yùn)行情況 ABCDEABCDEABCEACE( a ) q ＝ 1( b) q ＝ 41 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17tA、 B、 C、 D、 E？ A:4 B:3 C:4 D:2 E:4 第三章 處理機(jī)調(diào)度與死鎖 圖 36 q=1和 q=4時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間 進(jìn)程名 A B C D E 平均 到達(dá)時(shí)間 0 1 2 3 4 作業(yè) 情況 時(shí) 間 片 服務(wù)時(shí)間 4 3 4 2 4 完成時(shí)間 15 12 16 9 17 周轉(zhuǎn)時(shí)間 15 11 14 6 13 1 1. 8 RR q =1 帶權(quán)周轉(zhuǎn)時(shí)間 3. 75 3. 67 3. 5 3 3. 33 3. 46 完成時(shí)間 4 7 11 13 17 周轉(zhuǎn)時(shí)間 4 6 9 10 13 8. 4 RR q =4 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2. 25 5 3. 33 2. 5 第三章 處理機(jī)調(diào)度與死鎖 2． 多級(jí)反饋隊(duì)列調(diào)度算法 (1) 設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。 圖 35示出了時(shí)間片分別為 q=1和 q=4時(shí)， A、 B、 C、 D、 E五個(gè)進(jìn)程的運(yùn)行情況，而圖 36為 q=1和 q=4時(shí)各進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。 ?? 2）時(shí)間片的劃分 簡(jiǎn)單循環(huán)輪轉(zhuǎn)調(diào)度 時(shí)間片 Q=R/Nmax R：響應(yīng)時(shí)間 Nmax：最大進(jìn)程數(shù) 可變時(shí)間片輪轉(zhuǎn)調(diào)度 時(shí)間片 Q=R/N R：響應(yīng)時(shí)間 N：實(shí)際進(jìn)程數(shù) 第三章 處理機(jī)調(diào)度與死鎖 2) 時(shí)間片大小的確定 時(shí)間片很小 ：將有利于短作業(yè) ， 會(huì)頻繁地發(fā)生中斷 、 進(jìn)程上下文的切換 ， 從而增加系統(tǒng)的開銷； 時(shí)間片太長(zhǎng) ， 使得每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成 ， 時(shí)間片輪轉(zhuǎn)算法便退化為 FCFS算法 ， 無法滿足交互式用戶的需求 。 第三章 處理機(jī)調(diào)度與死鎖 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 1． 時(shí)間片輪轉(zhuǎn)法 1) 基本原理 將 CPU 的處理時(shí)間分成固定大小的時(shí)間片，系統(tǒng)將所有就緒進(jìn)程按先來先服務(wù)的原則排成隊(duì)列。 ?長(zhǎng)短作業(yè)都得到照顧，但是增加系統(tǒng)開銷。 (2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。據(jù)此，又可表示為： 要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間相應(yīng)比 ???PR每當(dāng)要進(jìn)行調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇其中 RP最大者 投入執(zhí)行。 HRN （ Highest Responseratio Next）是 對(duì) FCFS和 SJF方式的一種綜合平衡 。 改變進(jìn)程優(yōu)先級(jí)的方式： ??? 線形優(yōu)先級(jí)調(diào)度策略 新創(chuàng)建的進(jìn)程按 FCFS方式排成就緒隊(duì)列，優(yōu)先級(jí)以 a的速率增加，正在執(zhí)行的進(jìn)程優(yōu)先級(jí)以 b的速率下降。 靜態(tài)優(yōu)先權(quán) 特點(diǎn) ：簡(jiǎn)單易行，系統(tǒng)開銷?。徊粔蚓_，可能出現(xiàn)優(yōu)先級(jí)低的作業(yè)或進(jìn)程，長(zhǎng)期得不到調(diào)度。 第三章 處理機(jī)調(diào)度與死鎖 2． 優(yōu)先權(quán)的類型 如何確定 ？ 1) 靜態(tài)優(yōu)先權(quán) ? 作業(yè)的優(yōu)先級(jí)確定原則 ? 作業(yè)的緊急程度 ? 作業(yè)類型 ? 作業(yè)要求資源情況 第三章 處理機(jī)調(diào)度與死鎖 ? 進(jìn)程的優(yōu)先級(jí)確定原則 ? 按進(jìn)程的類型賦予不同的優(yōu)先級(jí) ? 用戶進(jìn)程類型： I/O 忙， CPU忙， I/O與 CPU 均衡 ? 系統(tǒng)進(jìn)程類型：調(diào)度進(jìn)程， I/O 進(jìn)程，中斷處理，存儲(chǔ)各類等。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就 立即停止當(dāng)前進(jìn)程 (原優(yōu)先權(quán)最高的進(jìn)程 )的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。 主要用于 批處理系統(tǒng)進(jìn)程調(diào)度 中；也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。 ? 用于進(jìn)程調(diào)度時(shí)，把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。 第三章 處理機(jī)調(diào)度與死鎖 作業(yè) 提交時(shí)間 執(zhí)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 3 4 平均周轉(zhuǎn)時(shí)間 t = 平均帶權(quán)周轉(zhuǎn)時(shí)間 w = FCFS、 SJF算法填表（單位：小時(shí)，并以十進(jìn)制計(jì)） 第三章 處理機(jī)調(diào)度與死鎖 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 1． 優(yōu)先權(quán)調(diào)度算法的類型 ? 為了照顧緊迫型作業(yè) /進(jìn)程，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先 (FPF、 HPF=highest priority first )調(diào)度算法。 和 FCFS調(diào)度算法進(jìn)行比較 第三章 處理機(jī)調(diào)度與死鎖 SJ(P)F調(diào)度算法缺點(diǎn)： (1) 該算法對(duì)長(zhǎng)作業(yè)不利 ， 可能出現(xiàn)饑餓現(xiàn)象 (2) 因而不能保證緊迫性作業(yè) (進(jìn)程 )會(huì)被及時(shí)處理 。短作業(yè)優(yōu)先 (SJF)的調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。 第三章 處理機(jī)調(diào)度與死鎖 圖 34 FCFS和 SJF調(diào)度算法的性能 進(jìn)程名 A B C D E 平 均 到達(dá)時(shí)間 0 1 2 3 4 作業(yè) 情況 調(diào)度 算法 服務(wù)時(shí)間 4 3 5 2 4 完成時(shí)間 4 7 12 14 18 周轉(zhuǎn)時(shí)間 4 6 10 11 14 9 FC FS (a ) 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2 5. 5 3. 5 2. 8 完成時(shí)間 4 9 18 6 13 周轉(zhuǎn)時(shí)間 4 8 16 3 9 8 SJF (b) 帶權(quán)周轉(zhuǎn)時(shí)間 1 2. 67 3. 1 1. 5 2. 25 2. 1 第三章 處理機(jī)調(diào)度與死鎖 2．短作業(yè) (進(jìn)程 )優(yōu)先調(diào)度算法 短作業(yè) (進(jìn)程 )優(yōu)先調(diào)度算法 SJ(P)F（ Shortest job first ） ，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。圖 34(a)示出有五個(gè)進(jìn)程 A、 B、 C、 D、 E，它們到達(dá)的時(shí)間分別是 0、 3和 4，所要求的服務(wù)時(shí)間分別是 2和 4，其完成時(shí)間分別是 1 14和 18。 進(jìn)程名 到達(dá)時(shí)間 服務(wù)時(shí)間 開始執(zhí)行時(shí)間 完成時(shí)間 周轉(zhuǎn)