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

邵亞麗，陳海華，張立臣，陳曉純

(1.廣東理工學院 信息工程系，廣東 肇慶 526000；2.廣東財經大學華商學院 數據科學學院，廣東 廣州 511300；3.廣東工業大學 計算機學院，廣東 廣州 510000)

0 引 言

CPS是一個多維復雜系統，通過計算、通信和控制等相關技術的相互協作，將信息世界和物理世界進行深度融合，實現實時感知、信息服務以及動態控制的功能。作為下一代智能化、網絡化、機電一體化控制系統的核心技術，CPS具有重大研究價值。大數據時代，CPS面臨著重大挑戰，它必須能夠實時感知、實時通信、實時控制，因此實時性是CPS的重要特征。該文從CPS的數據管理層面研究了它的實時性方法，并對這些方法進行研究、改進、仿真證明。

CPS是一個具有清晰架構和使用流程的技術體系，而非一項簡單的技術，對工業數據具有實時分析、實時處理的能力。它包含數據的整個處理流程(采集、聚合、解析、排序、分析、預測、決策和分發等)，并在分析過程中充分考慮各種特征和要求，例如邏輯、流程關系、目標等。在類似自動汽車、智能電網、建筑控制和醫療健康等CPS基礎設施中，監視和控制至關重要。傳統的控制系統的設計關注點如不確定性、物理干擾、魯棒控制和自適應控制不同，CPS反映了控制系統與計算技術的集成水平。受工業控制系統的啟發，如圖1所示，該文對CPS中的控制服務進行分層設計，展示了控制服務的不同設計層面，包括架構層、特定控制設計關注點和云那部分架構。在該架構中，主要關心延遲和實時控制操作。CPS的實時行為是多種不同操作的結合，如傳感、處理、通信和執行。這迫切需要一個將這些領域的現有研究成果和新的解決方案包含進來的統一實時操作理論，以保證CPS系統的實時性操作。為保證實時數據庫中的數據新鮮度和系統控制質量，該文從物理控制層出發，設計有效的算法來執行和調度傳感器的更新和控制任務。

圖1 CPS控制系統的通用框架及設計關注點

為了保持時間有效性，需要生成傳感器更新事務，以周期性地更新系統環境中實時數據對象的值[1]。傳感器更新事務具有無限數量的周期性作業，這些作業具有固定長度的周期和相對截止時間。目前已有許多學者為維持實時數據的有效性和新鮮度進行了廣泛的研究工作[2-7]。其中一些使用周期性更新事務，而其他的一些處理非周期性更新事務。第二類，如文獻[6-7]，主要設計用于軟實時系統，解決如何在運行時調度更新事務，以最大化實時數據對象的新鮮度，同時最小化它們對應用程序的實時事務處理的影響。盡管這些方法已被證明能有效地實現更好的平均性能，但是它們不能為實時事務的執行提供數據有效性保證。相反，使用周期性更新事務的那些方法的性能目標是對數據有效性提供保證。該文在已有的周期性調度算法的基礎上提出的改進算法在有效保證數據有效性的同時，最小化更新工作量。

1 CPS實時數據服務

通常CPS是深嵌于物理世界，用以將搜集到的動態物理測量結果(實時數據)存儲到實時數據庫(RTDBS)。接著其子系統就能夠對這些實時數據進行查詢，然后執行控制操作。作為一個實時控制系統，保證CPS子系統查詢數據的新鮮度是保證控制任務的正確及時執行的前提，因此顯得尤為重要。與傳統關系數據庫中的數據不同，實時數據有時間語義，即采樣值只在特定的時間段內有效[8-11]。大數據時代，CPS呈現出多模行為并且系統中的更新和控制工作負載動態變化，為了保證系統數據的新鮮度和控制質量，同時減少系統和網絡開銷，CPS如何高效處理和調度傳感器的更新和控制任務是個亟需解決的問題，因此有必要設計解決這類問題的算法。

定義1(實時數據)：一個實時數據對象Xi可以用一個三元組表示，Xi=(Val,Vi,Ri)，其中Val、Vi、Ri分別指數據對象的當前值、有效期間隔、采樣時間。

