資源受限周期任務(wù)雙速度調(diào)度算法

張憶文，吳文江，郭銳鋒

1(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所，沈陽 110168) 2(華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 廈門 361021)

1 引 言

實(shí)時(shí)系統(tǒng)已經(jīng)廣泛應(yīng)用于工業(yè)控制、航空航天、通信等行業(yè).實(shí)時(shí)系統(tǒng)按照任務(wù)釋放實(shí)例的特點(diǎn)，可以將任務(wù)劃分為周期任務(wù)、偶發(fā)任務(wù)和混合任務(wù)等.隨著技術(shù)的發(fā)展，實(shí)時(shí)系統(tǒng)的能耗越來越高，已經(jīng)成為系統(tǒng)發(fā)展的瓶頸.動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)[1]根據(jù)系統(tǒng)的實(shí)時(shí)負(fù)載，通過動(dòng)態(tài)調(diào)節(jié)處理器速度，降低處理器能耗，是解決系統(tǒng)能耗問題的重要技術(shù).

文獻(xiàn)[1-6]將實(shí)時(shí)調(diào)度理論與動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)結(jié)合起來，降低系統(tǒng)能耗.但這些工作都假設(shè)任務(wù)之間是相互獨(dú)立，沒有考慮任務(wù)之間的共享資源問題.事實(shí)上，在實(shí)時(shí)系統(tǒng)中，任務(wù)之間由于共享資源而存在相互依賴關(guān)系.文獻(xiàn)[7,8]研究了任務(wù)的資源共享問題，但這些研究主要針對(duì)偶發(fā)任務(wù)模型.針對(duì)周期任務(wù)模型的資源共享問題的研究相對(duì)較少.文獻(xiàn)[9,10]通過利用動(dòng)態(tài)優(yōu)先級(jí)策略調(diào)度周期任務(wù)，且所有任務(wù)在執(zhí)行過程中都以單一的速度執(zhí)行.這些研究工作不能適用于采用固定優(yōu)先級(jí)調(diào)度策略的系統(tǒng)，且節(jié)能效果差.

針對(duì)現(xiàn)有基于動(dòng)態(tài)優(yōu)先級(jí)策略資源受限周期任務(wù)能耗優(yōu)化算法不能適用于固定優(yōu)先級(jí)系統(tǒng)，且節(jié)能效果差等不足，提出RCPTDSSA.該算法基于RM/DPP算法，使用雙速度策略調(diào)度任務(wù)，利用動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)降低能耗.任務(wù)開始以低速度執(zhí)行，當(dāng)有阻塞發(fā)生時(shí)切換到高速度執(zhí)行，且被阻塞的任務(wù)也以高速度執(zhí)行.

2 系統(tǒng)模型

2.1 任務(wù)模型

2.2 處理器模型和能耗模型

P=Ps+h(Pind+CefSm)

(1)

3 雙優(yōu)先級(jí)單調(diào)速率調(diào)度算法

文獻(xiàn)[7,8]提出了RM/DPP算法，該算法基于RM策略，利用搶占閾值的思想，通過設(shè)置任務(wù)的優(yōu)先級(jí)，確保資源互斥訪問.在RM/DPP算法中，每個(gè)周期任務(wù)Ti有兩個(gè)優(yōu)先級(jí)：初始優(yōu)先級(jí)(IPi)和執(zhí)行優(yōu)先級(jí)(EPi).初始優(yōu)先級(jí)根據(jù)RM策略進(jìn)行分配，任務(wù)的周期越小，其優(yōu)先級(jí)就越高，反之，其優(yōu)先級(jí)越低.執(zhí)行優(yōu)先級(jí)是在任務(wù)開始執(zhí)行時(shí)分配.

先通過一個(gè)實(shí)例解釋RM/DPP算法.考慮有3個(gè)周期任務(wù)的任務(wù)集，其具體信息如下：

T1(1，1，4)，T2(1，0，5)，T3(3，1，20)

