基于云计算的“用户期待”任务调度算法的研究

刘之家 张体荣 谢雄程

（广西师范学院计算机与信息工程学院，广西 南宁 530001）

基于云计算的“用户期待”任务调度算法的研究

刘之家 张体荣 谢雄程

（广西师范学院计算机与信息工程学院，广西 南宁 530001）

文章在云计算提供的各项服务质量基础上，提出了云计算任务调度的用户期待函数，并根据用户期待函数和服务质量的任务分类，提出了用户期待函数的任务调度算法，最后在云计算仿真平台 CloudSim上进行仿真实验与分析。实验结果表明，该任务调度算法在调度时间、可靠性与费用等方面具有一定的优势。

云计算；服务质量；任务调度；仿真

（一）引言

云计算是由分布式计算、并行计算、网格计算、虚拟技术、普适计算等概念混合演化而来的一种新型的计算模型。它将计算任务分布在大量计算机、存储设备等组成的资源池上，用户可以根据需要获取计算能力、存储空间和各种软件服务，是一种以Internet为基础向用户提供信息服务的商业模式，其目标是为用户动态地提供可靠的、可定制的、服务质量( QoS)保证的IT计算服务环境。然而，不同的用户有不同的需求，云计算必须提供用户满意的服务，服务质量 QoS成为了衡量用户使用云计算服务满意程度的标准。这样对云计算的作业调度和资源分配提出了更高的要求。

多任务调度问题是计算机界公认的NP难题，采用启发式方法可以得到次最优解，而固定优先级调度策略可能会引起低优先级线程饥饿和短程任务滞后，先到先处理调度策略可能会引起高价值任务错失最佳处理时刻。因此，对云计算的任务调度进行研究具有重要的意义。

（二）基本理论

1.用户期待函数的定义

在云计算中，服务质量 QoS是衡量用户使用云计算服务满意程度的标准。云计算为互联网上的各类用户提供不同的服务，但由于用户的多样性，为了给用户提供满意的服务质量，云计算的任务调度和资源必须得到合理的分配。文章通过引入资源分配的用户期待函数对用户资源量的需求进行分析，任务的用户期待函数定义为：

其中， 为常量，且0<θ≤1，AR为任务的实际资源分配量，ER为任务期待的资源量。

2.基于QoS的任务分类

按照 QoS标准可将任务按完成时间、带宽、可靠性、费用分为四类，可建立如下的量化标准：

（1）完成时间：任务的时间性QoS描述包括开始时间、最迟完成时间、总完成时间、结束时间等。

Twait是从任务提交到被分配处理资源的等待时间，Texec为任务执行时间，Ttrans为任务传输时间。设任务的期待完成时间为Texpt，则用户期待函数表示为：

（3）费用：虚拟机按照单位对资源计费，任务消费的全部费用costvm为：

P1表示资源数量，C参数表示单位资源价格，设costuser为用户期待的费用，则用户期待函数为：

（4）可靠性：对于可靠性要求较高的用户任务来说，选择可靠性高的资源为其提供服务，能够显著提高其服务质量。设虚拟机的故障率为p，用户期待的任务完成率psucc由用户指定，则用户期待函数为：

当用户任务有多方面 QoS需求时，可将上面讨论的完成时间、带宽、费用、可靠性的用户期待评判函数进行综合，得到综合的用户期待函数：

根据以上四点描述，完成时间表示对实时性要求较高的用户，需要任务在尽可能少的时间内完成。当客户对通信带宽要求较高时，则需要优先考虑带宽要求。可靠性表示对长期运行任务的用户，需要云计算提供稳定可靠的性能，如云存储服务。此外，云计算按需付费，使用费用是用户关注的一个因素，对于希望廉价的服务的用户来说，费用是一个衡量标准。

（三）研究方法

云计算环境的特点包括了支持基础设施的建模与仿真，支持数据中心、服务代理人、调度和分配策略的平台。它提供虚拟化引擎，在数据中心节点上帮助建立和管理多重的、独立的、协同的虚拟化服务。对虚拟化服务分配处理核心时能够在时间共享和空间共享之间灵活切换。

