Scheduling Based on Process Behavior Analysis
Resumo
Pesquisas na área de escalonamento têm procurado entender a dinamicidade de aplicações, a fim de melhorar políticas de alocação de recursos. Estudos recentes analisam o comportamento de processos individuais sem considerar como eles interagem entre si. Essa limitação motivou este trabalho, que propõe uma nova abordagem de escalonamento de processos com base na maneira como as aplicações interagem quando competindo por recursos. Essa abordagem é baseada em conceitos de sistemas dinâmicos segundo os quais organizações estáveis podem ser alcançadas por meio de pertubações nos componentes do sistema. Foram analisados processos com diferentes ocupações a fim de obter estados comportamentais que representam um componente do sistema. Em seguida, combinou-se a execução de processos, priorizando os de maior carga estimada de CPU. Intercala-se, portanto, a execução de processos de acordo com suas cargas de trabalhos preditas, o que tende a um sistema mais estável. No contexto deste artigo, o termo sistema se refere à combinação de estados comportamentais de todos os processos. Para validar a abordagem, considerou-se cenários simulados representando diferentes cargas de um ambiente computacional obtendo, como resultado, tempos de execução menores, ou seja, maior desempenho.
Referências
Chunlin, L. and Layuan, L. (2009). A system-centric scheduling policy for optimizing objectives of application and resource in grid computing. Computers and Industrial Engineering, 57(3):1052–1061.
Devarakonda, M. V. and Iyer, R. K. (1989). Predictability of process resource usage: A measurement-based study on UNIX. IEEE Transactions on Software Engineering, 15(12):1579–1586.
Dinda, P. A. (2001). Online prediction of the running time of tasks. In IEEE International Symposium on High Performance Distributed Computing, pages 383–382.
Dodonov, E. and Mello, R. F. (2010). A novel approach for distributed application scheduling based on prediction of communication events. Future Generation Computer Systems, 26(5):740–752.
Downey, A. B. (1997). Predicting queue times on space-sharing parallel computers. In International Symposium on Parallel Processing, pages 209–218.
Feitelson, D. G. and Nitzberg, B. (1995). Job characteristics of a production parallel scientific workload on the NASA ames iPSC/860. In Job Scheduling Strategies for Parallel Processing, volume 949 of LNCS, pages 337–360. Springer-Verlag.
Feitelson, D. G., Rudolph, L., Schwiegelshohn, U., Sevcik, K. C., and Wong, P. (1997). Theory and practice in parallel job scheduling. In Job Scheduling Strategies for Parallel Processing, volume 1291 of LNCS, pages 1–34. Springer-Verlag.
Ferrari, D. and Zhou, S. (1988). An empirical investigation of load indices for load balancing applications. In International Symposium on Computer Performance Modelling, Measurement and Evaluation, pages 515–528.
Fraser, A. M. and Swinney, H. L. (1986). Independent coordinates for strange attractors from mutual information. Phys. Rev. A, 33(2):1134–1140.
Gibbons, R. (1997). A historical application profiler for use by parallel schedulers. In Job Scheduling Strategies for Parallel Processing, volume 1291 of LNCS, pages 58–77. Springer-Verlag.
González-Miranda, J. M. (2004). Syncronization and Control of Chaos: An Introduction for Scientists and Engineers. Imperial College Press.
Kennedy, J., Eberhart, R. C., and Shi, Y. (2001). Swarm Intelligence. Morgan Kaufmann Publishers.
Kennel, M. B., Brown, R., and Abarbanel, H. D. I. (1992). Determining embedding dimension for phase-space reconstruction using a geometrical construction. Phys. Rev. A, 45(6):3403–3411.
Krishnaswamy, S., Loke, S. W., and Zaslavsky, A. (2004). Estimating computation times of data-intensive applications. IEEE Distributed Systems Online, 5(4):1–12.
Lee, B.-D. and Schopf, J. M. (2003). Run-time prediction of parallel applications on shared environments. In IEEE International Conference on Cluster Computing, pages 487–491.
Mello, R. F. and Yang, L. (2009). Prediction of dynamical, nonlinear, and unstable process behavior. The Journal of Supercomputing, 49(1):22–41.
Schopf, J. M. and Berman, F. (1999). Stochastic scheduling. In ACM/IEEE Conference on Supercomputing.
Sevcik, K. C. (1989). Characterizations of parallelism in applications and their use in scheduling. Performance Evaluation Review, 17(1):171–180.
Smith, W., Foster, I., and Taylor, V. (2004). Predicting application run times with historical information. Journal of Parallel and Distributed Computing, 64(9):1007–1016.
Takens, F. (1980). Detecting strange attractors in turbulence. In Dynamical Systems and Turbulence, pages 366–381. Springer.
Whitney, H. (1936). Differentiable manifolds. The Annals of Mathematics, 37(3):645–680.
