Autonomic Share Allocation and Bounded Prediction of Response Times in Parallel Job Scheduling for Grids

Grid schedulers which need to decide on which sites the jobs are best allocated require controlled and predictable service. Fair-share scheduling has become widely used but lacks a formal model and depends on the current machine load. Existing approaches for response-time prediction still show significant prediction errors, mostly due to problems in dynamic arrival of jobs with potentially higher priority and hard-to-anticipate packing and backfilling effects. Thus, we propose a different job scheduler (Scojo-PECT) which provides a more suitable framework for predictability and service guarantees by employing preemption with coarse-grain time sharing. We formalize the approach via a queuing model to determine the resource shares necessary to meet target service levels. As further extension, Scojo-PECT can adapt resource shares within certain limits to variations in machine load, while maintaining predictability and service guarantees. We demonstrate the feasibility of service control, the tightness of the 95% prediction intervals (0-30% from average), and the high predictability obtained.