Utilization Bound of Non-preemptive Fixed Priority Schedulers

Moonju PARK  Jinseok CHAE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.10   pp.2152-2155
Publication Date: 2009/10/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.2152
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Dependable Computing
Keyword: 
real-time system,  non-preemptive scheduling,  fixed priority,  

Full Text: PDF(81.5KB)>>
Buy this Article



Summary: 
It is known that the schedulability of a non-preemptive task set with fixed priority can be determined in pseudo-polynomial time. However, since Rate Monotonic scheduling is not optimal for non-preemptive scheduling, the applicability of existing polynomial time tests that provide sufficient schedulability conditions, such as Liu and Layland's bound, is limited. This letter proposes a new sufficient condition for non-preemptive fixed priority scheduling that can be used for any fixed priority assignment scheme. It is also shown that the proposed schedulability test has a tighter utilization bound than existing test methods.