Hierarchical scheduling strategies for parallel tasks and advance reservations in grids

Recently, the advance reservation functionality gained high importance in grids due to increasing popularity of modern applications that require interactive tasks, co-allocation of multiple resources, and performance guarantees. However, simultaneous scheduling, both advance reservations and batch tasks affects the performance. Advance reservations significantly deteriorate flow time of batch tasks and the overall resource utilization, especially in hierarchical scheduling structures. This is a consequence of unknown batch task processing times and the lack of possibility of altering allocations of advance reservations. To address these issues we present a common model for scheduling both computational batch tasks and tasks with advance reservation requests. We propose simple on-line scheduling policies and generic advices that reduce negative impact of advance reservations on a schedule quality. We also propose novel data structures and algorithms for efficient scheduling of advance reservations. A comprehensive experimental analysis is presented to show the influence of advance reservations on resource utilization, mean flow time, and mean tardiness-the criteria significant for administrators, users submitting batch tasks, and users requesting advance reservations, respectively. All experiments were performed with a well-known real workload using the GSSIM simulator.