Study of the FB Queue in Multiprocessor Systems

• Alexandre Magno de Sousa CEFET/MG
• Cristina Duarte Murta CEFET/MG

Abstract

The Foreground-Background (FB) scheduling policy seems to be quite appropriate for systems that experiences at the same time load with high variability in service times and high traffic intensity. These characteristics can take the system into a critical condition, which can be handled by the FB queue, without requiring knowledge of the task size. This paper presents a study of the FB queue in strongly and weakly coupled distributed systems. The results are evaluated according to the response time and the scheduling fairness. This paper contributes to improve the knowledge on the characteristics of the FB scheduling policy in parallel and distributed environments.

References

Anger, F. D., Hwang, J.-J., and Chow, Y.-C. (1990). Scheduling with Sufficient Loosely Coupled Processors. Journal of Parallel and Distributed Computing, 9(1):87–92.

Bansal, N. and Harchol-Balter, M. (2001). Analysis of SRPT Scheduling: Investigating Unfairness. In Proceedings of ACM SIGMETRICS 2001.

Casavant, T. and Kuhl, J. (1988). A Taxonomy of Scheduling in General-purpose Distributed Computing Systems. Software Engineering, IEEE Transactions on, 14(2).

Conway, R. W., Maxwell, W. L., and Miller, L. W. (2003). Theory of Scheduling. Dover Publications, NY, USA.

Crovella, M. E. and Lipsky, L. (1997). Long-lasting Transient Conditions in Simulations With Heavy-tailed Workloads. In WSC ’97: Proceedings of the 29th conference on Winter simulation, pages 1005–1012, Washington, DC, USA. IEEE Computer Society.

Down, D. G. and Wu, R. (2006). Multi-layered Round robin Routing for Parallel Servers. Queueing Syst. Theory Appl., 53:177–188.

Feng, H. and Misra, V. (2004). On the Relationship between Coefficient of Variation and the Performance of M/G/1 - FB queues. SIGMETRICS Perform. Eval. Rev., 32(2).

Gupta, V. (2008). Finding the Optimal Quantum Size: Sensitivity Analysis of the M/G/1 Round-robin Queue. ACM SIGMETRICS Performance Evaluation Review, 36(2).

Harchol-Balter, M., Crovella, M., and Murta, C. (1999). On Choosing a Task Assignment Policy for a Distributed Server System. IEEE J. of Parallel and Distrib. Computing.

Jain, R. (1991). The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation and Modeling. John Wiley and Sons, New York, NY, USA.

MacDougall, M. H. (1987). Simulating Computer Systems: Techniques and Tools. MIT Press, Cambridge, MA, USA.

Nuyens, M. (2004a). The Foreground-Background Queue. PhD thesis, Universit van Amsterdam - Met samenvatting in het Nederlands.

Nuyens, M. (2004b). The Foreground-Background Queue. PhD thesis, Universit van Amsterdam - Met samenvatting in het Nederlands.

Nuyens, M. and Wierman, A. (2008). The Foreground-Background Queue: A Survey. Perform. Eval., 65(3-4):286–307.

Schrage, L. E. (1968). A Proof of the Optimality of the Shortest Processing Remaining Time Discipline. Operations Research, 16:678–690.

Schrage, L. E. and Miller, L. W. (1966). The Queue M/G/1 with the Shortest Remaining Processing Time Discipline. Operations Research, 14(4):670–684.

Sousa, A. M. and Murta, C. D. (2010). Simulation of the Foreground-Background Queue in Parallel Systems. XI WSCAD–SSC 2010, pages 17–24.

Tanenbaum, A. S. and Steen, M. V. (2007). Distributed Systems Principles and Paradigms. Prentice Hall, USA.

Tanenbaum, A. S. and Woodhull, A. S. (2006). Operating Systems Design and Implementation. Prentice Hall, USA.

Wierman, A. (2007a). Fairness and Classifications. SIGMETRICS Performance Evaluation Review, 34(4):4–12.

Wierman, A. (2007b). Scheduling for Today’s Computer Systems: Bridging Theory and Practice. PhD thesis, School of Comp. Science, Carnegie Mellon Univ., Pittsburgh.