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?