Research On Fault-tolerant Scheduling Algorithm For Real-Time Tasks In Cloud Computing

As a new paradigm for providing computing service,cloud computing plays an important role in the area of information technology after more than ten years of intensive research and rapid development.Cloud computing is mainly based on distributed computing and virtualization technology to realize resource integration and sharing through dynamic resource management.Cloud computing provides services to users in the on-demand and scalable manner.Nowadays,more and more enterprises are deploying applications on cloud computing platforms.However,with the expansion of the cloud data centers,the probability of failure within the cloud computing system increases.The failure of computing resources may cause some tasks to violate the realtime requirements.Since cloud computing platforms need to provide users with high availability and reliability guarantees,fault tolerance has become an indispensable design requirement for cloud computing.Task scheduling is an efficient and feasible method for realizing fault tolerance.The primary/backup(PB)model based on task replication is a common fault-tolerant technology.In the PB model,each task is duplicated into a primary copy and a backup copy.These two copies are assigned to different computing nodes to realize fault tolerance.Fault-tolerant methods based on the PB model have been extensively studied in traditional distributed systems.However,these fault-tolerant methods cannot be applied in the cloud environment due to the virtualization feature of cloud computing systems.To address this issue,this thesis considers the virtualization and scalability features of cloud computing,and studies various types of real-time tasks.Fault-tolerant scheduling algorithms based on the PB model for real-time tasks in the cloud environment are proposed.The main work is as follows:(1)For real-time periodic tasks,a real-time fault-tolerant static scheduling algorithm FTPC based on cloud computing is proposed.The FTPC algorithm is oriented to the heterogeneous virtualized cloud environment.The periodic task model and scheduling model are designed.The task scheduling constraints in the cloud environment are analyzed.The fixed priority is based on rate-monotonic.Schedulability test is designed based on the worst-case response time.The active backup deallocation and passive backup overloading are utilized to reduce the resource redundancy caused by fault tolerance.The failure recovery process is analyzed.The algorithm can effectively reduce the computing resource occupation under different task loads.(2)For real-time dynamic independent tasks,a dynamic fault-tolerant energy-efficient scheduling algorithm EFTR is proposed.The EFTR algorithm includes three parts: global scheduling,local scheduling and resource expansion.The scheduling model includes a global scheduler,local schedulers and a resource manager.The global scheduler is responsible for sending the primary and backup copies of tasks to different virtual machines.The local scheduler is responsible for rearranging the local task queue in the virtual machine by advancing the primary copies and delaying the backup copies when any backup copy is deallocated.The resource manager is responsible for extending the cloud computing resources by adding or migrating virtual machines when computing resources are insufficient.In the process of task scheduling,the task allocation constraints and backup overlapping conditions are analyzed in detail to ensure the schedulability of the tasks.In addition,the EFTR algorithm uses a proactive virtual machine creation strategy to improve the overall processing capacity of the system.(3)For real-time static independent tasks,a static fault-tolerant energy-efficient scheduling algorithm EFTP is proposed.The EFTP algorithm utilizes the backup overlapping technology to reduce the resources occupied by the backup copies.For the nearly unlimited cloud resource pool,the appropriate initial computing resources are selected by the resource estimation strategy,and the number of required virtual machines is calculated according to the task load,task deadline,and computing resource capacity.The computing resources are adjusted in an iterative manner according to the task scheduling results.For the selected computing resources,the particle swarm optimization algorithm is used for task allocation.The allocation result is guaranteed to meet the constraints of backup overlapping considering relationship between the virtual machine and the physical host.Under the premise of ensuring the real-time requirements of tasks,the system energy consumption is minimized.(4)For real-time workflow,a workflow static scheduling algorithm FTWP is proposed.For the first time,the task relationships in workflow are defined and divided into dependent,semiindependent and independent relationships.The task allocation and overlapping constraints of workflow scheduling are analyzed in detail.The constraints of backup overlapping are supplemented.In order to reduce the system energy consumption,the FTWP algorithm uses the particle swarm optimization algorithm to globally optimize the task allocation scheme with the deadline as the constraint.Meanwhile,in order to ensure the efficient utilization of resources,the adaptive resource adjustment strategy is used to adjust the number of virtual machines.In the end,the main contributions and defects of this thesis are concluded.Advices are given on the future research.