可靠性感知周期任務(wù)能耗管理調(diào)度算法*

張憶文，王 成

華僑大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，福建 廈門 361021

可靠性感知周期任務(wù)能耗管理調(diào)度算法*

張憶文+，王 成

華僑大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，福建 廈門 361021

針對EDF/DDM（earliest deadline first/dynamic deadline modify）算法不能利用空閑時間降低能耗的不足，提出了能夠回收空閑時間的靜態(tài)節(jié)能（static saving energy，SSE）算法。針對SSE算法沒有考慮系統(tǒng)可靠性問題，在證明可靠性感知資源受限周期任務(wù)調(diào)度問題是NP難之后，提出兩種啟發(fā)式算法：最長執(zhí)行時間優(yōu)先算法（longest execution time first，LETF）算法和最短執(zhí)行時間優(yōu)先算法（shortest execution time first，SETF）算法。仿真實驗表明所提出的LETF算法和SETF算法的能耗均低于EDF/DDM算法的能耗。此外，SETF算法和LETF算法的出錯率比EDF/DDM算法低，是EDF/DDM算法的97%和76%，系統(tǒng)可靠性得到提高。

能耗；可靠性感知；資源受限；實時調(diào)度

1 引言

對于使用電池供電的嵌入式系統(tǒng)便捷式設(shè)備而言，低能耗是其設(shè)計目標(biāo)。低能耗可以減少設(shè)備的冷卻成本，延長電池的使用時間。動態(tài)電壓調(diào)節(jié)（dynamic voltage supply，DVS）技術(shù)是一種有效的低功耗技術(shù)[1]，它利用系統(tǒng)的空閑時間，通過調(diào)節(jié)處理器速度，降低系統(tǒng)能耗。

低能耗調(diào)度算法是解決系統(tǒng)能耗的主要技術(shù)。文獻(xiàn)[1-4]提出的算法以系統(tǒng)能耗為目標(biāo)，忽略處理器速度對系統(tǒng)可靠性造成的影響。而文獻(xiàn)[5]的研究指出，處理器速度降低，系統(tǒng)可靠性降低。因此，在降低處理器速度時，必須采取措施來確保系統(tǒng)可靠性。近年來，很多研究者針對相互獨立的周期任務(wù)模型的可靠性感知調(diào)度問題開展研究[5-8]。文獻(xiàn)[6]首次提出了可靠性感知能耗管理（reliability aware power management，RA-PM）方法來解決系統(tǒng)可靠性問題。該方法通過利用空閑時間構(gòu)建恢復(fù)任務(wù)來確保系統(tǒng)可靠性。文獻(xiàn)[9]拓展了該研究成果，并且提出了能夠利用動態(tài)空閑時間構(gòu)建恢復(fù)任務(wù)的方法。但是文獻(xiàn)[9]所提的方法只能選取固定的任務(wù)作為縮放任務(wù)，對空閑時間的利用率低。文獻(xiàn)[10]提出了能夠動態(tài)利用空閑時間構(gòu)建恢復(fù)任務(wù)的方法。

以上的研究成果僅僅針對相互獨立的周期任務(wù)模型，忽略了系統(tǒng)的資源共享問題。文獻(xiàn)[11]提出了基本的繼承協(xié)議和天花板協(xié)議來解決資源共享問題。文獻(xiàn)[12]針對資源受限的偶發(fā)任務(wù)模型，提出了EDF/DDM（earliest deadline first/dynamic deadline modify）算法來解決因資源共享所造成的優(yōu)先級逆轉(zhuǎn)問題。但是該算法沒有考慮系統(tǒng)的能耗問題。文獻(xiàn)[13]擴展了該研究成果，提出了偶發(fā)任務(wù)低功耗調(diào)度算法。該算法利用DVS技術(shù)，降低了系統(tǒng)能耗，但其忽略了處理器的靜態(tài)功耗，且假設(shè)任務(wù)以其最壞情況下的執(zhí)行時間執(zhí)行。針對這些不足，張憶文等人[2]提出了考慮通用功耗模型，能夠回收動態(tài)空閑時間的調(diào)度算法。但是這些研究成果都忽略了處理器速度對系統(tǒng)可靠性的影響。

以上研究成果僅僅針對系統(tǒng)可靠性、資源共享問題的某一方面進(jìn)行研究，針對該問題提出了可靠性感知周期任務(wù)能耗管理調(diào)度算法。

2 系統(tǒng)模型和問題闡述

2.1 任務(wù)模型

