基于任务截止时间的多级密码服务调度方案*

王 瑛，张 芳，裴 升，李海波，周 波，刘坤禹

（中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引言

密码技术是云应用、云数据和云虚拟化设备的安全基础之一。传统密码技术受限于扩展性差的密码服务载体，无法满足云环境下用户对数据存储、计算和传输的安全防护要求。云环境下的密码服务是当前云安全解决方案的主流模式，而当前基于云计算的密码服务具有请求多样、算法多样的任务多样性。不同的服务应用根据自身的安全需求，可以选择自身需要的不同强度的密码服务。一种合理的调度方案是解决密码资源安全、合理、快速分配的关键。

当前，云资源调度策略已经从简单的单目标调度策略逐步演变为可预测的、多目标的、智能化的复杂调度策略。除需要考虑CPU、内存、存储等资源外，云环境下的密码服务需要考虑新引入的密码计算资源。不仅要实现密码服务平台的负载均衡和密码服务质量等目标，还要考虑密码计算资源利用率和密码设备的安全要求等对密码服务云性能的影响。如何针对不同的密码服务实现所请求的密码服务的快速完成，并完成多个虚拟密码机之间的合理调度，是实现资源利用率最优化的关键。

针对上述问题，本文提出基于任务截止时间的多级密码服务调度技术，将任务截止时间转化为任务紧迫度，以衡量任务的完成优先级。通过不同等级的调度，完成任务请求和虚拟密码机之间的映射，从而满足不同应用系统的差异化需求，整体提升云环境下的密码服务性能。

1 任务调度相关研究

1.1 国内外相关研究

任务调度是指在特定时间将某些任务分配给特定的资源，是云计算中的一个重要问题。如何使用一种合理的调度机制，是提高性能和资源有效利用率的关键。目前，国内外学者研究了很多不同类型的调用机制，如云服务调度、启发式调度、工作流调度、静态调度和动态调度。在云计算中，资源的内部和外部需求都要维护，同时带宽、存储、资源开销和响应时间等需求可能因每个任务的不同而不同。负载均衡、可伸缩性、可靠性、性能以及对计算节点的资源动态重新分配，是任务调度的主要问题。所以，在云计算中需要一个有效的任务调度算法。

根据最近的研究综述，基于粒子群优化算法（Particle Swarm Optimization，PSO）的任务调度和基于遗传算法（Genetic Algorithm，GA）的任务调度是研究热点。

PSO算法适用于动态任务调度。文献[1]提供了一个基于粒子群优化算法的启发式调度方法，用于减少总执行开销。该文献对比了PSO和最佳资源选择（Best Resource Selection，BRS）算法，结论是PSO有提升，节省了3倍的成本，同时增强了现有资源的工作分布，但是导致了更高的传输和存储开销。文献[2]简要提到了资源配置危机，通过设计一种PSO算法解决这一危机。该理论基于任务总执行时间、资源保留和每个任务的QoS，研究了多目标资源优化问题中的最优调度方法。然而，该成果只能够用于简单任务，没有适用于任务调度问题的一般收敛理论。

文献[3]采用最小-最小（Min-Min）和最大-最小（Max-Min）方法，结合标准遗传算法，提出了一种增强遗传算法。Min-Min算法是一种最小执行时间算法，将任务尽量分配至运算能力最强的资源节点上，减少任务执行时间，但会导致负载不均衡，使得能力较强的节点产生极高的占用率，而其他节点出现较小的利用率。Max-Min算法是将可执行任务时间最早的节点分配给需要最大资源的任务，然后更新节点的可用时间和剩余任务集，直到全部任务调用完毕。文献[4]阐述了如何使用遗传算法进行任务调度。文献[5]解释了云服务工作流调度和使用分层云服务工作流的优化方案，包括云工作流任务并行以及分割、语法和语义的云工作流任务匹配算法以及基于多个QoS约束的云工作流调度和优化，并对该算法的性能进行了实验分析。文献[6]解释了一种用于云环境中使用优先队列进行任务调度的改进遗传算法。当前的文献大多是基于一般的云服务任务调度，但是针对密码服务的任务调度没有很好的解决方案。针对该问题，本文提出了一种基于任务截止时间的多级密码服务调度方案。

