基于多目標調(diào)度的嵌入式可復(fù)用群控系統(tǒng)優(yōu)化

蔚晨月,李雪蓮

(1. 晉中信息學(xué)院信息工程學(xué)院,山西 太谷 030800;2. 山西大學(xué)計算機與信息技術(shù)學(xué)院,山西 太原 030006)

1 引言

嵌入式網(wǎng)絡(luò)是依據(jù)應(yīng)用需求,基于計算機技術(shù)[1]剪裁軟硬件的高端計算機專用系統(tǒng)。通常由嵌入式處理器以及外圍設(shè)備、相關(guān)軟件組合構(gòu)成,該系統(tǒng)以應(yīng)用為中心,根據(jù)系統(tǒng)的軟、硬件剪裁,建立適用于相關(guān)環(huán)境的高端定制系統(tǒng)。嵌入式系統(tǒng)[2]自被提出,就被人們廣泛地應(yīng)用在科技、經(jīng)濟、工業(yè)等各行各業(yè)中。隨著嵌入式系統(tǒng)的應(yīng)用不斷深入,對系統(tǒng)性能、實時性、能耗的要求也逐漸增高,對嵌入式系統(tǒng)進行必要的優(yōu)化是提升使用者體驗感的重要方法之一。

文獻[3]提出求解復(fù)雜耦合問題的多系統(tǒng)優(yōu)化方法。該方法依據(jù)子種群代表子系統(tǒng)優(yōu)化環(huán)境,通過遺傳算法中的種群變異、進化等操作求解全局優(yōu)化解;再對系統(tǒng)進行遷移處理,通過變量共享、目標函數(shù)以及約束條件的建立實現(xiàn)系統(tǒng)的信息反饋以及遷移,加速系統(tǒng)的全局優(yōu)化收斂速度;最后通過基準函數(shù)提取系統(tǒng)優(yōu)化特征,完成系統(tǒng)的優(yōu)化。該方法由于未能及時對系統(tǒng)數(shù)據(jù)進行去噪處理,導(dǎo)致存在系統(tǒng)延遲時間長的問題。文獻[4]提出結(jié)合模擬退火與規(guī)則約簡的模糊系統(tǒng)優(yōu)化方法。該方法依據(jù)支持度約簡系統(tǒng)獲取系統(tǒng)冗余規(guī)則,使用模擬退火算法優(yōu)化隸屬度函數(shù),通過優(yōu)化結(jié)果提高系統(tǒng)精度,實現(xiàn)系統(tǒng)優(yōu)化。該方法在提取數(shù)據(jù)冗余規(guī)則時存在問題,所以該優(yōu)化系統(tǒng)的運行利用率低。文獻[5]提出基于廣義短路比的光伏多饋入系統(tǒng)容量優(yōu)化方法。該方法首先基于系統(tǒng)的小干擾穩(wěn)定性,建立系統(tǒng)的小干擾穩(wěn)定分析模型,獲取系統(tǒng)的小干擾穩(wěn)定裕度值;再使用廣義的短路比方法計算系統(tǒng)中各個接入容量的靈敏度值;最后通過對系統(tǒng)小干擾穩(wěn)定裕度值以及接入容量的靈敏度值的整合,完成系統(tǒng)的優(yōu)化處理。該方法建立分析模型時存在較大誤差,所以該優(yōu)化系統(tǒng)的運行能耗高。

為解決上述系統(tǒng)優(yōu)化過程中存在的問題,提出基于多目標調(diào)度的嵌入式可復(fù)用群控系統(tǒng)優(yōu)化方法。

2 嵌入式系統(tǒng)容錯分析

在對嵌入式可復(fù)用群控系統(tǒng)進行優(yōu)化處理前,需要對系統(tǒng)進行容錯分析[6],獲取系統(tǒng)相關(guān)影響因素。

2.1 系統(tǒng)數(shù)據(jù)去噪

由于嵌入式可復(fù)用群控系統(tǒng)數(shù)據(jù)集中存在大量的噪聲數(shù)據(jù),所以在進行系統(tǒng)容錯分析前,需要對系統(tǒng)數(shù)據(jù)進行去噪處理。

