Memória Virtual
Sistemas Operacionais I
Módulo 9
FUNDAMENTOS

Execução de Programas
–
O S.O carrega partes de um processo
para a memória real
 Conjunto
–
residente (Resident set)
Configurável
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-2
FUNDAMENTOS

Execução de Programas
–
Uma falha (page-fault) é gerada quando
um endereço não presente na memória é
acessado
 Processo
vai para Blocked
 Parte que contém o endereço é carregado
para a M.R.
–
–
–
O S.O. emite uma requisição de leitura do disco
Outro processo é despachado para executar
Uma interrupção é emitida quando a E/S terminar
para que o S.O. mova o processo para a Ready
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-3
FUNDAMENTOS

Particionamento de programas
(modularização)
–
Mais processos mantidos em memória
 Só
é necessário carregar alguns pedaços do
processo
–
–
Com muitos processos na memória é
mais fácil colocar/estar no estado READY
Torna-se possível executar processos
com requisito de memória maior que a
memória real
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-4
FUNDAMENTOS

Particionamento de programas
(modularização)
–
Memória é definida em um dispositivo
secundário
 Programador
está efetivamente limitado pelo
tamanho do seu disco
–
Desnecessário carregar pedaços do
processo que não serão utilizados
 Economia
de tempo: minimiza o swap-in
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-5
FUNDAMENTOS

Tipos de memória
–
Real
 Principal
–
Virtual
 Em
disco
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-6
FUNDAMENTOS

Thrashing
–
–
“Swapping-out” pedaços de um
processo antes deste ser necessário
O processador gasta tempo em SWAP e
não em execução de processos
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-7
FUNDAMENTOS

Princípio da localidade
–
Referência a código e dados tendem a
ser localizados
 Loop
 Logo,
poucos pedaços precisam estar
presentes
–
É possível fazer uma aposta inteligente
sobre que páginas serão necessárias no
futuro
 Isto
sugere que a Memória virtual funciona
eficientemente?
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-8
FUNDAMENTOS

Memória virtual (M.V.)
–
–
Separação entre a memória lógica do
usuário e a memória física
Implementada em
 Paginação
sob demanda
 Segmentação sob demanda
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-9
FUNDAMENTOS

Suporte necessário a M.V.
–
–
Hardware precisa suportar paginação e
segmentação
O S.O precisa ser capaz de gerenciar o
movimento de páginas e segmentos
entre a memória principal e a secundária
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-10
FUNDAMENTOS

Características da paginação e
segmentação
–
Referências de memória
 Transladadas
de execução
–
em endereços físicos em tempo
Um processo
 Pode ser “swapped-out”
 Não precisa ser alocado de
 Pode ser modular
–
forma contínua
Todas as partes não precisam estar presentes na
memória principal
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-11
PAGINAÇÃO

Tabela de páginas
–
–
–
Pode ocupar muita memória real
Poderia ser armazenada na memória
virtual
Quando o processo está em RUNNING
parte da tabela está em memória
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-12
PAGINAÇÃO

Proteção de memória
–
–
Implementado com um bit de proteção
em cada frame
Valid/Invalid bit em cada entrada da
tabela de página
 “valid”
indica que a página está sendo
utilizada
 “invalid” indica que a página não está em uso
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-13
PAGINAÇÃO

Tabela de páginas multiníveis
–
Dois níveis
Tabela de Páginas
1 Nível
Tabela de Páginas
2 Nível
Sistemas Operacionais I - Versão Beta 3
Memória
24/04/2001
8-14
PAGINAÇÃO

Paginação multinível
–
Suponha um endereço lógico de 32-bits,
página de 4KBytes
 Page
Number consiste de 20-bits
 Page Offset (deslocamento) consiste de 12bits
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-15
PAGINAÇÃO

Paginação multinível
–
Supondo que a tabela de páginas é
paginada, temos
 Page
Number consiste de 10-bits (p1)
 Page Offset consiste de 10-bits (p2)
page number page offset
pi
10
p2
10
Sistemas Operacionais I - Versão Beta 3
d
12
24/04/2001
8-16
PAGINAÇÃO
Paginação
–
multinível
Exemplo interessante
Nível 1
(10-bits)
Nível 2
(10-bits)
29
19
Deslocamento
(10-Bits)
Endereço
virtual
Frame
(10-bits)
Deslocamento
(10-Bits)
Endereço
Real
0
0
0
1
0
1
10-bits
2
10-bits
2
1024
1024
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-17
PAGINAÇÃO
Paginação
–
multinível
Considerações
 Cada
nível é armazenado como uma tabela
separada
 O tempo para converter endereço lógico em
