Classifying scheduling policies with respect to unfairness in an M/GI/1

ABSTRACT

It is common to evaluate scheduling policies based on their mean response times. Another important, but sometimes opposing, performance metric is a scheduling policy's fairness. For example, a policy that biases towards small job sizes so as to minimize mean response time may end up being unfair to large job sizes. In this paper we define three types of unfairness and demonstrate large classes of scheduling policies that fall into each type. We end with a discussion on which jobs are the ones being treated unfairly.

REFERENCES

• 1: Baily, Foster, Hoang, Jette, Klingner, Kramer, Macaluso, Messina, Nielsen, Reed, Rudolph, Smith, Tomkins, Towns, and Vildibill. Valuation of ultra-scale computing systems. White Paper, 1999.
• 2: 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
• 3: N. Bansal and A. Wierman. Competitive analysis of M/GI/1 queueing policies. Technical Report CMU-CS-02-201, Carnegie Mellon University, December 2002.
• 4: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 5: A. B. Downey, A parallel workload model and its implications for processor allocation, Proceedings of the 6th International Symposium on High Performance Distributed Computing (HPDC '97), p.112, August 05-08, 1997
• 6: Eric J. Friedman , Shane G. Henderson, Fairness and efficiency in web server protocols, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 7: Mor Harchol-Balter , Allen B. Downey, Exploiting process lifetime distributions for dynamic load balancing, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.253-285, Aug. 1997 [doi>10.1145/263326.263344]
• 8: M. Harchol-Balter, B. Schroeder, N. Bansal, and M. Agrawal. Implementation of SRPT scheduling in web servers. ACM Transactions on Computer Systems, 21(2):To appear, May 2003.
• 9: Mor Harchol-Balter , Karl Sigman , Adam Wierman, Asymptotic convergence of scheduling policies with respect to slowdown, Performance Evaluation, v.49 n.1-4, p.241-256, September 2002 [doi>10.1016/S0166-5316(02)00132-3]
• 10: L. Kleinrock. Queueing Systems, volume II. Computer Applications. John Wiley & Sons, 1976.
• 11: R. Perera. The variance of delay time in queueing system M/G/1 with optimal strategy SRPT. Archiv fur Elektronik und Uebertragungstechnik, 47:110--114, 1993.
• 12: Idris A. Rai , Guillaume Urvoy-Keller , Ernst W. Biersack, Analysis of LAS scheduling for job size distributions with high variance, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 13: J. Roberts and L. Massoulie. Bandwidth sharing and admission control for elastic traffic. In ITC Specialist Seminar, 1998.
• 14: L. E. Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16:678--690, 1968.
• 15: L. E. Schrage and L. W. Miller. The queue M/G/1 with the shortest remaining processing time discipline. Operations Research, 14:670--684, 1966.
• 16: F. Schreiber. Properties and applications of the optimal queueing strategy SRPT - a survey. Archiv fur Elektronik und Uebertragungstechnik, 47:372--378, 1993.
• 17: Abraham Silberschatz , Peter Baer Galvin, Operating System Concepts, John Wiley & Sons, Inc., New York, NY, 1999
• 18: W. Stallings. Operating Systems, 2nd Edition. Prentice Hall, 1995.
• 19: Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 20: A. Wierman, N. Bansal, and M. Harchol-Balter. A note comparing response times in the M/GI/1/FB and M/GI/1/PS queues. Operations Research Letters, To appear, 2003.
• 21: R. W. Wolff. Stochastic Modeling and the Theory of Queues. Prentice Hall, 1989.

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Algorithms, Performance

Keywords:
FB, LAS, M/G/1, PS, SET, SRPT, feedback, least attained service, processor sharing, scheduling, shortest elapsed time, shortest remaining processing time, slowdown, unfairness