周本海，姚大鵬

(沈陽(yáng)工程學(xué)院計(jì)算機(jī)基礎(chǔ)教學(xué)部,遼寧 沈陽(yáng) 110136 )

1 引言

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

目前，CPS中普遍采用基于優(yōu)先級(jí)的搶占式調(diào)度方式，因?yàn)樗谔岣哔Y源利用率和及時(shí)響應(yīng)高優(yōu)先級(jí)任務(wù)方面具有很強(qiáng)的優(yōu)勢(shì)。但是，在CPS系統(tǒng)中的某些特定的應(yīng)用背景下，非搶占調(diào)度性能要優(yōu)于搶占式調(diào)度，原因在于搶占式系統(tǒng)容易導(dǎo)致較低的系統(tǒng)吞吐率。而且，搶占式調(diào)度方式中高優(yōu)先級(jí)任務(wù)搶占運(yùn)行，不考慮當(dāng)前任務(wù)的運(yùn)行狀態(tài)。如果被搶占任務(wù)即將完成，由于高優(yōu)先級(jí)任務(wù)無(wú)條件地?fù)屨?，?huì)導(dǎo)致低優(yōu)先級(jí)任務(wù)被延期或者錯(cuò)過(guò)截止期，更重要的是，頻繁的任務(wù)切換增加了系統(tǒng)的抖動(dòng)，嚴(yán)重影響了CPS的實(shí)時(shí)性能。

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

2 研究背景

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

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

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

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

3.1 CPS中實(shí)時(shí)任務(wù)模型

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

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

3.2 任務(wù)切換

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

4 保護(hù)閾值模型建立

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

(1)

經(jīng)整理得，

(2)

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

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

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

(3)

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

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

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

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

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

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

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

2. {Compute (Thresholdp,Sp,Ri)

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

4. if(Ri

5. {{riseτipriority to CELLPRIO;

6. executeτp;}

7. else executeτp;

8. //剩余時(shí)間超過(guò)保護(hù)閾值，則運(yùn)行高優(yōu)先級(jí)任務(wù)

}}

9. else executeπi;/*無(wú)高優(yōu)先級(jí)任務(wù)，則直接運(yùn)行當(dāng)前任務(wù)*/}

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

6 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

[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/.

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

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

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

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

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

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