Heterogeneous Cloud Resource Scheduling For Random Independent Tasks To Minimize Total Tardiness

Random independent task scheduling with soft deadline constraint in cloud computing is widely used in Mesos,Openstack,Kubernetes and other architectures or application scenarios.To ensure the quality of service,this kind of task should be completed before deadline,so as to minimize tardiness.It is a challenging NP-hard problem to reasonably schedule a set of randomly arrived tasks in order to minimize the total tardiness of these tasks in heterogeneous cloud environment.This thesis proposes a Two-Stage Scheduling Framework with Feedback(TSSF)that minimizes total tardiness of random independent tasks in the heterogenous cloud where the two stages refer to the central scheduling layer and the node scheduling layer.The central scheduling layer is composed of the central scheduler and re-scheduler.The central scheduler pre-allocates tasks to each virtual machine(VM)to improve the resource utilization of cluster.The task is migrated through the re-scheduler to rebalance the workload of each VM and reduce the waiting time of tasks.The node scheduling layer is responsible for the execution order of tasks on VM,and adopts an emergency priority strategy to execute tasks in order to reduce total tardiness of tasks.The central scheduling layer and the node scheduling layer cooperate to minimize total tardiness.For the central scheduler,we propose the Random Allocation Algorithm,the Processing-Rate based Numbering Sequence Algorithm,and the Minimum Variance of Resource Utilization Algorithm.For the node scheduler,we propose the Workload-based Dynamic Priority Algorithm,the Deadline-based Dynamic Priority Algorithm and the Laxity-based Dynamic Priority Algorithm.For the rescheduler,we propose the Task Count Balanced Rescheduling and the Workload Balanced Rescheduling.The proposed TSSF has a loosely coupled layered structure and feedback mechanism,which balances the workload of each VM in the cluster to ensure high resource utilization and high execution efficiency of the cluster.The experimental environment is Cloudsim simulation platform.The configuration of cluster and task parameters is simulated by analyzing the google trace dataset.The experimental results show that the Minimum Variance of Resource Utilization Algorithm has the best performance in the central scheduler.The Laxity-based Dynamic Priority Algorithm in the node scheduler is the best algorithm.The Task Count Balanced Rescheduling is similar to the Workload Balanced Rescheduling.At the same time,the experimental results show that TSSF has a more obvious optimization performance when the cluster task is crowded.In addition,this paper compares TSSF with the existing scheduling algorithms,including Minimum Link Counter Scheduling and Auto-scaling algorithm base on Resource Prediction.The result shows that TSSF is better than these two existing scheduling algorithms.