LLF schedulability analysis on multiprocessor platforms

Lee, Jinkyu; Easwaran, Arvind; Shin, Insik

http://hdl.handle.net/10400.22/3898

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
COM_JinkyuLee_2010_CISTER.pdf		381.67 KB	Adobe PDF	Download

Send Feedback

Authors

Lee, Jinkyu

Easwaran, Arvind

Shin, Insik

Abstract(s)

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms have been little studied until now. Orthogonally, it has remained open how to efficiently schedule general task systems, including constrained deadline task systems, upon multiprocessors. Recent studies have introduced zero laxity (ZL) policy, which assigns a higher priority to a task with zero laxity, as a promising scheduling approach for such systems (e.g., EDZL). Towards understanding the importance of laxity in multiprocessor scheduling, this paper investigates the characteristics of ZL policy and presents the first ZL schedulability test for any work-conserving scheduling algorithm that employs this policy. It then investigates the characteristics of LLF scheduling, which also employs the ZL policy, and derives the first LLF-specific schedulability test on multiprocessors. It is shown that the proposed LLF test dominates the ZL test as well as the state-of-art EDZL test.