該任務(wù)集的系統(tǒng)利用Utot=0.6，周期任務(wù)T1與周期任務(wù)T3共享資源R1，周期任務(wù)T2沒有資源需求.假設(shè)所有的周期任務(wù)都在時(shí)刻0釋放其任務(wù)實(shí)例.在區(qū)間[0，20]利用RM/DPP算法調(diào)度該周期任務(wù)集.周期任務(wù)T1、T2以及T3的初始優(yōu)先級(jí)分別為3，2，1.使用共享資源R1的所有周期任務(wù)的最大初始優(yōu)先級(jí)π1=3.在時(shí)刻0，周期任務(wù)T1、T2以及T3同時(shí)釋放實(shí)例，周期任務(wù)T1的初始優(yōu)先級(jí)最高，其最先執(zhí)行，且在時(shí)刻1完成執(zhí)行.在時(shí)刻2，周期任務(wù)T2完成執(zhí)行.在時(shí)刻2，周期任務(wù)T3開始執(zhí)行，由于其共享資源R1，所以其執(zhí)行優(yōu)先級(jí)被修改為3.盡管在時(shí)刻4，周期任務(wù)T1釋放實(shí)例，但其初始優(yōu)先級(jí)不大于周期任務(wù)T3的執(zhí)行優(yōu)先級(jí)，所以不能搶占其執(zhí)行，也就是說周期任務(wù)T1被周期任務(wù)T3阻塞.其他任務(wù)以相似的方法調(diào)度.RM/DPP算法調(diào)度周期任務(wù)集的最終結(jié)果如圖1所示.

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

從圖1可以看出，RM/DPP算法調(diào)度任務(wù)始終以最大的處理器速度執(zhí)行，造成很多空閑間隔如[7，8]、[9，10]、[11，12]、[13，15]以及[17，20]，浪費(fèi)了系統(tǒng)資源.接下來提出節(jié)能效果更好的RCPTDSSA算法.

4 RCPTDSSA算法

4.1 準(zhǔn)備工作

4.2 計(jì)算SL和SH

定理1[12].RM算法調(diào)度具有n個(gè)相互獨(dú)立周期任務(wù)的周期任務(wù)集是可行，其必須滿足以下條件：

Utot≤LLB(n)

(2)

根據(jù)定理1，SL可以通過下式計(jì)算；

(3)

定理2[13]. 基于RM調(diào)度策略的算法調(diào)度具有n個(gè)資源受限周期任務(wù)的周期任務(wù)集是可行，其必須滿足以下條件：

(4)

根據(jù)定理2，SH可以通過下式計(jì)算；

(5)

4.3 RCPTDSSA算法描述

所提出的RCPTDSSA算法基于RM/DPP算法，周期任務(wù)在執(zhí)行時(shí)沒有阻塞發(fā)生，其以低速度SL執(zhí)行，發(fā)生阻塞時(shí)其以高速度SH執(zhí)行，直到完成執(zhí)行，且被阻塞的周期任務(wù)也以高速度SH執(zhí)行.

算法1.RCPTDSSA算法

1) 計(jì)算低速度SL和高速度SH；

2) 當(dāng)SL

3) 當(dāng)SL>SH，SH=SL；// 確保高速度不低于低速度

4) 當(dāng)SH>1.0，SH=1.0； //確保高速度不超過處理器提供的最大速度.

5) 當(dāng)周期任務(wù)Ti釋放一個(gè)實(shí)例，根據(jù)RM策略將其插入到就緒隊(duì)列；

6) 周期任務(wù)Ti開始以低速度SL執(zhí)行，且修改其執(zhí)行優(yōu)先級(jí)；

7) 當(dāng)周期任務(wù)Ti阻塞周期任務(wù)Tk的執(zhí)行時(shí)，周期任務(wù)Ti以高速度SH執(zhí)行，直到其完成執(zhí)行；此時(shí)，周期任務(wù)Tk也以高速度SH執(zhí)行，直到其完成執(zhí)行.

RCPTDSSA算法的時(shí)間復(fù)雜度主要由計(jì)算低速度SL和高速度SH以及RM/DPP算法調(diào)度任務(wù)兩部分組成.計(jì)算低速度SL和高速度SH的時(shí)間復(fù)雜度分別為O(n)和O(n2)；而RM/DPP算法調(diào)度任務(wù)的時(shí)間復(fù)雜度為O(nlogn).因此，RCPTDSSA算法的時(shí)間復(fù)雜度為O(n2).

4.4 RCPTDSSA算法實(shí)例

在證明RCPTDSSA算法可行性之前，先介紹幾個(gè)引理.

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

