Deadline For Advance Reservation-based The Package Task Scheduling Constraints

Grid has the ability to integrate geographically distributed resources, either heterogeneous or homogeneous, and manage these resources uniformly, which lead to the birth of super computer. As a special kind of parallel job, Bag of tasks has become a grid hotspot and has been used in various fields. By adopting advance reservation technology, Bag of tasks, with deadline requirements, can be ensured to access appropriate resources when execution time arrives.There are seven classical scheduling algorithms for parallel jobs, First_fit, PE_bestfit, PE_worstfit, Duration_bestfit, Duration_worstfit, PEDuration-bestfit and PEDuration_worstfit. Although these algorithms are widely used in many areas and easy to implement, they ignored the impact of job placement on free resources, which results in low resource utilization. Based on existing technology of Bag of tasks scheduling and grid resource management, the seven algorithms mentioned above are analyzed and a new algorithm, ISC, useful in improving job scheduling curve smoothness, is proposed.The newly proposed algorithm, ISC, gives a method to distinguish and handle useable resource fragment and useless resource fragment. When scheduling resources for Bag of tasks, ISC calculate the curve smoothness firstly, according which the algorithm will select suitable resources for tasks. Meanwhile, resource fragment generated in resource scheduling will be handled according to proposed measure standard of resource fragment.Based on the study of Bag of tasks, workflow scheduling, a special Bag of tasks, is studied in this paper and a new algorithm which aims to integrate resource fragmentations is proposed. Simulation experiments are designed to verify the new algorithm and the five previous resource selection algorithms. Simulation results proved the advantage of new algorithm in resource utilization and local job acceptance rate.The main innovation of this paper lies on:(?) Proposed a method to distinguish and handle useable resource fragment and useless resource fragment.(?) Proposed the concept of curve smoothness and gives calculation method.(?) Taking into account of the impact of reserved tasks on waiting for reservation tasks and proposed ISC algorithms, which can improve tasks'schedule curve smoothness.(?) To deal with resource fragmentation produced in scheduling, IRP-WF which focuses on moving and integrating resource fragmentation is put forward.