夏 平，周興社

西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，西安 710072

面向分布式實(shí)時(shí)系統(tǒng)的安全驅(qū)動(dòng)調(diào)度算法研究

夏 平，周興社

西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，西安 710072

1 引言

隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，實(shí)時(shí)系統(tǒng)被廣泛應(yīng)用于航空、航天、國(guó)防等重要領(lǐng)域。這些領(lǐng)域?qū)?shí)時(shí)系統(tǒng)上運(yùn)行的關(guān)鍵應(yīng)用提出了極高的安全性要求。為此這些領(lǐng)域所部署的實(shí)時(shí)系統(tǒng)在底層提供了不同類(lèi)型的安全服務(wù)，每種服務(wù)封裝并實(shí)現(xiàn)了特定的安全功能，在高層運(yùn)行的實(shí)時(shí)應(yīng)用通過(guò)調(diào)用這些安全服務(wù)，使得自身的安全需求得以滿(mǎn)足。但運(yùn)行安全服務(wù)增加了實(shí)時(shí)應(yīng)用的時(shí)間開(kāi)銷(xiāo)，從而對(duì)實(shí)時(shí)系統(tǒng)的可調(diào)度性造成了不可忽視的影響。此外，用戶(hù)可能會(huì)依據(jù)自身需求動(dòng)態(tài)調(diào)整系統(tǒng)的整體安全級(jí)別，造成安全開(kāi)銷(xiāo)分析的不確定性，增加了實(shí)時(shí)調(diào)度的難度。因此有必要研究一種新型實(shí)時(shí)調(diào)度算法，使其在適應(yīng)系統(tǒng)動(dòng)態(tài)安全需求的前提下，對(duì)實(shí)時(shí)應(yīng)用進(jìn)行合理的調(diào)度，以確保實(shí)時(shí)應(yīng)用的實(shí)時(shí)性和安全性需求得到滿(mǎn)足。

目前關(guān)于實(shí)時(shí)調(diào)度問(wèn)題的研究已經(jīng)十分成熟，這方面已經(jīng)取得了很多研究成果。文獻(xiàn)[1-4]提出了多種適用于分布式系統(tǒng)的實(shí)時(shí)調(diào)度算法，這些算法雖然能夠提高系統(tǒng)調(diào)度的效率，但是沒(méi)有考慮實(shí)時(shí)應(yīng)用的安全性需求，因而不適用于調(diào)度安全關(guān)鍵實(shí)時(shí)應(yīng)用。文獻(xiàn)[5]提出了一種安全感知實(shí)時(shí)調(diào)度算法SAEDF（Security Assurance EarlyDeadline First），該算法在調(diào)度過(guò)程中考慮了實(shí)時(shí)任務(wù)的安全開(kāi)銷(xiāo)，并利用任務(wù)的松弛時(shí)間來(lái)提升其安全級(jí)別，從而實(shí)現(xiàn)系統(tǒng)整體安全性能提升。文獻(xiàn)[6]提出了一種面向異構(gòu)集群系統(tǒng)的雙階段調(diào)度策略TPSS（Two Phase Scheduling Strategy），該策略依據(jù)系統(tǒng)當(dāng)前負(fù)載來(lái)調(diào)整任務(wù)安全級(jí)別，并保證系統(tǒng)獲得較高的調(diào)度成功率。但是SAEDF和TPSS均未考慮實(shí)時(shí)系統(tǒng)對(duì)實(shí)時(shí)應(yīng)用的動(dòng)態(tài)安全約束，且不支持調(diào)度軟硬混合的實(shí)時(shí)任務(wù)。文獻(xiàn)[7-8]提出了兩種面向分布式實(shí)時(shí)系統(tǒng)的啟發(fā)式調(diào)度算法，在調(diào)度過(guò)程中也考慮了安全開(kāi)銷(xiāo)的影響，但這兩類(lèi)算法不支持對(duì)分布式實(shí)時(shí)系統(tǒng)的動(dòng)態(tài)調(diào)度。

