一種基于數據質量的多處理器平臺實時更新事務調度算法

白天，李國徽，申麗平

?

一種基于數據質量的多處理器平臺實時更新事務調度算法

白天1, 2，李國徽1，申麗平2

(1. 華中科技大學計算機科學與技術學院，湖北武漢，430074；2. 湖南理工學院計算機學院，湖南岳陽，414000)

提出一種多處理器平臺上基于數據質量的實時更新事務全局調度算法(MU-DA)。數據質量根據時態對象的無效程度來定義。算法通過合理地預分配各事務執行所需處理器資源以及動態控制更新實例的接納和執行使系統數據質量最大化。研究結果表明：MU-DA算法在各種事務集負載下均能保證較高的數據質量；在高負載設置下，MU-DA算法的系統數據質量與用戶事務質量均遠比基準算法MU-D與MU-SA的高，能夠很好地滿足用戶事務在數據實時性方面的要求。

信息物理融合系統；實時更新事務；數據質量；多處理器調度

信息物理融合系統(cyber physical system,CPS)是在環境感知的基礎上，通過計算、通信和控制能力的緊密結合來實現物理與計算過程深度融合的智能系統[1?2]。在CPS中，受監控的外部環境實體由實時數據對象(又稱時態對象)來表示。數據對象反映了實體的當前狀態，其采樣和更新由實時更新事務負責。系統應使用合理的策略來調度執行更新事務以保證數據對象的有效性，否則外部物理過程的變化將無法得到及時響應。現有的更新事務調度算法主要包括More?Less(ML)，DS?FP與基于早期截止期優先策略(EDF)的算法[3?10]。這些算法都是基于單處理器平臺來設計的，且采用了確定性的調度策略。其中，ML與基于EDF的算法采用周期性任務模型，兩者分別使用截止期單調策略(DM)與EDF策略來調度事務。DS?FP采用非周期性任務模型，在確保數據時態一致性的基礎上盡量推遲實例的開始時間。鑒于多核處理器在性能、功耗、可靠性等方面的優勢，研究多核(多處理器)平臺上的更新事務調度問題十分必要。盡管多處理器實時任務調度問題在近年來得到了廣泛研究[11]，但這些研究均沒有考慮數據的有效性約束，因此，不能直接用于更新事務的調度。另一方面，在視頻監控等CPS中，事務的最壞執行時間(WCET)一般比較長(遠超過大多數實例的實際執行時間)，采用確定性的調度策略將降低算法的調度成功率，使得算法在許多環境下無法有效地維護數據的時態一致性。確定性的調度策略也會造成資源過量分配，從而給系統中其他類型事務的執行帶來不利影響。XIONG等[12]提出了基于服務質量的調度算法來解決此問題。但該算法只是針對ML而設計的，因此，只能用于單處理器平臺，且算法沒有考慮用戶事務所讀取數據的聚集失效約束。本文首先給出一種綜合考慮單個數據對象的有效性及數據集上聚集失效約束的數據質量模型，然后，在此模型基礎上給出一種多處理器平臺上的事務調度算法。

1 數據質量模型

考慮在(≥2) 個同構處理器上調度更新事務集。其中，事務負責更新實時數據對象O，可表示為(g(), V, w)；概率密度函數g()描述了執行時間的分布情況；V為O的時態有效期；w為O的權重，滿足，w越大，O的重要程度越高。w可根據O在控制決策中所起的作用來定義。

定義1 實時數據對象O是有效的，或稱為時態一致的，(其中，c為系統的當前時間，為O當前值的采樣時間[13])。

多處理器平臺上的調度策略可分為3類：基于任務分派的調度方法、全局調度方法與混合調度方法[11]。基于任務分派的調度方法預先為每個任務指定1個處理器，任務只能在指定的處理器上執行。全局調度方法允許任務在執行過程中從處理器1轉移到處理器2上。混合調度方法通常使用某種策略將部分任務劃分為子任務，并將子任務分配到多個處理器上執行。混合調度方法可視為基于任務分派的調度方法與全局調度方法的綜合，但實現起來要比這2種方法復雜。本文使用全局方法來調度更新事務。

