資源受限周期任務雙速度調度算法

張憶文，吳文江，郭銳鋒

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

1 引 言

實時系統已經廣泛應用于工業控制、航空航天、通信等行業.實時系統按照任務釋放實例的特點，可以將任務劃分為周期任務、偶發任務和混合任務等.隨著技術的發展，實時系統的能耗越來越高，已經成為系統發展的瓶頸.動態電壓調節技術[1]根據系統的實時負載，通過動態調節處理器速度，降低處理器能耗，是解決系統能耗問題的重要技術.

文獻[1-6]將實時調度理論與動態電壓調節技術結合起來，降低系統能耗.但這些工作都假設任務之間是相互獨立，沒有考慮任務之間的共享資源問題.事實上，在實時系統中，任務之間由于共享資源而存在相互依賴關系.文獻[7,8]研究了任務的資源共享問題，但這些研究主要針對偶發任務模型.針對周期任務模型的資源共享問題的研究相對較少.文獻[9,10]通過利用動態優先級策略調度周期任務，且所有任務在執行過程中都以單一的速度執行.這些研究工作不能適用于采用固定優先級調度策略的系統，且節能效果差.

針對現有基于動態優先級策略資源受限周期任務能耗優化算法不能適用于固定優先級系統，且節能效果差等不足，提出RCPTDSSA.該算法基于RM/DPP算法，使用雙速度策略調度任務，利用動態電壓調節技術降低能耗.任務開始以低速度執行，當有阻塞發生時切換到高速度執行，且被阻塞的任務也以高速度執行.

2 系統模型

2.1 任務模型

2.2 處理器模型和能耗模型

P=Ps+h(Pind+CefSm)

(1)

3 雙優先級單調速率調度算法

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

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

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

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

圖1 RM/DPP算法調度周期任務集Fig.1 RM/DPP algorithm schedules the periodic task set

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

4 RCPTDSSA算法

4.1 準備工作

4.2 計算SL和SH

定理1[12].RM算法調度具有n個相互獨立周期任務的周期任務集是可行，其必須滿足以下條件：

Utot≤LLB(n)

(2)

根據定理1，SL可以通過下式計算；

(3)

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

(4)

根據定理2，SH可以通過下式計算；

(5)

4.3 RCPTDSSA算法描述

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

算法1.RCPTDSSA算法

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

2) 當SL

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

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

5) 當周期任務Ti釋放一個實例，根據RM策略將其插入到就緒隊列；

6) 周期任務Ti開始以低速度SL執行，且修改其執行優先級；

7) 當周期任務Ti阻塞周期任務Tk的執行時，周期任務Ti以高速度SH執行，直到其完成執行；此時，周期任務Tk也以高速度SH執行，直到其完成執行.

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

4.4 RCPTDSSA算法實例

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

圖2 RCPTDSSA算法調度周期任務集Fig.2 RCPTDSSA algorithm schedules the periodic task set

(6)

證明：參見文獻[13].

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

(7)

證明：參見文獻[13].

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

(8)

(9)

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

第一種情形：在區間[t″，t′]沒有阻塞發生.

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

(10)

由于存在任務在時刻t′錯過其截止期限.因此，下式成立.

(11)

令t=t′-t″，經過變換可知：

(12)

這與公式(6)矛盾.

第二種情形：在區間[t″，t′]發生阻塞.

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

由于存在任務在時刻t′錯過其截止期限，因此下式成立：

(13)

根據引理1，且經過不等式變換，可以得出：

(14)

進而推出：

(15)

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

(16)

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

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

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

5 仿真實驗

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

考察系統利用率對算法能耗的影響，系統利用率的范圍設置為0.15到0.65，步長設置為0.05.以RM/DPP算法在系統利用為0.65的能耗為基準進行歸一化.實驗的結果如圖3所示.

圖3 系統利用率對算法能耗的影響Fig.3 System utilization effects on the algorithm energy consumption

從圖3可以看出，RCPTDSSA算法和RM/DPP算法的能耗依賴于系統利用率.當系統利用率上升時，RCPTDSSA算法和RM/DPP算法的能耗上升.這是因為隨著系統利用率上升，任務的執行時間變長，而RM/DPP算法始終以最大的處理器速度執行，其能耗增加.而對于RCPTDSSA算法，系統率增加，不僅任務的執行時間增加，而且任務執行的低速度和高速度也增加，因此，其能耗也增加.此外，當系統利用率低于0.3時，RCPTDSSA算法能夠節約更多能耗，這是因為RCPTDSSA算法此時能夠以關鍵速度執行，所以其節約的能耗更多.當系統利用率大于0.3，RCPTDSSA算法能夠節約的能耗降低，這是因為系統利用率增加，RCPTDSSA算法的執行速度增加，所消耗的能耗也增加，節約的能耗變少.從圖中還可以看出，無論系統利用率如何變化，RCPTDSSA算法的歸一化能耗都低于RM/DPP算法的歸一化能耗.通過計算可知，RCPTDSSA算法比RM/DPP算法節約大約55.31%的能耗.

6 結 論

針對現有基于動態優先級策略資源受限周期任務能耗優化算法不能適用于固定優先級系統，且節能效果差等不足，提出RCPTDSSA算法.該算法基于RM/DPP算法，使用雙速度策略調度任務.任務開始以低速度執行，當有阻塞發生時切換到高速度執行，且被阻塞的任務也以高速度執行.利用理論分析的手段驗證RCPTDSSA算法的可行性，仿真實驗表明RCPTDSSA算法比RM/DPP算法節約大約55.31%的能耗.由于RCPTDSSA算法假設任務以最壞情況下執行時間執行以及任務的執行時間與處理器速度成線性關系，且忽略處理器速度轉化開銷等不足，接下來將研究能夠回收動態空閑時間，且考慮處理器速度切換開銷以及任務執行時間與處理器速度成非線性關系的資源受限周期任務能耗優化算法.