夏 平，周兴社

西北工业大学 计算机学院，西安 710072

面向分布式实时系统的安全驱动调度算法研究

夏 平，周兴社

西北工业大学 计算机学院，西安 710072

1 引言

随着计算机技术和网络技术的不断发展，实时系统被广泛应用于航空、航天、国防等重要领域。这些领域对实时系统上运行的关键应用提出了极高的安全性要求。为此这些领域所部署的实时系统在底层提供了不同类型的安全服务，每种服务封装并实现了特定的安全功能，在高层运行的实时应用通过调用这些安全服务，使得自身的安全需求得以满足。但运行安全服务增加了实时应用的时间开销，从而对实时系统的可调度性造成了不可忽视的影响。此外，用户可能会依据自身需求动态调整系统的整体安全级别，造成安全开销分析的不确定性，增加了实时调度的难度。因此有必要研究一种新型实时调度算法，使其在适应系统动态安全需求的前提下，对实时应用进行合理的调度，以确保实时应用的实时性和安全性需求得到满足。

目前关于实时调度问题的研究已经十分成熟，这方面已经取得了很多研究成果。文献[1-4]提出了多种适用于分布式系统的实时调度算法，这些算法虽然能够提高系统调度的效率，但是没有考虑实时应用的安全性需求，因而不适用于调度安全关键实时应用。文献[5]提出了一种安全感知实时调度算法SAEDF（Security Assurance EarlyDeadline First），该算法在调度过程中考虑了实时任务的安全开销，并利用任务的松弛时间来提升其安全级别，从而实现系统整体安全性能提升。文献[6]提出了一种面向异构集群系统的双阶段调度策略TPSS（Two Phase Scheduling Strategy），该策略依据系统当前负载来调整任务安全级别，并保证系统获得较高的调度成功率。但是SAEDF和TPSS均未考虑实时系统对实时应用的动态安全约束，且不支持调度软硬混合的实时任务。文献[7-8]提出了两种面向分布式实时系统的启发式调度算法，在调度过程中也考虑了安全开销的影响，但这两类算法不支持对分布式实时系统的动态调度。

