Evolução da arquitetura básica - fenix.tecnico.ulisboa.pt

Evolução da arquitetura básica • Processamento em estágios (com pipeline) • Caches • Memória virtual

José Delgado © 2012

Arquitetura de Computadores – Evolução da arquitetura básica

1

A microprogramação é sequencial • A microprogramação divide o processamento de uma instrução em vários estágios: – – – – –

Busca instrução (BI) Descodifica instrução (DI) Busca operandos (BO) Executa instrução (EI) Escreve resultado (ER)

BI DI BO EI ER BI DI BO EI ER BI DI BO EI ER



2

Processamento com pipeline BI DI BO EI ER BI DI BO EI ER BI DI BO EI ER

• Cada estágio é efetuado por um bloco de hardware diferente • Começa-se a tratar da instrução seguinte mal acabe o primeiro estágio da instrução corrente. O tempo que cada instrução demora a executar mantém-se.

BI DI BO EI ER

BI DI BO EI ER BI DI BO EI ER BI DI BO EI ER BI DI BO EI BI DI BO José Delgado © 2012

Mas o processador completa uma instrução por ER cada ciclo de relógio! EI ER


3

Desempenho do pipeline • A latência (tempo de espera até BI DI BO EI ER BI DI BO EI ER que uma dada instrução acabe) BI DI BO EI ER mantém-se. O que melhora é o BI DI BO EI ER ritmo (número de instruções BI DI BO EI ER BI DI BO EI ER executadas por unidade de tempo). • Idealmente, o pipeline melhora o desempenho N vezes, mas: – – – –

Há estágios inativos durante o enchimento/esvaziamento; Nem todas as instruções necessitam dos estágios todos; A frequência do relógio é limitada pelo estágio mais lento; A sequência temporal foi alterada (escala de tempos sobreposta), o que cria problemas de dependências (ler um valor antes de ele ter sido produzido, por exemplo).



4

Unidade de dados com pipeline Busca instrução Descodifica instrução e obtém operandos M U X

Executa instrução

+ +2

PC

EA

Escreve resultado

M U X

DA ALU

Memória de instruções EA – Endereço registo A EB – Endereço registo B DA – Conteúdo registo A DB – Conteúdo registo B DE – Dado a escrever EE – Endereço do registo a escrever


Registos EB DB DE EE

M U X

Endereço Memória de dados


M U X

5

Organização do pipeline M U X

+ +2

PC

EA

M U X

DA ALU

Memória de instruções

Registos EB DE

DB EE

M U X


M U X

• Os registos NÃO são edge-triggered. Permitem escrita na primeira metade do relógio e leitura na segunda (incluindo os dados escritos na primeira metade – read-after-write). • Memórias de instruções e de dados separados, para maior eficiência (na realidade, só as caches estão separadas – a ver mais tarde).



6

MOV – 1º estágio Busca instrução Descodifica instrução e obtém operandos M U X

Executa instrução

+ +2

PC

EA

Escreve resultado

M U X

DA ALU




M U X



M U X

7


Executa instrução

+ +2

PC

EA

Escreve resultado

M U X

DA ALU




M U X



M U X

8


Executa instrução

+ +2

PC

EA

Escreve resultado

M U X

DA ALU




M U X



M U X

9


Executa instrução

+ +2

PC

EA

Escreve resultado

M U X

DA ALU




M U X



M U X

10

MOV, ADD, JMP – Passo 1 MOV Busca instrução Descodifica instrução Executa instrução e obtém operandos M U X

+ +2

PC

EA

Escreve resultado

M U X

DA ALU




M U X



M U X

11

MOV, ADD, JMP – Passo 2 ADD MOV Busca instrução Descodifica instrução e obtém operandos M U X

Executa instrução

+ +1 +2

PC

EA

Escreve resultado

M U X

DA ALU




M U X



M U X

12