在單處理器硬實時系統(tǒng)中，考慮n個資源限制的周期任務(wù)集T={T1,T2,…,Tn}，該任務(wù)集共享的資源集合用R={R1,R2,…,Rn}表示[11]。每個周期任務(wù)Ti用三元組(ei,ri,pi)表示，其中ei是Ti最壞情況下的執(zhí)行時間；ri是Ti的資源需求，其值為1≤ri≤m之間的整數(shù)；pi是Ti的周期。ri≠0表示任務(wù)Ti在執(zhí)行過程中需要使用資源Rri；ri=0表示任務(wù)Ti沒有資源需求，意味著其在執(zhí)行過程中不會有優(yōu)先級逆轉(zhuǎn)問題。系統(tǒng)利用率用Utot表示，其值為。假設(shè)任務(wù)Ti的相對截止期限等于其周期，且任務(wù)一次至多只使用一個資源。任務(wù)Ti的第 j個實例用Ti,j表示。

利用文獻(xiàn)[12]提出的EDF/DDM算法調(diào)度周期任務(wù)集T。EDF/DDM算法以EDF策略為基礎(chǔ)，通過動態(tài)地修改任務(wù)的截止期限來實現(xiàn)，且利用信號量確保資源能夠被互斥訪問。每個任務(wù)Ti有兩個截止期限，初始截止期限(IDi)和執(zhí)行截止期限(EDi)。IDi是根據(jù)EDF調(diào)度策略分配的截止期限，而EDi是任務(wù)開始執(zhí)行時分配的截止期限。任務(wù)的優(yōu)先級根據(jù)其執(zhí)行截止期限來確定，執(zhí)行截止期限越近，其優(yōu)先級就越高，優(yōu)先調(diào)度。任務(wù)Ti就緒時，設(shè)置EDi=IDi。對于有資源需求的任務(wù)Ti開始執(zhí)行時修改EDi，將其值設(shè)置為。其中tri是 Ti的釋放時刻；Pi是所有共享資源Ri的周期任務(wù)的最小周期，其值為Pi=min(pj|rj=i)；tsi是Ti開始執(zhí)行的時刻。任務(wù)Ti的IDi=tri+pi。對于沒有資源需求的任務(wù)Ti，無論何時其EDi=IDi。

2.2 功耗模型

采用系統(tǒng)層次的功耗模型[2]，其功耗P的計算方法如下：

其中，Ps是靜態(tài)功耗，主要來自保持電路和基本時鐘運轉(zhuǎn)的功耗，系統(tǒng)關(guān)閉時其值為0；Pind是與速度無關(guān)的功耗；Cef是電路的有效負(fù)載電容；S是處理器歸一化速度；m為與系統(tǒng)相關(guān)的常數(shù)，其值為2≤m≤3；h是常數(shù)，當(dāng)處理器處于空閑狀態(tài)時，其值為h=0，否則h=1。

為了使系統(tǒng)層次的能耗最低，文獻(xiàn)[9]提出了關(guān)鍵速度Scrit的概念，為了確保任務(wù)不錯過截止期限，任務(wù)的執(zhí)行速度不低于關(guān)鍵速度Scrit。

2.3 錯誤模型與可靠性定義

嵌入式系統(tǒng)任務(wù)執(zhí)行過程中存在永久錯誤和瞬時錯誤。文獻(xiàn)[14]的研究指出，發(fā)生瞬時錯誤的頻率遠(yuǎn)遠(yuǎn)超過永久錯誤，因此只考慮瞬時錯誤。當(dāng)任務(wù)在執(zhí)行過程中發(fā)生了瞬時錯誤，利用時間冗余的方法或重新執(zhí)行任務(wù)來消除錯誤對系統(tǒng)的影響，以確保任務(wù)能夠順利地執(zhí)行。假設(shè)瞬時錯誤可以在任務(wù)執(zhí)行過程中通過一致性檢查技術(shù)檢測[15]，同時假設(shè)檢測的開銷計入任務(wù)最壞情況下的執(zhí)行時間。

文獻(xiàn)[5]的研究指出處理器速度變化會對任務(wù)的出錯概率造成影響，當(dāng)處理器速度降低時，任務(wù)的出錯概率變大。采用文獻(xiàn)[6-7]的任務(wù)發(fā)生錯誤的模型。該模型由下式給出：

其中，λ0是任務(wù)在最大處理器速度Smax下的平均出錯概率，且g(Smax)=1；S是當(dāng)前的處理器速度；g(S)服從指數(shù)分布，其值由下式給出:

式中，d是大于0的系統(tǒng)常數(shù)；Smin為處理器提供的運行速度。

文獻(xiàn)[7]給出了任務(wù)的可靠性定義，即指任務(wù)成功執(zhí)行的概率，對于任務(wù)Ti，其以速度Si執(zhí)行的可靠性由下式給出：

其中，λ(Si)的值由式（2）計算。

任務(wù)Ti的原始可靠性R0i是指任務(wù)以最大的處理器速度執(zhí)行的可靠性，其值為，而系統(tǒng)的原始可靠性是指任務(wù)集中所有任務(wù)原始可靠性的乘積，其值為。