针对以上算法存在的不足，提出了一种安全驱动实时调度算法SDSA（Security Driven Scheduling Algorithm），该算法能够很好地适应系统安全级别的动态变化，并依照系统安全级别来动态调整每个实时任务的安全策略，在不影响可调度性的前提下使其达到最优的安全强度。仿真实验结果表明，SDSA算法在系统动态安全需求的适应性、关键任务的可调度性以及安全防危能力方面具有较好的表现。

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∈Γ可用多元组(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的被高优先级任务抢占的时间，SO(τi)表示任务τi调用安全服务的时间开销，P(τi)表示任务τi运行所在的处理机。

关键任务用τci来表示，而普通任务用τni来表示。本文如无特别说明，τi可泛指任意类型的实时任务。系统为每个实时任务τi制定唯一的优先级，记为Φ(τi)，所有优先级高于任务τi的任务集合记为hp(τi)={τj|Φ(τj)＞Φ(τi)，τj∈Γ}，所有关键任务的优先级均高于普通任务，即∀τci∈Γ，τnj∈Γ，Φ(τci)＞Φ(τnj)。

2.3.3 安全驱动调度器

参照文献[5-6，8]，本文设计了一种安全驱动任务调度器，如图2所示。

该调度器分为全局调度器和局部调度器两个部分，其中全局调度负责检查新到达实时任务在当前系统安全级别约束下的可调度性，而系统安全级别可依照管理员命令进行动态调节。通过检查的实时任务将依照关键程度被分配到对应集群的处理机，这种做法可以很好地保护关键任务不受普通任务故障的影响，从而起到防危隔离的效果。局部调度器负责调度各个处理机上的实时任务，主要完成两项工作：（1）动态调整实时任务的安全策略，使其达到在任务可调度性和系统安全需求双重约束下的最优值；（2）按照优先级抢占式策略调度任务开始运行。在处理机运行过程中，局部调度器会将当前任务状态、处理机负载等信息反馈给全局调度器，作为其判定任务可调度性的依据。

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被高优先级任务集合hp(τi，Γ)阻塞的时间，S(τi)表示任务τi从到达时刻si起至当前时刻tnow的时间间隔。

图2 安全驱动调度器

性质1任意实时任务τi加入到任务集Γ后，如果公式（7）得到满足，则称该任务在任务集中可被调度。

其中lp(τi，Γ)表示优先级低于任务τ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算法的核心思想是为每个新分配到处理机的实时任务设置最优的安全策略，其遵循以下原则：在确保实时任务可被调度以及当前系统安全级别允许的前提下，为新分配的实时任务选择最大安全强度的安全服务。该算法的基本步骤如下所示。

3.2.3 LPS算法

LPS算法的核心思想是按照固定优先级抢占式策略调度单个处理机上的实时任务，其基本步骤如下所示。

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个，其到达时间及时限通过随机方式产生。任务负载率表示任务运行时间与其时限的比值，在区间[0.2，0.8]内取值，各任务运行时间通过时限与任务负载率的乘积得出。任务的优先级基于短周期优先策略来指定。参照文献[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算法在系统安全级别的动态适应性以及关键任务的可调度性方面优于其他两种算法。

图3 仿真实验结果1

图4（a）表示普通任务故障率NTFR对关键任务可调度性CTGR的影响，实验中系统安全级别设置为1，关键任务在所有任务中占比设置为20%。任务故障通过软件模拟实现，假设系统处理任务故障的时间开销为该任务运行时间的两倍。从图中结果得知，当普通任务的故障率FR （Fault Ratio）从10%增加到80%时，TPSS和SAEDF的关键任务可调度率急剧降低，而SDSA算法始终维持在100%，这是因为前两种算法没有采取防危性措施，导致普通任务的故障影响到关键任务的正常运行，而SDSA采用处理机集群隔离方式，能够很好地防止普通任务故障对关键任务的影响。因此，SDSA算法在安全防危能力上优于其他两种算法。

图4（b）表示系统安全级别SL和任务负载率U对系统整体安全性能GSP的影响。当任务负载率固定时，提升系统的安全级别会使得GSP提升明显，这是因为高系统安全级别提高了对任务的安全需求，迫使每个任务采用更高强度的安全策略。而当系统安全级别固定时，任务的负载率越低，任务就可以利用更多的空闲时间来调用更高安全强度的安全策略。因此，提升系统安全级别和降低任务负载率将会显著提升系统的整体安全性能。

图4 仿真实验结果2

5 结语

实时系统安全级别的动态调整会改变其上运行实时应用的安全需求，从而产生动态变化的安全开销，给实时调度造成了困难。针对这个问题，本文的主要贡献有：（1）构建了一种基于安全驱动的实时任务调度模型；（2）基于上述模型，提出了一种安全驱动调度算法SDSA；（3）将SDSA算法与两类参照算法在不同条件环境下进行仿真实验对比，实验结果分别反映出SDSA算法在系统动态安全需求的适应性、关键任务的可调度性以及安全防危能力等方面的优势。下一步工作包括：在调度算法中考虑对非独立任务的调度，以及研究更精确的安全开销分析。

[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].西北工业大学学报，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

针对现有实时调度算法无法适应动态安全需求的问题，构建了一种安全驱动调度模型，该模型从系统安全级别、系统安全服务和任务安全策略三个方面描述了实时系统的动态安全需求，并设计了一种基于安全驱动的实时任务调度器框架。以该模型和框架为基础，提出了一种安全驱动调度算法（Security Driven Scheduling Algorithm，SDSA）。从全局角度对新到达任务进行可调度性检查，并将可调度任务分配到合适的处理机上运行。按照系统安全级别来动态调整已分配到各处理机上实时任务的安全策略，使其达到安全性和可调度性的最优平衡。采用优先级抢占式策略对各实时任务进行调度。仿真结果表明，SDSA算法与其他同类算法相比，在系统动态安全需求的适应性、关键任务的可调度性以及安全防危能力等方面具有较好的表现。

分布式；实时；安全；调度

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