劉述田

(大連東軟信息學(xué)院，大連 116023)

0 引 言

分布式虛擬環(huán)境(DVE)中有很多人與環(huán)境或者人與人的交互活動(dòng)，這些活動(dòng)可以抽象為非周期性的實(shí)時(shí)任務(wù)。在實(shí)際應(yīng)用開(kāi)發(fā)過(guò)程中，可以在分布式實(shí)時(shí)仿真系統(tǒng)中按照HLA規(guī)則開(kāi)發(fā)RTI，以提高效率。然而HLA至今已經(jīng)發(fā)展到IEEE 1516-2010[1]，并沒(méi)有把實(shí)時(shí)性作為一項(xiàng)要求放在規(guī)則當(dāng)中，按照其開(kāi)發(fā)的系統(tǒng)并不能滿(mǎn)足實(shí)時(shí)性要求。例如，DVE中有大量的互操作以及人在回路中的情形，因此當(dāng)一個(gè)操作發(fā)生之后，系統(tǒng)需要給出可預(yù)測(cè)的響應(yīng)，如果不能在交互活動(dòng)的截止期限前完成通信并進(jìn)行響應(yīng)，那么系統(tǒng)就會(huì)給人以嚴(yán)重失真的感覺(jué)，甚至?xí)虼俗龀鲥e(cuò)誤判斷與動(dòng)作，所以需要保證互操作活動(dòng)的實(shí)時(shí)性。

正如HLA并沒(méi)有把實(shí)時(shí)性作為一項(xiàng)要求放在規(guī)則當(dāng)中一樣，容錯(cuò)性能也沒(méi)有作為規(guī)則在HLA中體現(xiàn)出來(lái)，一般的應(yīng)用如果需要系統(tǒng)或任務(wù)容錯(cuò)，必須在應(yīng)用內(nèi)進(jìn)行容錯(cuò)開(kāi)發(fā)。對(duì)于一些重要的實(shí)時(shí)性任務(wù)，系統(tǒng)必須能夠保證它們?cè)诮刂蛊谙迌?nèi)完成，如果不能完成，則會(huì)帶來(lái)比較嚴(yán)重的后果。如果任務(wù)出現(xiàn)異?；蚬收?，也會(huì)造成任務(wù)不能實(shí)時(shí)響應(yīng)。本文研究在非周期任務(wù)出現(xiàn)暫態(tài)異常時(shí)的調(diào)度方法。

1 非周期任務(wù)容錯(cuò)模型

在HLA擴(kuò)展中，“故障”定義為，發(fā)生在聯(lián)邦內(nèi)部或者運(yùn)行環(huán)境中，能夠阻止整個(gè)聯(lián)邦以HLA兼容的方式交互的問(wèn)題[2]。上述這些故障從系統(tǒng)體系結(jié)構(gòu)這一層次提出來(lái)的，而沒(méi)有涉及到底層故障模型及容錯(cuò)模型和調(diào)度算法。

文獻(xiàn)[3]已經(jīng)論述過(guò)，周期性任務(wù)是易于預(yù)測(cè)的，非周期任務(wù)給系統(tǒng)實(shí)時(shí)性帶來(lái)較大的不確定性，然而其卻在較大程度上影響了對(duì)系統(tǒng)實(shí)時(shí)性的判斷，因?yàn)榉侵芷谛缘娜蝿?wù)往往是人機(jī)交互或者聯(lián)邦成員之間交互的請(qǐng)求，因此非周期任務(wù)的實(shí)時(shí)性以及可靠性就提高到了很重要的地位。

當(dāng)錯(cuò)誤檢測(cè)手段檢測(cè)到了任務(wù)產(chǎn)生的故障之后，容錯(cuò)機(jī)制就需要處理這個(gè)故障以提高系統(tǒng)的可靠性。最簡(jiǎn)單的容錯(cuò)技術(shù)就是重復(fù)執(zhí)行該任務(wù)，其在功能上與主副版本技術(shù)[4]類(lèi)似，不過(guò)重運(yùn)行技術(shù)可以重復(fù)執(zhí)行多次而不受副版本數(shù)量的限制。

