LRU

Algoritmo de substituição de páginas LRU 

O LRU (Least Recently Used) é um algoritmo de substituição de página que apresenta um bom desempenho substituindo a página menos recentemente usada. Esta política foi definida baseada na seguinte observação: se a página está sendo intensamente referenciada pelas instruções é muito provável que ela seja novamente referenciada pelas instruções seguintes e, de modo oposto, aquelas que não foram acessadas nas últimas instruções também é provável que não sejam acessadas nas próximas. Apesar de o LRU apresentar um bom desempenho ele também possui  algumas deficiências [CAS03] quando o padrão de acesso é sequencial (em estruturas de dados do tipo vetor, lista, árvore), dentro de loops, etc. Diante dessas deficiências foram propostas algumas variações do LRU, dentre eles destacamos o LRU-K. Este algoritmo não substitui aquela que foi referenciada há mais tempo e sim quando ocorreu seu k-último acesso. Por exemplo, LRU-2 substituirá a página que teve seu penúltimo acesso feito há mais tempo e LRU-3 observará o antepenúltimo e assim por diante.

A implementação do LRU também pode ser feita através de uma lista, mantendo as páginas mais referenciadas no início (cabeça) e a menos referenciadas no final da lista. Portanto, ao substituir retira-se a página que está no final da lista. O maior problema com esta organização é que a lista deve ser atualizada a cada nova referência efetuada sobre as páginas, o que torna alto o custo dessamanutenção.