基于能效管理的云计算资源调度模型及算法(4)
例3.仍然考虑和上面一样的情形。在这个例子中，展示了一个更好的布局，让服务器1包含工作J1所有的虚拟机，服务器2包含工作J2,J3所有的虚拟机，这样的空间布局和时间布局都更好一些，如图1.c所示。这样服务器总共的工作时间为110分钟。
上面这些例子说明了对MapReduce任务来说，在获得能效时有一个时空权衡。如果把运行时间差别不是很大的虚拟机放置到同一台物理机上，这样当物理机上所有的虚拟机都运行结束的时候，就可以将物理机关闭以节省更多的电能。因此在本文中首先根据虚拟机运行时间将它们分成组，然后在每一个组内，再对虚拟机按照空间优化算法进行布置。
server1 server2 server1 server2 server3 server1 server2
图1
3.3 虚拟机分组
对每个虚拟机都记录的有运行时间，所以可以根据运行时间进行分组。本文将运行时间相同的分成一组。其中运行时间数组为vm_runtime，数组大小为n。
Step1：i=0；
Step2：依次判断虚拟机集合vmsets中的每一个虚拟机的运行时间是否等于vm_runtime[i]，如果等于则将其加入虚拟机集合vmset_i；
Step3：如果i<n，则i++，并跳转到Step2；否则，结束。
3.4 虚拟机映射
在组内采用遗传算法进行虚拟机映射。遗传算法把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
3.4.1 种群初始化
对于给定的虚拟机集合，首先调整给定的虚拟机序列，采用最佳适应算法进行放置，得到一种放置方案，然后再调整给定的虚拟机序列，再采用最佳适应算法进行放置，这样就得到另一种映射方案，如此反复调整虚拟机序列，放置虚拟机，我们就得到了n种映射方案，即初始种群的n个个体（其中每一个映射方案就是一个个体）。
Step1：新建一个虚拟机集合，用于保存调整原有虚拟机集合序列之后的虚拟机集合；
Step2：i =0；
while（虚拟机序列不为空）
{ 随机生成一个整数j，取值范围为（0，虚拟机个数-1）；
将原有虚拟机集合中第j个虚拟机放置到新虚拟机集合第i个位置；
将原有虚拟机集合中第j个虚拟机删除；
i++；
}
Step3：采用最佳适应算法对新虚拟机集合进行放置，得到一种放置方案，并将其保存到虚拟机装箱集合bin中；
Step4：判断是否生成了n个个体，如果生成了n个个体，则结束；否则跳转到Step1。
3.4.2 选择算子设计
根据每个个体的能耗Ei得到它们在这n个个体总能耗Etotal的比值（能耗越小，比值越大），并采用轮盘赌算法从中选取100个较优秀的个体（比值大的方案被选中的可能性更高）。
Step1：//设置每一个个体所对应的概率p[i]
i=0；
while（i！=n）
{ if（i=0）