系統識別號 | U0002-1908201413223100 |
---|---|
DOI | 10.6846/TKU.2014.00742 |
論文名稱(中文) | 改善並行虛擬機器排程演算法之研究 |
論文名稱(英文) | Improving Scheduling for Concurrent Virtual Machines |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 電機工程學系碩士班 |
系所名稱(英文) | Department of Electrical and Computer Engineering |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 102 |
學期 | 2 |
出版年 | 103 |
研究生(中文) | 周稚淵 |
研究生(英文) | Chih-Yuan Chou |
學號 | 600450075 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2014-06-20 |
論文頁數 | 65頁 |
口試委員 |
指導教授
-
莊博任
委員 - 陳省隆 委員 - 李維聰 |
關鍵字(中) |
虛擬化 排程 |
關鍵字(英) |
Xen scheduling |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
在虛擬化平台Xen Hypervisor上,有許多組態設定,像是Virtual CPU(VCPU)、Virtual Memory、Scheduling等皆是用來架構虛擬機器所需要的各種組態與排程。其中Xen Hypervisor上面之CPU Scheduling的演算策略設計為我們所深入研究之項目。目的在於改善當前Xen CPU Schdeduling的排程策略Credit下,對於執行並行程式的虛擬機器(VM),有可能造成可觀的時間浪費。 由於在並行程式中各個同階段的任務之間需要互相通信與同步,而在Credit的排程策略下,並不會根據並行程式而同時間執行,導致各任務需要花費較多的時間,在執行同步的動作。而在Tseng et al.的方法提出,針對並行程式的VCPU,附加了Turbo的優先權,在排程階段時,將同是Turbo的VCPU一同搬移到執行佇列的頂端執行。但Credit與Tseng et al.的方法皆是使用較花費時間的佇列操作方法(插入、刪除、查找)。 我們提出利用Linux kernel 2.6版本所使用的CFS(Completely Fair Scheduler)排程方法來改善Credit所產生的影響,並藉由CFS的機制來消彌並行VM與其他VM之間的差距。CFS可以更公平的分配到處理器的時間,且基於RB-Tree的概念與操作,可以讓越少被執行到的任務,有更高的優先機率被處理器執行到,而在並行VCPU的處理上,透過標記與設置等待佇列,亦達成了並行VCPU的同步問題。 在我們的實驗與比較部分,使用NAS Benchmark所提供的並行程式做實驗,在VM中執行並逐步調整VM的權重使VCPU在RB-Tree中的Virtual runtime增減,以換取PCPU挑選VCPU的機會,最後獲取執行時間來統計效能的變化。 實驗結果可以看出在Credit、Tseng et al.的方法與我們的演算方法相比較下,確實大幅減少了全域的運行時間,在並行虛擬機器下的整體效能大幅增加。 |
英文摘要 |
On the virtualization platform Xen Hypervisor, there are many configuration settings, such as Virtual CPU (VCPU), Virtual Memory, Scheduling are needed for a variety of configuration and scheduling for virtual machine architecture. The strategy design which Xen Hypervisor above the CPU Scheduling for our in-depth research project. The purpose is to improve the current under Xen CPU Schdeduling strategy Credit, for a virtual machine (VM) implementation of a concurrent application, it may result in considerable waste of CPU time. Due to need to communicate with each other with the phase synchronization between the various tasks in a concurrent application, and in the Credit scheduling strategy, not according to the concurrent application execution while at the same time, leading to spend more execution time for task is running synchronous operation. In Tseng et al. Methods proposed for VCPU of concurrent application, attached Turbo priority when scheduling phase, along with the Turbo's VCPU move to the top of the run queue to perform. However, Credit and Tseng et al. Methods are all the more time-consuming methods of operation (insert, delete, search). We propose the use of Linux kernel 2.6 version used CFS (Completely Fair Scheduler) scheduling methods to improve the problem of Credit generated, and by mechanisms to reduce the gap between the VM and the other VM. CFS may be a more equitable distribution to the CPU time, and RB-Tree is based on the concept of operations, allowing fewer tasks to be performed, there is a higher probability of being executed by the processor priority to, and in VCPU of concurrent processing, through the mark and set the concurrent wait queue, also reached a VCPU of concurrent synchronization problems. In our experiments and comparison, using the NAS Parallel Benchmark programs offered to do the experiment, the right to perform in a VM and VM weight gradually adjusted so that Virtual runtime in RB-Tree in a decrease for the chance to pick VCPU. At last, the execution time to obtain statistical performance changes. The results can be seen in the Credit, Tseng et al. compared with our strategy indeed significantly reduce the execution time, and substantial increase in concurrent virtual machine under the overall performance. |
第三語言摘要 | |
論文目次 |
第一章、緒論 1 1.1論文簡介 1 1.2研究動機 3 第二章、背景知識與相關研究 4 2.1 Virtualization 4 2.1.1 Full Virtualization 5 2.1.2 Para-virtualization 7 2.2 KVM[6] 9 2.3 Xen[4] 11 2.4 CPU Scheduling strategy 13 2.4.1 Credit[13] 14 2.5 Tseng et al.'s Method[15] 17 2.5.1比較與討論: 19 2.6 NAS Parallel benchmark 20 2.7 問題定義 23 第三章、我們的新排程演算策略 26 3.1 Completely Fair Scheduler(CFS) 26 3.1.1 Virtual Runtime 26 3.1.2 RB-Tree 28 3.2 新增our_sched 30 3.3 Our Method 33 3.3.1 Scheduling skeleton 33 3.3.2 Insert vcpu to RB-Tree 35 3.3.3 Update_tick 39 第四章、實驗與比較 44 4.1 實驗環境與測試工具 44 4.1.1硬體配置 44 4.1.3測試程式 44 4.1.4測試架構說明 45 4.2 實驗結果 47 4.2.1實驗一 48 4.2.2實驗一說明 50 4.2.3實驗二 51 4.2.5實驗彙整與討論 58 第五章、結論 60 第六章、參考文獻 63 圖目錄 圖2-1、虛擬化前後比較。 5 圖2-2、Full Virtualization基本圖示 6 圖2-3、Native與Paravirtualized 之system call, hypercall關係 8 圖2-4、Para Virtualization基本圖示 8 圖2-5、基本Xen架構 12 圖2-7、Sorting前PCPU queue 18 圖2-8、Sorting後PCPU queue 18 圖2-9、Credit Scheduler在執行並行程式上可能的狀況。 25 圖3-1、The skeleton of the scheduling algorithm 33 圖4-1、Benchmark-LU在DomU與Hypervisor之間的執行關係 45 圖4-2、(Part 1-1)比較各演算法之間在執行LU的執行時間圖 49 圖4-3、(Part 1-2)比較各演算法之間在執行EP的執行時間圖 49 圖4-4、(Part 2-1)CON-VM weight=32時在不同演算策略下的執行時間比較圖 53 圖4-5、(Part 2-2)CON-VM weight=512時在不同演算策略下的執行時間比較圖 53 圖4-6、Credit scheduler與Turbo及Ours演算策略的speedup比較圖 56 表目錄 表4-1、Benchmark參數表(LU與EP)。 45 表5-1、Credit、TURBO與Ours的做法比較 61 |
參考文獻 |
[1] VMware Virtualization Software. http://www.vmware.com/tw. [2] Virtualization. http://en.wikipedia.org/wiki/Virtualization. [3] Virtualization Spectrum. http://wiki.xen.org/wiki/Virtualization_Spectrum [4] D. Chisnall, "The Definitive Guide to the Xen Hypervisor", Prentice Hall, November 19, 2007. [5] P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, A. Warfield, "Xen and the Art of Virtualization", SOSP '03 Proceedings of the nineteenth ACM symposium on Operating systems principles, pp. 167-177, Dec 2003. [6] Kernel Based Virtual Machine. http://www.linux-kvm.org. [7] L. Cherkasova, D. Gupta, A. Vahdat, " Comparison of the Three CPU Schedulers in Xen.", ACM SIGMETRICS Performance Evaluation Review, pp. 42-51, Sep 2007 [8] K. J. Duda, D. R. Cheriton, "Borrowed-Virtual-Time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler", ACM Symposium on Operating Systems Principles, pp. 261-276, Dec 1999 [9] NAS Parallel Benchmarks. http://www.nas.nasa.gov/publications/npb.html. [10] H. Jin, M. Frumkin, J. Yan, "The OpenMP implementation of NAS parallel benchmarks and its performance", NAS Technical Report, NAS-99-011, October 1999 [11] C. Weng, M. Guo, Y. Luo, M. Li, "Hybrid CPU Management for Adapting to the Diversity of Virtual Machines", in IEEE Transactions on Computers, April 2012 [12] D. Gupta, R. Gardner, L. Cherkasova, "XenMon: QoS monitoring and performance profiling tool", Hewlett-Packard Laboratories Labs Technical Reports, HPL-2005-187, 2005 [13] Credit Scheduler. http://wiki.xensource.com/wiki/Credit_Scheduler [14] I. Molnar, Scheduler Core and Completely Fair Scheduler [CFS]. http://lwn.net/Articles/230501/. [15] C. Y. Tseng, S. C. Lin, L. C. Chen, and H. K. Chung, "The Performance Improvement and Evaluation of an Enhanced CPU Scheduler in Virtualized Environment," Proceedings of the 2011 International Conference on e-Commerce, e-Administration, e-Society, e-Education, and e-Technology (e-CASE & e-Tech 2011), pp.3107-3123, Jan. 2011 [16] L. Turbak , "Red-Black Trees" http://cs.wellesley.edu/~cs231/spring01/red-black.pdf [17] K. Adams, O. Agesen, "A comparison of software and hardware techniques for x86 virtualization", ASPLOS XII Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, pp. 2-13, Oct 2006. [18] Z. Haiyang, L. Qiaoyu, "Red-Black Tree Used for Arranging Virtual Memory Area of Linux", Management and Service Science (MASS) in 2010 International Conference, pp. 1-3, Aug 2010. [19] P. K. Hoong , O. Y. Shyang, " Red-black tree architecture for P2P media streaming ", TENCON 2013 IEEE Region 10 Conference (31194), pp. 1-4, Oct 2013. [20] E. G. Coffman, R. L. Graham, " Optimal Preemptive Scheduling on Two-Processor Systems ", Computers in IEEE Transactions (Volume:C-18 , Issue: 11 ), pp. 1014-1020, Nov 1969 [21] RB-Tree Time complexity, http://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_13spring/rb tree.pdf |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信