Task scheduling based on load balancing of virtual machines in cloud computing

Yong-jun ZHANG, Qing-guo XIONG, Wen-xiang LI

(1School of Information Science and Technology, Wuhan University of Science and Technology, Wuhan 430081, China)(2Engineering Research Center of for Metallurgical Automation and Detecting Technology of Ministry of Education,Wuhan University of Science and Technology, Wuhan 430081, China)(3Hubei Province Key Laboratory of Systems Science in Metallurgical Process, Wuhan University of Science and Technology, Wuhan 430081, China)



Task scheduling based on load balancing of virtual machines in cloud computing

Yong-jun ZHANG1,2*, Qing-guo XIONG1, Wen-xiang LI2,3

(1School of Information Science and Technology, Wuhan University of Science and Technology, Wuhan 430081, China)(2Engineering Research Center of for Metallurgical Automation and Detecting Technology of Ministry of Education,Wuhan University of Science and Technology, Wuhan 430081, China)(3Hubei Province Key Laboratory of Systems Science in Metallurgical Process, Wuhan University of Science and Technology, Wuhan 430081, China)

For task scheduling in current cloud computing, some models pursue the shortest completion time without considering the load balancing in physical resource. In this paper, pre-classification task-based scheduling strategy (PCSS) was proposed. The minimum completion time and deadline of tasks were took into account comprehensively to set priorities of tasks which were assigned to the appropriate physical quantities of resources according to the virtual machine tasks priority level, accomplished the task of shortest time completed and the load balancing. Finally, simulation experiments in Cloudsim shows that this scheduling strategy performs user tasks effectively and supports load balance in physical resources.

Cloud computing, Task scheduling, Virtual machine, Priority queue, Load balancing

1 Introduction

Cloud computing is a large-scale distributed systems providing the infrastructure and software services to users. Service providers provide a variety of physical resources and services, to ensure the stability in the use of resources and must manage resources at the same time, thus to provide a variety of efficient services to users. The virtualization is one of the core technologies of cloud computing [1-2], which has independent performance, efficient organization, easy to manage, and many other advantages [3-5], with the help of virtualization technology, cloud computing can map virtual resources to a different physical machine reasonably, thus to achieve load balancing of physical resources. Therefore, it is important to find an efficient and reasonable task scheduling strategy on the premise of improving the utilization of physical resources and at the same time meet the needs of different users.

This paper considers resources properties of physical machines and the user task properties, proposing a short-term task priority queuing model and task scheduling strategy. The strategy is based on pr-categorized tasks, executing tasks of the virtual machine task queue on different physical machines according to priority level. Minimizing the task completion time and maximizing the number of completed tasks at the same time, thus dynamic load-balancing of physical resources can be achieved.

The paper is structured as follows, section 1 of the article introduces the related research work, and points out the direction worth discussing and improving; section 2 is the study of the computing task expansion optimal scheduling strategy analysis; in section 3 simulation experiment were designed and then gives the conclusion.

2 Related works

With the development of heuristic algorithms, many researchers aims at cloud computing task scheduling propose algorithms based on PSO, ACO and Min-Min, Max-Min, etc. these algorithms can effectively improve the user Qos and physical resource utilization[2,7-9]. The literature of [10] is based on Min-Min algorithm, selects resources based on the weighted average execution time, regards physical resources bandwidth as QoS attributes, to ensure the task with high quality of service get optimal physical resources. While Pandey used particle swarm optimization algorithm in the literature[11], to find an optimal task scheduling in the cloud computing environment, maximized tasks execution time and communication time delay, but he did not consider the deadline of tasks. Propose a maximize utility of cloud model, and this model is no longer take minimize completion time as the objective function. Instead take the multi-target maximizing utility as the goal, the model can improve user’s satisfaction effectively in the literature[12].

The task scheduling must take into account the interests of both sides, users hope that their submitted job can be completed more and quickly. While service providers hope to use the resources reasonably in order to achieve the maximum benefit. The paper presents a batch task distribute scheduling model for physical node. First, gets the priority of tasks in virtual machine queue according to the execution time and deadline of tasks, and then follows the PCSS standard batch distributes user tasks to multiple heterogeneous physical nodes, executes the high priority task first to meet the user’s task needs better and takes into account overall performance.

3 Task scheduling model

3.1 Scheduling model

