計算機操作系統(tǒng)課件第十講

1、2021年11月29日星期一23時41分0秒內(nèi)蒙古工業(yè)大學1q教學目的教學目的掌握實時系統(tǒng)的特點掌握實時系統(tǒng)的特點掌握實時調(diào)度算法的分類掌握實時調(diào)度算法的分類第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法掌握時限調(diào)度算法與頻率單調(diào)調(diào)度算法掌握時限調(diào)度算法與頻率單調(diào)調(diào)度算法2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學2q教學內(nèi)容教學內(nèi)容4.6 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學3第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法q 實時系統(tǒng)的特點實時系統(tǒng)的特點 實時系統(tǒng)不僅要求處理和控

2、制的正確性，還要求計算和處理結果的產(chǎn)生時間。實時任務的分類實時任務的分類v硬實時任務（硬實時任務（hard real time task）要求系統(tǒng)必須完全滿足任務的時限要求。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學4第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法v軟實時任務（軟實時任務（soft real time task）允許系統(tǒng)對任務的時限要求有一定的延遲，其時限要求只是一個相對條件。v周期性任務周期性任務要求在周期t內(nèi)完成或開始處理。v非周期性任務非周期性任務要求在規(guī)定的時間內(nèi)完成或開始處理。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學5第九講第九講 實

3、時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法實時系統(tǒng)特點實時系統(tǒng)特點v有限等待時間（決定性）有限等待時間（決定性）要求所有進程在處理時間時，都必須在有限時間內(nèi)開始處理。v有限響應時間有限響應時間要求從系統(tǒng)響應外部事件開始，必須在有限時間內(nèi)處理完畢。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學6第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法v用戶控制用戶控制實時系統(tǒng)中，用戶可以控制進程的優(yōu)先級并選擇相應的調(diào)度算法，實現(xiàn)對進程執(zhí)行順序的控制。v可靠性高可靠性高實時系統(tǒng)對外部事件的處理和控制，不允許出現(xiàn)錯誤。v系統(tǒng)出錯處理能力強系統(tǒng)出錯處理能力強要求系統(tǒng)在出錯時，既能處理發(fā)生的錯誤又不影響當前正在執(zhí)

4、行的用戶應用。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學7第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法q實時系統(tǒng)具有的功能實時系統(tǒng)具有的功能快速的進程快速的進程/線程切換速度線程切換速度它是實時調(diào)度的核心。實時調(diào)度算法的設計原則是滿足所有硬實時任務的處理時限和盡可能多的滿足軟實時任務的處理時限。快速的外部中斷處理能力快速的外部中斷處理能力快速的外部中斷反應能力，是前提條件。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學8第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法基于優(yōu)先級的隨時搶先調(diào)度策略基于優(yōu)先級的隨時搶先調(diào)度策略優(yōu)先級優(yōu)先級+時間片輪轉(zhuǎn)調(diào)度策略時間片輪轉(zhuǎn)調(diào)

5、度策略v基于優(yōu)先級調(diào)度策略的分析基于優(yōu)先級調(diào)度策略的分析每次搶占發(fā)生必須得等到時間片結束或執(zhí)行進程主動放棄處理機，本方法不適用實時系統(tǒng)。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學9第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法基于優(yōu)先級的非搶占式調(diào)度策略基于優(yōu)先級的非搶占式調(diào)度策略高優(yōu)先級進程只能等到低優(yōu)先級進程結束或主動放棄處理機，才能得到調(diào)度。本方法不適用實時系統(tǒng)?；趦?yōu)先級的固定點搶占式調(diào)度策略基于優(yōu)先級的固定點搶占式調(diào)度策略高優(yōu)先級進程只能等到固定的時間點（小于時間片長度，滿足所有硬實時任務的需要）或執(zhí)行進程主動放棄處理機，才能得到調(diào)度。本方法適用實時系統(tǒng)?；趦?yōu)先級的

