操作系統(tǒng)10-實(shí)時(shí)調(diào)度課件

1、10.1/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度5、實(shí)時(shí)調(diào)度、實(shí)時(shí)調(diào)度1 1） 實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)( (real-time system) real-time system) P11P11實(shí)時(shí)：表示實(shí)時(shí)：表示“及時(shí)及時(shí)”，實(shí)時(shí)系統(tǒng)是系統(tǒng)能及時(shí)響應(yīng)外部事件請求，在規(guī)定時(shí)間內(nèi)完實(shí)時(shí)系統(tǒng)是系統(tǒng)能及時(shí)響應(yīng)外部事件請求，在規(guī)定時(shí)間內(nèi)完成對該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。成對該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。用于工業(yè)過程、軍事、金融等實(shí)時(shí)控制、實(shí)時(shí)信息處理領(lǐng)域用于工業(yè)過程、軍事、金融等實(shí)時(shí)控制、實(shí)時(shí)信息處理領(lǐng)域10.2/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度按任務(wù)執(zhí)行時(shí)是否

2、呈現(xiàn)周期性來劃分：按任務(wù)執(zhí)行時(shí)是否呈現(xiàn)周期性來劃分： 周期性實(shí)時(shí)任務(wù)：每隔一段固定的時(shí)間發(fā)生周期性實(shí)時(shí)任務(wù)：每隔一段固定的時(shí)間發(fā)生 非周期性實(shí)時(shí)任務(wù)：在不可預(yù)測的時(shí)間發(fā)生。非周期性實(shí)時(shí)任務(wù)：在不可預(yù)測的時(shí)間發(fā)生。 截止時(shí)間截止時(shí)間( (deadline)deadline)：開始截止時(shí)間（最晚開始時(shí)間）和完成截止時(shí)間（最晚完成時(shí)間）開始截止時(shí)間（最晚開始時(shí)間）和完成截止時(shí)間（最晚完成時(shí)間）根據(jù)對截止時(shí)間的要求來劃分：根據(jù)對截止時(shí)間的要求來劃分： 硬實(shí)時(shí)任務(wù)：存在必須滿足的時(shí)間限制。硬實(shí)時(shí)任務(wù)：存在必須滿足的時(shí)間限制。 軟實(shí)時(shí)任務(wù)軟實(shí)時(shí)任務(wù): :可以容忍偶爾超過時(shí)間限制?？梢匀萑膛紶柍^時(shí)間限制。

3、實(shí)時(shí)任務(wù)的類型：實(shí)時(shí)任務(wù)的類型：10.3/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度 2 2）實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件）實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 提供必要的信息提供必要的信息( (就緒時(shí)間、截止時(shí)間、處就緒時(shí)間、截止時(shí)間、處理時(shí)間、資源要求、資源優(yōu)先級理時(shí)間、資源要求、資源優(yōu)先級) )系統(tǒng)處理能力要足夠強(qiáng)系統(tǒng)處理能力要足夠強(qiáng): :單處理機(jī)情況下：設(shè)有單處理機(jī)情況下：設(shè)有m個(gè)周期性事件，事件個(gè)周期性事件，事件i的周期為的周期為Pi，其中每個(gè)事件需要其中每個(gè)事件需要Ci秒的秒的CPU時(shí)間時(shí)間來處理，可調(diào)度的的實(shí)時(shí)系統(tǒng)必須滿足：來處理，可調(diào)度的的實(shí)時(shí)系統(tǒng)必須滿足： C1/P1 + C2/P2 + + Cm

4、/Pm 1采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制具有快速切換機(jī)制10.4/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度3 3）實(shí)時(shí)調(diào)度算法的分類）實(shí)時(shí)調(diào)度算法的分類 1)1)非搶占式調(diào)度算法非搶占式調(diào)度算法 : :非搶占式輪轉(zhuǎn)調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法( (實(shí)時(shí)要求不太嚴(yán)格，實(shí)時(shí)要求不太嚴(yán)格，s)s)非搶占式優(yōu)先調(diào)度算法非搶占式優(yōu)先調(diào)度算法( (要求比較嚴(yán)格要求比較嚴(yán)格, ,數(shù)百數(shù)百ms)ms)2)2)搶占式調(diào)度算法搶占式調(diào)度算法: :基于時(shí)鐘中斷的搶占優(yōu)先調(diào)度算法基于時(shí)鐘中斷的搶占優(yōu)先調(diào)度算法( (要求比較嚴(yán)格要求比較嚴(yán)格, ,數(shù)數(shù)10ms)10ms)立即搶占優(yōu)先權(quán)調(diào)度算法立即搶

