嵌入式實(shí)時操作系統(tǒng)中實(shí)時調(diào)度算法綜述

1、嵌入式實(shí)時操作系統(tǒng)中實(shí)時調(diào)度算法綜述摘要：實(shí)時調(diào)度是指在有限的系統(tǒng)資源下，為一系列任務(wù)決定何時運(yùn)行， 并分配任務(wù)運(yùn)行除CPU之外的資源，以保證其時間約束、時序約束和資源約束得到滿足。一個實(shí)時系統(tǒng)可以由單處理器系統(tǒng)來實(shí)現(xiàn)，也可以用多處理器系統(tǒng)來實(shí)現(xiàn)。實(shí)時調(diào)度算法是保障實(shí)時系統(tǒng)時限性和高可靠性的最重要手段之一。 關(guān)鍵詞：嵌入式；實(shí)時操作系統(tǒng)；實(shí)時調(diào)度算法；RTOS；RMS引言嵌入式系統(tǒng)在當(dāng)今的生產(chǎn)和生活中得到了廣泛的應(yīng)用,鑒于嵌入式實(shí)時系統(tǒng)的特點(diǎn),要求任務(wù)調(diào)度等實(shí)時內(nèi)核功能精簡和高效。綜合了EDF 和RM調(diào)度策略的CSD 調(diào)度策略,更加適合嵌入式系統(tǒng)的特點(diǎn),滿足其內(nèi)核的要求。任務(wù)調(diào)度策略是實(shí)時系統(tǒng)

2、內(nèi)核的關(guān)鍵部分,如何進(jìn)行任務(wù)調(diào)度,使得各個任務(wù)能在其期限之內(nèi)得以完成是實(shí)時操作系統(tǒng)的一個重要的研究領(lǐng)域。它的精簡和高效,對提高低處理能力,小內(nèi)存系統(tǒng)整體性能具有重大的意義。 RTOS概述RTOS，即：實(shí)時系統(tǒng)（Real-time operating system），實(shí)時系統(tǒng)能夠在指定或者確定的時間內(nèi)完成系統(tǒng)功能和外部或內(nèi)部、同步或異步時間做出響應(yīng)的系統(tǒng)。它的正確性不僅依賴系統(tǒng)計(jì)算的邏輯結(jié)果，還依賴于產(chǎn)生這個結(jié)果的時間。因此實(shí)時系統(tǒng)應(yīng)該在事先先定義的時間范圍內(nèi)識別和處理離散事件的能力；系統(tǒng)能夠處理和儲存控制系統(tǒng)所需要的大量數(shù)據(jù)。對一般的程序來說，大多數(shù)是考慮指令執(zhí)行的邏輯順序，指令何時執(zhí)行并不重

3、要。而對實(shí)時應(yīng)用系統(tǒng)的程序就不一樣，當(dāng)外部某激勵出現(xiàn)時，系統(tǒng)必須以一定的方式和在限定的時間內(nèi)響應(yīng)它，如果已超時，那怕執(zhí)行結(jié)果是正確的，系統(tǒng)也認(rèn)為是失效的。實(shí)時操作系統(tǒng)通常被分為軟實(shí)時操作系統(tǒng)和硬實(shí)時操作系統(tǒng)。前者意味著偶爾錯過時限是可以容忍的；后者意味著執(zhí)行過程不但必須正確而且必須準(zhǔn)時。在實(shí)時操作系統(tǒng)中，系統(tǒng)將程序分成許多任務(wù)(或進(jìn)程)，而每個任務(wù)的行為都預(yù)先可知，或者是有明確的功能，系統(tǒng)根據(jù)一定的調(diào)度原則，決定誰可取得執(zhí)行權(quán)，這就是RTOS的核心所在。實(shí)時調(diào)度算法實(shí)時調(diào)度算法可以分為4類：單處理器靜態(tài)調(diào)度算法、多處理器靜態(tài)調(diào)度算法、單處理器動態(tài)調(diào)度算法、多處理器動態(tài)調(diào)度算法。下面分別分析嵌入

