Non-migratory online deadline scheduling on multiprocessors

ABSTRACT

In this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m processors. We show that I can also be completed by a non-migratory online schedule using m speed-5.828 processors (i.e., processors of 5.828 times faster). This result supplements the previous results that I can also be completed by a non-migratory offline schedule using 6m unit-speed processors [8] or a migratory online schedule using m speed-2 processors [13]. Our result is based on a simple conservative scheduling algorithm called PARK which commits a processor to a job only when the processor has zero commitment before its deadline. A careful analysis of PARK further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). PARK also finds application in overloaded systems; it gives the first online non-migratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm.

REFERENCES

• 1: S. Baruah , G. Koren , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha, On-line scheduling in the presence of overload, Proceedings of the 32nd annual symposium on Foundations of computer science, p.100-110, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185354]
• 2: Piotr Berman , Chris Coulston, Speed is More Powerful than Claivoyance, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.255-263, July 08-10, 1998
• 3: Marek Chrobak , Leah Epstein , John Noga , Jiri Sgall , Rob van Stee , Tomás Tichý , Nodari Vakhania, Preemptive Scheduling in Overloaded Systems, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.800-811, July 08-13, 2002
• 4: M. L. Dertouzos. Control robotics: the procedural control of physical processes. In Proc. IFIP Congress, pages 807--813, 1974.
• 5: M. L. Dertouzos , A. K. Mok, Multiprocessor Online Scheduling of Hard-Real-Time Tasks, IEEE Transactions on Software Engineering, v.15 n.12, p.1497-1506, December 1989 [doi>10.1109/32.58762]
• 6: Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301299]
• 7: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 8: Bala Kalyanasundaram , Kirk R. Pruhs, Eliminating migration in multi-processor scheduling, Journal of Algorithms, v.38 n.1, p.2-24, Jan. 2001 [doi>10.1006/jagm.2000.1128]
• 9: Gilad Koren , Emanuel Dar , Amihood Amir, The Power of Migration in Multiprocessor Scheduling of Real-Time Systems, SIAM Journal on Computing, v.30 n.2, p.511-527, 2000 [doi>10.1137/S0097539797326241]
• 10: Gilad Koren , Dennis Shasha, MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling, Theoretical Computer Science, v.128 n.1-2, p.75-97, June 6, 1994 [doi>10.1016/0304-3975(94)90165-1]
• 11: Tak Wah Lam , Kar Keung To, Trade-offs between speed and processor in hard-deadline scheduling, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 17-19, 1999, Baltimore, Maryland, United States
• 12: Tak-Wah Lam , Kar-Keung To, Performance guarantee for online deadline scheduling in the presence of overload, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.755-764, January 07-09, 2001, Washington, D.C., United States
• 13: Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258570]
• 14: Jiri Sgall, On-line Scheduling, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.196-231, January 1998
• 15: John A. Stankovic , Krithi Ramamritham , Marco Spuri, Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms, Kluwer Academic Publishers, Norwell, MA, 1998