1.2 密码服务的任务调度目标

虚拟机调度策略在不同的目标之间往往是相互冲突的[7]。

（1）以提高资源利用率为目标的调度策略需要在减少活跃虚拟机的情况下，将云资源充分地分配到各个虚拟机，而这将导致在突发性负载条件下云服务质量的降低，影响用户体验。

（2）以服务质量为目标的调度策略往往会预留部分资源用于处理突发任务，保证服务质量，但是易造成资源闲置。

（3）以降低能耗为目标的调度策略通常通过减少活跃虚拟机来降低数据中心的能耗，以低成本完成高负载，但同样会导致突发性负载条件下的宕机情况；

（4）以负载均衡为目标的调度策略需要开启更多的虚拟机，将系统负载均衡地分配到各个云主机，既增加了能耗，又不能充分利用云资源。

关于虚拟机调度的研究，大部分方法都是在特定的研究情境中满足主要目标，同时兼顾其他次要目标。本文主要针对云环境中的密码服务，与传统任务相比，密码服务的任务与虚拟资源属性之间、任务与用户的身份之间，存在很强的依赖型。即使是使用相同的密码服务，由于用户需求不同，任务所使用的密码算法可能不相同，导致不同的密码算法对云计算中的资源调度和需求都不同。密码服务对任务调度的时效性、安全性要求更高，各种密码算法的复杂度也更高。针对上述问题，本文在传统任务调度算法的基础上提出了一种基于任务截止时间的多级密码服务调度策略。

2 基于多级密码服务的任务调度方案

2.1 任务调度模型

任务调度模型如图1所示。本文提供的任务分析和任务调度中的密码处理分别由多个虚拟密码机完成。这里的任务主要是指一次完整的密码协议处理，如完成一次数据包的加密即为一个任务。

图1 任务调度模型

（1）任务集合T={T1,T2,…,Tn}，表示参与任务调度的任务集合，其中下标为i=(1,2,…,n)，表示第i个任务。

（2）虚拟密码机集合V={V1,V2,…,Vm}，其中下标为j=(1,2,…,m)，表示不同等级的虚拟密码机。根据密码的性能不同，可将其划分为不同等级的虚拟密码机群。

（3）FTij=ETij+TSj，其中FTij表示第i个任务在第j个虚拟密码机的完成时间，FTij表示第i个任务在第j个虚拟密码机的执行时间，TSj表示虚拟密码机的最早可用时间。

第i个密码服务形式化描述如下：

式中：Tid表示任务的标识；Tlen表示任务的大小长度；Ttype标识密码服务的类型，不同的密码服务所需的资源不同；Tdl表示该任务的截止时间。

第j个虚拟密码机形式化描述如下：

式中：Vid表示虚拟密码机的标识；Vsp表示虚拟密码机的处理速率；Vfc表示该虚拟密码机能够实现的密码功能；Vexc表示任务执行时间，Vmin表示最小可执行任务时间，若当前节点有k个任务正在执行，则

虚拟密码机的多元组属性由任务调度模块维护并更新。任务执行过程中对每个虚拟密码机的当前状态进行实时监控，以提高任务的调度效率和任务处理的实时性。

2.2 基于任务截止时间的任务调度方案

本文方案以任务截止时间为主目标，在此本文设置一个任务紧迫度，即：

它表示任务截止时间减去任务完成时间的值。这个值越小，表示任务越紧迫。当DTmin=0时，代表任务截止时间与完成时间相等；DTmin<0，则表示任务无法在截止时间内完成，则任务执行失败。当两个任务的紧迫度相同时，选择任务标识值更小的优先执行。

根据不同的密码服务需要的资源和任务紧迫度，将任务分为4类不同的密码服务类型。

（1）Ttype=1表示该服务需要最多的密码计算资源，任务紧迫度最高的任务（DTmin<1），如非对称加解密服务等；

（2）Ttype=2表示该服务需要较多的密码计算资源，任务紧迫度第二的任务（1

（3）Ttype=3表示该服务需要较少的密码计算资源，任务紧迫度第三的任务（10