endereço físico é multiplicado pelo número
de níveis
 Embora o tempo possa ser multiplicado, o
uso de cache permite minimizar o impacto
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-18
PAGINAÇÃO

Tabela de páginas invertida
–
Uma entrada para cada página existente
no sistema
A
entrada consiste de um endereço virtual da
página armazenada na memória real, com
informações sobre o processo que é dono
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-19
PAGINAÇÃO

Tabela de páginas invertida
–
Vantagem
 Diminui
a memória necessária para
armazenar a tabela de páginas
–
Desvantagem
 Aumenta
o tempo necessário para encontrar
a página referenciada
–
Solução
 Hash
–
Table
Limita a procura a um, ou poucos, acessos
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-20
PAGINAÇÃO

Tabela de páginas invertida
–
Arquitetura
Endereço
lógico/virtual
End.
Físico
Memória
Física
Busca
Endereço lógico
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-21
PAGINAÇÃO

Implementação de Tabela de Páginas
–
–
Mantida em memória
Dois registradores
 Page-table
–
Aponta para a tabela de páginas
 Page-table
–
base register (PTBR)
length register (PRLR)
Indica o número de páginas
 Esse
esquema implica em dois acessos a
memória. Um para tabela de páginas e outra
para a instrução/dados
–
Facilmente resolvível com o uso de Translation
Look-aside buffers (TLB)
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-22
PAGINAÇÃO

Translation Lookaside Buffer
–
Contém entradas da tabela de páginas
que foram utilizadas recentemente
 Similar
–
–
ao cache de memória
Dado um endereço virtual, o processador
examina a TLB
Se a entrada esta presente (hit) o Frame e
recuperado e o endereço real é formado
 Caso
contrário (miss) o page-number é
utilizado para indexar a tabela de páginas
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-23
PAGINAÇÃO

Translation Lookaside Buffer
–
Primeiro verifica se a página já está em
memória
 Caso
–
contrário um page-fault é gerado
A TLB é atualizada com a entrada de
página
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-24
PAGINAÇÃO

Translation Lookaside Buffer
Mem. Principal
Endereço virtual
Pág #
Offset
Mem. Secundária
Translation
Lookaside Buffer
TLB hit
Offset
Carga
Pág
Tab. De Pág
TLB miss
Frame #
Offset
Endeço Real
Page fault
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-25
PAGINAÇÃO

Tamanho da página
–
Pequena
 Fragmentos
internos pequenos
 Muitas páginas para um processo
 Tabela de páginas muito grande
 Tabelas grandes resultam em grande
quantidade da tabela de página na memória
virtual
 A memória secundária é projetada para
transferência de grandes blocos. Logo
páginas grandes são bem-vindas
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-26
PAGINAÇÃO

Tamanho da página
–
Pequena
 Um
grande número de páginas estarão
presentes na memória real
–
–
A medida que o tempo avança as páginas em
memória contém porções mais recentes do
processo. Baixo Índice de page-fault
Grande
 Aumenta
a taxa de page-fault
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-27
PAGINAÇÃO

Tamanho da página
–
Múltiplos tamanhos
 Flexibilidade
no uso da TLB
 Páginas grandes podem ser utilizadas para
instruções
 Páginas pequenas podem ser utilizadas para
threads
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-28
SEGMENTAÇÃO E PAGINAÇÃO

Paginação
–
–

Segmentação
–
–

Transparente para o desenvolvedor de
programas
Elimina a fragmentação externa
É visível para o desenvolvedor de programas
Permite o crescimento de estruturas,
modularidade e suporte a compartilhamento e
proteção
Cada segmento tem número fixo de
páginas
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-29
SEGMENTAÇÃO E PAGINAÇÃO

Endereçamento
Endereço virtual
Segmento #
Página #
Offset
Entrada da tabela de segmentos
Bits de controle
Tamanho
Segmento
Entrada da tabela de páginas
P M Bits de controle
Frame #
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-30
SEGMENTAÇÃO E PAGINAÇÃO

Translação de endereços
Seg # Pag #
Offset
Frame # Offset
Seg Table Ptr
Tabela de
Páginas
Tabela de
Segmentos
+
Processo
S#
Segmentação
Sistemas Operacionais I - Versão Beta 3
Offset
P#
Frame
+
Paginação
Memória principal
24/04/2001
8-31
SEGMENTAÇÃO E PAGINAÇÃO

MULTICS – Translação de endereços
Endereço virtual
S
N
Tabela de
Segmentos
End. Real
Tabela de Páginas
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-32
SEGMENTAÇÃO E PAGINAÇÃO

