分級(jí)調(diào)度實(shí)時(shí)架構(gòu)中處理器資源預(yù)設(shè)值的預(yù)借性

王華忠, 王文凱, 顏秉勇

(華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化教育部重點(diǎn)實(shí)驗(yàn)室 上海 200237)

分級(jí)調(diào)度實(shí)時(shí)架構(gòu)中處理器資源預(yù)設(shè)值的預(yù)借性

王華忠, 王文凱, 顏秉勇

(華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化教育部重點(diǎn)實(shí)驗(yàn)室 上海 200237)

分層多級(jí)自適應(yīng)調(diào)度(AdHierSched)架構(gòu)是Linux操作系統(tǒng)中的虛擬實(shí)時(shí)架構(gòu),在系統(tǒng)運(yùn)行時(shí),它通過(guò)監(jiān)測(cè)各子系統(tǒng)對(duì)處理器資源的需求動(dòng)態(tài)調(diào)整資源分配。本文在分級(jí)調(diào)度架構(gòu)中提出了處理器資源預(yù)借機(jī)制(BBM),通過(guò)服務(wù)器間資源的動(dòng)態(tài)分配達(dá)到處理器資源在各個(gè)實(shí)時(shí)系統(tǒng)中優(yōu)化配置的目的,并針對(duì)AdHierSched架構(gòu)中資源預(yù)設(shè)值的預(yù)借性進(jìn)行設(shè)計(jì)和實(shí)現(xiàn),通過(guò)靜態(tài)任務(wù)和動(dòng)態(tài)任務(wù)對(duì)該資源預(yù)設(shè)值預(yù)借控制器進(jìn)行實(shí)驗(yàn)評(píng)估。實(shí)驗(yàn)結(jié)果表明:當(dāng)AdHierSched架構(gòu)伴隨著處理器預(yù)借機(jī)制和資源調(diào)整機(jī)制同時(shí)運(yùn)行時(shí),內(nèi)部運(yùn)行任務(wù)整體的截止期限超出率減小。此外,資源預(yù)借性機(jī)制的添加導(dǎo)致的系統(tǒng)額外開(kāi)銷相比系統(tǒng)總的開(kāi)銷很小,表明該方案適合在實(shí)際分級(jí)調(diào)度實(shí)時(shí)系統(tǒng)內(nèi)推廣使用。

虛擬實(shí)時(shí)架構(gòu); 動(dòng)態(tài)任務(wù); 分級(jí)調(diào)度; 截止期限超出率; 資源預(yù)設(shè)值預(yù)借機(jī)制

系統(tǒng)虛擬技術(shù)的廣泛應(yīng)用使得實(shí)時(shí)操作系統(tǒng)(RTOSs)能夠與Linux、Windows或者其他系統(tǒng)在同臺(tái)機(jī)器上同時(shí)運(yùn)行。當(dāng)多個(gè)實(shí)時(shí)系統(tǒng)在虛擬系統(tǒng)中同時(shí)運(yùn)行時(shí),保持其各自建立時(shí)的時(shí)序?qū)傩圆蛔冿@得尤為重要。通過(guò)運(yùn)用分級(jí)調(diào)度(Hierarchical scheduling)技術(shù)可使組合后的各個(gè)系統(tǒng)相對(duì)安全地按照實(shí)時(shí)系統(tǒng)的時(shí)序要求進(jìn)行運(yùn)行[1]。同一硬件平臺(tái)上CPU資源的分配方式嚴(yán)重影響著各系統(tǒng)性能的發(fā)揮,將CPU資源分為一系列分區(qū)并分配給各個(gè)實(shí)時(shí)系統(tǒng)是分級(jí)調(diào)度技術(shù)中資源分配的主要方式,通過(guò)將單個(gè)系統(tǒng)獲得的CPU資源和其實(shí)際的需求進(jìn)行比較和調(diào)整,可達(dá)到CPU資源在各個(gè)系統(tǒng)中的最優(yōu)配置[2]。而單個(gè)系統(tǒng)實(shí)際資源需求是通過(guò)其內(nèi)部任務(wù)的最壞情況執(zhí)行時(shí)間(WCET)獲得的,但在實(shí)際應(yīng)用中有些實(shí)時(shí)任務(wù)的WCET不是先驗(yàn)已知的,例如視頻解碼器應(yīng)用程序,其執(zhí)行時(shí)間主要決定于輸入視頻包含的內(nèi)容,因視頻的不同會(huì)有顯著的改變;依靠傳感器來(lái)控制物理環(huán)境變化的控制任務(wù),其對(duì)CPU需求也因環(huán)境的改變而改變。即使WCET是已知的,其值通常比平均執(zhí)行時(shí)間大,若按照WCET對(duì)每個(gè)實(shí)時(shí)系統(tǒng)進(jìn)行資源分配,必將導(dǎo)致處理器資源的浪費(fèi),而且任務(wù)偶爾超出截止期限的情況在大多數(shù)軟實(shí)時(shí)系統(tǒng)中是可以接受的,所以在資源有限的嵌入式系統(tǒng)中過(guò)多分配CPU資源是極不可取的。

