在此篇論文中，我們提出一個在虛擬機器上運作的即時排程器設計 (MSC-RTS)，此設計著眼於解決在傳統虛擬機器系統中因為處理器資源以及週邊裝置被許多作業系統共享而導致的整體I/O效能低落以及過長的反應時間等問題。不同於傳統先進先出的排程方式，此即時排程器使用多重具有不同優先權的排程序列來保證即時任務能夠在虛擬機器系統中運行。詳細的排程器設計，包括排程器架構、各種排程方式的運作、分析，都將在論文中被一一提出。在分析的部份，我們提出一個雙重序列的M/M/1/K/K排程系統模型來描述不同服務類型的虛擬機器在此即時排程器中的運作情況。我們可藉由此模型預估虛擬機器的平均反應時間以及處理器使用率。但是由於實際上系統使用的共享週邊裝置的機制與模型上的差異，以及測量方式上的限制，使得預期結果會與實際量測值有所誤差。
此外，我們實作了此即時排程器，並且設計了一套實驗來驗證此即時排程器的效能。在實驗中我們將展現此排程器具有能夠支援即時任務的運行、快速的反應時間、可調整以用於不同狀況、可預測的行為等特性。在現在虛擬機器發展中僅有少數類型的服務系統能在虛擬機器系統上運行。尤其以即時性服務系統來說，在現有虛擬機器系統上即時性服務系統無法保障其服務品質。但是隨著硬體技術的發展，在虛擬機器系統上同時運行各種同質性以及異質性服務的需求將逐漸浮現。所以我們相信此即時排程器設計能夠幫助虛擬機器技術的發展，讓不同性質的服務系統能在虛擬機器系統上同時運行，並能夠保障各服務系統所需的服務品質，使得虛擬機器的用途更加廣泛。

In this paper, a multiple-service-classes real-time scheduler (MSC-RTS) designed for virtual machine (VM) is proposed. In traditional VMs, low throughout and long response time are the typical problems encountered due to the sharing of processor time and I/O peripherals among VMs. Instead of classic first-in-first-out task scheduling, a priority-based multiple queuing design is proposed to ensure the executions of real-time tasks. The details of the proposed scheduler are presented, including scheduler modeling, operations, analysis and performance evaluation. In analysis, the proposed mathematical model is composed of two M/M/1/K/K queues to characterize the dynamics of the multi-class VM services. Through the constructed mathematical model, average response time and processor utilization are primitively estimated. However, there is error between estimation and practicality. After the investigation, there are two possible factors of estimation errors: First, the practical system uses split I/O model to share I/O devices among VMs, and this causes the difference between the practicality and the model. The other factor is the limitations from estimating methods. Except to the mathematical analysis, a real-case implementation is also presented; the experimental results demonstrate valuable features of the proposed schedule, including (1) the great improvement of the scheduling-induced delay (SI-Delay) of real-time tasks, (2) fast response time (3) feasible software approach (4) predictable behaviors. As the hardware technology evolving, the computation with multiple homogenous/heterogeneous VMs has become one of significant issues in computer science. The developed scheme is the key to prompt the VM efficiency, in particular, for the applications with high real-time demand, such as multimedia services.

[ALL78] Arnold O. Allen, “Probability, Statistics, and Queueing Theory with Computer Science Applications Second Edition”, Academic Press, Inc., Orlando, FL, 1978.
[BAR03] Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, Andrew Warfield, “Xen and the Art of Virtualiza-tion”, Proceedings of the nineteenth ACM symposium on Operating systems principles, Oct. 2003.
[BEL05] Fabrice Bellard, “Qemu, a fast and portable dynamic translator”, Proceedings of the 2005 USENIX Annual Technical Conference, April 2005.
[CHE04] Ren-Hao Cheng, Po-Cheng Huang, Mong-Fong Horng, Jiang-Shiung Ker and Yau-Hwang Kuo, "A Two-stage Queuing Approach to Support Real-time QoS Guarantee for Multimedia Services in TDMA Wireless Networks", LECTURE NOTES IN COMPUTER SCIENCE 3331: 33-40 2004.
[CHE07] Lucy Cherkasova, Diwaker Gupta, Amin Vahdat, “Comparison of the 3 Schedulers in Xen”, Presentation on the Xen Summit 2007, April 2007.
[DOO06] Leendert van Doorn, “Hardware Virtualization Trends”, Second International Conference on Virtual Execution Environments, June 2006.
[FRA04] Keir Fraser, Steven Hand, Rolf Neugebauer, Ian Pratt, Andrew Warfield, Mark Williamson, “Safe Hardware Access with the Xen Virtual Machine Monitor”, Proceedings of the 1st Workshop on Operating System and Architectural Support for the on demand IT InfraStructure, Oct.2004.
[GOL73] R. P. Goldberg, “Architecture of virtual machines”, Proceedings of the work-shop on virtual computer systems, 1973.
[GOV07] Sriram Govindan, Arjun R. Nath, Amitayu Das, Bhuvan Urgaonkar, Anand Sivasubramaniam, “Xen and co.: communication-aware CPU scheduling for consolidated xen-based hosting platforms”, Proceedings of the 3rd international conference on Virtual execution environments, June 2007.
[HOR04] Mong-Fong Horng, Yau-Hwang Kuo, Jang-Pong Hsu, Ren-Hao Cheng, “Adaptive Slot Allocation to Control Queuing Delay in TDMA Wireless Base Station”, Journal of Information Science and Engineering, vol. 20, no. 5 , pp. 845-868, Sep. 2004.
[ONG08] Diego Ongaro, Alan L. Cox, Scott Rixner, “Scheduling I/O in Virtual Machine Monitors”, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 2008.
[PRA05] Ian Pratt, “Xen Virtualization”, Linux World 2005 Virtualization BOF Presentation.
[ROS05] Mendel Rosenblum, Tal Garfinkel, “Virtual Machine Monitors: Current Technology and Future Trends”, IEEE Computer Society, May 2005.
[SIN06] Amit Singh., “An Introduction to Virtualization”, http://www.kernelthread.com/publications/virtualization/
[SMI05] James E. Smith, Ravi Nair, “The Architecture of Virtual Machines”, IEEE Computer Society, May 2005.
[SUG01] Jeremy Sugerman, Ganesh Venkitachalam and Beng-Hong Lim, “Virtualizing I/O Devices on VMware Workstation’s Hosted Virtual Machine Monitor”, Pro-ceedings of the 2001 USENIX Annual Technical Conference. 2001.
[UHI05] URich Uhlig, Gil Neiger, Dion Rodgers, Amy L. Santoni, Fernando C.M. Mar-tins, Andrew V. Anderson, Steven M. Bennett, Alain Kgi, Felix H. Leung, Larry Smith, “Intel virtualization technology”, IEEE Computer Society, May 2005.
[UME05] Hidenori Umeno, Masato Kiyama, Takafumi Fukunaga, “New Method for Dis-patching Waiting Logical Processors in Virtual Machine System”, Proceedings of the 29th Annual International Computer Software and Applications Conference, 2005.
[WHI02] Andrew Whitaker, Marianne Shaw, and Steven D. Gribble, “Scale and Performance in the Denali Isolation Kernel”, Proceedings of the 5th symposium on Operating systems design and implementation, 2002.