面向系统应用模式的资源调度优化算法

2018-10-23白鸿武

舰船电子工程 2018年10期

白鸿武

（咸阳师范学院咸阳 712000）

1 引言

互联网技术的快速发展，导致了产品商品化竞争越来越激烈，用户体验对于企业成败至关重要［1］。业务能否高效运行直接关系到企业利润、业务流量增长［2］。面对网络复杂性、异构性和分布性的增强，网络环境日趋复杂，涉及的组件日趋广泛，如服务器、存储、网络、中间件和数据库等［3～5］，任何一个环节的短板都可能是整个系统的性能瓶颈，如何有效提高系统业务能力，是每个系统在发展过程中可能不得不面对的问题。

随着硬件性能的提升和高性能计算的发展，高性能计算机越来越普遍，给计算机应用带来了更多发展空间，计算机性能向着智能化、网络化等方向发展［6～8］，完成某项复杂功能的应用可能有大量完成部分功能的作业组成，或者完成某项功能希望同时运行几个应用，而服务器资源是有限的，由此产生一种资源管理问题，即资源受限项目调度问题（Resource Constrained Project Scheduling Problem，RCPSP）［9］，在满足应用资源需求及技术上需要的应用前后约束的前提下，对应用进行合理调度，寻找项目最短工期。为描述方便，论文将上述包含一系列作业的复杂应用或需要很多应用配合的复杂系统表述为系统，将其包含的作业或应用表述为应用。

在服务器中，系统包含的应用的调度大多是混乱的，由运维人员通过自身经验决定，没有科学的参考依据，如果能够通过对应用特征进行分析，获得应用的性能模式，根据应用性能模式为应用选择调度策略寻找一种更好的综合调度方案，不仅能提高服务器资源利用率，也能节省系统整体运行时间，对提升系统性能有很大价值。因此论文提出一种基于系统应用模式的资源调度优化算法。

2 算法概述

常用于解决资源受限项目调度问题的算法主要是将所有应用加入一个资源池，根据应用资源需求寻找调度方案［10］。而本文提出的基于系统应用模式的资源调度优化算法，从应用的行为模式出发，首先根据应用资源需求特征判断应用的行为模式，然后再从行为模式出发，选择不同调度策略寻找调度方案。

即使应用实现的功能千差万别，各不相同，但是对资源的需求却总是有模式可循的，偏计算功能的应用一般需要的CPU资源多一些，偏交互功能的应用可能需要的IO资源多一些。调度应用时，虽然不关心其功能，但是其资源需求却至关重要。设想将两个CPU资源需求都很高，但是内存需求却很低的应用一起调度，虽然可行，但是服务器的内存资源没有充分利用，CPU资源却存在强的竞争，可能造成应用性能瓶颈，影响用户体验。而如果将一个CPU资源需求高，内存需求低的应用和一个CPU资源需求低，而内存需求高的应用一起调度，不仅可以减少应用竞争，而且能够提高服务器资源利用率［11］。因此通过聚类的方法对应用资源需求特征进行挖掘，得到其行为模式，来指导调度算法可以优化调度方案。

本文采用的调度算法，首先通过人工干预的方式，根据系统应用模式为其选择调度策略，调度策略分两种：策略A，行为模式表明应用各种资源需求达到一种平衡，没有明显偏向，则此种模式应用内通过调度算法寻找调度方案；策略B，模式一和模式二两种模式表明这两种应用资源需求存在互补关系，比如模式一需要CPU资源多内存少，模式二需要CPU资源少内存多，则在两种应用内通过调度算法寻找调度方案。

综上，基于系统应用模式的资源调度优化算法分为两个步骤：一是系统应用模式挖掘，二是应用调度优化。

3 算法设计

3.1 基于聚类算法的系统应用模式挖掘算法设计

通过数据采集系统采集到的应用运行期间的数据是时间序列数据，因此，系统应用模式挖掘就是时间序列挖掘。因为时间序列数据具备高维性、复杂性、动态性及高噪声等特性，而且与时间相关联，数据量非常庞大，所以直接聚类分析有很大复杂性，因此采用基于特征的聚类方法，提取每类资源需求的最大值作为其资源需求特征，然后进行聚类分析。

基于聚类算法［12］的系统应用模式挖掘算法将k-means算法和层次聚类算法相结合［13］。首先根据开发人员的经验对数据初步分析，估计一个k值，k大于最终类别数，且远小于样本数目，然后通过k-means算法进行初步聚类，得到k个聚类中心点。再通过层次聚类算法对k个中心点再次聚类，得到层次聚类树，最后通过对层次聚类每次聚类情况的分析，对层次聚类树剪枝，得到最终的聚类结果。这样结合不仅解决了k-means算法k值难以确定的问题，也避免了层次聚类算法计算量过大，效率低下的问题。

