動態(tài)信息物理融合系統(tǒng)實時數(shù)據(jù)服務(wù)

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

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

0 引 言

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

1 任務(wù)和模式切換模型

為了能夠在保證數(shù)據(jù)新鮮度的同時實現(xiàn)更低的數(shù)據(jù)陳舊度以及更好的更新事務(wù)可調(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]。

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

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

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

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

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

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

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

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

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

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

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

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

因為在調(diào)度切換期間可能改變未改變?nèi)蝿?wù)的時間有效性。因此即使舊的和新的任務(wù)集在所選擇的調(diào)度策略下是可調(diào)度的，也不能保證將保持實時數(shù)據(jù)的時間有效性。因此，為了滿足所有事務(wù)的時間有效性約束，應(yīng)當仔細選擇切換點。在此提出兩種算法來搜索適當?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ù)設(shè)置。

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

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

在本實驗中，模擬系統(tǒng)中有10個連續(xù)模式，每個模式固定持續(xù)20 000個時間單位。每種模式的密度系數(shù)如圖4(a)所示。在每個模式中隨機生成200個任務(wù)集，實驗主要研究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)度策略。如果任務(wù)集僅在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時，這三種方法都具有相同的成功率，因為這時所有任務(wù)集都可由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ù)任務(wù)集此時可以在ML下調(diào)度，并且為了維持更高的數(shù)據(jù)新鮮度和更低的在線調(diào)度開銷UBSS優(yōu)先選擇周期性調(diào)度策略。另一方面，當系統(tǒng)工作負載較高且大部分任務(wù)集僅在DS-FP下可調(diào)度時，UBSS選擇DS-FP以最大化可調(diào)度性,此時它的CPU利用率將接近相應(yīng)的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的事務(wù)越多，可選切換點上的時間有效性約束越多。另外，通過調(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之間的切換延遲的比較?？傻茫珹BS相比SBS總是具有較低的切換延遲，并且當p增大時，它們的差值增加。這是因為SBS限制僅在空閑時段的開始時隙選擇切換點，而ABS沒有該約束。通過合理的調(diào)整，ABS極大地增加了調(diào)度切換候選的數(shù)量，并潛在地提高了切換延遲。

4 結(jié)束語

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