Optimal rate-based scheduling on multiprocessors

ABSTRACT

The PD² Pfair/ERfair scheduling algorithm is the most efficient known algorithm for optimally scheduling periodic tasks on multiprocessors. In this paper, we prove that PD² is also optimal for scheduling "rate-based" tasks whose processing steps may be highly jittered. The rate-based task model we consider generalizes the widely-studied sporadic task model.

REFERENCES

• 1: James Anderson , Sanjoy Baruah , Kevin Jeffay, Parallel Switching in Connection-Oriented Networks, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.200, December 01-03, 1999
• 2: J. Anderson and A. Srinivasan. Early-release fair scheduling. Proc. of the 12th Euromicro Conference on Real-Time Systems, pp. 35--43, 2000.
• 3: J. H. Anderson , A. Srinivasan, Pfair scheduling: beyond periodic task systems, Proceedings of the Seventh International Conference on Real-Time Systems and Applications (RTCSA'00), p.297, December 12-14, 2000
• 4: James H. Anderson , Anand Srinivasan, Mixed Pfair/ERfair Scheduling of Asynchronous Periodic Tasks, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.76, June 13-15, 2001
• 5: S. Baruah, N. Cohen, C.G. Plaxton, and D. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15:600--625, 1996.
• 6: Sanjoy K. Baruah , Johannes Gehrke , C. Greg Plaxton, Fast scheduling of periodic tasks on multiple resources, Proceedings of the 9th International Symposium on Parallel Processing, p.280-288, April 25-28, 1995
• 7: A. Chandra, M. Adler, P. Goyal, and P. Shenoy. Surplus fair scheduling: A proportional-share cpu scheduling algorithm for symmetric multiprocessors. In Proc. of the Fourth Symposium on Operating System Design and Implementation (OSDI), 2000.
• 8: Abhishek Chandra , Micah Adler , Prashant Shenoy, Deadline Fair Scheduling: Bridging the Theory and Practice of Proportionate Fair Scheduling in Multiprocessor Systems, Proceedings of the Seventh Real-Time Technology and Applications Symposium (RTAS '01), p.3, May 30-June 01, 2001
• 9: Kevin Jeffay , Steve Goddard, A Theory of Rate-Based Execution, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.304, December 01-03, 1999
• 10: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 11: A. K. Mok, FUNDAMENTAL DESIGN PROBLEMS OF DISTRIBUTED SYSTEMS FOR THE HARD-REAL-TIME ENVIRONMENT, Massachusetts Institute of Technology, Cambridge, MA, 1983

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Switching theory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

General Terms:
Algorithms, Experimentation, Performance, Theory