一種基于數(shù)據(jù)質(zhì)量的多處理器平臺(tái)實(shí)時(shí)更新事務(wù)調(diào)度算法

白天，李國(guó)徽，申麗平

?

一種基于數(shù)據(jù)質(zhì)量的多處理器平臺(tái)實(shí)時(shí)更新事務(wù)調(diào)度算法

白天1, 2，李國(guó)徽1，申麗平2

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

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

信息物理融合系統(tǒng)；實(shí)時(shí)更新事務(wù)；數(shù)據(jù)質(zhì)量；多處理器調(diào)度

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

1 數(shù)據(jù)質(zhì)量模型

考慮在(≥2) 個(gè)同構(gòu)處理器上調(diào)度更新事務(wù)集。其中，事務(wù)負(fù)責(zé)更新實(shí)時(shí)數(shù)據(jù)對(duì)象O，可表示為(g(), V, w)；概率密度函數(shù)g()描述了執(zhí)行時(shí)間的分布情況；V為O的時(shí)態(tài)有效期；w為O的權(quán)重，滿足，w越大，O的重要程度越高。w可根據(jù)O在控制決策中所起的作用來定義。

定義1 實(shí)時(shí)數(shù)據(jù)對(duì)象O是有效的，或稱為時(shí)態(tài)一致的，(其中，c為系統(tǒng)的當(dāng)前時(shí)間，為O當(dāng)前值的采樣時(shí)間[13])。

多處理器平臺(tái)上的調(diào)度策略可分為3類：基于任務(wù)分派的調(diào)度方法、全局調(diào)度方法與混合調(diào)度方法[11]?；谌蝿?wù)分派的調(diào)度方法預(yù)先為每個(gè)任務(wù)指定1個(gè)處理器，任務(wù)只能在指定的處理器上執(zhí)行。全局調(diào)度方法允許任務(wù)在執(zhí)行過程中從處理器1轉(zhuǎn)移到處理器2上?；旌险{(diào)度方法通常使用某種策略將部分任務(wù)劃分為子任務(wù)，并將子任務(wù)分配到多個(gè)處理器上執(zhí)行?；旌险{(diào)度方法可視為基于任務(wù)分派的調(diào)度方法與全局調(diào)度方法的綜合，但實(shí)現(xiàn)起來要比這2種方法復(fù)雜。本文使用全局方法來調(diào)度更新事務(wù)。

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

2 基于數(shù)據(jù)質(zhì)量的多處理器調(diào)度算法(MU-DA)

2.1 多處理器平臺(tái)上的事務(wù)預(yù)分配時(shí)間確定

根據(jù)數(shù)據(jù)質(zhì)量的定義，MU?DA算法需要確定各個(gè)事務(wù)的預(yù)分配執(zhí)行時(shí)間。預(yù)分配時(shí)間的設(shè)置首先必須滿足數(shù)據(jù)的時(shí)態(tài)一致性約束。即對(duì)于給定的，，能夠?yàn)檎业较鄬?duì)截止期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

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

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

在第次迭代中，算法根據(jù)當(dāng)前解生成至多個(gè)新解。當(dāng)生成的新解優(yōu)于當(dāng)前解(即新解可行且其對(duì)應(yīng)的小于)時(shí)，此解被接受；否則，新解將以概率被接受。當(dāng)新解可行時(shí)，設(shè)置為此解的與之差，否則，設(shè)置為此解的總約束違反量()與之差。當(dāng)算法所接受的新解為可行解時(shí)，設(shè)置為新解的；否則，設(shè)置為。

2.2 接納與執(zhí)行控制策略

3 實(shí)驗(yàn)評(píng)價(jià)