由于非周期任務(wù)在較大程度上影響了對(duì)系統(tǒng)實(shí)時(shí)性的判斷，因此必須給非周期任務(wù)以較高的優(yōu)先權(quán)運(yùn)行，在文獻(xiàn)[3]內(nèi)，有足夠的處理器時(shí)間運(yùn)行所有的任務(wù)，可以采用EDF算法，但是當(dāng)非周期任務(wù)出現(xiàn)錯(cuò)誤的時(shí)候，就需要提高該任務(wù)的優(yōu)先權(quán)，盡量減少由于其它非周期任務(wù)高于該任務(wù)的優(yōu)先權(quán)而搶占，造成過(guò)多不必要的搶占開(kāi)銷(xiāo)，使它不僅能夠在截止期限前完成，更需要它盡快完成。在這里，由于周期性任務(wù)周期性更新，因此不予考慮容錯(cuò)。

給定非周期任務(wù)集合X={J1,…,Jn}的一個(gè)任務(wù)Ji可以用一個(gè)三元組來(lái)描述：

Ji=

本文研究的調(diào)度策略前提條件如下：

(1)僅考慮非周期任務(wù)的暫時(shí)性軟件錯(cuò)誤，如果任務(wù)Ji出現(xiàn)錯(cuò)誤，則系統(tǒng)立即啟用容錯(cuò)策略，進(jìn)行容錯(cuò)處理；

(2)非周期任務(wù)是相互獨(dú)立的，即沒(méi)有由于時(shí)序優(yōu)先約束、同步或者因?yàn)楣蚕碣Y源而產(chǎn)生的阻塞；

(3)在故障模型中，假設(shè)兩個(gè)連續(xù)出現(xiàn)的故障之間有最小間隔，用PF表示．它是系統(tǒng)容錯(cuò)能力的一個(gè)標(biāo)準(zhǔn)，PF的值越小就表示系統(tǒng)的容錯(cuò)能力越強(qiáng)。

文獻(xiàn)[4]研究了硬實(shí)時(shí)系統(tǒng)中周期性任務(wù)的主版本和替代版本容錯(cuò)方式下，采用了容錯(cuò)優(yōu)先級(jí)可提升的雙重優(yōu)先級(jí)分配策略，不僅提高了系統(tǒng)的容錯(cuò)能力，也能夠減少任務(wù)之間的搶占開(kāi)銷(xiāo)。本文借鑒了其優(yōu)先權(quán)可提升的思想，在非周期任務(wù)的實(shí)時(shí)系統(tǒng)中對(duì)其進(jìn)行基于任務(wù)重運(yùn)行的調(diào)度算法研究。

對(duì)于優(yōu)先權(quán)繼承協(xié)議，一個(gè)任務(wù)被阻止的次數(shù)是有限的，但不能阻止死鎖。相比之下，優(yōu)先權(quán)上限協(xié)議(Priority-Ceiling Protocol)[5]阻止一個(gè)任務(wù)至多一次，并能夠防止死鎖。每個(gè)共享資源都有優(yōu)先權(quán)上限，它的值等于所有可能使用這個(gè)資源的任務(wù)的優(yōu)先權(quán)最大值。但是只有當(dāng)一個(gè)任務(wù)的優(yōu)先權(quán)高于所有鎖定該資源的任務(wù)的優(yōu)先權(quán)的情況下，該任務(wù)才可以鎖定這個(gè)共享資源。

當(dāng)任務(wù)Ji發(fā)生故障的時(shí)候，因?yàn)镋DF是根據(jù)最早的截止期限來(lái)確定任務(wù)的優(yōu)先權(quán)，而發(fā)生故障之后重復(fù)運(yùn)行時(shí)其截止期限并沒(méi)有發(fā)生改變，所以會(huì)繼承之前的優(yōu)先級(jí)，這樣，任務(wù)已經(jīng)運(yùn)行了一段時(shí)間之后出現(xiàn)故障，耽誤了一段時(shí)間，要重新運(yùn)行，在原來(lái)的優(yōu)先級(jí)上就不一定能保證任務(wù)在截止期限前完成了。雖然繼承優(yōu)先級(jí)策略相對(duì)簡(jiǎn)單，但卻不一定能適合于我們這種情形。

針對(duì)這種情形，文獻(xiàn)[6]提出了提升優(yōu)先級(jí)的調(diào)度策略，文獻(xiàn)[4]在此基礎(chǔ)上完善了當(dāng)故障任務(wù)重新運(yùn)行時(shí)提升它的優(yōu)先級(jí)的策略，這種策略可以在任務(wù)不能滿(mǎn)足截止期限的情況下提升容錯(cuò)任務(wù)的可調(diào)度性，在一定程度上緩解了系統(tǒng)的容錯(cuò)壓力。從這個(gè)角度來(lái)說(shuō)優(yōu)先級(jí)提升的策略要優(yōu)于優(yōu)先級(jí)繼承的策略。

