面向任務協同的異構多核嵌入式系統實時調度方法

程 瑋,楊智玲

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

0 引言

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

1 異構多核嵌入式系統實時調度方法設計

1.1 面向任務協同構建實時調度模型

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

圖1 面向任務協同構建系統實時調度模型

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

(1)

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

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

(2)

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

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

(3)

其中,ts表示任務節點進入系統的時間,te表示任務節點退出系統的時間,o表示任務節點進出系統的次數,n表示任務節點的數量。

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

1.2 設定實時調度相關參數

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

(4)

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

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

(5)

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

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

(6)

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

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

1.3 實現異構多核嵌入式系統的實時調度

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

圖2 異構多核嵌入式系統實時調度過程

在本文中,系統實時調度的具體過程如下:

(7)

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

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

2 仿真實驗

2.1 實驗準備

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

表1 實驗測試集

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

表2 實驗參數設置

圖3 實驗環境

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

2.2 實驗結果與討論

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

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

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

3 結語

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