Modeling and simulation of dynamic job scheduling in multiprocessor systems

Abstract

Realizing the full potential of a multiprocessor system requires a good job scheduling algorithm. We propose a new job scheduling algorithm, called K-FCFS, which is an extension of the FCFS algorithm. We developed an approximate analytic model for this algorithm by decomposing the system into two interdependent submodels: (i) queue submodel, and (ii) processor submodel. The overall model is solved using an iterative technique. Validation with simulation results shows the errors to be within acceptable limits. The impact of key parameters is studied. The proposed algorithm is found to perform better than the FCFS algorithm.

Keywords:

• dynamic job scheduling
• FCFS algorithm
• multiprocessor systems
• queueing theory
• approximate analysis

C.R. Categories:

• C.1.2
• D.4.1
• G.m.