當(dāng)前位置:首頁 > 單片機(jī) > 單片機(jī)
[導(dǎo)讀]0引言嵌入式實(shí)時(shí)系統(tǒng)由于自身CPU計(jì)算能力較弱和內(nèi)存容量較低的原因,希望采用復(fù)雜度低、系統(tǒng)開銷小的調(diào)度算法。目前的實(shí)時(shí)系統(tǒng)通常采用單優(yōu)先級驅(qū)動(dòng)的搶占式調(diào)度算法,根據(jù)任務(wù)的某一時(shí)間特性參數(shù)如任務(wù)周期或最后截

0引言

嵌入式實(shí)時(shí)系統(tǒng)由于自身CPU計(jì)算能力較弱和內(nèi)存容量較低的原因,希望采用復(fù)雜度低、系統(tǒng)開銷小的調(diào)度算法。目前的實(shí)時(shí)系統(tǒng)通常采用單優(yōu)先級驅(qū)動(dòng)的搶占式調(diào)度算法,根據(jù)任務(wù)的某一時(shí)間特性參數(shù)如任務(wù)周期或最后截止期等為各個(gè)任務(wù)分配系統(tǒng)資源[1][2]。這種搶占式調(diào)度策略具有靈活性和動(dòng)態(tài)性等優(yōu)點(diǎn)。但在,實(shí)際應(yīng)用系統(tǒng)中也有一些由不相交的周期任務(wù)子集組成,每個(gè)子集是系統(tǒng)的一個(gè)主要部分,稱之為子系統(tǒng)。例如,飛行管理系統(tǒng)包含飛行控制,電子設(shè)備和導(dǎo)航式三個(gè)子系統(tǒng)。這三個(gè)子系統(tǒng)的任務(wù)如果按照以前的靜態(tài)、動(dòng)態(tài)算法實(shí)現(xiàn)需要系統(tǒng)開發(fā)人員設(shè)計(jì)很復(fù)雜的調(diào)度算法,實(shí)時(shí)控制也相對困難[3][4]。本文按照分層思想在實(shí)時(shí)操作系統(tǒng)層面上設(shè)計(jì)調(diào)度算法,減輕了解決此類問題系統(tǒng)開發(fā)人員的負(fù)擔(dān),算法的主要思想是:修改內(nèi)核的任務(wù)控制塊,增加一個(gè)子模塊標(biāo)識來控制分層調(diào)度,采用固

定時(shí)間輪轉(zhuǎn)算法調(diào)度各子系統(tǒng)模塊,子系統(tǒng)中的任務(wù)按照速率單調(diào)算法調(diào)度,從而實(shí)現(xiàn)兩層的調(diào)度策略。本文首先定義了分層調(diào)度系統(tǒng)的模型,并對分層調(diào)度算法的可調(diào)度性進(jìn)行了理論分析;其次,以實(shí)時(shí)內(nèi)核μC/OS-Ⅱ?yàn)楸尘埃瑢?shí)現(xiàn)了具有分層調(diào)度功能的調(diào)度器,最后通過實(shí)驗(yàn)驗(yàn)證分層調(diào)度算法的可行性和正確性。

1 分層調(diào)度系統(tǒng)模型的定義

定義1 在不考慮釋放抖動(dòng)的情況下,一個(gè)任務(wù)集Τ={τ1,τ2,…, τn}中的任務(wù)τi 的屬性可以用一個(gè)五元組(Mi, ,Pi,Di, Ei)來表示。其中,Mi 表示任務(wù)屬于的模塊; 是相位;Pi 表示任務(wù)周期,對于非周期任務(wù),取其最小時(shí)間間隔作為周期;Di 表示任務(wù)完成

的最后期限;Ei 表示任務(wù)的最大請求運(yùn)行時(shí)間。

在定義任務(wù)屬性時(shí),擴(kuò)展以前任務(wù)描述的四元組到五元組[5],增加了任務(wù)所屬模塊的屬性,這一點(diǎn)是為了給子模塊的索引表提供一個(gè)標(biāo)志,以便實(shí)現(xiàn)任務(wù)集按子模塊分層調(diào)度管理。

