Application and Analysis of Feedback Control Theory in Handling Page Faults in Memory Management Systems

• Ivo Santos Cavalcante Carneiro UFBA
• Luciano Porto Barreto UFBA
• Alirio Santos de Sá UFBA

Abstract

The static nature of traditional page replacement algorithms make them unsuitable to handle sudden workload changes or variations in memory access patterns. Several adaptive algorithms have been designed in order to cope with this inability, however, they still lack flexibility to handle unpredicted scenarios. This paper presents a new approach, based on Control Theory, which is able to both properly manage OS paging as well as to adapt to disturbances introduced into the system.

References

Ang, K., Chong, G., Li, Y., Ltd, Y., and Singapore, S. (2005). PID control system analysis, design, and technology. IEEE Transactions on Control Systems Technology, 6LRU com Confinamento da Área de Trabalho 2377 13(4):559–576.

Belady, L., Nelson, R. A., and Shedler, G. S. (1969). An anomaly in space-time characteristics of certain programs running in a paging machine. Communications of the ACM, 12.

Cassettari, H. H. (2004). Análise da localidade de programas e desenvolvimento de algoritmos adaptativos para substituição de página. Master’s thesis, Escola Politécnica da Universidade de São Paulo.

Cassettari, H. H. and Midorikawa, E. T. (2004). Algoritmo adaptativo de substituição de páginas LRU-WAR: Exploração do modelo LRU com detecção de acessos sequenciais. Anais do XXIV Congresso da Sociedade Brasileira de Computação (SBC 2004), 1.

Chu, W. W. and Opderbeck, H. (1976). Program behavior and the Page-Fault-Frequency replacement algorithm. IEEE Computer.

Denning, P. J. (1968). The working set model for program behavior. Communications of the ACM, 11(5).

Denning, P. J. (1970). Virtual memory. ACM Computing Surveys, 2(3).

Diao, Y., Hellerstein, J., Parekh, S., Griffith, R., Kaiser, G., Phung, D., Center, I., and Hawthorne, N. (2005). A control theory foundation for self-managing computing systems. IEEE journal on selected areas in communications, 23(12):2213–2222.

Draper, N. and Smith, H. (1998). Applied regression analysis. Wiley Series in Probability and Statistics. Wiley-Interscience, 3 edition.

Fengyuan, R. and Chuang, L. (2003). Speed up the responsiveness of active queue management system. IEICE Transactions on CommunicationsE86-B (2), pages 630–636.

Glass, G. and Cao, P. (1997). Adaptive page replacement based on memory reference behavior. Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, pages 115–126.

Hellerstein, J. L., Diao, Y., Parekh, S., and Tilbury, D. M. (2004). Feedback Control of Computing Systems. Wiley-IEEE.

Hollot, C., Misra, V., Towsley, D., and Gong, W. (2001). A control theoretic analysis of RED. In IEEE INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, volume 3.

Majumdar, R., Moudgalya, K., and Ramamritham, K. (2003). Adaptive coherency maintenance techniques for time-varying data. Real-Time Systems Symposium, 2003. RTSS 2003. 24th IEEE, pages 98–107.

Majumdar, R., Ramamritham, K., Banavar, R., and Moudgalya, K. (2004). Disseminating dynamic data with qos guarantee in a wide area network: a practical control theoretic approach. Real-Time and Embedded Technology and Applications Symposium, 2004. Proceedings. RTAS 2004. 10th IEEE, pages 510–517.

Ogata, K. (1990). Modern Control engineering. Prentice Hall, Englewood Cliffs, 2nd edition.

Ogata, K. (1995). Discrete-Time Control Systems. Prentice-Hall, Upper Saddle River, NJ 07458, USA, 2nd edition.

2378 Shah, S. B., Moudgalva, K. M., and Ramamritham, K. (2008). Feedback control of internet applications involving the tracking of dynamic data. In Proc. 17th IFAC World Congress, Seoul, Korea.

Simon, D. (2002). Analyzing control system robustness. Potentials, IEEE, 21(1):16–19.

Smaragdakis, Y., Kaplan, S., and Wilson, P. (2003). The EELRU adaptive replacement algorithm. Performance Evaluation, 53(2):93–123.