邵亞麗，陳海華，張立臣，陳雪娟

(1.廣東理工學院，廣東 肇慶 526000；2.廣東工業(yè)大學，廣東 廣州 510006)

0 引 言

CPS是涉及信息系統(tǒng)和物理系統(tǒng)交互與融合的一個嶄新的研究領(lǐng)域，具有重大研究價值[1-2]。它具有復雜性、異構(gòu)性、深度融合、自組織與自適應、實時性、海量性等特性，能為大型系統(tǒng)提供動態(tài)控制、信息服務和實時感知等功能[3-5]。其中實時性是CPS的重要特征，對CPS系統(tǒng)至關(guān)重要[6-10]。在這些系統(tǒng)中，每種操作模式的特征在于由不同的更新事務集執(zhí)行的一組功能。稱這種信息物理融合系統(tǒng)為動態(tài)信息物理融合系統(tǒng)(DCPS)[11]。如飛機控制系統(tǒng)，在該系統(tǒng)中，每個模式由不同的任務集組成，可以根據(jù)任務集區(qū)分著陸，起飛和正常巡航模式。目前國內(nèi)外也有許多學者對CPS的實時性進行研究，文獻[12]在提高實時任務的調(diào)度性能以及系統(tǒng)資源利用率方面提出了改進的調(diào)度算法，文獻[13]對CPS中實時性控制任務提出一種改進的自適應調(diào)度策略，從而降低系統(tǒng)功耗，提高計算性能。文中從DCPS的數(shù)據(jù)管理層面研究了它的實時性方法，目標是在保持數(shù)據(jù)對象時間有效性的同時，保證在操作模式改變之前和之后還是模式改變的期間，都最小化數(shù)據(jù)的陳舊性。

1 任務和模式切換模型

為了能夠在保證數(shù)據(jù)新鮮度的同時實現(xiàn)更低的數(shù)據(jù)陳舊度以及更好的更新事務可調(diào)度性，需要解決兩個問題：(1)如何選擇模式；(2)何時進行切換。針對問題1，在調(diào)度算法的選擇上采用貪心策略；針對問題2，提出兩種算法：分別為基于搜索的切換(SBS)和基于調(diào)整的切換(ABS)，當滿足時間有效性約束時，來確定適當?shù)那袚Q點。SBS在模式改變請求(MCR)釋放之后檢查每個空閑時段的開始時隙并檢驗它是否是適當?shù)那袚Q點；ABS進一步放寬對可用切換點選擇的限制，并調(diào)整MCR和當前時隙之間的調(diào)度。與SBS相比，ABS大大增加了可用切換點的數(shù)量，進一步提高了MCR的快速性[14]。

完成任務：是在舊模式下活動但不在新模式中出現(xiàn)的任務。在MCR之后沒有新任務釋放的情況下，允許它們在舊調(diào)度策略下完成。為了保證它們的時間有效性，不能中止它們。

新任務：是只出現(xiàn)在新模式中的任務。它們在適當?shù)那袚Q點同時釋放。

未更改的任務：是經(jīng)歷模式切換的持久化任務。它們在MCR之后在舊的調(diào)度策略下被執(zhí)行和釋放，直到新的調(diào)度策略控制。應當仔細選擇切換點，以在切換期間保持時間有效性。

已更改的任務：是在兩種模式都出現(xiàn)但在新模式下有不同參數(shù)(如Ci和Vi)的任務。這些任務的時間有效性在切換期間還必須保持。

2 實時系統(tǒng)調(diào)度算法

文中主要考慮三個調(diào)度策略：HH，ML和DS-FP。DS-FP是這三個中可調(diào)度性最好的，但是具有最差的數(shù)據(jù)新鮮度，算法思想如下：

HH的基本思想是：為保持實時數(shù)據(jù)對象的有效性，在保證更新事務τi的周期和相對截止時間之和不大于該事務的有效時間間隔長度的前提下，規(guī)定τi的周期等于其相對截止時間，且都等于有效期間隔的一半[2，5，10]，即Pi=Di=Vi/2。

