O Algoritmo LFU
- Algoritmo de gerência de memória
- Limpa dados que não frequentemente usados
- Cada página possui um contador
- Página com menor contador é substituída
- Contador é zerado quando página é substituída
Arquitetura geral de um Computador
- Unidade Central de Processamento (CPU)
- Unidade de Controle
- Unidade Lógica e Aritmética
- Registradores
- Interconexão da CPU
- Memória Principal
- Dispositivos de E/S
- Sistemas de interconexão
Desvantagens do LFU
Hierarquia de Memórias
Giovanni A. Begossi
Iana C. S. de Albuquerque
João P. L. Antunes
Mara C. F. de Oliveira
Sanderson D. de M. Adelino
- Objetos muito referenciados no passado que estão em desuso permanecem em cache
- Deficiências quando o padrão de acesso é sequencial (vetor, lista), dentro de loops...
Isso nos leva às
evoluções
do
Vamos ver na
Prática?
Memória cache
N° de linhas da memória cache < N° de blocos da RAM
- Disparidade entre velocidade de processador e RAM
- Cache como intermediária entre RAM e processador
- Funcionamento: Cache hit e cache miss
- Mapeamento
- Capacidade reduzida
- Algoritmos de substituição de dados
F
U
L
east requently sed
Menos Frequentemente Utilizado
LFU-DA (LFU-Dynamic Aging)
LFU-Aging
- Problema: A eficiencia da LFU-Aging depende dos
- valores passados como parâmetros para seus limites
- No LFU-DA cada requisição ao objeto i dispara uma função que recalcula seu valor Ki pela fórmula:
- Ki = fi + L
- O algoritmo substitui o objeto com menor Ki e atribui seu valor a L
fi = frequencia de i
L = fator de envelhecimento
- Problema: Os objetos que foram muito referenciados no passado e estão em desuso permanecem em cache pois o LFU não apaga essas referências anteriores.
- LFU Aging insere dois parâmetros ao LFU:
- Limitador de valor médio da frequência (se passa desse valor é dividido por 2);
- Limite de frequência individual do objeto.
Comparação do tempo de execução de todas as políticas de substituição de cache