基於不同分配策略針對雲端環境中的任務排程及比較

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：94

、訪客IP：18.220.224.50

姓名

李壹維(Yi-wei Li) 查詢紙本館藏

畢業系所

資訊工程學系在職專班

論文名稱

基於不同分配策略針對雲端環境中的任務排程及比較
(Task scheduling for the comparison of different allocation strategies in the cloud environment)

相關論文

★ 以伸展樹為基礎的Android Binder Driver	★ 應用增量式學習於多種農作物判釋之研究
★ 應用分類重建學習偵測航照圖幅中的新穎坵塊	★ 用於輔助工業零件辨識之尺寸估算系統
★ 使用無紋理之3D CAD工業零件模型結合長度檢測實現細粒度真實工業零件影像分類	★ 一個建立在平行工作系統上的動態全球計算平台
★ 用權重參照計數演算法執行主動物件垃圾收集	★ 一個動態負載平衡之最大可能性估算計算架構
★ 利用多項系統負載資訊進行動態P2P系統重組的策略研究	★ 基於Hadoop系統的雲端應用程式特徵擷取與計算監測架構
★ 適用於大型動態分散式系統的調適性計算模型	★ 一個提供彈性虛擬資料中心的雲端服務平台
★ 雲端彈性虛擬機房服務平台之資源控管中心	★ 一個適用於自動供應雲端系統的動態調適計算架構
★ 線性相關工作與非相關工作的探索式排程策略	★ 適用於大資料集高效率的分散式階層分群演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

雲端運算在近年來已經越來越普及，帶動了網路流量與儲存資料的爆炸性成長。使用者不需要了解雲端中基礎設施的專業知識，也不需要自己管理、控制，使用者只需要專注於所需的資源與服務。而雲端運算的應用方式通常是以虛擬化的形式，把資訊技術，包括運算、儲存及網路頻寬，以服務的方式透過網路提供給使用者。如何能夠有效率的管理分配虛擬資源來滿足使用者需求則成為了雲端計算一項重要的課題。

CloudReports是根據雲端運算模式的一個模擬分散式運算環境的圖形化工具。本研究中我們實施了一些常用的演算法在CloudReports上，並仿照Amazon EC2執行環境進行了有關完成時間 (makespan) 和決策時間的幾個模擬，查看在同質和在異質環境中的性能表現。我們的結果顯示，在同質環境中Max-min及Round-robin會是比較好的選擇，但其他啟發式演算法表現上就沒有特別出色，且決策時間花費也比較長。異質環境方面，在平均表現上Max-min會比較好，但如果在任務數量及長度最多的時候，螞蟻演算法卻擁有較好的性能表現，當然也花費了相當長的決策時間去尋找最佳解。另外異質環境中在有限的VM時，基因演算法能夠在任務數量及長度最多時表現最佳。

摘要(英)

Cloud computing has become increasingly popular in recent years. One of the important issues in cloud computing is resource allocation for different kinds of tasks. Choosing a good scheduling algorithm for different kinds of computing jobs is the key to utilize resources efficiently. To this end, this study aims to investigate how different scheduling algorithms perform on different kinds of virtual environment, which may consist of heterogeneous virtual machines or homogeneous virtual machines. We have implemented several scheduling algorithms on CloudReports, which is a graphical tool for simulation of distributed computing environments based on the cloud computing model. The algorithms to be evaluated include random scheduling algorithms, heuristic scheduling algorithms, and meta-heuristics-based algorithms. We have conducted several simulations to evaluate the performance of various scheduling algorithms in terms of makespan of tasks and decision time of scheduling, given different kinds of system and task configurations. Our results show that, Max-Min and Round-Robin would be better choices in a homogeneous environment. Heuristic algorithms are not favored in a homogeneous environment since they need long decision time and may not achieve a good makespan. Generally, Max-Min would be a better choice in a heterogeneous environment. However, as the number of tasks and the length of each task become large, meta-heuristic algorithms tend to outperform Max-Min in makespan.

關鍵字(中)

★ 雲端運算
★ 雲端模擬
★ 排程演算法
★ 啟發式演算法

關鍵字(英)

★ Cloud Computing
★ Cloud Simulation
★ Task Scheduling
★ Heuristic Algorithms
★ Meta-Heuristic Algorithms

論文目次

摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章緒論 1
1-1 前言 1
1-2 問題與實作目標 2
1-3 論文貢獻 3
1-4 論文架構 4
第二章相關研究 5
2-1 相關系統工具 5
2-1-1 CloudSim 5
2-1-2 CloudSim的基本設計 6
2-1-3 CloudReports 7
2-2 相關任務排程策略 9
2-2-1 Hybrid job scheduling algorithm for cloud computing environment 9
2-2-2 Cloudlet Scheduling with Particle Swarm Optimization 9
2-2-3 An empirical study of most fit, max-min and priority task scheduling algorithms in cloud computing 10
第三章 CloudReports任務排程設計 11
3-1 First-Come-First-Serve with Random/Round-Robin 11
3-2 Shortest-Job-First with Random/Round-Robin 11
3-3 Longest-Job-First with Random/Round-Robin 12
3-4 Max-min 13
3-5 Min-min 13
3-6 Ant Colony Optimization 14
3-7 Simulated Annealing 16
3-8 Genetic Algorithm 18
3-9 Particle Swarm Optimization 20
第四章系統環境與測試 22
4-1 在同質環境中的性能分析 22
4-1-1 Cloudlet的數量不變/長度不斷增加時的性能分析 25
4-1-2 Cloudlet的長度不變/數量不斷增加時的性能比較 28
4-2 在異質環境中的性能分析 30
4-2-1 減少VM數量時的性能分析 33
4-2-2 增加VM數量時的性能分析 35
4-3 進一步分析與探討 38
第五章結論 41
第六章未來研究方向 42
參考文獻 43
附錄一 CloudReports相關設定值 45