4、式操作系統(tǒng)中采用的各種調(diào)度方法，以及這些調(diào)度方法是如何滿足實(shí)時性應(yīng)用的實(shí)時要求的。1 速率單調(diào)算法 速率單調(diào)算法是一個經(jīng)典的算法，它是針對那些響應(yīng)和處理周期性事件的實(shí)時任務(wù)的，它事先為每個這樣的實(shí)時任務(wù)分配一個與事件頻率成正比的優(yōu)先級。 實(shí)現(xiàn)時，就緒隊(duì)列中的所有任務(wù)按照優(yōu)先級Priority排隊(duì)，優(yōu)先級最高的任務(wù)排在隊(duì)首，當(dāng)處于運(yùn)行態(tài)的任務(wù)，由于某種原因掛起時，只要把就緒隊(duì)列的首元素從就緒隊(duì)列中取下，使運(yùn)行任務(wù)指針pRunTask指向該元素即可，如果是處于其他狀態(tài)的任務(wù)變?yōu)榫途w狀態(tài)，而掛于就緒隊(duì)列時，則必須對運(yùn)行任務(wù)和就緒隊(duì)列首元素的任務(wù)進(jìn)行比較，優(yōu)先級高的任務(wù)占有。2 截止期最早優(yōu)先算法 截

5、止期最早的任務(wù)優(yōu)先級最高，對于周期任務(wù)，其截止期即為下一周期開始的時間，有時，把這種算法稱為期限驅(qū)動算法，就緒隊(duì)列中的任務(wù)，按截止期排序，截止期早的任務(wù)排在隊(duì)首，這個算法的處理，與速率單調(diào)算法類似，不同的是，現(xiàn)在是對截止期進(jìn)行判斷，按截止期最早優(yōu)先策略處理。3 可達(dá)截止期最早優(yōu)先算法 這個算法是對截止期最早優(yōu)先策略的改進(jìn)，就緒隊(duì)列的任務(wù)，仍然按照截止期順序排隊(duì)，但是在調(diào)度時超過截止期的不予調(diào)度，如果記為t為系統(tǒng)當(dāng)前時間，為任務(wù)估算執(zhí)行時間，p為任務(wù)實(shí)際執(zhí)行時間，d為截止期。則 表示該任務(wù)的截止期是當(dāng)前可達(dá)到的，于是，只要在調(diào)度時，按照上式計(jì)算被調(diào)度就緒任務(wù)的d1，若大于，就進(jìn)行調(diào)度，否則，就夭

6、折它。 這種算法里，系統(tǒng)時鐘管理部分中的時鐘滴答中斷處理程序，必須對運(yùn)行任務(wù)的運(yùn)行時間進(jìn)行累計(jì)?？臻e任務(wù)IDLE的截止期DeadTime應(yīng)置為無限大，而估算時間PredictedTiem可為0，從而在進(jìn)行任務(wù)調(diào)度時，可以保證就緒隊(duì)列中至少有一個就緒任務(wù)，滿足調(diào)度要求。4 最小裕度算法 在上述算法中，優(yōu)先性由截止期時間的早晚而定，可能使一些不可達(dá)截止期的任務(wù)，因來不及處理而夭折，另外一種算法是：計(jì)算任務(wù)的富裕時間，稱為裕度，裕度小的，優(yōu)先級高，以彌補(bǔ)上述情況的不足。在這種算法里，時鐘的滴答中斷，不但要累計(jì)運(yùn)行任務(wù)的執(zhí)行時間，還要對就緒隊(duì)列上的任務(wù)的裕度進(jìn)行累減，實(shí)際上(3.1)式中的d1，便是這

7、里所謂的裕度，由于正在運(yùn)行的任務(wù)，其裕度不變，而就緒隊(duì)列上的任務(wù)，其裕度隨著時間的推移而減少，從而使得它們的優(yōu)先權(quán)，動態(tài)地發(fā)生變化。5 其他的實(shí)時調(diào)度算法1、價值最高優(yōu)先算法在這種算法里,每一個任務(wù)有一個價值函數(shù),價值最大，優(yōu)先級最高。2、價值比最大優(yōu)先算法在這種算法里，定義一個價值比函數(shù)：其中，v為類似上面所定義的價值函數(shù)，t為當(dāng)前時間，E為估算執(zhí)行時間，p為已執(zhí)行時間。這時，VD值越大，優(yōu)先級越高。下面具體介紹單調(diào)速率算法：單調(diào)速率調(diào)度算法RMS（Rate Monotonic Scheduling）為每個周期進(jìn)程指定一個固定不變的優(yōu)先級，周期最短的進(jìn)程優(yōu)先級最高。周期越短，進(jìn)程的到達(dá)頻率越

