Efficient Dynamic Job Scheduling Algorithms for Multiprocessor Systems

Saptarshi MAHESH; C. Siva Ram MURTHY; C. Pandu RANGAN

Efficient Dynamic Job Scheduling Algorithms for Multiprocessor Systems

Saptarshi MAHESH, C. Siva Ram MURTHY, C. Pandu RANGAN

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E78-D No.1 pp.3-12

Publication Date: 1995/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm and Computational Complexity

Cite this

Copy

Saptarshi MAHESH, C. Siva Ram MURTHY, C. Pandu RANGAN, "Efficient Dynamic Job Scheduling Algorithms for Multiprocessor Systems" in IEICE TRANSACTIONS on Information, vol. E78-D, no. 1, pp. 3-12, January 1995, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e78-d_1_3/_p

Copy

@ARTICLE{e78-d_1_3,
author={Saptarshi MAHESH, C. Siva Ram MURTHY, C. Pandu RANGAN, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Dynamic Job Scheduling Algorithms for Multiprocessor Systems},
year={1995},
volume={E78-D},
number={1},
pages={3-12},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Efficient Dynamic Job Scheduling Algorithms for Multiprocessor Systems
T2 - IEICE TRANSACTIONS on Information
SP - 3
EP - 12
AU - Saptarshi MAHESH
AU - C. Siva Ram MURTHY
AU - C. Pandu RANGAN
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1995
AB - 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.
ER -