透過工作排程與負載平衡來提昇雲端運算的效能

Enhancing the Performance of Cloud Computing Through Job Scheduling and Load Balancing

黃琨富(Kuen-Fu Huang)

指導教授 ： 唐元亮

朝陽科技大學/資訊學院/資訊管理系/碩士(2015年)

摘要

雲端運算自被提出後便受到相當多的注視與討論，雲端運算透過虛擬化技術產生虛擬機器以提升實體機器的資源利用率，進而增加處理工作的效率。然而，如何將工作分配至最適當的虛擬機器上執行使全體工作能以最小的總完工時間完成為相當重要的問題。因此，本研究先探討工作排程演算法種類，並分析工作排程演算法種類之效能，針對效能較好之工作排程演算法種類中的工作排程演算法進行深入之研究與分析，窺探出該工作排程演算法種類中的工作排程演算法特性與其優缺點。了解其特性與優缺點後，本研究將缺點改善並將分析出之優點加入於本研究所設計之工作排程演算法，提出一個新興之工作排程演算法Minimum Makespan and Load Balancing (MMALB)。
MMALB加入負載平衡此因素，使MMALB在進行工作之分配時能使虛擬機器都能被分配到工作，避免虛擬機器處於閒置狀態，且MMALB透過假設的工作遷移與工作交換之動作，使所有工作能找尋到最適當的虛擬機器使總完工時間呈現最小狀態，其中MMALB也考慮工作延遲被執行之因素，透過調整工作執行的順序，降低工作延遲被執行的時間。實驗部分本研究使用CloudSim實現本研究所提及之工作排程演算法並分析其效能，實驗結果顯示，本研究所提出之MMALB能使總完工時間最小，降低工作延遲被執行的時間，最小化虛擬機器之間之負載差距並使虛擬機器之資源使用率達到最佳化。

關鍵字

工作排程演算法 ； 虛擬化技術 ； 雲端運算 ； 負載平衡

並列摘要

Cloud computing has received a lot of attentions and discussions recently both in the academia and industry. It uses the virtualization technology to generate virtual resources and a lot of virtual machines from physical resources in order to enhance its performance. The main idea of virtualizing resources is to increase the utilization of various resources, such as CPUs, memory, storage space, networks, etc., by sharing them among users. In addition to resource virtualization, it is also very import to assign each work to the most appropriate virtual machine according to the machine’s computation capability in order to minimize the Makespan (i.e., the final completion time) of all works. In this research, the fundamental concepts of job scheduling are first reviewed, followed by introducing and analyzing the main existing algorithms, including comparison of their advantages, shortcomings, and performances. Second, a novel scheduling algorithm is proposed, in which the load balancing is taken into account so as to make even better resource utilization. The algorithm also minimizes the Makespan through work assignment and swapping. Thus, the waiting time of each work can be effectively reduced by carefully adjusting the order of execution. Experimental results show that the proposed algorithm can achieve minimum Makespan, minimum waiting time, maximum load balance, and best resource utility.

並列關鍵字

Load Balancing ； Job Scheduling Algorithm ； Virtualization Technology ； Cloud Computing

參考文獻

[33] R.P. Padhy and P.G. Prasad (2011), “Load Balancing in Cloud Computing System,” Department of Computer Science and Engineering National Institute of Technology, pp. 1-56.

[26] S. Ghemawat, H. Gobioff, and S.-T. Leung (2003), “The Google File System,” Proceedings of the nineteenth ACM symposium on Operating systems principles, pp. 1-15.

[1] S. Bansal and C. Hota (2011), “Efficient Refinery Scheduling Heuristic in Heterogeneous Computing Systems,” Journal of Advancesin Information Technology, Vol. 2, No. 3, pp. 159-164.

[3] T.D. Braun, H.J. Siegel, N. Beck, L.L. Bölöni, M. Maheswaran, A.I. Reuther, J.P. Robertson, M.D. Theys, B. Yao, D. Hensgen, and R.F, Freund (2001), “A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems,” Journal of Parallel and Distributed Computing, pp. 810–837.

[4] R.N. Calheiros, R. Ranjan, and A. Beloglazov, C.A.F.D. Rose, R. Buyya (2011), “CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms”, Software: Practice and Experience (SPE), Vol. 41, No. 1, pp. 23–50.