夏 平，周興社

西北工業(yè)大學 計算機學院，西安 710072

面向分布式實時系統的安全驅動調度算法研究

夏 平，周興社

西北工業(yè)大學 計算機學院，西安 710072

1 引言

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

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

針對以上算法存在的不足，提出了一種安全驅動實時調度算法SDSA（Security Driven Scheduling Algorithm），該算法能夠很好地適應系統安全級別的動態(tài)變化，并依照系統安全級別來動態(tài)調整每個實時任務的安全策略，在不影響可調度性的前提下使其達到最優(yōu)的安全強度。仿真實驗結果表明，SDSA算法在系統動態(tài)安全需求的適應性、關鍵任務的可調度性以及安全防危能力方面具有較好的表現。

2 安全驅動調度模型

2.1 問題描述及假設

本文的研究對象為多個處理機組成的分布式實時系統，各處理機通過高速網絡連接。系統上運行著一組具有時限和安全約束的實時任務，每個任務的基本屬性已知，且到達時間隨機。實時任務按照時間關鍵程度不同分為關鍵任務和普通任務，其中關鍵任務必須在時限前完成，而普通任務如運行違限可被放棄。這類實時系統的調度問題可以歸結為：如何調度每個新到達的實時任務到處理機上運行，使得該任務的實時性和在當前系統安全級別下的安全性約束得到滿足。

2.2 系統安全模型

系統安全模型如圖1所示，共分為三個部分：系統安全服務，系統安全級別和任務安全策略。

圖1 系統安全模型圖

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

2.3 安全驅動調度模型

安全驅動調度模型包括三個部分：調度器，處理機和實時任務，下面將詳細進行介紹。

2.3.1 處理機集群

假設分布式實時系統包含N個處理機，記為P={p1，p2，…}。每個處理機pi∈P可以用多元組(Γ(pj)，L(pj)，τ(pj))來表示，其中 Γ(pj)表示調度到 pj上運行的任務集合。L(pj)表示 pj的調度長度，即Γ(pj)中所有任務的剩余運行時間之和，τ(pj)表示 pj上正在運行的任務。

為了實現防危保護效果，關鍵任務和普通任務分別運行在不同的處理機集合上，其中運行關鍵任務的處理機集合稱為關鍵集群（critical cluster），記為PCc，而運行普通任務的處理機集合稱為普通集群（normal cluster），記為PCn。為了便于敘述，所有空閑處理機組成的集合記為PCidle。本文假設系統提供的處理機數量足夠應付在系統最大工作負載下所有關鍵任務的運行。

2.3.2 實時任務

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

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

2.3.3 安全驅動調度器

參照文獻[5-6，8]，本文設計了一種安全驅動任務調度器，如圖2所示。

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

3 安全驅動實時調度算法SDSA

基于上述模型，本文提出一個SDSA算法，本章首先介紹算法的相關概念，然后給出詳細的算法設計步驟。

3.1 相關概念

為了更好地描述算法內容，這里先給出相關定義與性質。

定義1在處理機 pj上運行著任務集Γ(pj)，對于任意實時任務τi∈Γ(pj)，如果其運行所產生的響應時間Ri不大于其時限Di，則稱該任務在處理機 pj可被調度。如果任務集Γ(pj)的所有任務都可被調度，則稱該任務集在處理機pj可被調度。

定義2對于實時任務τi，當系統安全級別為slj時，采用安全策略SP(τi，slj)所產生的安全開銷SO(τi)和所達到的安全強度QoS(τi，slj)可通過公式（1）和（2）來計算。

定義3在任務集Γ中，實時任務τi的最大響應時間可通過公式（3）來計算。

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

圖2 安全驅動調度器

性質1任意實時任務τi加入到任務集Γ后，如果公式（7）得到滿足，則稱該任務在任務集中可被調度。

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

3.2 算法設計

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

3.2.1 ACGA算法

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

3.2.2 SPA算法

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

3.2.3 LPS算法

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

4 仿真實驗

本文通過一組仿真實驗來評估SDSA算法的性能。為了便于比較，選取文獻[5]的SAEDF算法和文獻[6]的TPSS算法作為實驗的參照算法。

實驗主要采用三個性能評價指標：（1）關鍵任務可調度率CTGR（Crtical Tasks Guarantee Ratio），即可調度關鍵任務在全部關鍵任務中的所占比例；（2）普通任務可調度率NTGR（Normal Tasks Guarantee Ratio），即可調度普通任務在全部普通任務中的所占比例；（3）系統整體安全性能GSP(slj)（Global Security Performance），即系統在安全級別slj下所能達到的總體安全性能，其定義如公式（8）所示。

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

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

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

圖3 仿真實驗結果1

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

圖4（b）表示系統安全級別SL和任務負載率U對系統整體安全性能GSP的影響。當任務負載率固定時，提升系統的安全級別會使得GSP提升明顯，這是因為高系統安全級別提高了對任務的安全需求，迫使每個任務采用更高強度的安全策略。而當系統安全級別固定時，任務的負載率越低，任務就可以利用更多的空閑時間來調用更高安全強度的安全策略。因此，提升系統安全級別和降低任務負載率將會顯著提升系統的整體安全性能。

圖4 仿真實驗結果2

5 結語

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

[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]朱曉敏，陸佩忠.異構集群系統中安全關鍵實時應用調度研究[J].計算機學報，2010，33（12）：2364-2377.

[7]夏平，周興社，駱萬文，等.面向分布式實時系統的新型可信任務調度算法[J].西北工業(yè)大學學報，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

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

分布式；實時；安全；調度

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.

國家自然科學基金（No.60736017）。

夏平（1982—），男，博士研究生，工程師，CCF學生會員，主要研究方向為高性能計算、實時計算；周興社（1955—），男，博士生導師，教授，CCF高級會員，主要研究方向為高性能計算、嵌入式計算、普適計算。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