I386 – Translação de endereços
End.
Virtual
Descritor
Deslocamento
Tabela de Segmentos
Descritor
End.
Linear
Diretório
Memória Real
Página
Offset
End. Físico
Diretório de Tab. Páginas
Reg. Tabela Pág.
Tab. Páginas
Reg. Tabela Pág.
Dir. Páginas
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-33
SEGMENTAÇÃO E PAGINAÇÃO

Translação em dois níveis de endereços em
arquiteturas de 32-bits
End. Lógico
Tabela
de
Segmentos
Segmentos
Tabela
de
Páginas
Sistemas Operacionais I - Versão Beta 3
Páginas
24/04/2001
8-34
POLÍTICAS

Busca
–
–
Determina qual página ser retirada da
memória
Paginação por demanda somente carraga
a página quando uma referência é feita a
um endereço nela contida
 Alta
taxa de falhas de páginas quando o
processo inicia sua execução
–
Pré-paginação libera mais quadros
(frames) que o necessário
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-35
POLÍTICAS

Colocação
–
Determina onde, na memória real, partes
de um processo se alojarão
 Normalmente
irrelevante já que o hardware
determina os endereços reais
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-36
POLÍTICAS

Substituição
–
Seleciona a página que será substiuida
por uma nova
 Algumas
páginas podem não ser
substituíveis
–
–
Uso de lock no frame
Utilizado no núcleo do S.O., estruturas de dados,
buffers etc
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-37
POLÍTICAS

Substituição
–
Política ótima
 Seleciona
para substituição a página cuja a
próxima referência será mais demorada
 É impossível ter conhecimento de eventos
futuros!
–
Logo, essa política é uma falácia!
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-38
POLÍTICAS

Substituição
–
First-in, first-out (FIFO)
 Frames
alocados a um processo são tratados
com um buffer circular
–
–
Páginas “mais velhas” são substituídas
Páginas são removidas no estilo Round-Robin
 Fácil
implementação
 Essas páginas podem ter que retornar
rapidamente!
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-39
POLÍTICAS

Substituição
–
Least Recently Used (LRU)
 Substitui
a página que não foi referenciada
por mais tempo
 Esta página pode ser referenciada em um
futuro próximo
 Cada página precisa conter um campo com a
data da última referência
–
Overhead alto
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-40
POLÍTICAS

Substituição
–
Clock
 Utiliza
um bit , chamado use-bit
 Página é carregada na memória com
use-bit=0
 Referência a página faz use-bit=1
 Quando for necessário a substituição, o
primeiro frame com use-bit=0 é substituído
 Durante a procura para substituição use-bit=1
é trocado para use-bit=0
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-41
POLÍTICAS

0
Substituição
–
Pág. 9
use-bit=1
Clock
Pág. 1
use-bit=0
n
next frame
pointer
…
…
Pág. 191
use-bit=1
Pág. 13
use-bit=1
Sistemas Operacionais I - Versão Beta 3
Pág.45
use-bit=1
Pág. 556
use-bit=1
24/04/2001
8-42
POLÍTICAS

Page-buffering
–
A página substituída é colocada na
 Free-page-list
–
Se a não tiver sofrido modificações
 Modified-page-list
–
–
Se sofreu alguma alteração
É removida a posteriori
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-43
POLÍTICAS

Conjunto residente
–
Alocação fixa
 Número
fixo de páginas durante a execução
do processo
 Implica na substituição local de páginas
–
Alocação variável
 Número
de páginas alocadas ao processo
varia durante a execução do processo
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-44
POLÍTICAS

Limpeza
–
Por demanda
A
página somente é removida se for
selecionada para substituição
–
Antecipada
 Páginas
são removidas em lotes
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-45
POLÍTICAS

Limpeza
–
Uso de page-buffering melhora o
desempenho
 As
páginas podem ser “recuperadas”, caso
referenciadas, rapidamente
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-46
POLÍTICAS

Controle de carga
–
Determina o número de processos
residentes em memória
 Poucos
–
Algumas vezes todos os processos podem estar
no estado BLOCKED e a CPU fica ociosa
 Muitos
–
processos
processos
Trashing
 Como
definir muito e pouco?
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-47
POLÍTICAS

Suspensão
–
–
Processos com menor prioridade
Page-fault
O
processo não possui seu conjunto
presente na memória
 Estará no estado BLOCKED
–
Último processo a ser ativado
O
processo possivelmente não está com seu
conjunto residente presente na memória
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-48
POLÍTICAS

Suspensão
–
Processos com menor conjunto
residente
 Requer
