Efficient Dynamic Job Scheduling Algorithms for Multiprocessor Systems

Saptarshi MAHESH
C. Siva Ram MURTHY
C. Pandu RANGAN

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E78-D    No.1    pp.3-12
Publication Date: 1995/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
dynamic job scheduling,  multiprocessor systems,  FCFS algorithm,  LPT algorithm,  SJF algorithm,  LPR algorithm,  simulation,  fairness,  

Full Text: PDF>>
Buy this Article


Summary: 
Exploiting the full potential of a multiprocessor system requires a good job scheduling algorithm. In this paper we analyze three dynamic job scheduling algorithms in multiprocessor systems. These algorithms are based on static job scheduling algorithms, LPT (longest processing time first), SJF (shortest job first), and LPR (largest processor requirement first), each of which exhibits good performance in terms of asymptotic upper bound on the makespan of the schedule generated by it. We analyze their performance in the dynamic case experimentally, where we have a stochastic stream of jobs with arbitrary processing time and processor requirement. We compare their performance with the FCFS algorithm and its simple extension. Except for LPT, the algorithms are found to perform significantly better than FCFS, while among themselves SJF performs the best, followed by K-LPR, a variation of LPR. We also consider the fairness aspect of these algorithms and propose a general technique to impose fairness on these algorithms. Finally, we analyze the impact of imposing fairness on the performance of these algorithms.