AdHierSched[3]架構(gòu)具有在線監(jiān)測(cè)任務(wù)資源需求的能力,從而解決了上述問(wèn)題。該架構(gòu)是一個(gè)將硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)組合在一起的虛擬嵌入式實(shí)時(shí)系統(tǒng),運(yùn)用分級(jí)調(diào)度技術(shù)和基于服務(wù)器調(diào)度算法[4],不但能夠?yàn)橛矊?shí)時(shí)系統(tǒng)分配靜態(tài)的CPU資源,而且可根據(jù)軟實(shí)時(shí)系統(tǒng)運(yùn)行時(shí)的實(shí)際需求而動(dòng)態(tài)調(diào)整其獲得的CPU資源[5]。分級(jí)調(diào)度架構(gòu)(HSF)[6-8]運(yùn)用CPU分區(qū)技術(shù),將CPU資源分割成一定數(shù)量的區(qū)域,并將每個(gè)區(qū)域分配給架構(gòu)中的子系統(tǒng)。架構(gòu)內(nèi)的全局調(diào)度器調(diào)度其內(nèi)部所有子系統(tǒng),每個(gè)子系統(tǒng)內(nèi)包含一個(gè)調(diào)度其內(nèi)部任務(wù)或其子系統(tǒng)的本地調(diào)度器。分級(jí)調(diào)度系統(tǒng)中采用何種方式分配處理器資源至關(guān)重要,目前雖有文獻(xiàn)對(duì)分級(jí)調(diào)度架構(gòu)中處理器資源分配領(lǐng)域做了研究,但對(duì)處理器資源借用機(jī)制的研究鮮有報(bào)道。本文針對(duì)該問(wèn)題,提出了處理器資源預(yù)借適應(yīng)機(jī)制,并將該機(jī)制運(yùn)用于Linux內(nèi)核可加載模塊AdHierSched架構(gòu)中,通過(guò)動(dòng)態(tài)任務(wù)和靜態(tài)任務(wù)對(duì)該機(jī)制進(jìn)行評(píng)估,并對(duì)引入該機(jī)制而增加的額外開(kāi)銷進(jìn)行分析。

1 分層多級(jí)調(diào)度架構(gòu)

圖1 AdHierSched架構(gòu)框架圖Fig.1 AdHierSched framework

2 分級(jí)調(diào)度實(shí)時(shí)架構(gòu)中處理器資源預(yù)設(shè)值預(yù)借機(jī)制

2.1 服務(wù)器資源預(yù)借機(jī)制

2.2 資源預(yù)借機(jī)制觸發(fā)時(shí)機(jī)的設(shè)計(jì)