ML的基本思想是：采用周期性事務模型，在保證更新周期和相對截止時間的和不大于更新數(shù)據(jù)對象的有效期間隔的前提下，設置更新事務的周期Pi大于相應更新數(shù)據(jù)的有效期間隔的一半，即Pi+Di≤Vi,Di≤Vi/2≤Pi。

ML的提出是為了最小化更新工作負載，它使用單調(diào)截止時間(deadline monotonic，DM)[3]來調(diào)度周期性更新事務。

DS-FP的基本思想是[5]：以非周期性硬實時事務模型為基礎，在確保實時數(shù)據(jù)對象更新時間有效性的同時，盡可能推遲當前更新事務作業(yè)Ji,j的后繼作業(yè)的釋放時間ri,j+1，從而增加同一事務兩個連續(xù)作業(yè)的時間間隔，以降低CPU的工作負載[4-5,14]。其動態(tài)地為更新事務的作業(yè)分配周期和相對截止時間。

根據(jù)更新事務產(chǎn)生的工作負載來選擇調(diào)度策略(UBSS)，如圖1所示。當用MCR通知系統(tǒng)時，它將分別計算HH和ML下的新任務集的周期和截止時間。如果任務集在HH下不可調(diào)度，則將嘗試使用ML。當HH和ML都不能用時，將僅采用DS-FP。如果任務集甚至不能通過DS-FP的可調(diào)度性測試[8]，系統(tǒng)將報告錯誤，因為到目前為止，沒有比DS-FP能更有效地保持實時數(shù)據(jù)對象的時間有效性的調(diào)度算法。

圖1 基于利用率的調(diào)度策略選擇

因為在調(diào)度切換期間可能改變未改變?nèi)蝿盏臅r間有效性。因此即使舊的和新的任務集在所選擇的調(diào)度策略下是可調(diào)度的，也不能保證將保持實時數(shù)據(jù)的時間有效性。因此，為了滿足所有事務的時間有效性約束，應當仔細選擇切換點。在此提出兩種算法來搜索適當?shù)那袚Q點。以下是兩個搜索算法的偽代碼，如圖2和圖3所示。

算法1：基于搜索的切換算法

輸入：Tk,Tk+1,ψk,ψk+1,開始搜索時間t0及tL

輸出：tw

1：fort=t0tot0+tLdo

2： ift==t1then//t1為空閑時間段的開始點

3：f=TRUE;

4： //判斷t是否能選為tw

5： for eachτi∈Tk∩Tk+1do

6：ts=ψk中τi的最后作業(yè)的釋放時間；

7：l=ψk+1中τi的第一個作業(yè)地完成時間；

8： ift-ts+1>Vithen

9：f=FALSE;

10： end if

11： end for

12： iff==TRUE then

13： returnt;

14： end if

15： end if

16：end for

17：returntw不存在；

圖2 SBS算法

算法2：基于調(diào)整的切換算法

輸入：Tk,Tk+1,ψk,ψk+1,t0及tL

輸出：tw

1：fort=t0tot0+tLdo

4： continue；

5： else //調(diào)整[t0,t)間Tk的調(diào)度

6：f=ScheduleAdjustment(Tk,t0,t);

7： iff=FAIL then

8： continue；

9： else

10： for eachτi∈Tk∩Tk+1do

11；ts=ψk中τi的調(diào)整請求時間；

12：l=ψk+1中τi的第一個作業(yè)的完成時長；

13： ift-ts+l>Vithen //違反時間有效性

14：f=FAIL;

15: end if

16: end for

17: iff=SUCCESS then

18: returnt;

19: end if

20: end if

21: end if

22： end for;

圖3 ABS算法

3 仿真結(jié)果

文中實驗都是利用MATLAB下的simulink工具實現(xiàn)的。表1為實驗參數(shù)設置。

表1 實驗參數(shù)設置