2 WCRT的計(jì)算

任務(wù)Ji的最壞情形響應(yīng)時(shí)間(WCRT)會(huì)受到是否發(fā)生故障影響，在容錯(cuò)調(diào)度算法下，發(fā)生故障的任務(wù)要重復(fù)運(yùn)行，因此會(huì)被本身和比它優(yōu)先權(quán)高的任務(wù)影響到，因此WCRT的計(jì)算方法如下[7]：

(1)

如果發(fā)生故障情形下WCRT小于截止期限di，那么這個(gè)任務(wù)集合就可以在第二次錯(cuò)誤到來(lái)之前被調(diào)度運(yùn)行。

從公式(1)可以看出，任務(wù)的響應(yīng)時(shí)間的變化受第三項(xiàng)影響比較明顯，如果此時(shí)有任務(wù)發(fā)生故障，并且優(yōu)先權(quán)高于任務(wù)Ji，那么其等待時(shí)間會(huì)比較長(zhǎng)，而且因?yàn)檫^(guò)多的搶占也消耗系統(tǒng)處理能力，有可能最后錯(cuò)過(guò)截止期限。所以，容錯(cuò)的任務(wù)在故障后要提升優(yōu)先權(quán)，盡量少的被其它任務(wù)搶占，以保證在截止期限前完成。

WCRT的計(jì)算分以下兩種情況進(jìn)行：

由于本文重點(diǎn)考慮非周期任務(wù)的實(shí)時(shí)性，周期性任務(wù)每隔固定時(shí)間更新，因此，不考慮對(duì)周期任務(wù)進(jìn)行容錯(cuò)。

(2)

(3)

(4)

(5)

這是一個(gè)迭代計(jì)算的式子，具體方法可以參見(jiàn)下式：

(6)

容錯(cuò)任務(wù)的調(diào)度不僅要能保證自己能在截止期限完成，也要保證其他任務(wù)在截止期限前完成，不能因?yàn)楣收隙騺y其它任務(wù)的調(diào)度。

由文獻(xiàn)[3]可知，在時(shí)間步進(jìn)式聯(lián)邦中，所有的任務(wù)實(shí)例要么在一個(gè)步長(zhǎng)內(nèi)完成，要么在下一個(gè)步長(zhǎng)內(nèi)完成，不能跨越兩個(gè)步長(zhǎng)，那么

ti≤Δt

(7)

同時(shí)

ti≤di

(8)

根據(jù)周期性任務(wù)在每一個(gè)步長(zhǎng)的運(yùn)行情況，事先確定每個(gè)步長(zhǎng)內(nèi)非周期任務(wù)可以占用的最大比率UA，故第m個(gè)步長(zhǎng)可以調(diào)度的非周期任務(wù)集合F(m)必須滿(mǎn)足如下條件：

(9)

若要滿(mǎn)足非周期任務(wù)的實(shí)時(shí)性，必須同時(shí)滿(mǎn)足式(7)、式(8)和式(9)。

表1 優(yōu)先級(jí)提升的方法

在能保證所有的任務(wù)都能滿(mǎn)足時(shí)間約束的條件下，為每一個(gè)任務(wù)找到最大的優(yōu)先級(jí)，以防止優(yōu)先級(jí)較低的任務(wù)搶占到優(yōu)先級(jí)較高的任務(wù)的容錯(cuò)，這樣就能減少搶占的處理器開(kāi)銷(xiāo)，從而提高效率。

3 仿真測(cè)試與分析

仿真為了測(cè)試容錯(cuò)調(diào)度算法的容錯(cuò)能力，設(shè)計(jì)一個(gè)測(cè)試環(huán)境，能夠測(cè)試兩個(gè)連續(xù)出現(xiàn)的故障之間的最小間隔PF是系統(tǒng)容錯(cuò)能力的一個(gè)標(biāo)準(zhǔn)，PF的值越小就表示系統(tǒng)的容錯(cuò)能力越強(qiáng)。

仿真實(shí)驗(yàn)的測(cè)試系統(tǒng)采用如圖1的系統(tǒng)，以federate1作為研究對(duì)象：

圖1 仿真測(cè)試系統(tǒng)組織結(jié)構(gòu)

