Question

2. A memória cache é um dispositivo de armazenamento localizado no processador e tem como principal função de servir de um acesso rápido ao processador. Entretanto, seu espaço é limitado. Quando a cache fica cheia entra em cena os algoritmos de substituição. Explique, com suas palavras, o funcionamento dos algoritmos LRU, FIFO e LFU

Answer 1

Resposta e Explicação:

O LRU é lido como Least Recently Used:

• A vantagem do LRU é que ele escolhe o bloco que não é usado há muito tempo.
• A desvantagem é que tem um certo custo para guardar essa informação;
• Pode usar um bit pra indicar que a linha foi usada pelo processador;
• Em caches associativas por conjuntos de 2 linhas por conjunto;
• É simples de implementar;
• Quando uma das linhas for acessada, o bit é setado em (1) e o bit da outra linha do conjunto é zerado(0);

• Quando aumenta a associatividade, o problema se torna maior e fica difícil sua implementação.

Exemplo: Mantém as listas mais acessadas no topo e as menos acessadas por último.

O FIFO é lido como First-In, First-Out:

• É um algoritmo de fila simples;
• Nesse esquema de fila, o primeiro a chegar, é o primeiro a sair;
• A escolha de quem sai independe da frequência de uso daquele bloco.

Exemplo: Num controle de estoque, o primeiro produto que chega ao estoque será o primeiro a sair.

O LFU é lido como Least Frequently Used:

As características padrão desse método envolvem o sistema manter o controle do número de vezes que um bloco é referenciado na memória. Quando o cache estiver cheio e exigir mais espaço, o sistema limpará o item com a frequência de referência mais baixa.

Exemplo: Se a memória identificar que as imagens de um site são menos acessadas, ele vai limpar essas imagens pra que abra espaço pra sites mais acessados.