A Study On Grid Dependent Tasks Recheduling Based On Resource Dynamic Evaluation

Grid is a kind of infrastructure that could integrate geographically dispersed resources. It could connect all kinds of information resources as a whole, and provide each user transparent integration services, including computing power, data storage capacity as well as various applications. Grid resources are distributed on the dynamic Internet environment, with special natures of heterogeneous, dynamic and self-governing. On different grid resources, the task's performance is different. Thus, to achieve the overall performance of a grid application composed by a set of tasks, task scheduling is needed to assign the suitable resource for each task. In grid task scheduling problem, dependent tasks scheduling problem has been widely concerned. In dependent tasks scheduling problem, an assignment for one task may affect the other task's assignment. Therefore, to achieve the overall optimal performance or grid application, global optimization scheduling policy is needed, which relies on the anticipated information of the application and resources, and makes the total schedule before application starts to run according to the time arrangement and resource assignment in the schedule. Because of the dynamic nature of grid resource, resource's performance and availability will change very often and at any time. So during grid application running-time, the resource will change, and affect the optimum of the application's performance. Therefore, dependent tasks rescheduling is needed, to adjust the schedule for the application's optimal performance.To optimize application performance, global-optimization rescheduling policy and resource-change-trigger rescheduling method are needed for grid dependent tasks rescheduling, which lead to two difficulties:low rescheduling efficiency and frequently trigger. To address the above two difficulties, the paper presents a grid dependent tasks rescheduling mechanism based on resource dynamic evaluation, beginning with the rescheduling task scope identification, resources reduction, resources stability promotion and useless rescheduling avoiding problems. With the foundation of resource dynamic evaluation, and supported by the view-based resources organization model, rescheduling trigger mechanism and rescheduling tasks spread domain computing, the mechanism could make full use of resources with weaker dynamic and reasonably narrow the rescheduling task scope and trigger the rescheduling process at the right time to solve the low rescheduling efficiency and frequently trigger. problem. This paper completes the following main tasks:(1) To solve the difficulties of low rescheduling efficiency and frequently triggering faced by current rescheduling approaches, this paper studies grid dependent tasks rescheduling mechanism based on resource dynamic evaluation (G-DERM) and proposes resource dynamic evaluation model. Such model can evaluate the performance and changing cycle of single grid resource and resource environment. Based on resource dynamic evaluation, G-DERM can trigger the rescheduling process at the right time, make full use of dynamic resources with weaker dynamic and reasonably narrow the rescheduling task scope to solve the low rescheduling efficiency and frequently triggering problem.(2) To solve the problems of reducing the number of resources and improving the stability of candidate resources, this paper studies the view-based resources organization model. Such model is a three-layer structure for organizing resources which is established based on application requirement as well as resource dynamic evaluation. Such model can filter out high dynamic resources with similar performance for certain application. Based on such model, the stability of candidate resources for rescheduling can be enhanced. Thus, the rescheduling efficiency can be promoted and triggering frequency can be slowed down.(3) To solve the problem of avoiding useless rescheduling problem, this paper studies rescheduling triggering mechanism and proposes hierarchical rescheduling triggering rules. Through making use of the resource dynamic evaluation results and analyzing the resources changes'impact on application performance, these rules can determine whether to trigger rescheduling process, identify triggering time and delay triggering rescheduling process due to the estimation with low accuracy of task's execution time on resources. Thus, the number of useless rescheduling processes can be reduced and the triggering frequency of rescheduling processes can be slowed down.(4) To solve the problem of determining the scope of rescheduling tasks, this paper studies the rescheduling tasks spread domain and its computing algorithm. Based on resource environment dynamic evaluation results and task finish time estimation, through judging whether the task finish time is in the resource environment change cycle, the rescheduling process will not consider the tasks whose finish time is beyond the resource environment change cycle. Rescheduling tasks spread domain is computed according to the tasks' point-relationship, dependence-relationship and connection-relationship. Thus, the tasks scope can be narrowed and the rescheduling efficiency can be promoted with litter affecting the optimization of grid application performance. (5) To solve the problem of improving the rescheduling efficiency and optimization, this paper studies the G-DERM based grid dependent tasks rescheduling model and algorithms. This paper propose a DAG based rescheduling model and improved HEFT algorithm, as well as a T-RAG optimal selection based rescheduling model and immune genetic algorithm. Thus, the rescheduling efficiency and optimization performance can be ensured.(6) To solve the problem of verifying the effectiveness of proposed resource dynamic evaluation based grid dependent tasks rescheduling mechanism, this paper establishes a G-DERM simulation environment and conducts a set of experimentations to verify the better performance of the proposed rescheduling triggering mechanism, rescheduling tasks spread computing algorithm, and resource organization model in improving the efficiency of rescheduling and slowing down the triggering frequency.