為了確保系統(tǒng)可靠性，文獻(xiàn)[7]提出RA-PM算法來解決這個問題。所謂RA-PM算法是指在降低處理器速度之前，判斷此時的空閑時間是否足夠構(gòu)建恢復(fù)任務(wù)，以確保任務(wù)出現(xiàn)錯誤時能夠重新執(zhí)行該任務(wù)，恢復(fù)任務(wù)始終以最大處理器速度執(zhí)行。如果空閑時間足夠的話，除去構(gòu)建恢復(fù)任務(wù)的時間，將余下的時間用來調(diào)節(jié)處理器速度；否則任務(wù)以最大處理器速度執(zhí)行。對于任務(wù)Ti，以速度Si執(zhí)行，使用RAPM算法，其可靠性由下式給出：

式（5）中，第一部分代表任務(wù)Ti以速度Si執(zhí)行的可靠性；第二部分代表任務(wù)執(zhí)行時出現(xiàn)錯誤，恢復(fù)任務(wù)執(zhí)行的可靠性。從式（5）可以看出，任務(wù)的可靠性得到提高。

研究目標(biāo)：針對n個有資源需求的周期任務(wù)集，在滿足系統(tǒng)實時性、可靠性需求，確保資源被互斥使用的前提下，利用DVS技術(shù)，最大限度地降低系統(tǒng)能耗。

3 靜態(tài)節(jié)能算法

在提出靜態(tài)節(jié)能算法（static saving energy，SSE）之前，先通過一個特例，解釋EDF/DDM算法存在的不足。EDF/DDM算法基于EDF算法，能夠確保資源被互斥使用，但任務(wù)始終以最大的處理器速度執(zhí)行。

在單處理器系統(tǒng)中考慮3個周期任務(wù)的任務(wù)集，每個任務(wù)的參數(shù)信息如下：

其中任務(wù)T1與任務(wù)T3共享資源R1，Utot=0.5，使用資源R1的任務(wù)的最短周期P1=4。假設(shè)所有任務(wù)都在時刻0釋放，在區(qū)間[0,24]利用EDF/DDM算法調(diào)度該任務(wù)集。在時刻0，設(shè)置任務(wù)實例T1,1的ED1,1= ID1,1=4，且其在時刻1完成執(zhí)行。在時刻1，任務(wù)實例T2,1沒有資源需求，其ED2,1=ID2,1=5，且在時刻2完成執(zhí)行。在時刻3，任務(wù)實例T3,1的ID3,1=12，且開始執(zhí)行，設(shè)置ED3,1=7，在時刻3.5完成執(zhí)行。其他任務(wù)實例以相似的方法調(diào)度，最終的調(diào)度結(jié)果如圖1所示。

Fig.1 EDF/DDM algorithm schedules periodic task set圖1EDF/DDM算法調(diào)度周期任務(wù)集

從圖1可以看出，存在大量的空閑時間間隔如[4.5,8]，[10,12]，[18,20]，[21,24]等，可以利用這些空閑時間降低能耗，為此提出靜態(tài)節(jié)能（SEE）算法。在介紹SSE算法之前，先介紹幾個定義。

定義1有資源需求的任務(wù)集合用RT表示，值為RT={Tj|Tj∈T and rj≠0}。

定義2沒有資源需求的任務(wù)集合用NRT表示，值為NRT={Tj|Tj∈T and rj=0}。

定義3在區(qū)間[0,L](Pri＜L＜pi)內(nèi)，使有資源需求的集合RT中所有任務(wù)都能夠滿足其截止期限的最小運行速度用SRT(i)表示。

定義4在區(qū)間[0,L](Pri＜L＜pi)內(nèi)，使沒有資源需求的集合NRT中所有任務(wù)都能夠滿足其截止期限的最小運行速度用SNRT表示。

定義5資源限制的周期任務(wù)集T的最小運行速度用ST表示。

資源限制的周期任務(wù)集T被劃分為兩個子集RT和NRT。借鑒文獻(xiàn)[2]的思想，計算出相應(yīng)集合的最小運行速度。在集合NRT中，任務(wù)沒有資源的需求，其最小的運行速度SNRT由下式計算：

文獻(xiàn)[12]的研究指出對于有資源需求的任務(wù)Ti，在區(qū)間(Pri,pi)中必須滿足以下的條件：

根據(jù)式（7），任務(wù)Ti的最小運行速度為SRT(i)可以通過下式計算：

有資源需求的集合RT中任務(wù)只共享一個資源時，SRT(i)是任務(wù)Ti的最小運行速度。但RT中的任務(wù)共享不同的資源時，任務(wù)Ti的運行速度應(yīng)該是所有有資源需求任務(wù)的最小運行速度中的最大值。該速度用LSRT表示，其值可以由下式計算：

因此，資源限制周期任務(wù)集T的最小運行速度ST可以由下式計算：

