Comparing FB and PS scheduling policies

ABSTRACT

In this paper we obtain new results concerning the expected response time of the foreground-background (FB) scheduling discipline and its comparison with processor sharing (PS). Some results previously derived for job sizes with finite second moment or bounded sizes, are extended to infinite second moments. New bounds and asymptotic results are also derived. We show that for job sizes with infinite second moment large jobs may benefit from the FB scheduling discipline although this discipline favors short jobs. For certain distributions all jobs sizes may even benefit from FB with respect to PS showing that the performance benefits obtained by some job sizes need not be obtained at the expense of others.

REFERENCES

• 1: F. Baccelli and P. Bremaud. Elements of queuing theory: Palm martingale calculus and stochastic recurrences. Springer, 2003.
• 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: 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]
• 4: W. Feller. An introduction to probability theory and its applications, vol. II. John Wiley and Sons, 1971.
• 5: 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]
• 6: L. Kleinrock. Queueing Systems, vol. 2. John Wiley and Sons, 1976.
• 7: R. Núnez-Queija. Queues with equally heavy sojourn time and service requirement distributions. Annals of Operations Research, 113:101--117, 2002.
• 8: M. Nuyens, A. Wierman, and B. Zwart. Preventing large sojourn times with smart scheduling. Submitted, 2005.
• 9: T. M. O'Donovan. Distribution of attained service and residual service in general queueing systems. Operations Research, 22:570--575, 1974.
• 10: 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
• 11: Adam Wierman , Mor Harchol-Balter, Classifying scheduling policies with respect to unfairness in an M/GI/1, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA