Research On Algorithms Of Scheduling Confliots Detection And Control For Large-Scale Server Cluster

Shared-state scheduling is a kind of server cluster resource management and scheduling architecture.It decouples resource management and task scheduling and uses multi scheduling agents to schedule jobs in the cluster to resolve the scalability limitation of monolithic schedulers.So it has been well applied in large-scale server cluster.However,the conflict detection algorithms in this architecture are monotonous and inflexible.In addition,it also has the issue of scheduling performance deterioration which is caused by scheduling conflicts in high-load situation.So,this thesis makes a thorough study of shared state scheduling and proposed related solutions to address these issues.This thesis focuses on three major results: the research of scheduling architecture in large-scale server cluster,the research of conflict detection algorithm and scheduling related algorithms in shared-state schedulers.The contributions of this paper are as follows.1? This thesis proposed a parallel validation-based shared-state scheduler(PVBSSS)architecture.PVBSSS adopted multi scheduling agents to concurrently make scheduling decisions through shared resource available information.Then PVBSSS used conflict detection algorithms to solve conflicts between these concurrent scheduling decisions.For concurrent scheduling decisions of different type of workload,PVBSSS supported the adoption of different conflict detection algorithms to solve conflicts.So,combined with the scheduling requriments of two currently common workloads in server cluster,this thesis proposed two conflict detection algorithms: parallel coarse-grained conflict detection algorithm and parallel fine-grained conflict detection algorithm.The experimental results,which is carried out under OCSS(Omega Cluster Scheduler Simulator)platform with tens of thousands of server clusters and nearly daily millions of jobs,showed that PVBSSS can efficiently schedule large number of jobs and the two conflict detection algorithms can detect more harmful conflicts than original fine-grained conflict detection algorithms with less sensitive for the scheduling decision time.Therefore PVBSS can be better adapted to the application environment of the coexistence of different scheduling strategies.2? This thesis proposed a multi attributes fusion conflict detection algorithm.For batch task,this method firstly built the multi attributes model of it,then used D-S fusion rules to fuse the values of multi attributes to one value which represent the importance of task,finally through controlling the decision of conflict to optimize the scheduling performance of batch jobs.Besides,this method set the weight of fusion by two ways: subjective assignment and the weighted average evidence composition method.The experimental results showed this algorithm can improve the performance of scheduling for batch jobs.3? This thesis proposed three algorithms to prevent and control scheduling conflicts in PVBSSS: batch sampling scheduling algorithm with conflict prevention function,conflict prevention batch sampling scheduling algorithm based on opportunity cost and admission control algorithm based on random early detection mechanism.Except resource requirement and task constraints,batch sampling scheduling algorithm with conflict prevention function mainly consider the concurrency scheduling decisions occurring in cluster nodes.It plan to reduce conflicts through placing tasks to the node with least concurrent scheduling decisions.The theoretical and experimental analysis of this algorithm showed that it can significantly reduce conflicts.Conflict prevention sampling scheduling algorithm based on opportunity cost placed tasks by considering many factors such as machine marginal cost,conflicts and so on.Then,the experimental results showed this algorithm can balance the goals of load balance,reducing the stranded resources and conflict prevention,and was more suitable for complex scheduling environment.As the last algorithm proposed in this thesis,admission control algorithm based on random early detection mechanism admitted jobs according by the real-time conflict situation.It addressed the scheduling performance deterioration issue that caused by admitting more job in high-conflict situation.The experimental results showed this algorithm is effective for controlling conflicts in high-loaded cluster.