定義2(數據的時間有效性)：在任意時刻t，采樣的實時數據對象Xi的數據值在t+Vi內是暫時有效的,之后它是無效的或過時的。則稱該實時數據是時間有效的。

定義3(抖動時間)：即傳感器產生的數據更新事務τi到達實時數據庫系統的時間和采樣時間的差值[12]。

實時數據對象的有效性間隔的實際值取決于應用以及相應實體的動態屬性[8]。許多RTDBS的重要設計目標之一是保證實時數據的新鮮度，訪問無效數據值可能會嚴重影響系統的實時功能[3-5,13]。

2 實時系統調度

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

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

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

對于可調度的ML，事務τi(1≤i≤m)應當滿足三個約束條件：

(1)有效約束：事務τi的周期和相對截止時間的和總是小于或等于Vi，即Di+Pi≤Vi，如圖2所示。

(2)截止時間約束：更新事務的周期需大于其更新的實時數據的有效期間隔長度1/2，而它相應的截止時間小于或等于該實時數據對象的有效期長度的1/2。對于即將被調度的事務τi，其截止時間Di必須大于或等于τi的最壞情況執行時間Ci，即Pi≥Vi/2,Di≤Vi/2,Ii+Ci≤Di≤Pi。

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

類似的，DS-FP算法中更新事務τi(1≤i≤m)也需滿足三個約束條件：

(1)有效性約束：Ji,j的釋放時間和Ji,j+1的完成時間之間的最大間隔不能超過τi的有效期間隔Vi，即：

di,j+1-ri,j≤Vi

(2)截止時間約束：后繼作業Ji,j+1的相對截止時間不大于其執行時間，且不大于其周期，即：

和ML一樣，DS-FP也是基于最短有效期優先(Shortest Validity First，SVF)為事務分配優先級，即按實時數據對象的有效期的長度來分配優先級，有效期越短優先級越高，這有利于松弛度(Vi-Ci)較小的事務。

雖然DS-FP是一種能有效減少處理器利用率同時保證有效性約束的算法，但是受到在線調度開銷的影響，線調度開銷在時間復雜性方面遠高于ML。此外，DS-FP的調度開銷取決于事務的數量和更新數據的有效性時長。因此，在事務集變大時，DS-FP的代價可能變得非常大。和以任務周期的最小公倍數為其超級周期的周期性調度相反，DS-FP算法通常沒有這樣的自然超級周期。因此引入兩個具有超級周期的可延遲調度算法(deferrable scheduling with hyperperiod，DESH)：DESH-SC()和DESH-SA，用于從DS-FP算法中離線構造周期調度，可減少在線調度的時間復雜性。這兩個DESH算法具有以下兩個特征：

特征1：調度滿足有效性約束。

特征2：在線調度的時間復雜度為O(1)。

DESH-SC的基本思想是：搜索可以無限重復而不違反DS-FP調度的超級周期。如果找不到超級周期，則DESH-SC返回。DESH-SC算法由兩部分組成：一個用于離線找到超級周期的算法和一個在線調度事務的算法。一旦發現超級周期，后者就變得不重要了，因為它只需要重復超級周期的調度。

DESH-SA的基本思想是:為一組滿足有效性約束的事務T離線構造一個超級周期調度SH，假設SH調度的第一個超級周期的長度為||SH||。如果可以通過調整時間段[0,||SH||]內的DS-FP調度來構建SH的第一個超級周期，則可以通過每個||SH||時間單元無限重復SH的第一個超級周期來構建完整的SH調度。因此，和DESH-SC類似，DESH-SA算法由兩部分組成：用于離線構建超級周期的算法和一個用來在線調度事務的算法。

由于DS-FP是一個固定優先級調度算法，限制了需要使用動態優先級調度的系統對它的應用。為了克服該缺陷，提出一種稱為具有最小實際松弛優先的可延遲調度的動態調度算法(DS-LALF)，以保證實時數據對象的有效性。作業的實際松弛是在作業錯過它的截止時間之前通過考慮要執行較高優先級作業所需要的空閑時間來衡量該作業允許的空余時間。

