1、5、實時調(diào)度,1） 實時系統(tǒng)(real-time system) P11,實時：表示“及時”， 實時系統(tǒng)是系統(tǒng)能及時響應(yīng)外部事件請求，在規(guī)定時間內(nèi)完成對該事件的處理，并控制所有實時任務(wù)協(xié)調(diào)一致地運(yùn)行。 用于工業(yè)過程、軍事、金融等實時控制、實時信息處理領(lǐng)域,按任務(wù)執(zhí)行時是否呈現(xiàn)周期性來劃分： 周期性實時任務(wù)：每隔一段固定的時間發(fā)生 非周期性實時任務(wù)：在不可預(yù)測的時間發(fā)生。 截止時間(deadline)： 開始截止時間（最晚開始時間）和完成截止時間（最晚完成時間） 根據(jù)對截止時間的要求來劃分： 硬實時任務(wù)：存在必須滿足的時間限制。 軟實時任務(wù):可以容忍偶爾超過時間限制。,實時任務(wù)的類型：,2）實現(xiàn)

2、實時調(diào)度的基本條件,提供必要的信息(就緒時間、截止時間、處理時間、資源要求、資源優(yōu)先級) 系統(tǒng)處理能力要足夠強(qiáng): 單處理機(jī)情況下：設(shè)有m個周期性事件，事件i的周期為Pi，其中每個事件需要Ci秒的CPU時間來處理，可調(diào)度的的實時系統(tǒng)必須滿足： C1/P1 + C2/P2 + + Cm/Pm 1 采用搶占式調(diào)度機(jī)制 具有快速切換機(jī)制,練習(xí)：,一個實時系統(tǒng)中有4個周期性事件，周期分別為50、100、300和250ms。若假設(shè)其處理分別需要35、20、10和x毫秒，則該系統(tǒng)可調(diào)度允許的x值最大為多少？,實時任務(wù)可調(diào)度應(yīng)滿足如下條件：35/50+20/100+10/300+x/2501x250(1-28

3、/30)=16.67,3）實時調(diào)度算法的分類,1)非搶占式調(diào)度算法 : 非搶占式輪轉(zhuǎn)調(diào)度算法(實時要求不太嚴(yán)格，s) 非搶占式優(yōu)先調(diào)度算法(要求比較嚴(yán)格,數(shù)百ms) 2)搶占式調(diào)度算法: 基于時鐘中斷的搶占優(yōu)先調(diào)度算法(要求比較嚴(yán)格,數(shù)10ms) 立即搶占優(yōu)先權(quán)調(diào)度算法(緊迫任務(wù),幾ms甚至百微秒),圖 3-8 實時進(jìn)程調(diào)度,4）常用的幾種實時調(diào)度算法,I.最早截止時間優(yōu)先即EDF(Earliest Deadline First)算法 P100,圖 3-9 EDF算法用于非搶占調(diào)度方式,1）非搶占式調(diào)度用于非周期實時任務(wù)：最早開始截止時間優(yōu)先,Fig. 3-10,2）搶占式調(diào)度用于周期實時任務(wù)

4、：最早完成截止時間優(yōu)先,II. 最低松弛度優(yōu)先即LLF(Least Laxity First)算法 P101,該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級，即選擇松弛度最少的進(jìn)程執(zhí)行該算法。 主要用于可搶占調(diào)度方式中。,松弛度：即各個進(jìn)程的富裕時間（裕度） 松弛度=必須完成時間-其本身的運(yùn)行時間-當(dāng)前時間,圖 3-12 利用LLF算法進(jìn)行調(diào)度的情況,圖 3-11 A和B任務(wù)每次必須完成的時間,假如在一個實時系統(tǒng)中，有兩個周期性實時任務(wù)A和B，任務(wù)A要求每 20 ms執(zhí)行一次，執(zhí)行時間為 10 ms；任務(wù)B只要求每50 ms執(zhí)行一次，執(zhí)行時間為 25 ms。,實時調(diào)度問題-習(xí)題1,對下面的5個非周期性實時任務(wù)，按最早開始截止時間優(yōu)先調(diào)度算法如何進(jìn)行CPU調(diào)度？(非搶占式/搶占式),到達(dá)時間,開始截止時間,實時調(diào)度問題-習(xí)題1,對下面的5個非周期性實時任務(wù)，按最早開始截止時間優(yōu)先調(diào)度算法如何進(jìn)行CPU調(diào)度？(非搶占式/搶占式),到達(dá)時間,開始截止時間,實時調(diào)度問題-習(xí)題2,若有