In cloud computing, user tasks are divided into two categories, the computational and interaction tasks. Different type of tasks are quite different in the task scheduling and performance indicators [13]. In order to facilitate the analysis, scheduling model of the paper mainly discusses computational tasks.

The framework of cloud computing system of virtual machines and physical machines [6] are shown in Fig.1.

Fig.1 Cloud resources framework map

Using the virtual machine technology can utilize remaining resources of multiple physical machines (PM) to make up a virtual machine (VM) [12].

3.2 The objective function

According to the scheduling goals, build a multi-objective constraint functionWi={w1,w2}, namely

避嫌，怕人说闲话，好像不是什么多了不起的事，其实也是一种很高境界，看似平常，但并不容易做到，因为这要牺牲很多个人利益，甚至包括正当权益，没有点牺牲精神，自律意识，是很难做到的。如果天下手中有权的诸公，都能像宋徽宗、王学士、梅校长他们那样为了避嫌、不让人说闲话，谨慎用权，克己奉公，先人后己，严以自律，自然会风气清明，吏治严正，官员威信日高，人民由衷拥戴，事业红红火火，就没有干不成的事。

The equation (1) shows the maximum number of total tasks scheduling targets scheduling could be accomplished. The equation (2) shows that the shortest average completion time of scheduled tasks on the physical nodes, the completion time includes two parts, one is the remaining completion time of executing state tasks when tasks reach the physical machine, the other is the wait time of several previous tasks in task queue.

3.3 The constraint conditions

The following are the constraint conditions of the model:

Among them, the equation (3) represents the total number of tasks that physical machine needs to complete that is not lager than the total number of tasks in virtual machine user task queues, because the virtual machine task queue may discard tasks, equation (4) is to ensure that the occupancy rate of resource utilization of tasks distributed on a physical machine is not more than remaining resources, the equation (5) means that physical resource utilization assigned to it is greater than 0 for any user, equation (6) indicates that a task must be completed before the deadline which means that the maximum allowable time of completing tasks on a physical machine, proposed by users.

3.4 Design of scheduling algorithm

Model in this paper is the short-time priority task model, it means that tasks with minimum execution time should be dispatched first, then the total average dwell time is minimum[14]. Load balancing should also consider some remaining completion time for long-time task of important users, in order to better achieve user QoS. In here, we estimate the priority functions according to the deadline and execution time of tasks:

y=mCi+nDi

(7)

Wherem,nare non-negative parameters, which are used to measure the importance of execution time and deadline of the task.Ciis the theoretical execution time of the task, that is to say the required processing time to execute the task without interruption[15];Diis deadline of the task, and completion time must be less than the deadline of a task, otherwise the task will be discarded or die. Here we can adjust the value of m and n dynamically according to the importance of the task. A higher value of y indicates a higher priority level of tasks in virtual machine queue, scheduling high-priority task first.

The definition 1 is the remaining resource utilization, it is used to measure the computing power and communication capabilities of the physical machine, to quantify the physical resources. The specific formula of remaining resource utilization rate is as follow.

(8)

Whereα,β,γrepresent the processor, memory and bandwidth has a weight in the indicator of remaining resource utilization.Setting different attribute weights respectively according to requirements of user tasks for the importance of CPU, memory and bandwidth, then we can calculate the remaining resource utilization of physical nodesG. Since the resources of the physical machine may appear dynamic change in the process of scheduling [15], so every time before the realization of batch scheduling tasks, resource monitor gets the value of each attribute from the physical machine then calculates thepjof each physical machine which represents residual resource utilization rate.

3.5 Scheduling method based on PCSS

Because tasks in the virtual machine are diverse, so the required resource-ratio of each tasks on physical nodes is different, here we define the relative utilization of resources.

Definition 2 relative utilization of resources. For a physical machine node, required resources of processing each task divided by remaining resources is the relative utilization of resources, which is used to measure the ability of processing tasks for the physical machine.

The task scheduling problem can be described as a mapping relationship of scheduling the virtual machine task to physical nodes [2], so that the task completion time is shorter, processing user task as many as possible. This paper introduces the task allocation matrixC=T·P, which describes the mapping relationship between tasks and physical nodes:

(9)

In the equation (9),Ris the matrix of execution time,Sis matrix of relative resource utilization, elementrijis task execute completion time on each physical machine, elementsjis relative utilization rate of resources on different physical machines.