因不明確任務(wù)的執(zhí)行時(shí)間,服務(wù)器很難確定觸發(fā)資源預(yù)借機(jī)制的時(shí)機(jī),針對(duì)此問(wèn)題,本文提出了一種新方法來(lái)告知服務(wù)器何時(shí)需要借用資源。動(dòng)態(tài)任務(wù)τj的執(zhí)行時(shí)間Cj未知,其截止期限與任務(wù)周期相等,當(dāng)服務(wù)器沒(méi)有系統(tǒng)資源時(shí),其下面運(yùn)行的任務(wù)因資源問(wèn)題而暫停,直到該服務(wù)器資源得到補(bǔ)充才可以繼續(xù)執(zhí)行。任務(wù)截止期限與其停止時(shí)間tk之間的時(shí)間間隔為Δt,通過(guò)比較Δt與服務(wù)器周期的大小并檢查該任務(wù)是否完成執(zhí)行就可決定其是否會(huì)錯(cuò)過(guò)截止期限。如果Δt小于服務(wù)器周期,而且該任務(wù)還沒(méi)有執(zhí)行完,那么將不能在截止時(shí)間以前執(zhí)行完。因?yàn)樵诜?wù)器的資源沒(méi)有得到補(bǔ)充前,該任務(wù)只能處于等待狀態(tài),當(dāng)?shù)却隣顟B(tài)結(jié)束時(shí),其已經(jīng)超出截止期限。為確保任務(wù)能夠在Δt時(shí)間內(nèi)繼續(xù)執(zhí)行,服務(wù)器需要在結(jié)束當(dāng)前周期前觸發(fā)資源預(yù)借機(jī)制,從即將到來(lái)的下一個(gè)服務(wù)器周期中借一定數(shù)量的資源,進(jìn)而維持任務(wù)能夠繼續(xù)執(zhí)行。

圖2 服務(wù)器預(yù)設(shè)資源以及任務(wù)執(zhí)行時(shí)間在運(yùn)行時(shí)的追蹤圖Fig.2 Example of server borrow budget and task execution tine

圖3 觸發(fā)資源預(yù)借機(jī)制時(shí)機(jī)實(shí)例圖Fig.3 Example diagram of resource BBM

2.3 資源借用量的設(shè)計(jì)

在運(yùn)行資源預(yù)借機(jī)制之前,通過(guò)計(jì)算系統(tǒng)總的可用帶寬,可以獲得系統(tǒng)內(nèi)總的可用資源。因系統(tǒng)總的CPU帶寬為1,所以總的CPU帶寬減去系統(tǒng)應(yīng)用占用的帶寬即為可借用帶寬,計(jì)算公式如下:

(1)

其中:Ufree為可借用帶寬;Ui為服務(wù)器i所占用帶寬。由系統(tǒng)CPU可借用帶寬可計(jì)算出服務(wù)器在當(dāng)前周期中最大可借資源值BMax,其計(jì)算公式如下:

BMax=UfreeTj

(2)

為了估計(jì)實(shí)際需要借用資源的量,本文運(yùn)用自回歸模型(Autoregressive (AR) model)[12]估計(jì)每個(gè)服務(wù)器周期中所需分配資源的量。自回歸是變量對(duì)自身的回歸,根據(jù)歷史數(shù)據(jù)估計(jì)出相對(duì)準(zhǔn)確的估計(jì)值,通過(guò)AR模型獲得的估計(jì)值可用式(3)表述。

Bk+1=c+[θ1B1+θ2B2+…+θkBk]+ek

(3)

(4)

(5)

(6)

2.4 系統(tǒng)過(guò)載的處理

服務(wù)器獲得系統(tǒng)分配的資源后,計(jì)算所得的借用資源θ有可能大于最大可借資源BMax,導(dǎo)致系統(tǒng)出現(xiàn)過(guò)載現(xiàn)象。為了避免該情形的發(fā)生,借用資源θ需要與最大可借資源BMax進(jìn)行比較,當(dāng)θBMax時(shí),BMax數(shù)量的借用資源會(huì)被分配給服務(wù)器;但當(dāng)過(guò)載不可避免時(shí),重要性值較高的應(yīng)用程序會(huì)從重要性值較低的應(yīng)用程序那里獲取資源,以此來(lái)維持其內(nèi)部任務(wù)的運(yùn)行。