MOV, ADD, JMP – Passo 3 JMP ADD Busca instrução Descodifica instrução e obtém operandos M U X

MOV Executa instrução

+ +1 +2

PC

EA

Escreve resultado

M U X

DA ALU




M U X



M U X

13

MOV, ADD, JMP – Passo 4 ... JMP Busca instrução Descodifica instrução e obtém operandos M U X

ADD

MOV

Executa instrução

Escreve resultado

+ +2

PC

EA

M U X

DA ALU




M U X



M U X

14

MOV, ADD, JMP – Passo 5 ...

...

Busca instrução Descodifica instrução e obtém operandos M U X

JMP

ADD

Executa instrução

Escreve resultado

+ +2

PC

EA

M U X

DA ALU




M U X



M U X

15

MOV, ADD, JMP – Passo 6 ... Busca instrução Descodifica instrução e obtém operandos M U X

Executa instrução

+ +2

PC

EA

Escreve resultado

M U X

DA ALU




M U X



M U X

16

Controlo M U X

Controlo

+ +2

PC

EA

M U X

DA ALU




M U X



M U X

17

Conflitos de dados MOV R1, R2 ADD R3, R1 ADD R1, R3

BI DBO EI ER R1  R2 R3  R3 + R1 BI DBO EI ER R1  R1 + R3 BI DBO EI

ER

• As setas indicam as dependências entre instruções: – As caudas indicam onde os registos são escritos – As cabeças indicam onde os registos são lidos

• Setas para trás indicam conflitos de dados • Formas de resolver o problema: – Atrasando as instruções seguintes – Disponibilizando os dados mais cedo (data forwarding)



18

Atraso das instruções em SW MOV R1, R2 ADD R3, R1 ADD R1, R3


ER

• Solução em software (implementada pelo compilador)  inserir instruções “dummy”: MOV R1, R2 NOP ADD R3, R1 NOP ADD R1, R3 José Delgado © 2012

R1  R2 DBO EI ER BI DBO EI ER R3  R3 + R1 BI DBO EI ER BI DBO EI ER R1  R1 + R3 BI DBO EI

BI


ER 19

Atraso das instruções em HW MOV R1, R2 ADD R3, R1 ADD R1, R3


ER

• Solução em hardware (implementada pela unidade de controlo do processador)  inserir “bolhas” (desperdiçar ciclos do estágio do pipeline): MOV R1, R2 ADD R3, R1 ADD R3, R1 ADD R1, R3 ADD R1, R3 José Delgado © 2012

R1  R2 DBO EI ER BI DBO R3  R3 + R1 BI DBO EI ER BI DBO R1  R1 + R3 BI DBO

Bolhas

BI


EI

ER 20

Antecipação dos dados • Não esperar pelo “Escreve resultado” mas usar logo os dados que já estão disponíveis no estágio de execução (saída da ALU). A escrita do resultado nos registos sucede em paralelo. BI DBO EI ER R1  R2 R3  R3 + R1 BI DBO EI ER R1  R1 + R3 BI DBO EI

MOV R1, R2 ADD R3, R1 ADD R1, R3

ER

Conflito Data forwarding



21

Antecipação dos dados (cont.) Busca dos Operandos

RMI

M U X

Banco de registos IND_A IND_B

ROP

M U X

Execução da Microinstrução

M U X

BARR_C IND_C ENTR_RE

Gerador de constantes

M U X

ALU M U X

M U X Bits de estado

IND_C_EM

IND_C_BO

NUM_EXC_E


RSA

Escrita do Resultado

R E M

Cache de dados

IND_C_ER

Detetor de conflitos de dados


MUX

22

Exercícios de pipelines 1.

2.