針對(duì)以上算法存在的不足，提出了一種安全驅(qū)動(dòng)實(shí)時(shí)調(diào)度算法SDSA（Security Driven Scheduling Algorithm），該算法能夠很好地適應(yīng)系統(tǒng)安全級(jí)別的動(dòng)態(tài)變化，并依照系統(tǒng)安全級(jí)別來(lái)動(dòng)態(tài)調(diào)整每個(gè)實(shí)時(shí)任務(wù)的安全策略，在不影響可調(diào)度性的前提下使其達(dá)到最優(yōu)的安全強(qiáng)度。仿真實(shí)驗(yàn)結(jié)果表明，SDSA算法在系統(tǒng)動(dòng)態(tài)安全需求的適應(yīng)性、關(guān)鍵任務(wù)的可調(diào)度性以及安全防危能力方面具有較好的表現(xiàn)。

2 安全驅(qū)動(dòng)調(diào)度模型

2.1 問(wèn)題描述及假設(shè)

本文的研究對(duì)象為多個(gè)處理機(jī)組成的分布式實(shí)時(shí)系統(tǒng)，各處理機(jī)通過(guò)高速網(wǎng)絡(luò)連接。系統(tǒng)上運(yùn)行著一組具有時(shí)限和安全約束的實(shí)時(shí)任務(wù)，每個(gè)任務(wù)的基本屬性已知，且到達(dá)時(shí)間隨機(jī)。實(shí)時(shí)任務(wù)按照時(shí)間關(guān)鍵程度不同分為關(guān)鍵任務(wù)和普通任務(wù)，其中關(guān)鍵任務(wù)必須在時(shí)限前完成，而普通任務(wù)如運(yùn)行違限可被放棄。這類(lèi)實(shí)時(shí)系統(tǒng)的調(diào)度問(wèn)題可以歸結(jié)為：如何調(diào)度每個(gè)新到達(dá)的實(shí)時(shí)任務(wù)到處理機(jī)上運(yùn)行，使得該任務(wù)的實(shí)時(shí)性和在當(dāng)前系統(tǒng)安全級(jí)別下的安全性約束得到滿(mǎn)足。

2.2 系統(tǒng)安全模型

系統(tǒng)安全模型如圖1所示，共分為三個(gè)部分：系統(tǒng)安全服務(wù)，系統(tǒng)安全級(jí)別和任務(wù)安全策略。

圖1 系統(tǒng)安全模型圖

系統(tǒng)安全級(jí)別定義了實(shí)時(shí)系統(tǒng)在不同階段的安全總需求，假設(shè)實(shí)時(shí)系統(tǒng)制訂了P種安全級(jí)別，用SL={sl1，sl2，…，slp}來(lái)表示，其中slj的值越大，表示系統(tǒng)安全級(jí)別越高。當(dāng)系統(tǒng)安全級(jí)別為slj時(shí)，系統(tǒng)將每種安全服務(wù)svk的服務(wù)實(shí)現(xiàn)集合SSk限制為一個(gè)子集SSk(slj)，進(jìn)入調(diào)度的實(shí)時(shí)任務(wù)只允許從SSk(slj)中挑選服務(wù)。由于實(shí)時(shí)任務(wù)的安全性主要是通過(guò)調(diào)用系統(tǒng)底層提供的安全服務(wù)來(lái)獲得的，因而通過(guò)調(diào)整系統(tǒng)安全級(jí)別來(lái)實(shí)現(xiàn)對(duì)實(shí)時(shí)任務(wù)調(diào)用安全服務(wù)實(shí)現(xiàn)的限制，從某種意義上可視為系統(tǒng)對(duì)實(shí)時(shí)應(yīng)用施加的一種安全約束。為了便于敘述，文中將所有服務(wù)實(shí)現(xiàn)集合SSk及SSk(slj)的元素按照安全強(qiáng)度遞增排序。

2.3 安全驅(qū)動(dòng)調(diào)度模型

