Sojourn times in (discrete) time shared systems and their continuous time limits

ABSTRACT

We consider two classes of preemptive processor sharing scheduling policies in which the instantaneous weight given to a customer depends on a) the amount of service already imparted to the customer (Age-based scheduling), or b) the amount of service yet to be imparted to the customer (Residual Processing Time, RPT, based scheduling). We analyze the system for the mean sojourn time of a tagged customer conditioned on its service requirement. The main contribution of this article are:i) We decompose the sojourn time of a customer into two parts: a) the contribution of the descendants of the customer, and b) the contribution of the jobs (and their descendants) which the customer sees on arrival. For the preemptive system under consideration, it is shown that the behavior of the mean sojourn time for large values of service requirement is determined only by the first term above. We provide a closed form expression for this component of the sojourn time for general Age-based and RPT-based scheduling disciplines.iii) If the weight assigned to a customer with an age x units is xα for some α, we show that the behavior of mean sojourn time conditioned on service requirement is asymptotically linear for all 0 ≤ α ≤ 1. Moreover, this asymptotic slope is same for 0 ≤ α < 1 and shows a discontinuity at α = 1.

REFERENCES

• 1: A. A. Kherani and R. Nunez-Queija. TCP as an implementation of Age based scheduling. In proceedings of IEEE Infocom 2006, Barcelona, April 2006.
• 2: K. Avrachenkov, U. Ayesta, P. Brown, R. Nez-Queija, "Discriminatory Processor Sharing Revisited," In Proceedings of INFOCOM 2005, Miami, March 2005.
• 3: 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
• 4: S. C. Borst , O. J. Boxma , R. Núñez-Queija , A. P. Zwart, The impact of the service discipline on delay asymptotics, Performance Evaluation, v.54 n.2, p.175-206, 1 October 2003 [doi>10.1016/S0166-5316(03)00071-3]
• 5: Xuan Chen , John Heidemann, Preferential treatment for short flows to reduce web latency, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.6, p.779-794, 22 April 2003 [doi>10.1016/S1389-1286(02)00439-5]
• 6: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 7: E. G. Coffman, Jr. , R. R. Muntz , H. Trotter, Waiting Time Distributions for Processor-Sharing Systems, Journal of the ACM (JACM), v.17 n.1, p.123-130, Jan. 1970 [doi>10.1145/321556.321568]
• 8: G. Fayolle , I. Mitrani , R. Iasnogorodski, Sharing a Processor Among Many Job Classes, Journal of the ACM (JACM), v.27 n.3, p.519-532, July 1980 [doi>10.1145/322203.322212]
• 9: Mor Harchol-Balter , Bianca Schroeder , Nikhil Bansal , Mukesh Agrawal, Size-based scheduling to improve web performance, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.207-233, May 2003 [doi>10.1145/762483.762486]
• 10: 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]
• 11: L. Kleinrock, "Queuing Systems, Volume II: Computer Applications," Wiley, New York, 1976.
• 12: Michel Mandjes , Bert Zwart, Large deviations of sojourn times in processor sharing queues, Queueing Systems: Theory and Applications, v.52 n.4, p.237-250, April 2006 [doi>10.1007/s11134-006-5567-6]
• 13: S. Padhy and A. A. Kherani. Tail Equivalence for Some Time-shared Systems. submitted.
• 14: Idris A. Rai , Guillaume Urvoy-Keller , Mary K. Vernon , Ernst W. Biersack, Performance analysis of LAS-based scheduling disciplines in a packet switched network, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 15: R. Righter and J. G. Shanthikumar, "Scheduling Multiclass Single Server Queueing Systems to Stochastically Maximize the Number of Successful Departures," Probability in the Engineering and the Informational Sciences, vol. 3, pp. 323--333, 1989.
• 16: R. Schassberger. A new approach to the M/G/1 processor-sharing queue. Advances in applied probability16, 202--213.
• 17: Schrage, L. E. (1968). A proof of the optimality of the shortest remaining processing time discipline. Oper. Res.16, 687--690.
• 18: Righter, R., Shanthikumar, J. G. (1989). Scheduling multiclass single-server queueing systems to stochastically maximize the number of successful departures. Prob. Eng. Inf. Sc.3, 323--333.
• 19: R. W. Wolff (1989). Stochastic Modeling and the Theory of Queues, Prentice Hall.
• 20: C. W. Yang and S. Shakkottai. "Asymptotic Evaluation of Delay with the SRPT Scheduler," Submitted for journal publication, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
      I.6.8 Types of Simulation
          Subjects: Continuous

General Terms:
Theory