程 瑋,楊智玲

(1.廈門海洋職業(yè)技術(shù)學(xué)院,福建 廈門 361100; 2.廈門市智慧漁業(yè)重點(diǎn)實(shí)驗(yàn)室,福建 廈門 361100)

0 引言

多核處理器使嵌入式系統(tǒng)能夠同時運(yùn)行多個任務(wù),提升了系統(tǒng)的計(jì)算能力,同時也給系統(tǒng)的實(shí)時調(diào)度帶來了不小的挑戰(zhàn)[1]。與傳統(tǒng)的單核處理器不同,多核處理器在處理系統(tǒng)任務(wù)時,需要考慮任務(wù)的優(yōu)先級,也要考慮任務(wù)的分配問題,保證任務(wù)準(zhǔn)確、快速地完成[2]。因此,以往的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法面臨十分嚴(yán)峻的挑戰(zhàn)。對此,不少研究學(xué)者提出了自己的想法。劉璐等[3]提出基于半劃分調(diào)度算法的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法,在核集的支持下,利用半劃分調(diào)度算法,改變?nèi)蝿?wù)只能運(yùn)行在一個處理器核的情況,使得任務(wù)能夠運(yùn)行于局部核,降低系統(tǒng)進(jìn)行任務(wù)調(diào)度時的計(jì)算壓力,實(shí)現(xiàn)嵌入式系統(tǒng)的實(shí)時調(diào)度,實(shí)驗(yàn)結(jié)果表明該方法耗費(fèi)時間太長。張小花等[4]提出基于整數(shù)線性規(guī)劃的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法,通過將任務(wù)的控制流程圖分解成內(nèi)存圖,將內(nèi)存圖中的每個節(jié)點(diǎn)鎖定在高速緩存中,并創(chuàng)建出循環(huán)網(wǎng)樹,從中計(jì)算出任務(wù)運(yùn)行的最差時間,實(shí)現(xiàn)系統(tǒng)的實(shí)時調(diào)度。實(shí)驗(yàn)結(jié)果表明,該方法應(yīng)用成本過高。劉洪標(biāo)等[5]提出基于云計(jì)算技術(shù)的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法,通過對系統(tǒng)數(shù)據(jù)信息進(jìn)行分簇式整理,劃分系統(tǒng)數(shù)據(jù)信息的優(yōu)先級,利用云計(jì)算技術(shù),對系統(tǒng)數(shù)據(jù)進(jìn)行調(diào)控,實(shí)現(xiàn)系統(tǒng)的實(shí)時調(diào)度,實(shí)驗(yàn)結(jié)果表明該方法的適用性較差。在以往研究的基礎(chǔ)上,本文設(shè)計(jì)了面向任務(wù)協(xié)同的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法,通過構(gòu)建系統(tǒng)實(shí)時調(diào)度模型,設(shè)置相關(guān)的調(diào)度參數(shù),實(shí)現(xiàn)系統(tǒng)的實(shí)時調(diào)度。

1 異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法設(shè)計(jì)

1.1 面向任務(wù)協(xié)同構(gòu)建實(shí)時調(diào)度模型

為實(shí)現(xiàn)嵌入式系統(tǒng)的實(shí)時調(diào)度,需要對嵌入式系統(tǒng)的信息進(jìn)行實(shí)時分析。對于嵌入式系統(tǒng)的實(shí)時調(diào)度,需要先將嵌入式系統(tǒng)中的實(shí)時數(shù)據(jù)信息作為初始的任務(wù)結(jié)構(gòu)信息。在連接網(wǎng)絡(luò)時,利用通信裝置接收不同時刻任務(wù)的實(shí)時信息,并對該任務(wù)節(jié)點(diǎn)信息進(jìn)行判定[6]。本文在任務(wù)協(xié)同的基礎(chǔ)上,將原本的系統(tǒng)任務(wù)數(shù)據(jù)信息轉(zhuǎn)變成陣列形式的數(shù)據(jù),并結(jié)合調(diào)度行為來調(diào)整發(fā)送需求的平臺[7]。同時,在系統(tǒng)指定的空間,將系統(tǒng)實(shí)時信息進(jìn)行結(jié)構(gòu)描述,利用信息動態(tài)對其進(jìn)行控制,從而構(gòu)建系統(tǒng)實(shí)時調(diào)度模型[8]。其具體結(jié)構(gòu)規(guī)劃如圖1所示。

圖1 面向任務(wù)協(xié)同構(gòu)建系統(tǒng)實(shí)時調(diào)度模型

