Adjusting LRU-WAR for a Global Memory Management Policy

• Ricardo L. Piantola USP
• Edson T. Midorikawa USP

Abstract

Even with recent advances in Computer Architecture, the memory wall problem has not been solved yet. In order to lessen the performance difference between processor and memory, it is essential to create new memory management strategies, which are stronger in performance. Operating Systems generally use global policies for memory management. The adaptive strategies have as principle to adapt their behaviour based on programs memory access patterns. Its use in multiprogrammed environment has not been properly examined in previous studies. This paper intends to present a strategy to adjust LRU-WAR in order to obtain a good performance in a global memory management system. The results show that the same strategy can be used in algorithms following the same adaptive principle that LRU-WAR does.

References

Bansal, S. and Modha, D. S. (2004) “CAR: Clock with Adaptive Replacement”, In Proc. of the USENIX Conference on File and Storage Technologies (FAST’04), San Francisco, pp.187-200.

Cassettari, H. H. (2004). “Análise da Localidade de Programas e Desenvolvimento de Algoritmos Adaptativos para Substituição de Páginas.” Dissertação de Mestrado. Escola Politécnica da Universidade de São Paulo, 2004.

Cassettari, H.H. and Midorikawa, E.T. (2004a) “Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual”, In Anais do III Workshop em Desempenho de Sistemas Computacionais e de Comunicação (WPerformance 2004), Salvador, BA.

Cassettari, H.H. and Midorikawa, E.T. (2004b) “Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais”. In: Anais do I Workshop de Sistemas Operacionais (WSO 2004), Salvador, BA.

Denning, P.J. (1968) “The working set model for program behavior”. In: Communications of the ACM 11, 5, pp. 323-333.

Glass, G. and Cao, P. (1997) “Adaptive Page Replacement Based on Memory Reference Behavior”, In Proc. of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’97), Seattle, pp.115-126.

Intel. (2008). “Profile-Guided Optimizations Overview”. Disponível em [link]. Acesso em 16/03/2008.

Jiang, S. and Zhang, X. (2002) “LIRS: An Efficient Low Inter-Reference Recency Set Replacement Policy to Improve Buffer Cache Performance”, In Proc. of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’02), Marina Del Rey, pp.31-42.

Kim, J.M. et al. “A low-overhead high-performance unified buffer management scheme that exploit sequential and looping references”, In: Symposium on Operating System Design and Implementation, 4., San Diego, 2000. OSDI' 2000: Proceedings. San Diego: USENIX, 2000 pp.119-134.

Lee, D. et al. (2001) “LRFU: a spectrum of policies that subsumes the Least Recently Used and Least Frequently Used policies”. IEEE Transactions on Computers, vol.50, n.12, p.1352-1361.

Megiddo, N. and Modha, D. S. (2003) “ARC: A Self-Tuning, Low Overhead Replacement Cache”, In Proc. of the USENIX Conference on File and Storage Technologies (FAST’03), San Francisco, pp.115-130.

Midorikawa, E.T., Piantola, R.L., Cassettari, H.H. (2007) “Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas”. In: Anais do IV Workshop de Sistemas Operacionais (WSO 2007), Rio de Janeiro, RJ.

Sabeghil, M. and Yaghmaee (2006), M. H. “Using fuzzy logic to improve cache replacement decisions”. IJCSNS International Journal of Computer Science and Network Security, Seoul, v.6, n.3A, pages182-188.

Smaragdakis, Y., Kaplan, S., and Wilson, P. (1999) “EELRU: Simple and Effective Adaptive Page Replacement”, In Proc. of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’99), Atlanta, pp.122-133.