Performance evaluation of deadline-based and laxity-based scheduling algorithms in real-time multiprocessor environments

Abstract:- Scheduling algorithms play an important role in design of real-time systems. Owing to high processing power and low price of multiprocessors, real-time scheduling in such systems is more interesting; however, more complicated. Its complication is due to the fact that multiprocessors are composed of a number of processors that require more complex strategies in order to maintain the system’s performance over a desirable level. Earliest Deadline First (EDF) and Least Laxity First (LLF) are two well-known and extensively applied dynamic scheduling algorithms which have been proved to be optimal on uniprocessor systems. However, neither of these algorithms is shown to be optimal on multiprocessors. Up until now, many researches have been done on aforementioned algorithms, but to the best of our knowledge, none of which has compared the efficiency of the two algorithms 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 practical version of LLF which is called the Modified Least Laxity First (MLLF) algorithm instead of the traditional LLF and have compared its performance with the EDF algorithm. The MLLF is a job-level dynamic and optimal strategy on uniprocessor systems, similar to the EDF algorithm. We have comprehensively investigated the performance of EDF and MLLF from many different aspects. Key-Words:- real-time systems, multiprocessor systems, job-level dynamic scheduling, earliest deadline first, modified least laxity first 1