Application Oriented Real-time Task Scheduling On Multi-CPU Virtual Machine

Virtual machine can effectively improve the utilization of resources and reduce system management costs.Its good portability and isolation make it widely used in the modern military,industrial,scientific research and many other fields.However,with the constantly increasing real-time requirements of network application services,many applications running on the virtual machine are facing with the challenge of higher time precision in real-time performance.In order to ensure that real-time tasks are executed successfully within the deadline,the research of real-time scheduling algorithm becomes one of the hot issues in multi-CPU scheduling.In this thesis we summarize the basic principles of virtualization technology and KVM,and briefly describe the basic theoretical knowledge of real-time task scheduling.We focus on the real-time scheduling of multi-virtual machine system.The main contents and innovations of this thesis include the following three aspects.Firstly,the traditional task model cannot describe the implementation of real-time tasks in detail,for the general task has no strict requirements in time parameters.Besides,a single processor resource model cannot be directly applied to multi-CPU system resource scenarios.In the thesis,the real-time task model and the multiprocessor resource model are provided.The time constrains of real-time tasks are described by parameters such as the execution period and the relative deadline.The time constrains of processor resources are described by the rotation period and available resource time of each processor.The optimization target is to reduce the deadline miss ratio of real-time tasks.Secondly,the traditional multiprocessor real-time scheduling algorithm,for its fixed scheduling strategy to allocate CPU resources,cannot dynamically allocate the resources based on the usage of multiprocessor,which leads to a low resource utilization ratio and a high deadline miss ratio of real-time tasks.We present a multi-CPU real-time task scheduling algorithm--Adaptive Earliest Deadline First(A-EDF),which keeps the system load balanced,realizes the effective allocation and access of the system resources by comparing the required resources of real-time tasks with the available resources of multiprocessor,dynamically allocating the processor combinations based on upper task utilization,and dynamically migrating some urgent tasks on demand.To realize the scheme,we add the litmus patch to the Linux kernel and evaluate the performance of the proposed algorithm in Linux environment.Compared with the Partition Earliest Deadline First scheduling algorithm and the Global Earliest Deadline First scheduling algorithm,the experimental result shows that A-EDF can effectively reduce the deadline miss ratio of real-time tasks and improve the resources utilization ratio.Thirdly,the traditional real-time scheduling algorithms are limited to the fixed scheduling strategy.This makes it difficult for a single scheduling algorithm to adapt to the high real-time performance requirements of complex virtual machine systems.Based on the theory of compositional scheduling analysis,the computer system running the virtual machine is modularized and a multi-layer compositional scheduling structure is established,and the task demand interface and the resource supply interface are abstracted.We prove the constraints that the tasks and resources need to meet if the algorithm can be scheduled.Based on this,we deduce the task utilization bound of the proposed A-EDF algorithm and the traditional real-time scheduling algorithm P-EDF and G-EDF.We evaluate the performance of each compositional scheduling algorithm under the KVM environment,and the experiment result verified the correctness of the proposed compositional scheduling theory.