12 - Memória Principal e Secundária parte 5

Prévia do material em texto

Professores:
Ivanildo Melo e Rosangela Melo 
ivanildo.melo@paulista.ifpe.edu.br
rosangela.melo@paulista.ifpe.edu.br
Arquitetura de Computadores
Aula 11 – Memória Principal e Secundária: Características, 
Organização, Arquitetura, Hierarquia e Memória Cache. 
[Quinta Parte]
Sobre este Material
2
O material dessa aula segue o conteúdo literal e em alguns pontos adaptado das seguintes fontes:
• MONTEIRO, Mario A. Introdução a Organização de Computadores. 5ª ed. Rio de Janeiro: LTC, 2007.
• BARBOSA, Luiz Sérgio de O. Arquitetura e Organização de Computadores. (Apostila) PROINOVALAB- Amazonas.
Universidade do Estado do Amazonas (UEA)
• TANENBAUM, Andrew S. Organização Estruturada de Computadores. 5ª ed. São Paulo: Pearson Prentice Hall,
2010.
• STALLINGS, William. Arquitetura e Organização de Computadores. 8ª ed. São Paulo: Pearson Prentice Hall, 2010.
• Tiago Bandeira Marchesan – Memória – Disponível em:<http://coral.ufsm.br/tiago/introcomp/Aula%203%20-
%20Memoria.pdf>.
• TI Network. Organização de computadores - Aula 9 – Memória – Disponível em: <https://youtu.be/D39L13a7yPg>. 
• OLIVEIRA, Helder - Mapeamento Associativo e Associativo por Conjunto - Memória Cache
Memória Cache - Cont.
3
Nos Mapeamentos
Associativos e Associativo
por Conjunto quando a
memória cache encontra-se
completamente ocupada ou
cheia, é preciso definir
critérios para definir qual o
bloco da memória cache
será substituído,
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
0
1
2
3
Memória Cache - Cont.
4
1. Não aplicado ao mapeamento direto
devido ao mapeamento ser fixo alocar
o bloco na MP em uma posição fixa na
memória cache por meio do uso da
função de mapeamento.
2. Cada bloco é mapeado previamente
e caso necessite se carregado na
memória cache ele ocupará uma
posição pré-determinada.
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
Memória Cache - Cont.
5
• FIFO – First In First Out
• LFU – Last Frequently Used
• LRU – Least Recently Used
• Substituição Aleatória
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
Memória Cache - Cont.
6
• FIFO – First In First Out
• LFU – Least Frequently Used
• LRU – Least Recently Used
• Substituição Aleatória
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
Memória Cache - Cont.
7
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
FIFO – First In First Out
1. Utiliza o conceito de fila.
2. O primeiro bloco carregado é o primeiro a sair no
critério de substituição.
0
1
2
3
Memória Cache - Cont.
8
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
FIFO – First In First Out
1. Utiliza o conceito de fila.
2. O primeiro bloco carregado é o primeiro a sair no
critério de substituição.
3. Para o exemplo o Bloco “0” seria o candidato a
ser substituído, uma vez que ele foi o primeiro a
ser carregado.
0
1
2
3
Memória Cache - Cont.
9
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
FIFO – First In First Out
1. Utiliza o conceito de fila.
2. O primeiro bloco carregado é o primeiro a sair no
critério de substituição.
3. Para o exemplo o Bloco “0” seria o candidato a
ser substituído, uma vez que ele foi o primeiro a
ser carregado.
4. O Bloco 6 é carregado na memória cache.
0
1
2
3
Memória Cache - Cont.
10
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
FIFO – First In First Out
1. Utiliza o conceito de fila.
2. O primeiro bloco carregado é o primeiro a sair no
critério de substituição.
3. Para o exemplo o Bloco “0” seria o candidato a
ser substituído, uma vez que ele foi o primeiro a
ser carregado.
4. O Bloco 6 é carregado na memória cache.
5. Nesse momento a posição 1 da memoria cache
passa a ser posição ˜mais antiga˜
6. O algoritmo FIFO pode ser implementado por
meio de um registrador (via hardware)
0
1
2
3
Memória Cache - Cont.
11
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
FIFO – First In First Out
Considerações importantes:
1. O fato de uma determinada posição ter sido ocupada
primeiro não implica dizer que ela não seja relevante
ao processo.
2. Uma desvantagem ao utilizar o FIFO está relacionada
ao uso de variáveis globais de um determinado
programa.
3. Variáveis globais são trechos de códigos
frequentemente utilizadas, logo substituir essas
posições torna o uso da FIFO como uma estratégia
frágil nesse contexto.
0
1
2
3
Memória Cache - Cont.
12
• FIFO – First In First Out
• LFU – Least Frequently Used
• LRU – Least Recently Used
• Substituição Aleatória
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
Memória Cache - Cont.
13
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
1. Utiliza um contador para “contar” o uso da posição da
memória cache.
0
1
2
3
Contador
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
Memória Cache - Cont.
14
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
1. Utiliza um contador para “contar” o uso da posição da
memória cache.
0
1
2
3
200
Contador
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
Memória Cache - Cont.
15
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
1. Utiliza um contador para “contar” o uso da posição da
memória cache.
0
1
2
3
200
100
Contador
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
Memória Cache - Cont.
16
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
1. Utiliza um contador para “contar” o uso da posição da
memória cache.
0
1
2
3
200
100
10
Contador
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
Memória Cache - Cont.
17
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
1. Utiliza um contador para “contar” o uso da posição da
memória cache.
0
1
2
3
200
100
10
50
Contador
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
Memória Cache - Cont.
18
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
1. Utiliza um contador para “contar” o uso da posição da
memória cache.
2. O bloco a ser substituído é o menos frequentemente
utilizado.
0
1
2
3
200
100
10
50
Contador
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
Memória Cache - Cont.
19
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
1. Utiliza um contador para “contar” o uso da posição da
memória cache.
2. O bloco a ser substituído é o menos frequentemente
utilizado.
3. O bloco menos utilizado, no exemplo, é o Bloco “2” é o
candidato a ser substituído quando o algoritmo LFU é
utilizado, visto que ele foi o “menos utilizado”.
0
1
2
3
200
100
10
50
Contador
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
Memória Cache - Cont.
20
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
1. Utiliza um contador para “contar” o uso da posição da
memória cache.
2. O bloco a ser substituído é o menos frequentemente
utilizado.
3. O bloco menos utilizado, no exemplo, é o Bloco “2” é o
candidato a ser substituídoquando o algoritmo LFU é
utilizado, visto que ele foi o “menos utilizado”.
4. O Bloco 6 é carregado na memória cache.
0
1
2
3
200
100
10
50
Contador
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
Memória Cache - Cont.
21
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
Considerações importantes:
1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para
implementação, uma vez que elimina a desvantagem presente na FIFO.
0
1
2
3
200
100
10
50
Contador
Memória Cache - Cont.
22
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
Considerações importantes:
1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para
implementação, uma vez que elimina a desvantagem presente na FIFO.
2. Entretanto, a desvantagem presente na LFU concentra-se na não garantia
de que a posição mais frequentemente utilizada não necessariamente
tenha sido efetivamente usada.
0
1
2
3
200
100
10
50
Contador
Memória Cache - Cont.
23
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
Considerações importantes:
1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para
implementação, uma vez que elimina a desvantagem presente na FIFO.
2. Entretanto, a desvantagem presente na LFU concentra-se na não garantia
de que a posição mais frequentemente utilizada não necessariamente
tenha sido efetivamente usada.
3. Por exemplo, para o exemplo apresentado o Bloco “0” possui uma
contagem de 200 acessos. Entretanto, se considerarmos que esses 200
acessos fosse um vetor de 200 posições inicializado apenas?.
0
1
2
3
200
100
10
50
Contador
Memória Cache - Cont.
24
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
Considerações importantes:
1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para
implementação, uma vez que elimina a desvantagem presente na FIFO.
2. Entretanto, a desvantagem presente na LFU concentra-se na não garantia
de que a posição mais frequentemente utilizada não necessariamente
tenha sido efetivamente usada.
3. Por exemplo, para o exemplo apresentado o Bloco “0” possui uma
contagem de 200 acessos. Entretanto, se considerarmos que esses 200
acessos fosse um vetor de 200 posições inicializado apenas?.
4. Isso significaria que o contador para esse tipo de situação não se
mostra uma estratégia interessante, uma vez que dependendo da ação
realizada, ela não garantira em efetivo a substituição do menos
frequentemente utilizado. Em outras palavras, um bloco seria mantido
usando a LFU apenas pela ação de inicialização que se repete e não
pelo seu uso.
0
1
2
3
200
100
10
50
Contador
Memória Cache - Cont.
25
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LFU – Least Frequently Used
Considerações importantes:
1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para
implementação, uma vez que elimina a desvantagem presente na FIFO.
2. Entretanto, a desvantagem presente na LFU concentra-se na não garantia
de que a posição mais frequentemente utilizada não necessariamente
tenha sido efetivamente usada.
3. Por exemplo, para o exemplo apresentado o Bloco “0” possui uma
contagem de 200 acessos. Entretanto, se considerarmos que esses 200
acessos fosse um vetor de 200 posições inicializado apenas?.
4. Isso significaria que o contador para esse tipo de situação não se
mostra uma estratégia interessante, uma vez que dependendo da ação
realizada, ela não garantira em efetivo a substituição do menos
frequentemente utilizado. Em outras palavras, um bloco seria mantido
usando a LFU apenas pela ação de inicialização que se repete e não
pelo seu uso.
5. Por outro lado, nesse mesmo exemplo o bloco substituído (Bloco “2”)
poderia ter trechos de códigos referentes a variáveis globais. Logo, sua
substituição não seria adequada, visto que o seu uso se tornaria mais
frequente do que a inicialização de um vetor conforme descrito no item 3 e
4.
0
1
2
3
200
100
10
50
Contador
Memória Cache - Cont.
26
• FIFO – First In First Out
• LFU – Least Frequently Used
• LRU – Least Recently Used
• Substituição Aleatória
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
Memória Cache - Cont.
27
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
0
1
2
3
LRU – Least Recently Used
1. Remove o bloco menos recentemente utilizado.
Memória Cache - Cont.
28
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
0
1
2
3
LRU – Least Recently Used
1. Remove o bloco menos recentemente utilizado.
2. Se considerarmos os blocos carregados na
imagem, o bloco menos recentemente usado seria
o Bloco “4” da MP, representado em verde
carregado no endereço “0” da memória cache,
Memória Cache - Cont.
29
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
0
1
2
3
LRU – Least Recently Used
1. Remove o bloco menos recentemente utilizado.
2. Se considerarmos os blocos carregados na
imagem, o bloco menos recentemente usado seria
o Bloco “4” da MP, representado em verde
carregado no endereço “0” da memória cache,
3. Se o Bloco “0” for acessado, ele passa da condição
de menos recentemente utilizado e o Bloco “1” da
memória cache representado pela cor laranja
passaria ser o bloco menos recentemente utilizado,
carregado no endereço “1” da memória cache.
Memória Cache - Cont.
30
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
1. Remove o bloco menos recentemente utilizado.
2. Se considerarmos os blocos carregados na
imagem, o bloco menos recentemente usado seria
o Bloco “4” da MP, representado em verde
carregado no endereço “0” da memória cache,
3. Se o Bloco “0” for acessado, ele passa da condição
de menos recentemente utilizado e o Bloco “1” da
memória cache representado pela cor laranja
passaria ser o bloco menos recentemente utilizado,
carregado no endereço “1” da memória cache.
4. Desse modo, o endereço “0” da memória cache
passaria a ser o endereço mais recentemente
utilizado, ou seja, seria o último a ser substituído na
LRU.
0
1
2
3
Memória Cache - Cont.
31
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
Como isso se operacionaliza?
1. Este algoritmo utiliza o conceito de “idade”
para indicar se o bloco carregado na linha da
cache foi acessado recentemente ou não.
2. Para cada linha de endereço da memoria
cache relaciona um “bit de idade”
representado no exemplo por 4 bits.
0
1
2
3
0 0 0 0
Bits de Idade
Memória Cache - Cont.
32
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
Como isso se operacionaliza?
1. Este algoritmo utiliza o conceito de “idade”
para indicar se o bloco carregado na linha da
cache foi acessado recentemente ou não.
2. Para cada linha de endereço da memoria
cache relaciona um “bit de idade”
representado no exemplo por 4 bits.
0
1
2
3
0 0 0 0
0 0 0 1
Bits de Idade
Memória Cache - Cont.
33
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
Como isso se operacionaliza?
1. Este algoritmo utiliza o conceito de “idade”
para indicar se o bloco carregado na linha da
cache foi acessado recentemente ou não.
2. Para cada linha de endereço da memoria
cache relaciona um “bit de idade”
representado no exemplo por 4 bits.
0
1
2
3
0 0 0 0
0 0 0 1
0 0 1 0
Bits de Idade
Memória Cache - Cont.
34
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
Como isso se operacionaliza?
1. Este algoritmo utiliza o conceito de “idade”
para indicar se o bloco carregado na linha da
cache foi acessado recentemente ou não.
2. Para cada linha de endereço da memoria
cache relaciona um“bit de idade”
representado no exemplo por 4 bits.
0
1
2
3
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
Bits de Idade
Memória Cache - Cont.
35
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
Como isso se operacionaliza?
1. Este algoritmo utiliza o conceito de “idade”
para indicar se o bloco carregado na linha da
cache foi acessado recentemente ou não.
2. Para cada linha de endereço da memoria
cache relaciona um “bit de idade”
representado no exemplo por 4 bits.
3. Cada “bit de idade” indicará se o bloco
carregado na linha de endereço da cache foi
acessado recentemente ou não.
0
1
2
3
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
Bits de Idade
Memória Cache - Cont.
36
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
Como isso se operacionaliza?
1. Este algoritmo utiliza o conceito de “idade”
para indicar se o bloco carregado na linha da
cache foi acessado recentemente ou não.
2. Para cada linha de endereço da memoria
cache relaciona um “bit de idade”
representado no exemplo por 4 bits.
3. Cada “bit de idade” indicará se o bloco
carregado na linha de endereço da cache foi
acessado recentemente ou não.
4. Para o exemplo apresentado, a memória
cache está vazia e, após esse processo
exemplificado, foi completamente ocupada.
0
1
2
3
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
Bits de Idade
Memória Cache - Cont.
37
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
1. O algoritmo busca no “bit idade” o valor do bit que
indique o bloco menos recentemente utilizado.
0
1
2
3
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
Bits de Idade
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
?
Memória Cache - Cont.
38
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
1. O algoritmo busca no “bit idade” o valor do bit que
indique o bloco menos recentemente utilizado.
2. Para o exemplo, o Bloco carregado na memória
cache menos recentemente utilizado é o Bloco
“4” que está na linha de endereço “0” da memória
cache que possui o bit de idade correspondente a
”0000(2)”. Ele torna-se o candidato a ser
substituído.
0
1
2
3
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
Bits de Idade
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
?
Memória Cache - Cont.
39
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
1. O algoritmo busca no “bit idade” o valor do bit que
indique o bloco menos recentemente utilizado.
2. Para o exemplo, o Bloco carregado na memória
cache menos recentemente utilizado é o Bloco
“4” que está na linha de endereço “0” da memória
cache que possui o bit de idade correspondente a
”0000(2)”. Ele torna-se o candidato a ser
substituído.
3. O Bloco 6 é carregado na memória cache.
0
1
2
3
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
Bits de Idade
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
?
Memória Cache - Cont.
40
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
1. O algoritmo busca no “bit idade” o valor do bit que
indique o bloco menos recentemente utilizado.
2. Para o exemplo, o Bloco carregado na memória
cache menos recentemente utilizado é o Bloco
“4” que está na linha de endereço “0” da memória
cache que possui o bit de idade correspondente a
”0000(2)”. Ele torna-se o candidato a ser
substituído.
3. O Bloco 6 é carregado na memória cache.
4. O bit de idade é atualizado para ”0100(2)”.
Observe que o bit de idade possui um contador
que incrementa a medida em que existe um
acesso a posição da memória cache.
0
1
2
3
0 1 0 0
0 0 0 1
0 0 1 0
0 0 1 1
Bits de Idade
Como carregar o Bloco 6 da Memória
Principal se a memória cache encontra-se
cheia?
?
Memória Cache - Cont.
41
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
LRU – Least Recently Used
Considerações Importantes:
1. Diferentemente da LFU que usa um contador a LRU concentra-se no endereço menos
recentemente usado para a substituição.
2. O uso da LRU mostra-se mais efetivo do que o LFU e a FIFO por preservar a
informação mais recentemente carregada.
3. A LRU promove um número de Cache Hit maior que a LRU e FIFO tendo em vista que
utiliza o princípio da localidade temporal.
Memória Cache - Cont.
42
• FIFO – First In First Out
• LFU – Least Frequently Used
• LRU – Least Recently Used
• Substituição Aleatória
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
Memória Cache - Cont.
43
• Algoritmos de Substituição de Blocos Existentes na Memória Cache
Substituição Aleatória
• Quando um bloco da memória principal precisar vir ou
ser carregado para a memoria cache. A linha de
endereço selecionada na memória cache será escolhida
de maneira aleatória.
• Dessa forma, o bloco a ser carregado poderia entrar em
qualquer das linhas de endereço da memória cache.
• No livro do William Stalings, página 120, contém a
seguinte informação sobre Substituição Aleatória:
“Estudos de simulação têm mostrado que a
substituição aleatória oferece um desempenho
apenas ligeiramente inferior a um algoritmo
baseado no uso (SMITH, 1982).”
Professores:
Ivanildo Melo e Rosangela Melo 
ivanildo.melo@paulista.ifpe.edu.br
rosangela.melo@paulista.ifpe.edu.br
Arquitetura de Computadores
Aula 11 – Memória Principal e Secundária: Características, 
Organização, Arquitetura, Hierarquia e Memória Cache. 
[Quinta Parte]