嵌入式系統(tǒng)中的實(shí)時(shí)調(diào)度課件

嵌入式系統(tǒng)中的實(shí)時(shí)調(diào)度陳虎tommychen74yahoo嵌入式系統(tǒng)中的實(shí)時(shí)調(diào)度陳虎1參考文獻(xiàn)C.M.Krishna,Real-TimeSystems,Mcgraw-Hill,2019參考文獻(xiàn)C.M.Krishna,Real-TimeS2什么是實(shí)時(shí)系統(tǒng) 一般而言具有實(shí)時(shí)性能的控制系統(tǒng)是實(shí)時(shí)系統(tǒng)。實(shí)時(shí)表示一個(gè)非常短的時(shí)間間隔“timegap”（也可以認(rèn)為表示時(shí)間框架“timeframe”或者時(shí)間窗口“timewindow”），具有“立即”之含義。當(dāng)計(jì)算機(jī)進(jìn)行實(shí)時(shí)處理時(shí)，要求在接收到數(shù)據(jù)的同時(shí)執(zhí)行操作并輸出計(jì)算結(jié)果，不能超出計(jì)算機(jī)系統(tǒng)所能容忍的時(shí)限。什么是實(shí)時(shí)系統(tǒng) 一般而言具有實(shí)時(shí)性能的控制系統(tǒng)是實(shí)時(shí)系統(tǒng)。3實(shí)時(shí)系統(tǒng)的定義IEEE（美國(guó)電氣電子工程師協(xié)會(huì)）給出的實(shí)時(shí)系統(tǒng)定義是“那些正確性不僅取決于計(jì)算的邏輯結(jié)果，也取決于產(chǎn)生結(jié)果所花費(fèi)的時(shí)間的系統(tǒng)”。這就是說(shuō)，實(shí)時(shí)系統(tǒng)運(yùn)算能力具有及時(shí)與正確的雙重特征。本教程給出的實(shí)時(shí)系統(tǒng)（Real-TimeSystem）定義是：對(duì)外來(lái)事件能在限定的響應(yīng)時(shí)間內(nèi)做出預(yù)定質(zhì)量處理的計(jì)算機(jī)系統(tǒng)。實(shí)時(shí)系統(tǒng)的定義IEEE（美國(guó)電氣電子工程師協(xié)會(huì)）給出的實(shí)時(shí)系4實(shí)時(shí)系統(tǒng)的主要特點(diǎn)及時(shí)響應(yīng)外部發(fā)生的隨機(jī)任務(wù)請(qǐng)求在規(guī)定的時(shí)間內(nèi)完成任務(wù)任務(wù)執(zhí)行的時(shí)間限制類(lèi)型和類(lèi)型間關(guān)系截止時(shí)間(finishtime) 任務(wù)執(zhí)行預(yù)設(shè)時(shí)間(budgettime)一個(gè)任務(wù)的截止時(shí)間通常大于任務(wù)執(zhí)行預(yù)設(shè)時(shí)間實(shí)時(shí)系統(tǒng)的主要特點(diǎn)及時(shí)響應(yīng)外部發(fā)生的隨機(jī)任務(wù)請(qǐng)求5實(shí)時(shí)系統(tǒng)的關(guān)鍵因素計(jì)算機(jī)系統(tǒng)的實(shí)時(shí)性能主要由操作系統(tǒng)和運(yùn)行在操作系統(tǒng)上的應(yīng)用軟件決定，對(duì)于無(wú)操作系統(tǒng)的計(jì)算機(jī)則由控制程序決定。具有實(shí)時(shí)性能的操作系統(tǒng)稱(chēng)為實(shí)時(shí)操作系統(tǒng)(Real-TimeOperatingSystem,RTOS)實(shí)時(shí)系統(tǒng)的關(guān)鍵因素計(jì)算機(jī)系統(tǒng)的實(shí)時(shí)性能主要由操作系統(tǒng)和運(yùn)行在6實(shí)時(shí)系統(tǒng)與非實(shí)時(shí)系統(tǒng)的例子實(shí)時(shí)系統(tǒng)典型例子民用飛機(jī)的導(dǎo)航系統(tǒng)汽車(chē)的防剎車(chē)抱死系統(tǒng)(ABS)非實(shí)時(shí)系統(tǒng)典型例子銀行數(shù)據(jù)查詢(xún)處理系統(tǒng)視頻播放系統(tǒng)圖像掃描文字識(shí)別系統(tǒng)實(shí)時(shí)系統(tǒng)與非實(shí)時(shí)系統(tǒng)的例子實(shí)時(shí)系統(tǒng)典型例子7提高實(shí)時(shí)性能的因素以下幾種途徑常常用來(lái)提高應(yīng)用系統(tǒng)實(shí)時(shí)性能盡量采用硬件處理優(yōu)化微處理器的中斷機(jī)制采用簡(jiǎn)單的單線(xiàn)程循環(huán)程序采用基于實(shí)時(shí)操作系統(tǒng)的復(fù)雜多線(xiàn)程操作提高實(shí)時(shí)性能的因素以下幾種途徑常常用來(lái)提高應(yīng)用系統(tǒng)實(shí)時(shí)性能8實(shí)時(shí)系統(tǒng)的屬性和指標(biāo)實(shí)時(shí)系統(tǒng)的兩個(gè)基本屬性可預(yù)測(cè)性和可靠性實(shí)時(shí)系統(tǒng)的實(shí)時(shí)性能主要根據(jù)其RTOS的三個(gè)主要指標(biāo)來(lái)衡量響應(yīng)時(shí)間(responsetime)吞吐量(throughput)生存時(shí)間(survivaltime)實(shí)時(shí)系統(tǒng)的屬性和指標(biāo)實(shí)時(shí)系統(tǒng)的兩個(gè)基本屬性9響應(yīng)時(shí)間計(jì)算機(jī)從識(shí)別一個(gè)外部事件到做出響應(yīng)的時(shí)間RTOS響應(yīng)時(shí)間的具體指標(biāo)是：中斷延遲時(shí)間（InterruptLatency）任務(wù)切換時(shí)間（TaskSwitchingLatency）響應(yīng)時(shí)間計(jì)算機(jī)從識(shí)別一個(gè)外部事件到做出響應(yīng)的時(shí)間10響應(yīng)時(shí)間(續(xù))兩個(gè)時(shí)間指標(biāo)的計(jì)算公式是：中斷延遲時(shí)間=TCloseINT+TDoISR+TSaveReg+TStartService TCloseINT

