信息物理系統(tǒng)中基于保護閾值的實時調(diào)度算法研究*

周本海，姚大鵬

(沈陽工程學院計算機基礎(chǔ)教學部,遼寧 沈陽 110136 )

1 引言

信息物理融合系統(tǒng)CPS(Cyber-Physical Systems)是一個以時間為關(guān)鍵屬性的系統(tǒng)，實時性是重要的系統(tǒng)屬性，CPS必須在限定時間內(nèi)完成消息的發(fā)送和接收[1]。系統(tǒng)輸出結(jié)果的正確性不僅取決于計算所形成的邏輯結(jié)果，還要取決于結(jié)果產(chǎn)生的時間。因此，對實時信息物理融合系統(tǒng)進行研究，進而增強它在事先定義的時間范圍內(nèi)識別和處理離散事件的能力、增強其處理和儲存控制系統(tǒng)所需要的大量數(shù)據(jù)的能力，具有很大的研究意義。

目前，CPS中普遍采用基于優(yōu)先級的搶占式調(diào)度方式，因為它在提高資源利用率和及時響應高優(yōu)先級任務方面具有很強的優(yōu)勢。但是，在CPS系統(tǒng)中的某些特定的應用背景下，非搶占調(diào)度性能要優(yōu)于搶占式調(diào)度，原因在于搶占式系統(tǒng)容易導致較低的系統(tǒng)吞吐率。而且，搶占式調(diào)度方式中高優(yōu)先級任務搶占運行，不考慮當前任務的運行狀態(tài)。如果被搶占任務即將完成，由于高優(yōu)先級任務無條件地搶占，會導致低優(yōu)先級任務被延期或者錯過截止期，更重要的是，頻繁的任務切換增加了系統(tǒng)的抖動，嚴重影響了CPS的實時性能。

所以，CPS特別需要一種搶占與非搶占結(jié)合的調(diào)度方式，進行合理而有效的實時任務調(diào)度。據(jù)此，本文建立了任務集的松弛時間與保護時間模型，提出了保護閾值的實時調(diào)度算法，有效地抑制了任務頻繁切換產(chǎn)生的抖動對系統(tǒng)性能的影響，提高了系統(tǒng)的利用率與實時性能。

2 研究背景

CPS在醫(yī)療、智能交通以及軍事等多個關(guān)鍵領(lǐng)域發(fā)揮著極其重要的作用，該類系統(tǒng)的典型特征是實時性，是指CPS必須保證所有實時任務在其截止期內(nèi)完成。由于CPS對系統(tǒng)資源的限制非常嚴格，單純的搶占式調(diào)度會造成任務切換次數(shù)過多，增大系統(tǒng)開銷的問題，這將嚴重影響CPS的實時性能。如何在不降低系統(tǒng)可調(diào)度性的前提下盡量減少任務切換次數(shù)，已成為CPS環(huán)境下新的研究熱點問題。

文獻[2]給出了搶占閾值的實時調(diào)度模型,以離線的方式降低任務調(diào)度中搶占的次數(shù)。文獻[3]在此基礎(chǔ)上提出了一個優(yōu)化標準，用來減少固定優(yōu)先級調(diào)度的搶占開銷。文獻[4]通過為任務的搶占建立一個模型,將任務的啟動時間作為一個調(diào)度參數(shù),降低了任務的搶占次數(shù),但模型的計算時間復雜度具有不確定性。文獻[5]提出了針對就緒的周期任務隊列的調(diào)度算法,優(yōu)化了動態(tài)調(diào)度算法的搶占次數(shù),但對于動態(tài)調(diào)度算法的時間復雜度較高,系統(tǒng)開銷很大。文獻[6]提出了搶占閾值的方法，適用于任務集不確定、優(yōu)先級動態(tài)變化的實時系統(tǒng)。文獻[7]提出一種按比例確定閾值的方法。文獻[8]提出將優(yōu)先級繼承協(xié)議集成到搶占閾值調(diào)度中，優(yōu)化了最壞情況下任務切換次數(shù)。文獻[9]提出由任務特征參數(shù)決定的搶占閾值調(diào)度算法，并用云模型理論進行優(yōu)化。文獻[10]提出了基于DVS(Dynamic Voltage Scaling)的搶占閾值算法。然而，以上設(shè)計的閾值確定算法未能很好地解決系統(tǒng)的抖動現(xiàn)象，上下文切換次數(shù)仍然較多，任務截止錯失率比較高，影響了系統(tǒng)的實時性能。