3 實(shí)驗(yàn)設(shè)計(jì)與驗(yàn)證

3.1 實(shí)驗(yàn)環(huán)境配置

3.2 實(shí)驗(yàn)任務(wù)的選擇和實(shí)驗(yàn)設(shè)計(jì)

運(yùn)用動(dòng)態(tài)任務(wù)和靜態(tài)任務(wù)對(duì)AdHierSched架構(gòu)進(jìn)行評(píng)估,其中動(dòng)態(tài)任務(wù)由兩部分組成,一部分動(dòng)態(tài)任務(wù)的執(zhí)行時(shí)間由泊松分布隨機(jī)產(chǎn)生,剩下的任務(wù)來(lái)自Mplayer音樂(lè)播放器程序。當(dāng)播放音樂(lè)時(shí),為了使AdHierSched架構(gòu)能夠收到Mplayer音樂(lè)播放器中的任務(wù),Mplayer的源代碼被稍微改動(dòng)。在3種不同條件下進(jìn)行實(shí)驗(yàn):(1)架構(gòu)僅伴隨資源預(yù)借控制器運(yùn)行;(2)架構(gòu)僅伴隨資源調(diào)節(jié)器運(yùn)行;(3)架構(gòu)同時(shí)伴隨資源預(yù)借控制器和資源調(diào)節(jié)器運(yùn)行。

3.3 實(shí)驗(yàn)結(jié)果

表1 任務(wù)和服務(wù)器參數(shù)表

3.3.2 多服務(wù)器多靜態(tài)任務(wù)實(shí)驗(yàn) 本實(shí)驗(yàn)采用4個(gè)靜態(tài)任務(wù)和3個(gè)服務(wù)器,詳細(xì)參數(shù)見(jiàn)表2,服務(wù)器的重要性值與服務(wù)器的編號(hào)一致,即ζ0>ζ1>ζ2。圖4示出了實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)表明,當(dāng)AdHierSched在條件2下工作時(shí),所有任務(wù)具有最低的DMR值;當(dāng)任務(wù)在條件3下運(yùn)行時(shí),由于有過(guò)載發(fā)生,因服務(wù)器S0重要性值最高,系統(tǒng)為使其下面任務(wù)具有相對(duì)較低的DMR值,導(dǎo)致分配到服務(wù)器S2內(nèi)的資源有所減少,造成任務(wù)τ3DMR值在此實(shí)驗(yàn)中有所增加。

表2 靜態(tài)任務(wù)和服務(wù)器參數(shù)表

圖4 多靜態(tài)任務(wù)多服務(wù)器實(shí)驗(yàn)結(jié)果Fig.4 Multiple static tasks and severs experiment

3.3.3 單服務(wù)器單動(dòng)態(tài)任務(wù)實(shí)驗(yàn) 本實(shí)驗(yàn)中,動(dòng)態(tài)任務(wù)的執(zhí)行時(shí)間在40～90 ms之間變化。任務(wù)和服務(wù)器的詳細(xì)參數(shù)見(jiàn)表3。圖5示出了本實(shí)驗(yàn)中任務(wù)執(zhí)行時(shí)間的正態(tài)分布圖。本實(shí)驗(yàn)共有20組,每組包含100個(gè)不同的執(zhí)行時(shí)間。因動(dòng)態(tài)任務(wù)的執(zhí)行時(shí)間不同導(dǎo)致每組的DMR輸出有所變化。圖6所示為本次實(shí)驗(yàn)中服務(wù)器在不同運(yùn)行條件下的最高、最低和平均截止期限超出率。實(shí)驗(yàn)結(jié)果表明,該架構(gòu)在條件3下工作的表現(xiàn)性能最好,其平均DMR值僅為13%,運(yùn)行在條件1和條件2下的平均DMR值分別為51%和19%。

