Computer Science Department
School of Computer Science, Carnegie Mellon University


Analysis of Task Assignment with Cycle Stealing

Mor Harchol-Balter, Cuihong Li*, Takayuki Osogami,
Alan Scheller-Wolf*, Mark S. Squillante**

July 2002

Keywords: Cycle stealing, task assignment, server farm, distributed system, unfairness, star-vation, load sharing, supercomputing, matrix-geometric methods, busy periods, multi-class queue, multiserver queue.

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.

35 pages

*Graduate School of Industrial Administration, Carnegie Mellon University **IBM Research Division, Thomas J. Watson Research Center, Yorktown Heights, NY 10598.

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by