Reserve Collaborative Algorithm Research Based On Resource Fragments

Resource advance reservation is a core technology to guarantee the quality of service in distributed systems. However, in the process of reserving resources for grid users, the entire resources will be cut into discontinuous small pieces of resource fragmentation, the formation and existence of which can reduce the resource utilization rate and job-acceptance rate. In jobs scheduling process with constrained deadline, we arrange different available resources for different jobs and different scheduling schemes have different generated resource fragments, which will have different effects on the acceptance rate of following tasks. So, we can effectively improve the job acceptance rate and resource utilization rate through the optimization of the scheduling schemes.This paper first studies the history and current situation of co-allocation reservation technologies, analyzes the reasons of resources fragments formation in single processor and multiple machines grid environment, and discusses the effects on the job-acceptance rate and resource utilization rate with different scheduling schemas. Based on the above analysis, this article proposes a new quantitative approach with the consideration of the fragmentation of resources by the schedule of current job. And then gives resource fragments different weights according to their sizes and the ability to accept new jobs. According to the quantitative approach, we proposed the Fragment-aware Selection Best Fit (FSB) algorithm and Fragment-aware Selection Worst Fit reservation (FSW) algorithm. Simulation experiments are adopted to verify the performance of the two algorithms.The simulation experiments are controlled by four parameters, job flexibility, job’s average duration, system load and resource number. We can see the performance of algorithms by their acceptance rate, resource utilization and job’s average slowdown. In the experiments, we compared the performance of FSB and FSW with the Best Fit, First Fit, Min_LIP and Min_TIP algorithms. Simulation results and analysis showed that the FSW and FSB algorithms can achieve higher job acceptance rate under heavy system loads. FSW has better performance on job acceptance rate than FSB. But the performance of FSW on average slowdown and resource utilization is worst then FSB.