使用高斯分布模型對嵌入式可復(fù)用群控系統(tǒng)整體數(shù)據(jù)進行收縮處理[7],獲取系統(tǒng)數(shù)據(jù)的分布式中心,基于正態(tài)分布方法對分布式中心進行擬合處理,取得系統(tǒng)數(shù)據(jù)方差,完成系統(tǒng)數(shù)據(jù)的去噪。具體流程如下:

1)建立一個坐標系,將嵌入式可復(fù)用群控系統(tǒng)數(shù)據(jù)集中到該坐標X軸上,并將其平均劃分成若干區(qū)間,數(shù)量用M表述。將區(qū)間內(nèi)的數(shù)據(jù)分布作為正態(tài)的分布模型,計算模型的正態(tài)分布均值以及數(shù)據(jù)的標準差,過程如下式所示

(1)

式中,區(qū)間內(nèi)數(shù)據(jù)標記為x,正態(tài)分布函數(shù)標記為f(x),正態(tài)分布均值標記為η,標準差標記為δ,迭代系數(shù)標記為π,區(qū)間i的數(shù)據(jù)分布標記為xi,各個區(qū)間數(shù)據(jù)量標記為m。

2)依據(jù)上述計算結(jié)果建立嵌入式可復(fù)用群控系統(tǒng)數(shù)據(jù)的誤差理想?yún)?shù)。首先對設(shè)定的理想化參數(shù)n進行初始化處理,隨機在各個坐標區(qū)間中進行數(shù)據(jù)采樣,建立正態(tài)分布模型獲取數(shù)據(jù)均值η以及標準差δ;通過區(qū)間數(shù)據(jù)均值、標準差與整體區(qū)間數(shù)據(jù)均值、標準差的對比獲取二者之間的誤差值σ,若誤差范圍在設(shè)定的理想誤差區(qū)間內(nèi),則認定數(shù)據(jù)去噪成功,若在區(qū)間外則繼續(xù)對數(shù)據(jù)進行迭代計算,直至計算結(jié)果達到理想誤差參數(shù)上限,完成各區(qū)間數(shù)據(jù)去噪處理。

3)數(shù)據(jù)去噪后通過MATIAB擬合算法將去噪結(jié)果擬合成一條數(shù)據(jù)分布曲線,獲取數(shù)據(jù)分布函數(shù),從而進行嵌入式可復(fù)用群控系統(tǒng)的容錯分析。

2.2 嵌入式可復(fù)用群控系統(tǒng)容錯分析

基于上述獲取的嵌入式可復(fù)用群控系統(tǒng)數(shù)據(jù)分布曲線,對嵌入式可復(fù)用群控系統(tǒng)進行容錯分析。

2.2.1 系統(tǒng)容錯分析流程

依據(jù)獲取的嵌入式可復(fù)用群控系統(tǒng)數(shù)據(jù)分布曲線建立系統(tǒng)容錯模型[8],分析嵌入式可復(fù)用群控系統(tǒng)故障概率與最大故障概率之間的關(guān)系,概率獲取過程中,需要完成系統(tǒng)處理器發(fā)布任務(wù)的當前故障概率。設(shè)定系統(tǒng)處理器接收任務(wù)的任務(wù)信號為a,處理器信號為b,處理器設(shè)定成C形式,硬實時狀態(tài)用t表述,檢查插入點數(shù)量為d,軟實時狀態(tài)標記為r。

系統(tǒng)在運行過程中會出現(xiàn)不同情況,具體分析結(jié)果如下:

1)系統(tǒng)軟硬實時任務(wù)狀態(tài)均未出現(xiàn)故障

設(shè)定嵌入式可復(fù)用群控系統(tǒng)處理器的對應(yīng)概率為Cp(0,t,d;0,r;C),子處理器j響應(yīng)概率標記Cp(0,t,d;0,r;Cj),表達形式如下式所示

(2)

式中,映射函數(shù)用YS(p)表示。依據(jù)上述可知,該情況為系統(tǒng)硬實時任務(wù)狀態(tài)以及軟實時任務(wù)狀態(tài)均未出現(xiàn)故障,系統(tǒng)任務(wù)成功執(zhí)行且任務(wù)執(zhí)行子處理器與總處理器狀態(tài)一致。

2)硬實時任務(wù)狀態(tài)出現(xiàn)故障