安全驅(qū)動(dòng)調(diào)度模型包括三個(gè)部分：調(diào)度器，處理機(jī)和實(shí)時(shí)任務(wù)，下面將詳細(xì)進(jìn)行介紹。

2.3.1 處理機(jī)集群

假設(shè)分布式實(shí)時(shí)系統(tǒng)包含N個(gè)處理機(jī)，記為P={p1，p2，…}。每個(gè)處理機(jī)pi∈P可以用多元組(Γ(pj)，L(pj)，τ(pj))來(lái)表示，其中 Γ(pj)表示調(diào)度到 pj上運(yùn)行的任務(wù)集合。L(pj)表示 pj的調(diào)度長(zhǎng)度，即Γ(pj)中所有任務(wù)的剩余運(yùn)行時(shí)間之和，τ(pj)表示 pj上正在運(yùn)行的任務(wù)。

為了實(shí)現(xiàn)防危保護(hù)效果，關(guān)鍵任務(wù)和普通任務(wù)分別運(yùn)行在不同的處理機(jī)集合上，其中運(yùn)行關(guān)鍵任務(wù)的處理機(jī)集合稱(chēng)為關(guān)鍵集群（critical cluster），記為PCc，而運(yùn)行普通任務(wù)的處理機(jī)集合稱(chēng)為普通集群（normal cluster），記為PCn。為了便于敘述，所有空閑處理機(jī)組成的集合記為PCidle。本文假設(shè)系統(tǒng)提供的處理機(jī)數(shù)量足夠應(yīng)付在系統(tǒng)最大工作負(fù)載下所有關(guān)鍵任務(wù)的運(yùn)行。

2.3.2 實(shí)時(shí)任務(wù)

實(shí)時(shí)應(yīng)用表示為一組非周期的獨(dú)立實(shí)時(shí)任務(wù)集Γ={τ1，τ2，...}，對(duì)于任意實(shí)時(shí)任務(wù) τi∈?？捎枚嘣M(C(τi)，D(τi)，R(τi)，SO(τi)，B(τi)，P(τi))來(lái)表示，其中C(τi)表示任務(wù)τi的最大運(yùn)行時(shí)間，D(τi)表示任務(wù)τi的時(shí)限（deadline），R(τi)表示任務(wù)τi的最大響應(yīng)時(shí)間，即從該任務(wù)的到達(dá)直至運(yùn)行完成的時(shí)間間隔，B(τi)表示任務(wù)τi的被高優(yōu)先級(jí)任務(wù)搶占的時(shí)間，SO(τi)表示任務(wù)τi調(diào)用安全服務(wù)的時(shí)間開(kāi)銷(xiāo)，P(τi)表示任務(wù)τi運(yùn)行所在的處理機(jī)。

關(guān)鍵任務(wù)用τci來(lái)表示，而普通任務(wù)用τni來(lái)表示。本文如無(wú)特別說(shuō)明，τi可泛指任意類(lèi)型的實(shí)時(shí)任務(wù)。系統(tǒng)為每個(gè)實(shí)時(shí)任務(wù)τi制定唯一的優(yōu)先級(jí)，記為Φ(τi)，所有優(yōu)先級(jí)高于任務(wù)τi的任務(wù)集合記為hp(τi)={τj|Φ(τj)＞Φ(τi)，τj∈Γ}，所有關(guān)鍵任務(wù)的優(yōu)先級(jí)均高于普通任務(wù)，即?τci∈Γ，τnj∈Γ，Φ(τci)＞Φ(τnj)。

2.3.3 安全驅(qū)動(dòng)調(diào)度器

參照文獻(xiàn)[5-6，8]，本文設(shè)計(jì)了一種安全驅(qū)動(dòng)任務(wù)調(diào)度器，如圖2所示。