6、隨時搶占式調(diào)度策略基于優(yōu)先級的隨時搶占式調(diào)度策略2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學10第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法q 實時調(diào)度算法分類實時調(diào)度算法分類靜態(tài)表格驅(qū)動類靜態(tài)表格驅(qū)動類v參數(shù)準備參數(shù)準備周期、執(zhí)行時間、周期性結束時限、優(yōu)先級等v基本原理基本原理對可能的調(diào)度條件和參數(shù)進行靜態(tài)分析，并將分析結果作為實際調(diào)度結果。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學11第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法v典型算法典型算法最早時限優(yōu)先法靜態(tài)優(yōu)先級驅(qū)動搶占式調(diào)度算法類靜態(tài)優(yōu)先級驅(qū)動搶占式調(diào)度算法類v典型算法典型算法頻率單調(diào)調(diào)度算法v基

7、本原理基本原理靜態(tài)分析的結果，用來指定任務的優(yōu)先級2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學12第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法動態(tài)計劃調(diào)度算法類動態(tài)計劃調(diào)度算法類v基本原理基本原理在調(diào)度任務執(zhí)行之前排出調(diào)度計劃，并分析計劃的調(diào)度結果是否使得任務所要求的處理時限得到滿足。如能滿足，按計劃執(zhí)行，否則修改計劃。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學13第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法盡力而為調(diào)度算法類盡力而為調(diào)度算法類v基本原理基本原理只對到達的時間和相關任務指定相應的優(yōu)先級，并進行調(diào)度。2021年11月29日星期一23時41分1秒內(nèi)

8、蒙古工業(yè)大學14第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法q 時限調(diào)度算法時限調(diào)度算法時限分類時限分類v處理開始時限（處理開始時限（starting deadline）指任務最晚開始的時刻。v處理結束時限（處理結束時限（ending deadline）指任務最晚結束的時刻。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學15第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法參數(shù)準備參數(shù)準備v任務就緒時間任務就緒時間/事件到達時間事件到達時間指進程進入就緒狀態(tài)，可以被調(diào)度執(zhí)行的時間。對周期性任務是可預知的，對于非周期任務，需要時間驅(qū)動。v開始時限開始時限指處理機必須開始對任務進行處理的

9、最晚時限。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學16第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法v完成時限完成時限指任務必須完成的最后時間v處理時間處理時間任務如果還需要其他資源，則調(diào)度算法較復雜v資源需求資源需求完成相關任務所需占用處理機的時間優(yōu)先級可以計算得到，也可由用戶指定v優(yōu)先級優(yōu)先級2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學17第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法算法基本思想算法基本思想按照用戶的時限要求順序設置優(yōu)先級，優(yōu)先級高者占據(jù)處理機，即時限要求最近的任務優(yōu)先占用處理機。v典型特點典型特點搶占式搶占式把新到達任務的時限和當前正在執(zhí)

10、行任務的時限要求進行比較，系統(tǒng)挑選時限最近的執(zhí)行，即優(yōu)先權最大的2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學18第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法算法實例算法實例實時系統(tǒng)從兩個不同的數(shù)據(jù)源da和db周期性的收集數(shù)據(jù)并進行處理，其中da的時限要求以30ms為周期，db以75ms為周期。設da所需的處理時限為15ms，設db所需的處理時限為38ms，與da和db有關進程的事件如圖所示。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學19第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學20第九講第九講 實時系

11、統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法v調(diào)度結果調(diào)度結果2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學21第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法q 頻率單調(diào)調(diào)度算法頻率單調(diào)調(diào)度算法 基本原理基本原理頻率越低（周期越長）的任務的優(yōu)先級越低。算法的必要條件算法的必要條件c=tc為任務執(zhí)行時間，t為周期2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學22第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法算法的充分條件算法的充分條件 c1 c2 ci cn +=n(21/n-1) t1 t2 ti tn2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學23第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法q 處理機調(diào)度小結處理機調(diào)度小結調(diào)度的分類調(diào)度的分類v作業(yè)調(diào)度作業(yè)調(diào)度調(diào)度目標：盡量做到公平合理，能執(zhí)行盡可能多的作業(yè)，盡快地響應時間和高的設備利用率。調(diào)度算法：fcfs、sjf和hrn。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學24第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)調(diào)度算法v中級調(diào)度中級調(diào)度調(diào)度目標：盡量的騰出較多的內(nèi)存空間，提高系統(tǒng)的并發(fā)率。2021年11月29日星期一23時41分1秒內(nèi)蒙古工業(yè)大學25第九講第九講 實時系統(tǒng)調(diào)度算法實時系統(tǒng)