一种基于组合优化的虚拟机调度方法

摘要

本发明公开了一种基于组合优化的虚拟机调度方法，该方法可用于虚拟集群中实时的虚拟机调度决策，能够根据虚拟集群当前的资源使用情况实时地决策虚拟机的开启位置，使得被占用的物理主机的数量最小，这样既可以提高资源利用率又可以减少能源的消耗。本发明所涉及的虚拟机调度方法采用简单的数学计算，可在有限次比较次数内获得调度结果，比较次数与虚拟机种类以及物理主机种类有关。与传统解决组合优化问题时所采用的人工智能算法相比，本发明所涉及的虚拟机调度方法具有较高的实时性，可以实时决策出虚拟机的放置位置，满足对虚拟机调度系统高实时性的要求。

主权项

一种基于组合优化的虚拟机调度方法，其特征在于，包括以下步骤：1)集群状态建模1.1)统计集群中资源种类数量N，并为每种资源编号，依次为1～N；1.2)统计集群中物理主机的资源向量，每一台物理主机均提供N种资源供运行在该主机上的多台虚拟机共享；1.3)对虚拟机进行分类，统计虚拟机的种类总数I，并为每一种虚拟机类型进行编号，依次为1～I；1.4)统计每种虚拟机对资源的请求，每种虚拟机对资源的请求均为一个N维的向量，与物理主机的资源向量对应；1.5)计算物理主机能够同时运行的虚拟机的组合种类，使用一个I维的向量k表示物理主机的负载情况；1.6)将集群中的物理主机按资源配置向量分类，统计各种资源配置物理主机的数量；其中，资源配置为k的物理主机的数量为X_k；所有X_k组成一个|K|维的向量X，X为集群状态向量；2)虚拟机调度2.1)解析虚拟机请求，获得虚拟机所属的种类编号i；2.2)构造一个权重函数：$w^r\left(X\right)=\min (1,\frac{X}{r^p})$其中r为系统中虚拟机的总数，p为一常数且p∈(1/2，1)；w^r(X)的反导函数为：$f^r\left(X\right)=\left\{\begin{array}{c}\frac{X^2}{{2r}^p},\mathrm{ifX}\in [0,r^p];\\ X-\frac{r^p}{2},\mathrm{ifX}>r^p.\end{array}\right.$定义近似函数F^r(X)＝∑_k∈Kf^r(X_k)，近似地表示物理主机的数量总和∑_k∈KX_k；2.3)k为集合K中的元素，集群中资源配置向量为k的物理主机数量为X_k；向量e_i也是一个资源配置向量，是集合K中的单位向量，表示仅有一台类型为i的虚拟机；向量k‑e_i与向量k的分别表示物理主机在虚拟机实例开启前后的资源配置向量；集群中资源配置向量为k‑e_i的物理主机的数量为定义一个权重差来表示F^r(X)的一阶变化量，其中：${\Delta }_{(k,i)}^r\left(X\right)=w^r\left(X_k\right)-w^r\left(X_{k-e_i}\right)$w^r(X_k)为集群状态X_k的权重函数，为集群状态的权重函数，X_k和分别为调度操作前后的集群状态；2.4)选取最小的值对应的k‑e_i值作为目标资源配置；为F^r(X)的一阶变化量，近似的表示虚拟机调度前后集群中物理主机数量的变化；2.5)在资源配置为k‑e_i的物理主机中选取一台作为目标主机，在该主机上创建虚拟机实例。