Um processador com um pipeline com 5 estágios é 5 vezes mais rápido (para a mesma frequência de relógio) do que um processador sem pipeline. Concorda com esta afirmação? Porquê? Considere o código seguinte e assuma que é para ser executado num processador com um pipeline de 4 estágios (o usado nestes slides) ADD R2, R4 ADD R5, R2 MOV R3, [R5+6] ADD R3, R5 a) Identifique todas as dependências de dados que terão problemas neste pipeline. b) Indique que dependências poderão ser resolvidas com antecipação dos dados (data forwarding)



23

Hierarquia de memória Processador registos menor tempo de acesso

Cache 32 KB Cache nível 2 (RAM estática) 4 MB Memória central (RAM dinâmica) 2 GB Disco 300 GB



maior capacidade, menor custo

• Os computadores possuem uma hierarquia de memória com vários níveis. • As caches têm cópias das células de memória mais usadas e são de funcionamento automático. • A memória central (ou principal) pode servir de cache do disco (memória virtual) • O disco pode servir de cache à informação em servidores. • Os “mirrors” são servidores que atuam como caches de outros.

24

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



25

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.



26

Acesso às caches • 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); – 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.

• 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%.



27

Desempenho das caches • Quanto maior a cache face à memória principal, maior a hit rate. • Tem um impacte grande no desempenho, mas também no custo (há processadores mais baratos, só por terem menos cache – na realidade, são chips iguais aos outros em que parte da cache não funciona…) • 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ó tivéssemos a memória principal



28

Caches de mapeamento direto 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)


...

... 0000 0111 0000 0110 0000 0101 0000 0100 0000 0011 0000 0010 0000 0001 0000 0000


29

Como saber se é um cache hit? • Exemplo com um endereço (de byte) de 32 bits, um bus de dados de 32 bits e uma cache de mapeamento direto de 1K palavras: Endereço (32 bits)

10

2 byte

dados 32 bits

=?



processador

20

validade etiqueta 1 bit 20 bits 0 1 2 3 ... ... 1021 1022 1023

Cache hit

30

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) 20

2

10

byte

validade etiqueta 1 bit 20 bits 0 1 2 3 ... ... 1021 1022 1023

dados 32 bits

1

Memória principal José Delgado © 2012


31

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 mas várias palavras, de endereços consecutivos (bloco). • Assim, enquanto o processador aceder aos endereços das palavras no bloco não será necessário efetuar carregamentos na cache (porque dá cache hit). • O bloco passa a ser a unidade de leitura e escrita da memória principal.



32

Cache com blocos de 4 palavras Endereço (32 bits) Validade (1 bit)

Etiqueta (20 bits)

20

8

2

2

Byte na palavra

Dados (4 x 32 bits) 0 1 2 ... ... ... 253 254 255

Multiplexer

=? Cache hit José Delgado © 2012

processador


33

Exemplo (endereços de byte) Endereço (32 bits)

• Onde é armazenada a palavra com endereço (de byte) 03088H? • Endereço em binário:

Validade (1 bit)

0...00 0011 0000 1000 1000

Etiqueta (20 bits)

20

2

2

byte

Dados (4 x 32 bits) 0 1 2 ... 8 ... 253 254 255 Multiplexer

=?

etiqueta

8

índice palavra byte

Cache hit

processador

• Quais os endereços (de byte) das palavras no mesmo bloco (que partilham a mesma etiqueta)? 3080H 3084H 3088H 308CH

0…00 0011 0000 1000 0000 0…00 0011 0000 1000 0100 0…00 0011 0000 1000 1000 0…00 0011 0000 1000 1100 20


8

2 2


34

Mapeamento associativo • O mapeamento direto 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), exceto 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)



35

Implementação da associatividade 2 Endereço (32 bits)

28

2 byte

=? =?

Cache hit

=? =? • Uma cache associativa precisa de muito hardware! José Delgado © 2012


36

Mapeamento associativo por conjuntos de K vias • Uma solução intermédia é usar K caches de mapeamento direto e fazer a procura em todas elas em paralelo (mapeamento associativo de K vias). • Uma linha das várias caches de mapeamento direto é um conjunto (uma cache associativa). conjunto conjunto conjunto

