  Advance reservation is important to guarantee the quality of services of jobs
by allowing exclusive access to resources over a defined time interval on
resources. It is a challenge for the scheduler to organize available resources
efficiently and to allocate them for parallel AR jobs with deadline constraint
appropriately. This paper provides a slot-based data structure to organize
available resources of multiprocessor systems in a way that enables efficient
search and update operations, and formulates a suite of scheduling policies to
allocate resources for dynamically arriving AR requests. The performance of the
scheduling algorithms were investigated by simulations with different job sizes
and durations, system loads and scheduling flexibilities. Simulation results
show that job sizes and durations, system load and the flexibility of
scheduling will impact the performance metrics of all the scheduling
algorithms, and the PE-Worst-Fit algorithm becomes the best algorithm for the
scheduler with the highest acceptance rate of AR requests, and the jobs with
the First-Fit algorithm experience the lowest average slowdown. The data
structure and scheduling policies can be used to organize and allocate
resources for parallel AR jobs with deadline constraint in large-scale
computing systems.

Distributed, Parallel, and Cluster Computing