Utilization bound revisited
Journal
IEEE Transactions on Computers
Journal Volume
52
Journal Issue
3
Pages
351-361
Date Issued
2003
Author(s)
Abstract
Utilization bound is a well-known concept introduced in the seminal paper of Liu and Layland, which provides a simple and practical way to test the schedulability of a real-time task set. The original utilization bound for the fixed-priority scheduler was given as a function of the number of tasks In the periodic task set. In this paper, we define the utilization bound as a function of the information about the task set. By making use of more than just the number of tasks, better utilization bound over the Liu and Layland bound can be achieved. We investigate in particular the bound given a set of periods for which it is still unknown if there is a polynomial algorithm for the exact bound. By investigating the relationships among the periods, we derive algorithms that yield better bounds than the Liu and Layland bound and the harmonic chain bound. Randomly generated task sets are tested against different bound algorithms. We also give a more intuitive proof of the harmonic chain bound and derive a computationally simpler algorithm.
Subjects
Preemptive fixed-priority scheduling; Rate-monotonic priority assignment; Utilization bound
Other Subjects
Algorithms; Boundary conditions; Computational complexity; Harmonic analysis; Scheduling; Rate monotonic analysis (RMA); Real time systems
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
09.pdf
Size
261.05 KB
Format
Adobe PDF
Checksum
(MD5):ca3fbbf7daeee1bd220a5fdc3d5e7189