We consider the problem of task assignment in a distributed server system, 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, where short and long jobs have generally distributed service requirements, and arrivals are Poisson. We consider two variants of this problem: a central queue model and an immediate dispatch model. This paper presents the first analysis of cycle stealing under the central-queue model. (Cycle stealing under the immediate dispatch model is analyzed in [9]). The analysis uses a technique which we refer to as busy period transitions. Results show that cycle stealing can reduce mean response time for short jobs by orders of magnitude, while long jobs are only slightly penalized. Furthermore using a central queue yields significant performance improvement over immediate dispatch, both from the perspective of the benefit to short jobs and the penalty to long jobs.
By: Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, Mark S. Squillante
Published in: RC23098 in 2004
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .