An optimal pinwheel scheduler using the single-number reduction technique

摘要

Several pinwheel schedulers have been reported previously for scheduling real-time systems in which the temporal distances between consecutive executions of tasks must be less than their respective distance constraints. The scheduler Sr has been used for task sets with real number distance constraints and execution times. Sr transforms the distance constraints in a system into harmonic values with a base of 2. The authors present a pinwheel scheduler Sr/sup b/ which is derived from Sr using any base greater than or equal to d. The schedulability condition of Sr/sup b/ is presented and its optimality is proved. They also study the performance of Sr/sup b/ by simulation and compare it with a near-optimal heuristic algorithm HSr.