這里通過實(shí)驗(yàn)對(duì)所提出的算法進(jìn)行評(píng)價(jià)?，F(xiàn)有的調(diào)度算法均為單處理器平臺(tái)上的算法，與它們比較沒有意義，為此，給出2種多處理器上的基準(zhǔn)事務(wù)調(diào)度算法。第1種算法(MU-D)直接用WCET調(diào)度事務(wù)，通過將算法1中的替換為WCET即可實(shí)現(xiàn)。第2種算法(MU-SA)仍然采用文中方法確定事務(wù)的預(yù)分配時(shí)間，但系統(tǒng)在運(yùn)行時(shí)不會(huì)接納任何實(shí)際執(zhí)行時(shí)間大于預(yù)分配時(shí)間的實(shí)例。

算法的主要性能指標(biāo)包括系統(tǒng)數(shù)據(jù)質(zhì)量(SD)與用戶事務(wù)質(zhì)量(UT)。若O在時(shí)間區(qū)間內(nèi)的有效時(shí)間為L，則。若用戶事務(wù)讀取的所有時(shí)態(tài)對(duì)象均有效，則認(rèn)為也是有效的。(其中，為成功執(zhí)行的用戶事務(wù)個(gè)數(shù)，M為有效事務(wù)個(gè)數(shù))。此外，算法產(chǎn)生的更新負(fù)載也將在實(shí)驗(yàn)中進(jìn)行比較。

實(shí)驗(yàn)的主要參數(shù)及設(shè)置見表1。更新實(shí)例的計(jì)算時(shí)間滿足正態(tài)分布，其均值在[15, 25]內(nèi)隨機(jī)選取。在實(shí)驗(yàn)中，系統(tǒng)負(fù)載的變化通過更新事務(wù)數(shù)量的變化來實(shí)現(xiàn)。假定所有更新事務(wù)的權(quán)重均相同，用戶事務(wù)的數(shù)目設(shè)置為3。以泊松分布來生成用戶事務(wù)，每個(gè)事務(wù)均在中隨機(jī)選取。K設(shè)定為，在[0.1,0.25]內(nèi)隨機(jī)選取。P設(shè)置為0.25，參數(shù)V與N都滿足均勻分布。系統(tǒng)使用EDF策略來調(diào)度用戶事務(wù)。

表1 主要參數(shù)及設(shè)置

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

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

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

圖2 n=2時(shí)完成率之差?C

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

圖3 n=2時(shí)用戶事務(wù)質(zhì)量QUT比較

圖4所示為MU?SA與MU?DA產(chǎn)生的更新負(fù)載比較結(jié)果。由于當(dāng)事務(wù)數(shù)量不大于140個(gè)時(shí)可使用WCET來調(diào)度事務(wù)集，因此，這2種算法的負(fù)載完全相同，故不在圖中給出。由圖4可知：MU?DA生成的負(fù)載在不同事務(wù)數(shù)量下均不比MU?SA的低；隨著事務(wù)數(shù)量增加，這2種算法生成的負(fù)載均會(huì)增加。其原因是MU?DA接納了更多的實(shí)例，從而使得其更新負(fù)載也相應(yīng)增加。需要注意的是：MU?DA相對(duì)更高的負(fù)載也帶來了更高的系統(tǒng)數(shù)據(jù)質(zhì)量，從提高數(shù)據(jù)質(zhì)量的角度來說MU?DA產(chǎn)生的負(fù)載是合理的。

圖4 n=2時(shí)更新負(fù)載比較

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

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

4 結(jié)論

1) 給出了一種數(shù)據(jù)質(zhì)量模型。在模型中不僅考慮了單個(gè)時(shí)態(tài)對(duì)象的有效性，而且考慮了用戶事務(wù)讀取的時(shí)態(tài)對(duì)象集上的聚集失效約束。

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

3) 多處理器平臺(tái)上的實(shí)時(shí)任務(wù)調(diào)度算法除全局方法外，還包括基于任務(wù)分派的方法與混合方法。如何利用這2類方法進(jìn)行數(shù)據(jù)質(zhì)量的維護(hù)有待進(jìn)一步研究。

[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] 何積豐. 信息物理融合系統(tǒng)[J]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊, 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

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

白天，講師，從事實(shí)時(shí)數(shù)據(jù)庫及信息物理融合系統(tǒng)研究；E-mail: baitiannobel@163.com

(編輯 陳燦華)