The length of time slots for efficient gang scheduling
209. B. B. Zhou,
A. M. Goscinski and
R. P. Brent,
Concerning the length of time slots for efficient gang scheduling,
Proc. Third International Conference on Parallel and Distributed
Computing Applications and Technologies (PDCAT2002),
Kanazawa, Japan, September 2002, 364-371.
Revision in IEICE Transactions on Information and Systems
E86-D (2003), 1594-1600.
PDCAT paper:
dvi (20K),
pdf (68K),
ps (33K).
IEICE paper:
pdf (196K).
Abstract
Applying gang scheduling can alleviate the blockade problem
caused by exclusively used space-sharing strategies for parallel
processing. However, the original form of gang scheduling is not
practical as there are several fundamental problems associated
with it. Recently many researchers have developed new strategies
to alleviate some of these problems. Unfortunately, one important
problem has not been so far seriously addressed, that is, how to
set the length of time slot to obtain a good performance of gang
scheduling. With gang scheduling time is divided into time slots
of equal length, the number of time slots introduced in the
system forms a scheduling round and each new job is first
allocated to a particular time slot and then starts to run in the
following scheduling round. Ideally, the length of time slot
should be set long to avoid frequent context switches and so to
reduce the scheduling overhead. The number of time slots in a
scheduling round should also be limited to avoid a large number
of jobs competing for limited resources (CPU time and memory).
Long time slots and the limited number of time slots in each
scheduling round may cause jobs to wait for a long time before it
can be executed after arrival, which can significantly affect the
performance of jobs, especially short jobs which are normally
expected to finish quickly. However, the performance of a short
job can also suffer if the length of time slot is not long enough
to let the short job complete in a single time slot. In this
paper we present a strategy to deal with this important issue for
efficient gang scheduling.
Comments
Related papers are
[189,
192].
Go to next publication
Return to Richard Brent's index page