Analysis of Task Assignment with Cycle Stealing

The problem of task assignment in a distributed server system is considered, where short jobs are separated from long jobs, but short jobs may be run in the long job partition if it is idle (cycle stealing). Jobs are assumed to be non-preemptible. New techniques are presented for analyzing this problem, both in the case of immediate dispatch of jobs to hosts and in the case of a central queue. The analysis is approximate, but can be made as close to exact as desired. Analysis is validated via simulation. Results of the analysis show that cycle stealing can reduce mean response time for short jobs by orders of magnitude, while long jobs are only slightly penalized.