EFFICIENT DYNAMIC JOB SCHEDULING ALGORITHMS FOR MULTIPROCESSOR SYSTEMS

Exploiting the full potential of a multiprocessor system requires a go od job scheduling algorithm. In this paper we analyze three dynamic jo b scheduling algorithms in multiprocessor systems. These algorithms ar e based on static job scheduling algorithms, LPT (longest processing t ime first), SJF (shortest job first), and LPR (largest processor requi rement first), each of which exhibits good performance in terms of asy mptotic upper bound on the marketspan of the schedule generated by it. We analyze their performance in the dynamic case experimentally, wher e we have a stochastic stream of jobs with arbitrary processing time a nd processor requirement. We compare their performance with the FCFS a lgorithm and its simple extension. Except for LPT, the algorithms are found to perform significantly better than FCFS, while among themselve s SJF performs the best, followed by K-LPR, a variation of LPR. We als o consider the fairness aspect of these algorithms and propose a gener al technique to impose fairness on these algorithms. Finally, we analy ze the impact of imposing fairness on the performance of these algorit hms.