Arquitetura e Organização de computadores - Hierarquia de Memória

Prévia do material em texto

Profa. Alexandra L. Zimpeck
alexandra.zimpeck@ucpel.edu.br
ARQUITETURA E ORGANIZAÇÃO DE 
COMPUTADORES
Algoritmos de substituição da 
memória cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
HIERARQUIA DE MEMÓRIA
§ Restrições de projeto
­ Capacidade (novas aplicações)
­ Velocidade (processador)
­ Custo (compatível)
§ Diversas tecnologias são usadas para implementar os sistemas 
de memória
­ Tempo de acesso mais rápido, maior o custo por bit
­ Maior capacidade, menos custo por bit
­ Maior capacidade, maior tempo de espera
2
Organizar a memória hierarquicamente
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
HIERARQUIA DE MEMÓRIA
3
Memória Interna
Memória ExternaArmazenamento
De Segurança
Registradores
Memória cache
Memória principal
Disco magnético, 
CD, DVD, SSD
Fita magnética,
WORM
Diminuição do 
custo por bit
Aumento da 
capacidade
Aumento do tempo 
de acesso
Frequência de 
acesso a memória 
pelo processador 
diminui
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
MEMÓRIA INTERNA
4
CPU
L1
L2
Memória Principal
SRAM (RAM Estática)
DRAM (RAM Dinâmica)
Registradores
M
em
ór
ia
 C
