CloudSim中基于偏序关系的调度算法研究

熊 磊， 陈宏伟， 王淑平

(湖北工业大学计算机学院， 湖北 武汉 430068)

云计算是一个以经济模式为驱动的大型分布式计算模式[1]．在这种模式的驱动下，以云存储和云安全为基础的各种服务相继出现．云计算通过虚拟技术，将云的计算能力及各类资源提供给用户．将云端资源有效的分配给用户是一个关键的技术问题．

学者们提出了先来先服务算法(FCFS，first come first service)、贪心算法(Greedy)、蚁群优化算法(ACO)[2]，遗传算法等来解决这个问题．先来先服务算法优点在于它容易实现，其缺点在于其没有考虑虚拟机的处理能力和任务的长度等一系列属性．贪心调度算法很好地避免了将长任务分配给处理能力弱的情况，但这个算法是一个局部最优的算法，它没有考虑系统的整体执行效率．蚁群优化算法作为一种智能算法，任务在经过蚁群的多次迭代之后必然能分配给一个合理的虚拟机，但其时间复杂度会高于FCFS和Greedy算法．

这些算法都没有涉及到任务的依赖关系和优先级．针对这个问题，本文提出了一种带偏序关系的调度算法(POA, Partial Order Algorithm)，给每个任务设置依赖关系和优先级，然后将FCFS、Greedy、ACO分别嵌入到POA中用于任务调度．带偏序关系的调度算法将会用CloudSim工具包[3-5]进行模拟仿真．CloudSim是在离散事件模拟包SimJava上开发的函数库，它继承了GridSim的编程模型，支持云计算的研究和开发．

本文在第1部分介绍CloudSim的体系结构；在第2部分和第3部分中分别给出POA的算法实现及相关的仿真结果．

1 CloudSim的体系结构

云计算平台任务调度的基本模型包含3个主要的部分：Users、Tasks、Virtual Machines．Users即为云计算平台的终端用户，他们不需要了解云计算平台的技术实现细节，只需要通过终端接入云计算平台提供的接口便能够使用其提供的服务．Tasks是用户向云计算平台请求处理的任务单元，它和用户是多对一的关系，一个用户可以请求处理多个任务，但一个具体的任务只隶属于一个用户．用户的任务最终都会放到Virtual Machines上进行处理．CloudSim中的基本模型见图1．

图 1 CloudSim的基本模型

2 POA算法

CloudSim中的任务默认是没有依赖关系和优先级的．但是实际生活中的云任务，往往存在这些偏序关系，某个任务的执行必须等待其它某个任务执行完毕；而且，在云计算中，虚拟机属于稀有资源，它需要合理地处理那些优先级比较高的任务．本文中，如果任务A依赖B，我们则以A→B的形式来描述它们的依赖关系；设置任务的默认优先级为10．最后将任务的依赖关系和优先级写入到两个不同的文件．

图 2 POA算法执行流程图

如果在任务的依赖关系文件中有如下依赖：A→B，B→C．因为A不需要依赖任何任务，故规定任务A为依赖关系图的第一层，根据图的深度，B属于第二层，C属于第三层．POA执行的流程图见图2，其具体执行步骤如下：

Step1. 分析任务的依赖关系文件，如果任务存在相互依赖或依赖关系形成环，则报错并退出．

Step2. 如果依赖关系合理，则对这些依赖关系进行分析，并将依赖关系图的每一层保存．

Step3. 依次读取步骤2中依赖关系图的每一层，如果某一层中某个任务的优先级别比其依赖任务的优先级要高，则表明依赖关系和优先级别冲突，报错并退出．

Step4. 如果步骤3不报错，则重新读取依赖关系图的每一层，然后分别通过先来先服务算法(FCFS)、贪心算法(Greedy)、蚁群优化算法(ACO)对这一层中的任务进行调度，并以最后一个任务完成的时间作为调度时间进行记录．

Step5. 当每一层都调度结束以后，对步骤4中记录的每一层的调度时间进行累加，最终得到的就是完成所有任务调度的时间．

3 仿真及结果分析

仿真系统中设置了两种不同的参数设置方式，其分别是平均随机和高斯随机．其中，平均随机出来的虚拟机和任务参数将平均地分布在参数下限和上限之间；高斯随机出来的参数将呈现正态分布．在平均随机中，虚拟机要设置其数量、处理能力下限、处理能力上限；任务需要设置其数量、长度下限、长度上限．通过这样随机得到的参数会均匀的分布到一条直线上．在高斯随机中，虚拟机要设置其数量、处理能力平均值μ、处理能力标准差σ；任务需要配置其数量、长度平均值μ、长度标准差σ．

图3、图4描述了虚拟机参数和任务参数变化时对POA算法中三种不同调度策略的影响．当采用平均随机进行调度，设定虚拟机数量在200～400间波动、Mips在200～400间变化、任务数量在400～800之间变化、任务长度在10 000～20 000间变化，POA中三种不同调度策略完成任务调度的时间如图3所示；采用高斯随机调度，设定虚拟机数量在200～400间波动，Mips在平均值为200方差为50，任务数量在400～800之间变化，任务长度平均值为15 000，标准差为500时，POA中三种调度策略完成任务调度的时间见图4．

图 3 平均随机下的POA算法

图 4 高斯随机下的POA算法

4 结束语

本文的主要工作是对CloudSim中的任务调度算法进行改进，提出了POA算法．本文通过平均随机、高斯随机的方式来测试POA算法的性能．最后，在参数相同的情况下对内嵌于POA算法的FSFS、Greedy、ACO进行比较并以此评判各算法的优劣．在本文谈及的POA任务调度中，我们只将FCFS、Greedy、ACO这些相对比较简单的算法用于任务调度．这些算法本身存在着一些弊端，应该有其它调度算法在低时间复杂度的情形下更合理地将任务分配给虚拟机，这些未考虑的问题，在以后的工作中将会被改进．

[参考文献]

[1] Cenk Erdil D.Simulating peer-to-peer cloud resource scheduling[J]. Peer-to-Peer Networking and Applications, 2012, 5(03): 219-230.

[2] Xiangqian Song, Lin Gao, Jieping Wang.Job scheduling based on ant colony optimization in cloud computing[C].2011 International Conference on Computer Science and Service System (CSSS), 2011： 3 309-3 312.

[3] Buyya R, Ranjan R, Calheiros R N. Modeling and simulation of scalable Cloud computing environments and the CloudSim toolkit: Challenges and opportunities [C]. International Conference on High Performance Computing & Simulation, 2009(HPCS '09), 2009：1-11.

[4] Xiaocheng Liu, Qiang He, Xiaogang Qiu, et al.Cloud-based computer simulation: Towards planting existing simulation software into the cloud[J].Simulation Modelling Practice and Theory, 2012,26:135-150.

[5] Werner J, Geronimo G, Westphall C, et al. Simulator improvements to validate the Green Cloud Computing approach[C].2011 7th Latin American Network Operations and Management Symposium (LANOMS), 2011：1-8.