系統中的用戶事務通常根據一部分時態對象的值來進行決策，系統應充分保證這些數據對象的有效性。令()表示用戶事務(，為用戶事務集)讀取的時態對象集，Y表示()中的失效對象個數。給定失效對象數量閾值K與失效概率閾值P，聚集失效約束要求失效對象個數不少于K的概率應小于或等于P，即

2 基于數據質量的多處理器調度算法(MU-DA)

2.1 多處理器平臺上的事務預分配時間確定

根據數據質量的定義，MU?DA算法需要確定各個事務的預分配執行時間。預分配時間的設置首先必須滿足數據的時態一致性約束。即對于給定的，，能夠為找到相對截止期D與周期T，滿足以下條件：

算法1 temporal validity test for

Input: sensor transaction set

Output:DandTfor each

for=2 to

whileR≤V/2

D=R;

computeW(R);

endfor

computeRusing condition 2;

ifD=R

T=V?R, break;

endif

endwhile

ifR＞V/2

is unschedulable, return failure;

endif

endfor

事務預分配時間的設置還需要滿足聚集失效約束(式(2))。式(2)涉及的計算。通常(即()中所含時態對象的數目)較小，可以直接計算。令表示的前個數據對象中至少有個失效的概率，則可得如下遞推式：

在確保算法1執行成功和聚集失效約束得到滿足的前提下，預分配時間的設置應使得盡可能地小。由于問題中的約束均非凸且約束的導數也難以獲取，因此，基于梯度的優化方法難以奏效。這里利用模擬退火算法進行優化。傳統的模擬退火算法只能處理無約束優化問題，為此，利用雙序列方法[15]來處理約束。在具體進行優化之前，首先使用算法1判斷在WCET下是否可行，若可行，則為1，無需進一步處理。令表示算法生成的解序列中最近的可行解所對應的，表示此解序列中最近的不可行解的總約束違反量。由下式給出：

在第次迭代中，算法根據當前解生成至多個新解。當生成的新解優于當前解(即新解可行且其對應的小于)時，此解被接受；否則，新解將以概率被接受。當新解可行時，設置為此解的與之差，否則，設置為此解的總約束違反量()與之差。當算法所接受的新解為可行解時，設置為新解的；否則，設置為。

2.2 接納與執行控制策略

3 實驗評價

這里通過實驗對所提出的算法進行評價。現有的調度算法均為單處理器平臺上的算法，與它們比較沒有意義，為此，給出2種多處理器上的基準事務調度算法。第1種算法(MU-D)直接用WCET調度事務，通過將算法1中的替換為WCET即可實現。第2種算法(MU-SA)仍然采用文中方法確定事務的預分配時間，但系統在運行時不會接納任何實際執行時間大于預分配時間的實例。

算法的主要性能指標包括系統數據質量(SD)與用戶事務質量(UT)。若O在時間區間內的有效時間為L，則。若用戶事務讀取的所有時態對象均有效，則認為也是有效的。(其中，為成功執行的用戶事務個數，M為有效事務個數)。此外，算法產生的更新負載也將在實驗中進行比較。

實驗的主要參數及設置見表1。更新實例的計算時間滿足正態分布，其均值在[15, 25]內隨機選取。在實驗中，系統負載的變化通過更新事務數量的變化來實現。假定所有更新事務的權重均相同，用戶事務的數目設置為3。以泊松分布來生成用戶事務，每個事務均在中隨機選取。K設定為，在[0.1,0.25]內隨機選取。P設置為0.25，參數V與N都滿足均勻分布。系統使用EDF策略來調度用戶事務。

表1 主要參數及設置

處理器個數為2時3種算法的系統數據質量比較見圖1。由圖1可知：當事務個數不超過140時，3種算法的系統數據質量都為1，其原因是在此設置下，直接使用WCET就能夠成功調度事務集，因此，數據在任何時刻都是有效的；當事務個數超過140時，事務集的負載也較高，此時，MU-D幾乎無法調度任何事務集，因此，其系統數據質量也不再存在，而MU-SA與MU-DA使用較小的預分配時間來調度事務集，因此，仍然能保證一定的系統數據質量。這2種算法的系統數據質量都隨事務數量的增加而下降，但MU?SA的下降幅度遠比MU?DA的大，這使得MU?DA的系統數據質量一直比MU?SA的高。例如，當事務個數為240時，前者比后者高約0.14。原因是MU?DA的接納和執行控制策略使得系統能夠成功地執行一部分在MU?SA中被拒絕的實例，從而使得MU?DA的數據有效性時間比MU?SA的長。

