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).


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.


Related papers are [189, 192].

Go to next publication

Return to Richard Brent's index page