算法1 SSE算法

（1）將資源限制周期任務(wù)集T劃分為兩個不相交的子集RT和NRT；

（2）計算最小運行速度ST；

（3）假如ST＜Scrit，ST=Scrit；

（4）假如任務(wù)Ti釋放一個實例，根據(jù)EDF策略將其插入到就緒隊列中；

（5）假如任務(wù)Ti開始執(zhí)行，修改EDi；

（6）任務(wù)Ti始終以速度ST執(zhí)行。

SSE算法計算ST，其時間復(fù)雜度為O(m)，而根據(jù)EDF策略將任務(wù)插入到就緒隊列中，其時間復(fù)雜度為O(nlbn)。因此，SSE算法的時間復(fù)雜度為O(nlb(n+m))。

利用EDF/DDM算法的實例來解釋SSE算法。該資源限制的周期任務(wù)集T被劃分為RT={T1,T3}和NRT={T2}，根據(jù)式（6），SNRT=0.125；根據(jù)式（8），SRT(3)= 0.499 4；根據(jù)式（9），LSRT=0.499 4；根據(jù)式（10），ST=0.62。利用SSE算法調(diào)度任務(wù)集T的結(jié)果如圖2所示。

Fig.2 SSE algorithm schedules periodic task set圖2 SSE算法調(diào)度周期任務(wù)集

使用文獻(xiàn)[3]所提出的功耗模型,該功耗模型為P=0.08+1.52×S3，關(guān)鍵速度Scrit=0.3，處理器處于空閑狀態(tài)的功耗為0.085。EDF/DDM算法調(diào)度周期任務(wù)集的總能耗為22.49，而SSE算法調(diào)度周期任務(wù)集的總能耗為8.95。因此，SSE算法比EDF/DDM算法的能耗少60.20%。

SSE算法可行的必要條件由以下的定理給出。

引理1資源限制的周期任務(wù)集T，假設(shè)周期任務(wù)的相對截止期限等于周期。SSE算法調(diào)度T是可行的，必須滿足以下條件：

（1）Utot＜1；

（2）資源限制的周期任務(wù)集的最小運行速度ST滿足以下條件：

證明張憶文等人在文獻(xiàn)[2]中給出了調(diào)度資源限制偶發(fā)任務(wù)集可行的必要條件，且給出了證明。而資源限制周期任務(wù)集是資源限制偶發(fā)任務(wù)集的特例。詳細(xì)的證明過程請參見文獻(xiàn)[2]。 □

4 兩種啟發(fā)式算法

SSE算法將所有的空閑時間用來降低系統(tǒng)能耗，沒有考慮處理器速度對系統(tǒng)可靠性造成的影響。文獻(xiàn)[5]的研究指出處理器速度降低時，任務(wù)的出錯概率變大。在提出解決方案之前，先證明可靠性感知周期任務(wù)低能耗調(diào)度問題是NP難的。

引理2資源限制周期任務(wù)可靠性感知低能耗調(diào)度（reliability-aware low power scheduling for periodic tasks with shared resources，RMLPSR）問題是NP難的。

證明文獻(xiàn)[7]針對共享同一截止期限的相互獨立周期任務(wù)可靠性感知低能耗調(diào)度（RA-MP）問題開展研究，并且證明了該調(diào)度問題是NP難的。而RAMP是RMLPSR問題的一個特例，因此定理得證。□

考慮到RMLPSR問題是NP難的，為此提出啟發(fā)式算法來解決這個問題。解決RMLPSR問題需要考慮兩個問題：其一，哪些任務(wù)可以降低處理器速度（縮放任務(wù)）？其二，縮放任務(wù)的運行速度如何確定？

針對第一個問題提出兩個啟發(fā)式策略：其一，最長執(zhí)行時間優(yōu)先算法（longest execution time first，LETF），即將最壞情況下執(zhí)行時間（worst case execution time,WCET）最大的任務(wù)作為縮放任務(wù)，當(dāng)任務(wù)的WCET相同時，下標(biāo)小的任務(wù)作為縮放任務(wù)；其二，最短執(zhí)行時間優(yōu)先（shortest execution time first，SETF）算法，即將WCET最小的任務(wù)作為縮放任務(wù)，當(dāng)任務(wù)的WCET相同時，下標(biāo)小的任務(wù)作為縮放任務(wù)。針對第二個問題，將空閑時間首先用來構(gòu)建縮放任務(wù)的恢復(fù)任務(wù)（recover task，RK），余下的空閑時間用來調(diào)節(jié)處理器速度。當(dāng)周期任務(wù)Ti被選為縮放任務(wù)時，空閑時間將用于構(gòu)建其恢復(fù)任務(wù)RKi，剩余的空閑時間將用于調(diào)節(jié)處理器速度?；謴?fù)任務(wù)RKi的執(zhí)行時間等于Ti的WCET，且其截止期限等于Ti的截止期限。為了確保系統(tǒng)可靠性，恢復(fù)任務(wù)始終以最大的處理器速度執(zhí)行。如果此時的空閑時間不足以用來構(gòu)建恢復(fù)任務(wù)RKi，縮放任務(wù)將以最大的處理器速度執(zhí)行。

