云环境下两阶段安全驱动的容错调度算法

白晶晶，田生伟，禹 龙，于 炯，田国忠

（1.新疆大学 信息科学与程工学院，新疆 乌鲁木齐830046；2.新疆大学 软件学院，新疆 乌鲁木齐830008；3.新疆大学 网络中心，新疆 乌鲁木齐830046；4.新疆工程学院 计算机工程系，新疆 乌鲁木齐830000）

0 引 言

云计算具有动态性、开放性和共享性等特点，这使云环境下的任务调度面临新的安全挑战［1］。在任务调度过程中，云供应商除了满足用户基本的时间和费用需求外，还应保障用户数据和隐私不被泄露、窃取和篡改［2］；此外，云资源往往表现出一定的失效性和波动性［3］，因此可靠性成为任务调度的另一重要需求。针对安全可靠性调度，许多研究者提出了新的安全技术架构和调度策略［2－4］。蒋从峰等通过改进备份策略和调度算法，提高了任务调度成功率。但实际的云计算是处在异构环境下，其任务之间具有依赖关系，这些算法仅适用于相互独立的任务调度，存在一定的局限性［5，6］。

为了解决该问题，不少学者以具有依赖关系的任务为基础，将安全驱动模型与任务调度相结合，优化了调度长度和安全满意度，但忽略了用户的可靠性需求，未能实现容错调度［7，8］；Qin Xiao等通过改进通信模型或主／副本策略，实现了容错调度，并缩短了调度长度，但这些方法主要针对任务调度的可靠性，未对处理机进行安全筛选，且同一时刻仅支持一个处理机失效，使容错存在一定的局限性［9－12］。

针对已有算法的局限性，本文以现有工作为基础，提出了云环境下综合考虑安全性和可靠性的调度算法。改进了备份方式，并使用队列策略扩大了容错范围，支持多处理机同时失效，使算法更具有应用性。优化了任务调度的安全性和可靠性。

1 容错调度模型

云环境下的异构系统具有较高的复杂性，且任务调度是一个NP问题，为了集中讨论所关心的中心问题，我们设定以下前提约束［13］：首先，系统中任意处理机均可能失效，失效可在任意时间点发生；其次，每个任务在执行期间仅遇到一次处理机失效。

1.1 任务模型

云计算是异构分布式系统的体现，任务之间具有依赖关系。一般选择有向无环图DAG （directed acyclic graph）对并行任务进行描述。

定义1 用一个二元组G＝ （V，E）表示DAG，其中V＝ ｛v1，v2，…，vN｝表示任务的集合，N 表示任务总数；E＝ ｛eij｜eij＝＜vi，vj＞，vi，vj∈V｝为有向边的集合，eij表示vi和vj间具有依赖关系，vj为vi的后继，vj只有在vi完成后才能执行；w（vi）表示vi的计算开销，w（eij）表示vi和vj间的通信开销，如果vi和vj在同一个处理机上，w（eij）的值为0。图1 为任务DAG 的一个实例。

图1 任务

定义2 异构系统中包含一组处理机，这些处理机通过网络连接在一起，网络具有全连通性［7］。P＝ ｛p1，p2，…，pM｝表示处理机的集合，M 为处理机的总数；wij表示任意2个处理机pi和pj之间的通信开销。图2为处理机的一个实例。

图2 处理机

1.2 安全模型

为了提高调度的安全性，模型中每个任务提供一个安全需求 （security demand，SD），每个处理机有一个信任等级 （trust level，TL）。处理机可以提供的安全服务共3种，分别为真实性、完整性和保密性［11］。

为了更具体地分析资源的安全水平，评估任务调度的风险性，我们对任务调度的风险率做出以下量化处理

2 调度算法

2.1 任务分配预备阶段

2.1.1 任务调度优先级

本文在经典算法HEFT （heterogeneous earliest－finishtime）［7］的基础上，考虑各种安全措施带来的时间开销，计算出任务的优先级［7］。SRank＝ ｛SRank（vi）｜vi∈V｝，SRank（vi）表示任务vi的优先级，根据优先级大小对任务进行排序，得到任务的调度序列，用SL （scheduling list）表示

