動態信息物理融合系統實時數據服務

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

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

0 引 言

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

1 任務和模式切換模型

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

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

新任務：是只出現在新模式中的任務。它們在適當的切換點同時釋放。

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

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

2 實時系統調度算法

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

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

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

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

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

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

圖1 基于利用率的調度策略選擇

因為在調度切換期間可能改變未改變任務的時間有效性。因此即使舊的和新的任務集在所選擇的調度策略下是可調度的，也不能保證將保持實時數據的時間有效性。因此，為了滿足所有事務的時間有效性約束，應當仔細選擇切換點。在此提出兩種算法來搜索適當的切換點。以下是兩個搜索算法的偽代碼，如圖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的最后作業的釋放時間；

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

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：基于調整的切換算法

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

輸出：tw

1：fort=t0tot0+tLdo

4： continue；

5： else //調整[t0,t)間Tk的調度

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的調整請求時間；

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

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 仿真結果

文中實驗都是利用MATLAB下的simulink工具實現的。表1為實驗參數設置。

表1 實驗參數設置

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

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

圖4 調度成功率和密度因子

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

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

圖5 CPU利用率比較

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

圖6 模式數據陳舊度和CPU負載

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

圖7 ABS和SBS成功率和延遲仿真結果

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

4 結束語

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