Efficient algorithms for schedulability analysis and priority assignment for fixed-priority preemptive scheduling with offsets
by Zonghua Gu; Haibin Cai
International Journal of Embedded Systems (IJES), Vol. 6, No. 4, 2014

Abstract: Fixed-priority scheduling is the most common scheduling algorithm used in industry practice. Imposing fixed task release offsets is an effective technique for improving schedulability by avoiding the critical instant when all tasks are released simultaneously. In this paper, we address the problem of schedulability analysis and priority assignment for a periodic taskset with fixed-priority preemptive scheduling, where tasks have fixed offset relationships relative to each other. For exact schedulability analysis, we present an efficient algorithm for computing busy periods, and obtaining response times of all instances of a task τ_i in the feasibility interval once the priority-level-p_i busy periods are determined. For priority assignment, we adopt Audsley's optimal priority assignment (OPA) algorithm, and present an efficient algorithm for incremental construction of busy periods. We also present an efficient conservative algorithm for schedulability analysis of an asynchronous taskset with much improved accuracy compared to the schedulability test without offset constraints. Performance evaluation demonstrates significant performance improvements compared to existing algorithms in terms of both computation efficiency and analysis accuracy.

Online publication date: Sat, 11-Oct-2014

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Embedded Systems (IJES):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com