A faster exact schedulability analysis for fixed-priority scheduling
Journal
Journal of Systems and Software
Journal Volume
79
Journal Issue
12
Pages
1744-1753
Date Issued
2006
Author(s)
Abstract
Real-time scheduling for task sets has been studied, and the corresponding schedulability analysis has been developed. Due to the considerable overheads required to precisely analyze the schedulability of a task set (referred to as exact schedulability analysis), the trade-off between precision and efficiency is widely studied. Many efficient but imprecise (i.e., sufficient but not necessary) analyses are discussed in the literature. However, how to precisely and efficiently analyze the schedulability of task sets remains an important issue. The Audsley's Algorithm was shown to be effective in exact schedulability analysis for task sets under rate-monotonic scheduling (one of the optimal fixed-priority scheduling algorithms). This paper focuses on reducing the runtime overhead of the Audsley's Algorithm. By properly partitioning a task set into two subsets and differently treating these two subsets during each iteration, the number of iterations required for analyzing the schedulability of the task set can be significantly reduced. The capability of the proposed algorithm was evaluated and compared to related works, which revealed up to a 55.5% saving in the runtime overhead for the Audsley's Algorithm when the system was under a heavy load. © 2006 Elsevier Inc. All rights reserved.
Subjects
Fixed-priority preemptive scheduling; Periodic tasks; Real-time systems; Schedulability analysis
Other Subjects
Algorithms; Iterative methods; Scheduling; Set theory; Fixed-priority preemptive scheduling; Schedulability analysis; Real time systems
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
23.pdf
Size
222.03 KB
Format
Adobe PDF
Checksum
(MD5):2b905ec9dc08e992235742167a0418f5