Scheduling Based on Process Behavior Analysis
Abstract
Process scheduling researches attempt to understand the dynamics of applications in order to improve resource allocation policies. Recent studies in this area have analyzed the behavior of single processes without considering how they interact with each other. This drawback motivated this paper, which proposes a new process scheduling approach based on how applications interact when competing for resources. This approach is based on concepts of dynamical systems theory which state that stabler organizations can be reached by means of perturbations in system components. First, we analyze process occupation variables to obtain behavioral states which represent a system component here. Next, we combine the execution of processes by prioritizing the one with higher estimated CPU load. The execution of processes is then interleaved according to their predicted workloads and the system tends to be stabler. Here, the term system refers to the combination of behavioral states of all processes. To validate this approach, we consider simulated scenarios representing different workloads of a computational environment, obtaining shorter execution times and, therefore, higher performance as result.
References
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.