算法：1—MU?D；2—MU?SA；3—MU?DA。

為了進一步說明MU?DA接納和執行控制策略的有效性，記錄實驗中MU?DA與MU?SA在截止期之前完成的實例數量，由此可得到相應的實例完成率。圖2所示為兩者完成率之差的變化情況。由圖2可知：大于零且隨事務數量的增加呈上升趨勢。其原因是事務預分配時間將隨事務數量的增加而減小，從而使得更多的實例被MU?SA拒絕，而MU?DA通過合理的選擇進入系統的實例和控制當前實例的運行能夠保證這些實例中的大部分在截止期前完成。

圖2 n=2時完成率之差?C

圖3所示為分別使用MU?SA與MU?DA調度更新事務時用戶事務質量的比較結果。從圖3可以看出：MU?DA下的用戶事務質量在不同的事務數量下均要比MU?SA的高，例如，當事務數量為200個時，前者比后者高約0.2；隨著事務數量增加，這2種算法下的用戶事務質量也隨之降低，且MU?SA的下降幅度要比MU?DA的大。其原因在于當事務數量超過140個時，MU?DA的系統數據質量一直要比MU?SA的高(見圖1)。系統數據質量越高，用戶事務在某一時刻訪問到有效數據的概率越大，因而，用戶事務本身有效的概率也會越高。當事務數量不到140個時，2種算法的系統數據質量都為1(見圖1)，因此，2種算法下的用戶事務質量也都為1。

圖3 n=2時用戶事務質量QUT比較

圖4所示為MU?SA與MU?DA產生的更新負載比較結果。由于當事務數量不大于140個時可使用WCET來調度事務集，因此，這2種算法的負載完全相同，故不在圖中給出。由圖4可知：MU?DA生成的負載在不同事務數量下均不比MU?SA的低；隨著事務數量增加，這2種算法生成的負載均會增加。其原因是MU?DA接納了更多的實例，從而使得其更新負載也相應增加。需要注意的是：MU?DA相對更高的負載也帶來了更高的系統數據質量，從提高數據質量的角度來說MU?DA產生的負載是合理的。

圖4 n=2時更新負載比較

當處理器數量為4和8個時，系統數據質量比較結果分別如圖5(a)與5(b)所示。從圖5可見：當處理器個數增加時，算法所支持的事務個數也隨之增加，但這3種算法之間的相對性能并不改變；在中、低負載下(處理器個數為4時，事務數量不超過290個；處理器個數為8時，事務數量不超過580個)，3種算法均能確保SD為1；在高負載下，MU?DA的SD要比MU?SA的高。此外，處理器個數的增加使得MU?DA與MU?SA的SD下降速度變慢。上述設置下算法的用戶事務質量數據與更新負載數據也分別與圖3和圖4所示的類似。除此之外，還考察了算法在處理器個數為16時的性能，結果也與上述實驗結果類似。

(a) n=4; (b) n=8

4 結論

1) 給出了一種數據質量模型。在模型中不僅考慮了單個時態對象的有效性，而且考慮了用戶事務讀取的時態對象集上的聚集失效約束。

2) 提出了一種基于全局方法的多處理器更新事務調度算法。該算法通過處理器資源的預先分配和事務實例的動態接納執行控制來最大化數據質量。算法在不同的事務集負載下都能提供較高的數據質量，能夠很好地滿足用戶事務對于數據實時性的要求。

3) 多處理器平臺上的實時任務調度算法除全局方法外，還包括基于任務分派的方法與混合方法。如何利用這2類方法進行數據質量的維護有待進一步研究。

[1] RAJKUMAR R, LEE I, SHA L, et al. Cyber-physical systems: the next computing revolution[C]// Proceedings of the 47th ACM/IEEE Design Automation Conference (DAC). Anaheim, CA, USA: IEEE, 2010: 731?736.

