Research On Virtual Machine Scheduling For Real-time Applications

With the development and popularization of computer,the research focus has shifted from the performance of single computer to other features of computing environment,such as convenience,flexibility,reliability,ease of use,energy saving,and so on.The traditional computer environment,which is made up of all units by hardware,can't meet the requirement of these changes.The Virtual Machine Monitor(VMM)decouples the application programs and computer hardware,which leads to greatly increased flexibility,reliability and convenience of computer environment.It meets the requirement of diverse computing purposes.This technology has become the main approach to construct the computing environment and been widely recognized and used.Because of the VMM,semantic gap is raised between the requirement of application programs and the scheduling of resource,which results in some new problems in the usage of virtual machine in some fields,especially in the real-time application,such as the requirement of low delay of I/O response,the guarantee of real-time task deadline,the ratio of CPU usage of real-time applications,the support of concurrent tasks execution efficiency,multi real-time virtual machines effectively scheduling in multi processors,etc.There are some limitations in the related researches.For example,there has been no effective scheduling algorithm so far in scheduling multi concurrent virtual machines in multi processors system.1)To solve these problems existing in the virtual machine in real-time applications,this dissertation researches the scheduling problems of Xen VMM.In terms of the I/O response delay,this thesis sets up the relationship among the biggest delay of the I/O response,the scheduling time slice and the number of VCPUs,and raises the dynamic scheduling time slice strategy by the study and formal analysis of the process of Credit scheduling algorithm.Based on the round robin scheduling process,we present the non-uniform scheduling time slice self-adaption scheduling algorithm which is named Dynamic Time Slice Credit(DTSCredit).In the new algorithm,the self-adaption module adjusts the scheduling time slice according to the parameters of I/O event and number of VCPUs which are collected by the I/O monitor module.In this way,the maximum of delay of I/O response can be limited.Based on the preemptive scheduling mechanism,we also presents the priority preemptive dynamic scheduling time slice scheduling algorithm which is named Self-Adapt Credit(SACredit).In this algorithm,the corresponding VCPU of the I/O event can be boosted when the I/O event comes and the scheduler schedules this VCPU to preempt the current VCPU so that the I/O event can be responded as soon as possible in the CPU intensive virtual machines,which is similar to the scene of that in I/O intensive virtual machines.2)Based on the Credit resource allocation,the dissertation studies the key matters of concurrent VCPU scheduling in multi processors,suggests the mechanism of synchronous queue according to the resource updating,and realizes the concurrent virtual machine synchronous scheduling algorithm which is called Parallel Schedule Algorithm(PSA).Compared to the original Credit scheduler,the Balance scheduler and the Urgent VCPU First(UVF)scheduler,this new scheduling algorithm has better performance of scheduling the concurrent virtual machines.In order to meet the requirement of scheduling the parallel soft real-time virtual machine,we further presents the Parallel Soft Real-Time Scheduling Algorithm(PSRTSA).In this new scheduling algorithm,the non-work-conserving model is introduced to schedule the VCPUs of parallel soft real-time virtual machine.The ratio of CPU usage of real-time virtual machine is allocated in the way of absolute ratio.The performance of the new algorithm is better than the parallel soft real-time scheduling algorithm,Poris,especially when the workload of the system is dynamic.In order to schedule the parallel and non-parallel real-time virtual machines at the same time,we still present the Soft Real-Time Scheduling Algorithm(SRTA).The real-time priority of SRTA has been refined,and the period of running is devided into multi sections which reduce the effect of scheduling delay of real-time virtual machines.This scheduling algorithm can schedule the parallel real-time virtual machine correctly,and at the same time,the non-parallel real-time virtual machine can be scheduled appropriately.The performance of the SRTA in scheduling the parallel and non-parallel real-time virtual machine is much better than other existing schedulers.3)Scheduling algorithm of real-time applications in multi-processor system is always the focus of the scheduling researches in real-time scheduling,but the research of scheduling real-time virtual machine lags behind.So the dissertation,based on the real-time scheduling and concurrent scheduling,proposes the Gang Earliest Deadline First(Gang EDF)scheduling algorithm.According to the formal proof of schedulable judging,the algorithm schedules the parallel VCPUs in Gang manner and determines the real-time priority with EDF strategy.The non-real-time virtual machines are scheduled in the backfilling manner which schedules the non-real-time virtual machine in the interval of real-time virtual machine scheduling.The new algorithm can satisfy the scheduling of real-time virtual machine and ensure the efficiency of the system.The evaluations of the prototype in Xen prove the validity and usability of the algorithm.Compared to other real-time scheduling algorithms of multi-processor,the new algorithm not only satisfies the deadline of the real-time virtual machine but also has an obvious advantage in the efficiency of scheduling parallel virtual machine.