DS-EDF是文獻中最先研究動態優先級系統中的可延遲調度。在DS-EDF中，每個更新事務的所有第一個作業的釋放時間被初始化為零，且它們的截止時間被分配為相應的有效性長度。將被調度的更新作業按照它們的截止時間的升序順序放入隊列QEDF中。然后，總是最先調度QEDF中具有最早截止時間的作業。對于每個更新事務的第一個作業，它們從指定的釋放時間0開始調度，而所有其他作業從它們的截止時間向后調度，并通過考慮從調度中的較高優先級作業的總搶占來推出它們的釋放時間。一旦作業Ji,j完成，其下一個作業Ji,j+1的截止時間di,j+1被設為ri,j+1+Vi，并將Ji,j+1放入QEDF隊列中。當作業是不可調度時，該算法失敗，即計算到它的釋放時間小于它前面作業的截止時間。

雖然DS-EDF使用比DS-FP更靈活的優先級分配，但它的可調度性并不比DS-FP好。與DS-EDF類似，DS-LALF是DS-FP的擴展。兩個連續更新作業之間的間隔是根據在運行時中的較高優先級作業的總搶占來確定的，而不是使用最壞情況的響應時間。然而，與根據其最后截止時間為每個更新作業Ji,k分配優先級的DS-EDF不同，DS-LALF使用實際松弛，即在它前面的更新工作Ji,k-1完成后，根據時間段[di,k-1,di,k]中的可用空閑時隙數來決定作業的優先級。實際松弛在更新作業中考慮了上述可調度性約束，它更好地指示了作業的緊急程度，并且更適應于調度，特別是當作業的負載很重時。

3 仿真結果

實驗都是利用MATLAB下的simulink工具實現。

3.1 ML和DS-FP的性能比較

第一組實驗主要用于比較算法ML、DS-FP、DESH-SC和DESH-SA在處理一組相同更新事務的工作負載。第二組實驗，主要研究DS-FP和ML的調度成功率。

CPU工作負載的比較。

表1中給出了本實驗使用的參數及它們的值。實時數據對象的數量從50變化到300，且假設每個實時數據對象的有效性間隔長度范圍為4 000 ms到8 000 ms。對于更新事務，假設每個事務更新一個實時數據對象，且每個事務的CPU時間從5 ms到15 ms均勻變化。根據這些參數隨機生成更新事務。

表1 實驗參數設置

ML和DS-FP產生的更新事務的CPU工作負載的定量比較結果如圖2所示。

由圖2可知，ML中的CPU工作負載始終低于DS-FP的CPU工作負載。且隨著更新事務量的增加，差異越大，當事務量為300時，差異達16.8%，這是因為DS-FP以較低速率自適應地采樣實時數據對象。注意DESH-SC的曲線僅在更新事務量為10到35的范圍內繪制。這是因為在實驗中，DESH-SC只能在更新事務數量不超過35時找到其超級周期。由圖還能發現，DESH-SC和DESH-SA的CPU工作負載幾乎和DS-FP的一樣，但是DESH-SA的工作負載始終低于ML。這是因為DESH-SA中截止時間調整對增加系統總體工作負載幾乎無影響。即使系統中的事務數量高達300， DESH-SA只會比DS-FP多不到1%的CPU工作負載。這是因為在實驗中，DS-FP忽略了在線調度開銷。DS-FP的實際CPU工作負載應高于圖中所示的值。

圖2 CPU負載比較

實驗表明DS-FP下的CPU負載少于ML中的CPU負載。

3.2 可調度性比較

表2 實驗參數設置

該組實驗，比較DS-FP和ML在各種CPU利用率下的調度成功率。在實驗中，系統中有10個更新事務，且密度因子在[0.5,0.72]間變化，實驗過程中通過固定Ci和減少Vi來增加密度因子。對每個點運行200次，記錄它們的平均值。圖3(a)為DS-FP和ML的調度成功率結果圖。可以發現DS-FP在可調度性方面始終優于ML。且可由ML調度的所有任務集也均可由DS-FP調度。當密度因子為0.58時，ML的成功率下降到0.85以下。而在DS-FP中只有當密度因子大于0.63時，才會發生。此外，當密度因子為0.64時，大多數事務集不能由ML調度，而DS-FP的成功率仍然在0.55左右。圖3(b)描述了在ML和DS-FP下可調度的任務集對應的CPU利用率，表明ML始終高于DS-FP的CPU利用率，且當密度因子增加時它們的差異增加。當密度因子為0.67時，差異達到18.6%，此時ML的調度成功率接近0。實驗表明DS-FP的性能比ML好。

