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
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:
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:
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
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:
a) mapeamento direto
Qual é o problema que uma hierarquia de memória tenta resolver?
Uma cache de conjunto associativo contém ao todo 64 linhas divididas em conjuntos de 4 linhas. A memória principal contém 4 K blocos de 128 palavras cada. Mostre o formato dos endereços da memória principal e da cache. Determine o tamanho de s, de w.
Considere uma máquina com uma memória principal endereçável por byte (ou seja, 1 célula palavra=1 byte) com bytes e um tamanho de bloco de 8 bytes. Suponha que essa máquina utilize uma cache de 32 linhas mapeadas diretamente. Responda as questões abaixo.
c) Quantos bytes de memória podem ser armazenados na cache, ou seja, qual a capacidade da cache?