1.云计算的任务调度模型

任务调度模型的工作方式如图 1所示，云信息服务和数据调度中心实现资源发现和信息交互，是任务调度的核心。设计的调度算法可在数据调度中心中实现，从而实现调度算法的模拟。

图1 云计算的任务调度模型

2.任务调度流程

云计算调度的数据流程如图 2所示，数据中心的资源创建以后向 CIS云信息服务注册，由数据中心调度管理信息的交互过程。

图2 调度数据流

3.用户期待函数的任务调度算法流程

Step 1：给定任务参数表，表中含有用户所期待的资源与用户的任务大小。

Step 2：获取虚拟机的资源，根据资源分别计算虚拟机的性能。

Step 3：按QoS的任务类型计算综合Jzh，为了方便计算，可用expJzh代替。Step 4：根据Step 2与Step 3 的计算结果将虚拟机与任务按性能与用户期待值从大到小进行对应的映射与绑定，任务数按虚拟机数进行平均分配。

Step 5：执行并统计和返回所有任务的总花费。

（四）仿真实验

1.仿真平台

云计算的仿真平台目前有澳大利亚墨尔本大学设计的CloudSim，它是在网格实验室和 Gridbus基础上建立的。仿真的过程分为以下步骤进行：

（1）初始化GridSim库

GridSim.init(num_user,calendar,trace_flag,exclu de_from_file, exclude_from_processing, report_name);

（2）创建数据中心

在仿真平台中，一个数据中心由一台或多台 Machine组成，而一台Machine可由一个或多个PEs或CPUs组成。本实验程序创建了两个数据中心，每个数据中心有两台Machine，其中一台Machine由4个PEs组成，另一台由2个PEs组成。

DataCenter datacenter0 = createDatacenter("Datacenter_0");

DataCenter datacenter1 = createDatacenter("Datacenter_1");

（3）创建Broker

DatacenterBroker broker = createBroker();

int brokerId = broker.get_id();

（4）创建虚拟机

VirtualMachine vm1 = new VirtualMachine(new VMCharacteristics(vmid, brokerId, size, memory, bw,vcpus, priority, vmm, new TimeSharedVMScheduler()));

（5）创建云任务

cloudletList = new CloudletList();

Cloudlet cloudlet1 = new Cloudlet(id, length,file_size, output_size);

Cloudlet1.setUserID(brokerId);

（6）启动仿真

GridSim.startGridSimulation();

（7）统计结果

CloudletList newList = broker.getCloudletList();

GridSim.stopGridSimulation();

printCloudletList(newList);

datacenter0.printDebts();

datacenter1.printDebts();

具体的仿真程序编写过程可参考CloudSim网站提供的编程样例。

2.实验数据

本实验采用前面两类任务的调度来模拟用户期待函数的任务调度，如表1所示包含有8个任务，表中的参数分别表示为任务标识、长度、提交到数据中心的文件大小、数据中心输出文件的大小、任务期待的带宽。表2包含了4个虚拟机的参数，分别表示虚拟机的身份标识、CPU个数、内存大小、带宽、虚拟机性参数。其中虚拟机性能参数大小等于 CPU个数，即内存大小与带宽的乘积，这个值越大，表示虚拟机的性能越好。

表1 任务参数表

表2 虚拟机参数列表

3.实验方法与分析

文章的任务调度算法在仿真环境中实现任务的调度有两种方法实现，一种是重载CloudSim的DatacenterBroker类的bindCloudletToVM()方法，该方法是将单一的任务绑定到指定的单一虚拟机上运行，在重载的方法里可实现自己的任务调度策略，但是重载后需重新编译CloudSim，这种方法属于内部嵌入的方式。另一种方法是在编写仿真程序时通过调度算法算出各个任务的优先级，再调用bindCloudletToVM方法将任务与虚拟机进行绑定，此种方法属于外部接口方式。文章的仿真程序采用外部接口方式，云任务与虚拟机的绑定部分代码如下所示：

broker.bindCloudletToVM(cloudlet[0].getCloudlet Id(),vm[3].getVmId());

