基于OpenStack云计算的资源调度算法研究

朱建宇

1 引言

随着计算机的快速发展和广泛使用，计算机数据变得越来越复杂，规模越来越庞大。

为了处理大规模的数据和应用，计算机数据做出各种正确的行为指导，云计算应运而生。云计算是一种在分布式计算，并行计算，网格计算的基础上发展形成的一种计算模式。目前，从国内国外的研究现状来看，谷歌、微软、亚马逊、IBM等巨型IT公司纷纷在全球建立数据中心，研发和应用云计算，并形成了相对成熟稳定的云计算平台。同时，均将云计算作为发展的重要战略之一[1]。同样，诸如Facebook，苹果等其他大型公司及部分中小型企业也开始加大对云计算的投资力度，实现云计算的各领域的落地服务。在国内，以阿里云为首，腾讯云，华为云，百度云等几十家互联网企业。都对云计算进行了巨额投资和研发，并实现了初步的商用目的。国内的大型央企，国企，政府机构，都已经建立了各自的云计算平台，为自己的单位建立了相对完善的私有云平台。

云计算利用了虚拟化技术将物理资源虚拟成为软件资源，形成了多种资源池，这样可以提供按需交付、灵活弹性、集中规模、自由调度、安全管理等多种功能。适应了当代企业和用户对大规模数据计算，复杂逻辑处理的迫切要求。由于很多科学研究、项目需求对云计算的资源有各种各样的要求，包括计算资源，网络资源，存储资源。研究高效灵活的云计算相关技术任重道远，满足各种使用需求具有非常重要的价值和意义。

OpenStack是IaaS的重要组件，OpenStack的作用是创建虚拟机需要各种服务的交互和配合工作。OpenStack支持几乎所有类型的云环境，项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenStack通过各种互补的服务提供了基础设施即服务的解决方案，每个服务提供API以进行集成。目前OpenStack开发速度非常快，社区也很活跃，国内外的很多企业、研究机构、学校、组织都踊跃参与和贡献OpenStack的开发和修复工作，发展非常顺利。

用户在使用云计算服务的过程中，更为关注可靠性、效率、成本。基于上述指标提出QoS(quality of service)服务质量。为了最大程度满足QoS的需求，提高用户满意度，云计算需要在资源分配环节从用户角度考虑，实现资源调度的合理化、自由化、准确化。因此，资源调度和资源方向是云计算的重要研究方向。

为了保障QoS，提高资源利用率，必须解决好云计算中的资源调度问题，随着仿生学的发展，人们开始关注遗传算法，并将遗传算法应用到云计算当中，提高了资源调度的智能性。

但是，传统的遗传算法具有局部收敛的问题。只能得到局部最优解，因此，针对上述问题，本文提出基于OpenStack云计算的资源调度改进遗传算法，提高了可靠性，满足了资源利用最大化，更好的发挥了遗传算法的智能性作用。

2 OpenStack云计算理论基础及传统调度算法

2.1 云计算

云计算是一种可以提供按需收费，能够弹性伸缩的一种新型的计算模式。正所谓弹性可伸缩，即资源分配和部署可以根据用户的需求时时的改动。云计算的这种资源使用模式，为用户通过网络提供访问计算资源的可能。比如存储，应用服务，软件程序等。从用户角度来讲，云计算有以下特征：（1）按需服务，云计算可以为用户快速提供可用资源可用服务，并且能够根据用户的需求对资源进行使用，释放，这样，云服务商可以根据用户需求调度各种云资源；（2）资源池，云计算通过虚拟化技术将存入资源进行虚拟并组成资源池，让多个用户根据需求共同利用资源池中的资源[2]；（3）弹性伸缩，云服务商可以根据用户的需求,快速的，弹性的分配，释放，回收资源，这对于用户而言，代表资源是无限的，任何需求都能够及时得到满足；（4）按需付费，按需服务的基本眼球要求按需付费，云计算商按照用户是使用的资源进行按量计费，满足了用户的需求，当然，这些资源也是虚拟抽象出来的资源，比如CPU，内存，硬盘，带宽等。

2.2 虚拟化技术

虚拟化技术是云计算IaaS层核心组成部分，虚拟化也可以理解为对物理资源的抽象化。其本质是隔离了软件和硬件的一种中间件技术，将物理底层进行屏蔽，并为上层提供统一的接口服务。虚拟化的对象可以划分为服务器的虚拟化，网络的虚拟化，存储的虚拟化等多种不同形式。本文的资源调度主要针对的是服务器的虚拟化。服务器虚拟化是把一台服务器抽象成为多台服务器，这样一台物理主机就可以变成多台虚拟机，并且多台虚拟机是互相独立的，是完全隔离的。这样保证了虚拟机的安全性与可靠性。服务器虚拟化主要是将物理的CPU，内存，硬盘，网络设备，I/O接口等资源进行抽象。其中CPU虚拟化会将物理的CPU虚化成多个虚拟的CPU。这样，多个虚拟的CPU可以提高物理CPU的利用率。内存虚拟化将物理内存抽象成多个虚拟内存，内存空间完全隔离;网络设备和I/O接口虚拟化，就是将真实的物理设备抽象为多个虚拟设备，为多台虚拟机进行I/O请求，提供服务[3]。