（4）Ttype=4表示该服务需要的计算资源不用太多，任务紧迫度最低的任务(20

同样的，相应的任务等级对应4个等级的虚拟密码机。等级越高，下标越小，功能及性能越好。这是一个向下单向兼容的虚拟机分类。当高等级虚拟机空闲时，也可以将低等级的任务分配至高等级虚拟机，但是高等级的任务不能够分配至低等级的虚拟密码机执行，以尽可能达到资源利用率高且负载均衡的目的。

（1）Vfc=1表示该虚拟机具有全部密码服务的功能，且计算能力最强，可执行全部等级的任务，优先执行高等级任务；

（2）Vfc=2表示该虚拟机具有大部分密码服务的功能，且计算能力较强，可执行除Ttype=1的其余等级任务；

（3）Vfc=3表示该虚拟机具有较少密码服务的功能，且计算能力较弱，可执行3、4等级的任务；

（4）Vfc=4表示该虚拟机只具有固定的密码服务的功能，且计算能力最弱，只能够执行等级为4的任务。

3 任务调度流程

3.1 任务流程

应用系统发起的密码服务请求首先汇聚到任务接收队列，任务分析模块对任务接收队列中的任务包进行分类，并按照不同类型的密码服务将任务包放入不同的任务请求队列。这里将任务分类到不同队列的主要作用有两个：对应用未设置任务截止时间的，可以根据不同业务类型设置截止时间；可以方便使用多线程，同时对多个任务进行映射处理，提升处理速率，同时避免一种类型的任务阻塞其他任务；用户可以设置相应的参数，如将任务紧迫度设置为高，可以将任务提前送入空队列进行作业。

任务调度具体流程如下。

（1）服务器将任务发送到任务分析模块，由任务分析模块根据任务的属性、请求等，将具有任务标识等多元属性的包头添加至任务包；

（2）任务分析模块将具有多元属性域的包头的任务包发送到任务调度模块；

（3）任务调度模块通过分析包头中的相关属性字段，将任务映射至相应虚拟密码机进行密码服务，完成一次任务调度。

在以任务截止时间为首要目标的同时，通过合理设置，利用Min-Min调度算法思想，在高等级虚拟密码机空闲或即将空闲时，将低等级的任务合理分配至高等级虚拟机。在高等级虚拟密码机占用率过高时，正常分配相应等级的任务至相应虚拟密码机，从而达到负载均衡的目的。

本文通过对任务截止时间为首要目标进行等级划分，建立虚拟密码机性能和任务截止时间之间的映射关系，将任务分别放入不同虚拟密码机对应的等级队列。映射的主要依据是任务处理截止时间要求和等级队列的最小任务等待时间。截止时间为每个任务包处理完成的时间需求。最小任务等待时间可表示对应虚拟密码机的处理速率或负载情况，随着系统运行动态变化。最终各等级队列中的任务将被分发至相应等级的虚拟密码机，由虚拟密码机负责执行相应密码服务。完整的密码服务多级调度流程如图2所示。

图2 密码服务多级调度流程

3.2 不同策略的执行时间对比测试

本文为了测试方案的效率，与传统的遗传算法（GA策略）和粒子群算法（PSO策略）进行对比。测试对比任务参数设置如表1所示。

表1 测试参数

在使用相同数量虚拟密码机和任务属性的情况下，计算3种方案在不同任务数量情况下的任务执行时间，结果如图3所示。

图3 策略效率对比

从图3可以看出，本文策略比传统的遗传算法和粒子群算法在相同任务量的执行时间上有进一步的提升。本文方案将任务截止时间作为首要考虑参数，且设计多级调度，将最紧要的任务调度到性能最好的虚拟密码机执行，是合理有效的。

4 结语

本文通过分析现有的任务调度方案和密码服务需求，提出了一种基于任务截止时间的多级密码服务调度技术。以任务截止时间为第一优化目标，提出任务紧迫度的等级划分，并以本文所提出的任务紧迫度作为衡量任务调度的标准，使得不同等级的虚拟密码机完成不同等级的任务。通过和传统的任务调度算法进行效率对比可以看出，本文方案在使得完成密码服务的时间尽量短的情况下，兼顾虚拟密码机性能的负载均衡，以满足不同应用系统的差异化需求，整体提升云环境下的密码服务能力。