Research On Job Scheduling And Reousrce Allocation In Multi-Clusters Grid And Computational Market

Grid is a new type of information technology infrastructure based on the Internet, which goal is seamlessly integrating wide area resources to solve problems and achieve the comprehensively sharing of computing resources, storage resources, communication resources, software resources, information resources and knowledge resources. The traditional job scheduling method is ineffective for the distributed, heterogeneous, dynamic, and autonomous resources in the Grid.Firstly, the dissertation introduces the concept, evaluation and classification of Grid computing. After analyzing the main problems in grid job scheduling, Chapter2 recalls theory of scheduling and clarifies the new features in grid scheduling, i.e., large-scale heterogeneous machine, dynamic and unreliable environment and user-centric objective. In particular, the research focuses on the two kinds of grid environment named Multi-Clusters and Computational Market. The "Global-Local" 2 stage method is taken for the Multi-Clusters scheduling; while the distributed bi-directional choosing mechanism is adopted for the Computational Market.Resource monitoring is the basis of multi-cluster scheduling and needs to solve issues of heterogeneity and scalability. Chapter3 proposes a self-description method for common representation of heterogeneous resources information. A universal resource monitoring system is implemented based on monitoring tools such as Ganglia, GridView, and PBS, etc. An adaptive RTT-aware MST algorithm is designed to improve system scalability. Experiment shows this method reduces intrusive overhead and improves real-time ability.After that, Chapter 4 proposes and implements the "Global-Local" 2 stage super-scheduler model. Aiming at computing intensive applications, this chapter presents a QoS-aware batch-mode scheduling algorithm. The algorithm is used in the global queue scheduling. Compared to traditional batch-mode scheduling algorithm, it proves to be with equal throughput of system but with improved in-time complete ratio. This algorithm also presents nice adaptability under prediction error of task execution time.Chapter 5 focuses on the incentive mechanism with combination of market and trust. By integrating the trust notion into Grid Market Model, the dissertation introduces the Grid Trust Aware Resource Transaction Model (G-Tart), and describes design ideas, the entities, components and the transaction flow in the model. The trust is set as an important metric measuring the reputation of peers in the market transactions, which can not only stimulate peers to obey the transaction contract, but also provide an incentive for honest service providers. This raises two key issues: how to select appropriate resources and how to accept proper jobs?Thus Chapter 6 proposes a trust-filtered approach is for resource selection to bridge this gap. This approach first filters most of the lower-trust resources basing user's trust demand. To the remaining resources above demand, it then uses a minimal opportunity-cost algorithm to guide the judgment. Its main idea is to takes both of price and risk into considerations. Simulations show the approach gives two-fold incentives. It effectively guarantees profit of reliable resources, reduces job failure rate and saves cost 8%～10% averagely.Chapter 7 investigates a market-based task service in Gird environment. From providers' standpoint and basing on relative information provided by users, the provider computes sunk cost and opportunity cost if receiving the task to maximize itself profit. The experiment shows that the scheduler further reduces the cost of resources providers and improves their profit.Finally, based on the G-Tart model, Chapter 8 presents a distributed resource scheduling system for grid environment using supply and demand theory. The Oppsim is implemented to facilicate the system simulation. The system provides a bi-directional choosing mechanism and a QoS guaranteeing mechanism for users and resources to supervise them heuristically. The simulation result of the system shows that the system is scalable, flexible, and capable of handling load balance well. Meanwhile it guarantees QoS of tasks. Task Accomplishment ratio is greater than that in Nimrod/G by 22.5%.By analyzing the characteristic of grid such as large-scale, heterogeneity, unreliability and user-centric, the dissertation gives deeply analysis and beneficial practice on two typical grid environment. It is very useful of the "Global-Local" 2 stage method for the Multi-Clusters scheduling. Meanwhile the dissertation proposes the G-Tart Model which organically combines the market mechanism and trust mechanism, and the incentive-driven distributed scheduling methed shows the brand new view and fine perspective for the future of the grid.