定義2 對于任務(wù)τi,其各實(shí)例從到達(dá)時(shí)刻至執(zhí)行完成時(shí)刻之間的時(shí)間間隔稱為該實(shí)例的響應(yīng)時(shí)間,各實(shí)例響應(yīng)時(shí)間的最大值稱為任務(wù)τi的最大響應(yīng)時(shí)間 Ri,若 Ri≤Di,則稱任務(wù)τi可調(diào)度。

2 分層調(diào)度算法模型的實(shí)現(xiàn)

2.1分層模型的可調(diào)度性分析

假定:系統(tǒng)中具有n個(gè)獨(dú)立的,可搶占的任務(wù),并且任務(wù)的相對時(shí)限等于各自的周期。如果系統(tǒng)的總利用率U滿足下式:

(該子系統(tǒng)模塊1中的任務(wù)在最壞的情況下,完成任務(wù)的時(shí)間分別為:
R11=RL-1+E1=2+0.5=2.5
R12=2*RL-1-(1-E1)+E2=5-0.5+1.2=5.7
R13=3*RL-1-(2-E1-E2)+E3+E1=9-1-0.3+0.8-0.5=9

而按照分層模型可調(diào)度性公式(2.2a)迭代計(jì)算可知Rij最大響應(yīng)時(shí)間分別如下:

R11(max):初始預(yù)設(shè)值為t(1)=0.5(即任務(wù)的執(zhí)行時(shí)間),用該值替代t,發(fā)現(xiàn)公式(2.2a)左邊等于0.5,但右邊為0,不滿足公式(2.2a),第二次迭代中,t(2)= =3,經(jīng)計(jì)算發(fā)現(xiàn)針對該t值,公式(2.2a)成立,因此T11的最大響應(yīng)時(shí)間為3,依次可計(jì)算第一個(gè)子模塊中其它兩個(gè)任務(wù)的最大響應(yīng)時(shí)間分別為 R12(max)=6,R13(max)=9。

由此可知系統(tǒng)在分層調(diào)度情況下,子模塊M1中的任務(wù)最壞情況下的調(diào)度能在最大響應(yīng)時(shí)間內(nèi)運(yùn)行完畢。同理,對其它2個(gè)模塊中的任務(wù)逐個(gè)檢驗(yàn)它的可調(diào)度條件,可判別出子系統(tǒng)模塊中的任務(wù)在最壞情況下的調(diào)度能滿足最大響應(yīng)時(shí)間的要求,從而保證分層情況下任務(wù)的可調(diào)度性。

2.2 實(shí)現(xiàn)分層調(diào)度的μC/OS-Ⅱ內(nèi)核結(jié)構(gòu)修改和擴(kuò)展

為了實(shí)現(xiàn)分層調(diào)度,需要修改和擴(kuò)展μC/OS-Ⅱ內(nèi)核結(jié)構(gòu)。創(chuàng)建一個(gè)模塊控制塊MCB,以此作為模塊標(biāo)識,將屬于同一模塊的任務(wù)TCB掛在同一模塊任務(wù)鏈上,在調(diào)度過程中,子模塊按固定時(shí)間輪轉(zhuǎn)調(diào)度,子模塊中任務(wù)的調(diào)度仍然保持μC/OS-Ⅱ按優(yōu)先級的搶占式調(diào)度策略按RM調(diào)度算法進(jìn)行。為實(shí)現(xiàn)分層任務(wù)的級聯(lián)查找,需要?jiǎng)?chuàng)建兩級索引表,一級指向子模塊,另一級索引子模塊中的任務(wù),原內(nèi)核結(jié)構(gòu)如圖2所示,改進(jìn)后的內(nèi)核結(jié)構(gòu)如圖3所示。

