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
,
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
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
. 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:
-
Acesso 0:
- Cache está vazia. Falta (miss).
- Colocamos o bloco 0 na primeira linha.
- Cache: [0, -, -, -]
- Ordem de uso: [0]
-
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]
-
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]
-
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]
-
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]
-
Acesso 0:
- Cache: [0, 2, 3, -]. Bloco 0 está na cache. Acerto.
- Ordem de uso permanece a mesma.
- Ordem de uso: [3, 2, 0]
-
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]
-
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]
-
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]
-
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:
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%.