圖3 ML和DS-FP的成功率及CPU負載對比

3.3 DS-LALF的性能評估

以下實驗評估DS-LALF算法中更新事務占用的CPU利用率及調度的成功率。實驗的參數設置同表2，結果如圖4所示。

圖4 調度成功率和CPU利用率的比較

由圖4(a)可知，DS-FP和DS-LALF的CPU利用率始終低于ML，特別是在更新事務的數量較大時。當系統中有24個更新事務時，DS-FP在ML上的改善為9.5%，DS-LALF在ML上的改善為11.2%。且可以發現DS-LALF的CPU利用率始終略低于DS-FP的，并明顯低于ML，特別是當更新事務數更大時。這表明在CPU利用率方面，DS-LALF的性能優于DS-FP以及ML，因為它根據可用時隙數根據它們的緊急程度自適應地調度作業。

在圖4(b)中通過改變密度因子來比較在不同更新工作負載下這幾個算法間的可調度性。該圖描述了由5個更新事務組成的系統的密度因子從0.35變化到0.65時，它們的調度的成功率，其中執行時間總是設置為最壞情況值。對每個點運行200次，圖中結果是它們的平均值。

由圖4(b)可得，DS-LALF的調度成功率始終高于ML和DS-EDF，但略低于DS-FP。當密度因子為0.55時，ML和DS-EDF的成功率下降到0.85以下。而在DS-FP和DS-LALF中，只有當密度因子分別為0.6和0.59時發生。此外，當密度因子為0.63時，幾乎所有事務集都不能由ML和DS-EDF調度，而DS-FP和DS-LALF的成功率分別仍在0.27和0.1左右。還能發現DS-EDF的調度成功率隨不同的密度因子值波動較大。當密度因子值較小時，它的可調度性與ML，DS-LALF和DS-FP類似，因為工作負載小。但是，當密度因子較高時，與DS-LALF和DS-FP相比，DS-EDF的可調度性不穩定，原因是引入的動態調度機制以使用最早截止時間優先來調度更新作業可能使一些作業在被CPU長時間服務后錯失了它們的截止時間。

4 結束語

CPS的實時數據服務是其實時性研究的重要部分，該文主要談論了固定優先級環境下，實時數據庫中周期性和非周期性事務的實時調度算法問題，分析研究了幾個較為經典的周期性事務實時調度算法HH和ML以及非周期可延遲調度算法DS-FP，它們都能很好地維持實時數據時間有效性。此外，研究了基于DS-FP的新的和實用的方法，DESH-SC和DESH-SA，它們將在線調度開銷減少到O(1)。與ML相比，DS-FP大大降低了處理器工作負載。因此，當RTDBS使用DS-FP去跟蹤環境變化時，DS-FP可以提高應用程序事務的性能。DESH-SA是一種最小化傳感器更新工作量并保證有效性約束的非常有效的方法，并且在時間和空間復雜性方面具有高效性。

DS-LALF是DS-FP的增強方法，能在保持實時數據對象有效性的同時，進一步降低DS-FP的在線計算開銷并能適用于需要動態優先級分配的系統。DS-LALF與DS-FP應用相同的可延遲調度原理以盡可能晚地推遲更新作業的釋放時間，最大化來自同一更新事務的兩個連續更新作業之間的時差，最小化由更新事務引起的CPU工作負載。DS-LALF不使用最短有效性優先策略分配更新事務的優先級,而根據更新事務在運行過程中的實際松弛度為它們分配優先級。與DS-FP相比，DS-LALF具有更低的在線計算開銷和更低的更新工作負載。最后通過大量的仿真實驗進行了論證。