(6)

證明：參見文獻(xiàn)[13].

?t∈U={mpi|i=1，…，k；m=1，…，?pk/pi」}，則下式成立：

(7)

證明：參見文獻(xiàn)[13].

定理3.周期任務(wù)集T按照其周期進(jìn)行非降序排序，共享m個(gè)連續(xù)可重用資源的資源集合R={R1，R2，…，Rm}，其假設(shè)周期任務(wù)的相對(duì)截止期限等于其周期；RCPTDSSA算法以低速度SL和高速度SH調(diào)度該周期任務(wù)集是可行的充分條件為：?k，1≤k≤n，?ta，tb∈U={mpi|i=1，…，k；m=1，…，?pk/pi」，公式(8)和公式(9)成立.

(8)

(9)

證明：反證法.假設(shè)存在一個(gè)任務(wù)錯(cuò)過其截止期限.當(dāng)t″不存在時(shí)，其值設(shè)置為t″=0.因此，在區(qū)間[t″，t′]不存在空閑時(shí)間.區(qū)間[t″，t′]的任務(wù)可以分為兩種情形.第一種情形，任務(wù)實(shí)例釋放時(shí)刻不早于t″且初始優(yōu)先級(jí)比任務(wù)Ti高的集合，用β表示.第二種情形，處理器在時(shí)刻t″之前處于空閑狀態(tài)或者存在一個(gè)初始優(yōu)先級(jí)任務(wù)比任務(wù)Ti的初始優(yōu)先級(jí)低的任務(wù)，且在其在時(shí)刻t″已經(jīng)占有共享資源，該任務(wù)用Tk表示.

第一種情形：在區(qū)間[t″，t′]沒有阻塞發(fā)生.

第一種情形只有集合β中的任務(wù)在區(qū)間[t″，t′]以低速度SL執(zhí)行.在區(qū)間[t″，t′]的處理器需求Dt″，t′由下式給出：

(10)

由于存在任務(wù)在時(shí)刻t′錯(cuò)過其截止期限.因此，下式成立.

(11)

令t=t′-t″，經(jīng)過變換可知：

(12)

這與公式(6)矛盾.

第二種情形：在區(qū)間[t″，t′]發(fā)生阻塞.

第二種情形假設(shè)任務(wù)Tj是時(shí)刻t″之前已經(jīng)開始執(zhí)行，且假設(shè)任務(wù)Tk在區(qū)間[t″，t′]被任務(wù)Tj阻塞.顯然，任務(wù)Tk是集合β中初始優(yōu)先級(jí)最高的任務(wù).任務(wù)Tk的截止期限以及其被任務(wù)Tj阻塞的時(shí)刻分別用td和th表示.任務(wù)Tj開始以低速度SL執(zhí)行.在時(shí)刻th，任務(wù)Tj以高速度SH執(zhí)行直到其完成執(zhí)行.當(dāng)任務(wù)Tj完成執(zhí)行，任務(wù)Tk以高速度完成執(zhí)行.因此，在區(qū)間[t″，t′]的處理器需求可以分為三部分：

由于存在任務(wù)在時(shí)刻t′錯(cuò)過其截止期限，因此下式成立：

(13)

根據(jù)引理1，且經(jīng)過不等式變換，可以得出：

(14)

進(jìn)而推出：

(15)

令t=td-th，則下式成立：

(16)

這與公式(7)矛盾.因此，定理得證.

推論1.周期任務(wù)集T按照其周期進(jìn)行非降序排序，共享m個(gè)連續(xù)可重用資源的資源集合R={R1，R2,…，Rm}，其假設(shè)周期任務(wù)的相對(duì)截止期限等于其周期；RCPTDSSA算法以低速度SL和高速度SH調(diào)度該周期任務(wù)集是可行的充分條件為：SL和SH分別滿足公式(3)和公式(5).

證明：直接由引理1、引理2以及定理3得出.

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

為了評(píng)價(jià)算法的性能，利用C語言實(shí)現(xiàn)一個(gè)基于RM策略的周期任務(wù)調(diào)度仿真器.該仿真器采用文獻(xiàn)[9]的功耗模型.P=0.08+1.52S3，處理器處于空閑狀態(tài)的功耗為0.085，關(guān)鍵速度Scrit=0.3.在仿真器中實(shí)現(xiàn)RM/DPP算法和RCPTDSSA算法.以數(shù)控系統(tǒng)的任務(wù)集為研究對(duì)象[2]，該任務(wù)集由8個(gè)周期任務(wù)組成.每個(gè)周期任務(wù)Ti的周期在區(qū)間[2.4，9.6]中隨機(jī)選擇，其相應(yīng)的最壞情況下的執(zhí)行時(shí)間在0.035到其周期之間隨機(jī)選擇.隨機(jī)選擇4個(gè)任務(wù)作為有資源需求的任務(wù)，其余任務(wù)沒有資源需求.實(shí)驗(yàn)的仿真時(shí)間設(shè)置為100000個(gè)時(shí)間單位，重復(fù)實(shí)驗(yàn)100次，取平均值作為最后的實(shí)驗(yàn)結(jié)果.

考察系統(tǒng)利用率對(duì)算法能耗的影響，系統(tǒng)利用率的范圍設(shè)置為0.15到0.65，步長設(shè)置為0.05.以RM/DPP算法在系統(tǒng)利用為0.65的能耗為基準(zhǔn)進(jìn)行歸一化.實(shí)驗(yàn)的結(jié)果如圖3所示.

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

從圖3可以看出，RCPTDSSA算法和RM/DPP算法的能耗依賴于系統(tǒng)利用率.當(dāng)系統(tǒng)利用率上升時(shí)，RCPTDSSA算法和RM/DPP算法的能耗上升.這是因?yàn)殡S著系統(tǒng)利用率上升，任務(wù)的執(zhí)行時(shí)間變長，而RM/DPP算法始終以最大的處理器速度執(zhí)行，其能耗增加.而對(duì)于RCPTDSSA算法，系統(tǒng)率增加，不僅任務(wù)的執(zhí)行時(shí)間增加，而且任務(wù)執(zhí)行的低速度和高速度也增加，因此，其能耗也增加.此外，當(dāng)系統(tǒng)利用率低于0.3時(shí)，RCPTDSSA算法能夠節(jié)約更多能耗，這是因?yàn)镽CPTDSSA算法此時(shí)能夠以關(guān)鍵速度執(zhí)行，所以其節(jié)約的能耗更多.當(dāng)系統(tǒng)利用率大于0.3，RCPTDSSA算法能夠節(jié)約的能耗降低，這是因?yàn)橄到y(tǒng)利用率增加，RCPTDSSA算法的執(zhí)行速度增加，所消耗的能耗也增加，節(jié)約的能耗變少.從圖中還可以看出，無論系統(tǒng)利用率如何變化，RCPTDSSA算法的歸一化能耗都低于RM/DPP算法的歸一化能耗.通過計(jì)算可知，RCPTDSSA算法比RM/DPP算法節(jié)約大約55.31%的能耗.

