機(jī)載公共設(shè)備管理系統(tǒng)中的自適應(yīng)調(diào)度算法

1、240 機(jī)載公共設(shè)備管理系統(tǒng)中的自適應(yīng)調(diào)度算法劉 亭，王占林，裘麗華(北京航空航天大學(xué)自動(dòng)化科學(xué)與電氣工程學(xué)院機(jī)械電子工程系，北京 100083摘 要：多處理機(jī)任務(wù)分配和調(diào)度是機(jī)載公共設(shè)備綜合管理系統(tǒng)中的一個(gè)關(guān)鍵技術(shù)問(wèn)題。采用全局調(diào)度、局部調(diào)度和反饋調(diào)度相結(jié)合的方法，實(shí)現(xiàn)不確定性情況下的混合任務(wù)動(dòng)態(tài)調(diào)度。通過(guò)改進(jìn)免疫克隆算法進(jìn)行靜態(tài)調(diào)度，靜態(tài)調(diào)度的結(jié)果作為動(dòng)態(tài)分配的初始值，動(dòng)態(tài)調(diào)度具有檢測(cè)、分類(lèi)、自適應(yīng)反饋功能，適合混合任務(wù)共存以及變化的任務(wù)負(fù)載。 關(guān)鍵詞：公共設(shè)備綜合管理系統(tǒng)；自適應(yīng)調(diào)度；變化負(fù)載Adaptive Scheduling Algorithm in Aircraft Utilit

2、y Management SystemLIU Ting, WANG Zhan-lin, QIU Li-hua(Department of Mechatronics, School of Automation Science and Electrical Engineering,Beijing University of Aeronautics and Astronautics, Beijing 100083【Abstract 】Multiprocessor task allocation and scheduling is a key technology of the aircraft Ut

3、ility Management System(UMS. Dynamicscheduling of hybrid tasks in condition of uncertain instance is carried out by means of combination of static and dynamic condition and ofcombination of global, local and feedback scheduling. The static scheduling is carried out by the improved immune clone algor

4、ithm. Its result is asinitial value of dynamic allocation. The dynamic scheduling has the function of detecting, classifying, and adaptive feedback. It is applicable forcoexistence of hybrid tasks and variety of task load.【Key words】Utility Management System(UMS; adaptive scheduling; variable load計(jì)

5、算 機(jī) 工 程Computer Engineering第34卷 第9期 Vol.34 No.9 2008年5月May 2008工程應(yīng)用技術(shù)與實(shí)現(xiàn)文章編號(hào)：10003428(200809024003文獻(xiàn)標(biāo)識(shí)碼：A中圖分類(lèi)號(hào)：TP302.1機(jī)載公共設(shè)備的綜合化是種必然趨勢(shì)。多處理機(jī)任務(wù)分配和調(diào)度是機(jī)載公共設(shè)備綜合管理系統(tǒng)(UMS中一個(gè)關(guān)鍵技術(shù)問(wèn)題，屬于NP 難解問(wèn)題，在實(shí)際中很難得到最優(yōu)解。目前UMS 中任務(wù)調(diào)度多采用靜態(tài)方法，對(duì)動(dòng)態(tài)變化的負(fù)載較少考慮。動(dòng)態(tài)在線的方法對(duì)收斂性、快速性、準(zhǔn)確性、初始值的要求較嚴(yán)格，不便直接把靜態(tài)的方法應(yīng)用于動(dòng)態(tài)的場(chǎng)合。1 動(dòng)態(tài)自適應(yīng)任務(wù)調(diào)度算法動(dòng)態(tài)任務(wù)調(diào)度如圖1所示

6、。其中各部分功能如下：(1靜態(tài)任務(wù)分配，其結(jié)果作為動(dòng)態(tài)分配的初始值； (2任務(wù)分類(lèi)器，把不同的任務(wù)區(qū)分開(kāi)；(3分類(lèi)調(diào)度器，不同的任務(wù)采用不同的調(diào)度方法；(4檢測(cè)器，監(jiān)視本處理機(jī)任務(wù)執(zhí)行情況、處理機(jī)利用 情況；(5調(diào)整控制器，調(diào)整處理機(jī)利用率，對(duì)檢測(cè)器監(jiān)視到的情況進(jìn)行相應(yīng)的處理；(6準(zhǔn)入控制或可調(diào)度性測(cè)試，測(cè)試任務(wù)在當(dāng)前處理機(jī)調(diào)度上的可調(diào)度性；(7創(chuàng)建/接收/刪除任務(wù)，處理非預(yù)測(cè)負(fù)載；(8基本調(diào)度器，本處理機(jī)上調(diào)度隊(duì)列的基本調(diào)度方法； (9BC端分配器，對(duì)任務(wù)進(jìn)行全局動(dòng)態(tài)分配。 RT 端處理機(jī)動(dòng)態(tài)任務(wù)調(diào)度思路如下：(1BC端分配器把靜態(tài)任務(wù)分配結(jié)果分配到各個(gè)RT 端處理機(jī)；(2準(zhǔn)入控制器進(jìn)行可調(diào)

7、度性測(cè)試，通過(guò)則準(zhǔn)許控制，否則拒絕，告知BC 端分配器，構(gòu)成全局反饋調(diào)度； (3任務(wù)分類(lèi)器辨別任務(wù)類(lèi)型，若為周期任務(wù)采用彈性調(diào)度，若為非周期任務(wù)采用偷間隙調(diào)度，若為突發(fā)任務(wù)采用公平調(diào)度；(4周期任務(wù)、非周期任務(wù)和突發(fā)任務(wù)組成調(diào)度隊(duì)列； (5調(diào)度隊(duì)列采用基本調(diào)度器調(diào)度； (6準(zhǔn)備隊(duì)列運(yùn)行；(7采用檢測(cè)器對(duì)運(yùn)行情況進(jìn)行監(jiān)視；(8當(dāng)欠/過(guò)載時(shí)，調(diào)整控制器對(duì)CPU 利用率進(jìn)行調(diào)整，并進(jìn)入準(zhǔn)入控制器，構(gòu)成局部反饋調(diào)度；(9當(dāng)超過(guò)載或優(yōu)先級(jí)倒置時(shí)，刪除任務(wù)，并告知BC 端分配器，構(gòu)成全局反饋調(diào)度；(10當(dāng)處理機(jī)失效時(shí)，告知BC 端分配器，構(gòu)成全局反饋調(diào)度。BC 端處理機(jī)動(dòng)態(tài)任務(wù)分配思路如下：(1BC端分配

8、器把靜態(tài)任務(wù)分配結(jié)果分配到各個(gè)RT 端處理機(jī)；(2獲得各個(gè)RT 端處理機(jī)的CPU 利用率情況；(3對(duì)新建的任務(wù)、處理機(jī)失效的任務(wù)、局部調(diào)度被拒任務(wù)、超過(guò)載和優(yōu)先級(jí)倒置而被刪除的任務(wù)重新進(jìn)行分類(lèi)；基金項(xiàng)目：國(guó)家部委預(yù)研基金資助項(xiàng)目“機(jī)載公共設(shè)備綜合管理系統(tǒng)的研究”作者簡(jiǎn)介：劉 亭(1977 ，女，博士，主研方向：機(jī)載公共設(shè)備綜合管理系統(tǒng)，機(jī)載飛行器管理系統(tǒng)；王占林、裘麗華，教授、博士生導(dǎo)師收稿日期：2007-05-10 E-mail ：liuting241(4 周期任務(wù)和突發(fā)任務(wù)采用基于公平的調(diào)度；(5非周期調(diào)度采用把任務(wù)動(dòng)態(tài)分配到RT 端輕載處理器的方法；(6當(dāng)RT 端處理機(jī)失效時(shí)，BC 端分

9、配器采用啟發(fā)式算法，對(duì)失效處理機(jī)上的任務(wù)重新分配，并喚醒其他處理機(jī)上的備份版本。具體的自適應(yīng)調(diào)度算法實(shí)現(xiàn)如下： (1靜態(tài)任務(wù)分配免疫算法用在任務(wù)調(diào)度中1-3，具有很強(qiáng)的分布自適應(yīng)性、收斂性和智能自學(xué)習(xí)能力。文獻(xiàn)3采用表調(diào)度的方法，把免疫蟻群算法用到任務(wù)調(diào)度中。本文把它應(yīng)用于動(dòng)態(tài)系統(tǒng)中，對(duì)以往離線靜態(tài)和非實(shí)時(shí)的場(chǎng)合加以補(bǔ)充，進(jìn)一步說(shuō)明如何把它應(yīng)用于通信開(kāi)銷(xiāo)、任務(wù)負(fù)載和系統(tǒng)資源變化的場(chǎng)合。靜態(tài)任務(wù)分配結(jié)果作為動(dòng)態(tài)任務(wù)分配的初始查詢(xún)依據(jù)。靜態(tài)任務(wù)分配的目標(biāo)是最小化通信開(kāi)銷(xiāo)和沖突開(kāi)銷(xiāo)，平衡各個(gè)處理機(jī)負(fù)載。本文綜合考慮這些指標(biāo)，約束條件采用罰函數(shù)進(jìn)行處理，考慮節(jié)點(diǎn)差異，目標(biāo)函數(shù)為式(1，, , 0, 1

10、代表權(quán)系數(shù)，i S 代表各個(gè)處理機(jī)的處理速度系數(shù)，其他各變量的定義見(jiàn)文獻(xiàn)4。這是一個(gè)帶約束的多目標(biāo)優(yōu)化問(wèn)題：(total111, min min ( ( m mk k k k n i k i k i k CU U m U u P A U= (1 建立目標(biāo)函數(shù)為(11obj total (/ m mk k k k k k C U S U S C =+1( m k k k S U U = (2靜態(tài)任務(wù)分配采用改進(jìn)的免疫克隆算法進(jìn)行離線計(jì)算，多次運(yùn)行，求得次優(yōu)解。雖然傳統(tǒng)的免疫克隆算法絕對(duì)收斂，但是由于初始種群的隨機(jī)性，在有限的種群代數(shù)下，以及固定概率的變異，不能保證多次運(yùn)行的最優(yōu)率，本文采用如下的

11、改進(jìn)措施。1 編碼方式：雖然DNA 編碼的特點(diǎn)對(duì)于UMS 中4個(gè)處理機(jī)的多任務(wù)分配系統(tǒng)有一定的契合點(diǎn)，但由于本問(wèn)題具有較多的變量，復(fù)雜度將以指數(shù)級(jí)增長(zhǎng)，不適合采用DNA 編碼。與基于任務(wù)排列的方法相比，采用基于處理機(jī)的編碼，雖然會(huì)產(chǎn)生編碼冗余，但是具有更好的從父代繼承遺傳信息的能力。2 初始種群的確定：為快速收斂到近似最優(yōu)值，采用具有較好的局部尋優(yōu)能力的粒子群算法產(chǎn)生N 個(gè)初始抗體 種群。3 疫苗的更新：混沌序列的方法以50個(gè)任務(wù)的全排列進(jìn)行搜索，搜索空間太大，勢(shì)必會(huì)影響此算法的效率，本文以模擬退火算法對(duì)p N (01個(gè)疫苗進(jìn)行更新，并存儲(chǔ)在記憶庫(kù)中。4 免疫選擇概率、交叉、變異概率的確定：選

12、擇概率p 、交叉概率c p 、變異概率m p 常用的方法是自適應(yīng)的方法。而本文由模糊神經(jīng)網(wǎng)絡(luò)產(chǎn)生，輸入是適應(yīng)度，輸出是選擇概率、交叉概率、變異概率，隸屬度函數(shù)采用鈴形隸屬度函數(shù)：220( exp( /(2x x x = (3CPU 時(shí)間和尋優(yōu)次數(shù)反映了單次運(yùn)行的優(yōu)化效率，最優(yōu)率、空間搜索率和收斂率反映了多次運(yùn)行的優(yōu)化效率。仿真結(jié)果表明，改進(jìn)算法與基本算法相比，平均CPU 運(yùn)行時(shí)間相差不多，尋優(yōu)次數(shù)減少，最優(yōu)率較高，空間搜索率較小，收斂率仍然保持為100%，具有較好的多次運(yùn)行優(yōu)化效率。改進(jìn)算法與傳統(tǒng)的克隆算法相比，性能有所提高。(2任務(wù)分類(lèi)器本系統(tǒng)中實(shí)時(shí)任務(wù)錯(cuò)過(guò)截止期不會(huì)帶來(lái)災(zāi)難性的后果，為軟實(shí)

13、時(shí)任務(wù)。根據(jù)任務(wù)特點(diǎn)分為周期任務(wù)、非周期任務(wù)和突發(fā)任務(wù)。周期任務(wù)具有固定的相位和周期，非周期任務(wù)在隨機(jī)時(shí)間釋放且有軟截止期或無(wú)截止期，突發(fā)任務(wù)在隨機(jī)時(shí)間釋放且有硬截止期。周期任務(wù)由執(zhí)行時(shí)間i e ，周期i p 0i p , max i p ，相位i ，彈性系數(shù)i E (i E 與周期的變化量成正比 ，最壞情況執(zhí)行時(shí)間i WCET ，CPU 利用率/i i i u e p =，絕對(duì)截止期i d ，釋放時(shí)間i r ，相對(duì)截止期i D =i d -i r ，松弛時(shí)間i L =i D -i e 等因素來(lái)描述，i T =i e , i p , i E , i WCET , i u , i d , i r

14、 。圖1 動(dòng)態(tài)任務(wù)調(diào)度算法示意圖242非周期任務(wù)由執(zhí)行時(shí)間i e ，釋放時(shí)間間隔i p ，最壞情況執(zhí)行時(shí)間i WCET ，CPU 利用率i u ，軟截止期i d ，釋放時(shí)間i r 等來(lái)描述，i T =i e , i p , i WCET , i u , i d , i r 。突發(fā)任務(wù)由執(zhí)行時(shí)間i e ，釋放時(shí)間間隔i p ，最壞情況執(zhí)行時(shí)間i WCET ，CPU 利用率i u ，硬截止期i d ，釋放時(shí)間i r 等來(lái)描述，i T =i e , i p , i WCET , i u , i d , i r 。(3分類(lèi)調(diào)度器周期任務(wù)采用可變負(fù)載的彈性調(diào)度，彈性調(diào)度使周期在min i p , max

15、 i p 之間變化，通過(guò)壓縮任務(wù)周期，增大任務(wù)利用率，改善欠載狀況，提高QoS ，過(guò)載時(shí)則延伸任務(wù)周期，提高采樣周期內(nèi)周期任務(wù)實(shí)例執(zhí)行的數(shù)目；非周期任務(wù)采用偷間隙調(diào)度；突發(fā)任務(wù)采用公平調(diào)度。(4檢測(cè)器由檢測(cè)器對(duì)運(yùn)行情況進(jìn)行監(jiān)視，監(jiān)視處理機(jī)利用率情況，監(jiān)測(cè)任務(wù)優(yōu)先級(jí)倒置、處理器失效、欠載、過(guò)載、超過(guò)載(調(diào)整彈性任務(wù)后處理機(jī)仍然過(guò)載 、優(yōu)先級(jí)倒置等情況。(5調(diào)整控制器根據(jù)監(jiān)測(cè)器監(jiān)測(cè)的情況，對(duì)于變化的情況進(jìn)行相應(yīng)的處理，采用PID 控制規(guī)則控制任務(wù)的利用率，減少任務(wù)的截止期錯(cuò)失率。(6準(zhǔn)入控制或可調(diào)度性測(cè)試若通過(guò)測(cè)試，則進(jìn)入分類(lèi)調(diào)度器，否則，通知BC 端分配器，根據(jù)RT 端處理器負(fù)載情況，進(jìn)行全局分

16、配。每個(gè)處理機(jī)的負(fù)載都不能超過(guò)1。(7創(chuàng)建/接收/刪除任務(wù) 處理非預(yù)測(cè)負(fù)載。 (8基本調(diào)度器采用故障容錯(cuò)EDF 。 (9BC端分配器對(duì)新建的任務(wù)、處理機(jī)失效的任務(wù)、局部反饋調(diào)度被拒任務(wù)、超過(guò)載和優(yōu)先級(jí)倒置而刪除的任務(wù)重新進(jìn)行分類(lèi)。若是周期任務(wù)和突發(fā)任務(wù)，則采用基于公平的調(diào)度PD 2，允許任務(wù)片在0, 1內(nèi)變化大小，不同特性任務(wù)片組成超任務(wù)，超任務(wù)在不同的RT 端處理機(jī)上運(yùn)行且不需要同步。若是非周期任務(wù)，通知其他輕載處理機(jī)接管該任務(wù)，把任務(wù)動(dòng)態(tài)分配到RT 端處理機(jī)，使得RT 端處理機(jī)在原來(lái)負(fù)載基礎(chǔ)上共同分擔(dān)新增的負(fù)載，當(dāng)RT 端處理機(jī)失效時(shí)，采用啟發(fā)式近視算法，分配到其他處理機(jī)上?？梢?jiàn)本文并沒(méi)有

17、把所有的任務(wù)一開(kāi)始都分配在BC 端分配器上再向RT 端處理機(jī)分發(fā)，而是首先由各個(gè)RT 端處理機(jī)調(diào)度任務(wù)，對(duì)局部調(diào)度不能處理的情況進(jìn)行全局調(diào)度。(10通信BC 端分配器裝有兩余度1553B 總線控制器BC ，RT 端處理機(jī)有4個(gè)，每個(gè)分別裝有兩余度1553B 遠(yuǎn)程終端RT 。相互之間通過(guò)1553B 實(shí)時(shí)總線通信，并保證各個(gè)RT 端處理機(jī)之間的時(shí)鐘同步。(11容錯(cuò)采用多版本技術(shù)，每個(gè)任務(wù)兩余度(主版本和備份版本 ，備份版本在同一處理機(jī)或不同處理機(jī)上備份運(yùn)行。當(dāng)主版本出現(xiàn)故障時(shí)，副版本投入運(yùn)行。2 實(shí)驗(yàn)把多處理機(jī)調(diào)度比擬為水箱模型，如圖2所示。 圖2 水箱模型采用水箱模型，閉環(huán)輸入模擬到達(dá)任務(wù)，開(kāi)環(huán)

18、輸入表示新加入任務(wù)，開(kāi)環(huán)輸出表示完成任務(wù)，閉環(huán)輸出表示轉(zhuǎn)移，箭頭表示轉(zhuǎn)移方向，泵、閥表示遵守的控制策略。一個(gè)處理機(jī)同時(shí)存在周期任務(wù)、非周期任務(wù)和突發(fā)任務(wù)時(shí)，利用率動(dòng)態(tài)控制仿真結(jié)果如圖3所示。時(shí)間/s輸入輸出910876543210.51.0處理機(jī)利用率0.00圖3 利用率控制仿真曲線在圖3中，輸入表示期望的利用率加上了幅值為0.01的干擾，輸出表示在動(dòng)態(tài)調(diào)度策略下的實(shí)際利用率響應(yīng)曲線。從圖中可以看出，周期任務(wù)、非周期任務(wù)和突發(fā)任務(wù)并存時(shí)候，輸出利用率可以近似跟蹤期望值。上升沿和下降沿處的滯后時(shí)間和幅值超調(diào)很小，在允許的范圍內(nèi)。3 結(jié)束語(yǔ)本文采用靜動(dòng)結(jié)合的方法，實(shí)現(xiàn)不確定性情況下的混合任務(wù)動(dòng)態(tài)調(diào)度。動(dòng)態(tài)調(diào)度具有如下特點(diǎn)：(1多任務(wù)并存，多調(diào)度方法的并發(fā)控制；(2全局反饋和局部反饋并存，自適應(yīng)