該調(diào)度器分為全局調(diào)度器和局部調(diào)度器兩個(gè)部分，其中全局調(diào)度負(fù)責(zé)檢查新到達(dá)實(shí)時(shí)任務(wù)在當(dāng)前系統(tǒng)安全級(jí)別約束下的可調(diào)度性，而系統(tǒng)安全級(jí)別可依照管理員命令進(jìn)行動(dòng)態(tài)調(diào)節(jié)。通過(guò)檢查的實(shí)時(shí)任務(wù)將依照關(guān)鍵程度被分配到對(duì)應(yīng)集群的處理機(jī)，這種做法可以很好地保護(hù)關(guān)鍵任務(wù)不受普通任務(wù)故障的影響，從而起到防危隔離的效果。局部調(diào)度器負(fù)責(zé)調(diào)度各個(gè)處理機(jī)上的實(shí)時(shí)任務(wù)，主要完成兩項(xiàng)工作：（1）動(dòng)態(tài)調(diào)整實(shí)時(shí)任務(wù)的安全策略，使其達(dá)到在任務(wù)可調(diào)度性和系統(tǒng)安全需求雙重約束下的最優(yōu)值；（2）按照優(yōu)先級(jí)搶占式策略調(diào)度任務(wù)開(kāi)始運(yùn)行。在處理機(jī)運(yùn)行過(guò)程中，局部調(diào)度器會(huì)將當(dāng)前任務(wù)狀態(tài)、處理機(jī)負(fù)載等信息反饋給全局調(diào)度器，作為其判定任務(wù)可調(diào)度性的依據(jù)。

3 安全驅(qū)動(dòng)實(shí)時(shí)調(diào)度算法SDSA

基于上述模型，本文提出一個(gè)SDSA算法，本章首先介紹算法的相關(guān)概念，然后給出詳細(xì)的算法設(shè)計(jì)步驟。

3.1 相關(guān)概念

為了更好地描述算法內(nèi)容，這里先給出相關(guān)定義與性質(zhì)。

定義1在處理機(jī) pj上運(yùn)行著任務(wù)集Γ(pj)，對(duì)于任意實(shí)時(shí)任務(wù)τi∈Γ(pj)，如果其運(yùn)行所產(chǎn)生的響應(yīng)時(shí)間Ri不大于其時(shí)限D(zhuǎn)i，則稱(chēng)該任務(wù)在處理機(jī) pj可被調(diào)度。如果任務(wù)集Γ(pj)的所有任務(wù)都可被調(diào)度，則稱(chēng)該任務(wù)集在處理機(jī)pj可被調(diào)度。

定義2對(duì)于實(shí)時(shí)任務(wù)τi，當(dāng)系統(tǒng)安全級(jí)別為slj時(shí)，采用安全策略SP(τi，slj)所產(chǎn)生的安全開(kāi)銷(xiāo)SO(τi)和所達(dá)到的安全強(qiáng)度QoS(τi，slj)可通過(guò)公式（1）和（2）來(lái)計(jì)算。

定義3在任務(wù)集Γ中，實(shí)時(shí)任務(wù)τi的最大響應(yīng)時(shí)間可通過(guò)公式（3）來(lái)計(jì)算。

其中L(τi)表示任務(wù)τi的剩余運(yùn)行時(shí)間，Cused(τi)表示任務(wù)τi實(shí)際運(yùn)行的時(shí)間，B(τi)表示任務(wù)τi被高優(yōu)先級(jí)任務(wù)集合hp(τi，Γ)阻塞的時(shí)間，S(τi)表示任務(wù)τi從到達(dá)時(shí)刻si起至當(dāng)前時(shí)刻tnow的時(shí)間間隔。

圖2 安全驅(qū)動(dòng)調(diào)度器

性質(zhì)1任意實(shí)時(shí)任務(wù)τi加入到任務(wù)集Γ后，如果公式（7）得到滿(mǎn)足，則稱(chēng)該任務(wù)在任務(wù)集中可被調(diào)度。

其中l(wèi)p(τi，Γ)表示優(yōu)先級(jí)低于任務(wù)τi的任務(wù)集合。