broker.bindCloudletToVM(cloudlet[1].getCloudlet Id(),vm[3].getVmId());

broker.bindCloudletToVM(cloudlet[2].getCloudlet Id(),vm[1].getVmId());

broker.bindCloudletToVM(cloudlet[3].getCloudlet Id(),vm[0].getVmId());

broker.bindCloudletToVM(cloudlet[4].getCloudlet Id(),vm[2].getVmId());

broker.bindCloudletToVM(cloudlet[5].getCloudlet Id(),vm[2].getVmId());

broker.bindCloudletToVM(cloudlet[6].getCloudlet Id(),vm[0].getVmId());

broker.bindCloudletToVM(cloudlet[7].getCloudlet Id(),vm[1].getVmId());

本程序中有4个虚拟机，每个虚拟机处理2个任务。根据式4计算expJbw值，这与计算Jbw值的效果是等价的，式中取1。如表3所示，表中“按带宽VMID”表示按带宽条件进行任务与虚拟机的映射，实验测得 Processing Cost的值为1370.25。同理，再进行“按完成时间”计算expJT，然后进行任务与虚拟机的映射，实验测得 Processing Cost的值为1089.75。expJT的计算可由输入数据中心的文件大小与输出数据中心的文件大小比值进行估算。

经过与表5中Processing Cost为1265.25的值进行比较可知，单纯的按带宽进行任务调度效果反而不如系统默认的最小完成时间调度算法效率高，但按完成时间测试得到的结果略高于最小完成时间调度算法。因此，考虑将“按带宽VMID”与“按完成时间”二者综合起来计算函数f(expJ)的综合值，测试结果如表4所示。

表3 云任务与虚拟机映射表

表4 用户期待函数的任务调度算法实验结果

表5 最小完成时间调度算法实验结果

对比表4与表5的实验结果，从单个任务的最小完成时间来说，用户期待函数的调度算法与最小完成时间的调度算法相比没有优势，如任务 6按最小完成时间算法时的花费值为24，而用户期待函数调度则花费值为84，二者相差较大。但从整体花费上相比，用户期待函数调度的综合花费为1089.75，要优于最小完成时间的调度算法的花费值1265.25。因此，用户期待函数的调度算法从平均性能来说要比最小完成时间更好地满足用户需求。

（五）结束语

随着云计算技术的发展与应用，对云计算服务质量的要求不断提高。文章通过引入用户期待函数对用户任务调度策略进行研究。仿真实验结果表明，用户期待函数的任务调度算法与传统的最小完成时间任务调度算法从平均性能来说具有一定的优势，而研究更理想更有效的云计算任务调度算法是下一步的工作目标。

[1]宋远骏,杨孝宗,李德毅,崔东华.多机多任务实时系统云调度策略[J].计算机学报,2000,23(10):1107-1110.

[2]陈全,邓倩妮.云计算及其关键技术[J].计算机应用,2009,2(9):2562-2568.

[3]郭本俊,王鹏,陈高云,黄健.基于 MPI的云计算模型[J].计算机工程,2009,35(24).

[4]Rodrigo N. Calheiros, Rajiv Ranjan, Cesar A. F. De Rose,Rajkumar Buyya.CloudSim.A Novel Framework for Modeling and Simulation of Cloud Computing Infrastructures and Services[R]. Technical Report, GRIDS-TR-2009-1,2009.

[5]张海宾,唐琳莎,刘立祥.网格调度综述[J].计算机工程与设计,2009,30(9):2151-2154.

TP301.6

A

1008-1151(2011)04-0075-03

2011-01-21

国家自然科学基金（60864001），广西教育厅基金项目（200911MS144）

刘之家（1963－），男（壮族），广西南宁人，广西师范学院计算机与信息工程学院讲师，研究生，研究方向为网络技术、云计算；张体荣（1965－），男，广西全州人，广西师范学院计算机与信息工程学院工程师、企业管理咨询师，研究生，研究方向为管理软件、云应用；谢雄程（1972－），男，广西南宁人，广西师范学院计算机与信息工程学院讲师，硕士，研究方向为计算机网络。