Efficient real-time scheduling algorithms for multiprocessor systems

For real-time systems, multiprocessor support is indispensable to handle the large number of requests. Existing on-line scheduling algorithms such as Earliest Deadline First Algorithm (EDF) and Least Laxity Algorithm (LLA) may not be suitable for scheduling hard real-time tasks on multiprocessors. Although EDF has a low context switching overhead, it can produce arbitrarily low processor utilization. LLA has been shown as suboptimal, but has the potential for higher context switching overhead. We propose new on-line scheduling algorithms Earliest Deadline/Least Laxity (ED/LL) and Earliest Deadline Zero Laxity (EDZL) for identical multiprocessors. We show that ED/LL is suboptimal for multiprocessors and EDZL is suboptimal for two processors. Experimental results show that ED/LL and EDZL have low context switching overhead and low deadline miss rate.