(1)UBSS與ML、DS-FP的調(diào)度成功率、CPU利用率的仿真對比。

在本實驗中，模擬系統(tǒng)中有10個連續(xù)模式，每個模式固定持續(xù)20 000個時間單位。每種模式的密度系數(shù)如圖4(a)所示。在每個模式中隨機生成200個任務集，實驗主要研究CPU利用率、調(diào)度成功率、數(shù)據(jù)陳舊性、調(diào)度開銷和切換延遲。

圖4 調(diào)度成功率和密度因子

圖4(b)給出了ML，DS-FP和UBSS的調(diào)度成功率的結(jié)果。從圖中可以發(fā)現(xiàn)，DS-FP和UBSS在具有不同密度因子的不同模式中總是具有相同的成功率。這是因為在每個模式的開始，UBSS將進行可調(diào)度性測試，并選擇最適合的調(diào)度策略。如果任務集僅在DS-FP下可調(diào)度，則UBSS將為了最大化可調(diào)度性而選擇DS-FP。此外，還能發(fā)現(xiàn)這三種方法的成功率都隨著密度因子的增加而下降，但DS-FP和UBSS始終優(yōu)于ML。當密度因子為0.63時，ML的成功率低至0.01，而DS-FP和UBSS的成功率仍然可以保持在0.79。當密度因子低于0.55時，這三種方法都具有相同的成功率，因為這時所有任務集都可由ML調(diào)度。

圖5顯示了三種方法中CPU利用率的比較。如前所述，與ML相比DS-FP可以極大地降低CPU的利用率，同時仍然保持時間有效性。其中DS-FP的CPU利用率始終低于ML，并且當模式6中的密度因子為0.63時，差異達到15.1%。而UBSS的CPU利用率在ML和DS-FP之間。當密度因子低時，UBSS的CPU利用率接近ML，因為大多數(shù)任務集此時可以在ML下調(diào)度，并且為了維持更高的數(shù)據(jù)新鮮度和更低的在線調(diào)度開銷UBSS優(yōu)先選擇周期性調(diào)度策略。另一方面，當系統(tǒng)工作負載較高且大部分任務集僅在DS-FP下可調(diào)度時，UBSS選擇DS-FP以最大化可調(diào)度性,此時它的CPU利用率將接近相應的DS-FP調(diào)度。

圖5 CPU利用率比較

(2)UBSS與DS-FP在數(shù)據(jù)陳舊度的仿真對比。

圖6 模式數(shù)據(jù)陳舊度和CPU負載

(3)ABS和SBS的仿真對比。

圖7 ABS和SBS成功率和延遲仿真結(jié)果

由圖7(a)可以發(fā)現(xiàn)，當概率p增大時，SBS和ABS下的切換成功率都下降。這是因為Tk+1的事務越多，可選切換點上的時間有效性約束越多。另外，通過調(diào)度調(diào)整主動創(chuàng)建切換點，而非被動搜索，ABS總是在切換成功率方面優(yōu)于SBS，當百分比p提升到95%時，它們的差值達到14%。由于Tk在ML下不可調(diào)度，當p=100%時，Tk+1等于Tk，并且它們的成功率都降為0。圖7(b)顯示了SBS和ABS之間的切換延遲的比較?？傻?，ABS相比SBS總是具有較低的切換延遲，并且當p增大時，它們的差值增加。這是因為SBS限制僅在空閑時段的開始時隙選擇切換點，而ABS沒有該約束。通過合理的調(diào)整，ABS極大地增加了調(diào)度切換候選的數(shù)量，并潛在地提高了切換延遲。

4 結(jié)束語

主要研究了如何在動態(tài)信息物理融合系統(tǒng)中，在模式變化的情況下保持實時數(shù)據(jù)的時間有效性的問題。介紹了任務和模式切換模型，研究了在線調(diào)度切換問題，建議在不同的模式下使用不同的調(diào)度策略，并引入兩種算法來搜索適當?shù)那袚Q點。最后通過仿真模擬論證了算法的有效性。