在式 （3）和式 （4）中，vexit表示出口任务；w（eix）表示边eix的通信开销，w（vi）表示vi的计算开销；succ（vi）是vi后继的集合，SRank（vI，pj）表示vi在pj上的优先级；uj表示pj的执行速度，Cij表示vi在pj上的安全开销。从出口任务开始，递归计算出每个任务的优先级。

2.1.2 处理机筛选及备份预处理

在1.2小节可得出任务在处理机上的调度风险率Pr（vi，pj）（vI∈V，pj∈P），为了对处理机进行定量筛选，我们设定了风险率阈值，用γ表示。选择满足条件Pr（vi，pj）＜γ的处理机作为vi的候选处理机。SP（vi）＝ ｛pj｜vi∈V，Pr（vi，pj）＜γ｝表示符合条件的处理机集合。若｜SP（vi）｜＝0，则用户降低安全需求等级，使｜SP（vi）｜＞0；当｜SP（vi）｜＞4时，选取Pr（vi，pj）值最大的4 个处理机，最终的候选处理机集合用SP’（vi）表示。

采用自适应备份方式，确定任务备份数目，为正式调度做准备。每个任务有一个主本和若干个副本，replica（vi）表示任务vi的副本数。如式 （5）所示，根据处理机的筛选结果确定replica（vi）的值，为了使备份数在一个合理的范围内，replica （vi）的上限为3［5］

2.2 任务调度阶段

2.2.1 队列策略

在任务正式调度阶段，由于已对处理机进行了筛选，只需计算任务在候选处理机上的est和eft，从而减少计算开销，降低了冗余度。EST（vi）＝ ｛est（vi，pj）｜pj∈SP’（vi），vi∈V｝，EFT（vi）＝ ｛eft（vi，pj）｜pj∈SP’（vi），vi∈V｝，其中est（vi，pj）和eft（vi，pj）分别表示任务vi在pj上的最早开始时间和最早完成时间，pj是vi的候选处理机。将EFT（vi）中的元素按其值的大小非降序排列，得到序列EFT（vi）asce和对应的处理机序列SP’（vi）asce。

在上一阶段已得到任务备份的数量，本阶段将以此为基础，对任务的主／副本进行正式分配。参考田冠华等［3］的队列理念，系统中每个处理机均维护2个局部队列，和分别代表pj的主本队列和副本队列。若pj处于SP（vi）’asce的首位，则进入；否则，进入。每个任务的主／副本在相应队列中的位置与SL 中的位置保持一致。

2.2.2 调度原则

任务调度中，处理机上可能会出现空闲时间槽 （idle time slot，ITS），这里我们将时间长度不足的空闲时间段称为任务的非完整空闲时间槽 （形成空闲时间槽所需的其他条件均满足），用INITS （incomplete idle time slot）表示。

本文采用被动副本方式，当且仅当主本执行失败时才启动副本的执行［4］。每个任务的主本以经典算法HEFT 的调度方式执行，当出现处理机失效导致任务主本调度失败时，副本的执行遵循以下调度原则 （the principles of backup－copy scheduling，PBS）：①优先选择ITS，当存在多个ITS时，选择使任务的eft最小的方案；②当不存在ITS时，优先选择INITS，若存在多个INITS，选择造成其他任务延迟时间最小的方案；③根据以上原则得出执行方案后，均需与调度到处理机末尾的副本 （若存在这样的副本）作对比，选择eft最小的方案执行；④同时有多个任务执行失败，且失败任务的副本出现竞争时，竞争副本的执行顺序参照所在副本队列的顺序。

在蒸汽保护热处理的情况下，毛白杨不一样的热处理时间得到了不一样的粗糙度数据和图片，结合图7可知，在微观形貌上，将未处理材与热处理2 h、4 h比较，发现随热处理时间增加，样品表面大而深的沟槽及表面木毛明显减少，起伏状况明显减弱，同时附着物逐渐减少，其间的间隙、孔洞也逐渐变小，样品表面趋于光滑平整。但1 h样品因为短时间的热处理，导致其表面出现了较明显的开裂，故其表面比未处理样品还要粗糙。

为了更清楚地说明以上调度原则，下面从一般情况到特殊情况对副本调度原则进行实例性解释说明。