：關(guān)中斷的最長(zhǎng)時(shí)間

TDoISR：開(kāi)始執(zhí)行中斷服務(wù)子程序的第一條指令的時(shí)間

TSaveReg：保存CPU內(nèi)部寄存器的時(shí)間

TStartService：內(nèi)核進(jìn)入中斷服務(wù)函數(shù)的執(zhí)行時(shí)間任務(wù)切換時(shí)間：TtoDoBTaskTime–TtoPauseATaskTime TtoDoBTaskTime：開(kāi)始執(zhí)行B任務(wù)的時(shí)刻

TtoPauseATask

：暫停執(zhí)行A任務(wù)的時(shí)刻響應(yīng)時(shí)間(續(xù))兩個(gè)時(shí)間指標(biāo)的計(jì)算公式是：11響應(yīng)時(shí)間(續(xù))任務(wù)的切換時(shí)間就是CPU從停止一個(gè)任務(wù)的執(zhí)行切換到另一個(gè)任務(wù)所需時(shí)間VxWorks是實(shí)時(shí)嵌入式系統(tǒng)，內(nèi)核為Wind。下表給出了eCos操作系統(tǒng)內(nèi)核實(shí)時(shí)響應(yīng)時(shí)間參考數(shù)據(jù)硬件測(cè)試環(huán)境中斷延遲時(shí)間任務(wù)切換時(shí)間ARM7TDMI（20MHz）22.10ms49.14msStrongARM（221.2MHz）3.25ms1.85msIntelXcale（600MHz）1.87ms0.87ms響應(yīng)時(shí)間(續(xù))任務(wù)的切換時(shí)間就是CPU從停止一個(gè)任務(wù)的執(zhí)行切12實(shí)時(shí)系統(tǒng)的分類(lèi)根據(jù)響應(yīng)性能分硬實(shí)時(shí)系統(tǒng) 系統(tǒng)未能在時(shí)限內(nèi)就某一事件做出響應(yīng)而失敗，并且該失敗被認(rèn)為是一種全面的系統(tǒng)失敗，則可以認(rèn)為該系統(tǒng)是一個(gè)硬實(shí)時(shí)（hardreal-time）系統(tǒng)。軟實(shí)時(shí)系統(tǒng) 非硬實(shí)時(shí)的實(shí)時(shí)系統(tǒng)可以歸類(lèi)為軟實(shí)時(shí)系統(tǒng)。在一個(gè)軟實(shí)時(shí)（softreal-time）系統(tǒng)中，存在時(shí)限指標(biāo)，但是如果輸出響應(yīng)超過(guò)時(shí)限，一般不會(huì)造成嚴(yán)重后果。實(shí)時(shí)系統(tǒng)的分類(lèi)根據(jù)響應(yīng)性能分13硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)時(shí)限效益硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)時(shí)限效益14實(shí)時(shí)系統(tǒng)的分類(lèi)(續(xù))按照響應(yīng)時(shí)間的快慢分類(lèi)：強(qiáng)實(shí)時(shí)系統(tǒng)：其響應(yīng)時(shí)間在毫秒級(jí)或微秒級(jí)普通實(shí)時(shí)系統(tǒng)：其響應(yīng)時(shí)間一般幾秒弱實(shí)時(shí)系統(tǒng)：其響應(yīng)時(shí)間一般在數(shù)十秒實(shí)時(shí)系統(tǒng)的分類(lèi)(續(xù))按照響應(yīng)時(shí)間的快慢分類(lèi)：15一個(gè)例子——汽車(chē)自動(dòng)駕駛V：汽車(chē)速度S：汽車(chē)發(fā)現(xiàn)紅燈時(shí)的距離VSSminSmin：最小剎車(chē)距離求從發(fā)現(xiàn)紅燈信號(hào)到開(kāi)始剎車(chē)的最大響應(yīng)時(shí)間D一個(gè)例子——汽車(chē)自動(dòng)駕駛V：汽車(chē)速度VSSminSmin：最16實(shí)時(shí)系統(tǒng)中的任務(wù)模型周期性實(shí)時(shí)系統(tǒng)系統(tǒng)中任務(wù)數(shù)目固定——N每個(gè)任務(wù)必須按照一定的周期執(zhí)行——Pi每個(gè)任務(wù)的執(zhí)行時(shí)間固定——ei處理器器利用率非周期性實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)中的任務(wù)模型周期性實(shí)時(shí)系統(tǒng)17周期性實(shí)時(shí)系統(tǒng)的例子兩個(gè)任務(wù)T1和T2T1的周期為10ms，執(zhí)行時(shí)間為3msT2的周期為6ms，執(zhí)行時(shí)間為1ms任務(wù)T1任務(wù)T2306121824301020CPU上的執(zhí)行過(guò)程起始時(shí)間完成時(shí)間(Deadline)任務(wù)的執(zhí)行周期性實(shí)時(shí)系統(tǒng)的例子兩個(gè)任務(wù)T1和T2任務(wù)T1任務(wù)T230618實(shí)時(shí)系統(tǒng)調(diào)度靜態(tài)表驅(qū)動(dòng)在系統(tǒng)開(kāi)始時(shí)就已經(jīng)確定了所有任務(wù)的實(shí)行時(shí)間靜態(tài)優(yōu)先級(jí)——可剝奪式每個(gè)任務(wù)有固定的優(yōu)先級(jí)當(dāng)優(yōu)先級(jí)高的任務(wù)需要執(zhí)行時(shí)，可以打斷當(dāng)前正在執(zhí)行的低優(yōu)先級(jí)任務(wù)動(dòng)態(tài)優(yōu)先級(jí)每個(gè)任務(wù)的優(yōu)先級(jí)可以動(dòng)態(tài)變化實(shí)時(shí)系統(tǒng)調(diào)度靜態(tài)表驅(qū)動(dòng)19周期性實(shí)時(shí)任務(wù)調(diào)度的基本結(jié)構(gòu)就緒<->執(zhí)行如果當(dāng)前有新的任務(wù)就緒，則比較正在執(zhí)行任務(wù)和新任務(wù)的優(yōu)先級(jí)，選擇優(yōu)先級(jí)高的任務(wù)執(zhí)行，低優(yōu)先級(jí)任務(wù)回到就緒狀態(tài)。執(zhí)行->休眠當(dāng)前周期性任務(wù)執(zhí)行結(jié)束，根據(jù)下一個(gè)周期開(kāi)始時(shí)間確定休眠時(shí)間，啟動(dòng)定時(shí)器休眠->執(zhí)行當(dāng)休眠定時(shí)器時(shí)間到，將到時(shí)的任務(wù)加入到就緒任務(wù)隊(duì)列中，并進(jìn)行優(yōu)先級(jí)選擇。周期性實(shí)時(shí)任務(wù)調(diào)度的基本結(jié)構(gòu)就緒<->執(zhí)行20單調(diào)速率調(diào)度(RateMonotonic,RM)靜態(tài)優(yōu)先級(jí)可剝奪策略每個(gè)任務(wù)的優(yōu)先級(jí)取決于起任務(wù)執(zhí)行周期周期越短的任務(wù)優(yōu)先級(jí)越高單調(diào)速率調(diào)度(RateMonotonic,RM)靜態(tài)優(yōu)先21RM算法的例子PeTask120.5Task262.0Task3102.0三個(gè)任務(wù)的參數(shù)問(wèn)題1：誰(shuí)的優(yōu)先級(jí)最高？問(wèn)題2：CPU的運(yùn)行圖？012345678T1T2T1T1T1T2T3T3Task1,2,3Task1,2,3Task1,3Task1，2T2Task2,3Task2,3Task3Task3Task2RM算法的例子PeTask120.5Task262.0Tas22RM算法的基本結(jié)論RM算法是一個(gè)最優(yōu)的靜態(tài)調(diào)度策略如果有其它靜態(tài)調(diào)度策略可以完成一個(gè)任務(wù)集合的調(diào)度，則RM算法也可以完成如果有兩個(gè)任務(wù)，其執(zhí)行時(shí)間分別為e1,e2,執(zhí)行周期分別為P1,P2，如果滿(mǎn)足則這兩個(gè)任務(wù)是RM算法可以調(diào)度的如果有N個(gè)任務(wù)，其執(zhí)行時(shí)間分別為e1,e2,…,eN