ac
he
A cache contém uma 
cópia de uma parte 
da memória principal.
L3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
HIT E MISS DE MEMÓRIA
§ HIT de MEMÓRIA ou ACERTO
Informação desejada é encontrada na memória mais rápida.
§ MISS de MEMÓRIA ou ERRO ou FALHA
Informação desejada não é encontrada na memória mais rápida;
Informação é buscada na memória mais lenta;
Informação é copiada da memória mais lenta para a memória mais
rápida.
5
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
6
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
7
1
3
4
7
Se a cache estiver vazia, primeiramente 
completamos ela.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
8
1, 6
3
4
7
1 está a mais tempo na cache, por isso é 
substituído pelo 6.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
9
1, 6
3
4
7
4 já está na cache, nenhum dado é 
substituído!
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
10
1, 6
3
4
7
3 já está na cache, nenhum dado é 
substituído!
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
11
1, 6
3
4
7
6 já está na cache, nenhum dado é 
substituído!
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
12
1, 6
3, 8
4
7
3 está a mais tempo na cache, por isso é 
substituído pelo 8.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
13
1, 6
3, 8
4, 3
7
4 está a mais tempo na cache, por isso é 
substituído pelo 3.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
14
1, 6
3, 8
4, 3
7, 4
7 está a mais tempo na cache, por isso é 
substituído pelo 4.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
15
1, 6, 1
3, 8
4, 3
7, 4
6 está a mais tempo na cache, por isso é 
substituído pelo 1.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
16
1, 6, 1
3, 8
4, 3
7, 4
8 já está na cache, nenhum dado é 
substituído!
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
17
1, 6, 1
3, 8
4, 3
7, 4
3 já está na cache, nenhum dado é 
substituído!
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
18
1, 6, 1
3, 8
4, 3
7, 4
4 já está na cache, nenhum dado é 
substituído!
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
19
1, 6, 1
3, 8, 9
4, 3
7, 4
8 está a mais tempo na cache, por isso é 
substituído pelo 9.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
20
1, 6, 1
3, 8, 9
4, 3, 8
7, 4
3 está a mais tempo na cache, por isso é 
substituído pelo 8.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO FIFO 
First In First Out
Substitui o bloco que foi armazenado primeiro na cache.
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
21
1, 6, 1
3, 8, 9
4, 3, 8
7, 4
7 substituições na memória cache.
Sequência de valores na cache
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
22
Coloco o primeiro 
dado na cache. 
Todos os contadores 
são iguais a zero.
1
Li
nh
as
Sequência de valoresdos contadores Sequência de valores na cache
0
1
2
3
0 
0
0
0
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
23
0 1
0 0
0 0
0 0
Coloco o segundo 
dado na cache. 
Incremento o 
contador da linha 0 
(está 1x sem ser 
acessado).
1
3
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
24
0 1 2
0 0 1
0 0 0
0 0 0
Coloco o terceiro 
dado na cache. 
Incremento os 
contadores da 
linha 0 (2) e
da linha 1 (1).
1
3
4Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
25
0 1 2 3
0 0 1 2
0 0 0 1
0 0 0 0
Coloco o quarto 
dado na cache. 
Incremento os 
contadores da 
linha 0 (3), da
linha 1 (2) e da 
linha 2 (1).
1
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
26
0 1 2 3 0
0 0 1 2 3
0 0 0 1 2
0 0 0 0 1
Cache cheia: dado 
precisa ser substituído!
Qual linha está mais 
tempo sem ser 
acessada (maior 
contador)? Linha 0. 
Contador é zerado.
1, 6
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
27
0 1 2 3 0 1
0 0 1 2 3 4
0 0 0 1 2 0
0 0 0 0 1 2
Dado está na linha 2 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada.
Os demais são 
incrementados.
1, 6
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
28
0 1 2 3 0 1 2
0 0 1 2 3 4 0
0 0 0 1 2 0 1
0 0 0 0 1 2 3
Dado está na linha 1 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada.
Os demais são 
incrementados.
1, 6
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
29
0 1 2 3 0 1 2 0
0 0 1 2 3 4 0 1
0 0 0 1 2 0 1 2
0 0 0 0 1 2 3 4
Dado está na linha 0 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada. Os demais 
são incrementados.
1, 6
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
30
0 1 2 3 0 1 2 0 1
0 0 1 2 3 4 0 1 2
0 0 0 1 2 0 1 2 3
0 0 0 0 1 2 3 4 0
Cache cheia: dado 
precisa ser substituído!
Qual linha está mais 
tempo sem ser 
acessada (maior 
contador)? Linha 3. 
Contador é zerado.
1, 6
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
31
0 1 2 3 0 1 2 0 1 2
0 0 1 2 3 4 0 1 2 0
0 0 0 1 2 0 1 2 3 4
0 0 0 0 1 2 3 4 0 1
Dado está na linha 1 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada. Os demais 
são incrementados.
1, 6
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
32
0 1 2 3 0 1 2 0 1 2 3
0 0 1 2 3 4 0 1 2 0 1
0 0 0 1 2 0 1 2 3 4 0
0 0 0 0 1 2 3 4 0 1 2
Dado está na linha 2 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada. Os demais 
são incrementados.
1, 6
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
33
0 1 2 3 0 1 2 0 1 2 3 0
0 0 1 2 3 4 0 1 2 0 1 2
0 0 0 1 2 0 1 2 3 4 0 1
0 0 0 0 1 2 3 4 0 1 2 3
Cache cheia: dado 
precisa ser substituído!
Qual linha está mais 
tempo sem ser 
acessada (maior 
contador)? Linha 0.
Contador é zerado.
1, 6, 1
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
34
0 1 2 3 0 1 2 0 1 2 3 0 1
0 0 1 2 3 4 0 1 2 0 1 2 3
0 0 0 1 2 0 1 2 3 4 0 1 2
0 0 0 0 1 2 3 4 0 1 2 3 0
Dado está na linha 3 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada. Os demais 
são incrementados.
1, 6, 1
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
35
0 1 2 3 0 1 2 0 1 2 3 0 1 2
0 0 1 2 3 4 0 1 2 0 1 2 3 0
0 0 0 1 2 0 1 2 3 4 0 1 2 3
0 0 0 0 1 2 3 4 0 1 2 3 0 1
Dado está na linha 1 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada. Os demais 
são incrementados.
1, 6, 1
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
36
0 1 2 3 0 1 2 0 1 2 3 0 1 2 3
0 0 1 2 3 4 0 1 2 0 1 2 3 0 1
0 0 0 1 2 0 1 2 3 4 0 1 2 3 0
0 0 0 0 1 2 3 4 0 1 2 3 0 1 2
Dado está na linha 2 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada. Os demais 
são incrementados.
1,6, 1
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
37
0 1 2 3 0 1 2 0 1 2 3 0 1 2 3 0
0 0 1 2 3 4 0 1 2 0 1 2 3 0 1 2
0 0 0 1 2 0 1 2 3 4 0 1 2 3 0 1
0 0 0 0 1 2 3 4 0 1 2 3 0 1 2 3
Cache cheia: dado 
precisa ser substituído!
Qual linha está mais 
tempo sem ser 
acessada (maior 
contador)? Linha 0.
Contador é zerado.
1, 6, 1, 9
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
38
0 1 2 3 0 1 2 0 1 2 3 0 1 2 3 0 1
0 0 1 2 3 4 0 1 2 0 1 2 3 0 1 2 3
0 0 0 1 2 0 1 2 3 4 0 1 2 3 0 1 2
0 0 0 0 1 2 3 4 0 1 2 3 0 1 2 3 0
Dado está na linha 3 
da cache. O contador 
desta linha é zerado, 
pois a linha foi 
acessada. Os demais 
são incrementados.
1, 6, 1, 9
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LRU 
Least Recently Used
Substitui o bloco que está mais tempo sem ser acessado. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
39
0 1 2 3 0 1 2 0 1 2 3 0 1 2 3 0 1
0 0 1 2 3 4 0 1 2 0 1 2 3 0 1 2 3
0 0 0 1 2 0 1 2 3 4 0 1 2 3 0 1 2
0 0 0 0 1 2 3 4 0 1 2 3 0 1 2 3 0
1, 6, 1, 9
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
4 substituições na 
memória cache.
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
40
Coloco o primeiro 
dado na cache. O 
contador da linha 0 
é incrementado pois 
foi acessado.
1
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1
0
0
0
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
41
Coloco o segundo 
dado na cache. O 
contador da linha 1 
é incrementado pois 
foi acessado. Todos 
os outros 
permanecem iguais.
1
3
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1
0 1
0 0
0 0
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
42
Coloco o terceiro 
dado na cache. O 
contador da linha 2 
é incrementado pois 
foi acessado. Todos 
os outros 
permanecem iguais.
1
3
4Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1
0 1 1
0 0 1
0 0 0
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
43
Coloco o quarto 
dado na cache. O 
contador da linha 3 
é incrementado pois 
foi acessado. Todos 
os outros 
permanecem iguais.
1
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
44
Cache cheia: dado 
precisa ser 
substituído!
Qual linha está com 
menos acessos 
(menor contador)? 
Linha 0 (FIFO 
quando der empate).
Contador da linha 0 
não incrementa!
1, 6
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
45
Dado está na linha 2 
da cache. O contador 
desta linha é 
incrementado, pois o 
número 4 foi acessado 
duas vezes. Os demais 
contadores 
permanecem iguais.
1, 6
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1
0 1 1 1 1 1
0 0 1 1 1 2
0 0 0 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
46
Dado está na linha 1 
da cache. O contador 
desta linha é 
incrementado, pois o 
número 3 foi acessado 
duas vezes. Os demais 
contadores 
permanecem iguais.
1, 6
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1
0 1 1 1 1 1 2
0 0 1 1 1 2 2
0 0 0 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
47
Dado está na linha 0 
da cache. O contador 
desta linha é 
incrementado, pois o 
número 6 foi acessado 
duas vezes. Os demais 
contadores 
permanecem iguais.
1, 6
3
4
7
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2
0 1 1 1 1 1 2 2
0 0 1 1 1 2 2 2
0 0 0 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
48
Cache cheia e um dado 
precisa ser substituído!
Qual linha está com 
menos acessos (menor 
contador)? Linha 3.
Contador da linha 3 
não incrementa!
1, 6
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2
0 1 1 1 1 1 2 2 2
0 0 1 1 1 2 2 2 2
0 0 0 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
49
Dado está na linha 1 da 
cache. O contador desta 
linha é incrementado, 
pois o número 3 foi 
acessado três vezes. Os 
demais contadores 
permanecem iguais.
1, 6
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2
0 1 1 1 1 1 2 2 2 3
0 0 1 1 1 2 2 2 2 2
0 0 0 1 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
50
Dado está na linha 2 da 
cache. O contador desta 
linha é incrementado, 
pois onúmero 4 foi 
acessado três vezes. Os 
demais contadores 
permanecem iguais.
1, 6
3
4
7, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2 2
0 1 1 1 1 1 2 2 2 3 3
0 0 1 1 1 2 2 2 2 2 3
0 0 0 1 1 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
51
Cache cheia: dado 
precisa ser substituído!
Qual linha está com 
menos acessos (menor 
contador)? Linha 3.
Contador da linha 3 não 
incrementa!
1, 6
3
4
7, 8, 1
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2 2 2
0 1 1 1 1 1 2 2 2 3 3 3
0 0 1 1 1 2 2 2 2 2 3 3
0 0 0 1 1 1 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
52
Cache cheia: dado 
precisa ser substituído!
Qual linha está com 
menos acessos (menor 
contador)? Linha 3.
Contador da linha 3 não 
incrementa!
1, 6
3
4
7, 8, 1, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2 2 2 2
0 1 1 1 1 1 2 2 2 3 3 3 3
0 0 1 1 1 2 2 2 2 2 3 3 3
0 0 0 1 1 1 1 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
53
Dado está na linha 1 da 
cache. O contador desta 
linha é incrementado, 
pois o número 3 foi 
acessado quatro vezes. 
Os demais contadores 
permanecem iguais.
1, 6
3
4
7, 8, 1, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2 2 2 2 2
0 1 1 1 1 1 2 2 2 3 3 3 3 4
0 0 1 1 1 2 2 2 2 2 3 3 3 3
0 0 0 1 1 1 1 1 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
54
Dado está na linha 2 da 
cache. O contador desta 
linha é incrementado, 
pois o número 4 foi 
acessado quatro vezes. 
Os demais contadores 
permanecem iguais.
1, 6
3
4
7, 8, 1, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
0 1 1 1 1 1 2 2 2 3 3 3 3 4 4
0 0 1 1 1 2 2 2 2 2 3 3 3 3 4
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
55
Cache cheia e um dado 
precisa ser substituído!
Qual linha está com 
menos acessos (menor 
contador)? Linha 3.
Contador da linha 3 não 
incrementa!
1, 6
3
4
7, 8, 1, 8, 9
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4
0 0 1 1 1 2 2 2 2 2 3 3 3 3 4 4
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
56
Cache cheia: dado 
precisa ser substituído!
Qual linha está com 
menos acessos (menor 
contador)? Linha 3.
Contador da linha 3 não 
incrementa!
1, 6
3
4
7, 8, 1, 8, 9, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
0 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4 4
0 0 1 1 1 2 2 2 2 2 3 3 3 3 4 4 4
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
ALGORITMO LFU 
Least Frequently Used
Substitui o bloco com menos acessos dentro da cache. 
Exemplo: Considere que uma aplicação acessa os blocos de 
memória na seguinte ordem:
1, 3, 4, 7, 6, 4, 3, 6, 8, 3, 4, 1, 8, 3, 4, 9, 8
57
1, 6
3
4
7, 8, 1, 8, 9, 8
Li
nh
as
Sequência de valores dos contadores Sequência de valores na cache
0
1
2
3
1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
0 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4 4
0 0 1 1 1 2 2 2 2 2 3 3 3 3 4 4 4
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6 substituições na 
memória cache.
ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
COMPARAÇÃO
FIFO (First In First Out)
7 substituições de cache (pior caso)
LRU (Least Recently Used)
4 substituições de cache (melhor caso)
LFU (Least Frequently Used)
6 substituições de cache (caso médio)
58
Profa. Alexandra L. Zimpeck
alexandra.zimpeck@ucpel.edu.br
ARQUITETURA E ORGANIZAÇÃO DE 
COMPUTADORES
Algoritmos de substituição da 
memória cache