設(shè)定系統(tǒng)總處理器響應(yīng)概率為Cp(ug,t,d;0,r;C),子處理器j響應(yīng)概率標記Cp(uG,t,d;0,r;Cj),系統(tǒng)處理硬實時任務(wù)過程中故障概率[9]次數(shù)標記為ug,假定嵌入式可復(fù)用群控系統(tǒng)檢查點數(shù)量相同,則可以獲取如下公式

(3)

式中,系統(tǒng)故障錯誤的檢查點數(shù)量集標記為B,故障段標記為bx。依據(jù)上述分析可知,當系統(tǒng)進行任務(wù)調(diào)度時,軟實時狀態(tài)未發(fā)現(xiàn)故障、硬實時狀態(tài)出現(xiàn)故障[10],且故障總數(shù)量不會超出ug次。

這時,設(shè)定系統(tǒng)執(zhí)行任務(wù)集為Z,由硬實時任務(wù)α1以及軟實時任務(wù)α2組成。當嵌入式可復(fù)用群控系統(tǒng)執(zhí)行目標調(diào)度硬實時任務(wù)時,若成功發(fā)現(xiàn)軟實時任務(wù),就說明本次檢測任務(wù)執(zhí)行成功,可以構(gòu)建檢查點;若對硬實時任務(wù)進行檢測時發(fā)現(xiàn)軟實時任務(wù)出現(xiàn)故障,就說明需要對軟實時任務(wù)進行修復(fù),修復(fù)完成后建立檢測點,表明該檢測任務(wù)成功執(zhí)行。

3)軟實時任務(wù)狀態(tài)出現(xiàn)故障

設(shè)定系統(tǒng)總處理器響應(yīng)概率為Cp(0,t,d;us,r;C),子處理器j的響應(yīng)概率標記Cp(0,t,d;uS,r;Cj),獲取過程如下式所示

(4)

式中,系統(tǒng)在執(zhí)行多目標任務(wù)時,軟實時狀態(tài)出現(xiàn)的故障次數(shù)標記為us,當r?R時,說明軟實時狀態(tài)出現(xiàn)故障。

基于上述分析結(jié)果可知,嵌入式可復(fù)用群控系統(tǒng)任務(wù)調(diào)度問題是影響該系統(tǒng)優(yōu)化的主要原因,所以要利用相關(guān)算法對嵌入式系統(tǒng)的任務(wù)多目標調(diào)度進行優(yōu)化,達到優(yōu)化嵌入式系統(tǒng)的目的。

3 嵌入式可復(fù)用群控系統(tǒng)優(yōu)化方法

依據(jù)上述分析結(jié)果,使用Linux嵌入式單調(diào)調(diào)度算法[11]優(yōu)化系統(tǒng)的多目標調(diào)度分配,從而實現(xiàn)嵌入式可復(fù)用系統(tǒng)的優(yōu)化。

3.1 規(guī)范系統(tǒng)任務(wù)裕度空閑時間

首先設(shè)定嵌入式可復(fù)用群控系統(tǒng)任務(wù)調(diào)度的周期性數(shù)值為μ,優(yōu)先級等級為λ,使用任務(wù)搶先排序法對系統(tǒng)任務(wù)調(diào)度的周期性數(shù)值進行計算,結(jié)果如下式所示

(5)

式中,固定周期閾值標記為W。依據(jù)上述計算結(jié)果,將系統(tǒng)的任務(wù)裕度空閑時間[12]設(shè)定為si(t),并依據(jù)下式對其進行相關(guān)規(guī)范

(6)

式中,執(zhí)行時間標記為Di(t),規(guī)范結(jié)果用Ii(t)表述。

3.2 提取任務(wù)的特征價值關(guān)系

設(shè)定系統(tǒng)中調(diào)度對象的周期性安排為θ,任務(wù)的等級重要關(guān)系用Wt1≤Wt2≤…≤Wtm表示,任務(wù)的特征價值關(guān)系以及資源利用率[13]獲取過程如下式所示

(7)

通過上述計算流程進行系統(tǒng)多任務(wù)調(diào)度時,需要針對系統(tǒng)任務(wù)集對系統(tǒng)內(nèi)部任務(wù)參數(shù)進行計算,從而識別該系統(tǒng)任務(wù)是調(diào)度類型,過程如下式所示

(8)

式中,系統(tǒng)的可調(diào)度范圍用F表示。

3.3 確定相關(guān)約束條件

根據(jù)嵌入式可復(fù)用系統(tǒng)[14]的RM任務(wù)資源比對系統(tǒng)進行任務(wù)單調(diào)調(diào)度,確定系統(tǒng)任務(wù)優(yōu)先級,過程中需要利用EDF算法對系統(tǒng)任務(wù)調(diào)度進行規(guī)范化處理。設(shè)定系統(tǒng)任務(wù)的任務(wù)集為X,需要滿足的條件如下式所示

(9)

3.4 優(yōu)化流程

具體系統(tǒng)調(diào)度分配優(yōu)化流程如下式所示:

1)初始化系統(tǒng)數(shù)據(jù),并對數(shù)據(jù)進行相關(guān)去噪處理。

2)對系統(tǒng)任務(wù)調(diào)度數(shù)據(jù)進行初始化,確定系統(tǒng)任務(wù)調(diào)度屬性。

3)確定最佳分配路徑并依據(jù)式(8)完成任務(wù)特征數(shù)據(jù)值的采集和分類。

4)選定最高調(diào)度值執(zhí)行任務(wù)。

5)依據(jù)式(9)計算任務(wù)參數(shù),確定任務(wù)優(yōu)先級。

6)依據(jù)上述流程依次完成系統(tǒng)任務(wù)的多目標調(diào)度,完成系統(tǒng)任務(wù)多目標調(diào)度進行優(yōu)化,從而實現(xiàn)優(yōu)化嵌入式系統(tǒng)的目的。

依據(jù)上述流程優(yōu)化系統(tǒng)目標調(diào)度[15]流程時,需要對相關(guān)任務(wù)調(diào)度的約束屬性進行計算。設(shè)定嵌入式可復(fù)用系統(tǒng)任務(wù)的調(diào)用特征函數(shù)為Ri,以此優(yōu)化系統(tǒng)任務(wù)的調(diào)度策略,結(jié)果如下式所示

(10)

式中,系統(tǒng)的優(yōu)化調(diào)度策略標記為Ki(ω),最大約束數(shù)值標記為xmaxi,最小約束數(shù)值標記為xmini。最后通過上述流程完成系統(tǒng)多目標調(diào)度的優(yōu)化,從而實現(xiàn)對嵌入式可復(fù)用系統(tǒng)的優(yōu)化目的。

4 實驗

為了驗證上述嵌入式系統(tǒng)優(yōu)化方法的整體有效性,需要對此方法進行測試。分別對基于多目標調(diào)度的嵌入式可復(fù)用群控系統(tǒng)優(yōu)化方法(本文方法)、求解復(fù)雜耦合問題的多系統(tǒng)優(yōu)化方法(文獻[3]方法)、結(jié)合模擬退火與規(guī)則約簡的模糊系統(tǒng)優(yōu)化方法(文獻[4]方法)進行測試。

系統(tǒng)在進行優(yōu)化的過程中,系統(tǒng)延遲時間的高低、CPU利用率的大小以及處理能耗的大小都能側(cè)面證明系統(tǒng)優(yōu)化效果好壞。采用本文方法、文獻[3]方法以及文獻[4]方法進行系統(tǒng)優(yōu)化后,基于上述優(yōu)化效果測試指標,測試三種系統(tǒng)優(yōu)化方法的優(yōu)化效果。

1)系統(tǒng)延遲時間測試

系統(tǒng)在進行任務(wù)調(diào)度分配時,系統(tǒng)處理延遲時間的大小能夠反映系統(tǒng)的優(yōu)化效果。系統(tǒng)延遲時間越高,證明系統(tǒng)的優(yōu)化效果越差。反之則越好。利用本文方法、文獻[3]方法以及文獻[4]方法進行系統(tǒng)優(yōu)化后,對三種系統(tǒng)的任務(wù)處理延遲時間進行測試,測試結(jié)果如圖1所示。

圖1 不同系統(tǒng)優(yōu)化后的延遲時間測試結(jié)果

