張憶文，王 成

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

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

張憶文+，王 成

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

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

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

1 引言

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

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

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

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

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

2.1 任務(wù)模型

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

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

2.2 功耗模型

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

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

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

2.3 錯(cuò)誤模型與可靠性定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1 SSE算法

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

（2）計(jì)算最小運(yùn)行速度ST；

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

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

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

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

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

利用EDF/DDM算法的實(shí)例來(lái)解釋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ù)的相對(duì)截止期限等于周期。SSE算法調(diào)度T是可行的，必須滿(mǎn)足以下條件：

（1）Utot＜1；

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

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

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

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

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

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

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

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

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

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

LETF算法和SETF算法都是基于SSE算法，通過(guò)利用系統(tǒng)產(chǎn)生的空閑時(shí)間，構(gòu)建恢復(fù)任務(wù)，確保系統(tǒng)可靠性，以及利用空閑時(shí)間，降低系統(tǒng)能耗。利用EDF/DDM算法所用的實(shí)例來(lái)解釋LETF算法和SETF算法。在這個(gè)實(shí)例中，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ù)。在時(shí)刻2，任務(wù)T3的執(zhí)行截止期限和釋放時(shí)刻分別為7和0。因此，在第一個(gè)截止期限內(nèi)可以利用的空閑時(shí)間ST為(1-0.62)×(7-0)=2.66。可以用來(lái)調(diào)節(jié)處理器速度的空閑時(shí)間為2.66-1.5=1.16。此時(shí)任務(wù)T3以速度1.5/(1.5+1.16)=0.56執(zhí)行。在時(shí)刻13，任務(wù)T3的執(zhí)行截止期限和釋放時(shí)刻分別為18和12。因此，在第二個(gè)截止期限內(nèi)可以利用的空閑時(shí)間 ST為(1-0.62)×(18-12)=2.28?？梢杂脕?lái)調(diào)節(jié)處理器速度的空閑時(shí)間為2.28-1.5=0.78。此時(shí)任務(wù)T3以速度1.5/(1.5+0.78)=0.66執(zhí)行。

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

為了更好地評(píng)價(jià)所提出算法的性能[7]，引入以下的概念。

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

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

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

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

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

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

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

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

利用C語(yǔ)言實(shí)現(xiàn)一個(gè)基于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。在該仿真器中實(shí)現(xiàn)4種調(diào)度算法：（1）EDF/DDM算法，該算法所有任務(wù)都以最大處理器速度執(zhí)行；（2）SSE算法，該算法基于EDF/DDM算法，且所有任務(wù)都以速度ST執(zhí)行，但其忽略了速度對(duì)系統(tǒng)可靠性的影響；（3）LETF算法，該算法基于SSE算法，考慮了速度對(duì)系統(tǒng)可靠性的影響，且WCET最大的任務(wù)被選為縮放任務(wù)；（4）SETF算法，該算法基于SSE算法，考慮了速度對(duì)系統(tǒng)可靠性的影響，且WCET最小的任務(wù)被選為縮放任務(wù)。

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

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

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

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

在圖5中，以EDF/DDM算法在系統(tǒng)利用率等于0.8時(shí)的能耗為基準(zhǔn)進(jìn)行歸一化。從圖5中可以看出，所有算法的歸一化能耗都受到系統(tǒng)利用率的影響。系統(tǒng)利用率上升時(shí)，算法的歸一化能耗也上升。這是因?yàn)橄到y(tǒng)利用率越高，任務(wù)的執(zhí)行時(shí)間就越長(zhǎng)，能耗也就增加。此外，SSE算法的歸一化能耗低于其他算法的歸一化能耗。這是因?yàn)樵撍惴▽⑺械目臻e時(shí)間用來(lái)降低系統(tǒng)能耗，忽略了速度對(duì)系統(tǒng)可靠性的影響。SETF和LETF算法的歸一化能耗均低于EDF/DDM算法的歸一化能耗。同時(shí)，LETF算法的歸一化能耗低于SETF算法的歸一化能耗?？傊琒SE算法比EDF/DDM算法節(jié)約21.73%～66.36%的能耗，且SETF算法和LETF算法比EDF/ DDM算法分別節(jié)約3.61%和13.36%的能耗。

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

6 結(jié)束語(yǔ)

針對(duì)EDF/DDM算法存在的不足，提出能夠回收空閑時(shí)間的SSE算法。針對(duì)SSE算法存在的不足，在證明可靠性感知資源受限周期任務(wù)調(diào)度問(wèn)題是NP難之后，提出兩種啟發(fā)式算法：LETF算法和SETF算法。仿真實(shí)驗(yàn)表明所提算法的能耗均低于EDF/ DDM算法的能耗。此外，SETF算法和LETF算法的出錯(cuò)概率比EDF/DDM算法低，這意味著系統(tǒng)的可靠性得到提高。因?yàn)镾ETF算法和LETF算法假設(shè)任務(wù)始終以其最壞情況下執(zhí)行時(shí)間執(zhí)行，而任務(wù)真實(shí)執(zhí)行時(shí)間小于其最壞情況下的執(zhí)行時(shí)間，所以會(huì)產(chǎn)生動(dòng)態(tài)空閑時(shí)間。能夠回收動(dòng)態(tài)空閑時(shí)間的可靠性感知資源受限周期任務(wù)動(dòng)態(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]張憶文,郭銳鋒.硬實(shí)時(shí)系統(tǒng)周期任務(wù)低功耗調(diào)度算法[J].西安交通大學(xué)學(xué)報(bào),2014,48(7):90-95.

[8]羅鈞,劉永鋒,付麗.能耗限制的實(shí)時(shí)周期任務(wù)可靠性感知調(diào)度[J].重慶大學(xué)學(xué)報(bào),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年于中國(guó)科學(xué)院大學(xué)獲得博士學(xué)位，現(xiàn)為華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院講師，CCF會(huì)員，主要研究領(lǐng)域?yàn)閷?shí)時(shí)系統(tǒng)，綠色計(jì)算。主持華僑大學(xué)科研啟動(dòng)項(xiàng)目1項(xiàng)，參與核高基國(guó)家科技重大專(zhuān)項(xiàng)1項(xiàng)、國(guó)家科技支撐計(jì)劃1項(xiàng)，發(fā)表學(xué)術(shù)論文16篇，其中SCI/EI檢索12篇，申請(qǐng)發(fā)明專(zhuān)利15項(xiàng)，授權(quán)2項(xiàng)，出版學(xué)術(shù)專(zhuān)著1部，獲得1項(xiàng)軟件著作權(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é)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士生導(dǎo)師、副教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)樾盘?hào)處理，人工智能。主持國(guó)家自然科學(xué)基金1項(xiàng)、福建省面上項(xiàng)目1項(xiàng)、華僑大學(xué)科研啟動(dòng)項(xiàng)目1項(xiàng)，發(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(國(guó)家自然科學(xué)基金);the Introduction Talents Scientific Research Projects of Huaqiao University under Grant No.16BS104(華僑大學(xué)引進(jìn)人才科研啟動(dòng)項(xiàng)目).

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