如圖1所示,面對多個任務(wù),系統(tǒng)會使用多個處理單元進(jìn)行處理,且每個任務(wù)并不會僅使用單一的處理器進(jìn)行處理。同時,在進(jìn)行任務(wù)實(shí)時處理時,需要重點(diǎn)考慮的一個因素就是系統(tǒng)的丟包率[9]。系統(tǒng)中處理器對于任務(wù)的處理效率,將會直接影響系統(tǒng)的丟包率大小。因此,在進(jìn)行系統(tǒng)調(diào)度時,系統(tǒng)中任務(wù)節(jié)點(diǎn)的傳輸情況如下:

(1)

其中,F(t)表示系統(tǒng)傳輸?shù)男?L(i,t)表示系統(tǒng)在節(jié)點(diǎn)i時的丟包率,S(i,t)表示系統(tǒng)在節(jié)點(diǎn)i處的任務(wù)數(shù)據(jù)信息交換速度,S1表示系統(tǒng)中任意任務(wù)節(jié)點(diǎn)傳輸時所需的速率,B(i,t)表示系統(tǒng)在傳輸任務(wù)節(jié)點(diǎn)的最大速率。

通過式(1)可計(jì)算出系統(tǒng)任務(wù)節(jié)點(diǎn)的速度,同時,對系統(tǒng)中各任務(wù)節(jié)點(diǎn)的丟包率按照一定的順序進(jìn)行排序,將其中最小丟包率和次小丟包率的任務(wù)節(jié)點(diǎn)的速度進(jìn)行提升,提升到最大速率,再將任務(wù)節(jié)點(diǎn)按照丟包率的從小到大的順序進(jìn)行速度的提升,直到所有的任務(wù)節(jié)點(diǎn)速度均不低于正常的傳輸速率[10]。在本文的設(shè)計(jì)中,將丟包率作為系統(tǒng)實(shí)時跳讀的依據(jù),能夠提高任務(wù)節(jié)點(diǎn)的傳輸速度,加強(qiáng)系統(tǒng)的有效傳輸,但這也會導(dǎo)致不需要高速率傳輸?shù)娜蝿?wù)節(jié)點(diǎn)無法進(jìn)行有效傳輸,增加系統(tǒng)負(fù)載,同時還會導(dǎo)致其他任務(wù)節(jié)點(diǎn)無法進(jìn)行快速傳輸,無法實(shí)現(xiàn)系統(tǒng)整體的效率最大化[11]。因此,在上述設(shè)計(jì)的實(shí)時調(diào)度模型中,通過對任務(wù)節(jié)點(diǎn)數(shù)據(jù)的分時分批傳輸,將任務(wù)節(jié)點(diǎn)的貢獻(xiàn)情況引入系統(tǒng)中,提升系統(tǒng)的傳輸速率,減少資源浪費(fèi)。其具體的貢獻(xiàn)過程如下:

(2)

其中,C(i,t)表示任務(wù)節(jié)點(diǎn)i的貢獻(xiàn)量,β表示任務(wù)傳輸?shù)乃俾?C1(i,t)表示任務(wù)節(jié)點(diǎn)的上傳量,i,j表示任務(wù)節(jié)點(diǎn)在上傳過程中的序列數(shù),D表示系統(tǒng)運(yùn)行頻率,α表示任務(wù)節(jié)點(diǎn)的貢獻(xiàn)因子,k表示系統(tǒng)在一定周期內(nèi)傳輸任務(wù)的個數(shù)。

在上述公式的基礎(chǔ)上,構(gòu)建嵌入式系統(tǒng)實(shí)時調(diào)度的數(shù)學(xué)模型。其模型具體描述如下:

(3)

其中,ts表示任務(wù)節(jié)點(diǎn)進(jìn)入系統(tǒng)的時間,te表示任務(wù)節(jié)點(diǎn)退出系統(tǒng)的時間,o表示任務(wù)節(jié)點(diǎn)進(jìn)出系統(tǒng)的次數(shù),n表示任務(wù)節(jié)點(diǎn)的數(shù)量。

通過上述公式,構(gòu)建系統(tǒng)實(shí)時調(diào)度模型,為后續(xù)系統(tǒng)的實(shí)時調(diào)度做準(zhǔn)備。至此,面向任務(wù)協(xié)同的嵌入式系統(tǒng)實(shí)時調(diào)度模型的構(gòu)建完成。

1.2 設(shè)定實(shí)時調(diào)度相關(guān)參數(shù)

在完成嵌入式系統(tǒng)實(shí)時調(diào)度模型的構(gòu)建后,為保證系統(tǒng)內(nèi)數(shù)據(jù)信息調(diào)度的合理性,對系統(tǒng)實(shí)時調(diào)度模型中相關(guān)參數(shù)進(jìn)行設(shè)定。在構(gòu)建系統(tǒng)調(diào)度模型后,為了保證設(shè)定的參數(shù)具有一定的時效性,系統(tǒng)中會匯聚大量的有效信息和無效信息[12]。其具體匯集過程如下:

(4)

其中,C表示信息匯集的最終結(jié)果,T表示系統(tǒng)傳輸數(shù)據(jù)的時間,x1表示系統(tǒng)任務(wù)傳輸?shù)谋忍匦蛄?Xv表示系統(tǒng)任務(wù)傳輸?shù)姆植夹蛄?M表示系統(tǒng)傳輸?shù)淖畲笞止?jié),N表示系統(tǒng)傳輸?shù)淖钚∽止?jié)。

通過上述公式,將大量的任務(wù)數(shù)據(jù)信息匯集到一起。由于匯集的任務(wù)數(shù)據(jù)信息占用了大量的空間,會影響到后續(xù)的參數(shù)設(shè)定[13],因此將匯集的信息量進(jìn)行自適應(yīng)分析,其具體分析過程如下:

(5)

其中,sm(t)表示系統(tǒng)中任務(wù)數(shù)據(jù)的自適應(yīng)分析量,V表示任務(wù)在系統(tǒng)中傳輸?shù)膶?shí)時數(shù)據(jù)量,c1表示系統(tǒng)傳輸?shù)乃俾氏禂?shù)。

在上述公式的基礎(chǔ)上,設(shè)定實(shí)時調(diào)度模型的相關(guān)參數(shù)。其具體設(shè)定過程如下:

(6)

其中,A表示系統(tǒng)實(shí)時調(diào)度的時間均衡控制參數(shù),u(i,d)表示系統(tǒng)任務(wù)的信息傳輸補(bǔ)償系數(shù),z(i,d)表示系統(tǒng)任務(wù)調(diào)度的速率控制系數(shù),x(i,d)表示系統(tǒng)任務(wù)的傳輸頻率系數(shù),CR表示系統(tǒng)任務(wù)實(shí)時調(diào)度的信息最大可容量,FZ表示系統(tǒng)任務(wù)的安全性系數(shù),n1表示隨機(jī)傳輸?shù)南到y(tǒng)任務(wù)信息。

通過上述公式,計(jì)算出系統(tǒng)調(diào)度模型的時間均衡控制參數(shù)和安全性系數(shù),以此作為基礎(chǔ)進(jìn)行系統(tǒng)的實(shí)時調(diào)度。至此,系統(tǒng)實(shí)時調(diào)度相關(guān)參數(shù)的設(shè)定完成。

1.3 實(shí)現(xiàn)異構(gòu)多核嵌入式系統(tǒng)的實(shí)時調(diào)度

在上述設(shè)定的基礎(chǔ)上,實(shí)現(xiàn)異構(gòu)多核嵌入式系統(tǒng)的實(shí)時調(diào)度,其實(shí)時調(diào)度過程如圖2所示。在調(diào)度開始時,從構(gòu)建的模型中獲取系統(tǒng)原始隊(duì)列中最高優(yōu)先級任務(wù),并滿足最高優(yōu)先級任務(wù)的配置需求,同時從任務(wù)集合中獲取最高優(yōu)先級的任務(wù),將任務(wù)集合中的最高優(yōu)先級任務(wù)和原始隊(duì)列中最高優(yōu)先級任務(wù)進(jìn)行對比,若前者大于后者,則直接將任務(wù)集合中的最高優(yōu)先級任務(wù)作為后繼任務(wù),并在處理器上運(yùn)行,從而完成系統(tǒng)調(diào)度[14]。若前者不大于后者,則需要進(jìn)行二次判定,判斷前者是否等于后者:若等于,則將執(zhí)行時間較長的任務(wù)作為后繼任務(wù),在處理器上運(yùn)行,完成系統(tǒng)實(shí)時調(diào)度[15];若不等于,則將原始隊(duì)列中的最高優(yōu)先級任務(wù)作為后繼任務(wù),在處理器上進(jìn)行運(yùn)行,從而完成系統(tǒng)的實(shí)時調(diào)度。

圖2 異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度過程

在本文中,系統(tǒng)實(shí)時調(diào)度的具體過程如下:

(7)

其中,Smax表示系統(tǒng)實(shí)時調(diào)度的結(jié)果,xi,j表示進(jìn)行實(shí)時調(diào)度的任務(wù),minSmax表示系統(tǒng)實(shí)時調(diào)度的最小屬性值,p表示實(shí)時調(diào)度的最小周期,m表示系統(tǒng)實(shí)時調(diào)度的任務(wù)量,k表示系統(tǒng)的調(diào)度參數(shù)。