表3 單服務(wù)器單動(dòng)態(tài)任務(wù)實(shí)驗(yàn)

圖5 動(dòng)態(tài)任務(wù)的工作執(zhí)行時(shí)間正態(tài)分布圖Fig.5 Normal distribution of all the dynamic tasks

圖6 單動(dòng)態(tài)任務(wù)實(shí)驗(yàn)結(jié)果Fig.6 Single dynamic task deadline miss ratio experiment results

3.3.4 多服務(wù)器多動(dòng)態(tài)任務(wù)實(shí)驗(yàn) 本實(shí)驗(yàn)采用5個(gè)動(dòng)態(tài)任務(wù)和3個(gè)服務(wù)器,其詳細(xì)參數(shù)見(jiàn)表4,實(shí)驗(yàn)結(jié)果見(jiàn)圖7。由圖7可知,當(dāng)架構(gòu)在條件1下運(yùn)行時(shí),每個(gè)服務(wù)器下面的任務(wù)都有錯(cuò)過(guò)截止期限的情況發(fā)生。然而當(dāng)架構(gòu)在條件2下運(yùn)行時(shí),其表現(xiàn)性能好于前者,各個(gè)任務(wù)的平均DMR值都有所下降;當(dāng)架構(gòu)在條件3下運(yùn)行時(shí),任務(wù)τ0、τ1和τ2的平均DMR值比在條件2時(shí)更低,但是任務(wù)τ3和τ4的DMR值反而有所增加,造成此情況是因有過(guò)載發(fā)生,所以系統(tǒng)根據(jù)各服務(wù)器的重要性值進(jìn)行分配資源。因S0具有最高的重要性值,因此該架構(gòu)以減少對(duì)服務(wù)器S1、S2資源分配為代價(jià)來(lái)提高τ0和τ1的DMR值,因此任務(wù)τ3和τ4的DMR值才會(huì)增加。

表4 多動(dòng)態(tài)任務(wù)多服務(wù)器實(shí)驗(yàn)參數(shù)表

圖7 多動(dòng)態(tài)任務(wù)多服務(wù)器實(shí)驗(yàn)結(jié)果Fig.7 Multiple dynamic tasks and severs experiment

3.3.5 系統(tǒng)開(kāi)銷分析 去除Linux系統(tǒng)調(diào)度開(kāi)銷外,實(shí)驗(yàn)運(yùn)行時(shí)系統(tǒng)內(nèi)共有3種開(kāi)銷:(1)用來(lái)計(jì)算調(diào)度任務(wù)的分級(jí)調(diào)度開(kāi)銷;(2)資源預(yù)借控制器中用來(lái)計(jì)算和借用服務(wù)器資源的開(kāi)銷;(3)資源調(diào)控器中用來(lái)計(jì)算和調(diào)節(jié)服務(wù)器資源的開(kāi)銷。本文通過(guò)程序運(yùn)行時(shí)的時(shí)間戳來(lái)測(cè)量開(kāi)銷。針對(duì)多服務(wù)器多動(dòng)態(tài)任務(wù)的實(shí)驗(yàn),當(dāng)架構(gòu)在條件3下運(yùn)行時(shí),3種開(kāi)銷所占的比例見(jiàn)圖8。用來(lái)計(jì)算資源預(yù)借控制器和資源調(diào)控器的額外開(kāi)銷都很小,幾乎相同,且3種開(kāi)銷的總和約為0.224 % CPU時(shí)間,故因添加資源預(yù)借控制器而添加的額外開(kāi)銷在實(shí)際應(yīng)用中是可以接受的。