仿真實(shí)驗(yàn)除了運(yùn)行周期性任務(wù)和邦員1內(nèi)部的其它任務(wù)之外，還為產(chǎn)生非周期任務(wù)的federateA1模擬了非周期任務(wù)，每個(gè)任務(wù)的占用的處理器時(shí)間在[1, 5]ms內(nèi)均勻分布，隨機(jī)選出，釋放時(shí)間在仿真時(shí)間段內(nèi)服從參數(shù)為每個(gè)步長(zhǎng)2個(gè)的泊松分布，UA設(shè)為15%。每個(gè)任務(wù)的截止期限設(shè)為從其釋放開(kāi)始之后50 ms，如果在一個(gè)步長(zhǎng)30 ms內(nèi)不能完成就安排到下一個(gè)步長(zhǎng)內(nèi)運(yùn)行。仿真時(shí)間長(zhǎng)度為1000個(gè)步長(zhǎng)，即30000 ms。

仿真共進(jìn)行50次，每次仿真都安排間隔為PF、處理時(shí)間3 ms的周期任務(wù)模擬發(fā)生故障的非周期任務(wù)，測(cè)試其響應(yīng)時(shí)間，每個(gè)任務(wù)的截止期限也設(shè)為從其釋放開(kāi)始之后50 ms以計(jì)算優(yōu)先級(jí)。PF的值分別取處理時(shí)間3 ms的正整數(shù)倍，每次仿真增加1倍，從1倍增加至50倍，即150 ms。把每次仿真中所有模擬任務(wù)的響應(yīng)時(shí)間取算術(shù)取平均值作為仿真結(jié)果。

算法用C++語(yǔ)言在Visual Studio 2010環(huán)境下實(shí)現(xiàn)，在Core i5 2.50 GHz CPU硬件平臺(tái)上運(yùn)行。

仿真結(jié)果如圖2所示，橫軸為實(shí)驗(yàn)組編號(hào)，同時(shí)也是PF與任務(wù)處理時(shí)間的比值，縱軸為任務(wù)平均響應(yīng)時(shí)間(ms)和丟失的任務(wù)的比例(%)。

圖2 容錯(cuò)任務(wù)的平均響應(yīng)時(shí)間

從圖中可以看出來(lái)，當(dāng)PF在6倍處理時(shí)間以下的時(shí)候，任務(wù)的響應(yīng)時(shí)間非常長(zhǎng)，最高達(dá)到500 ms，遠(yuǎn)遠(yuǎn)超過(guò)預(yù)定的截止期限50 ms，這是因?yàn)榧俣ǖ娜蝿?wù)出錯(cuò)頻率太高，處理器根本沒(méi)有時(shí)間來(lái)處理這么多容錯(cuò)任務(wù)，因而丟失了約70%的任務(wù)，當(dāng)PF增大的時(shí)候響應(yīng)時(shí)間仍然沒(méi)有減小，但是丟失任務(wù)的比例卻在下降。當(dāng)PF過(guò)了一個(gè)臨界點(diǎn)(這里是6倍平均任務(wù)處理時(shí)間)，容錯(cuò)任務(wù)的響應(yīng)時(shí)間與非周期任務(wù)的平均響應(yīng)時(shí)間基本持平，這說(shuō)明只要有足夠的處理器時(shí)間，容錯(cuò)調(diào)度算法是能達(dá)到容錯(cuò)需求的。事實(shí)上，任務(wù)的故障間隔應(yīng)該比6倍處理時(shí)間高很多，所以在本系統(tǒng)內(nèi)基于任務(wù)重運(yùn)行的容錯(cuò)調(diào)度算法可以達(dá)到容錯(cuò)性能要求。

4 結(jié) 語(yǔ)

HLA并沒(méi)有把實(shí)時(shí)性和容錯(cuò)性能作為一項(xiàng)要求放在規(guī)則當(dāng)中，因此RTI中任務(wù)的容錯(cuò)需要開(kāi)發(fā)者根據(jù)應(yīng)用的具體情況開(kāi)發(fā)適合的容錯(cuò)方法。

本文主要研究了在HLA/RTI系統(tǒng)中，實(shí)時(shí)性要求較強(qiáng)的互操作或人與機(jī)器的交互的時(shí)候產(chǎn)生的非周期任務(wù)的容錯(cuò)調(diào)度方法。基于重運(yùn)行的容錯(cuò)調(diào)度算法，在考慮了所有的非周期任務(wù)的最壞情形響應(yīng)時(shí)間的前提下，把故障任務(wù)的優(yōu)先級(jí)和其它任務(wù)修改到最優(yōu)的程度，減少了任務(wù)之間的搶占，因而能夠增加任務(wù)容錯(cuò)的可調(diào)度性。