Speed is as powerful as clairvoyance

ABSTRACT

We introduce resource augmentation as a method for analyzing online scheduling problems. In resource augmentation analysis the on-line scheduler is given more resources, say faster processors or more processors, than the adversary. We apply this analysis to two well-known on-line scheduling problems, the classic uniprocessor CPU scheduling problem 1 |ri, pmtn|&Sgr; Fi, and the best-effort firm real-time scheduling problem 1|ri, pmtn| &Sgr; wi( 1- Ui). It is known that there are no constant competitive nonclairvoyant on-line algorithms for these problems. We show that there are simple on-line scheduling algorithms for these problems that are constant competitive if the online scheduler is equipped with a slightly faster processor than the adversary. Thus, a moderate increase in processor speed effectively gives the on-line scheduler the power of clairvoyance. Furthermore, the on-line scheduler can be constant competitive on all inputs that are not closely correlated with processor speed. We also show that the performance of an on-line scheduler is best-effort real time scheduling can be significantly improved if the system is designed in such a way that the laxity of every job is proportional to its length.

REFERENCES

• 1: Susanne Albers , Sanjeev Arora , Sanjeev Khanna, Page replacement for general caching problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.31-40, January 17-19, 1999, Baltimore, Maryland, United States
• 2: Sanjoy K. Baruah , Jayant R. Haritsa, Scheduling for Overload in Real-Time Systems, IEEE Transactions on Computers, v.46 n.9, p.1034-1039, September 1997 [doi>10.1109/12.620484]
• 3: BARUAH, S., HARITSA, J., AND SHARMA, N. 1994. On-line scheduling to maximize task completions. In Proceedings of the IEEE Real-Time Systems Symposium. IEEE Computer Society Press, Los Alamitos, Calif., pp. 228-237.
• 4: S. Baruah , G. Koren , D. Mao , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha , F. Wang, On the competitiveness of on-line real-time task scheduling, Real-Time Systems, v.4 n.2, p.125-144, May 1992 [doi>10.1007/BF00365406]
• 5: 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]
• 6: BEN-DAVID, S., AND BORODIN, A. 1994. A new measure for the study of on-line algorithms. Algorithmica 11, 73-91.
• 7: 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
• 8: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 9: Peter Brucker, Scheduling Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 1995
• 10: COLWELL, R., SUCHOZA, R., AND ZORINE, D. 1995. On-line real-time scheduling with laxities. Manuscript.
• 11: 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]
• 12: Abraham Silberschatz , James L. Peterson , Peter B. Galvin, Operating system concepts (3rd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 13: Leslie A. Hall, Approximation algorithms for scheduling, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: Bala Kalyanasundaram , Kirk Pruhs, Fault-Tolerant Real-Time Scheduling, Proceedings of the 5th Annual European Symposium on Algorithms, p.296-307, September 15-17, 1997
• 15: Bala Kalyanasundaram , Kirk Pruhs, The Online Transportation Problem, Proceedings of the Third Annual European Symposium on Algorithms, p.484-493, September 25-27, 1995
• 16: B. Kalyanasundaram , K. R. Pruhs, Minimizing flow time nonclairvoyantly, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.345, October 19-22, 1997
• 17: Bala Kalyanasundaram , Kirk Pruhs, Maximizing Job Completions Online, Proceedings of the 6th Annual European Symposium on Algorithms, p.235-246, August 24-26, 1998
• 18: KOUTSOUPIAS, E., AND PAPADIMITRIOU, C. 1994. Beyond competitive analysis. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. Springer-Verlag, New York, pp. 394-400.
• 19: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 20: KOREN, G., AND SHASHA, D. 1992. D .... : An optimal on-line scheduling algorithm for overloaded real-time systems. In Proceedings of the IEEE Real-time Systems Symposium. IEEE Computer Society Press, Los Alamitos, Calif., pp. 290-299.
• 21: 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]
• 22: 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
• 23: LAWLER, E., LENSTRA, J. K., RINNOOY NAN, A., AND SHMOYS, D. 1993. Sequencing and scheduling: algorithms and complexity. In Logistics of Production and Inventory, Handbooks in OR & MS 4, S. Graves, A. Rinnooy Kan, and P. Zipkin, eds. Chap. 9. Elsevier Science, Amsterdam, The Netherlands, pp. 445-522.
• 24: Y. Mansour , B. Patt-Shamir, Jitter Control in QoS Networks, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.50, November 08-11, 1998
• 25: Tsuyoshi Matsumoto, Competitive Analysis of the Round Robin Algorithm, Proceedings of the Third International Symposium on Algorithms and Computation, p.71-77, December 16-18, 1992
• 26: Milan Milenkovic, Operating systems: concepts and design, McGraw-Hill, Inc., New York, NY, 1992
• 27: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 28: 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]
• 29: RAGHAVAN, P. 1992. A statistical adversary for on-line algorithms. Online Algorithms, DIMACS Series in Discrete Mathematics and Computer Science 7, 79-83.
• 30: Jiri Sgall, On-line Scheduling, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.196-231, January 1998
• 31: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 32: Gerhard J. Woeginger, On-line scheduling of jobs with fixed start and end times, Theoretical Computer Science, v.130 n.1, p.5-16, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90150-3]
• 33: YOUNG, N. 1994.The k-server dual and loose competitiveness for paging. Algorithmica 11,525-541.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

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

General Terms:
Algorithms, Design, Economics, Management, Performance

Keywords:
multi-level feedback scheduling, resource augmentation, scheduling