menor esforço para carregá-lo para
memória
–
Processos “grandes
 Obtém
–
maior número de frames livres
Processo com a maior janela de
execução restante
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-49
UNIX e SOLARIS
Gerencia de Memória

Sistema de paginação para processos
–

Alocador de memória para o Kernel
Estruturas de dados
–
Tabela de páginas
 Uma
–
por processo
Disk block descriptor
 Descreve
–
Page frame data table
 Descreve
–
a cópia da página virtual (em disco)
cada quadro da M.R.
Swap-use table
 Uma
por cada dispositivo de swap
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-50
UNIX e SOLARIS
Gerencia de Memória

Substituição de páginas
–
Refinamento da política do relógio
 two-handed

clock algorithm
Kernel Memory Allocator
–
Muitos blocos são menores que a página
padrão
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-51
Windows NT
Gerencia de Memória

Todos os processos compartilham o
mesmo espaço de endereçamento
–

2 Gbyte
Tipos de Paginas
–
–
Available
Reserved
 Reservada
para um processo mas não
computa na quota de memória do processo
–
–
Committed
Zeros
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-52
WORKING SET

Número fixo de páginas referenciáveis
–

  working-set window
Exemplo: 10,000 instruções
WSSi (working set do processo Pi)
–
–
Total de páginas referenciadas no último

Se 
 Muito
pequeno, não incorpora bem a
localidade
 Muito grande, atua além da localidade
   incorpora o programa todo
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-53
WORKING SET

Demanda de frames
–
D= WSSi
D > memória  Thrashing
 Se D > memória
 Se
Então suspenda um processo
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-54
MANUTENÇÃO DO WORKING SET


Aproximação entre interval timer e
reference bit
Exemplo:  = 10,000
–
–
–
Timer interrompe a cada 5000 u.t.
2 bits de referência para cada página
Sempre que ocorrer a interrupção



–
Se um dos bits em 1  Página no W.S.
Coloca os bits em 0
Por que isto não é completamente preciso?
Aprimorando

10 bits e interrupção a cada 1000 u.t.
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-55
ESQUEMA
PAGE-FAULT FREQUENCY

Taxa “aceitável” de page-fault
–
Taxa pequena
 Processo
perde frames.
–
Taxa alta
 Processo
ganha frames.
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-56
OUTRAS CONSIDERAÇÕES
Preparação
 Seleção do tamanho de página

–
–
–
–
fragmentação
Tamanho da tabela
E/S overhead
localidade
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-57
OUTRAS CONSIDERAÇÕES
Estrutura
de programa
–
Array A[1024, 1024] de integer
–
Cada linha é armazenada em uma página
Programa 1:
for j := 1 to 1024 do
for i := 1 to 1024 do
A[i,j] := 0;
1024 x 1024 page faults
Sistemas Operacionais I - Versão Beta 3
Program 2:
for i := 1 to 1024 do
for j := 1 to 1024 do
A[i,j] := 0;
1024 page faults
24/04/2001
8-58
SEGMENTAÇÃO POR DEMANDA

Utilizado quando o hardware não suporta
(eficientemente) paginação por demanda
–

S.O. aloca memória em segmentos registrados
em “segment descriptors”
O Segment descriptor contém um bit de
validade (valid bit) para indicar se o
segmento está presente na memória
–
–
Se presente: o acesso continua
Se não presente: “segmentation fault”.
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-59
Evolução das Organizações de Memória
Real
Sistemas
Mono
Usuário
Real
Virtual
Sistemas
Multiprogramados
em Memória Real
Sistemas
Multiprogramados
em Memória Virtual
Paginação
Partições
Fixas
Absoluta
Partições
Variáveis
Paginação
Pura
Segmentação
e
Segmentação
Pura
Combinadas
Relocáveis
Sistemas Operacionais I - Versão Beta 3
24/04/2001
8-60
SEGMENTAÇÃO POR DEMANDA

Ótimo
String
Referência
Frame 1
de
7
7
7
2
2
2
2
2
2
2
2
2
2
2
2
2
2
7
7
7
0
0
0
0
0
0
4
4
4
0
0
0
0
0
0
0
0
0
0
1
1
1
3
3
3
3
3
3
3
3
1
1
1
1
1
1
1
F
F
Frame 3
F
F
1
“A
exemplo
das
pessoas,
os1 computadores
2
0
3
0
4
2
3
0
3
2
2
0
1
7
0
também tendem a adiar o quanto possível a
ocorrência de eventos desagradáveis”
0
Frame 2
Page Faults

7
F
Sistemas Operacionais I - Versão Beta 3
F
F
F
1
F
24/04/2001
8-61