Article: Efficient algorithms for schedulability analysis and priority assignment for fixed-priority preemptive scheduling with offsets Journal: International Journal of Embedded Systems (IJES) 2014 Vol.6 No.4 pp.303 - 318 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-pi 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. Inderscience Publishers - linking academia, business and industry through research

Title: Efficient algorithms for schedulability analysis and priority assignment for fixed-priority preemptive scheduling with offsets

Authors: Zonghua Gu; Haibin Cai

Addresses: College of Computer Science, Zhejiang University, Hangzhou 310027, China ' Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China

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.

Keywords: real-time scheduling; schedulability analysis; priority assignment; fixed-priority scheduling; preemptive scheduling; offsets.

DOI: 10.1504/IJES.2014.064991

International Journal of Embedded Systems, 2014 Vol.6 No.4, pp.303 - 318

Received: 11 Oct 2013
Accepted: 20 Dec 2013
Published online: 11 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Efficient algorithms for schedulability analysis and priority assignment for fixed-priority preemptive scheduling with offsets

Keep up-to-date