資源限制的周期任務(wù)集T的最小運行速度ST可以通過式（10）計算。所有的任務(wù)都以最大的處理器速度Smax(ST≤Smax)執(zhí)行，這時會產(chǎn)生靜態(tài)空閑時間。對于周期任務(wù)Ti，在此每一個調(diào)度周期內(nèi)，所產(chǎn)生的空閑時間ST可以通過式（11）計算：

其中，EDi是任務(wù)Ti的執(zhí)行截止期限；tb是周期任務(wù)Ti的釋放時刻。當(dāng)ST大于任務(wù)Ti的ei時，構(gòu)建恢復(fù)任務(wù)RKi，余下的空閑時間ST-ei用來調(diào)節(jié)處理器速度。

LETF算法和SETF算法都是基于SSE算法，通過利用系統(tǒng)產(chǎn)生的空閑時間，構(gòu)建恢復(fù)任務(wù)，確保系統(tǒng)可靠性，以及利用空閑時間，降低系統(tǒng)能耗。利用EDF/DDM算法所用的實例來解釋LETF算法和SETF算法。在這個實例中，ST=0.62。LETF算法和SETF算法在區(qū)間[0,24]調(diào)度該任務(wù)集的最終調(diào)度結(jié)果分別如圖3和圖4所示。

Fig.3 LETF algorithm schedules periodic task set圖3 LETF算法調(diào)度任務(wù)集

Fig.4 SETF algorithm schedules periodic task set圖4 SETF算法調(diào)度任務(wù)集

