Period Selection for Minimal Hyperperiod in Periodic Task Systems
- 9 October 2012
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 62 (9) , 1813-1822
Abstract
Task period selection is often used to adjust the workload to the available computational resources. In this paper, we propose a model where each selected period is not restricted to be a natural number, but can be any rational number within a range. Under this generalization, we contribute a period selection algorithm that yields a much smaller hyperperiod than that of previous works: with respect to the largest period, the hyperperiod with integer constraints is exponentially bounded; with rational periods the worst case is only quadratic. By means of an integer approximation at each task activation, we show how our rational period approach can work under system clock granularity; it is thus compatible with scheduling analysis practice and implementation. Our finding has practical applications in several fields of real-time scheduling: lowering complexity in table driven schedulers, reducing search space in model checking analysis, generating synthetic workload for statistical analysis of real-time scheduling algorithms, etc.Keywords
This publication has 18 references indexed in Scilit:
- Task period selection to minimize hyperperiod2011
- Generation of static tables in embedded memory with dense scheduling2010
- A method for adjusting the periods of periodic processes to reduce the least common multiple of the period lengths in real-time embedded systems2010
- Negative Results for Scheduling Independent Hard Real-Time Tasks with Self-Suspensions2005
- On task schedulability in real-time control systems2002
- Elastic task model for adaptive rate control2002
- Fundamentals of Implementing Real-Time Control Applications in Distributed Computer SystemsReal-Time Systems, 1998
- Applying new scheduling theory to static priority pre-emptive schedulingSoftware Engineering Journal, 1993
- A note on preemptive scheduling of periodic, real-time tasksInformation Processing Letters, 1980
- Algorithm for computer control of a digital plotterIBM Systems Journal, 1965