Minimizing migrations in fair multiprocessor scheduling of persistent tasks

ABSTRACT

Suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). Each machine is capable of performing one unit of work in each integral time unit and each job may be executed on at most one machine at a time. The schedule needs to specify which job is to be executed on each machine in each time window. The goal is to find a schedule that minimizes job migrations between machines while guaranteeing a fair schedule. We measure the fairness by the drift d defined as the maximum difference between the execution times accumulated by any two jobs. Since jobs are persistent we measure the quality of the schedule by the ratio of the number of migrations to time windows. We show a tradeoff between the drift and the number of migrations. Let n = qm + r with 0 < r < m (the problem is trivial for n ≤ m and for r = 0). For any d ≥ 1, we show a schedule that achieves a migration ratio of r(m - r)/(n(q(d 1) + 1)) + o(1); namely, it asymptotically requires r(m - r) job migrations every n(q(d 1) + 1) time windows. We show how to implement the schedule efficiently. We prove that our algorithm is almost optimal by proving a lower bound of r(m r)/(nqd) on the migration ratio. We also give a more complicated schedule that matches the lower bound for an infinite number of instances. Our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time.

REFERENCES

• 1: J. Anderson and A. Srinivasan. Towards a More Efficient and Flexible Pfair Scheduling Framework. 20th IEEE Real-time Systems Symposium (RTSS), Dec. 1999, pp. 46--50.
• 2: S.K. Baruah. Scheduling Periodic Tasks on Uniform Multiprocessors. 12th Euromicro Conference on Real-Time Systems (Euromicro-RTS), 2000, pp. 7--14.
• 3: Sanjoy K. Baruah, Dynamic- and Static-priority Scheduling of Recurring Real-time Tasks, Real-Time Systems, v.24 n.1, p.93-128, January 2003 [doi>10.1023/A:1021711220939]
• 4: S. Baruah and J. Carpenter. Multiprocessor fixed-priority scheduling with restricted interprocessor migrations. 15th Euromicro Conference on Real-Time Systems (Euromicro-RTS), 2003.
• 5: S. Baruah, N. Cohen, G. Plaxton and D. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica Vol. 15, No. 6, June 1996, pp. 600--625.
• 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: S. Baruah, J. Gehrke, G. Plaxton, I. Stoica, H. Abdel-Wahab and K. Jefiay. Fair on-line scheduling of a dynamic set of tasks on a single resource. Information Processing Letters, Vol. 64, No. 1, Oct. 1997, pp 43--51.
• 8: J. Bruno, E. Gabber, B. Özden and A. Silberschatz. The Eclipse Operating System: Providing Quality of Service via Reservation Domains. 1998 USENIX Annual Technical Conference, pp. 235--246.
• 9: Amotz Bar-Noy , Alain Mayer , Baruch Schieber , Madhu Sudan, Guaranteeing Fair Service to Persistent Dependent Tasks, SIAM Journal on Computing, v.27 n.4, p.1168-1189, Aug. 1998 [doi>10.1137/S0097539795282092]
• 10: 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
• 11: Kenneth J. Duda , David R. Cheriton, Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.261-276, December 12-15, 1999, Charleston, South Carolina, United States
• 12: S. Harizopoulos and A. Ailamaki. A finity Scheduling in Staged Server Architectures. Technical Report CMU-CS-02-113, March 2002.
• 13: Autonomic Computing: IBM's perspective on the state of Information Technology. http://www.research.ibm.com/autonomic/manifesto/.
• 14: Michael B. Jones , Daniela Roşu , Marcel-Cătălin Roşu, CPU reservations and time constraints: efficient, predictable scheduling of independent activities, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.198-211, October 05-08, 1997, Saint Malo, France
• 15: C. L. Liu. Scheduling Algorithms for Hard-Real-Time Multiprogramming of a Single Processor. JPL Space Program Summary, Vol. 2, Nov. 1969, pp. 37--60.
• 16: 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]
• 17: Constantine P. Sapuntzakis , Ramesh Chandra , Ben Pfaff , Jim Chow , Monica S. Lam , Mendel Rosenblum, Optimizing the migration of virtual computers, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060324]
• 18: Anand Srinivasan , Philip Holman , James H. Anderson, Integrating Aperiodic and Recurrent Tasks on Fair-Scheduled Multiprocessors, Proceedings of the 14th Euromicro Conference on Real-Time Systems, p.19, June 19-21, 2002
• 19: Anand Srinivasan , Philip Holman , James H. Anderson , Sanjoy Baruah, The Case for Fair Multiprocessor Scheduling, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.114.1, April 22-26, 2003
• 20: C. A. Waldspurger , E. Weihl. W., Stride Scheduling: Deterministic Proportional- Share Resource Management, Massachusetts Institute of Technology, Cambridge, MA, 1995