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

避嫌，怕人說閑話，好像不是什么多了不起的事，其實(shí)也是一種很高境界，看似平常，但并不容易做到，因?yàn)檫@要犧牲很多個(gè)人利益，甚至包括正當(dāng)權(quán)益，沒有點(diǎn)犧牲精神，自律意識，是很難做到的。如果天下手中有權(quán)的諸公，都能像宋徽宗、王學(xué)士、梅校長他們那樣為了避嫌、不讓人說閑話，謹(jǐn)慎用權(quán)，克己奉公，先人后己，嚴(yán)以自律，自然會(huì)風(fēng)氣清明，吏治嚴(yán)正，官員威信日高，人民由衷擁戴，事業(yè)紅紅火火，就沒有干不成的事。

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.

摘要：以機(jī)械加工中常用車床CA6140為研究對象，分別采用基于ANSYS的有限元法和實(shí)驗(yàn)法對其主軸進(jìn)行了振動(dòng)模態(tài)與頻率響應(yīng)分析，并對兩者的計(jì)算結(jié)果進(jìn)行了對比分析，驗(yàn)證了ANSYS數(shù)值仿真的準(zhǔn)確性。數(shù)值仿真和實(shí)驗(yàn)結(jié)果表明：主軸在一階頻率和五階頻率處容易發(fā)生共振，但未達(dá)到共振，且低階頻率要比高階頻率對主軸的振動(dòng)影響大；通過實(shí)驗(yàn)得出，主軸在工作狀態(tài)下的最大振動(dòng)主要集中在其兩端軸承附近區(qū)域，因此改進(jìn)軸承是減小主軸振動(dòng)、保證主軸加工精度的重要途徑，其研究結(jié)果可對車床的結(jié)構(gòu)優(yōu)化設(shè)計(jì)提供理論指導(dǎo)。

關(guān)鍵詞：ANSYS有限元法；主軸；模態(tài)分析；頻率響應(yīng)；共振

云虛擬機(jī)資源負(fù)載均衡的任務(wù)調(diào)度研究

張勇軍1,2*, 熊慶國1， 李文翔2,3

1.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院,武漢430081 2.武漢科技大學(xué) 冶金自動(dòng)化與檢測技術(shù)教育部工程研究中心,武漢430081 3.武漢科技大學(xué) 冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室,武漢430081

針對云計(jì)算中現(xiàn)有任務(wù)調(diào)度模型為追求最短完成時(shí)間,而沒有從物理資源的負(fù)載均衡角度考慮, 提出了基于任務(wù)預(yù)先分類的調(diào)度策略(PCSS)。該策略通過綜合考慮任務(wù)的最少執(zhí)行時(shí)間和截止時(shí)間來設(shè)置優(yōu)先級,根據(jù)優(yōu)先級別將任務(wù)批量分配給合適的物理機(jī),實(shí)現(xiàn)了任務(wù)的最短完成時(shí)間和物理機(jī)的負(fù)載均衡。最后通過Cloudsim 仿真實(shí)驗(yàn)分析和比較,該策略能很好地執(zhí)行用戶任務(wù)并體現(xiàn)出良好的負(fù)載均衡。

云計(jì)算；任務(wù)調(diào)度；虛擬機(jī)；優(yōu)先級隊(duì)列；負(fù)載均衡

(Continued from 63 page)

基于ANSYS有限元法的某型車床主軸振動(dòng)頻率響應(yīng)分析

周澤新*

武漢理工大學(xué) 能源與動(dòng)力工程學(xué)院，武漢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