基于聚类算法的系统应用模式挖掘算法流程如图1所示。

图1 基于聚类算法的系统应用模式挖掘算法流程图

3.2 基于系统应用模式的资源调度算法优化设计

根据多维资源综合调度算法［14］实现基于系统应用模式的调度算法。

服务器的资源容量抽象为一个m维向量，R={r1,..,rm}，ri表示资源Ri的总量。假设服务器有n个应用需要调度，应用 j由资源需求向量wj={w1,j,..,wm,j}，对资源Ri的需求记做wi,j。

定义Pj表示调度应用 j的收益，如下面式（1）所示。问题最终目的是最大化总收益：

定义αi，表明各种资源维度之间的稀缺程度，如式（2）所示，其中，uj和rj是没有调度的应用数量和资源限制。

定义效率度量标准ej，用来动态调整优先选择那些需要较少的稀缺资源的应用，如式（3）所示。

在基于系统应用模式的调度算法中，主要分为两步：一是通过人工干预的方式，根据系统应用模式，选择调度策略；二是根据不同调度策略对不同模式的应用进行调度。最后将所有模式的调度方案合并，得到系统完整调度方案。

根据系统应用模式，可以判断哪些模式对于资源的需求达到了一种平衡，采用调度策略A，此种模式的应用加入一个资源池进行调度；哪些模式对于资源需求是具有互补关系，采用调度策略B，这两种模式的应用加入一个资源池进行调度。具体调度过程如下：

步骤1：计算每种资源稀缺程度α，每个应用的收益P和效率e；

步骤2：按照e递减，P递减的方式对等待调度的应用进行排序；

步骤3：调度策略A，从等待调度的应用队列中选择可以满足资源需求且可以调度的应用进行调度；

步骤4：调度策略B，从等待调度的应用队列中优先选择正在运行的应用中模式较少的一方的可调度应用进行调度，比如正在运行的应用中模式一数量多，则优先选择模式二的应用，反之亦然；

步骤5：从正在运行的应用队列中选择运行结束的应用移除队列，释放资源；

步骤6：重复上述过程，直到等待调度的应用队列为空，得到调度方案。

基于系统应用模式的调度算法的伪代码如算法1所示。

算法1：基于系统应用模式的调度算法输入：服务器资源容量res，应用信息jobInfos输出：调度方案BEGIN:strategys=SelectStrategyByPattern(jobInfos)res=initRes()jobs_wait=initJobsWait(jobInfos)while(jobs_wait.length＞0):jobs_wait.compute(p,α,p)jobs_wait.sortDESC(e,p)if(strategy==‘A’):jobs_choosed=jobs_wait.choose()else:jobs_choosed=jobs_wait.chooseTheLessPattern()end if jobs_wait.pop(jobs_choosed)jobs_run.append(jobs_choosed)res.subtract(jobs_choosed.need)jobs_finish=jobs_run.finish()jobs_run.pop(jobs_finish)res.add(jobs_finish.need)jobs_finish.append(jobs_finish)end while return jobs_finish END

4 实验验证

选择90个应用，取其CPU、内存和网络需求，作为数据样本。首先通过k-means对数据样本进行初步聚类，取k为30。然后对中心点层次聚类。计算每次合并时，所有样本的距离和，如图2所示，可以看出6是一个明显拐点，因此最终将90个应用聚成6类。

图2 层次聚类距离图

应用聚成6类时，数据中心即系统应用模式如表1所示。从数据中心可以看出，应用1和应用2，应用5和应用6在资源需求上存在互补关系，应用3在资源需求上处于一种自平衡的状态，应用4资源占用与应用2比较接近，归入应用2。

表1 系统应用模式表

本文对应用1和应用2（包含应用4），应用5和应用6运用基于系统应用模式调度算法的策略B，对3应用策略A。选择其中30个应用进行调度，通过多种算法比较进行可行性分析。不同算法情况如表2所示。

表2 不同算法生成的调度方案情况表

从表2中数据可以看出，任何一种调度算法给出的调度方案都可以对调度结果产生优化，不仅可以缩短整体调度时间，还可以提高数据中心资源利用率。同时，我们也可以从表中数据看出，不同调度算法的优化效果存在很大差距。

粒子群算法［15］由于位置、速度初始化以及中间调整过程都具有随机性，产生的结果并不理想。多维资源综合调度算法，表现比较好，程序运行时间很短，整体调度时间缩短了一半，各类资源利用率也有很大提高。遗传算法生成的调度方案效果最好，但是程序运行时间很长，时间复杂度太高。基于系统应用模式的调度算法，不仅运行时间短，且整体调度时间最短，各类资源平均利用率也是大幅度提高，综合来看，表现最好。