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

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

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

0 引 言

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

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

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

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

新任務(wù)：是只出現(xiàn)在新模式中的任務(wù)。它們?cè)谶m當(dāng)?shù)那袚Q點(diǎn)同時(shí)釋放。

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出：tw

1：fort=t0tot0+tLdo

2： ift==t1then//t1為空閑時(shí)間段的開始點(diǎn)

3：f=TRUE;

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

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

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

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

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)整請(qǐng)求時(shí)間；

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

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

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é)果

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

表1 實(shí)驗(yàn)參數(shù)設(shè)置

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

在本實(shí)驗(yàn)中，模擬系統(tǒng)中有10個(gè)連續(xù)模式，每個(gè)模式固定持續(xù)20 000個(gè)時(shí)間單位。每種模式的密度系數(shù)如圖4(a)所示。在每個(gè)模式中隨機(jī)生成200個(gè)任務(wù)集，實(shí)驗(yàn)主要研究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在具有不同密度因子的不同模式中總是具有相同的成功率。這是因?yàn)樵诿總€(gè)模式的開始，UBSS將進(jìn)行可調(diào)度性測(cè)試，并選擇最適合的調(diào)度策略。如果任務(wù)集僅在DS-FP下可調(diào)度，則UBSS將為了最大化可調(diào)度性而選擇DS-FP。此外，還能發(fā)現(xiàn)這三種方法的成功率都隨著密度因子的增加而下降，但DS-FP和UBSS始終優(yōu)于ML。當(dāng)密度因子為0.63時(shí)，ML的成功率低至0.01，而DS-FP和UBSS的成功率仍然可以保持在0.79。當(dāng)密度因子低于0.55時(shí)，這三種方法都具有相同的成功率，因?yàn)檫@時(shí)所有任務(wù)集都可由ML調(diào)度。

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

圖5 CPU利用率比較

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

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

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

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

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

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

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