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

1、10.10.10.1 1 1/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)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)外部事件請(qǐng)求，在規(guī)定時(shí)間內(nèi)完實(shí)時(shí)系統(tǒng)是系統(tǒng)能及時(shí)響應(yīng)外部事件請(qǐng)求，在規(guī)定時(shí)間內(nèi)完成對(duì)該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。成對(duì)該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。用于工業(yè)過(guò)程、軍事、金融等實(shí)時(shí)控制、實(shí)時(shí)信息處理領(lǐng)域用于工業(yè)過(guò)程、軍事、金融等實(shí)時(shí)控

2、制、實(shí)時(shí)信息處理領(lǐng)域10.10.10.2 2 2/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)按任務(wù)執(zhí)行時(shí)是否呈現(xiàn)周期性來(lái)劃分：按任務(wù)執(zhí)行時(shí)是否呈現(xiàn)周期性來(lái)劃分： 周期性實(shí)時(shí)任務(wù)：周期性實(shí)時(shí)任務(wù)：每隔一段固定的時(shí)間發(fā)生每隔一段固定的時(shí)間發(fā)生 非周期性實(shí)時(shí)任務(wù)：非周期性實(shí)時(shí)任務(wù)：在不可預(yù)測(cè)的時(shí)間發(fā)生。在不可預(yù)測(cè)的時(shí)間發(fā)生。 截止時(shí)間截止時(shí)間(deadline)(deadline)：開(kāi)始截止時(shí)間（最晚開(kāi)始時(shí)間）和完成截止時(shí)間（最晚完成時(shí)間）開(kāi)始截止時(shí)間（最晚開(kāi)始時(shí)間）和完成截止時(shí)間（最晚完成時(shí)間）根據(jù)對(duì)截止時(shí)間的要求來(lái)劃分：根據(jù)對(duì)截止

3、時(shí)間的要求來(lái)劃分： 硬實(shí)時(shí)任務(wù)：存在必須滿足的時(shí)間限制。硬實(shí)時(shí)任務(wù)：存在必須滿足的時(shí)間限制。 軟實(shí)時(shí)任務(wù)軟實(shí)時(shí)任務(wù): :可以容忍偶爾超過(guò)時(shí)間限制?？梢匀萑膛紶柍^(guò)時(shí)間限制。實(shí)時(shí)任務(wù)的類(lèi)型：實(shí)時(shí)任務(wù)的類(lèi)型：10.10.10.3 3 3/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng) 2 2）實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件）實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 提供必要的信息提供必要的信息( (就緒時(shí)間、截止時(shí)間、處就緒時(shí)間、截止時(shí)間、處理時(shí)間、資源要求、資源優(yōu)先級(jí)理時(shí)間、資源要求、資源優(yōu)先級(jí)) )系統(tǒng)處理能力要足夠強(qiáng)系統(tǒng)處理能力要足夠強(qiáng): :單處理機(jī)情況下

4、：設(shè)有單處理機(jī)情況下：設(shè)有m個(gè)周期性事件，事件個(gè)周期性事件，事件i的周的周期為期為pi，其中每個(gè)事件需要，其中每個(gè)事件需要ci秒的秒的cpu時(shí)間來(lái)處時(shí)間來(lái)處理，可調(diào)度的的實(shí)時(shí)系統(tǒng)必須滿足：理，可調(diào)度的的實(shí)時(shí)系統(tǒng)必須滿足： c1/p1 + c2/p2 + + cm/pm 1采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制具有快速切換機(jī)制10.10.10.4 4 4/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3 3）實(shí)時(shí)調(diào)度算法的分類(lèi)）實(shí)時(shí)調(diào)度算法的分類(lèi) 1)1)非搶占式調(diào)度算法非搶占式調(diào)度算法 : :非搶占式輪轉(zhuǎn)調(diào)度算法非搶占

5、式輪轉(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)度算法立即搶占優(yōu)先權(quán)調(diào)度算法( (緊迫任務(wù)緊迫任務(wù), ,幾幾msms甚至百微秒甚至百微秒) )10.10.10.5 5 5/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)圖圖 3-8 3-8 實(shí)時(shí)進(jìn)程

6、調(diào)度實(shí)時(shí)進(jìn)程調(diào)度 10.10.10.6 6 6/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)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ù)：最早開(kāi)始截止時(shí)間優(yōu)先）非搶占式調(diào)度用于非周期實(shí)時(shí)任務(wù)：最早開(kāi)始截止時(shí)間優(yōu)先10.10.10.7 7 7/13/13/13 november 21novem

7、ber 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)2 2）搶占式調(diào)度用于周期實(shí)時(shí)任務(wù)：最早完成截止時(shí)間優(yōu)先）搶占式調(diào)度用于周期實(shí)時(shí)任務(wù)：最早完成截止時(shí)間優(yōu)先10.10.10.8 8 8/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)ii. 最低松弛度優(yōu)先即最低松弛度優(yōu)先即llf(least laxity first)算法算法 p101 該算法是根據(jù)任務(wù)緊急該算法是根據(jù)任務(wù)緊急( (或松弛或松弛) )的程度，來(lái)確定任務(wù)的程度，來(lái)確定任務(wù)的優(yōu)先級(jí)，即的優(yōu)先級(jí)，即選擇松弛度最少的進(jìn)程執(zhí)行選擇松弛度最少的進(jìn)程執(zhí)行該算法。該算法。 主

8、要用于可搶占調(diào)度方式中。主要用于可搶占調(diào)度方式中。松弛度：即各個(gè)進(jìn)程的富裕時(shí)間（裕度）松弛度：即各個(gè)進(jìn)程的富裕時(shí)間（裕度）松弛度松弛度=必須完成時(shí)間必須完成時(shí)間-其本身的運(yùn)行時(shí)間其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間當(dāng)前時(shí)間10.10.10.9 9 9/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)圖圖 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ù)

9、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。 10.10.10.101010/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)實(shí)時(shí)調(diào)度問(wèn)題-習(xí)題110.10.10.111111/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)實(shí)時(shí)調(diào)度問(wèn)題-習(xí)題110.10.10.121212/13/13/13 november 21novembe

10、r 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)實(shí)時(shí)調(diào)度問(wèn)題-習(xí)題210.10.10.131313/13/13/13 november 21november 21november 21操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)（第三章（第三章 進(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ū)；信號(hào)量、臨界資源、臨界區(qū)；信號(hào)量、pv操作；經(jīng)典同步操作；經(jīng)典同步問(wèn)題、同步問(wèn)題問(wèn)題、同步問(wèn)題;管程管程進(jìn)程間通信進(jìn)程間通信ipcipc：基本概念；三種通信方式；直接、間接方式基本概念；三種通信方式；直接、間接方式線程：線程：引入原因，與進(jìn)程比較引入原因，與進(jìn)程比較管程：管程：概念，特點(diǎn)概念，特點(diǎn)死鎖問(wèn)題：死鎖問(wèn)題：原因，條件，解決方法；原因，條件，解決方法；銀行家算法銀