Via 0 =?

etiqueta

Via 1 =?

índice

palavra dentro do bloco

byte José Delgado © 2012

hit Arquitetura de Computadores – Evolução da arquitetura básica

37

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 é direto. 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 direto 8 vias, 1 conjunto com 8 blocos 0



38

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 direto: 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



39

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 atualiza 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



40

Exercícios de caches 1.

Considere uma cache de mapeamento direto 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 total de bits número de bits de da dos



41

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?



42

Exercícios (endereços de palavra) Endereço memória 1 4

Caso A - Cache de mapeamento direto 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

%



43

Exercícios (endereços de palavra) 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

%



44

Exercícios (endereços de palavra) 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

%



45

Exercícios (endereços de palavra) 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

%



46

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 “veem”) para físicos é transparente e automático. • Também atua como mecanismo de proteção (porque um processo não tem acesso ao espaço de endereçamento dos outros).



47

Espaço de endereçamento virtual • O espaço de endereçamento virtual existe parte em memória física e parte em disco. Endereços virtuais

Tradução de Endereços

Endereços físicos

Endereços no disco



48

Memória virtual paginada • Para otimizar, 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. • Os espaços de endereçamento virtual e físico podem ter dimensões diferentes. 31

12 11 Nº página virtual

0

Deslocamento

Tradução virtual  físico 31

12 11

Nº página física José Delgado © 2012

0

Deslocamento


49

Tabela de páginas 31


0

Deslocamento

Tabela de páginas Registo com endereço base da tabela

“1” se a página estiver carregada em memória 31

12 11 Nº página física


0

Deslocamento


50

Tamanho da tabela de páginas • Se o espaço virtual for de 31 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 31 • Se o espaço virtual for de 48 bits, gasta 64 K vezes mais, ou 256 Gbytes!!! • Assim, a tabela de páginas:


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 © 2012


51

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

Diretório

1K entradas (4 Kbytes)

registo

...

...

... • As próprias tabelas de páginas estão na memória virtual (sujeitas a swapping), exceto o diretório.


...


52

Tradução de endereços 10 bits

10 bits

12 bits

páginas físicas

deslocamento


4 Kbytes

registo

• A tradução do número de página virtual para físico implica aceder às tabelas.

Diretó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 © 2012


53

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 © 2012

Deslocamento

Deslocamento


54

Falta de página (page fault) 10 bits

10 bits

12 bits

páginas físicas

deslocamento


4 Kbytes

• Page fault – acesso a uma página que não está carregada em memória.

registo

Diretório

Tabelas de páginas 1K entradas (4 Kbytes)

...

...

...

• A ocorrência de uma page fault gera uma exceção. O sistema operativo é responsá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 © 2012


55

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 Diretó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 12

4

Palavra dentro do bloco + byte

Cache 16

=?

=? Palavra acedida

Palavra acedida

Palavra pretendida hit José Delgado © 2012


56

• O que pode falhar no acesso:

Válido Alterada

Tipos de misses Número de página virtual

Deslocamento

20

Etiqueta

12 Nº página física ...

– Cache miss (um acesso à memória) – TLB miss (vários acessos à memória) – Page fault (acesso ao disco)

...

Page fault

...

...

20 Número de página física Etiqueta física

Deslocamento Índice 12

4 Palavra dentro do bloco + byte

16

• As cache e TLB =? =? Palavra acedida Palavra acedida misses medem-se em dezenas de hit ciclos de relógio. • As page faults medem-se em dezenas de milissegundos (podem implicar vários acessos ao disco). • Felizmente, estas situações são a exceção e não a regra! José Delgado © 2012


57

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 © 2012


58

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á atualmente 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 respetivo 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 © 2012


59

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.



60

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 © 2012


61

Evolução da arquitetura básica - fenix.tecnico.ulisboa.pt

Recommend Documents