3.2 算法設(shè)計(jì)

SDSA算法分為三個(gè)部分：AC&GA（Admission Checking&Global Assigning）算法，SPA（Security Policy Adjusting）和LPS（Local Preemptive Scheduling）算法，下面分別具體介紹。

3.2.1 ACGA算法

AC&GA算法主要用于在全局角度調(diào)度新到達(dá)的實(shí)時(shí)任務(wù)，調(diào)度主要完成以下工作：首先檢查到達(dá)隊(duì)列中的每個(gè)實(shí)時(shí)任務(wù)在當(dāng)前系統(tǒng)負(fù)載下的可調(diào)度性，被檢查任務(wù)被設(shè)置為當(dāng)前安全級(jí)別所允許的最低安全策略（即服務(wù)實(shí)現(xiàn)界的第一個(gè)元素）。然后將通過(guò)檢查的任務(wù)分配到最合適的處理機(jī)上運(yùn)行。針對(duì)不同類(lèi)型的實(shí)時(shí)任務(wù)，算法采用不同的處理策略：對(duì)于關(guān)鍵任務(wù)，如果在關(guān)鍵集群中尋找到可調(diào)度的處理機(jī)，則將其分配到該處理機(jī)上運(yùn)行，否則為其分配一個(gè)新處理機(jī)，并將該處理機(jī)加入到關(guān)鍵集群。對(duì)于普通任務(wù)，將其分配給普通集群中可調(diào)度的處理機(jī)，否則將其丟棄。算法的基本步驟如下所示。

3.2.2 SPA算法

SPA算法的核心思想是為每個(gè)新分配到處理機(jī)的實(shí)時(shí)任務(wù)設(shè)置最優(yōu)的安全策略，其遵循以下原則：在確保實(shí)時(shí)任務(wù)可被調(diào)度以及當(dāng)前系統(tǒng)安全級(jí)別允許的前提下，為新分配的實(shí)時(shí)任務(wù)選擇最大安全強(qiáng)度的安全服務(wù)。該算法的基本步驟如下所示。

3.2.3 LPS算法

LPS算法的核心思想是按照固定優(yōu)先級(jí)搶占式策略調(diào)度單個(gè)處理機(jī)上的實(shí)時(shí)任務(wù)，其基本步驟如下所示。

4 仿真實(shí)驗(yàn)

本文通過(guò)一組仿真實(shí)驗(yàn)來(lái)評(píng)估SDSA算法的性能。為了便于比較，選取文獻(xiàn)[5]的SAEDF算法和文獻(xiàn)[6]的TPSS算法作為實(shí)驗(yàn)的參照算法。

實(shí)驗(yàn)主要采用三個(gè)性能評(píng)價(jià)指標(biāo)：（1）關(guān)鍵任務(wù)可調(diào)度率CTGR（Crtical Tasks Guarantee Ratio），即可調(diào)度關(guān)鍵任務(wù)在全部關(guān)鍵任務(wù)中的所占比例；（2）普通任務(wù)可調(diào)度率NTGR（Normal Tasks Guarantee Ratio），即可調(diào)度普通任務(wù)在全部普通任務(wù)中的所占比例；（3）系統(tǒng)整體安全性能GSP(slj)（Global Security Performance），即系統(tǒng)在安全級(jí)別slj下所能達(dá)到的總體安全性能，其定義如公式（8）所示。

其中CTGR和NTGR的值越大表示調(diào)度策略越成功，而GSP(slj)的值越大表示系統(tǒng)所獲得的安全性越強(qiáng)。