8、高，優(yōu)先級也越高，這正是此策略被稱為速率單調(diào)算法的原因。RMS算法也可用于多CPU環(huán)境,用于分配任務(wù)優(yōu)先級。這種方法基于哪個任務(wù)執(zhí)行的次數(shù)最頻繁，執(zhí)行最頻繁的任務(wù)優(yōu)先級最高。RMS的由來是從硬實(shí)時環(huán)境的初始定義開始的：1,所有的任務(wù)都是周期性的，各個任務(wù)請求的deadline呈周期性，同時具有恒定的時間間隔；2,所有任務(wù)都必須在下一次任務(wù)請求（即deadline）到來之前完成；3,所有的任務(wù)都是獨(dú)立的，每一次任務(wù)請求不依賴于其他任務(wù)的執(zhí)行或者初始化；4,每個任務(wù)都存在一個恒定且非時變的執(zhí)行時間，即CPU不間斷地執(zhí)行該任務(wù)的時間；5,任何非周期的任務(wù)屬于特殊任務(wù)，它們屬于初始化或者是恢復(fù)錯誤的事

9、件，僅當(dāng)它們自身執(zhí)行的時候才能取代周期性任務(wù)，同時非周期性任務(wù)不存在有deadline.RMS算法的實(shí)現(xiàn)(C+模板元程序?qū)崿F(xiàn)示例)1，聲明任務(wù)my_task的結(jié)構(gòu)體變量：struct my_task enum cost = 100,period = 600,phasing = 50,droppable = 0,importance = 1000 ;static void do_task(const context& c) cout << "my_task:do_task()" << endl;period表示任務(wù)的響應(yīng)周期；phasing 表

10、示任務(wù)的邏輯定向；droppable 為布爾變量，表示是否該任務(wù)可以被掛起以保證其之后可以被調(diào)度；importance為整形變量，具體指定了CPU執(zhí)行該任務(wù)的情愿度，具有低importance在執(zhí)行較高優(yōu)先級的任務(wù)之前被掛起；do_task 為功能性函子，具體指定即將被執(zhí)行的具體任務(wù)；2， 使用RMA_Feasible函數(shù)（已被Schedule函數(shù)調(diào)用）循環(huán)查詢判斷任務(wù)是否可以被調(diào)度template <class TL, int m, int i>struct check_i;template <class Head, class Tail, int m, int i>

11、struct check_i<Typelist<Head, Tail>, m, i> enum task_result =task_feasible<Typelist<Head,Tail>,i>:Result,Result = check_i<Typelist<Head,Tail>,m,i+1>:Result&& task_result ; ;template <class Head, class Tail, int m>struct check_i<Typelist<Head, T

12、ail>, m, m> enum Result = task_feasible<Typelist<Head,Tail>,m>:Result ;template <class TaskSet>struct RMA_Feasible enum m = Length<TaskSet>:value,Result = check_i<TaskSet, m, 1>:Result ;3，判斷可調(diào)度的充要條件不等式3)是否成立(核心算法實(shí)現(xiàn))template <class TL, int i, int t, int j = 0>

13、;struct sum_j /初始化結(jié)構(gòu)體變量sum_j，表示j=1iCjtTjtypedef typename TypeAt<TL, j>:Result J;enum Cj = J:cost, /定義Cj為任務(wù)的開銷,即CPU執(zhí)行時間Tj = J:period, /定義Tj為任務(wù)的執(zhí)行周期my_result = Cj * (t%Tj > 0 ? 1 : 0) + (t / Tj),/定義my_result為 CjtTj Result = sum_j<TL,i,t,j+1>:Result + my_result ; / 迭代求出 j=1iCjtTj 的值，存入Re

14、sult變量中template <class TL, int i, int t_ix, int k=0>struct get_t / 計(jì)算t值enum Ti = TypeAt<TL,i-1>:Result:period,Tk = TypeAt<TL,k>:Result:period,/分別讀取任務(wù)i-1,k的周期，并存入Ti,Tk變量num_l = Ti/Tk,Result = (t_ix >= num_l) ? get_t<TL, i, t_ix - num_l, k+1>:Result : (t_ix + 1) * Tk ;/判斷l(xiāng)是否

15、取到了可能的最大值，若是則求出t的值，否則t_ix減去num_l，再判斷下一個k是否能使l取到最大值template <class TL, int i, int t_ix = 0>struct task_feasible typedef get_t<TL, i, t_ix> t_type;enum t = t_type:Result,Result = (t > 0) && ( sum_j<TL, i, t>:Result <= t| task_feasible<TL, i, t_ix + 1>:Result ) ; /

