Proportional-share scheduling in single-server and multiple-server computing systems

ABSTRACT

Proportional Share Scheduling (PSS), which is the allocation of prespecified fractions of a certain resource to different classes of customers, has been studied both in the context of the allocation of network bandwidth and of processors. Much of this work has focused on systems with a single scheduler and when all classes of customers are constantly backlogged. We study the objectives and performance of PSS policies for processor scheduling when these conditions do not hold.

REFERENCES

• 1: O. Abuamsha , N. Pekergin, Comparison of Fair Queuing Algorithms with a Stochastic Approach, Proceedings of the 6th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.139, July 19-24, 1998
• 2: S. C. Borst, Optimal probabilistic allocation of customer types to servers, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.116-125, May 15-19, 1995, Ottawa, Ontario, Canada
• 3: [3] O. J. Boxma and J. W. Cohen. The M/G/1 queue with permanent customers. IEEE J. Selected Areas in Communications, 9: 179-184, 1991.
• 4: D. H. J. Epema, Decay-usage scheduling in multiprocessors, ACM Transactions on Computer Systems (TOCS), v.16 n.4, p.367-415, Nov. 1998 [doi>10.1145/292523.292535]
• 5: Jay Sethuraman , Mark S. Squillante, Optimal stochastic scheduling in multiclass parallel queues, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.93-102, May 01-04, 1999, Atlanta, Georgia, United States
• 6: [6] H. Zhang. Services disciplines for guaranteed performance service in packet-switching networks. Proc. of the IEEE, 83: 1374-1396, 1995.

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:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Design, Measurement, Performance, Theory