5、占優(yōu)先權(quán)調(diào)度算法( (緊迫任務(wù)緊迫任務(wù), ,幾幾msms甚至百微秒甚至百微秒) )10.5/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度圖圖 3-8 3-8 實(shí)時(shí)進(jìn)程調(diào)度實(shí)時(shí)進(jìn)程調(diào)度 10.6/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度4 4）常用的幾種實(shí)時(shí)調(diào)度算法）常用的幾種實(shí)時(shí)調(diào)度算法 I.最早截止時(shí)間優(yōu)先即最早截止時(shí)間優(yōu)先即EDF(Earliest Deadline First)算法算法 P100圖圖 3-9 EDF3-9 EDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式 1 1）非搶占式調(diào)度用于非周期實(shí)時(shí)任務(wù)：最早開始截止時(shí)間優(yōu)先）非搶占式調(diào)度用于非周期實(shí)時(shí)任務(wù)：最早開始截止時(shí)間優(yōu)先10.

6、7/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度2 2）搶占式調(diào)度用于周期實(shí)時(shí)任務(wù)：最早完成截止時(shí)間優(yōu)先）搶占式調(diào)度用于周期實(shí)時(shí)任務(wù)：最早完成截止時(shí)間優(yōu)先10.8/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度II. 最低松弛度優(yōu)先即最低松弛度優(yōu)先即LLF(Least Laxity First)算法算法 P101 該算法是根據(jù)任務(wù)緊急該算法是根據(jù)任務(wù)緊急( (或松弛或松弛) )的程度，來確定任務(wù)的程度，來確定任務(wù)的優(yōu)先級，即的優(yōu)先級，即選擇松弛度最少的進(jìn)程執(zhí)行選擇松弛度最少的進(jìn)程執(zhí)行該算法。該算法。 主要用于可搶占調(diào)度方式中。主要用于可搶占調(diào)度方式中。松弛度：即各個(gè)進(jìn)程的富裕時(shí)間（裕度松弛度：即各個(gè)進(jìn)程

7、的富裕時(shí)間（裕度）松弛度松弛度=必須完成時(shí)間必須完成時(shí)間-其本身的運(yùn)行時(shí)間其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間當(dāng)前時(shí)間10.9/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度圖圖 3-12 3-12 利用利用LLFLLF算法進(jìn)行調(diào)度的情況算法進(jìn)行調(diào)度的情況圖圖 3-11 A3-11 A和和B B任務(wù)每次必須完成的時(shí)間任務(wù)每次必須完成的時(shí)間假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和和B，任務(wù)，任務(wù)A要求每要求每 20 ms執(zhí)行一次，執(zhí)行時(shí)間為執(zhí)行一次，執(zhí)行時(shí)間為 10 ms；任務(wù)；任務(wù)B只要求每只要求每50 ms執(zhí)行一次，執(zhí)行時(shí)間為執(zhí)行一次，執(zhí)行時(shí)間為 25 ms。

8、 10.10/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度問題-習(xí)題110.11/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度問題-習(xí)題110.12/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度問題-習(xí)題210.13/132022年1月操作系統(tǒng)10-實(shí)時(shí)調(diào)度（第三章（第三章 進(jìn)程管理）小結(jié)進(jìn)程管理）小結(jié)順序執(zhí)行和并發(fā)執(zhí)行順序執(zhí)行和并發(fā)執(zhí)行進(jìn)程：進(jìn)程：相關(guān)概念相關(guān)概念;(;(與程序比較與程序比較) )；靜態(tài)表示（上下文，包括；靜態(tài)表示（上下文，包括PCBPCB），），動(dòng)態(tài)表示（狀態(tài)）動(dòng)態(tài)表示（狀態(tài)）進(jìn)程控制進(jìn)程控制: :狀態(tài)轉(zhuǎn)換（注意：掛起和激活）狀態(tài)轉(zhuǎn)換（注意：掛起和激活）互斥和同步：互斥和同步：臨界資源、臨界區(qū)；信號量、臨界資源、臨界區(qū)；信號量、PV操作；經(jīng)典同步操作；經(jīng)典同步問題、同步問題問題、同步問題;管程管程進(jìn)程間通信進(jìn)程間通信IPCIPC：基本概念；三種通信方式；直接、間接方式基本概念；三種通信方式；直接、間接方式線程：線程：引入原因，與進(jìn)程比較引入原因，與進(jìn)程比較管程：管程：概念，特點(diǎn)概念，特點(diǎn)死鎖問題：死鎖問題：原因，條件，解決方法；原因，條件，解決方法；銀行家算法銀行家算法處理機(jī)調(diào)度：處理機(jī)調(diào)度：分為幾個(gè)層次分為幾個(gè)層次(