Quantitative Comparison of Job-level Dynamic Scheduling Policies in Parallel Real-time Systems

Abstract

Scheduling algorithms play an important role in design of real-time systems. Due to high processing power and low price of multiprocessors, real-time scheduling in such systems is more interesting; however, more complicated. Earliest deadline first (EDF) and least laxity first (LLF) are two well-known and extensively applied dynamic scheduling algorithms on which many researches have already been done. However, to the best of our knowledge, the efficiency of aforementioned algorithms has not been compared under similar conditions. Perhaps the main reason is that LLF algorithm is fully dynamic and impractical to implement. In this research, we have used a job-level dynamic and practical version of LLF which is called modified least laxity first (MLLF) algorithm instead of the traditional LLF and have compared its performance with EDF algorithm from many different aspects. The success ratio has been chosen as the key factor for evaluation of the algorithms