Estudo da Fila FB em Sistemas Multiprocessados
Resumo
A política de escalonamento FB (Foreground-Background) se mostra bastante apropriada para sistemas que experimentam, ao mesmo tempo, cargas com grande variabilidade no tempo de serviço e intensidade de tráfego elevada. Estas características colocam o sistema em um estado crítico, que pode ser tratado pela fila FB, sem exigir conhecimento do tamanho da tarefa. Este artigo apresenta um estudo da fila FB em ambientes distribuídos, para sistemas fortemente e fracamente acoplados. Os resultados são avaliados quanto ao tempo de execução das tarefas e quanto à justiça do escalonamento. Este artigo contribui para o conhecimento mais amplo das características da fila FB em ambientes paralelos e distribuídos.Referências
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.
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.
Publicado
19/07/2011
Como Citar
SOUSA, Alexandre Magno de; MURTA, Cristina Duarte.
Estudo da Fila FB em Sistemas Multiprocessados. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 10. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 2047-2060.
ISSN 2595-6167.