本文提出的基于保護閾值的CPS實時調(diào)度算法，能夠有效地減少任務切換次數(shù)，有效地提高了系統(tǒng)的利用率與實時性能。

3 相關(guān)技術(shù)

3.1 CPS中實時任務模型

為了方便描述具體任務模型，下面給出討論中將涉及到的任務及其有關(guān)參數(shù)的定義與表示。設(shè)一個有n個任務的任務集τ=(τ1,τ2,…,τi,…,τn)，它們的周期分別為T1,T2,…,Tn，每個周期內(nèi)的最壞情況執(zhí)行時間分別為C1,C2,…,Cn，相對截止期為D1,D2,…,Dn,對于第i(1≤i≤n)個周期任務taskpi，必須滿足Ci≤Di≤Ti。處理機利用率表示任務集對處理器資源的占用程度，任務集τ的處理器利用率可以用如下公式可表示：

Figure 1 Task switching in three situations圖1 三種情況下的任務切換

3.2 任務切換

CPS系統(tǒng)中的節(jié)點若采用非搶占式調(diào)度，則任務切換發(fā)生在當前任務運行結(jié)束時，其優(yōu)勢是避免了不必要的任務切換，系統(tǒng)開銷小。缺點是高優(yōu)先級任務有時被阻塞，直到低優(yōu)先級任務運行結(jié)束。圖1a中表示了非搶占的調(diào)度方式。相反，搶占式調(diào)度方式是當高優(yōu)先級任務就緒時，立刻得到運行，剝奪正在執(zhí)行的低優(yōu)先級任務的運行時間(如圖1b所示)。搶占式調(diào)度的優(yōu)勢是能夠增強系統(tǒng)的可預測性，最小化任務的響應時延。但是，由于搶占導致的頻繁任務切換，造成嚴重的系統(tǒng)資源浪費，影響實時性能。圖1c表示了一種改進的搶占式調(diào)度方式，在保障高優(yōu)先級任務的時限的基礎(chǔ)上，最大化低優(yōu)先級任務的執(zhí)行時間，該種方式可以有效地減少任務切換次數(shù)，提高系統(tǒng)的可調(diào)度率。

4 保護閾值模型建立