Definition 3 capacity Matrices, lineionli={Qi1,Qi2,…,Qii} represents that the ability matrix to perform on the tasktiassigned to each physical machine, that means to multiply mapping relationship of time from the task arrive at physical node by the relative resource utilization of physical node’s tasks.

From the ability of matrixli, we can see that the tasktichooses the smallest task-resource pair fromQijthen schedules it, the physical machine executes assigned tasks in batch. This would avoid the Min-Min algorithm to focus only on the task completion time without considering the disadvantages of the load balancing of physical resources.

4 Simulation and analysis

4.1 The simulation experiment scheme

According to the task scheduling strategy in this paper, simulation experiments were performed with the cloud simulation tool, namely, CloudSim. In order to achieve the performance comparison between the PCSS algorithm and the original Min-Min algorithm, the system generated 100 to 700 user tasks and 10 compute nodes randomly, the storage of tasks was generated randomly and its range is 100 to 1 000 kb. The theoretical execution times and deadlines of tasks were generated randomly as well. Their range are 1 to 200 ms. The task entered the simulation experimental system as a way of Poisson stream, processing capabilities of each physical machine nodes are different, the transmission rate of user tasks and different physical machines were generated randomly, the range of them is 100 to 1 000 kbps.

4.2 The results of simulation analysis

As shown in Fig.2, the PCSS strategy can balancing load effectively with task quantity increasing. When the tasks is less, user tasks were assigned to the physical machine 1 and 2, because the performance of physical machine 1 and 2 relative to other physical machines is better, then the other physical machines were in the idle state. But with the number of task increasing, the working flow was assigned to each physical machines, when the number of tasks up reached 700, the user task allocation ratio is balanced on four physical machines, 36% of the task was assigned to physical machine 1 to accept the services, there are 18% of the tasks were execute on the physical machine 4, This result reflects the load balancing of the algorithm.

As shown in Fig. 3, under the circumstance of different number of tasks, task average completion time of Min-Min algorithm and PCSS algorithm, namely the total completion time and the ratio of the number of tasks. When the task is less, n the average completion time of Min-Min algorithm and PCSS algorithm is same. But with the number of task increasing, PCSS algorithm has a great advantage on the average completion time than Min-Min algorithm, because the Min-Min algorithm schedules tasks to best physical machine, while the PCSS algorithm is according to the shor-term task priority and relative resource utilization, that could balance scheduling tasks on each physical, making the total completion time more less, so the average completion time is smaller.

Fig.2 Node assigned amount proportional

Fig.3 Average completion time

Fig. 4 presents the missed deadline ratio of tasks of Min-Min algorithm and algorithm in this paper which was variety with the amount of tasks. Miss ratio is the ratio between the number of tasks which is discarded before the deadline or abortive and the total number of tasks. When the tasks is less, task miss ratio is basically the same, because more resources to deal with the task request, the system could complete most tasks as long reasonable arrangement tasks with short deadline preferentially, the system could complete most tasks. With the increasing number of tasks, due to physical resources constraints, tasks can only be completed partially, therefore the missed deadline ratio of tasks is much bigger, but the performance is always better than that of Min-Min algorithm.

Fig. 4 Task deadline miss ratio

5 Conclusions

According to the feature of task scheduling cloud computing, this paper studied on computational tasks, sets the priority level according to the short-term task priority and deadline, scheduled tasks in the virtual machine queue execution on the physical machine according to the priority level, this ensures complete the task as quickly as possible and more, takes out the smallest task-resource pair from the product of task completion time and the relative resource utilization and then schedules it in order to meet the load balancing features.

Acknowledgement

This work is supported by Self-dependent Innovation fund Program of Wuhan University of Science and Technology (13ZRC124).