具體的調(diào)度算法如下 :
OS_Layered_Sched(){
OSMCBRdy = "Get a ready submode";/* 控制塊就緒指針指向一個(gè)子模塊*/
if ( OSMCBGetCycle_Piece = =ture ) {/*子模塊得到固定時(shí)間分配。*/
if (MCBTb[].TaskTcb[].Rdy==ture) /*查看其中是否有就緒的任務(wù),如果有,則調(diào)度*/
{OS_ENTER_CRITICAL();
OS_PRIOCYCLE_RDY =(INT8U)(z+(y<<3+)+OS_UnMapTb1[OSRdyTb1[y]];
 /* z是用來確定模塊的地址*/     OS_sched(); 
OS_EXIT_CRITICAL()}
else {
   if( MCBTb!= MCBTb[n]) /*判斷是否到了最后一個(gè)子模塊*/
{ MCBTb= MCBTb->next;  }/*是,指向下一個(gè)子模塊,否,指針回到第一個(gè)子模塊*/
Else
{ MCBTb = MCBTb[1] }
}
}

3、實(shí)驗(yàn)仿真及結(jié)果分析

移植μC/OS- Ⅱ?qū)崟r(shí)操作系統(tǒng)到PC機(jī)上,以BC++4.5為開發(fā)平臺,完成分層調(diào)度算法下任務(wù)的調(diào)度執(zhí)行,結(jié)果如圖4所示。

實(shí)驗(yàn)結(jié)果顯示,改進(jìn)后的算法可以實(shí)現(xiàn)分層子模塊中任務(wù)的調(diào)度,調(diào)度器運(yùn)轉(zhuǎn)正常,證明了分層調(diào)度算法的可行性。在執(zhí)行多次后,如有任務(wù)完成,它就脫離原來的鏈,重新調(diào)整兩級索引表,并按調(diào)整后的兩級索引表引起新的調(diào)度。

本算法存在的問題是任務(wù)切換的頻繁次數(shù)增加,增大了調(diào)度的時(shí)間開銷,表1是對圖1的任務(wù)集在分層前后的調(diào)度運(yùn)行時(shí)任務(wù)切換次數(shù)的比較。

表1 分層調(diào)度前、后的任務(wù)切換次數(shù)對比分析表

4、結(jié)束語

本文作者創(chuàng)新點(diǎn):通過重構(gòu)μC/OS-Ⅱ內(nèi)核結(jié)構(gòu)和改進(jìn)其調(diào)度器,達(dá)到了μC/OS-Ⅱ支持分層調(diào)度的設(shè)計(jì)目標(biāo),其調(diào)度功能得到了擴(kuò)展和加強(qiáng)。改進(jìn)的μC/OS-Ⅱ內(nèi)核支持兩級的分層調(diào)度,在不改變原μC/OS-Ⅱ內(nèi)核搶占式內(nèi)核特征下實(shí)現(xiàn)了子系統(tǒng)模塊的固定時(shí)間分配方案的調(diào)度策略,使得μC /OS-Ⅱ內(nèi)核有能力支撐更為復(fù)雜的實(shí)時(shí)應(yīng)用。理論分析和實(shí)驗(yàn)認(rèn)證證明了擴(kuò)展μC/OS-Ⅱ內(nèi)核功能方法的正確性和有效性。

參考文獻(xiàn):
[1]WilliamL.Preemption-threshold. White Paper[Z].Express Logic Inc. 1992.
[2] Wang Y, Saksena M. Scheduling Fixed Priority Tasks with PreemptionThreshold[C]. Proceeding of 6th IEEE Real-time Computing Systemsand Applications Symposium, Hong Kong, 1999: 328-335.
[3]楊博,陳志剛. 一種基于雙層進(jìn)化結(jié)構(gòu)的網(wǎng)格任務(wù)調(diào)度算[J].計(jì)算機(jī)工程與應(yīng)用, 2006(15):4-7.
[4]劉衛(wèi),程明霄王曉榮. 實(shí)時(shí)系統(tǒng)優(yōu)先級位圖調(diào)度算法的改進(jìn)[J].微計(jì)算機(jī)信息程,2007,23(2):155-157.
[5] Mok,A.K.-L.,and D.Chen,“A multiframe model for real-time,”Proceedings of IEEE Real-time Systems Symposium,December, 1996.
 

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動(dòng)現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動(dòng)力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