在一組可調(diào)度的任務集中，我們采用RM調(diào)度方法對所有周期任務按優(yōu)先級從高至低排序，即在任務集τ中，任務τi的優(yōu)先級大于任務τj(1≤i

(1)

經(jīng)整理得，

(2)

由此可知，如果一個任務集是可調(diào)度的，則Sp≥0，反之，Sp<0。

任務集τ中，按照任務的優(yōu)先級排列，當任務數(shù)量大于或等于兩個時，保護閾值模型如公式(3)所示：

Thresholdp=min({S2,…,Sp})

(3)

Thresholdp為被搶占任務的最大可繼續(xù)執(zhí)行時間，即高優(yōu)先級任務的延遲時間[0,Thresholdp]內(nèi)，任務集是可調(diào)度的。

5 基于保護閾值的CPS實時調(diào)度算法描述

根據(jù)松弛時間模型與保護閾值模型計算當前任務的剩余時間、高優(yōu)先級任務的松弛時間以及保護閾值。當系統(tǒng)中有高優(yōu)先級任務就緒時，判斷低優(yōu)先級任務是否可以繼續(xù)執(zhí)行。測試方法是：如果低優(yōu)先級任務的剩余時間大于松弛時間，則不進行提升優(yōu)先級的操作，高優(yōu)先級任務進行搶占調(diào)度，任務切換次數(shù)加1；反之，提升當前任務的優(yōu)先級至最高，直至執(zhí)行完畢，恢復優(yōu)先級，高優(yōu)先級任務開始運行。通過上述描述，下面給出基于保護閾值的CPS實時調(diào)度算法。

算法基于保護閾值的CPS實時調(diào)度算法

初始化：CreateTasks( );//創(chuàng)建任務集

功能函數(shù)：Schedule( ) //任務調(diào)度

1. {if (τpis ready) //如果高優(yōu)先級任務集就緒

2. {Compute (Thresholdp,Sp,Ri)

3. /*計算就緒高優(yōu)先級任務的保護閾值，松弛時間，剩余時間*/

4. if(Ri

5. {{riseτipriority to CELLPRIO;

6. executeτp;}

7. else executeτp;

8. //剩余時間超過保護閾值，則運行高優(yōu)先級任務

}}

9. else executeπi;/*無高優(yōu)先級任務，則直接運行當前任務*/}

該算法使用的是固定任務集，即任務集的超周期長度取決于任務的個數(shù)。所以，松弛時間模型為靜態(tài)模型。在計算任務的剩余時間與保護閾值的差值時，算法復雜度與高優(yōu)先任務集的任務數(shù)量無關(guān)。即本文提出的基于預留的調(diào)度算法的執(zhí)行時間不隨問題規(guī)模n的增加而增長，創(chuàng)建任務集算法的時間復雜度為O(1)。

6 實驗結(jié)果與分析

本文采用調(diào)度模擬器RTSIM(Real Time Simulation)[11]對本文提出的理論方法進行仿真驗證，該模擬器可以仿真目前大多數(shù)的處理器結(jié)構(gòu)，如單處理器、多處理器、CMP等多種體系結(jié)構(gòu)。利用該模擬器，將本文的保護閾值實時調(diào)度算法在多處理器環(huán)境中進行仿真驗證。在RTSIM上將本文的算法與目前較為流行的比例閾值和以繼承協(xié)議為手段的降低任務切換次數(shù)的算法進行仿真比較。并且將上述三種方法應用在最優(yōu)化的RM(Rate Monotonic)調(diào)度算法上，比較三種方法在CPS節(jié)點上在一個超周期內(nèi)產(chǎn)生的任務搶占次數(shù)。如圖2與圖3所示，圖中各點的值是100組任務集合的均值。

Figure 2 Effect of system utilization on task switch圖2 系統(tǒng)利用率對任務切換次數(shù)的影響

Figure 3 Task swith comparison of the three algorithms圖3 三種算法任務切換次數(shù)的比較

從圖2可以看出，在任務數(shù)量固定的情況下，三種算法的任務切換次數(shù)均低于未做改進的調(diào)度方法，并且任務切換的均值也要低于原來方法。本文的算法在可調(diào)度的前提下，在[0.1，0.9]的利用率范圍內(nèi)，任務切換次數(shù)都要小于RM算法，平均值比RM算法低37.8%。圖3表示本文的保護閾值的方法與比例閾值以及優(yōu)先級繼承協(xié)議算法的任務切換次數(shù)比較。可以得出，本文算法的任務切換次數(shù)要低于其他兩種方法，并且任務切換的平均值分別低于22.7%與29.8%。

Figure 4 Task switches when task number equals to 20圖4 任務數(shù)為20時的任務切換次數(shù)變化

Figure 5 Task switch comparison of the three algorithms when task number equals to 20圖5 任務數(shù)為20時的三種算法任務切換次數(shù)的比較

將每組任務數(shù)量設(shè)置為20，在[0.1，0.9]的利用率范圍內(nèi)，圖4表示任務切換次數(shù)都要小于RM算法，平均值比RM算法低35.9%。圖5是本文的保護閾值的方法與比例閾值以及優(yōu)先級繼承協(xié)議算法的任務切換次數(shù)的比較。從圖5可以得出，本文算法的任務切換次數(shù)要低于其他兩種方法，并且任務切換的平均值分別低于18.7%與33.1%。

7 結(jié)束語

CPS中的關(guān)鍵屬性為實時性，大多數(shù)算法采用了搶占式調(diào)度模式，而單純的搶占方式容易導致頻繁的任務切換，嚴重影響了CPS的實時特性。本文將搶占與非搶占的調(diào)度方式相結(jié)合，提出了一種基于保護閾值的實時調(diào)度算法。通過建立任務集的松弛時間與保護閾值模型，在可調(diào)度的前提下，最大化被搶占任務的執(zhí)行時間，降低了任務切換頻率。通過仿真實驗結(jié)果表明，與搶占式調(diào)度的RM算法相比，本文算法有效地降低了任務的切換次數(shù)，增強了系統(tǒng)的實時性與可靠性。

[1] Wang Zhong-jie,Xie Lu-lu.Cyber-physical systems:A survey[J]. ACTA Automatica SINICA，2011,37(10):1157-1167.(in Chinese)

[2] MinSeong K,Andy W.Applying fixed-priority preemptive scheduling with preemption threshold to asynchronous event handling in the RTSJ [J].Concurrency and Computation:Practice and Experience, 2011,23(14):1609-1622.

[3] Ding Wan-fu, Guo Rui-feng, Qin Cheng-gang, et al. Preemption threshold scheduling algorithm with higher fault-tolerant priority[J].Journal of Software, 2011,22(12):2894-2904.(in Chinese)

[4] Keskin U.Exact response-time analysis for fixed-priority preemption-threshold scheduling[C]∥Proc of Emerging Technologies and Factory Automation (ETFA),2010:1-4.

[5] Chen Ying-ge,Wang Xiao-ying,Zhao Hai,et al.Ready queue optimization research in task scheduling[J]. Journal of System Simulation, 2006,18(4):877-882. (in Chinese)

[6] Evans B G, Baughan K. Vision of 4G[J]. Electronics and Communication Engineering Journal, 2000, 12(6):293-303.

[7] Wu Wei, Qian Liang,Xu You-yun. Sampling frequency compensation algorithm for OFDM systems and its FPGA implementation[J]. Telecommunication Engineering, 2007, 47(4):32-36.(in Chinese)

[8] Chen Xiu-ping,Zeng Xiao-yang.Optimal synchronization scheme for CMMB receivers[J]. Computer Engineering, 2010, 36(21):95-97.(in Chinese)

[9] Stefan A. OFDM carrier and sampling frequency synchronization and its performance on stationary and mobile channels[J]. IEEE Transactions on Consumer Electronics, 2000, 46(3):438-441.

[10] Liu Yang. Integrating preemption threshold to fixed priority DVS scheduling algorithms[C]∥Proc of Embedded and Real-Time Computing Systems and Applications, 2009:165-171.

[11] http://rtsim.sssup.it/.

附中文參考文獻：

[1] 王中杰，謝璐璐.信息物理融合系統(tǒng)研究綜述[J]. 自動化學報, 2011, 37(10):1157-1167.

[3] 丁萬夫，郭銳鋒，秦承剛，等.容錯優(yōu)先級提升的搶占閾值容錯調(diào)度算法[J].軟件學報，2011,22(12):2894-2904.

[5] 陳英革,王小英，趙海，等.任務調(diào)度過程中就緒隊列的優(yōu)化研究[J].系統(tǒng)仿真學報, 2006,18(4):877-882.

[7] 吳煒, 錢良, 徐友云. OFDM 系統(tǒng)采樣中補償算法及其FPGA 實現(xiàn)[J]. 電訊技術(shù), 2007, 47(4):32-36.

[8] 陳秀平, 曾曉洋. CMMB 接收機同步優(yōu)化方案[J]. 計算機工程,2010, 36(21):95-97.