[2] 何積豐. 信息物理融合系統[J]. 中國計算機學會通訊, 2010, 6(1): 25?29. HE Jifeng. Cyber-physical systems[J]. Communications of the China Computer Federation, 2010, 6(1): 25?29.

[3] XIONG M, RAMAMRITHAM K. Deriving deadlines and periods for real-time update transactions[J]. IEEE Transactions on Computers, 2004, 53(5): 567?583.

[4] XIONG M, HAN S, LAM K Y, et al. Deferrable scheduling for maintaining real-time data freshness: algorithms, analysis, and results[J]. IEEE Transactions on Computers, 2008, 57(7): 952?964.

[5] HAN S, CHEN D J, XIONG M, et al. Schedulability analysis of deferrable scheduling algorithms for maintaining real-time data freshness[J]. IEEE Transactions on Computers, 2014, 63(4): 979?994.

[6] XIONG M, HAN S, CHEN D J, et al. DESH: overhead reduction algorithms for deferrable scheduling[J]. Real-Time Systems, 2010, 44(1/2/3): 1?25.

[7] LI J J, XIONG M, LEE V C S, et al. Workload-efficient deadline and period assignment for maintaining temporal consistency under EDF[J]. IEEE Transactions on Computers, 2013, 62(6): 1255?1268.

[8] WANG J T, HAN S, LAM K Y, et al. Maintaining data temporal consistency in distributed real-time systems[J]. Real-Time Systems, 2012, 48(4): 387?429.

[9] WANG J T, LAM K Y, HAN S, et al. On co-scheduling of periodic update and application transactions with fixed priority assignment for real-time monitoring[C]// IEEE 26th International Conference on Advanced Information Networking and Applications (AINA). Fukuoka, Japan: IEEE, 2012: 253?260.

[10] HAN S, LAM K Y, WANG J T, et al. On Co-scheduling of update and control transactions in real-time sensing and control systems: algorithms, analysis, and performance[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(10): 2325?2342.

[11] ROBERT I D, ALAN B. A survey of hard real-time scheduling for multiprocessor systems[J]. ACM Computing Surveys, 2011, 43(4): 1?44.

[12] XIONG M, LIANG B Y, LAM K Y, et al. Quality of service guarantee for temporal consistency of real-time transactions[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(8): 1097?1110.

[13] RAMAMRITHAM K. Real-time databases[J]. Distributed and Parallel Databases, 1993, 1(2): 199?226.

[14] BERTOGNA M,M. Response time analysis for global scheduled symmetric multiprocessor platforms[C]// Proceedings of the 28th IEEE International Real-Time Systems Symposium. Tucson, USA: IEEE, 2007: 149?160.

[15] OZDAMAR L. A dual sequence simulated annealing algorithm for constrained optimization[C]// Proceedings of the 10th WSEAS International Conference on Applied Mathematics. Dallas, Texas, USA, 2006: 557?564.

Quality of data based scheduling for real-time update transactions on multiprocessor platforms

BAI Tian1, 2, LI Guohui1, SHEN Liping2

(1. College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China; 2. College of Computer Science, Hunan Institute of Science and Technology, Yueyang 414000, China)

A quality of data (QoD) aware algorithm MU-DA was proposed to globally schedule the real-time update transactions on multiprocessors. The QoD measures the degree of invalidity of temporal data objects. To maximize the QoD, the algorithm pre-allocates resources of processors to update transactions, and then judiciously admits and schedules the update instances in the runtime. The results show that the proposed algorithm can guarantee high data quality under different system workloads. In particular, the system’s QoD and user transactions’ quality are much better than those of the baseline algorithms (MU-D and MU-SA) under high workloads, thus it can satisfy the data timeliness requirements of user transactions.

cyber physical systems; real-time update transactions; quality of data; multiprocessor scheduling

10.11817/j.issn.1672-7207.2016.09.021

TP311

A

1672?7207(2016)09?3066?06

2015?11?12；

2016?01?25

國家自然科學基金資助項目(61173049)；湖南省自然科學基金資助項目(2015JJ6044) (Project(61173049) supported by the National Natural Science Foundation of China; Project(2015JJ6044) supported by the Natural Science Foundation of Hunan Province)

白天，講師，從事實時數據庫及信息物理融合系統研究；E-mail: baitiannobel@163.com

(編輯 陳燦華)