Research On Primary-Backup Based Fault-Tolerant Scheduling Algorithms For Cloud Computing

With the development of the Internet, the data transmission speed constantly continues to improve and the number of machines connected to the Internet becomes more and more tremendous. Customers'demands on the high-capacity and high-density computing are rising, so cloud computing which has lower prices and a super-computing capacity and efficient resource utilization came into being. With the production of cloud computing systems, the fault-tolerant capability of system has become increasingly important. In this paper, the main study is fault-tolerant scheduling algorithms of cloud computing based on primary-backup technique.The main work of this article includes the following aspects:Firstly, we introduce a new method for the division of tasks and endue each task which just arrived with a key degree. These tasks are divided into mission-critical and non-emergency tasks. We make use of ASAP (as soon as possible) algorithm to schedule the mission-critical primary task and ALAP (as later as possible) algorithm schedule the non-emergency task. On the basis of analyzing the characteristics of these two algorithms, we recover a new algorithm called CAS-AL (Integrated ASAP and ALAP) scheduling algorithm.When two or more processors are failure in a certain period time, in order to reduce this case influencing the results of the implementation of the task, put forward a new backup task scheduling technique called synchronization stagger-location scheduling technique. This technique takes into account not only all pre-tasks but also these tasks which are isochronous with the current task to limit where the backup of current task can be scheduled. And apply the technique to independent tasks, dependent tasks and dependent tasks with communication delays.After the synchronization stagger-location scheduling technique gives constraints of the backup tasks where can map, apply the concept of t boundary schedules to gain two scheduling algorithms which are the minimum replication cost scheduling algorithm and the earliest completion time algorithm for backup tasks. They consider replication costs minimized and the backup of current task at the earliest completion as the main objective, respectively.In this paper, we use a new communication model for communication between the processors. After finding a balance between replication cost minimized and the earliest completion time of the backup task, we get the backup tasks optimal scheduling algorithm. This compensates the drawback for the minimum replication cost scheduling algorithm and the earliest completion time algorithm for backup tasks which only consider the cost or time.Finally exerting through simulation analysis of experimental data, we find the advantages of the above-mentioned algorithms to traditional algorithms ASAP, ALAP and eFRD. The comparable criterions are separately from the task rejection rate, the replication cost and response time. In task rejection rate, CAS-AL is lower than ASAP and ALAP. MRCA is also lower than eFRD and ASAP on independent task. In the all algorithms, the BOSA is the best. In the replication cost, all three algorithms proposed in this paper are much less than eFRD and ASAP. In the response time, all three algorithms proposed in this paper are shorter than eFRD and ASAP on independent task, while on dependent task all algorithms are the same except eFRD.