[1]HuangKai. Cloud computing resource management model and scheduling strategy research[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2013.

[2]XueYu. Cloud computing resource scheduling optimization model research[J]. Computer simulation, 2013, 30(5): 322-366.

[3]Amazon Inc. Amazon Web services EC2 site [EB/OL].[2010-12-18].http://aws.amazon.com/ec2/.

[4]WangWei, Guosun Zeng, Daizhong Tang et al. Cloud-DLS: Dynamic trusted scheduling for Cloud computing[J]. Expert Systems with Application, 2012, 39(3):165-172.

[5]Joel J P C. Rodrigues, Liang Zhou, Lucas D P. Mendes et al. Distributed media aware flow scheduling in cloud computing environment[J]. Computer communications, 2012, 35(15):131-142.[6]XuBaomin. Cloud computing decryption: Technology Principles and Application[M]. Beijing: Electronic Industry Press, 2014.

[7]BARHAM P, DRAGOVIC B, Fraser K, et al. Proceedings of the 19th ACM Symposium on Operating Systems Principles[C]//New York, USA: ACM, 2003.

[8]JUNGERS M, TRELAT E, ABOU-KANDIL H. Min-Max and Min-Min strackel berg strategies with closed-loop information structure[J]. Journal of Dynamical and Control System, 2011, 17(3): 185-198.

[9]BANSAL S K, BANSAL A, BLACK M B. Trust-based dynamic Web service composition using network analysis[C]//BASNA 2010: Proceedings of the 2010 IEEE International Workshop on Business Applications for Social Network Analysis. Piscataway: IEEE, 2010: 1-8.

[10]CHANHAN S, JOSHI R C. A heuristic for QoS based independent task scheduling in grid environment[C]//International Conference on Industrial and Information Systems. Mangalore of India, 2010:102-106．

[11]PANDEY S, WU L. Aparticle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments [C]//Proceeding of the 24thIEEE International Conference on Advanced Information Networking and Applications. Piscataway: IEEE, 2010:400-407.

[12]ShiXuelin, XuGe. Cloud virtual machine resource allocation utility maximization model [J].2013 Computer Journal, 36(2): 252-261.

[13]ZuoLiyun, ZuoLifeng. The cloud computing optimization scheduling algorithm based on pre-classification [J] . Computer Engineering and Design, 2012, 33(4): 1357-1361.

[14]KePeng, JinShanshan, LiWenxiang. priority queuing model for multi-service communication scheduling [J]. Computer Science, 2013, 40(3): 159-162.

[15]ZhuJiayu, XiaoDan. Cloud computing load balancing multidimensional+QoS+constraint task scheduling mechanism[J]. Compute-r Engineering and Applications, 2013, 49(9):85-90.

摘要：以机械加工中常用车床CA6140为研究对象，分别采用基于ANSYS的有限元法和实验法对其主轴进行了振动模态与频率响应分析，并对两者的计算结果进行了对比分析，验证了ANSYS数值仿真的准确性。数值仿真和实验结果表明：主轴在一阶频率和五阶频率处容易发生共振，但未达到共振，且低阶频率要比高阶频率对主轴的振动影响大；通过实验得出，主轴在工作状态下的最大振动主要集中在其两端轴承附近区域，因此改进轴承是减小主轴振动、保证主轴加工精度的重要途径，其研究结果可对车床的结构优化设计提供理论指导。

关键词：ANSYS有限元法；主轴；模态分析；频率响应；共振

云虚拟机资源负载均衡的任务调度研究

张勇军1,2*, 熊庆国1， 李文翔2,3

1.武汉科技大学 信息科学与工程学院,武汉430081 2.武汉科技大学 冶金自动化与检测技术教育部工程研究中心,武汉430081 3.武汉科技大学 冶金工业过程系统科学湖北省重点实验室,武汉430081

针对云计算中现有任务调度模型为追求最短完成时间,而没有从物理资源的负载均衡角度考虑, 提出了基于任务预先分类的调度策略(PCSS)。该策略通过综合考虑任务的最少执行时间和截止时间来设置优先级,根据优先级别将任务批量分配给合适的物理机,实现了任务的最短完成时间和物理机的负载均衡。最后通过Cloudsim 仿真实验分析和比较,该策略能很好地执行用户任务并体现出良好的负载均衡。

云计算；任务调度；虚拟机；优先级队列；负载均衡

(Continued from 63 page)

基于ANSYS有限元法的某型车床主轴振动频率响应分析

周泽新*

武汉理工大学 能源与动力工程学院，武汉430063

15 January 2015; revised 19 March 2015;

Yong-jun Zhang.

E-mail: zhang421083@126.com.

10.3969/j.issn.1001-3881.2015.18.012 Document code: A

TP301

accepted 2 June 2015

Hydromechatronics Engineering

http://jdy.qks.cqut.edu.cn

E-mail: jdygcyw@126.com