仿真實(shí)驗(yàn)代碼采用C++語(yǔ)言編寫(xiě)，參與實(shí)驗(yàn)的實(shí)時(shí)任務(wù)數(shù)量為200個(gè)，其到達(dá)時(shí)間及時(shí)限通過(guò)隨機(jī)方式產(chǎn)生。任務(wù)負(fù)載率表示任務(wù)運(yùn)行時(shí)間與其時(shí)限的比值，在區(qū)間[0.2，0.8]內(nèi)取值，各任務(wù)運(yùn)行時(shí)間通過(guò)時(shí)限與任務(wù)負(fù)載率的乘積得出。任務(wù)的優(yōu)先級(jí)基于短周期優(yōu)先策略來(lái)指定。參照文獻(xiàn)[5]，假設(shè)系統(tǒng)提供3種安全服務(wù)類(lèi)型，每種服務(wù)類(lèi)型有共6種具體實(shí)現(xiàn)。實(shí)驗(yàn)將系統(tǒng)安全級(jí)別設(shè)置為4級(jí)，每級(jí)共包含2個(gè)服務(wù)實(shí)現(xiàn)。所有實(shí)驗(yàn)過(guò)程重復(fù)進(jìn)行10次，最終實(shí)驗(yàn)結(jié)果取其平均值。

圖3（a）和圖3（b）表示系統(tǒng)安全級(jí)別SL對(duì)兩種任務(wù)可調(diào)度性CTGR和NTGR的影響。當(dāng)SL從（最低級(jí)）1提升到（最高級(jí)）4時(shí)，采用TPSS算法和SAEDF算法的兩種任務(wù)的可調(diào)度率無(wú)明顯變化，而采用SDSA算法的兩種任務(wù)的可調(diào)度率變化較大，這是因?yàn)門(mén)PSS和SDEDF沒(méi)有考慮SL對(duì)調(diào)度的影響，其任務(wù)選擇的安全策略始終固定不變，這違反了當(dāng)前系統(tǒng)安全級(jí)別對(duì)任務(wù)的安全約束，因而調(diào)度結(jié)果是無(wú)效的。而SDSA對(duì)SL的變化具有很好的適應(yīng)性，當(dāng)SL增加時(shí)，新到達(dá)任務(wù)采用更高級(jí)別的安全策略，導(dǎo)致其安全開(kāi)銷(xiāo)增加。對(duì)于普通任務(wù)，其對(duì)應(yīng)的處理機(jī)集群無(wú)法承擔(dān)更高負(fù)載，從而降低了該類(lèi)任務(wù)的可調(diào)度率。而對(duì)于關(guān)鍵任務(wù)，SDSA通過(guò)增加硬件開(kāi)銷(xiāo)來(lái)維持其100%的可調(diào)度性。因此，SDSA算法在系統(tǒng)安全級(jí)別的動(dòng)態(tài)適應(yīng)性以及關(guān)鍵任務(wù)的可調(diào)度性方面優(yōu)于其他兩種算法。

圖3 仿真實(shí)驗(yàn)結(jié)果1

圖4（a）表示普通任務(wù)故障率NTFR對(duì)關(guān)鍵任務(wù)可調(diào)度性CTGR的影響，實(shí)驗(yàn)中系統(tǒng)安全級(jí)別設(shè)置為1，關(guān)鍵任務(wù)在所有任務(wù)中占比設(shè)置為20%。任務(wù)故障通過(guò)軟件模擬實(shí)現(xiàn)，假設(shè)系統(tǒng)處理任務(wù)故障的時(shí)間開(kāi)銷(xiāo)為該任務(wù)運(yùn)行時(shí)間的兩倍。從圖中結(jié)果得知，當(dāng)普通任務(wù)的故障率FR （Fault Ratio）從10%增加到80%時(shí)，TPSS和SAEDF的關(guān)鍵任務(wù)可調(diào)度率急劇降低，而SDSA算法始終維持在100%，這是因?yàn)榍皟煞N算法沒(méi)有采取防危性措施，導(dǎo)致普通任務(wù)的故障影響到關(guān)鍵任務(wù)的正常運(yùn)行，而SDSA采用處理機(jī)集群隔離方式，能夠很好地防止普通任務(wù)故障對(duì)關(guān)鍵任務(wù)的影響。因此，SDSA算法在安全防危能力上優(yōu)于其他兩種算法。

