Abstract | ||
---|---|---|
Utilization bound is a well-known concept first introduced in the seminal paper of Liu & 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, we obtain various improvements over the Liu & Layland bound. In particular, we shall give a more intuitive derivation of the bound as a function of the number of harmonic chains in the task periods which allows us to derive a simpler algorithm to calculate such bounds. We derive algorithms that yield better bounds as a function of the period parameters of the task set. We also give a generalization of the bound for tasks whose deadlines are smaller than their periods. |
Year | DOI | Venue |
---|---|---|
1999 | 10.1109/RTCSA.1999.811259 | RTCSA |
Keywords | Field | DocType |
better bound,fixed-priority scheduler,periodic task set,task set,seminal paper,original utilization,real-time task set,harmonic chain,task period,utilization bound re-visited,intuitive derivation,system testing,scheduling,computer science,scheduling algorithm,real time systems,polynomials | Polynomial,System testing,Computer science,Scheduling (computing),Harmonic,Real-time computing,Processor scheduling,Periodic graph (geometry),Distributed computing | Conference |
ISBN | Citations | PageRank |
0-7695-0306-3 | 7 | 1.45 |
References | Authors | |
9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Deji Chen | 1 | 669 | 44.92 |
Aloysius K. Mok | 2 | 662 | 86.52 |
Tei-Wei Kuo | 3 | 3203 | 326.35 |