在圖3中，任務(wù)T3被選為縮放任務(wù)。在時刻2，任務(wù)T3的執(zhí)行截止期限和釋放時刻分別為7和0。因此，在第一個截止期限內(nèi)可以利用的空閑時間ST為(1-0.62)×(7-0)=2.66?？梢杂脕碚{(diào)節(jié)處理器速度的空閑時間為2.66-1.5=1.16。此時任務(wù)T3以速度1.5/(1.5+1.16)=0.56執(zhí)行。在時刻13，任務(wù)T3的執(zhí)行截止期限和釋放時刻分別為18和12。因此，在第二個截止期限內(nèi)可以利用的空閑時間 ST為(1-0.62)×(18-12)=2.28?？梢杂脕碚{(diào)節(jié)處理器速度的空閑時間為2.28-1.5=0.78。此時任務(wù)T3以速度1.5/(1.5+0.78)=0.66執(zhí)行。

在圖4中，任務(wù)T1被選為縮放任務(wù)。在時刻0，任務(wù)T1的執(zhí)行截止期限和釋放時刻分別為4和0。因此，在第一個截止期限內(nèi)可以利用的空閑時間ST為(1-0.62)×(4-0)=1.52?？梢杂脕碚{(diào)節(jié)處理器速度的空閑時間為1.52-1=0.52。此時任務(wù)T1以速度1/(1+0.52)=0.66執(zhí)行。在時刻5.02，任務(wù)T1的執(zhí)行截止期限和釋放時刻分別為8和4。因此，在第二個截止期限內(nèi)可以利用的空閑時間ST為(1-0.62)× (8-4)=1.52。可以用來調(diào)節(jié)處理器速度的空閑時間為1.52-1=0.52。此時任務(wù)T1以速度1/(1+0.52)= 0.66執(zhí)行。其他任務(wù)實例以相似的方法進(jìn)行調(diào)度，這里不再贅述。

為了更好地評價所提出算法的性能[7]，引入以下的概念。

定義6任務(wù)Ti的原始出錯概率用Fi0表示，值為。

定義7任務(wù)Ti在速度Si下的出錯概率用Fi(Si)表示，值為Fi(Si)=1-Ri(Si)。

定義8資源限制的周期任務(wù)集T的原始出錯概率用TF0表示，值為，其中ki為周期任務(wù)Ti的任務(wù)實例的個數(shù)。

定義9存在縮放任務(wù)的資源限制的周期任務(wù)集T的出錯概率用TF表示，值為T，其中ki為周期任務(wù)Ti的任務(wù)實例的個數(shù)。

利用文獻(xiàn)[14]的研究成果，假設(shè)λ0=10-6,d=2。通過計算可知。對于任務(wù)Ti而言，不同的實例其可靠性是不同的，簡單起見，選擇最小的可靠性作為這些任務(wù)實例的可靠性。在SSE算法中，通過計算可知任務(wù)T1、T2和T3的出錯概率。這意味著任務(wù)T1、T2和T3的出錯概率是EDF/DDM算法的相應(yīng)任務(wù)出錯概率的27.68倍、27.68倍和97.07倍。此外，計算出存在縮放任務(wù)的資源限制的周期任務(wù)集T的出錯概率TF=45.01TF0。至此可以看出，SSE算法的出錯概率是EDF/DDM算法的45.01倍，而它的能耗比EDF/DDM算法少60.22%。其他算法的能耗以及出錯概率用相似的方法計算，最終的結(jié)果參見表1。

Table 1 Energy consumption and probability of failure表1 能耗與出錯概率

從表1中可以看出，SETF算法的出錯概率最低，且相對于EDF/DDM算法可以節(jié)約33.00%的能耗。此外，SETF算法和LETF算法的能耗都高于SSE算法的能耗，但它們的出錯概率都遠(yuǎn)遠(yuǎn)低于SSE算法的出錯概率。

5 仿真實驗

利用C語言實現(xiàn)一個基于EDF/DDM調(diào)度策略的周期任務(wù)調(diào)度仿真器，該仿真器基于PXA270處理器。PXA270處理器的功耗模型[3]：P=0.08+1.52×S3，該功耗模型的關(guān)鍵速度Scrit=0.3，處理器處于空閑狀態(tài)的功耗為0.085。在該仿真器中實現(xiàn)4種調(diào)度算法：（1）EDF/DDM算法，該算法所有任務(wù)都以最大處理器速度執(zhí)行；（2）SSE算法，該算法基于EDF/DDM算法，且所有任務(wù)都以速度ST執(zhí)行，但其忽略了速度對系統(tǒng)可靠性的影響；（3）LETF算法，該算法基于SSE算法，考慮了速度對系統(tǒng)可靠性的影響，且WCET最大的任務(wù)被選為縮放任務(wù)；（4）SETF算法，該算法基于SSE算法，考慮了速度對系統(tǒng)可靠性的影響，且WCET最小的任務(wù)被選為縮放任務(wù)。

以文獻(xiàn)[16]的數(shù)控系統(tǒng)任務(wù)集為研究對象，該任務(wù)集包含8個周期任務(wù)，每個周期任務(wù)Ti的周期 pi在[2.4,9.6]中隨機選取。為了更好地評價各個算法的性能，周期任務(wù)Ti在最壞情況下的執(zhí)行時間從0.035到其周期 pi中選取。假設(shè)資源任務(wù)集有兩個資源，也就是R={R1,R2}。同時假設(shè)，任務(wù)T1和任務(wù)T8共享資源R1，任務(wù)T2和任務(wù)T7共享資源R2。在每個實驗中設(shè)置λ0=10-6,d=2。設(shè)置仿真實驗的時間為1 000 000個時間片，每次仿真實驗產(chǎn)生10個任務(wù)集，以這10個任務(wù)集實驗結(jié)果的平均值作為最終的實驗結(jié)果。在實驗中任務(wù)的出錯概率等于執(zhí)行失敗的任務(wù)的個數(shù)除以所有執(zhí)行的任務(wù)的總個數(shù)。

在實驗中，設(shè)置系統(tǒng)利用率從0.1到0.8，考察系統(tǒng)利用率對算法能耗和出錯概率的影響。實驗結(jié)果如圖5和圖6所示。

Fig.5 System utilization effects on algorithm energy consumption圖5 系統(tǒng)利用率對算法能耗的影響

Fig.6 System utilization effects on algorithm probability of failure圖6 系統(tǒng)利用率對算法出錯概率的影響

在圖5中，以EDF/DDM算法在系統(tǒng)利用率等于0.8時的能耗為基準(zhǔn)進(jìn)行歸一化。從圖5中可以看出，所有算法的歸一化能耗都受到系統(tǒng)利用率的影響。系統(tǒng)利用率上升時，算法的歸一化能耗也上升。這是因為系統(tǒng)利用率越高，任務(wù)的執(zhí)行時間就越長，能耗也就增加。此外，SSE算法的歸一化能耗低于其他算法的歸一化能耗。這是因為該算法將所有的空閑時間用來降低系統(tǒng)能耗，忽略了速度對系統(tǒng)可靠性的影響。SETF和LETF算法的歸一化能耗均低于EDF/DDM算法的歸一化能耗。同時，LETF算法的歸一化能耗低于SETF算法的歸一化能耗。總之，SSE算法比EDF/DDM算法節(jié)約21.73%～66.36%的能耗，且SETF算法和LETF算法比EDF/ DDM算法分別節(jié)約3.61%和13.36%的能耗。

從圖6中可以看出，所有算法的出錯概率都受到系統(tǒng)利用率的影響。隨著系統(tǒng)利用率的上升，EDF/ DDM算法、SETF算法、LETF算法的出錯概率都增加。這是因為系統(tǒng)利用率越高，導(dǎo)致任務(wù)的執(zhí)行時間增加，從而任務(wù)的出錯概率增加。對于SSE算法而言，當(dāng)系統(tǒng)利用率低于0.3時，出錯概率上升。這是因為該算法的運行速度受到關(guān)鍵速度(Scrit=0.3)的限制。當(dāng)系統(tǒng)利用率大于0.3，該算法的出錯概率下降。這是因為系統(tǒng)利用率越高，導(dǎo)致任務(wù)的靜態(tài)空閑時間越少，從而任務(wù)將以更高的速度運行。此外，LETF算法的出錯概率總是低于SETF算法的出錯概率?？傊?，SSE算法的出錯概率是EDF/DDM算法的80.01倍，而SETF算法和LETF算法的出錯概率比EDF/DDM算法低，是它的97%和76%，也就是說SETF算法和LETF算法與EDF/DDM算法相比，系統(tǒng)可靠性得到提高。

6 結(jié)束語

針對EDF/DDM算法存在的不足，提出能夠回收空閑時間的SSE算法。針對SSE算法存在的不足，在證明可靠性感知資源受限周期任務(wù)調(diào)度問題是NP難之后，提出兩種啟發(fā)式算法：LETF算法和SETF算法。仿真實驗表明所提算法的能耗均低于EDF/ DDM算法的能耗。此外，SETF算法和LETF算法的出錯概率比EDF/DDM算法低，這意味著系統(tǒng)的可靠性得到提高。因為SETF算法和LETF算法假設(shè)任務(wù)始終以其最壞情況下執(zhí)行時間執(zhí)行，而任務(wù)真實執(zhí)行時間小于其最壞情況下的執(zhí)行時間，所以會產(chǎn)生動態(tài)空閑時間。能夠回收動態(tài)空閑時間的可靠性感知資源受限周期任務(wù)動態(tài)調(diào)度算法，將是下一步的研究工作。

[1]Yao F,Demers A,Shenker S.A scheduling model for reduced CPU energy[C]//Proceedings of the 36th Annual Symposium on Foundations of Computer Science,Milwaukee,USA, Oct 23-25,1995.Piscataway,USA:IEEE,1995:374-382.

[2]Zhang Yiwen,Guo Ruifeng.Low-power scheduling algorithms for sporadic task with shared resources in hard real-time systems[J].The Computer Journal,2015,58(7):1585-1597.

[3]Chen Jianjia,Kuo Teiwei.Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems[C]//Proceedings of the 2007 International Conference on Computer-Aided Design,San Jose,USA, Nov 5-8,2007.Piscataway,USA:IEEE,2007:289-294.

[4]Zhang Yiwen,Guo Ruifeng.A scheduling algorithm with low power for periodic tasks in hard real-time system[J]. Journal of Xi’an Jiaotong University,2014,48(7):90-95.

[5]Zhu Dakai,Melhem R,Mossé D.The effects of energy management on reliability in real-time embedded systems[C]// Proceedings of the 2004 International Conference on Computer-Aided Design,San Jose,USA,Nov 7-11,2004.Piscataway,USA:IEEE,2004:35-40.

[6]Zhu Dakai,Aydin H.Energy management for real-time embedded systems with reliability requirements[C]//Proceedings of the 2006 International Conference on Computer-Aided Design,San Jose,USA,Nov 5-9,2006.Piscataway, USA:IEEE,2006:528-534.

[7]Zhu Dakai,Aydin H.Reliability-aware energy management for periodic real-time tasks[J].IEEE Transactions on Computers,2009,58(10):1382-1397.

[8]Luo Jun,Liu Yongfeng,Fu Li.Reliability-aware schedule of periodic tasks in energy-constrained real-time systems[J]. Journal of Chongqing University,2011,34(8):86-90.

[9]Zhu Dakai.Reliability-aware dynamic energy management in dependable embedded real-time systems[C]//Proceedings of the 12th Real-Time and Embedded Technology and Applications Symposium,San Jose,USA,Apr 4-7,2006.Piscataway,USA:IEEE,2006:397-497.

[10]Zhao Baoxian,Aydin H,Zhu Dakai.Energy management under general task-level reliability constraints[C]//Proceedings of the 18th Real-Time and Embedded Technology and Applications Symposium,Beijing,Apr 16-19,2012.Piscataway,USA:IEEE,2012:285-294.

[11]Sha L,Rajkumar R,Lehoczky J P.Priority inheritance protocols:an approach to real-time synchronization[J].IEEE Transactions on Computers,1990,39(9):1175-1185.

[12]Jeffay K.Scheduling sporadic tasks with shared resources in hard-real-time systems[C]//Proceedings of the Real-Time Systems Symposium,Phoenix,USA,Dec 2-4,1992.Piscataway,USA:IEEE,1992:89-99.

[13]Huang C S,Kuo Y H,Hu J W.Scheduling sporadic,hard real-time tasks with resources[C]//Proceedings of the 3rd International Conference on Innovative Computing Information and Control,Dalian,China,Jun 18-20,2008.Piscataway, USA:IEEE,2008:84-87.

[14]Castillo X,McConnel S R,Siewiorek D P.Derivation and calibration of a transient error reliability model[J].IEEE Transactions on Computers,1982,31(7):658-671.

[15]Pradhan D K.Fault tolerance computing:theory and techniques[M].Upper Saddle River,USA:Prentice Hall,1986.

[16]Kim N,Ryu M,Hong S,et al.Visual assessment of a realtime system design:a case study on a CNC controller[C]// Proceedings of the 17th Real-Time Systems Symposium, Washington,Dec 4-6,1996.Piscataway,USA:IEEE,1996: 300-310.

附中文參考文獻(xiàn)：

[4]張憶文,郭銳鋒.硬實時系統(tǒng)周期任務(wù)低功耗調(diào)度算法[J].西安交通大學(xué)學(xué)報,2014,48(7):90-95.

[8]羅鈞,劉永鋒,付麗.能耗限制的實時周期任務(wù)可靠性感知調(diào)度[J].重慶大學(xué)學(xué)報,2011,34(8):86-90.

ZHANG Yiwen was born in 1988.He received the Ph.D.degree from University of Chinese Academy of Sciences in 2016.Now he is a lecturer at College of Computer Science and Technology,Huaqiao University,and the member of CCF.His research interests include real-time system and low-power scheduling.

張憶文（1988—），男，福建周寧人，2016年于中國科學(xué)院大學(xué)獲得博士學(xué)位，現(xiàn)為華僑大學(xué)計算機科學(xué)與技術(shù)學(xué)院講師，CCF會員，主要研究領(lǐng)域為實時系統(tǒng)，綠色計算。主持華僑大學(xué)科研啟動項目1項，參與核高基國家科技重大專項1項、國家科技支撐計劃1項，發(fā)表學(xué)術(shù)論文16篇，其中SCI/EI檢索12篇，申請發(fā)明專利15項，授權(quán)2項，出版學(xué)術(shù)專著1部，獲得1項軟件著作權(quán)。

WANG Cheng was born in 1984.He received the Ph.D.degree in mechanics from Xi’an Jiaotong University in 2012.Now he is an associate professor and M.S.supervisor at Huaqiao University,and the senior member of CCF. His research interests include signal processing and artificial intelligence.

王成（1984—），男，湖北通城人，2012年于西安交通大學(xué)獲得博士學(xué)位，現(xiàn)為華僑大學(xué)計算機科學(xué)與技術(shù)學(xué)院碩士生導(dǎo)師、副教授，CCF高級會員，主要研究領(lǐng)域為信號處理，人工智能。主持國家自然科學(xué)基金1項、福建省面上項目1項、華僑大學(xué)科研啟動項目1項，發(fā)表學(xué)術(shù)論文20余篇。

Reliability-Aware Energy Management SchedulingAlgorithm for Periodic Task*

ZHANG Yiwen+,WANG Cheng
College of Computer Science and Technology,Huaqiao University,Xiamen,Fujian 361021,China

+Corresponding author:E-mail:zyw@hqu.edu.cn

ZHANG Yiwen,WANG Cheng.Reliability-aware energy management scheduling algorithm for periodic task. Journal of Frontiers of Computer Science and Technology,2017,11(5)：833-841.

Aiming at the shortcoming of the EDF/DDM(earliest deadline first/dynamic deadline modify)algorithm which can't use the slack time to reduce the energy consumption,this paper proposes the SSE(static saving energy) algorithm which can reclaim the slack time.But,it ignores that the processor speed has a negative effect on the system reliability.This paper proves that the problem of reliability-aware resource-constrained low-power periodic task scheduling is NP-hard.Furthermore,this paper presents two heuristic algorithms:LETF(longest execution time first)algorithm and SETF(shortest execution time first)algorithm.The simulation results show that the energy consumption of the LETF algorithm and the SETF algorithm is lower than that of the EDF/DDM algorithm.In addition, the probability of failure of the LETF algorithm and the SETF algorithm is 97%and 76%lower than that of the EDF/DDM algorithm,respectively.It means that the system reliability is improved.

energy consumption;reliability-aware;resource constrained;real-time scheduling

10.3778/j.issn.1673-9418.1609039

A

TP316.2

*The National Natural Science Foundation of China under Grant No.51305142(國家自然科學(xué)基金);the Introduction Talents Scientific Research Projects of Huaqiao University under Grant No.16BS104(華僑大學(xué)引進(jìn)人才科研啟動項目).

Received 2016-09,Accepted 2016-12.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-12-07,http://www.cnki.net/kcms/detail/11.5602.TP.20161207.0922.014.html