Evolução da arquitectura
básica
• Hierarquia de memória
• Caches
• Memória virtual
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
1
Tipos de memória
• A memória é fundamental nos computadores.
Infelizmente, o custo, capacidade e tempos de acesso
são factores incompatíveis (valores típicos):
Tipo
Tempo de
acesso
Capacidade
Custo/MB
Registo
0.5 ns
512 bytes
---
RAM estática
5 ns
128-512 KB
80 €
RAM
dinâmica
50 ns
128-512 MB
0.3 €
Disco
magnético
10
milisegundos
20-80 GB
0.005 €
Fita magnética
segundos
20-40 GB
0…
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
2
Hierarquia de memória
• Os computadores possuem uma
hierarquia de memória com vários níveis.
• O disco pode servir de cache à
informação em servidores.
• Os “mirrors” são servidores que actuam
como caches de outros.
Cache 32 KB
menor tempo de acesso
• A memória central (ou principal) pode
servir de cache do disco (memória
virtual)
registos
Cache nível 2
(RAM estática)
4 MB
Memória central
(RAM dinâmica)
2 GB
Disco
300 GB
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
maior capacidade, menor custo
• As caches têm cópias das células de
memória mais usadas e são de
funcionamento automático.
Processador
3
PEPE com caches
• As caches são pequenas memórias internas (mais rápidas
que a memória externa) que contêm os dados e instruções
mais usados (dão ao núcleo do processador a ilusão de
memórias separadas).
instruções
endereços
de instruções
Núcleo do
processador
dados
dados
endereços
de dados
Cache de
instruções
endereços
Interface
de
memória
Cache de
dados
dados/instruções
Memória
principal
(dados e
instruções)
WR
RD
Processador
José Delgado, Rui
Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
4
Princípios de funcionamento
das caches
• Felizmente, os programas acedem à memória com:
– Localidade temporal. Se um endereço for acedido agora, há uma
grande probabilidade de ser acedido no futuro próximo (ciclos,
rotinas de invocação frequente, dados importantes);
– Localidade espacial. Se um endereço for acedido, a
probabilidade de os próximos acessos serem em endereços
próximos é grande (execução sequencial, ciclos, arrays cujos
dados são acedidos sequencialmente).
• Assim, a cache só tem as células de memória mais
frequentemente acedidas.
• Pode ser mais pequena que a memória completa, logo
muito mais rápida sem o custo ser muito elevado.
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
5
Acesso às caches
Terminologia
• Quando se acede a um determinado endereço:
– Se a célula com esse endereço estiver na cache, o acesso é
muito rápido (cache hit); hit time é o tempo necessário para tal.
– Se não estiver, dá-se um cache miss. Tem de se ir à memória
principal, carregar essa célula na cache e repetir o acesso.
Neste caso, o tempo necessário para trazer essa célula para a
cache e disponibilizá-la ao processador é o miss penalty.
• O desempenho das caches é normalmente medido pelo
hit rate (percentagem média dos acessos com cache
hit, tipicamente superiores a 95%)
• Também se pode falar na miss rate (percentagem
média dos acessos com cache miss = 1 – hit rate),
tipicamente inferior a 5%.
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
6
Desempenho das caches
• Quanto maior a cache face à memória principal, maior
o hit rate.
• Tem um impacto grande no desempenho, mas também
no custo (os Celerons, mais baratos, são Pentiums com
metade da cache)
• Supondo:
– Tempo de acesso da cache: 5 ns
– Tempo de acesso da memória principal: 50 ns
– Hit rate média: 95%
• Então, o tempo de acesso médio será:
0.95 * 5 ns + 0.05 * 55 ns = 7. 5 ns
• Ou seja, 50 ns/7.5 ns = 6.7 vezes mais rápido do que
se só tivessemos a memória principal
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
7
Questões básicas das caches
1. Como saber se a célula com um dado endereço está
na cache? (é ou não um cache hit?)
2. Quando não está (cache miss) e é preciso ir buscá-la
à memória principal, em que sítio da cache se
coloca?
3. Quando a cache encher (o seu tamanho é limitado),
a única forma de ir buscar uma nova célula é
substituir uma das que estão na cache. Qual?
4. O que fazer para actualizar a memória principal
quando o processador faz um acesso em escrita na
cache?
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
8
Caches de mapeamento directo
6 bits
etiqueta
endereço
válido etiqueta
11
10
01
00
•
•
1
0
0
0
1
0
1
2 bits
índice
memória
1111 0111
1111 0110
1111 0101
1111 0100
1111 0011
1111 0010
1111 0001
1111 0000
dados
000001
000001
111101
111100
cache
Cada célula da cache só pode ter
uma das células de memória que
tenham o mesmo índice
A etiqueta identifica o resto do
endereço (distinguindo entre
células com o mesmo índice)
José Delgado, Rui Rocha © 2010
...
...
0000 0111
0000 0110
0000 0101
0000 0100
0000 0011
0000 0010
0000 0001
0000 0000
Arquitectura de Computadores – Evolução da arquitectura básica
9
Caches de mapeamento directo
6 bits
etiqueta
endereço
válido etiqueta
11
10
01
00
1
0
0
0
1
0
1
2 bits
índice
memória
1111 0111
1111 0110
1111 0101
1111 0100
1111 0011
1111 0010
1111 0001
1111 0000
dados
000001
000001
111101
111100
...
cache
Blockcache = Blockadd mod (nº blocos na chache)
Exemplo:
nº blocos na cache=4 ; Blockadd= 18 [010010]
Blockcache = 18 mod. 4 = 2 [10]
...
0000 0111
0000 0110
0000 0101
0000 0100
0000 0011
0000 0010
0000 0001
0000 0000
Cada posição da cache alberga: Dimmem /Dimcache posições da mem.
primária
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
10
Como saber se é um cache hit?
• Exemplo com um endereço de 32 bits, um bus de dados de 32
bits e uma cache de mapeamento directo de 1K palavras:
Endereço (32 bits)
Byte
10
etiqueta
20 bits
dados
32 bits
processador
20
validade
1 bit
0
1
2
3
...
...
1021
1022
1023
=?
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
Cache hit
11
E se for um cache miss?
• O controlador da cache carrega automaticamente a palavra em
falta (o processador pode ter de esperar). Em seguida repete o
acesso (que já dá cache hit).
Endereço (32 bits)
Byte
20
10
validade etiqueta
1 bit
20 bits
0
1
2
3
...
...
1021
1022
1023
dados
32 bits
1
Memória principal
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
12
Localidade espacial
• Ter na cache as palavras recentemente acedidas
explora a localidade temporal, mas não a espacial.
• A localidade espacial pode ser aproveitada lendo para
a cache não uma palavra mas várias de endereços
consecutivos (bloco).
• Assim, enquanto o processador aceder aos endereços
das palavras no bloco não será necessário efectuar
carregamentos na cache (porque dá cache hit).
• O bloco passa a ser a unidade de leitura e escrita da
memória.
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
13
Cache com blocos de 4 palavras
Endereço (32 bits)
Validade (1 bit)
Etiqueta (22 bits)
22
8
2
Dados (4 x 32 bits)
0
1
2
3
...
...
253
254
255
Multiplexer
=?
Cache hit
José Delgado, Rui Rocha © 2010
processador
Arquitectura de Computadores – Evolução da arquitectura básica
14
Exemplo
Endereço (32 bits)
• Onde é armazenada a
palavra com endereço
3C02H?
• Endereço em binário:
0011 1100 0000 0010
Validade (1 bit)
Etiqueta (22 bits)
22
índice
2
Dados (4 x 32 bits)
0
1
2
3
...
...
253
254
255
Multiplexer
=?
etiqueta
8
palavra
Cache hit
processador
• Quais os endereços no mesmo bloco (que
partilham a mesma etiqueta)?
3C00H
3C02H
3C04H
3C06H
José Delgado, Rui Rocha © 2010
0011 1100 0000 0000
0011 1100 0000 0010
0011 1100 0000 0100
0011 1100 0000 0110
Arquitectura de Computadores – Evolução da arquitectura básica
15
Desempenho em função da dimensão do
bloco
Endereço (32 bits)
Validade (1 bit) Etiqueta (22 bits)
22
•
Aumentando a dimensão do bloco (linha)
da cache tira-se partido da localidade
espacial. Um miss acarreta maior
penalização.
8
2
Dados (4 x 32 bits)
0
1
2
3
...
...
253
254
255
Multiplexer
=?
Cache hit
processador
COPYRIGHT 1998 MORGAN KAUFMANN PUBLISHERS, INC. ALL RIGHTS RESERVED
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
16
Mapeamento associativo
• O mapeamento directo tem o problema de dois blocos
com o mesmo índice não poderem coexistir na cache,
mesmo que:
– os dois blocos estejam a ser muito usados
– o resto da cache esteja vazia!!!
• No mapeamento associativo qualquer bloco pode
ocupar qualquer posição na cache, mas :
– A etiqueta tem de ser o endereço todo (para distinguir
quaisquer blocos), excepto os bits de endereço da palavra
dentro do bloco
– A procura do bloco (para ver se é cache hit) já não é por
índice. Tem de se comparar o endereço com a etiqueta em
todos os blocos ao mesmo tempo (para ser rápido)
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
17
Implementação da associatividade
2
Endereço
(32 bits)
30
=?
=?
Cache hit
=?
=?
• Uma cache associativa precisa de muito hardware!
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
18
Mapeamento associativo por
conjuntos de K vias
• Uma solução intermédia é usar K caches de mapeamento directo
e fazer a procura em todas elas em paralelo (mapeamento
associativo de K vias).
• Uma linha das várias caches de mapeamento directo é um
conjunto (uma cache associativa).
conjunto
conjunto
conjunto
Via 0
=?
etiqueta
Via 1
=?
índice
palavra dentro
do bloco
José Delgado, Rui Rocha © 2010
hit
Arquitectura de Computadores – Evolução da arquitectura básica
19
Variabilidade entre extremos
• Uma cache com N blocos pode ter K vias (K [0, N-1]),
cada uma com N/K conjuntos de K blocos.
• Dentro de cada via o mapeamento é directo.
1 via,
8 conjuntos com
1 bloco cada
2 vias,
4 conjuntos com
2 blocos cada
0
1
2
3
0
1
2
3
4
5
6
7
4 vias,
2 conjuntos com
4 blocos cada
0
1
Mapeamento associativo
Mapeamento directo
8 vias, 1 conjunto com 8 blocos
0
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
20
Desempenho de vários tipos de Cache
Consideremos a sequência de acessos a blocos de
cache:0, 8, 0, 6, 8.
Qual o comportamento das várias estruturas?
Associativo (2 vias):
Directo:
bloco cache (0) = (0 mod 4)=0 bloco cache (0) = (0 mod 2)=0
bloco cache (6) = 0
bloco cache (8) = 0
bloco cache (8) = 0
Assoc. (full)
Assoc. (2 vias)
Directo
bloco cache (6) = 2
End. bloco mem.
0
8
0
6
8
acesso
miss
miss
miss
miss
miss
bloco c(0)
Mem[0]
Mem[8]
Mem[0]
Mem[0]
Mem [8]
End. bloco mem.
0
8
0
6
8
acesso
miss
miss
hit
miss
Miss
set(0)
Mem[0]
Mem[0]
Mem[0]
Mem[0]
Mem [8]
End. bloco mem.
0
8
0
6
8
acesso
miss
miss
hit
miss
hit
B0
Mem[0]
Mem[0]
Mem[0]
Mem[0]
Mem[0]
bloco c(2)
Mem[6]
Mem[6]
set(0)
Mem[8]
Mem[8]
Mem[6]
Mem[6]
B1
Mem[8]
Mem[8]
Mem[8]
Mem[8]
José Delgado, Rui Rocha © 2010
B2
B3
COPYRIGHT 1998 MORGAN KAUFMANN PUBLISHERS, INC. ALL RIGHTS RESERVED
Mem[6]
Mem[6]
Arquitectura de Computadores – Evolução da arquitectura básica
21
Política de substituição
• Onde colocar uma célula de memória que se foi buscar
à memória principal devido a um cache miss?
– Caches de mapeamento directo: na célula indicada pelo índice
– Caches de mapeamento completamente associativo:
• Com lugares vagos: num lugar vago qualquer
• Cheia: no lugar da célula usada menos recentemente (LRU –
Least Recently Used)
• Na prática, costuma usar-se um contador para ir escrevendo na
célula seguinte, independentemente de estar cheia ou vazia, de
ter sido muito usada ou não. É um método simples e não muito
pior que os anteriores
– Caches associativas com K vias: obtém-se o conjunto através
do índice e escolhe-se uma via
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
22
Política de escrita
• Quando a célula está na cache (write hit):
– Write-through: escreve-se na cache e na memória principal
– Write-back: escreve-se só na cache e só se actualiza a
memória principal quando o bloco tem de sair da cache
• Quando a célula NÃO está na cache (write miss):
– Write around: escreve na memória principal sem escrever na
cache (bom se a célula não for lida a curto prazo)
– Write allocate: faz um cache miss (carrega a célula) e faz write
through
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
23
Exercícios de caches
1.
Considere uma cache de mapeamento directo com capacidade para 8
Kbytes de dados e blocos de 8 palavras de 32 bits, a usar por um
processador de 32 bits, com endereçamento de byte e 32 bits de
endereço.
a) Quantos bits deve ter a etiqueta de cada bloco?
b) Quantos blocos é que a cache consegue armazenar
simultaneamente?
c) Indique em que bloco (numerado entre 0 e o número obtido na alínea
anterior menos um) ficará armazenada a palavra com o endereço
1000H. Dê a sua resposta em hexadecimal.
d) Indique os endereços das palavras que ficam no mesmo bloco que a
palavra com o endereço 1000H.
e) Dê o endereço (à sua escolha) de duas palavras que nunca poderão
estar ao mesmo tempo na cache e explique porquê.
f) Supondo que, para além dos dados, a cache tem de guardar as
etiquetas e os bits de validade, indique o número total de bits que a
cache tem de poder armazenar.
g) Indique qual o overhead da cache em termos de capacidade, isto é, o
rácio
número tot al de bits
número de bits de da dos
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
24
Exercícios de caches (cont.)
2.
Pretende-se escolher um sistema de cache para um determinado
processador. Assume-se 8 blocos, cada um com 1 palavra do
processador, mas qual o melhor tipo de cache? Para melhor se aferir o
comportamento dos vários tipos de cache dispõe-se de um simulador em
que se regista os acessos à referida cache. No simulador executa-se um
benchmark (programa de teste) que acede aos seguintes endereços (em
decimal): 1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17. Admita que a
cache está inicialmente vazia e que o algoritmo de substituição de blocos
é LRU (quando se aplicar).
a) Preenchendo as tabelas seguintes (são dadas as duas primeiras
linhas para servir de exemplo), represente para os tipos de cache
nelas indicados:
i.
ii.
iii.
b)
os sucessivos conteúdos da cache (usando a notação M[endereço] para
representar o conteúdo de uma dada posição de memória)
o tipo de acesso (hit ou miss)
a miss rate
Em que medida é que o aumento da dimensão da cache (mais blocos
ou mais vias, conforme o caso) para o dobro melhoraria a miss rate de
cada um dos sistemas referidos, no caso deste benchmark?
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
25
Exercícios
Endereço
memória
1
4
Caso A - Cache de mapeamento directo com 8 blocos de 1 palavra cada
Nº de bloco
hit ou
miss
0
1
2
3
4
5
6
miss
M[1]
miss
M[1]
M[4]
7
8
5
20
17
19
56
9
11
4
43
5
6
9
17
Miss rate
%
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
26
Exercícios
Caso B - Cache associativa de 2 vias com um total de 8 blocos de 1 palavra cada
Nº de bloco via 0
Nº de bloco via 1
Endereço hit ou
memória
miss
0
1
2
3
0
1
2
1
miss
M[1]
4
miss
M[4]
M[1]
3
8
5
20
17
19
56
9
11
4
43
5
6
9
17
Miss rate
%
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
27
Exercícios
Caso C - Cache associativa de 4 vias com um total de 8 blocos de 1 palavra cada
Nº de bloco via 0 Nº de bloco via 1 Nº de bloco via 2 Nº de bloco via 3
Endereço hit ou
memória
miss
0
1
0
1
0
1
0
1
1
miss
M[1]
4
miss
M[4]
M[1]
8
5
20
17
19
56
9
11
4
43
5
6
9
17
Miss rate
%
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
28
Exercícios
Caso D - Cache totalmente associativa com um total de 8 blocos de 1 palavra cada
Nº de bloco
Endereço hit ou
memória
miss
0
1
2
3
4
5
6
1
miss
M[1]
4
miss
M[1]
M[4]
7
8
5
20
17
19
56
9
11
4
43
5
6
9
17
Miss rate
%
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
29
Memória virtual
• Mecanismo que permite tratar a memória principal como cache de
uma memória virtual (não existe na realidade) igual ao somatório
dos espaços de endereçamento dos vários processos.
• As zonas de memória virtual não carregadas em memória principal
e com dados/código dos processos estão em disco (swap file)
• O mecanismo de tradução de endereços virtuais (os que os
processos “vêem”) para físicos é transparente e automático.
• Também actua como mecanismo de protecção (porque um
processo não tem acesso ao espaço de endereçamento dos
outros).
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
30
Espaço de endereçamento
virtual
• O espaço de endereçamento virtual existe parte em memória
física, parte em disco.
Endereços virtuais
Tradução de
Endereços
Endereços físicos
Endereços no disco
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
31
Memória virtual paginada
• Para optimizar, o espaço de endereçamento é dividido em
páginas, todas de igual dimensão (4 Kbytes, por exemplo).
• Assim, apenas é necessário traduzir o endereço de base da
página, de virtual para físico.
31
12 11
Nº página virtual
0
Deslocamento
Tradução virtual  físico
15
12 11
Nº página física
José Delgado, Rui Rocha © 2010
0
Deslocamento
Arquitectura de Computadores – Evolução da arquitectura básica
32
Tabela de páginas
32
12 11
Nº página virtual
0
Deslocamento
Tabela de páginas
Registo com
endereço base
da tabela
“1” se a página
estiver carregada em
memória
32
12 11
Nº página física
José Delgado, Rui Rocha © 2010
0
Deslocamento
Arquitectura de Computadores – Evolução da arquitectura básica
33
Tamanho da tabela de páginas
• Se o espaço virtual for de
32
32 bits (4 Gbytes) e a
página for de 4 Kbytes,
Registo com
então a tabela de páginas endereço
base
da tabela
tem 1 M entradas de 32
bits. Ou seja, gasta 4
“1” se a página
Mbytes!
estiver carregada em
memória
32
• Se o espaço virtual for de
48 bits, gasta 64 K vezes
mais, ou 256 Gbytes!!!
• Assim, a tabela de páginas:
12 11
Nº página virtual
0
Deslocamento
Tabela de páginas
12 11
Nº página física
0
Deslocamento
– é feita em vários níveis hierárquicos
– só tem as entradas necessárias
– está, ela própria, sujeita ao mecanismo de memória virtual
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
34
Tabela de páginas hierárquica
10 bits
10 bits
Nº de página virtual
12 bits
páginas físicas
deslocamento
4 Kbytes
Tabelas de páginas
Directório
1K
entradas
(4 Kbytes)
registo
...
...
...
• As próprias tabelas de
páginas estão na memória
virtual (sujeitas a
swapping), excepto o
directório.
José Delgado, Rui Rocha © 2010
...
Arquitectura de Computadores – Evolução da arquitectura básica
35
Tradução de endereços
10 bits
• A tradução do
número de página
virtual para físico
implica aceder às
tabelas.
10 bits
12 bits
páginas físicas
deslocamento
Nº de página virtual
4 Kbytes
registo
Directório
Tabelas de páginas
1K
entradas
(4 Kbytes)
...
...
...
...
• É incomportável percorrer as várias
tabelas em cada acesso à memória!!!
• Solução: cache que tenha a tradução de
endereços das páginas mais usadas.
• Se houver um cache hit, a cache diz logo qual o endereço
físico da página.
• Se houver um cache miss, então é preciso percorrer as várias
tabelas.
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
36
TLB
• TLB = Translation Lookaside Buffer (cache de
tradução de endereços virtuais para físicos).
Válido
Alterada
Número de página virtual
Etiqueta
Dados
Número de página física
José Delgado, Rui Rocha © 2010
Deslocamento
Deslocamento
Arquitectura de Computadores – Evolução da arquitectura básica
37
Falta de página (page fault)
10 bits
• Page fault –
acesso a uma
página que não
está carregada
em memória.
10 bits
12 bits
páginas físicas
deslocamento
Nº de página virtual
4 Kbytes
registo
Directório
Tabelas de páginas
1K
entradas
(4 Kbytes)
...
...
...
• A ocorrência de uma page fault gera
uma excepção. O sistema operativo é
reponsável por percorrer as tabelas de
páginas e carregar a página em falta.
• Esta operação é lenta. É preciso:
...
– Percorrer as várias tabelas (vários acessos à memória)
– Carregar as tabelas de páginas que não estiverem em memória
– Carregar a página que originou a page fault
• Felizmente, os programas têm localidade espacial e temporal
e esta operação não acontece em todos os acessos!
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
38
Memória virtual + caches
Endereço virtual
(32 bits)
Válido
Alterada
Número de página virtual
Deslocamento
20
12
Etiqueta
Nº página física
registo
10 bits
10 bits
12 bits
deslocamento
Nº de página virtual
Tabelas de páginas
1K
Directório
entradas
(4 Kbytes)
páginas físicas
4 Kbytes
...
...
TLB
TLB fault
...
...
20
Número de página física
Etiqueta física
Endereço físico
(32 bits)
Deslocamento
Índice
14
2
Palavra dentro do bloco
Cache
16
=?
=?
Palavra acedida
Palavra acedida
Palavra pretendida
hit
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
39
• O que pode falhar no
acesso:
– Cache miss (um
acesso à memória)
– TLB miss (vários
acessos à
memória)
– Page fault (acesso
ao disco)
• As cache e TLB
misses medem-se
em dezenas de
ciclos de relógio.
Válido
Alterada
Tipos de misses
Número de página virtual
Deslocamento
20
12
Etiqueta
Nº página física
...
...
Page fault
...
...
20
Número de página física
Etiqueta física
Deslocamento
Índice
14
2
Palavra dentro do bloco
16
=?
=?
Palavra acedida
Palavra acedida
hit
• As page faults medem-se em dezenas de milisegundos (pode
implicar vários acessos ao disco).
• Felizmente, estas situações são a excepção e não a regra!
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
40
Exercícios de memória virtual
1.
Um sistema de memória virtual tem um tamanho de página de 1000
palavras, 8 páginas virtuais e 4 páginas físicas. Assuma que inicialmente a
tabela de páginas está vazia (nenhuma página carregada em memória).
a) Preencha a tabela seguinte com o estado que terá após acesso aos
endereços (de palavra) virtuais 7000, 2000, 5000, 1000.
Página virtual
0
1
2
3
4
5
6
7
b)
c)
Página física
Após estes acessos, quais os endereços físicos dos endereços
virtuais 0, 3728, 999, 1025, 7800 e 4096 (endereços de palavra)?
Dê um exemplo de um endereço virtual que provoque agora uma
page fault
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
41
Exercícios de memória virtual
2.
O TLB de um sistema de memória virtual, com 20 bits de número de
página virtual, 12 bits de número de página física e 12 bits de
deslocamento dentro de cada página, está actualmente com o conteúdo
indicado pela tabela seguinte.
Válida
1
0
0
1
1
1
a)
b)
c)
d)
Alterada
1
0
0
0
0
1
Nº pág. virtual
01AF4H
0E45FH
012FFH
01A37H
02BB4H
03CA0H
Nº pág. física
FFFH
E03H
2F0H
788H
45CH
657H
Qual a dimensão de cada página?
Qual a dimensão dos espaços de endereçamento virtual e físico?
Indique, para cada um dos endereços virtuais seguintes, o respectivo
endereço físico (ou se originam page fault): 2BB4A65H, E45FB32H,
D34E9DCH, 3CA0777H e 1AF4E06H.
Para cada um destes endereços, indique quais não foram,
garantidamente, escritos desde que foram carregados em memória.
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
42
Exercícios de memória virtual
3. Um processador tem:
i.
ii.
iii.
iv.
v.
vi.
a)
b)
um TLB completamente associativo de 2 palavras, com algoritmo de
substituição FIFO (rotativo)
uma cache de mapeamento associativo de 2 vias, com um total com 8
blocos de 1 palavra cada.
uma tabela linear (um só nível) de 8 páginas virtuais, com algoritmo
de substituição LRU
uma memória física de 4 páginas
uma página com 256 palavras de dimensão
endereçamento exclusivamente em palavras (bytes não)
Qual a dimensão, em palavras, dos espaços de
endereçamento virtual e físico?
Assumindo que inicialmente a memória não tem nenhum
programa ou dados carregados, preencha a tabela seguinte,
indicando o que acontece em cada acesso aos endereços
virtuais indicados e qual o estado em que o sistema fica. Use a
notação M[endereço] para indicar o conteúdo da cache. No
TLB indique o nº de página virtual e física. As duas primeiras
colunas estão preenchidas para servir de exemplo.
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
43
Exercícios de memória virtual
Endereço virtual 505
0
5 0
TLB
1
TLB miss/hit
miss
7A0
5 0
7 1
322
5F5
322
505
4C0
435
100
723
miss
0
1
2
3
Tabela
páginas
4
5
0
0
6
7
1
Page fault/hit
miss
miss
Endereço físico
005
1A0
0
M[1A0]
1 M[005] M[005]
2
3
Cache
0
1
2
3
Cache miss/hit
miss
miss
José Delgado, Rui Rocha © 2010
Arquitectura de Computadores – Evolução da arquitectura básica
44