LLFpi: Schedulability-Improved LLF Algorithm in Multiprocessor Real-Time Embedded Systems

摘要

As the workload of real-time applications becomes more complex, more diverse, and heavier, multiprocessor architecture and priority-driven scheduling algorithms are adopted in recent embedded systems. One of priority-driven algorithms is LLF (Least Laxity First). It assigns higher priority to active jobs with less laxity. It is known that LLF outperforms many scheduling algorithms on multiprocessor platforms in term of the number of successfully scheduled task sets. This paper proposes LLFpi (LLF with priority inversion) scheduling algorithm which is a modification of LLF. LLFpi reduces processor idle time by allowing temporary priority inversion, so that it improves the schedulability of LLF. This paper proves that LLFpi strictly dominates LLF, that is, LLFpi can successfully schedule any task set which is schedulable by LLF. It also presents the performance evaluation results through extensive simulation.