一种用于云系统的资源调度方法
一种用于云系统的资源调度方法
【技术领域】
[0001] 本发明涉及计算机技术领域，具体说涉及一种用于云系统的资源调度方法。
【背景技术】
[0002] 云计算就是通过互联网将分布在不同数据中心的计算，存储和网络等基础设施， 以及其上的开发平台、软件和应用等以服务的形式提供给用户。由于云计算具有按需收费， 节约成本，充分利用资源等特点，使得全球进入了云计算的时代。
[0003] 云计算应用平台的资源分布广泛并且种类多样，通常云计算应用平台会根据用户 的使用需求将资源合理的分配给用户，使得整个云计算应用平台负载均衡。但是在正常使 用云计算的过程中，使用者的使用需求往往是实时变化的。随着使用云计算的用户不断增 多，面对海量的用户的需求的实时变化，云计算应用平台的负载会出现不均衡的状态，从而 造成资源浪费。并且负载不均衡也会导致局部负载过载的情况发生。
[0004] 为了解决负载不均衡的问题，需要根据云计算平台的实际使用情况对资源进行调 度。目前云计算平台的资源调度问题，通常是通过监测负载均衡日志和检测响应时间来实 现的。其资源管理算法考虑的情况相对简单，而且存在较多的负载，性能，服务质量等方面 的问题。另外，资源调度会产生迀移代价，不合理的资源调度方法不仅不能很好的解决负载 不均衡的问题而且会生成过高的迀移代价。
[0005]以在开源的软件基础结构（ElasticUtilityComputingArchitecturefor LinkingYourProgramsToUsefulSystems，Eucalyptus)上实现的云平台为例。 Eucalyptus平台采用三种独立的调度算法去解决，分别是：
[0006] (1)greedy算法：优点是简单，直接但是容易过载。
[0007] (2)roundrobin算法：优点是负载均衡了但是能源消耗高。
[0008] (3)p〇Wersave算法：优点是降低了能量消耗但是资源利用率低。
[0009] 针对负载均衡、资源利用率高、迀移代价小等标准，不能在一种调度算法中同时满 足这些目标。
[0010] 因此，针对现有云计算平台的资源调度方法存在的问题，需要一种新的资源调度 方法以达到在充分利用资源，实现负载均衡的基础上尽可能的减小迀移代价的目的。
【发明内容】
[0011] 针对现有云计算平台的资源调度方法存在的问题，本发明提供了一种用于云系统 的资源调度方法，所述方法包括以下步骤：
[0012] 种群初始化步骤，获取云系统的资源调度的备选方案，利用所述备选方案构造初 始种群，其中，所述备选方案包含节点控制器与虚拟机的分配关系，每个所述备选方案对应 所述初始种群中的一个个体；
[0013] 构造适应度函数步骤，针对所述资源调度的具体需求构造总适应度函数；
[0014] 种群筛选步骤，利用所述总适应度函数对所述初始种群中的个体进行筛选从而获 取适应个体；
[0015] 资源调度步骤，根据所述适应个体对应的所述备选方案对所述虚拟机以及所述节 点控制器进行资源调度。
[0016] 在一实施例中，所述种群初始化步骤包含建模步骤，对参与所述资源调度的资源 对象进行建模，所述资源对象包括所述节点控制器、所述虚拟机、所述云系统的负载状况以 及所述资源调度的迀移代价。
[0017] 在一实施例中，在所述建模步骤中，从所述云系统中选择特定的一个集群进行分 析以获取分析结果，根据所述分析结果进行建模。
[0018] 在一实施例中，所述种群初始化步骤包含编码步骤，对所述备选方案进行编码。
[0019] 在一实施例中，在所述编码步骤中，利用数组进行编码，从而生成表示所述虚拟机 与所述节点控制器的分配关系的关系数组。
[0020] 在一实施例中，在所述种群初始化步骤中，采用轮询算法获取所述备选方案。
[0021] 在一实施例中，在所述种群筛选步骤中，利用轮盘赌的方法进行筛选。
[0022] 在一实施例中，在所述构造适应度函数步骤中，根据所述云系统的负载状况以及 所述资源调度的迀移代价构造所述总适应度函数，所述总适应度函数与负载均衡以及所述 迀移代价相关。
[0023] 在一实施例中，所述构造适应度函数步骤包含以下步骤：
[0024] 针对所述负载情况以及所述迀移代价分别构造负载均衡适应度函数以及迀移代 价适应度函数；
[0025] 通过所述负载均衡适应度函数以及所述迀移代价适应度函数的权值的组合获取 所述总适应度函数。
[0026] 在一实施例中，所述种群筛选步骤还包含单代筛选步骤、个体交叉步骤和/或个 体变异步骤，其中：
[0027] 在所述单代筛选步骤中利用所述总适应度函数对所述初始种群中的个体进行筛 选以生成第一种群；
[0028] 对所述第一种群执行所述个体交叉步骤和/或所述个体变异步骤以生成第二种 群；
[0029] 对所述第二种群再次执行所述单代筛选步骤以更新所述第一种群，并对更新后的 所述第一种群再次执行所述个体交叉步骤和/或所述个体变异步骤；
[0030] 重复执行特定次数的所述单代筛选步骤，最终获取的更新后的所述第一种群中的 个体为所述适应个体；
[0031] 在所述个体交叉步骤中基于遗传学算法按照特定的交叉概率随机选取所述第一 种群中的两个个体进行交叉以产生两个新个体从而丰富所述第一种群进而生成所述第二 种群；
[0032] 在所述种群初始化步骤中基于遗传学算法按照特定的变异概率随机选取所述第 一种群中一个个体，对所述个体对应的备选方案在可取范围内进行随机变化从而产生新个 体以丰富所述第一种群进而生成所述第二种群。
[0033] 与现有技术相比，本发明的资源调度方法可以在实现负载均衡结果良好的同时实 现较小的迀移代价。
[0034] 本发明的其它特征或优点将在随后的说明书中阐述。并且，本发明的部分特征或 优点将通过说明书而变得显而易见，或者通过实施本发明而被了解。本发明的目的和部分 优点可通过在说明书、权利要求书以及附图中所特别指出的步骤来实现或获得。
【附图说明】
[0035] 附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实 施例共同用于解释本发明，并不构成对本发明的限制。在附图中：
[0036] 图1是根据本发明一实施例执行流程图；
[0037] 图2是根据本发明一实施例个体编码示意图；
[0038] 图3是根据本发明一实施例资源调度结果仿真图。
【具体实施方式】
[0039] 以下将结合附图及实施例来详细说明本发明的实施方式，借此本发明的实施人员 可以充分理解本发明如何应用技术手段来解决技术问题，并达成技术效果的实现过程并依 据上述实现过程具体实施本发明。需要说明的是，只要不构成冲突，本发明中的各个实施 例以及各实施例中的各个特征可以相互结合，所形成的技术方案均在本发明的保护范围之 内。
[0040] 云计算就是通过互联网将分布在不同数据中心的计算，存储和网络等基础设施， 以及其上的开发平台、软件和应用等以服务的形式提供给用户。在正常使用云计算的过程 中，面对海量的用户的需求的实时变化，云计算应用平台的 负载会出现不均衡的状态，从而 造成资源浪费。并且负载不均衡也会导致局部负载过载的情况发生。
[0041] 为了解决负载不均衡的问题，需要根据云计算平台的实际使用情况对资源进行调 度。目前云计算平台的资源调度问题，通常是通过监测负载均衡日志和检测响应时间来实 现的。其资源管理算法考虑的情况相对简单，而且存在较多的负载，性能，服务质量等方面 的问题。另外，资源调度会产生迀移代价，不合理的资源调度方法不仅不能很好的解决负载 不均衡的问题而且会生成过高的迀移代价。
[0042] 以在开源的软件基础结构（ElasticUtilityComputingArchitecturefor LinkingYourProgramsToUsefulSystems，Eucalyptus)上实现的云平台为例。 Eucalyptus平台采用三种独立的调度算法去解决，分别是：
[0043] (1)greedy算法：优点是简单，直接但是容易过载。
[0044] (2)roundrobin算法：优点是负载均衡了但是能源消耗高。
[0045] (3)p〇Wersave算法：优点是降低了能量消耗但是资源利用率低。
[0046] 针对负载均衡、资源利用率、迀移代价小等标准，不能在一种调度算法中同时满足 这些目标。
[0047] 因此，针对现有云计算平台的资源调度问题，本法命题出了一种用于云系统的资 源调度方法。本发明首先改进了遗传算法，然后将改进后的遗传算法应用于云计算平台的 资源调度。根据不同的目标在遗传算法中设计不同的目标函数和阈值，利用遗传算法求得 全局最优解的特性，实现在该算法中同时满足对云资源调度的多种标准要求，从而解决了 现有调度算法中无法同时满足负载均衡，高资源利用率，迀移代价小的问题。
[0048] 接下来基于流程图来详细描述本发明的资源调度方法的具体执行过程，附图的流 程图中示出的步骤可以在包含诸如一组计算机可执行指令的计算机系统中执行。虽然在流 程图中示出了各步骤的逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示 出或描述的步骤。
[0049] 遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的 计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能 潜在的解集的一个种群开始，种群中的每个个体都是问题的一种可能的解决方案。根据具 体的解决问题的需求设定外在环境，通过环境适应度筛选种群中的个体，从而获取最适应 外在环境的个体，即最适应解决问题的需求的解决方案。
[0050] 本发明的方法主要是利用遗传算法获取最优的资源调度方案，因此首先要构建用 于遗传算法筛选的初始种群。在本实施例中，如图1所示，首先要执行步骤S110,种群初始 化步骤，获取用于筛选最优资源调度方案的初始种群。初始种群包含进行资源调度的多个 可能的解决方案，即初始种群中的每一个个体都是针对云系统的资源调度的备选方案。云 系统的资源调度主要是在各个虚拟机以及节点控制器之间分配资源，因此，每个云系统的 资源调度的备选方案均包含节点控制器、虚拟机以及节点控制器与虚拟机的分配关系，每 个备选方案对应初始种群中的一个个体
[0051] 在使用遗传算法获取最优的资源调度方案之前，为了便于算法的顺利执行，首先 要将与资源调度有关的研宄对象数字化。在本实施例中，首先执行步骤111，建模步骤，对 云系统中参与资源调度的资源对象进行建模。由于云系统的资源调度主要是在各个虚拟 机以及节点控制器之间分配资源，因此需要执行建模的资源对象包括节点控制器以及虚拟 机。另外，由于本实施例中进行资源调度的目的是实现负载均衡，因此需要执行建模的资源 对象还包括云系统的负载情况。最后，本实施例的方法还要尽可能的达到最小迀移代价，因 此需要执行建模的资源对象还包括迀移代价。
[0052] 进行建模就需要对整个云系统中的所有建模对象进行分析。考虑到云系统中包含 多个集群（多个集群控制器），而资源调度的执行是在每个集群中执行的。而本发明的研 宄对象是一个集群控制器下的多个节点，每个节点控制器下多个虚拟机。因此为了简化流 程，降低建模复杂程度，本实施例在所述建模步骤中，从云系统中选择特定的一个集群进行 分析以获取分析结果，从而根据分析结果进行建模。
[0053] 具体建模如下：
[0054] (1)虚拟机和节点控制器：对于一个集群控制器（ClusterController，CC) 下的多个节点控制器（NodeController，NC)以及虚拟机（VirtualManufacturing， VM)，用NQ，NC2,NC3,......NQ来表示第一个节点，第二个节点……第i个节点；用 VM〇,VM2,......表示第1个虚拟机，第2个虚拟机……第j+1个虚拟机。
[0055] (2)负载情况：为了表示出负载，需要选取一个时间周期T记录这个时间段内的平 均负载，并选取cpu利用率（ratio(cpu))、内存（memeory)、网络流量（Net)三者由不同权 值（A、B、C)组合成一个节点控制器NC上的负载总值（Load)，如下式1所示：
[0056]Load=A*ratio(cpu)+B*memeory+C*Net(1)〇
[0057] 所以第j个VM的平均负载（)就是
[0059]则每个节点控制器总负载
[0061]也就是说在T周期内，所有在该节点上的虚拟机负载的综合是该节点的总负
[0062]载。所以每个节点控制器的资源负载比为
[0064] 其中&表示第i个节点控制器的能力（节点控制器的容量，即最大能容纳多少的 负载）。
[0065] (3)迀移代价：由于在资源调度中需要对虚拟机部署做适度的调整，所以存在需 要虚拟机迀移的情况。以M'表示需要迀移的虚拟机，M表示总的虚拟机。由于算法中的种 群就是不同的虚拟机被分配到不同节点的方案的集合。则定义在实施方案后需要迀移的虚 拟机数目为迀移代价。迀移代价C为
[0067]在遗传算法中，一个种群是由经过基因编码的一定数目的个体组成。每个个体实 际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内 部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是 由染色体中控制这一特征的某种基因组合决定的。
[0068] 因此在使用遗传算法时，在一开始需要实现从表现型到基因型的映射即编码工 作。在本实施例中，为配合遗传算法，如图1所示，要执行步骤S112,编码步骤，对构成初始 种群的个体（备选方案）进行编码。即针对虚拟机、节点控制器、虚拟机与节点控制器的分 配关系进行编码。
[0069]由于仿照基因编码的工作很复杂，通常会进行简化，利用二进制编码进行编码。但 是二进制编码不适合描述本实施例中的备选方案。因此为了方便计算，减少资源调度的执 行难度，本实施例采用数组进行编码。根据Eucalyptus云平台资源调度情况，将数组的值 作为节点的序列号，将数组数值所在的位置作为虚拟机的序列号。这样最后生成的备选方 案就包含虚拟机与节点控制器的关系数组。
[0070]在本实施例中，染色体是以整数数组的形式表示，并且数组中每个元素的位置代 表虚拟机的序列号，每个元素的值为节点控制器的序列号。如图2所示，虚线框200内表 示 的是一具体的虚拟机部署方案：第〇号虚拟机被部署在第5号节点上运行，第1号虚拟机被 部署在第9号节点上运行，第2号虚拟机也被部署在第5号虚拟机上运行，第3号虚拟机被 部署在第1号节点上运行，第4号虚拟机被部署在第3号节点上运行。则部署方案200就 可以表示为数组201 (5,9, 5,1，3)。
[0071] 建模后就可以利用备选方案构造初始种群，即获取构成初始种群的各个个体。由 于在本实施例中，初始种群的每个个体对应的是云系统资源调度的备选方案。因此此时执 行步骤S112,获取备选方案步骤。本发明的目的是从多个备选方案（初始种群）中筛选出 最适合的方案（个体）。因此。初始种群的丰富程度（个体数目/带筛选的备选方案的丰 富程度）以及整体负载均衡程度越高，最后获取的筛选结果也越好。
[0072] 为了尽可能多的获取备选方案，丰富初始种群，均衡整体的负载程度在编码的基 础上，本实施例采用了采用轮询算法对种群进行初始，也就是经过轮询算法后形成的虚拟 机与节点控制器的关系数组为最初的种群。这样不仅达到了丰富初始种群的目的而且还使 初始化的种群先达到整体的负载均衡情况。
[0073] 在本实施例中，采用轮询算法将一定数量的虚拟机分配给合适的节点控制器。构 造一个数组集合作为初始种群。数组集合中的每一个数组代表一种虚拟机部署方案（虚拟 机与节点控制器的关系数组）（见图2所示的具体例子）。
[0074] 初始种群产生之后，就可以按照适者生存和优胜劣汰的原理，根据个体对环境的 适应程度进行筛选以获取最适合环境的个体（问题的最优解）。这里首先要构造用于筛选 的环境，具体到本实施例，就是要执行步骤S120,构造适应度函数步骤，针对云系统的资源 调度的具体需求构造总适应度函数（用于筛选的环境）。
[0075] 由于本实施例中进行资源调度的目的是实现负载均衡并尽可能的达到最小迀移 代价，因此在步骤S120中，根据云系统的负载情况以及迀移代价构造总适应度函数，使得 总适应度函数与负载均衡以及迀移代价相关。
[0076] 由于总适应度函数有多个目标，那么首先就要设定多个目标函数。即首先针对负 载情况以及迀移代价分别构造负载均衡适应度函数以及迀移代价适应度函数；然后通过负 载均衡适应度函数以及迀移代价适应度函数的权值的组合获取总适应度函数。其中，采用 每个节点利用率与平均资源利用率的方差来表示负载均衡情况，用需要迀移的虚拟机与总 虚拟机的比值作为迀移代价。
[0077] 具体执行如下：
[0078] 首先是负载均衡适应度函数：假设总共有i个节点，现有的虚拟机总数为j+1，根 据当前系统的具体要求设定节点的资源利用率的阀值为R〇,迀移代价的阀值为CJ设定迀 移代价的阀值可使迀移代价控制在较小的范围内）。根据上面过程中建立的模型（式1-式 5)最终负载均衡的适应度函数为：
[0079] R^R0 (6)
[0083] 其中：氏为每个节点控制器的资源负载比（见式4);
[0084] 云为系统中所有节点的平均资源利用率；
[0085] Sn为方差，即每个节点的资源利用率与平均资源利用率的差值，用来表示负载是 否均衡。
[0086] 迀移代价的适应度函数为：
[0088] 其中：M'表示需要迀移的虚拟机，M表示总的虚拟机，Q表示每种方案下的迀移代 价，Q表示迀移代价的阀值（见式5)。
[0089] 由于每个方案下，都有各自的迀移代价和负载方差。分别设定迀移代价和负载方 差的权值V和W，V+W= 1。这样总的适应度函数取决于这两个方面因素，方差越小越好，迀 移代价越小越好。选其倒数，这样方差和迀移代价越小的方案，适应度函数的值越大，在下 一步的轮盘赌步骤下被选中的概率也就越大，优秀个体就越易被保存下来。则最终的适应 度函数？"是迀移代价与负载均衡的适应度函数的结合
[0091] 接下来就可以执行步骤S130,筛选步骤，利用总适应度函数（环境）对初始种群中 的个体进行筛选从而获取适应个体（最适应环境的个体）。
[0092] 然而在自然界中，一个种群不是一成不变的，个体会逐代演化产生出越来越适应 环境的个体（更加接近问题完美解决方案的近似解）。遗传算法模拟了上一过程，在每一 代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合 交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代 种群比前代更加适应于环境，这样末代种群中的最优个体就可以作为问题近似最优解。
[0093] 本发明将上述原理改进后应用到了资源调度备选方案的筛选上。即利用总适应度 函数对初始种群进行筛选（自然选择中的一代选择），在筛选之后对筛选的结果进行个体 交叉和/或个体变异以构成新的种群（自然选择中的每一代个体的遗传变异）。然后利用 总适应度函数对新生成的种群再次筛选。多次重复筛选、交叉和/或变异过程（自然选择 中对物种的多代选择）直到完成特定次数的筛选。
[0094] 具体到本实施例则是在筛选步骤S130构造了单代筛选步骤（S131)、个体变异步 骤（S132)以及个体交叉步骤（S133)。
[0095] 步骤S133是基于遗传学算法按照特定的交叉概率随机选取目标种群中的两个个 体进行交叉以产生两个新个体从而丰富目标种群进而生成新的种群。在传统的遗传算法 中，交叉概率的范围是0. 6到0. 95。在本发明中采用单点交叉，交叉点为数组中的某个位置 上的数据值，也就是在该位置上所分配的节点的改变。因此在本实施例中，特定的交叉概率 为 0? 7〇
[0096] 步骤S132是基于遗传学算法按照特定的变异概率随机选取目标种群中的一个个 体，对个体对应的备选方案在可取范围内进行随机变化从而产生新个体以丰富目标种群进 而生成新的种群。对于遗传算法，变异概率的范围是0.01到0.03。当一个个体被选中时， 也就是选中一个数组，则这个数组中某个位置的值会随机的变成1~i中的一个数值。其 中1~i是所有节点的序列号。在本实施例中，特定的变异概率为〇. 02。
[0097] 同时，由于本实施例的备选方案包含虚拟机与节点控制器的关系数组，因此在步 骤S132中，随机选取个体后，对数组中的某个数值位置的值随机变成在可取范围内的某个 节点的序列号以生成新的数组（个体）。
[0098] 筛选步骤S130的具体执行过程如下：
[0099] 首先在步骤S131中利用总适应度函数对初始种群中的个体进行筛选；
[0100] 然后针对步骤S131的筛选结果执行步骤S132和步骤S133以生成新的种群；
[0101] 对新的种群再次执行步骤S131以获取新的筛选结果；
[0102] 如此循环重复直到执行特定次数的步骤S131，此时步骤S131的筛选结果中的个 体即为适应个体。
[0103] 在本实施例中，预先设定需要执行100次步骤S131(对种群进行100代的自然选 择）。因此在筛选步骤S130还构造有计数步骤（S134)以及计数结果判定步骤（S135)。 在每次执行步骤S131完毕后执行步骤S134,计数步骤S131的执行次数。然后执行步骤 S135,判断步骤S134的计数结果（步骤S131的执行次数）是否达到预设值（本实施例中 为100)。如果未达到预设值（100)则执行步骤 S133以及步骤S132 (遗传变异）并再次执 行步骤S131。如果达到预设值则此时的筛选结果中的个体即为适应个体。
[0104] 在步骤S131中，只通总适应度函数的值的大小筛选种群个体可能会筛选掉优秀 的种群。为了尽可能的避免上述情况，在本实施例中，步骤S131利用轮盘赌的方法进行筛 选。即在步骤S131中选择出最适应环境的个体，根据适应度函数的值，组成轮盘，采用轮盘 赌的方法，也就是适应度函数的值越大则被选中的概率越大这种方法进行选择。轮盘赌是 通过得到的适应度函数的值，给出概率，值越大，概率越大，但是也不会排除值小也能被选 中的可能。
[0105] 在本实施例中，预先设定了固定的筛选次数（自然选择代数），在本发明的另一实 施例中则是预先设定了特定的资源调度要求。即利用总适应度函数对初始种群进行筛选 后，如果筛选结果不能满足资源调度的要求，则对筛选的结果进行个体交叉和/或个体变 异以构成新的种群。然后利用总适应度函数对新生成的种群再次筛选。多次重复筛选、筛 选结果判断、交叉和/或变异过程直到最终的筛选结果满足资源调度的要求。
[0106] 对应特定的资源调度要求，筛选步骤的具体执行过程如下：
[0107] 首先在单代筛选中利用总适应度函数对初始种群中的个体进行筛选；
[0108] 然后执行筛选结果判断，基于特定的资源调度要求对单代筛选的筛选结果进行鉴 定，当单代筛选的筛选结果不符合特定的资源调度要求时针对单代筛选的筛选结果执行个 体交叉和/或个体变异以生成新的种群；
[0109] 对新的种群再次执行单代筛选以获取新的筛选结果，并对新的筛选结果再次执行 筛选结果判断；
[0110] 如此循环重复直到单代筛选的筛选结果符合特定的资源调度要求，当单代筛选的 筛选结果符合特定的资源调度要求时单代筛选的筛选结果中的个体即为适应个体。
[0111] 当筛选步骤S130完成后，最后执行步骤S140,资源调度步骤，根据最终的适应个 体对应的备选方案对云系统进行资源调度。
[0112] 下面基于一仿真实例对本发明的方法的具体效果进行描述。图3所示的是经过本 发明的方法进行资源调度后的系统个节点的负载情况。在图3中，横坐标是系统的执行时 间（单位为秒），纵坐标是每个节点的负载利用率，图标五角星、方块、圆形以及菱形分别代 表节点1、节点2、节点3以及节点4四个节点。
[0113] 由图3可以看出可以看出节点1、节点2、节点3以及节点4四个节点在整个系统 执行的过程中，其上的负载利用率都相差不大，也就是说四个节点的负载方差小，这说明了 本发明的资源调度方法能够达到负载均衡的效果。又由于迀移代价由算法中的阀值限制， 保证了较小的迀移代价。与现有技术相比，本发明的资源调度方法在实现负载均衡结果良 好的同时达到了较小的迀移代价。因此本发明是一个能够同时满足负载均衡，迀移代价小 的优化资源调度方法。
[0114] 虽然本发明所公开的实施方式如上，但所述的内容只是为了便于理解本发明而采 用的实施方式，并非用以限定本发明。本发明所述的方法还可有其他多种实施例。在不背 离本发明实质的情况下，熟悉本领域的技术人员当可根据本发明作出各种相应的改变或变 形，但这些相应的改变或变形都应属于本发明的权利要求的保护范围。
【主权项】
1. 一种用于云系统的资源调度方法，其特征在于，所述方法包括以下步骤： 种群初始化步骤，获取云系统的资源调度的备选方案，利用所述备选方案构造初始种 群，其中，所述备选方案包含节点控制器与虚拟机的分配关系，每个所述备选方案对应所述 初始种群中的一个个体； 构造适应度函数步骤，针对所述资源调度的具体需求构造总适应度函数； 种群筛选步骤，利用所述总适应度函数对所述初始种群中的个体进行筛选从而获取适 应个体； 资源调度步骤，根据所述适应个体对应的所述备选方案对所述虚拟机以及所述节点控 制器进行资源调度。2. 根据权利要求1所述的方法，其特征在于，所述种群初始化步骤包含建模步骤，对参 与所述资源调度的资源对象进行建模，所述资源对象包括所述节点控制器、所述虚拟机、所 述云系统的负载状况以及所述资源调度的迀移代价。3. 根据权利要求2所述的方法，其特征在于，在所述建模步骤中，从所述云系统中选择 特定的一个集群进行分析以获取分析结果，根据所述分析结果进行建模。4. 根据权利要求1所述的方法，其特征在于，所述种群初始化步骤包含编码步骤，对所 述备选方案进行编码。5. 根据权利要求4所述的方法，其特征在于，在所述编码步骤中，利用数组进行编码， 从而生成表示所述虚拟机与所述节点控制器的分配关系的关系数组。6. 根据权利要求1所述的方法，其特征在于，在所述种群初始化步骤中，采用轮询算法 获取所述备选方案。7. 根据权利要求1所述的方法，其特征在于，在所述种群筛选步骤中，利用轮盘赌的方 法进行筛选。8. 根据权利要求1-7中任一项所述的方法，其特征在于，在所述构造适应度函数步骤 中，根据所述云系统的负载状况以及所述资源调度的迀移代价构造所述总适应度函数，所 述总适应度函数与负载均衡以及所述迀移代价相关。9. 根据权利要求8所述的方法，其特征在于，所述构造适应度函数步骤包含以下步骤： 针对所述负载情况以及所述迀移代价分别构造负载均衡适应度函数以及迀移代价适 应度函数； 通过所述负载均衡适应度函数以及所述迀移代价适应度函数的权值的组合获取所述 总适应度函数。10. 根据权利要求1所述的方法，其特征在于，所述种群筛选步骤还包含单代筛选步 骤、个体交叉步骤和/或个体变异步骤，其中： 在所述单代筛选步骤中利用所述总适应度函数对所述初始种群中的个体进行筛选以 生成第一种群； 对所述第一种群执行所述个体交叉步骤和/或所述个体变异步骤以生成第二种群； 对所述第二种群再次执行所述单代筛选步骤以更新所述第一种群，并对更新后的所述 第一种群再次执行所述个体交叉步骤和/或所述个体变异步骤； 重复执行特定次数的所述单代筛选步骤，最终获取的更新后的所述第一种群中的个体 为所述适应个体； 在所述个体交叉步骤中基于遗传学算法按照特定的交叉概率随机选取所述第一种 群中的两个个体进行交叉以产生两个新个体从而丰富所述第一种群进而生成所述第二种 群； 在所述种群初始化步骤中基于遗传学算法按照特定的变异概率随机选取所述第一种 群中一个个体，对所述个体对应的备选方案在可取范围内进行随机变化从而产生新个体以 丰富所述第一种群进而生成所述第二种群。
【专利摘要】本发明公开了一种用于云系统的资源调度方法，所述方法包括以下步骤：种群初始化步骤，获取云系统的资源调度的备选方案，利用所述备选方案构造初始种群；构造适应度函数步骤，针对所述云系统的资源调度的具体需求构造总适应度函数；种群筛选步骤，利用所述总适应度函数对所述初始种群中的个体进行筛选从而获取适应个体；资源调度步骤，根据所述适应个体对应的所述备选方案对所述虚拟机以及所述节点控制器进行资源调度。与现有技术相比，本发明的资源调度方法可以在实现负载均衡结果良好的同时实现较小的迁移代价。
【IPC分类】G06F9/50
【公开号】CN104899100
【申请号】CN201510284673
【发明人】李小勇, 张锐
【申请人】北京邮电大学
【公开日】2015年9月9日
【申请日】2015年5月28日
【技术领域】
[0001] 本发明涉及计算机技术领域，具体说涉及一种用于云系统的资源调度方法。
【背景技术】
[0002] 云计算就是通过互联网将分布在不同数据中心的计算，存储和网络等基础设施， 以及其上的开发平台、软件和应用等以服务的形式提供给用户。由于云计算具有按需收费， 节约成本，充分利用资源等特点，使得全球进入了云计算的时代。
[0003] 云计算应用平台的资源分布广泛并且种类多样，通常云计算应用平台会根据用户 的使用需求将资源合理的分配给用户，使得整个云计算应用平台负载均衡。但是在正常使 用云计算的过程中，使用者的使用需求往往是实时变化的。随着使用云计算的用户不断增 多，面对海量的用户的需求的实时变化，云计算应用平台的负载会出现不均衡的状态，从而 造成资源浪费。并且负载不均衡也会导致局部负载过载的情况发生。
[0004] 为了解决负载不均衡的问题，需要根据云计算平台的实际使用情况对资源进行调 度。目前云计算平台的资源调度问题，通常是通过监测负载均衡日志和检测响应时间来实 现的。其资源管理算法考虑的情况相对简单，而且存在较多的负载，性能，服务质量等方面 的问题。另外，资源调度会产生迀移代价，不合理的资源调度方法不仅不能很好的解决负载 不均衡的问题而且会生成过高的迀移代价。
[0005]以在开源的软件基础结构（ElasticUtilityComputingArchitecturefor LinkingYourProgramsToUsefulSystems，Eucalyptus)上实现的云平台为例。 Eucalyptus平台采用三种独立的调度算法去解决，分别是：
[0006] (1)greedy算法：优点是简单，直接但是容易过载。
[0007] (2)roundrobin算法：优点是负载均衡了但是能源消耗高。
[0008] (3)p〇Wersave算法：优点是降低了能量消耗但是资源利用率低。
[0009] 针对负载均衡、资源利用率高、迀移代价小等标准，不能在一种调度算法中同时满 足这些目标。
[0010] 因此，针对现有云计算平台的资源调度方法存在的问题，需要一种新的资源调度 方法以达到在充分利用资源，实现负载均衡的基础上尽可能的减小迀移代价的目的。
【发明内容】
[0011] 针对现有云计算平台的资源调度方法存在的问题，本发明提供了一种用于云系统 的资源调度方法，所述方法包括以下步骤：
[0012] 种群初始化步骤，获取云系统的资源调度的备选方案，利用所述备选方案构造初 始种群，其中，所述备选方案包含节点控制器与虚拟机的分配关系，每个所述备选方案对应 所述初始种群中的一个个体；
[0013] 构造适应度函数步骤，针对所述资源调度的具体需求构造总适应度函数；
[0014] 种群筛选步骤，利用所述总适应度函数对所述初始种群中的个体进行筛选从而获 取适应个体；
[0015] 资源调度步骤，根据所述适应个体对应的所述备选方案对所述虚拟机以及所述节 点控制器进行资源调度。
[0016] 在一实施例中，所述种群初始化步骤包含建模步骤，对参与所述资源调度的资源 对象进行建模，所述资源对象包括所述节点控制器、所述虚拟机、所述云系统的负载状况以 及所述资源调度的迀移代价。
[0017] 在一实施例中，在所述建模步骤中，从所述云系统中选择特定的一个集群进行分 析以获取分析结果，根据所述分析结果进行建模。
[0018] 在一实施例中，所述种群初始化步骤包含编码步骤，对所述备选方案进行编码。
[0019] 在一实施例中，在所述编码步骤中，利用数组进行编码，从而生成表示所述虚拟机 与所述节点控制器的分配关系的关系数组。
[0020] 在一实施例中，在所述种群初始化步骤中，采用轮询算法获取所述备选方案。
[0021] 在一实施例中，在所述种群筛选步骤中，利用轮盘赌的方法进行筛选。
[0022] 在一实施例中，在所述构造适应度函数步骤中，根据所述云系统的负载状况以及 所述资源调度的迀移代价构造所述总适应度函数，所述总适应度函数与负载均衡以及所述 迀移代价相关。
[0023] 在一实施例中，所述构造适应度函数步骤包含以下步骤：
[0024] 针对所述负载情况以及所述迀移代价分别构造负载均衡适应度函数以及迀移代 价适应度函数；
[0025] 通过所述负载均衡适应度函数以及所述迀移代价适应度函数的权值的组合获取 所述总适应度函数。
[0026] 在一实施例中，所述种群筛选步骤还包含单代筛选步骤、个体交叉步骤和/或个 体变异步骤，其中：
[0027] 在所述单代筛选步骤中利用所述总适应度函数对所述初始种群中的个体进行筛 选以生成第一种群；
[0028] 对所述第一种群执行所述个体交叉步骤和/或所述个体变异步骤以生成第二种 群；
[0029] 对所述第二种群再次执行所述单代筛选步骤以更新所述第一种群，并对更新后的 所述第一种群再次执行所述个体交叉步骤和/或所述个体变异步骤；
[0030] 重复执行特定次数的所述单代筛选步骤，最终获取的更新后的所述第一种群中的 个体为所述适应个体；
[0031] 在所述个体交叉步骤中基于遗传学算法按照特定的交叉概率随机选取所述第一 种群中的两个个体进行交叉以产生两个新个体从而丰富所述第一种群进而生成所述第二 种群；
[0032] 在所述种群初始化步骤中基于遗传学算法按照特定的变异概率随机选取所述第 一种群中一个个体，对所述个体对应的备选方案在可取范围内进行随机变化从而产生新个 体以丰富所述第一种群进而生成所述第二种群。
[0033] 与现有技术相比，本发明的资源调度方法可以在实现负载均衡结果良好的同时实 现较小的迀移代价。
[0034] 本发明的其它特征或优点将在随后的说明书中阐述。并且，本发明的部分特征或 优点将通过说明书而变得显而易见，或者通过实施本发明而被了解。本发明的目的和部分 优点可通过在说明书、权利要求书以及附图中所特别指出的步骤来实现或获得。
【附图说明】
[0035] 附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实 施例共同用于解释本发明，并不构成对本发明的限制。在附图中：
[0036] 图1是根据本发明一实施例执行流程图；
[0037] 图2是根据本发明一实施例个体编码示意图；
[0038] 图3是根据本发明一实施例资源调度结果仿真图。
【具体实施方式】
[0039] 以下将结合附图及实施例来详细说明本发明的实施方式，借此本发明的实施人员 可以充分理解本发明如何应用技术手段来解决技术问题，并达成技术效果的实现过程并依 据上述实现过程具体实施本发明。需要说明的是，只要不构成冲突，本发明中的各个实施 例以及各实施例中的各个特征可以相互结合，所形成的技术方案均在本发明的保护范围之 内。
[0040] 云计算就是通过互联网将分布在不同数据中心的计算，存储和网络等基础设施， 以及其上的开发平台、软件和应用等以服务的形式提供给用户。在正常使用云计算的过程 中，面对海量的用户的需求的实时变化，云计算应用平台的 负载会出现不均衡的状态，从而 造成资源浪费。并且负载不均衡也会导致局部负载过载的情况发生。
[0041] 为了解决负载不均衡的问题，需要根据云计算平台的实际使用情况对资源进行调 度。目前云计算平台的资源调度问题，通常是通过监测负载均衡日志和检测响应时间来实 现的。其资源管理算法考虑的情况相对简单，而且存在较多的负载，性能，服务质量等方面 的问题。另外，资源调度会产生迀移代价，不合理的资源调度方法不仅不能很好的解决负载 不均衡的问题而且会生成过高的迀移代价。
[0042] 以在开源的软件基础结构（ElasticUtilityComputingArchitecturefor LinkingYourProgramsToUsefulSystems，Eucalyptus)上实现的云平台为例。 Eucalyptus平台采用三种独立的调度算法去解决，分别是：
[0043] (1)greedy算法：优点是简单，直接但是容易过载。
[0044] (2)roundrobin算法：优点是负载均衡了但是能源消耗高。
[0045] (3)p〇Wersave算法：优点是降低了能量消耗但是资源利用率低。
[0046] 针对负载均衡、资源利用率、迀移代价小等标准，不能在一种调度算法中同时满足 这些目标。
[0047] 因此，针对现有云计算平台的资源调度问题，本法命题出了一种用于云系统的资 源调度方法。本发明首先改进了遗传算法，然后将改进后的遗传算法应用于云计算平台的 资源调度。根据不同的目标在遗传算法中设计不同的目标函数和阈值，利用遗传算法求得 全局最优解的特性，实现在该算法中同时满足对云资源调度的多种标准要求，从而解决了 现有调度算法中无法同时满足负载均衡，高资源利用率，迀移代价小的问题。
[0048] 接下来基于流程图来详细描述本发明的资源调度方法的具体执行过程，附图的流 程图中示出的步骤可以在包含诸如一组计算机可执行指令的计算机系统中执行。虽然在流 程图中示出了各步骤的逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示 出或描述的步骤。
[0049] 遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的 计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能 潜在的解集的一个种群开始，种群中的每个个体都是问题的一种可能的解决方案。根据具 体的解决问题的需求设定外在环境，通过环境适应度筛选种群中的个体，从而获取最适应 外在环境的个体，即最适应解决问题的需求的解决方案。
[0050] 本发明的方法主要是利用遗传算法获取最优的资源调度方案，因此首先要构建用 于遗传算法筛选的初始种群。在本实施例中，如图1所示，首先要执行步骤S110,种群初始 化步骤，获取用于筛选最优资源调度方案的初始种群。初始种群包含进行资源调度的多个 可能的解决方案，即初始种群中的每一个个体都是针对云系统的资源调度的备选方案。云 系统的资源调度主要是在各个虚拟机以及节点控制器之间分配资源，因此，每个云系统的 资源调度的备选方案均包含节点控制器、虚拟机以及节点控制器与虚拟机的分配关系，每 个备选方案对应初始种群中的一个个体
[0051] 在使用遗传算法获取最优的资源调度方案之前，为了便于算法的顺利执行，首先 要将与资源调度有关的研宄对象数字化。在本实施例中，首先执行步骤111，建模步骤，对 云系统中参与资源调度的资源对象进行建模。由于云系统的资源调度主要是在各个虚拟 机以及节点控制器之间分配资源，因此需要执行建模的资源对象包括节点控制器以及虚拟 机。另外，由于本实施例中进行资源调度的目的是实现负载均衡，因此需要执行建模的资源 对象还包括云系统的负载情况。最后，本实施例的方法还要尽可能的达到最小迀移代价，因 此需要执行建模的资源对象还包括迀移代价。
[0052] 进行建模就需要对整个云系统中的所有建模对象进行分析。考虑到云系统中包含 多个集群（多个集群控制器），而资源调度的执行是在每个集群中执行的。而本发明的研 宄对象是一个集群控制器下的多个节点，每个节点控制器下多个虚拟机。因此为了简化流 程，降低建模复杂程度，本实施例在所述建模步骤中，从云系统中选择特定的一个集群进行 分析以获取分析结果，从而根据分析结果进行建模。
[0053] 具体建模如下：
[0054] (1)虚拟机和节点控制器：对于一个集群控制器（ClusterController，CC) 下的多个节点控制器（NodeController，NC)以及虚拟机（VirtualManufacturing， VM)，用NQ，NC2,NC3,......NQ来表示第一个节点，第二个节点……第i个节点；用 VM〇,VM2,......表示第1个虚拟机，第2个虚拟机……第j+1个虚拟机。
[0055] (2)负载情况：为了表示出负载，需要选取一个时间周期T记录这个时间段内的平 均负载，并选取cpu利用率（ratio(cpu))、内存（memeory)、网络流量（Net)三者由不同权 值（A、B、C)组合成一个节点控制器NC上的负载总值（Load)，如下式1所示：
[0056]Load=A*ratio(cpu)+B*memeory+C*Net(1)〇
[0057] 所以第j个VM的平均负载（)就是
[0059]则每个节点控制器总负载
[0061]也就是说在T周期内，所有在该节点上的虚拟机负载的综合是该节点的总负
[0062]载。所以每个节点控制器的资源负载比为
[0064] 其中&表示第i个节点控制器的能力（节点控制器的容量，即最大能容纳多少的 负载）。
[0065] (3)迀移代价：由于在资源调度中需要对虚拟机部署做适度的调整，所以存在需 要虚拟机迀移的情况。以M'表示需要迀移的虚拟机，M表示总的虚拟机。由于算法中的种 群就是不同的虚拟机被分配到不同节点的方案的集合。则定义在实施方案后需要迀移的虚 拟机数目为迀移代价。迀移代价C为
[0067]在遗传算法中，一个种群是由经过基因编码的一定数目的个体组成。每个个体实 际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内 部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是 由染色体中控制这一特征的某种基因组合决定的。
[0068] 因此在使用遗传算法时，在一开始需要实现从表现型到基因型的映射即编码工 作。在本实施例中，为配合遗传算法，如图1所示，要执行步骤S112,编码步骤，对构成初始 种群的个体（备选方案）进行编码。即针对虚拟机、节点控制器、虚拟机与节点控制器的分 配关系进行编码。
[0069]由于仿照基因编码的工作很复杂，通常会进行简化，利用二进制编码进行编码。但 是二进制编码不适合描述本实施例中的备选方案。因此为了方便计算，减少资源调度的执 行难度，本实施例采用数组进行编码。根据Eucalyptus云平台资源调度情况，将数组的值 作为节点的序列号，将数组数值所在的位置作为虚拟机的序列号。这样最后生成的备选方 案就包含虚拟机与节点控制器的关系数组。
[0070]在本实施例中，染色体是以整数数组的形式表示，并且数组中每个元素的位置代 表虚拟机的序列号，每个元素的值为节点控制器的序列号。如图2所示，虚线框200内表 示 的是一具体的虚拟机部署方案：第〇号虚拟机被部署在第5号节点上运行，第1号虚拟机被 部署在第9号节点上运行，第2号虚拟机也被部署在第5号虚拟机上运行，第3号虚拟机被 部署在第1号节点上运行，第4号虚拟机被部署在第3号节点上运行。则部署方案200就 可以表示为数组201 (5,9, 5,1，3)。
[0071] 建模后就可以利用备选方案构造初始种群，即获取构成初始种群的各个个体。由 于在本实施例中，初始种群的每个个体对应的是云系统资源调度的备选方案。因此此时执 行步骤S112,获取备选方案步骤。本发明的目的是从多个备选方案（初始种群）中筛选出 最适合的方案（个体）。因此。初始种群的丰富程度（个体数目/带筛选的备选方案的丰 富程度）以及整体负载均衡程度越高，最后获取的筛选结果也越好。
[0072] 为了尽可能多的获取备选方案，丰富初始种群，均衡整体的负载程度在编码的基 础上，本实施例采用了采用轮询算法对种群进行初始，也就是经过轮询算法后形成的虚拟 机与节点控制器的关系数组为最初的种群。这样不仅达到了丰富初始种群的目的而且还使 初始化的种群先达到整体的负载均衡情况。
[0073] 在本实施例中，采用轮询算法将一定数量的虚拟机分配给合适的节点控制器。构 造一个数组集合作为初始种群。数组集合中的每一个数组代表一种虚拟机部署方案（虚拟 机与节点控制器的关系数组）（见图2所示的具体例子）。
[0074] 初始种群产生之后，就可以按照适者生存和优胜劣汰的原理，根据个体对环境的 适应程度进行筛选以获取最适合环境的个体（问题的最优解）。这里首先要构造用于筛选 的环境，具体到本实施例，就是要执行步骤S120,构造适应度函数步骤，针对云系统的资源 调度的具体需求构造总适应度函数（用于筛选的环境）。
[0075] 由于本实施例中进行资源调度的目的是实现负载均衡并尽可能的达到最小迀移 代价，因此在步骤S120中，根据云系统的负载情况以及迀移代价构造总适应度函数，使得 总适应度函数与负载均衡以及迀移代价相关。
[0076] 由于总适应度函数有多个目标，那么首先就要设定多个目标函数。即首先针对负 载情况以及迀移代价分别构造负载均衡适应度函数以及迀移代价适应度函数；然后通过负 载均衡适应度函数以及迀移代价适应度函数的权值的组合获取总适应度函数。其中，采用 每个节点利用率与平均资源利用率的方差来表示负载均衡情况，用需要迀移的虚拟机与总 虚拟机的比值作为迀移代价。
[0077] 具体执行如下：
[0078] 首先是负载均衡适应度函数：假设总共有i个节点，现有的虚拟机总数为j+1，根 据当前系统的具体要求设定节点的资源利用率的阀值为R〇,迀移代价的阀值为CJ设定迀 移代价的阀值可使迀移代价控制在较小的范围内）。根据上面过程中建立的模型（式1-式 5)最终负载均衡的适应度函数为：
[0079] R^R0 (6)
[0083] 其中：氏为每个节点控制器的资源负载比（见式4);
[0084] 云为系统中所有节点的平均资源利用率；
[0085] Sn为方差，即每个节点的资源利用率与平均资源利用率的差值，用来表示负载是 否均衡。
[0086] 迀移代价的适应度函数为：
[0088] 其中：M'表示需要迀移的虚拟机，M表示总的虚拟机，Q表示每种方案下的迀移代 价，Q表示迀移代价的阀值（见式5)。
[0089] 由于每个方案下，都有各自的迀移代价和负载方差。分别设定迀移代价和负载方 差的权值V和W，V+W= 1。这样总的适应度函数取决于这两个方面因素，方差越小越好，迀 移代价越小越好。选其倒数，这样方差和迀移代价越小的方案，适应度函数的值越大，在下 一步的轮盘赌步骤下被选中的概率也就越大，优秀个体就越易被保存下来。则最终的适应 度函数？"是迀移代价与负载均衡的适应度函数的结合
[0091] 接下来就可以执行步骤S130,筛选步骤，利用总适应度函数（环境）对初始种群中 的个体进行筛选从而获取适应个体（最适应环境的个体）。
[0092] 然而在自然界中，一个种群不是一成不变的，个体会逐代演化产生出越来越适应 环境的个体（更加接近问题完美解决方案的近似解）。遗传算法模拟了上一过程，在每一 代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合 交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代 种群比前代更加适应于环境，这样末代种群中的最优个体就可以作为问题近似最优解。
[0093] 本发明将上述原理改进后应用到了资源调度备选方案的筛选上。即利用总适应度 函数对初始种群进行筛选（自然选择中的一代选择），在筛选之后对筛选的结果进行个体 交叉和/或个体变异以构成新的种群（自然选择中的每一代个体的遗传变异）。然后利用 总适应度函数对新生成的种群再次筛选。多次重复筛选、交叉和/或变异过程（自然选择 中对物种的多代选择）直到完成特定次数的筛选。
[0094] 具体到本实施例则是在筛选步骤S130构造了单代筛选步骤（S131)、个体变异步 骤（S132)以及个体交叉步骤（S133)。
[0095] 步骤S133是基于遗传学算法按照特定的交叉概率随机选取目标种群中的两个个 体进行交叉以产生两个新个体从而丰富目标种群进而生成新的种群。在传统的遗传算法 中，交叉概率的范围是0. 6到0. 95。在本发明中采用单点交叉，交叉点为数组中的某个位置 上的数据值，也就是在该位置上所分配的节点的改变。因此在本实施例中，特定的交叉概率 为 0? 7〇
[0096] 步骤S132是基于遗传学算法按照特定的变异概率随机选取目标种群中的一个个 体，对个体对应的备选方案在可取范围内进行随机变化从而产生新个体以丰富目标种群进 而生成新的种群。对于遗传算法，变异概率的范围是0.01到0.03。当一个个体被选中时， 也就是选中一个数组，则这个数组中某个位置的值会随机的变成1~i中的一个数值。其 中1~i是所有节点的序列号。在本实施例中，特定的变异概率为〇. 02。
[0097] 同时，由于本实施例的备选方案包含虚拟机与节点控制器的关系数组，因此在步 骤S132中，随机选取个体后，对数组中的某个数值位置的值随机变成在可取范围内的某个 节点的序列号以生成新的数组（个体）。
[0098] 筛选步骤S130的具体执行过程如下：
[0099] 首先在步骤S131中利用总适应度函数对初始种群中的个体进行筛选；
[0100] 然后针对步骤S131的筛选结果执行步骤S132和步骤S133以生成新的种群；
[0101] 对新的种群再次执行步骤S131以获取新的筛选结果；
[0102] 如此循环重复直到执行特定次数的步骤S131，此时步骤S131的筛选结果中的个 体即为适应个体。
[0103] 在本实施例中，预先设定需要执行100次步骤S131(对种群进行100代的自然选 择）。因此在筛选步骤S130还构造有计数步骤（S134)以及计数结果判定步骤（S135)。 在每次执行步骤S131完毕后执行步骤S134,计数步骤S131的执行次数。然后执行步骤 S135,判断步骤S134的计数结果（步骤S131的执行次数）是否达到预设值（本实施例中 为100)。如果未达到预设值（100)则执行步骤 S133以及步骤S132 (遗传变异）并再次执 行步骤S131。如果达到预设值则此时的筛选结果中的个体即为适应个体。
[0104] 在步骤S131中，只通总适应度函数的值的大小筛选种群个体可能会筛选掉优秀 的种群。为了尽可能的避免上述情况，在本实施例中，步骤S131利用轮盘赌的方法进行筛 选。即在步骤S131中选择出最适应环境的个体，根据适应度函数的值，组成轮盘，采用轮盘 赌的方法，也就是适应度函数的值越大则被选中的概率越大这种方法进行选择。轮盘赌是 通过得到的适应度函数的值，给出概率，值越大，概率越大，但是也不会排除值小也能被选 中的可能。
[0105] 在本实施例中，预先设定了固定的筛选次数（自然选择代数），在本发明的另一实 施例中则是预先设定了特定的资源调度要求。即利用总适应度函数对初始种群进行筛选 后，如果筛选结果不能满足资源调度的要求，则对筛选的结果进行个体交叉和/或个体变 异以构成新的种群。然后利用总适应度函数对新生成的种群再次筛选。多次重复筛选、筛 选结果判断、交叉和/或变异过程直到最终的筛选结果满足资源调度的要求。
[0106] 对应特定的资源调度要求，筛选步骤的具体执行过程如下：
[0107] 首先在单代筛选中利用总适应度函数对初始种群中的个体进行筛选；
[0108] 然后执行筛选结果判断，基于特定的资源调度要求对单代筛选的筛选结果进行鉴 定，当单代筛选的筛选结果不符合特定的资源调度要求时针对单代筛选的筛选结果执行个 体交叉和/或个体变异以生成新的种群；
[0109] 对新的种群再次执行单代筛选以获取新的筛选结果，并对新的筛选结果再次执行 筛选结果判断；
[0110] 如此循环重复直到单代筛选的筛选结果符合特定的资源调度要求，当单代筛选的 筛选结果符合特定的资源调度要求时单代筛选的筛选结果中的个体即为适应个体。
[0111] 当筛选步骤S130完成后，最后执行步骤S140,资源调度步骤，根据最终的适应个 体对应的备选方案对云系统进行资源调度。
[0112] 下面基于一仿真实例对本发明的方法的具体效果进行描述。图3所示的是经过本 发明的方法进行资源调度后的系统个节点的负载情况。在图3中，横坐标是系统的执行时 间（单位为秒），纵坐标是每个节点的负载利用率，图标五角星、方块、圆形以及菱形分别代 表节点1、节点2、节点3以及节点4四个节点。
[0113] 由图3可以看出可以看出节点1、节点2、节点3以及节点4四个节点在整个系统 执行的过程中，其上的负载利用率都相差不大，也就是说四个节点的负载方差小，这说明了 本发明的资源调度方法能够达到负载均衡的效果。又由于迀移代价由算法中的阀值限制， 保证了较小的迀移代价。与现有技术相比，本发明的资源调度方法在实现负载均衡结果良 好的同时达到了较小的迀移代价。因此本发明是一个能够同时满足负载均衡，迀移代价小 的优化资源调度方法。
[0114] 虽然本发明所公开的实施方式如上，但所述的内容只是为了便于理解本发明而采 用的实施方式，并非用以限定本发明。本发明所述的方法还可有其他多种实施例。在不背 离本发明实质的情况下，熟悉本领域的技术人员当可根据本发明作出各种相应的改变或变 形，但这些相应的改变或变形都应属于本发明的权利要求的保护范围。
【主权项】
1. 一种用于云系统的资源调度方法，其特征在于，所述方法包括以下步骤： 种群初始化步骤，获取云系统的资源调度的备选方案，利用所述备选方案构造初始种 群，其中，所述备选方案包含节点控制器与虚拟机的分配关系，每个所述备选方案对应所述 初始种群中的一个个体； 构造适应度函数步骤，针对所述资源调度的具体需求构造总适应度函数； 种群筛选步骤，利用所述总适应度函数对所述初始种群中的个体进行筛选从而获取适 应个体； 资源调度步骤，根据所述适应个体对应的所述备选方案对所述虚拟机以及所述节点控 制器进行资源调度。2. 根据权利要求1所述的方法，其特征在于，所述种群初始化步骤包含建模步骤，对参 与所述资源调度的资源对象进行建模，所述资源对象包括所述节点控制器、所述虚拟机、所 述云系统的负载状况以及所述资源调度的迀移代价。3. 根据权利要求2所述的方法，其特征在于，在所述建模步骤中，从所述云系统中选择 特定的一个集群进行分析以获取分析结果，根据所述分析结果进行建模。4. 根据权利要求1所述的方法，其特征在于，所述种群初始化步骤包含编码步骤，对所 述备选方案进行编码。5. 根据权利要求4所述的方法，其特征在于，在所述编码步骤中，利用数组进行编码， 从而生成表示所述虚拟机与所述节点控制器的分配关系的关系数组。6. 根据权利要求1所述的方法，其特征在于，在所述种群初始化步骤中，采用轮询算法 获取所述备选方案。7. 根据权利要求1所述的方法，其特征在于，在所述种群筛选步骤中，利用轮盘赌的方 法进行筛选。8. 根据权利要求1-7中任一项所述的方法，其特征在于，在所述构造适应度函数步骤 中，根据所述云系统的负载状况以及所述资源调度的迀移代价构造所述总适应度函数，所 述总适应度函数与负载均衡以及所述迀移代价相关。9. 根据权利要求8所述的方法，其特征在于，所述构造适应度函数步骤包含以下步骤： 针对所述负载情况以及所述迀移代价分别构造负载均衡适应度函数以及迀移代价适 应度函数； 通过所述负载均衡适应度函数以及所述迀移代价适应度函数的权值的组合获取所述 总适应度函数。10. 根据权利要求1所述的方法，其特征在于，所述种群筛选步骤还包含单代筛选步 骤、个体交叉步骤和/或个体变异步骤，其中： 在所述单代筛选步骤中利用所述总适应度函数对所述初始种群中的个体进行筛选以 生成第一种群； 对所述第一种群执行所述个体交叉步骤和/或所述个体变异步骤以生成第二种群； 对所述第二种群再次执行所述单代筛选步骤以更新所述第一种群，并对更新后的所述 第一种群再次执行所述个体交叉步骤和/或所述个体变异步骤； 重复执行特定次数的所述单代筛选步骤，最终获取的更新后的所述第一种群中的个体 为所述适应个体； 在所述个体交叉步骤中基于遗传学算法按照特定的交叉概率随机选取所述第一种 群中的两个个体进行交叉以产生两个新个体从而丰富所述第一种群进而生成所述第二种 群； 在所述种群初始化步骤中基于遗传学算法按照特定的变异概率随机选取所述第一种 群中一个个体，对所述个体对应的备选方案在可取范围内进行随机变化从而产生新个体以 丰富所述第一种群进而生成所述第二种群。
【专利摘要】本发明公开了一种用于云系统的资源调度方法，所述方法包括以下步骤：种群初始化步骤，获取云系统的资源调度的备选方案，利用所述备选方案构造初始种群；构造适应度函数步骤，针对所述云系统的资源调度的具体需求构造总适应度函数；种群筛选步骤，利用所述总适应度函数对所述初始种群中的个体进行筛选从而获取适应个体；资源调度步骤，根据所述适应个体对应的所述备选方案对所述虚拟机以及所述节点控制器进行资源调度。与现有技术相比，本发明的资源调度方法可以在实现负载均衡结果良好的同时实现较小的迁移代价。
【IPC分类】G06F9/50
【公开号】CN104899100
【申请号】CN201510284673
【发明人】李小勇, 张锐
【申请人】北京邮电大学
【公开日】2015年9月9日
【申请日】2015年5月28日
最新回复(0)