Adaptive LRU-WAR Algorithm with Page Access Frequency Detection

• Jacinto C. A. Cansado USP
• João Henrique de S. Pereira USP
• Edson T. Midorikawa USP

Abstract

The efficient memory usage in high performance computing systems with timesharing is a difficult challenge. Some research areas on adaptive algorithms concerning memory page replacement, analyze the memory access behavior seeking to maintain in memory the pages that will be used in a near future and discarding the others. This is important due to the high cost of treating page faults. The proposal is to analyze the influence of page access frequency on the adaptive algorithm LRU-WAR, using its structure and applying page replacement with the access frequency analysis, as a function of its execution state. The comparative performance analysis is conducted by using trace files that represent different memory access behaviors.

References

Belady, L. A. (1996) “A study of replacement algorithms for a virtual storage computer”. IBM System Journal, v.5, n.2, p.78-101.

Cassettari, H. H., Midorikawa, E. T. (2004) “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.

Cassettari, H. H., Midorikawa, E. T. (2005) “Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock”. In: Anais do II Workshop de Sistemas Operacionais (WSO 2005), São Leopoldo, RS.

Glass, G., 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.

Jiang, S., 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.

Johnson, T., Shasha, D. (1994) “2Q: a low overhead high performance buffer management replacement algorithm”. In: International Conference on Very Large Data Bases, 20., Santiago, 1994. VLDB’ 94: Proceedings. Santiago: Morgan Kaufmann, 1994. p.439-450.

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., Modha, D.S. (2003) “ARC: a self-tuning, low overhead replacement cache”. In: Conference on File and Storage Technologies, 2., San Francisco, 2003. FAST’ 03: Proceedings. San Francisco: USENIX, 2003. p.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.

Piantola, R. L., Midorikawa, E. T. (2008) “Ajustando o LRU-WAR para uma Política de Gerência de Memória Global”. In: Anais do V Workshop de Sistemas Operacionais (WSO 2008), Belém do Pará, PA.

Robinson, J. T., Devarakonda, M. V. (1990) “Data cache management using frequency-based replacement”. In: ACM SIGMETRICS Conference on Measurement and Modeling of computer systems.

Silberschatz, A., Galvin, P. B.; Gagne, G. (2005) “Operating Systems Concepts”. 7th ed., Wiley.

Smaragdakis, Y., Kaplan, S., Wilson, P. (1999) “EELRU: simple and effective adaptive page replacement”. In: International Conference on Measurement and Modeling of Computer Systems, 24., Atlanta, 1999. SIGMETRICS’ 99: Proceedings. Atlanta: ACM, 1999. p.122-133.

Uhlig, R. A., Mudge, T. N. (1997) “Trace-driven memory simulation: a survey”. ACM Computing Surveys, v.29, n.2, p.128-170.