3.3.6 與分級(jí)調(diào)動(dòng)架構(gòu)中其他資源調(diào)節(jié)機(jī)制的比較 文獻(xiàn)[13]通過(guò)采用反饋控制理論實(shí)現(xiàn)分級(jí)調(diào)度架構(gòu)中處理器資源在子系統(tǒng)中的動(dòng)態(tài)調(diào)整,反饋控制雖有很多優(yōu)點(diǎn),但當(dāng)多個(gè)任務(wù)同時(shí)執(zhí)行時(shí),反饋控制器上的時(shí)滯問(wèn)題嚴(yán)重,系統(tǒng)資源不能及時(shí)分配到相應(yīng)的子系統(tǒng)中,因此執(zhí)行任務(wù)的截止期限超

圖8 條件3下系統(tǒng)開(kāi)銷實(shí)驗(yàn)Fig.8 Overhead experiment when the framework runs under condition 3

出率雖略有下降,但依然不是很理想;文獻(xiàn)[14]在分級(jí)調(diào)度架構(gòu)內(nèi)采用模糊控制來(lái)調(diào)整CPU資源在子系統(tǒng)中的分配。模糊控制雖具有較強(qiáng)的魯棒性和容錯(cuò)能力,但是由于分級(jí)架構(gòu)內(nèi)僅對(duì)資源信息進(jìn)行模糊處理,導(dǎo)致架構(gòu)內(nèi)動(dòng)態(tài)調(diào)整資源分配的能力不是很強(qiáng)。分級(jí)調(diào)度架構(gòu)內(nèi)CPU資源不同調(diào)節(jié)機(jī)制對(duì)比參見(jiàn)表5。

表5 分級(jí)調(diào)度架構(gòu)內(nèi)CPU資源不同調(diào)節(jié)機(jī)制對(duì)比

4 結(jié) 論

本文對(duì)分級(jí)調(diào)度實(shí)時(shí)系統(tǒng)內(nèi)部的資源配置進(jìn)行研究,提出了處理器資源預(yù)借機(jī)制,并在AdHierSched架構(gòu)內(nèi)對(duì)該機(jī)制進(jìn)行研究、設(shè)計(jì)和實(shí)驗(yàn)驗(yàn)證。首先運(yùn)用自回歸模型為即將運(yùn)行的服務(wù)器估計(jì)新的預(yù)設(shè)資源,然后通過(guò)運(yùn)用實(shí)時(shí)系統(tǒng)中動(dòng)態(tài)任務(wù)和靜態(tài)任務(wù)來(lái)對(duì)該機(jī)制進(jìn)行評(píng)估,實(shí)驗(yàn)結(jié)果表明:當(dāng)AdHierSched架構(gòu)伴隨著處理器預(yù)借機(jī)制和資源調(diào)整機(jī)制同時(shí)運(yùn)行時(shí),內(nèi)部運(yùn)行任務(wù)整體的截止期限超出率減小,實(shí)時(shí)系統(tǒng)中資源的分配得到優(yōu)化。此外,資源預(yù)借性機(jī)制的添加沒(méi)有明顯增加系統(tǒng)額外開(kāi)銷,因而本文提出的方案在分級(jí)調(diào)度實(shí)時(shí)應(yīng)用系統(tǒng)中具有較高的實(shí)用價(jià)值。

[1] Chris Grujon.Gnu operating system[EB/OL].[2016-07-08].http://embedded-computing.com/articles/the-multiprocessor-multi-os-systems

[2] YAMAGUCHI A,NAKAMOTO Y,SATO K,etal.EDF-PStream:Earliest deadline first scheduling of preemptable data streams:Issues related to automotive applications[C]//2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications.Hong Kong,China,IEEE,2015:257-267.

[3] KHALILZAD N,BEHNAM M,NOLTE T.Multi-level adaptive hierarchical scheduling framework for composing real-time systems[C]//2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications.Taipei,China:IEEE,2013:320-329.

[4] LUCA M,GIUSEPPE L,PATRICIA B,etal.Iris:A new reclaiming algorithm for server-based real-time systems[C]//10th IEEE Real-Time and Embedded Technology and Applications Symposium.USA:IEEE,2004, 211-218.