參考文獻

[1] I. Foster, Y. Zhao, I. Raicu, and S. Lu, “Cloud Computing and Grid Computing 360-Degree Compared,” in Grid Computing Environments Workshop, 2008.GCE ’08, 2008, pp. 1–10.
[2] B. Furht, “Handbook of Cloud Computing,” in Handbook of Cloud Computing, B.Furht and A. Escalante, Eds. Boston, MA: Springer US, 2010, pp. 3–19.
[3] P. Mell and T. Grance, “The NIST Definition of Cloud Computing.”
[4] Rodrigo N. Calheiros, Rajiv Ranjan, Anton Beloglazov, Cesar A. F. De Rose, and Rajkumar Buyya, “CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms”in Software: Practice and Experience, Volume 41, Number 1, Pages: 23-50, ISSN: 0038-0644, Wiley Press, New York, USA, January 2011.
[5] Thiago Teixeira Sá, Rodrigo N. Calheiros and Danielo G. Gomes “CloudReports: An Extensible Simulation Tool for Energy-Aware Cloud Computing Environments” in Cloud Computing,Part of the series Computer Communications and Networks pp. 127-142.
[6] Chung-Yi Chou, “M-CloudSim: A Simulation Platform of Virtual Resource Provisioning Algorithm in Cloud Computing”, pp. 1-6, July, 2012
[7] 趙立慧. “基於 CLOUDSIM 平台的雲任務分配策略研究”. MS thesis. Inner Mongolia Agricultural University, 2013.
[8] Tracy D. Braun, Howard Jay Siegel, and Noah Beck, “A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems,” JPDC, Vol. 61, No. 6, pp. 810-837, 2001.
[9] Min-Yi Tsai, Ping-Fang Chiang, Yen-Jan Chang, and Wei-Jen Wang, “Heuristic Scheduling Strategies for Linear-Dependent and Independent Jobs on Heterogeneous Grids,” in CCIS, Volume 261, pp. 496-505, 2011.
[10] X. Song and L. Gao, "Job scheduling based on ant colony optimization in cloud computing," in 2011 Proc. of CSSS, Nanjing, China, pp. 3309-3312, 2011.
[11] Asim YarKhan and Jack Dongarra, “Experiments with Scheduling Using Simulated Annealing in a Grid Environment,” in Proc. of GRID ′02, London, UK, pp. 232-242, 2002.
[12] J. Page and J. Naughton, “Framework for task scheduling in heterogeneous distributed computing using genetic algorithms”, Artificial Intelligence Review, 2005 pp.415–429.
[13] S. Pandey and L. Wu, and R. Buyya, “A Particle Swam Optimization-based Heuristic for Scheduling Workflow Application in Cloud Computing Environments”, in IEEE AINA, pp. 400-407, 2010
[14] Chen, Wei-Neng, and Jun Zhang.“An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements.”Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on 39.1 (2009): 29-43.
[15] Hussein S. Al-Olimat ,“Optimizing Cloudlet Scheduling and Wireless Sensor Localization using Computational Intelligence Techniques”,pp. 21-34
[16] Hong-Lin Huang, Wei-Lun Fang and Wei-Jen Wang,“Developing extensions for CloudReports and Drawing Comparisons between Different Datacenter Broker Policies”,National Central University,2013
[17] S.Devipriya,C.Ramesh,”IMPROVED MAX-MIN HEURISTIC MODEL FOR TASK SCHEDULING IN CLOUD” IEEE 2013.
[18] Javanmardi, Saeed, et al. "Hybrid job scheduling algorithm for cloud computing environment." Proceedings of the Fifth International Conference on Innovations in Bio-Inspired Computing and Applications IBICA 2014. Springer International Publishing, 2014.
[19] Al-Olimat, Hussein S., et al. "Cloudlet Scheduling with Particle Swarm Optimization." Communication Systems and Network Technologies (CSNT), 2015 Fifth International Conference on. IEEE, 2015.
[20] Zuo, Liyun, et al. "A Multi-Objective Optimization Scheduling Method Based on the Ant Colony Algorithm in Cloud Computing." Access, IEEE 3 (2015): 2687-2699.
[21] Taneja, Bhawna. "An empirical study of most fit, max-min and priority task scheduling algorithms in cloud computing." Computing, Communication & Automation (ICCCA), 2015 International Conference on. IEEE, 2015.
[22] “CloudSim”. [Online].https://en.wikipedia.org/wiki/CloudSim/.
[23] “GA Algorithm”. [Online].http://www.codeforge.cn/read/225532/SGAFrame.java__html
[24] Kaur, Navdeep, and Khushdeep Kaur. "Improved Max-Min Scheduling Algorithm."
[25] Dorigo, Marco, Vittorio Maniezzo, and Alberto Colorni. "Ant system: optimization by a colony of cooperating agents." Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 26.1 (1996): 29-41.
[26] “模擬退火”. https://zh.wikipedia.org/wiki/模擬退火

指導教授

王尉任(Wei-jen Wang)

審核日期

2016-3-15

推文