目前，较为流行的虚拟化管理软件有KVM，Xen，vSphere，本文研究的OpenStack云计算对KVM提供很好的支持。KVM是基于Linux内核对虚拟机进行管理的，所以它要求底层硬件必须都支持虚拟化。

2.3 传统遗传算法

遗传算法按照自然界的生存法则，将具体问题抽象化，把需要解决的问题虚拟成为染色体，接着把这些染色体进行选择，交叉和变异，直到得到目标最优解[4]。具体的算法过程按照以下描述，随机产生初始化种群后，通过不断地的选择，交叉，变异来优化，调度，扩大下一代种群搜索空间。并利用适应度函数对已经编码的种群进行优胜劣汰，留下适应度较高的个体，淘汰掉适应度较低的个体。筛选完个体之后，由新的个体产生新的种群。

3 改进资源调度遗传算法

3.1 改进资源调度遗传算法

传统的遗传算法，采用0，1的编码方式对染色体完成编码，但是资源调度的问题是有不同的分配方案的，需要明确每一个任务在每一个资源节点执行，传统的编码方式不能覆盖全部信息。本文采用一种间接编码方式，规定任务的数量就是染色体的长度。染色体的每一位表示一个任务，对应一个资源。比如染色体（3，5，2，6，8，7）表示染色体长度是6，需要执行6个任务，第一个任务被分配到节点3，第二个任务被分配到节点5，以此类推。

3.2 适应度函数

适应度函数表示个体被度量的函数，用来计算个体被选中的概率。适应度越大，个体越好，被选中概率越大，保证特性得到遗传。适应度函数的选择能够决定是否可以得到最优解，所以选择合适的是适应度函数非常重要。

满足用户QoS的需求有四个指标，分别是时间、可用性、成本、安全性。这四项指标能够满足用户的需求，决定最优解。目标函数值越大，代表优化效果越好，也代表算法性能高。因此本文选用目标函数的平方当做适应度函数。QoS四项指标按照权重系数来影响适应度函数。权重系数由资源的刚性和弹性偏好决定。也可以根据用户自身需求进行调节。

3.3 改进遗传算法操作过程

遗传算法主要有三部分组成，选择，交叉，变异。这三个部分直接影响到遗传操作的效果。

（1）选择

选择是为了通过对当代种群的筛选，利用适应度函数对个体进行评价，完成对种群的不断优化。因为适应度函数的大小决定了个体被筛选的概率，所以可以将优良的个体通过评价筛选后遗传到下一代。本文采用的选择方法是赌轮选择法。当个体的适应度值比较大的时候，被选择的可能性也越大。

（2）交叉

交叉算子可以使我们的搜索空间扩大，是遗传算法中的基因重组，具有核心作用[5]。交叉是指两个父体结构进行替换，重新生成两个新个体。交叉概率的选取非常重要，取值偏大会导致良好的结构被破坏，取值偏小会影响个体的产生速度。本文设施了一种自适应方式，避免交叉概率偏大或者偏小。调整公式1如下：

favg代表种群的品均适应度，fmax代表种群最大的适应度，f代表交叉双方适应值比较大的一方。k1和k2在（0，1）之间取值，从公式中可以看出，个体适应度值接近最大适应度值的时候，交叉概率就小，而当适应度值和最大适应读值相等的时候，交叉概率等于0。

（3）变异

变异可以为算法找到最优解提供条件，可以丰富种群的多样性。变异操作可以使算法向着最优解的方向收敛。并且保持多样性，变异概率设置太大，不会加速寻找最优解，反而会破坏变异基因位。本文设计了一种自适应的方式选取变异概率。调整公式2如下：

其中，favg代表种群的品均适应，fmax代表种群最大的适应度，代表变异双方适应值比较大的一方。k3和k4在（0，1）之间取值。从公式中可以看出，当变异个体的适应值接近最大的适应值的时候，变异概率就小，而适应度值与最大适应读值相同的时候，变异概率等于0。

综上所述，本文的交叉算法有更强的全局搜索能力，而本文的变异算法可以提高局部的搜索能力。通过选择交叉变异三种操作，遗传算法可以扩大全局搜索范围，提高局部搜索能力，使得问题可以加速并保证精准的寻求和接近最优解。

4 总结

本文研究了云计算，OpenStack的基本原理和核心技术，对传统的遗传算法进行了深入学习和实验。提出了一套可以改进资源调度效果的遗传算法，能够实现在满足QoS的情况下，降低成本，提高资源利用率。