通過上述公式,完成對系統(tǒng)實(shí)時調(diào)度結(jié)果的計(jì)算。同時,根據(jù)計(jì)算的實(shí)時調(diào)度的最小屬性值,判斷當(dāng)前調(diào)度結(jié)果是否為最優(yōu)調(diào)度過程,如果最小屬性值小于或等于標(biāo)準(zhǔn)值,則說明當(dāng)前調(diào)度方法較好;如果最小屬性值大于標(biāo)準(zhǔn)值,則需要重新規(guī)劃調(diào)度過程[16]。至此,面向任務(wù)協(xié)同的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法的設(shè)計(jì)完成。

2 仿真實(shí)驗(yàn)

2.1 實(shí)驗(yàn)準(zhǔn)備

為驗(yàn)證本文設(shè)計(jì)的面向任務(wù)協(xié)同的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法在實(shí)際應(yīng)用中的效果,進(jìn)行仿真實(shí)驗(yàn)。在本次實(shí)驗(yàn)中,從某異核多構(gòu)嵌入式系統(tǒng)選取11個實(shí)驗(yàn)測試集,作為實(shí)驗(yàn)對象。11個實(shí)驗(yàn)測試集的具體介紹如表1所示。

表1 實(shí)驗(yàn)測試集

如表1所示,利用本文設(shè)計(jì)的方法對上述實(shí)驗(yàn)測試集進(jìn)行實(shí)驗(yàn)測試。同時,為保證實(shí)驗(yàn)順利進(jìn)行,搭建相應(yīng)的實(shí)驗(yàn)環(huán)境,設(shè)置對應(yīng)的實(shí)驗(yàn)參數(shù)。具體設(shè)置情況如表2所示,實(shí)驗(yàn)環(huán)境如圖3所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

圖3 實(shí)驗(yàn)環(huán)境

如圖3所示,在上述環(huán)境中進(jìn)行實(shí)驗(yàn)測試。為保證本次實(shí)驗(yàn)的可信度,設(shè)置對照實(shí)驗(yàn)。本文設(shè)計(jì)的面向任務(wù)協(xié)同的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法為方法1,基于群集一致性的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法為方法2,基于混沌進(jìn)化算法的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法為方法3。

2.2 實(shí)驗(yàn)結(jié)果與討論

為驗(yàn)證三種方法在實(shí)驗(yàn)中的效果,本次實(shí)驗(yàn)以各調(diào)度方法的調(diào)度時間為評價指標(biāo),對三種方法測試效果進(jìn)行對比。由于本文篇幅有限,本次實(shí)驗(yàn)結(jié)果僅展示三種方法對實(shí)驗(yàn)測試集adpcm的測試效果。其具體結(jié)果如圖4所示。

圖4 三種實(shí)時調(diào)度方法的調(diào)度時間

如圖4所示,不論哪種實(shí)時調(diào)度方法,極少有任務(wù)調(diào)度時間超過10 s的,這說明在10 s時間內(nèi),系統(tǒng)能夠完成絕大部分的任務(wù)調(diào)度。同時,從上述任務(wù)調(diào)度時間的分布狀態(tài)上看,方法1的任務(wù)調(diào)度時間最短,最大調(diào)度僅為5 s,方法2和方法3的任務(wù)調(diào)度時間雖然都在10 s之內(nèi),但是存在大部分任務(wù)調(diào)度需要花費(fèi)5 s以上的時間,可見,方法1實(shí)時調(diào)度所花費(fèi)的時間最短。因此,本文設(shè)計(jì)的面向任務(wù)協(xié)同的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法在實(shí)際應(yīng)用中效果最好,能夠快速且準(zhǔn)確地進(jìn)行系統(tǒng)調(diào)度。

3 結(jié)語

綜上所述,本文設(shè)計(jì)的面向任務(wù)協(xié)同的異構(gòu)多核嵌入式系統(tǒng)實(shí)時調(diào)度方法通過構(gòu)建系統(tǒng)實(shí)時調(diào)度模型,設(shè)置相應(yīng)的模型,提高了系統(tǒng)進(jìn)行任務(wù)調(diào)度的速度和準(zhǔn)確性。同時,本文設(shè)計(jì)的方法針對系統(tǒng)調(diào)度不準(zhǔn)確的問題,采用多處理器協(xié)同作業(yè),保證了系統(tǒng)的響應(yīng)速度。然而,本文設(shè)計(jì)的方法中還存在些許不足,如系統(tǒng)內(nèi)部緩存空間不充足,在下一步研究中將針對此問題進(jìn)行改善。