Memoria Virtual

3/31/14

AEDS III
Aula 2: Memória Virtual e Paginação
Prof. Olga Goussevskaia

Conteúdo
• Localidade de Referência
• Memória Virtual e Paginação
• Ordenação Externa
•
•
•
•

Intercalação balanceada
Seleção por substituição
Intercalação polifásica
Quicksort externo

• Árvores B, B*
2

1

3/31/14

Hierarquia de memória

3

Localidade de Referência
Padrões de acesso a dados observados desde os primeiros sistemas de computação:
Temporal: se um dado é acessado uma vez, há uma probabilidade grande dele ser acessado novamente num futuro próximo.
Ex: instruções dentro do corpo de um loop; árvores…

Espacial: se um dado é acessado uma vez, há uma probabilidade grande do seu vizinho ser acessado em breve.
Ex: percorrendo vetor[0], vetor[1], vetor[2], …
4

2

3/31/14

Localidade em padrões de acesso

5

Pesquisa em Memória Secundária
Localidade de Referência Temporal:
Sistemas de hierarquia de memória

Localidade de Referência Espacial:
Estruturas de paginação

Projeto de um sistema de memória secundária
Dimensionamento de cada nível de memória
Benefício x custo

Dimensionamento de páginas
Pequenas demais: muitos “misses”, poucos “hits”
Grande demais: fragmentação: memória ocupada por dados que não serão acessados

6

3

3/31/14

Pesquisa em Memória Secundária
• O que fazer quando os dados (e.g. vetor a ser ordenado) não cabem na memória principal?
• Como implementar de forma eficiente a interface entre dois níveis de memória, e.g., RAM e disco? • Solução: VIRTUALIZAÇÃO DE MEMÓRIA

7

Memória Virtual
Espaço de endereçamento virtual:
• Não possui relação com o espaço físico de memória
• Permite o uso de dispositivos adicionais, tais como discos rígidos, como se fosse memória (RAM)
• Permite o uso de mais “memória” do que o fisicamente instalado no sistema. (Resolve o problema de falta de memória)
• Permite que cada programa tenha um espaço de endereçamento contíguo