分析圖1可知,系統(tǒng)待處理目標任務(wù)越多,系統(tǒng)的延遲時間越高。本文方法在目標任務(wù)數(shù)量為100以前,測試出的系統(tǒng)延遲時間均為0,自目標任務(wù)數(shù)量為150時,測試結(jié)果出現(xiàn)變換,該方法出現(xiàn)系統(tǒng)延遲情況。文獻[3]方法在系統(tǒng)待處理目標任務(wù)數(shù)量為50時,系統(tǒng)未出現(xiàn)延遲情況,但是當目標任務(wù)數(shù)量為100時,該系統(tǒng)出現(xiàn)延遲,并隨著目標任務(wù)數(shù)量的增長不斷增加延遲時間。文獻[4]方法自測試開始就出現(xiàn)系統(tǒng)延遲情況,并隨著測試的進行測試出的延遲時間呈急速增長趨勢。由此可看出,本文方法進行系統(tǒng)優(yōu)化后,系統(tǒng)的延遲時間低于其它兩種系統(tǒng)優(yōu)化方法。

2)系統(tǒng)利用率測試

系統(tǒng)優(yōu)化后,系統(tǒng)利用率能夠直觀地反映出系統(tǒng)的優(yōu)化效果。系統(tǒng)在運行過程中,利用率越高,說明優(yōu)化效果越好,利用率越低,說明優(yōu)化效果越差。采用選定的三種系統(tǒng)優(yōu)化方法對系統(tǒng)進行優(yōu)化,測試三種系統(tǒng)優(yōu)化后的系統(tǒng)利用率,測試結(jié)果如圖2所示。

圖2 不同系統(tǒng)優(yōu)化后的運行利用率測試結(jié)果

分析圖2可知,隨著檢測次數(shù)的增加,系統(tǒng)的運行利用率呈不同程度的下降趨勢。本文方法測試出的系統(tǒng)運行利用率高于文獻[3]方法以及文獻[4]方法測試結(jié)果,文獻[3]方法測試結(jié)果高于文獻[4]方法,低于本文方法測試結(jié)果,文獻[4]方法測試結(jié)果最差。這主要是因為本文方法在進行系統(tǒng)優(yōu)化前對系統(tǒng)數(shù)據(jù)噪聲進行了去噪處理,所以該方法優(yōu)化后的系統(tǒng)在運行時的系統(tǒng)利用率高。

3)系統(tǒng)能耗測試

系統(tǒng)優(yōu)化后,系統(tǒng)運行能耗同樣能夠反映出系統(tǒng)的優(yōu)化效果,系統(tǒng)運行能耗越低,說明系統(tǒng)優(yōu)化效果越好,反之則越低。采用三種系統(tǒng)優(yōu)化方法優(yōu)化系統(tǒng)時,測試三種系統(tǒng)優(yōu)化后的系統(tǒng)運行能耗,測試結(jié)果如圖3所示。

圖3 不同系統(tǒng)優(yōu)化后的運行能耗測試結(jié)果

分析圖3可知,本文方法進行系統(tǒng)優(yōu)化后的系統(tǒng)運行能耗低于其它兩種系統(tǒng)優(yōu)化方法,文獻[3]方法在目標任務(wù)數(shù)量為200以前,測試出的系統(tǒng)運行能耗低于文獻[4]方法測試結(jié)果,但是當目標任務(wù)數(shù)量為300時,文獻[3]方法測試結(jié)果超出文獻[4]方法能耗測試結(jié)果,并隨著測試的進行測試出的能耗結(jié)果不斷升高。由此可知,本文方法在進行系統(tǒng)運行能耗測試時的測試結(jié)果優(yōu)于其它兩種方法。

綜上所述,本文方法優(yōu)化的系統(tǒng),系統(tǒng)延遲低、系統(tǒng)利用率高以及系統(tǒng)運行能耗低,可進一步證明本文方法的優(yōu)化效果好。

5 結(jié)束語

近年來,隨著科技的不斷進步,嵌入式可復(fù)用系統(tǒng)的應(yīng)用領(lǐng)域也逐漸擴大,結(jié)構(gòu)也愈加復(fù)雜。針對傳統(tǒng)嵌入式系統(tǒng)優(yōu)化方法中存在的問題,提出基于多目標調(diào)度的嵌入式可復(fù)用群控系統(tǒng)優(yōu)化方法。該方法依據(jù)系統(tǒng)的容錯性分析,找出影響系統(tǒng)運行的影響因子;使用Linux嵌入式單調(diào)調(diào)度算法對其進行優(yōu)化,從而實現(xiàn)嵌入式可復(fù)用系統(tǒng)的優(yōu)化目的。該方法由于在分析系統(tǒng)運行故障時還存在一定問題,今后會針對該項問題繼續(xù)完善該系統(tǒng)優(yōu)化方法。