Research On Online-Min-Min Algorithm For Grid Task Scheduling

Grid is one kind of distributed computing whose main features are resource sharing and task coordination. It is a virtual "super computer" integrated by hardware and software resources which connected through Internet or private network, these resources maybe geographically distributed, heterogeneous or dynamically. The "super computer" can provide high-performance services such as computing, storage, management, etc.The chief research contents of this thesis are algorithms and model of Grid task scheduling. The research achievement and innovation of this thesis mainly include the following two points:(1). A new priority-based Online-Min-Min scheduling algorithm is proposed aim at the defect of serious load imbalance of the Min-Min algorithm. The Online-Min-Min algorithm abolish some assumptions of Grid task scheduling, adopt on-line scheduling model to accommodate the dynamic variation of Grid environment. The Online-Min-Min algorithm reduce the time complexity of scheduling algorithm and cut down the average time of task schedule compared to batch Min-Min scheduling algorithm; it also introduce the strategy of task priority so we can management the tasks dynamically; the resource reservation mechanism which allows more than one tasks mapped to the same resource at the same time was improved, so the Online-Min-Min algorithm have a better load balance features. Online-Min-Min algorithm and static Min-Min algorithm are simulated respectively use GridSim toolkit, the simulation results show that the Online-Min-Min algorithm reduce the average time of the task scheduling evidently, and improve the load balance of task scheduling. (2). Based on the analyze of the difference between centered Grid scheduling model and distributed Grid scheduling model, we can conclude some defects of centered Grid scheduling model:the failure of a single point may cause tremendous jeopardize to the whole system, load imbalance, low scalability, can't adapt to the heterogeneous of Grid, scheduling algorithm inflexible, etc. So a new distributed Grid scheduling model was proposed which divide the Grid into multiple domains according to the characteristics of tasks and resources. Each domain has an independent grid scheduler, and the schedulers of different domains can cooperate with each other when some tasks need to be scheduled to resources in a different domain, which can achieve the inter-domain load balance. The distributed Grid scheduling model can effectively disperse and balance the load on the grid and reduce the load of central node, improve the robustness of system. The distributed scheduling model can also employ different scheduling policy and scheduling algorithm in different domains to meet the diversity of resources and tasks. The Online-Min-Min scheduling algorithm is applied in the distributed scheduling model, the combination of dynamic scheduling algorithm and the distributed models further improved the scheduling efficiency and load balancing, and reflect the dynamic, autonomous, and heterogeneous of the Grid. By comparing the simulation results of the distributed scheduling model and centered scheduling model respectively, the advantages of the distributed scheduling model in task scheduling efficiency and system scalability can be fully demonstrate, and will have a great research value and application platform.