圖4（b）表示系統(tǒng)安全級(jí)別SL和任務(wù)負(fù)載率U對(duì)系統(tǒng)整體安全性能GSP的影響。當(dāng)任務(wù)負(fù)載率固定時(shí)，提升系統(tǒng)的安全級(jí)別會(huì)使得GSP提升明顯，這是因?yàn)楦呦到y(tǒng)安全級(jí)別提高了對(duì)任務(wù)的安全需求，迫使每個(gè)任務(wù)采用更高強(qiáng)度的安全策略。而當(dāng)系統(tǒng)安全級(jí)別固定時(shí)，任務(wù)的負(fù)載率越低，任務(wù)就可以利用更多的空閑時(shí)間來(lái)調(diào)用更高安全強(qiáng)度的安全策略。因此，提升系統(tǒng)安全級(jí)別和降低任務(wù)負(fù)載率將會(huì)顯著提升系統(tǒng)的整體安全性能。

圖4 仿真實(shí)驗(yàn)結(jié)果2

5 結(jié)語(yǔ)

實(shí)時(shí)系統(tǒng)安全級(jí)別的動(dòng)態(tài)調(diào)整會(huì)改變其上運(yùn)行實(shí)時(shí)應(yīng)用的安全需求，從而產(chǎn)生動(dòng)態(tài)變化的安全開(kāi)銷(xiāo)，給實(shí)時(shí)調(diào)度造成了困難。針對(duì)這個(gè)問(wèn)題，本文的主要貢獻(xiàn)有：（1）構(gòu)建了一種基于安全驅(qū)動(dòng)的實(shí)時(shí)任務(wù)調(diào)度模型；（2）基于上述模型，提出了一種安全驅(qū)動(dòng)調(diào)度算法SDSA；（3）將SDSA算法與兩類(lèi)參照算法在不同條件環(huán)境下進(jìn)行仿真實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果分別反映出SDSA算法在系統(tǒng)動(dòng)態(tài)安全需求的適應(yīng)性、關(guān)鍵任務(wù)的可調(diào)度性以及安全防危能力等方面的優(yōu)勢(shì)。下一步工作包括：在調(diào)度算法中考慮對(duì)非獨(dú)立任務(wù)的調(diào)度，以及研究更精確的安全開(kāi)銷(xiāo)分析。

[1]Vallee G，Morin C，Berthou J Y，et al.A new approach to configurable dynamic scheduling in clusters based on single system image technologies[C]//Proceedings of Parallel and Distributed Processing Symposium.Washington，DC，USA：IEEE Computer Society，2003：91-100.

[2]Zhang Yanyong，Sivasubramaniam A，Moreira J，et al.Impact of workload and system parameters on next generation cluster scheduling mechanisms[J].IEEE Transactions on Parallel and Distributed Systems，2001，12（9）：967-985.

[3]BertgnaM，CirineiM，LipariG.Improved schedulability analysis of EDF on multiprocessor platforms[C]//Proceedings of the 17th Euromicro Conference on Real-Time Systems. Washington，DC，USA：IEEE Computer Society，2005：209-218.

[4]Baruah S.Techniques for multiprocessor global schedulability analysis[C]//Proceedings of Real-Time Systems Symposium. Washington，DC，USA：IEEE ComputerSociety，2007： 119-128.

[5]Xie Tao，Qin Xiao.Scheduling security-critical real-time applications on clusters[J].IEEE Transactions on Computers，2006，55（7）：864-879.

