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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Deferrable Scheduling algorithm for Fixed Priority transactions(DS-FP)的基本思想是：以非周期性硬實(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ù)載[6,15-16]。其動(dòng)態(tài)地為更新事務(wù)的作業(yè)分配周期和相對(duì)截止時(shí)間。

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

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

di,j+1-ri,j≤Vi

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

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果

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

3.1 ML和DS-FP的性能比較

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

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

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

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

圖2 CPU負(fù)載比較

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

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

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

該組實(shí)驗(yàn)，比較DS-FP和ML在各種CPU利用率下的調(diào)度成功率。在實(shí)驗(yàn)中，系統(tǒng)中有10個(gè)更新事務(wù)，且密度因子在[0.5,0.72]間變化，實(shí)驗(yàn)過(guò)程中通過(guò)固定Ci和減少Vi來(lái)增加密度因子。對(duì)每個(gè)點(diǎn)運(yùn)行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時(shí)，ML的成功率下降到0.85以下。而在DS-FP中只有當(dāng)密度因子大于0.63時(shí)，才會(huì)發(fā)生。此外，當(dāng)密度因子為0.64時(shí)，大多數(shù)事務(wù)集不能由ML調(diào)度，而DS-FP的成功率仍然在0.55左右。圖3(b)描述了在ML和DS-FP下可調(diào)度的任務(wù)集對(duì)應(yīng)的CPU利用率，表明ML始終高于DS-FP的CPU利用率，且當(dāng)密度因子增加時(shí)它們的差異增加。當(dāng)密度因子為0.67時(shí)，差異達(dá)到18.6%，此時(shí)ML的調(diào)度成功率接近0。實(shí)驗(yàn)表明DS-FP的性能比ML好。

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

3.3 DS-LALF的性能評(píng)估

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

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

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

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

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

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

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

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