Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais

• Hugo Henrique Cassettari USP
• Edson Toshimi Midorikawa USP

Resumo

Algoritmos de substituição de páginas influenciam diretamente o desempenho de sistemas computacionais que utilizam memória virtual paginada. Algoritmos adaptativos têm a capacidade de modificar o seu comportamento ao longo do tempo, de acordo com as características de processamento observadas. Este artigo apresenta um novo algoritmo adaptativo para substituição de páginas, cujo objetivo é minimizar falhas detectadas no algoritmo LRU sem perder a sua simplicidade computacional: o LRU-WAR (LRU with Working Area Restriction / LRU com Confinamento da Área de Trabalho).

Referências

BANSAL, S.; MODHA, D.S. CAR: Clock with adaptive replacement. In: CONFERENCE ON FILE AND STORAGE TECHNOLOGIES, 3., San Francisco, 2004. FAST’ 04: Proceedings. San Francisco: USENIX, 2004. p.187-200.

CASSETTARI, H.H. Análise da localidade de programas e desenvolvimento de algoritmos adaptativos para substituição de páginas. 2004. 118p. Dissertação (Mestrado) – Escola Politécnica, Universidade de São Paulo. São Paulo, 2004.

CASSETTARI, H.H.; MIDORIKAWA, E.T. Caracterização de cargas de trabalho em estudos sobre gerência de memória virtual. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO, 3., Salvador, 2004. WPerformance’ 04: Anais. Salvador: SBC, 2004.

CHOI, J. et al. An implementation study of a detection-based adaptive block replacement scheme. In: ANNUAL TECHNICAL CONFERENCE, 4., Monterey, 1999. USENIX’ 99: Proceedings. Monterey: USENIX, 1999. p.239-252.

____. Towards application/file-level characterization of block references: a case for fine-grained buffer management. In: INTERNATIONAL CONFERENCE ON MEASUREMENT AND MODELING OF COMPUTER SYSTEMS, 25., Santa Clara, 2000. SIGMETRICS’ 00: Proceedings. Santa Clara: ACM, 2000. p.286-295.

DENNING, P.J. The working set model for program behavior. Communications of the ACM, v.11, n.5, p.323-333, 1968.

GLASS, G.; CAO, P. Adaptive page replacement based on memory reference behavior. In: INTERNATIONAL CONFERENCE ON MEASUREMENT AND MODELING OF COMPUTER SYSTEMS, 22., Seattle, 1997. SIGMETRICS’ 97: Proceedings. Seattle: ACM, 1997. p.115-126.

JIANG, S.; ZHANG, X. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. In: INTERNATIONAL CONFERENCE ON MEASUREMENT AND MODELING OF COMPUTER SYSTEMS, 27., Marina Del Rey, 2002. SIGMETRICS’ 02: Proceedings. Marina Del Rey: ACM, 2002. p.31-42.

JOHNSON, T.; SHASHA, D. 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.

KIM, J.M. et al. A low-overhead high-performance unified buffer management scheme that exploits sequential and looping references. In: SYMPOSIUM ON OPERATING SYSTEM DESIGN AND IMPLEMENTATION, 4., San Diego, 2000. OSDI’ 00: Proceedings. San Diego: USENIX, 2000. p.119-134.

MEGIDDO, N.; MODHA, D.S. 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. Uma nova estratégia para a gerência de memória para sistemas de computação de alto desempenho. 1997. 193p. Tese (Doutorado) – Escola Politécnica, Universidade de São Paulo. São Paulo, 1997.

SMARAGDAKIS, Y.; KAPLAN, S.; WILSON, P. 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. Trace-driven memory simulation: a survey. ACM Computing Surveys, v.29, n.2, p.128-170, 1997.