16、判斷該任務(wù)是否滿足不等式2，即是否sum_j<=t，返回Result4，算法查錯RMS算法在查錯的時候，使用的C+的庫的宏定義STATISTIC_CHECK，我們就能很容易地使特定的任務(wù)在聲明的時候都是可行的。typedef Schedule<TYPELIST_2(taskA, taskB)>my_schedule;STATIC_CHECK(my_schedule:feasible,Schedule_Infeasible);Schedule_Infeasible宏定義定義的為字符串，通過編譯器輸出顯示錯誤聲明和提示： Loki:CompileTimeError<0>

17、; ERROR_Schedule_Infeasible has incomplete type and cannot be defined將STATIC_CHECK宏定義放在Schedule:schedule()函數(shù)中，可以確保在CPU運(yùn)行的時間調(diào)度任務(wù)都是可行的。硬件初始化操作系統(tǒng)初始化各任務(wù)參數(shù)初始化含Ci,Ti算法實(shí)現(xiàn)的流程圖： STATIC_CHECK是否有誤? Y N比較優(yōu)先級并且排序 任務(wù)集是否可調(diào)度 掛起 N Y生成代碼并執(zhí)行任務(wù)查詢?nèi)蝿?wù)集中各個任務(wù)的可調(diào)度性和CPU使用率 總而言之，算法實(shí)現(xiàn)的核心在于RMA分析（Rate Monotonic Analysis），通過對每個任務(wù)實(shí)

18、現(xiàn)不等式3）的判定，對已知就緒的優(yōu)先級最高的任務(wù)查詢來它確定是否可以調(diào)度，從而實(shí)現(xiàn)算法。此算法優(yōu)缺點(diǎn)分析：優(yōu)點(diǎn)：1，RMS算法在靜態(tài)調(diào)度中屬于最優(yōu)算法，任意的固定優(yōu)先級算法能夠?qū)崿F(xiàn)的調(diào)度，在RMS算法中也能實(shí)現(xiàn)。盡管RMS算法的CPU利用率最小上確界為0.693，實(shí)際上的平均CPU利用率可達(dá)0.88。2，RMS算法可在運(yùn)行前“離線”確定周期進(jìn)程的執(zhí)行順序，運(yùn)行時不必保留很多信息，同時可調(diào)度件測試簡單，因此易于實(shí)現(xiàn)，運(yùn)行時的調(diào)度開銷相對較小，這是靜態(tài)優(yōu)先級調(diào)度算法對動態(tài)優(yōu)先級調(diào)度算法的普遍優(yōu)勢。3，另外，優(yōu)先級的預(yù)先確定也使系統(tǒng)過載的現(xiàn)象比較好控制。即使系統(tǒng)出現(xiàn)了暫時的過載，也能夠確保最重要的任

19、務(wù)的調(diào)度需求。4，在滿足周期性任務(wù)的同時，仍有余力（約30%左右的CPU使用率）致力于對非周期性任務(wù)（例如系統(tǒng)和參數(shù)的初始化，錯誤處理）快速響應(yīng)。同時支持?jǐn)U展和固件升級，這對消費(fèi)類產(chǎn)品而言意義重大。缺點(diǎn)：1，它的潛在CPU利用率小于動態(tài)優(yōu)先級策略，在動態(tài)優(yōu)先級的最優(yōu)算法EDF(Earliest Deadline First)中最壞情況下的可調(diào)度CPU使用率為1.000。2，執(zhí)行頻率最高的任務(wù)并非最重要的任務(wù)。且較長周期的任務(wù)相對于較短周期的任務(wù)，更加容易錯過deadline。3，由于RMS算法的靜態(tài)調(diào)度屬性，它運(yùn)行時靈活性較差，自適應(yīng)性弱?，F(xiàn)今常用的實(shí)時性的操作任務(wù)，常常具有較靈活的使用率需求，但同時具有嚴(yán)格RMS算法完全建立在硬實(shí)時的條件下，主張所有被調(diào)度的周期性任務(wù)具有固定的優(yōu)先級，這就顯得強(qiáng)調(diào)在deadline之前的必須完成任務(wù)的思想超出了必要限度。具體而言，在特殊場合，一些任務(wù)的deadline是可以被錯過的，只要在deadline前完成任務(wù)的要求能在一定百分率下得到滿足。這種高靈活性使得RMS的最小上 界理論毫無提出之必要了。具體而言，在實(shí)時多媒體應(yīng)用的調(diào)度之中，特點(diǎn)經(jīng)常是：a，單個應(yīng)用的執(zhí)行次數(shù)常常是不定的；b，錯過deadline盡管是不愿意出現(xiàn)的情況，但它確實(shí)是非致命的錯誤，這樣在實(shí)時多媒