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
CMU-CS-02-158.ps
CMU-CS-02-158.pdf
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 This page maintained by [email protected]
School of Computer Science homepage