Algoritmo Adaptativo LRU-WAR com Detecção de Freqüência de Acessos de Páginas

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

Resumo

O uso da memória de forma eficiente, em sistemas multiprogramados de alto desempenho, é um grande desafio. Nesse sentido, linhas de pesquisa por algoritmos adaptativos de substituição de páginas de memória têm sido desenvolvidas com o intuito de explorar o comportamento de acesso à memória por programas, procurando manter na memória as páginas que serão utilizadas em um futuro próximo e descartando as demais devido ao alto custo do tratamento de uma falta de página. O presente trabalho avalia a influência da freqüência de acesso a páginas no algoritmo adaptativo LRU-WAR utilizando sua estrutura como base e aplicando a substituição de página com a análise da freqüência de acesso em função de seu estado de execução. Uma análise comparativa do desempenho é realizada utilizando-se arquivos de trace que representam diferentes comportamentos de acesso à memória.

Referências

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.