情况3：如图3 （c）所示，在tfail时刻p1和p2同时失效，和执行失败。vi有一个副本，vj有2 个副本。（2）∈。在p3上，和间存在INITS，此时和（1）间存在竞争。由于在中，的优先级较高，故选择的执行方案为：从t0时刻在p3上依次执行和，造成延迟时间△tjl，。此外，若（2）在p4末尾执行，。由于t1＜t2，故选择的最终方案为：在p3上依次执行和（1）。

图3 副本调度原则情况举例

2.3 算法流程

下面给出算法的基本流程：

（1）～ （2）步是计算任务调度优先级，并根据优先级对任务进行排序； （4）～ （10）步是计算调度风险率，对处理机进行筛选；（11）步是根据筛选结果最终确定候选处理机，计算出备份数目； （12）～ （16）步是任务正式备份，主／副本进入相应的队列； （17）～ （25）步是根据调度原则对任务进行正式调度，同时实现容错。

3 实验结果与分析

为了验证算法TSDFT （two－stage security－driven and fault tolerant scheduling algorithm）的有效性，我们设计了一组实验，从风险率、可调度性和可靠性3个方面对算法进行评估。使用matlab作为仿真实验环境，由于云环境下系统具有异构性，实验中所有DAG 和资源图随机生成，使用不同参数得到不同的DAG 和资源图。任务总数N ∈｛20，40，60，80，100｝，处理机总数M ∈ ｛8，16，32，64｝；任务的计算开销在 ［5，50］内均匀分布。

3.1 实验1：风险率测试与分析

本次实验在通信／计算比率 （communication to computational ratio，CCR）不同的情况下，对比TSDFT、HEFT和SDS （security－driven list scheduling algorithm）［7］3 种算法的任务调度风险率。CCR ∈ ｛0.1，0.4，0.8，1.0，2.0｝，风险率阈值γ取0.3。随机生成100 个DAG，每个CCR值下，实验进行100次，结果取平均值。实验结果如图4所示。

图4 风险率对比结果

算法eFRD （efficient fault－tolerant reliability cost driven algorithm）［12］和FMCED （fault－tolerant maximum communication efficiency－driven algorithm）［13］实现了容错调度，但未考虑对资源的安全筛选，且备份方式固定。为了验证本文在改进以上2种算法后的有效性，我们进行了实验2和实验3。实验中，处理机失效率服从泊松分布，设定其范围在MINR 和MAXR 之间，MINR 取1.0×10－6／h，MAXR∈［3.5×10－6／h，7.5×10－6／h］［13］。

3.2 实验2：可调度性测试与分析

成功执行的任务占所有提交的任务的百分比称为可调度性，它反映了算法寻找可行方案的能力［13］。实验2在不同的任务数目下，对比算法eFRD、FMCED 和TSDFT 的可调度性。实验结果如图5所示。

图5 可调性对度比结果

从图5中可以看出，当任务数目在40以内时，3种算法的性能比较接近；随着任务数目的增加，TSDFT 可调度性优于eFRD 和FMCED。主要原因是，随着提交的任务数的增加，调度规模不断扩大，在调度过程中失效任务数目也相应增加，致使可调度性出现一定的波动；而算法TSDFT 的容错调度建立在资源安全筛选的基础上，当任务执行失败时，其副本所在处理机安全等级较高，调度成功率增加，从而减小了失败任务在提交任务中的比例。

3.3 实验3：可靠性测试与分析

可靠性反映了算法的容错能力［13］，本次实验在处理机失效率不同的情况下，对比任务调度的可靠性。实验结果如图6所示。

图6 可靠性对比结果

从图6中可以看出，随着处理机失效率的增加，3种算法的可靠性均有小幅波动，整体呈下降趋势。处理机失效率相同的情况下，TSDFT 的可靠性较高，并且随着处理机失效率增大，这种优势更加明显。主要原因是，当处理机失效率增大时，单位时间内失效处理机次数增多，执行失败的任务数量也随之增加。在失效率较高时，可能出现一个以上处理机同时失效的情况。算法TSDFT 对处理机进行安全筛选，且使用队列策略解决了多处理机同时失效的问题，容错能力更强，提高了调度的可靠性。

4 结束语

