Seja a memória cache formada por quatro linhas, em que cada linha possui apenas uma única palavra. Se for realizada uma sequência de leituras pelos endereços 0,2,3,2,
0,0,4,0,5,6 respectivamente, qual será o resultado final da memória cache e a taxa de acerto quando for utilizado:
b) mapeamento associativo com política de substituição LRU

Passo 1

Beleza, vamos resolver esse exercício sobre memória cache! A questão fala sobre uma cache com quatro linhas, cada uma contendo uma única palavra. A gente vai analisar uma sequência de leituras pelos endereços 0, 2, 3, 2, 0, 0, 4, 0, 5, 6. Nosso objetivo é descobrir como fica a memória cache no final e qual a taxa de acerto usando mapeamento associativo com a política de substituição LRU (Least Recently Used). Para isso, vamos precisar entender como funciona o mapeamento associativo e a política LRU na gestão da cache.

Passo 2

Primeiro, vamos relembrar o que é mapeamento associativo. Nesse tipo de mapeamento, qualquer bloco da memória principal pode ser colocado em qualquer linha da cache. Isso dá mais flexibilidade comparado a outros métodos como o mapeamento direto. Agora, a política de substituição LRU decide qual bloco substituir quando a cache está cheia: ela substitui o bloco que foi usado há mais tempo, ou seja, o menos recentemente usado.

Passo 3

Vamos iniciar com a cache vazia e percorrer cada acesso na sequência. Vamos também manter um registro de quais blocos estão na cache e a ordem de uso para aplicar a política LRU.
Sequência de leituras: 0, 2, 3, 2, 0, 0, 4, 0, 5, 6
Vamos analisar cada passo:
  1. Acesso 0:
    • Cache está vazia. Falta (miss).
    • Colocamos o bloco 0 na primeira linha.
    • Cache: [0, -, -, -]
    • Ordem de uso: [0]
  2. Acesso 2:
    • Cache: [0, -, -, -]. Bloco 2 não está na cache. Falta.
    • Colocamos o bloco 2 na próxima linha disponível.
    • Cache: [0, 2, -, -]
    • Ordem de uso: [0, 2]
  3. Acesso 3:
    • Cache: [0, 2, -, -]. Bloco 3 não está na cache. Falta.
    • Colocamos o bloco 3 na próxima linha disponível.
    • Cache: [0, 2, 3, -]
    • Ordem de uso: [0, 2, 3]
  4. Acesso 2:
    • Cache: [0, 2, 3, -]. Bloco 2 está na cache. Acerto (hit).
    • Atualizamos a ordem de uso: 2 é o mais recentemente usado.
    • Ordem de uso: [0, 3, 2]
  5. Acesso 0:
    • Cache: [0, 2, 3, -]. Bloco 0 está na cache. Acerto.
    • Atualizamos a ordem de uso: 0 é o mais recentemente usado.
    • Ordem de uso: [3, 2, 0]
  6. Acesso 0:
    • Cache: [0, 2, 3, -]. Bloco 0 está na cache. Acerto.
    • Ordem de uso permanece a mesma.
    • Ordem de uso: [3, 2, 0]
  7. Acesso 4:
    • Cache: [0, 2, 3, -]. Bloco 4 não está na cache. Falta.
    • Temos uma linha disponível (quarta posição). Colocamos o bloco 4 lá.
    • Cache: [0, 2, 3, 4]
    • Ordem de uso: [3, 2, 0, 4]
  8. Acesso 0:
    • Cache: [0, 2, 3, 4]. Bloco 0 está na cache. Acerto.
    • Atualizamos a ordem de uso: 0 é o mais recentemente usado.
    • Ordem de uso: [3, 2, 4, 0]
  9. Acesso 5:
    • Cache: [0, 2, 3, 4]. Bloco 5 não está na cache. Falta.
    • Cache está cheia, então precisamos substituir o bloco menos recentemente usado.
    • Pelo LRU, o bloco 3 é o mais antigo na ordem de uso.
    • Substituímos o bloco 3 pelo bloco 5.
    • Cache: [0, 2, 5, 4]
    • Ordem de uso: [2, 4, 0, 5]
  10. Acesso 6:
    • Cache: [0, 2, 5, 4]. Bloco 6 não está na cache. Falta.
    • Novamente, a cache está cheia. O bloco menos recentemente usado agora é o 2.
    • Substituímos o bloco 2 pelo bloco 6.
    • Cache: [0, 6, 5, 4]
    • Ordem de uso: [4, 0, 5, 6]

Resposta

No final, a memória cache fica assim:
Cache Final = [0, 6, 5, 4]
Para calcular a taxa de acerto, contamos quantos acessos foram acertos:
Total de acessos: 10
Total de acertos: 5 (nos acessos aos endereços 2, 0, 0, 0, 0)
Taxa de acerto:
Então, a taxa de acerto é de 50%.

Exercícios relacionados