6 結(jié) 論

針對(duì)現(xiàn)有基于動(dòng)態(tài)優(yōu)先級(jí)策略資源受限周期任務(wù)能耗優(yōu)化算法不能適用于固定優(yōu)先級(jí)系統(tǒng)，且節(jié)能效果差等不足，提出RCPTDSSA算法.該算法基于RM/DPP算法，使用雙速度策略調(diào)度任務(wù).任務(wù)開始以低速度執(zhí)行，當(dāng)有阻塞發(fā)生時(shí)切換到高速度執(zhí)行，且被阻塞的任務(wù)也以高速度執(zhí)行.利用理論分析的手段驗(yàn)證RCPTDSSA算法的可行性，仿真實(shí)驗(yàn)表明RCPTDSSA算法比RM/DPP算法節(jié)約大約55.31%的能耗.由于RCPTDSSA算法假設(shè)任務(wù)以最壞情況下執(zhí)行時(shí)間執(zhí)行以及任務(wù)的執(zhí)行時(shí)間與處理器速度成線性關(guān)系，且忽略處理器速度轉(zhuǎn)化開銷等不足，接下來將研究能夠回收動(dòng)態(tài)空閑時(shí)間，且考慮處理器速度切換開銷以及任務(wù)執(zhí)行時(shí)間與處理器速度成非線性關(guān)系的資源受限周期任務(wù)能耗優(yōu)化算法.