通过分析云计算环境下任务调度的安全和可靠性需求，提出了一种两阶段安全驱动的容错调度算法。该算法同时实现了资源安全筛选和任务的容错调度，改进了备份方式并扩大了容错范围。实验结果表明算法降低了任务调度的风险率，提高了任务调度的安全性和可靠性，使算法适合于云计算环境下异构系统中具有依赖关系任务的调度。下一步的研究工作主要是进一步完善容错调度模型，考虑任务2次执行失败的情况，进一步扩大容错范围。

［1］FENG Dengguo，ZHANG Min，ZHANG Yan，et al.Study on cloud computing security ［J］.Journal of Computing Applications，2011，22 （1）：71－83（in Chinese）.［冯登国，张敏，张妍，等.云计算安全研究［J］.软件学报，2011，22 （1）：71－83.］

［2］Dimitrios Z，Dimitrios L.Addressing cloud computing security issues［J］.Future Generation Computer Systems，2012，28（3）：583－592.

［3］TIAN Guanhua，MENG Dan，ZHAN Jianfeng.Reliable resource provision policy for cloud computing［J］.Chinese Journal of Computers，2010，33 （10）：1859－1872 （in Chinese）. ［田冠华，孟丹，詹剑锋.云计算环境下基于失效规则的资源动态提供策略［J］.计算机学报，2010，33 （10）：1859－1872.］

［4］ZHANG Shuiping，LI Jizhen，ZHANG Fengqin，et al.Research and implementation of data center security system based on cloud computing ［J］.Computer Engineering and Design，2011，32 （12）：3965－3968 （in Chinese）. ［张水平，李纪真，张风琴，等.基于云计算的数据中心安全体系研究与实现［J］.计算机工程与设计，2011，32 （12）：3965－3968.］

［5］JIANG Congfeng，WANG Cheng，LIU Xiaohu.Fault tolerant grid job scheduling based on dynamic replication ［J］.Application Research of Computers，2008，25 （3）：738－743 （in Chinese）.［蒋从峰，王乘，刘小虎.基于动态备份的容错网格任务调度 ［J］.计算机应用研究，2008，25 （3）：738－743.］

［6］LUO Wei，YANG Fumin，PANG Liping，et al.A real time fault－tolerant scheduling algorithm of periodic tasks in heterogeneous distributed systems［J］.Chinese Journal of Computers，2007，30 （10）：1741－1749 （in Chinese）.［罗威，阳富民，庞丽萍，等.异构分布式系统中实时周期任务的容错调度算法［J］.计算机学报，2007，30 （10）：1741－1749.］

［7］TANG XY，LI K，ZENG Z，et al.A novel security－driven scheduling algorithm for precedence－constrained tasks in heterogeneous distributed systems ［J］.IEEE Transaction on Computers，2011，60 （7）：1017－1029.

［8］ZHU Hai，WANF Yuping.Integration of security grid dependent tasks scheduling double－objective optimization model and algorithm ［J］.Journal of Software，2011，22 （11）：2729－2748 （in Chinese）.［朱海，王宇平.融合安全的网格依赖任务调度双目标优化模型及算法 ［J］.软件学报，2011，22（11）：2729－2748.］

［9］ZHENG Q，Veeravalli B.On the design of communicationaware fault－tolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication devices［J］.Journal of Parallel and Distributed Computing，2009，69 （3）：282－294.

［10］Benoit A，Hakem M，Robet Y.Contention awareness and fault－tolerant scheduling for precedence constrained tasks in heteroge－neous systems ［J］.Parallel Computing，2009，35（2）：83－108.

［11］QIN X，JIANG H.A novel fault－tolerant scheduling algorithm for precedence constrained tasks in real time heterogeneous system［J］.Parallel Computing，2006，32 （5－6）：331－356.

［12］TANG XY，Li K，Li RF，et al.Reliability－aware scheduling strategy for heterogeneous distributed computing systems［J］.Journal of Parallel and Distributed Computing，2010，70 （9）：941－952.

［13］LING Y，LUO ZS，GE YJ.Fault－tolerant scheduling algorithm for precedence constrained tasks in grid computing systems with communication efficiency ［C］／／Proceeding of the 3rd International Conference on Information Sciences and Interaction Sciences.Chengdu，China：IEEE，2010：205－210.