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

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

0 引 言

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

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

圖1 CPS控制系統(tǒng)的通用框架及設(shè)計關(guān)注點

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

1 CPS實時數(shù)據(jù)服務(wù)

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

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

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

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

實時數(shù)據(jù)對象的有效性間隔的實際值取決于應(yīng)用以及相應(yīng)實體的動態(tài)屬性[8]。許多RTDBS的重要設(shè)計目標(biāo)之一是保證實時數(shù)據(jù)的新鮮度，訪問無效數(shù)據(jù)值可能會嚴(yán)重影響系統(tǒng)的實時功能[3-5,13]。

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

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

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

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

對于可調(diào)度的ML，事務(wù)τi(1≤i≤m)應(yīng)當(dāng)滿足三個約束條件：

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

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

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

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

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

di,j+1-ri,j≤Vi

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

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

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

特征1：調(diào)度滿足有效性約束。

特征2：在線調(diào)度的時間復(fù)雜度為O(1)。

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

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

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

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

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

3 仿真結(jié)果

實驗都是利用MATLAB下的simulink工具實現(xiàn)。

3.1 ML和DS-FP的性能比較

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

CPU工作負(fù)載的比較。

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

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

ML和DS-FP產(chǎn)生的更新事務(wù)的CPU工作負(fù)載的定量比較結(jié)果如圖2所示。

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

圖2 CPU負(fù)載比較

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

3.2 可調(diào)度性比較

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

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

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

3.3 DS-LALF的性能評估

以下實驗評估DS-LALF算法中更新事務(wù)占用的CPU利用率及調(diào)度的成功率。實驗的參數(shù)設(shè)置同表2，結(jié)果如圖4所示。

圖4 調(diào)度成功率和CPU利用率的比較

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

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

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

4 結(jié)束語

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

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