[[alternative]]Schedulability Analyses for EDkL Scheduling on Real-Time Multiprocessor Systems

[[abstract]]There has been an increasing demand for real-time scheduling on multiprocessor systems. With the decreasing cost of hardware, multiprocessor architecture becomes more popular nowadays. However, a multiprocessor real-time system may not provide a performance speedup proportional to the number of processors. Choosing a suitable scheduling algorithm is very important in order to get good performance. In this paper, we study some efficient real-time scheduling algorithms for multiprocessor systems. The first is EDZL (Earliest Deadline first until Zero Laxity). Then we extend the cases to the condition of k laxities. We also try to replace the EDF module with other heuristics in EDZL algorithm. We find that EDkL could not improve processor utilization and other heuristics are not good enough as EDF in EDZL. Using a special task set we got from experiments, we disprove the conjecture that the utilization bound of EDZL is 3m/4. Finally, we also get a property that the utilization bound of EDZL is not greater than m(1-1/e) where e is the natural logarithm. Although the bound of EDZL is not ideal enough, EDZL is still an efficient and practical scheduling algorithm for real-time multiprocessor systems.