[5] KHALILZAD N,BEHNAM M, NOLTE T.Implementation of the multi-level adaptive hierarchical scheduling framework[C]//9th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Appllication.Paris,France:ACM,2013:11-19.

[6] BIONDI A,GIORGIO C B,MARKO B.Schedulability analysis of hierarchical real-time systems under shared resources[J].IEEE Transactions on Computers,2016,65(5):1593-1605.

[7] VAN DEN H,MARTIJN M H P,REINDER J.Budget allocations for hierarchical fixed-priority scheduling of sporadic tasks with deferred preemptions upon EDP resources[J].ACM SIGBED Review,2015,12(1):19-27.

[8] LUNNISS W,SEBASTIAN A,ROBERT I D.Accounting for cache related pre-emption delays in hierarchical scheduling with local EDF scheduler[J].Real-Time Systems,2014,52(2):13-16.

[9] INSIK S,LEE I.Periodic resource model for compositional real-time guarantees[C]// RTSS '03 Proceedings of the 24th IEEE International Real-Time Systems Symposium.USA:IEEE,2003:2-13.

[10] CHEN M S,HWANG C P,WANG H F.Analysis of the queue service probability for the EDF scheduling algorithm[C]//2016 30th International Conference on Advanced Information Networking and Applications Workshops (WAINA).Switzerland:IEEE Computer Society,2016:960-963.

[11] NATHAN F,DEWAN F.A bandwidth allocation scheme for compositional real-time systems with periodic resources[J].Real-Time Systems,2012,48(3):223-263.

[12] HIROTUGU A.Fitting autoregressive models for prediction[J].Annals of the Institute of Statistical Mathematics,1969,21(1):243-247.

[13] KHALILZAD N M,BEHNAM M,NOLTE T,etal.On adaptive hierarchical scheduling of real-time systems using a feedback controller[C]//3rd Workshop on Adaptive and Reconfigurable Embedded Systems (APRES’11).Chicago:[s.n.],2011:159-165.

[14] KHALILZAD N M,BEHNAM M,SPAMPINATO G,etal.Bandwidth adaptation in hierarchical scheduling using fuzzy controllers[C]//7th IEEE International Symposium on Industrial Embedded Systems (SIES’12).USA:IEEE,2012:148-157.

ResourceBorrowingMechanismBasedonHierarchicalSchedulingReal-TimeFramework

WANGHua-zhong,WANGWen-kai,YANBing-yong

(KeyLaboratoryofAdvancedControlandOptimizationforChemicalProcesses,MinistryofEducation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

Multi-level adaptive hierarchical scheduling (AdHierSched) framework is a virtualized real-time framework in Linux operating system,which dynamically schedules the CPU partition sizes by monitoring the demand of every subsystem during running process.This paper presents a Budget Borrowing Mechanism (BBM) in hierarchical scheduling framework.The proposed BBM can dynamically assign the CPU resource between servers in real-time systems.Moreover,in AdHierSched framework,the proposed BBM is designed and implemented for dynamical adaptation the resource parameters.Both static and dynamic tasks are utilized to evaluate the budget borrowing controller.Experiment results show that while different tasks execute in the framework with the proposed BBM,the task’s deadline miss ratio is lower than those without using this mechanism.Compared with the total overhead of system,the extra overhead from budget borrowing calculation is very small.Hence,the proposed mechanism is suitable in actual applications.

virtualized real-time framework; dynamic task; hierarchical scheduling; deadline miss ratio; resource budget borrowing mechanism

1006-3080(2017)06-0837-07

10.14135/j.cnki.1006-3080.2017.06.013

2016-12-06

國(guó)家自然科學(xué)基金青年基金(51407078)

王華忠(1965-),男,副教授,主要研究方向?yàn)閺?fù)雜工業(yè)過(guò)程建模、控制與故障診斷。E-mail:hzwang@ecust.edu.cn

TP316.2

A