面向任務協(xié)同的異構多核嵌入式系統(tǒng)實時調度方法

程 瑋,楊智玲

(1.廈門海洋職業(yè)技術學院,福建 廈門 361100; 2.廈門市智慧漁業(yè)重點實驗室,福建 廈門 361100)

0 引言

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

1 異構多核嵌入式系統(tǒng)實時調度方法設計

1.1 面向任務協(xié)同構建實時調度模型

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

圖1 面向任務協(xié)同構建系統(tǒng)實時調度模型

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

(1)

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

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

(2)

其中,C(i,t)表示任務節(jié)點i的貢獻量,β表示任務傳輸的速率,C1(i,t)表示任務節(jié)點的上傳量,i,j表示任務節(jié)點在上傳過程中的序列數,D表示系統(tǒng)運行頻率,α表示任務節(jié)點的貢獻因子,k表示系統(tǒng)在一定周期內傳輸任務的個數。

在上述公式的基礎上,構建嵌入式系統(tǒng)實時調度的數學模型。其模型具體描述如下:

(3)

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

通過上述公式,構建系統(tǒng)實時調度模型,為后續(xù)系統(tǒng)的實時調度做準備。至此,面向任務協(xié)同的嵌入式系統(tǒng)實時調度模型的構建完成。

1.2 設定實時調度相關參數

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

(4)

其中,C表示信息匯集的最終結果,T表示系統(tǒng)傳輸數據的時間,x1表示系統(tǒng)任務傳輸的比特序列,Xv表示系統(tǒng)任務傳輸的分布序列,M表示系統(tǒng)傳輸的最大字節(jié),N表示系統(tǒng)傳輸的最小字節(jié)。

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

(5)

其中,sm(t)表示系統(tǒng)中任務數據的自適應分析量,V表示任務在系統(tǒng)中傳輸的實時數據量,c1表示系統(tǒng)傳輸的速率系數。

在上述公式的基礎上,設定實時調度模型的相關參數。其具體設定過程如下:

(6)

其中,A表示系統(tǒng)實時調度的時間均衡控制參數,u(i,d)表示系統(tǒng)任務的信息傳輸補償系數,z(i,d)表示系統(tǒng)任務調度的速率控制系數,x(i,d)表示系統(tǒng)任務的傳輸頻率系數,CR表示系統(tǒng)任務實時調度的信息最大可容量,FZ表示系統(tǒng)任務的安全性系數,n1表示隨機傳輸的系統(tǒng)任務信息。

通過上述公式,計算出系統(tǒng)調度模型的時間均衡控制參數和安全性系數,以此作為基礎進行系統(tǒng)的實時調度。至此,系統(tǒng)實時調度相關參數的設定完成。

1.3 實現異構多核嵌入式系統(tǒng)的實時調度

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

圖2 異構多核嵌入式系統(tǒng)實時調度過程

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

(7)

其中,Smax表示系統(tǒng)實時調度的結果,xi,j表示進行實時調度的任務,minSmax表示系統(tǒng)實時調度的最小屬性值,p表示實時調度的最小周期,m表示系統(tǒng)實時調度的任務量,k表示系統(tǒng)的調度參數。

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

2 仿真實驗

2.1 實驗準備

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

表1 實驗測試集

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

表2 實驗參數設置

圖3 實驗環(huán)境

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

2.2 實驗結果與討論

為驗證三種方法在實驗中的效果,本次實驗以各調度方法的調度時間為評價指標,對三種方法測試效果進行對比。由于本文篇幅有限,本次實驗結果僅展示三種方法對實驗測試集adpcm的測試效果。其具體結果如圖4所示。

圖4 三種實時調度方法的調度時間

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

3 結語

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