[6]朱曉敏，陸佩忠.異構(gòu)集群系統(tǒng)中安全關(guān)鍵實(shí)時(shí)應(yīng)用調(diào)度研究[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（12）：2364-2377.

[7]夏平，周興社，駱萬(wàn)文，等.面向分布式實(shí)時(shí)系統(tǒng)的新型可信任務(wù)調(diào)度算法[J].西北工業(yè)大學(xué)學(xué)報(bào)，2011，29（2）：155-159.

[8]Xia Ping，Zhou Xingshe.Security-driven fault tolerant scheduling algorithm for high dependable distributed real-time system[C]//Proceedings of the 2011 4th International Symposium on Parallel Architectures，Algorithms and Programming. Washington，DC，USA：IEEE Computer Society，2011：29-33.

XIA Ping,ZHOU Xingshe

School of Computer Science,Northwestern Polytechnical University,Xi'an 710072,China

The paper solves the problem that current scheduling algorithms cannot meet the dynamic security requirement of realtime system.It builds a new security-driven scheduling model which describes the common security requirement of standard real-time system from three aspects including system security level,system security service and task security policy,and designs new security-driven scheduler framework.Based on the model the paper proposes a new Security-Driven Scheduling Algorithm （SDSA）for distributed real-time system.The algorithm checks the new arrived task and treats it by its critical type,then assigns it to the schedulable processor.It adjusts the security policy of tasks assigned on the same processor to the optimal balance between security and schedulability under current system security level.It adopts the priority preemptive policy to schedule these tasks on the same processor.Empirical investigations show that the improvements in the adaptability to dynamic security level and the schedulability of critical task and the safegurad effects can be achieved by choosing SDSA than other similar algorithms.

distributed;real-time;security;scheduling

針對(duì)現(xiàn)有實(shí)時(shí)調(diào)度算法無(wú)法適應(yīng)動(dòng)態(tài)安全需求的問(wèn)題，構(gòu)建了一種安全驅(qū)動(dòng)調(diào)度模型，該模型從系統(tǒng)安全級(jí)別、系統(tǒng)安全服務(wù)和任務(wù)安全策略三個(gè)方面描述了實(shí)時(shí)系統(tǒng)的動(dòng)態(tài)安全需求，并設(shè)計(jì)了一種基于安全驅(qū)動(dòng)的實(shí)時(shí)任務(wù)調(diào)度器框架。以該模型和框架為基礎(chǔ)，提出了一種安全驅(qū)動(dòng)調(diào)度算法（Security Driven Scheduling Algorithm，SDSA）。從全局角度對(duì)新到達(dá)任務(wù)進(jìn)行可調(diào)度性檢查，并將可調(diào)度任務(wù)分配到合適的處理機(jī)上運(yùn)行。按照系統(tǒng)安全級(jí)別來(lái)動(dòng)態(tài)調(diào)整已分配到各處理機(jī)上實(shí)時(shí)任務(wù)的安全策略，使其達(dá)到安全性和可調(diào)度性的最優(yōu)平衡。采用優(yōu)先級(jí)搶占式策略對(duì)各實(shí)時(shí)任務(wù)進(jìn)行調(diào)度。仿真結(jié)果表明，SDSA算法與其他同類(lèi)算法相比，在系統(tǒng)動(dòng)態(tài)安全需求的適應(yīng)性、關(guān)鍵任務(wù)的可調(diào)度性以及安全防危能力等方面具有較好的表現(xiàn)。

分布式；實(shí)時(shí)；安全；調(diào)度

A

TP301

10.3778/j.issn.1002-8331.1205-0036

XIA Ping,ZHOU Xingshe.Security-driven scheduling algorithm for distributed real-time system.Computer Engineering and Applications,2013,49（5）：8-12.

國(guó)家自然科學(xué)基金（No.60736017）。

夏平（1982—），男，博士研究生，工程師，CCF學(xué)生會(huì)員，主要研究方向?yàn)楦咝阅苡?jì)算、實(shí)時(shí)計(jì)算；周興社（1955—），男，博士生導(dǎo)師，教授，CCF高級(jí)會(huì)員，主要研究方向?yàn)楦咝阅苡?jì)算、嵌入式計(jì)算、普適計(jì)算。E-mail：sharkping@gmail.com

2012-05-14

2012-08-23

1002-8331（2013）05-0008-05

CNKI出版日期：2012-11-06 http://www.cnki.net/kcms/detail/11.2127.TP.20121106.1607.004.html