Server scheduling in the Lp norm: a rising tide lifts all boat

ABSTRACT

Often server systems do not implement the best known algorithms for optimizing average Quality of Service (QoS) out of concern of that these algorithms may be insufficiently fair to individual jobs. The standard method for balancing average QoS and fairness is optimize the L_p metric, 1 < p < ∞. Thus we consider server scheduling strategies to optimize the L_p norms of the standard QoS measures, flow and stretch. We first show that there is no n^o(1)-competitive online algorithm for the L_p norms of either flow or stretch. We then show that the standard clairvoyant algorithms for optimizing average QoS, SJF and SRPT, are O(1+ε)-speed O(1/ε)-competitive for the L_p norms of flow and stretch. And that the standard nonclairvoyant algorithm for optimizing average QoS, SETF, is O(1+ε)-speed O(1/ε^(2+2/p))-competitive for the L_p norms of flow. These results argue that these standard algorithms will not starve jobs until the system is near peak capacity. In contrast, we show that the Round Robin, or Processor Sharing algorithm, which is sometimes adopted because of its seeming fairness properties, is not O(1+ε)-speed n^o(1)-competitive for sufficiently small ε.

REFERENCES

• 1: Noga Alon , Yossi Azar , Gerhard J. Woeginger , Tal Yadid, Approximation schemes for scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.493-500, January 05-07, 1997, New Orleans, Louisiana, United States
• 2: A. Avidor, Y. Azar, and J. Sgall. Ancient and new algorithms for load balancing in the lp norm. Algorithmica, 29(3):422--441, 2001.
• 3: B. Awerbuch , Y. Azar , E. F. Grove , Ming-Yang Kao , P. Krishnan , J. S. Vitter, Load balancing in the L/sub p/ norm, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.383, October 23-25, 1995
• 4: N. Bansal , K. Dhamdhere, Minimizing weighted flow time, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Nikhil Bansal , Kedar Dhamdhere , Jochen Könemann , Amitabh Sinha, Non-clairvoyant Scheduling for Minimizing Mean Slowdown, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.260-270, February 27-March 01, 2003
• 6: Nikhil Bansal , Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.279-290, June 2001, Cambridge, Massachusetts, United States
• 7: Luca Becchetti , Stefano Leonardi, Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.94-103, July 2001, Hersonissos, Greece [doi>10.1145/380752.380782]
• 8: Luca Becchetti , Stefano Leonardi , Alberto Marchetti-Spaccamela , Kirk Pruhs, Online Weighted Flow Time and Deadline Scheduling, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.36-47, August 18-20, 2001
• 9: Michael A. Bender , S. Muthukrishnan , Rajmohan Rajaraman, Improved algorithms for stretch scheduling, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.762-771, January 06-08, 2002, San Francisco, California
• 10: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 11: Chandra Chekuri , Sanjeev Khanna, Approximation schemes for preemptive weighted flow time, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509954]
• 12: Chandra Chekuri , Sanjeev Khanna , An Zhu, Algorithms for minimizing weighted flow time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.84-93, July 2001, Hersonissos, Greece [doi>10.1145/380752.380778]
• 13: M. Crovella, R. Frangioso, and M. Harchol-Balter. Connection scheduling in web servers. In USENIX Symposium on Internet Technologies and Systems, pages 243--254, 1999.
• 14: Jeff Edmonds, Scheduling in the dark, Theoretical Computer Science, v.235 n.1, p.109-141, March 17, 2000 [doi>10.1016/S0304-3975(99)00186-3]
• 15: Leah Epstein , Jiri Sgall, Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines, Proceedings of the 7th Annual European Symposium on Algorithms, p.151-162, July 16-18, 1999
• 16: M. Harchol-Balter, M. Crovella, and S. Park. The case for srpt scheduling of web servers.
• 17: http://httpd.apache.org/docs/.
• 18: http://www.netcraft.com/survey/.
• 19: Bala Kalyanasundaram , Kirk R. Pruhs, Fault-tolerant scheduling, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.115-124, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195115]
• 20: 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
• 21: 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]
• 22: Donald E. Knuth, The TEXbook, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 23: James F. Kurose , Keith Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 24: 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]
• 25: S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
• 26: 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]
• 27: B. Schroeder and M. Harchol-Balter. Web servers under overload: how scheduling can help.
• 28: Andrew S. Tanenbaum, Operating systems: design and implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 29: K. Thompson. Unix implementation. The Bell System Technical Journal, 57(6):1931--1946, 1978.

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:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Performance, Theory

Keywords:
flow time, multilevel feedback, resource augmentation, scheduling, shortest elapsed time first, shortest job first, shortest remaining processing time