執(zhí)行周期分別為P1,P2,…,PN,如果滿(mǎn)足則這N個(gè)任務(wù)是RM算法可以調(diào)度的RM算法的基本結(jié)論RM算法是一個(gè)最優(yōu)的靜態(tài)調(diào)度策略23問(wèn)題PeTask131Task242Task361下述兩個(gè)任務(wù)集合是否是RM可調(diào)度的，如果是請(qǐng)完成10ms內(nèi)的調(diào)度過(guò)程，如果不是請(qǐng)說(shuō)明理由處理器利用率小于多少時(shí)，RM算法總是可以調(diào)度的？PeTask131Task2102Task3102問(wèn)題PeTask131Task242Task361下述兩個(gè)任24EarlierDeadlineFirst(EDF)調(diào)度策略可剝奪的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度策略任務(wù)的優(yōu)先級(jí)取決于它的Deadline離Deadline越近的任務(wù)優(yōu)先級(jí)越高EarlierDeadlineFirst(EDF)調(diào)25EDF算法的例子到達(dá)時(shí)間執(zhí)行時(shí)間DeadlineTask101030Task24310Task358253個(gè)非周期任務(wù)0246810121416T1T2T3Task2Task3Task1T1EDF算法的例子到達(dá)時(shí)間執(zhí)行時(shí)間DeadlineTask1026EDF的基本結(jié)論EDF算法是一個(gè)優(yōu)化的單處理器調(diào)度算法如果有一個(gè)動(dòng)態(tài)調(diào)度算法能完成實(shí)時(shí)調(diào)度，則EDF算法必然可以如果EDF算法不能完成一個(gè)任務(wù)集合的實(shí)時(shí)調(diào)度，則不存在其它的動(dòng)態(tài)調(diào)度算法來(lái)完成實(shí)時(shí)調(diào)度。在周期性實(shí)時(shí)系統(tǒng)中，如果每個(gè)任務(wù)的相對(duì)Deadline都等于其周期，則只要總的處理器利用率小于1，EDF算法都可以調(diào)度。EDF的基本結(jié)論EDF算法是一個(gè)優(yōu)化的單處理器調(diào)度算法27RM和EDF比較考慮以下任務(wù)集合，可以使用RM調(diào)度嗎？可以使用EDF調(diào)度嗎？如果可以請(qǐng)畫(huà)出12個(gè)時(shí)間單位的任務(wù)調(diào)度圖。PeTask131Task242Task361RM和EDF比較考慮以下任務(wù)集合，可以使用RM調(diào)度嗎？可以使28優(yōu)先級(jí)反轉(zhuǎn)在多任務(wù)系統(tǒng)中，可能出現(xiàn)高優(yōu)先級(jí)任務(wù)等待低優(yōu)先級(jí)任務(wù)的情況！T1等待T2優(yōu)先級(jí)反轉(zhuǎn)在多任務(wù)系統(tǒng)中，可能出現(xiàn)高優(yōu)先級(jí)任務(wù)等待低優(yōu)先級(jí)任29優(yōu)先級(jí)繼承如果有高優(yōu)先級(jí)任務(wù)等待低優(yōu)先級(jí)任務(wù)的資源，則低優(yōu)先級(jí)任務(wù)可以暫時(shí)獲得高優(yōu)先級(jí)優(yōu)先級(jí)繼承如果有高優(yōu)先級(jí)任務(wù)等待低優(yōu)先級(jí)任務(wù)的資源，則低優(yōu)先30RM算法特征的證明如果有兩個(gè)任務(wù)T1,T2，其執(zhí)行時(shí)間分別為e1,e2,執(zhí)行周期分別為P1,P2，如果滿(mǎn)足則這兩個(gè)任務(wù)是可以調(diào)度的RM算法特征的證明如果有兩個(gè)任務(wù)T1,T2，其執(zhí)行時(shí)間分別31Case1T1T1T1T1T2T2T20P12P1P2<=0Case1T1T1T1T1T2T2T2032Case2T1T1T1T1T2T2T20P12P1P20