Tópicos
Memória Virtual
P rof. Dr. José Luís Ze m
P rof. Dr. Re nato Kraide S offner
P rof. Ms. Rossano P ablo P into
Faculda de de Tecnologia de Americana
Introdução
E spaço de Endereçamento Virtual
Mapeamento
Paginação
S egmentação
S egmentação com Paginação
Proteção
Compartilhamento de Memória
S wapping em Memória Virtual
Trashing
Centro P aula S ouza
Introdução
Memória Virtual (v irtual memory) é uma técnica bastante poderosa
de gerenciamento de memória, onde as memórias principal e
secundária são combinadas , oferecendo ao usuário a impressão
de existir uma memória muito maior que a memória principal.
O conceito está baseado em desvincular o endereçamento feito
pelo processo dos endereços físicos da memória principal
Introdução
E n d e r e ç o F ís i c o
50 0
V ET [1 ]
50 1
V ET [2 ]
50 2
V ET [3 ]
50 3
V ET [4 ]
V ET [5 ]
50 4
Desta maneira, os processos e suas estruturas de dados deixam de
estar limitados ao tamanho da memória física disponív el.
.
.
.
59 9
.
.
.
.
.
.
V ET [1 0 0 ]
Um programa no ambiente de memória virtual não faz referência a
endereços físicos de memória (endereços reais), mas apenas a
endereços virtuais.
E n d e r e ç o v ir tu a l 0
E sp a ç o d e e n d e re ç a m e n to v irtu a l
Espaço de Endereçamento Virtual
No momento da execução de uma instrução, o endereço v irtual é
traduzido para um endereço físico para poder ser atendido pela
CPU.
O mecanismo de tradução do endereço virtual para o endereço
físico é denominado mapeamento.
O conjunto de endereços v irtuais que os processos podem
endereçar é chamado espaço de endereçamento virtual. Da
mesma maneira, o conjunto de endereços reais é chamado de
espaço de endereçamento real.
Espaço de Endere çamento Virtual
M e m ó ria V irtu a l
M e m ó r ia P r i n c i p a l
E n d e r e ç o v ir tu a l 1
E n d e r e ç o v ir tu a l 2
E n d e r e ç o v ir tu a l 3
E n d e r e ç o v ir tu a l 4
E n d e r e ç o v ir tu a l 5
.
.
.
E s p a ç o d e e n d e r e ça m e n to r e a l
Espaço de Endere çamento Virtual
E n d e r e ço re a l 0
En d e r e ço r e a l 1
En d e r e ço r e a l 2
En d e r e ço r e a l 3
.
.
.
E n d e r e ço re a l R
E n d e r e ç o v ir tu a l V
Mapeamento
Toda a estrutura do processo ou programa executado em seu
contexto precisa estar no espaço de endereçamento real para
poder ser referenciado pelo processador. Portanto, deve existir um
.
.
.
.
.
.
.
mecanismo que transforme endereços virtuais em endereços reais.
M e m ó r ia S e cu n d á r ia
Cada processo tem o mesmo espaço de endereçamento v irtual,
como se possuísse memória própria. O mecanismo de tradução se
encarrega de manter as tabelas de mapeamento exclusivas para
cada processo, relacionando os endereços virtuais do processo às
suas posições na memória física.
Mapeamento
Mapeamento
M e m ó r ia V i r t u a l
E s p a ço d e
e n d ere ça m en to
v ir t u a l d e A
E n d e r e ço v ir t u a l 1
.
.
.
Ta b e l a d e
m a p e a m en to
de A
.
.
.
M e m ó r ia P rin cip a l
M e m ó r ia P r in c ip a l
P r o c e ss o A
E s p a ço d e
e n d ere ça m en to
v i r tu a l d e B
.
.
.
M a p e a m e n to
E n d e r e ço v ir t u a l 1
Ta b e l a d e
m a p e a m en to
de B
.
.
.
Pro c e s s o B
P aginação
É a técnica de gerência de memória onde o espaço de
endereçamento virtual e o espaço de endereçamento real são
divididos em blocos do mesmo tamanho, chamados páginas.
P aginação
M e m ó r ia Pr in c ip a l
M e m ó r ia V ir tu a l
Pá g i n a r e a l 0
P á g in a v ir t u a l 0
Pá g i n a r e a l 1
As páginas no espaço virtual são denominadas páginas v irtuais,
enquanto as páginas no espaço real são chamadas de páginas
reais ou frames.
P á g in a v ir t u a l 1
Todo o mapeamento é realizado em nível de página, através de
tabelas de páginas.
Cada página virtual do processo possui uma entrada na tabela
(Entrada na Tabela de Página - ETP), com informações sobre o
mapeamento.
.
.
.
.
Ta b ela d e
p á g in a s
.
.
.
ETP
Pá g i n a r e a l R
Pá g i n a v i rtu a l 2
Pá g in a v i rt u a l V
M e m ó r ia Se cu n d á r ia
P aginação
P aginação
Pá g i n a v i rt u a l
Quando um programa é executado, as páginas v irtuais são
transferidas da memória secundária para a memória principal e
colocadas em frames.
D e s lo c a m e n to
E n d e r e ç o v i r tu a l
Sempre que o programa fizer referência a um endereço virtual, o
mecanismo de mapeamento localiza, na ETP da tabela do
processo, o endereço físico do frame.
N PV
D e s lo c .
T a b e la d e p á g i n a s
E TP
En d . d o f ra m e
O endereço v irtual é formado pelo número da página v irtual e um
deslocamento dentro da página.
En d . d o f ra m e
D e sl o c .
Fr am e
D e sl o c a m e n t o
E n d e r e ç o fís ic o
P aginação
P aginação
Além da informação sobre a localização da página virtual, a ETP
possui outras informações.
B it de validade que indica se uma página está ou não na memória
física (v alid bit ou residence bit).
B it de indicação se uma página
carregada (modify bit ou dirty bit).
M e m ó r i a P r in c i p a l
E n d e r e ço v irtu a l
Ta b e l a d e p á g i n a s
B i t d e v a l id a d e
0
Pa g
e fa
u lt
Pa g e in
sofreu alteração após ser
M e m ó r ia s e c u n d á r i a
M e m ó r i a P r in c i p a l
Ta b e l a d e p á g i n a s
B i t d e v a l id a d e
1
M e m ó r ia s e c u n d á r i a
P aginação
Paginação por Demand (Demand Paging)
P aginação
As páginas dos processos são transferidas da memória
secundária para a principal apenas quando são referenciadas.
O problema
pagináv eis.
da
fragmentação
também
existe
em
sistemas
A fragmentação só é encontrada, realmente, na última página,
quando o código não a ocupa por completo.
A maior ou menor fragmentação é conseqüência do tamanho da
página.
Paginação por Antecipação (Antecipatory Paging)
As páginas próximas àquela referenciada também são
carregadas, simulando uma prev isão de quais páginas serão
necessárias, trazendo-as antecipadamente para a memória.
P aginação
P aginação
P á g in a 0
PRO G RA M Fra g ;
VAR
P á g in a 1
PRO C ED U RE A ;
P á g in a 2
EN D ;
P á g in a 3
B E G IN
Páginas pequenas:
P á g in a 4
EN D .
F r a g m e n ta ç ã o
necessitam de tabelas de mapeamento maiores;
provocam maior taxa de paginação;
aumentam o número de acessos à memória secundária;
geram menor fragmentação.
O tamanho da página varia de sistema para sistema, mas
normalmente está entre 512 bytes a 4 Kbytes.
P aginação - W orking S et
P aginação - W orking S et
O conceito de W orking Set surgiu a partir da análise da taxa de
paginação dos processos.
Quando um programa iniciava sua execução, percebia-se uma
elevada taxa de page faults, que se estabilizava com o decorrer de
sua execução.
Localidade é a tendência que existe em um programa de fazer
referências às posições de memória relativ amente próximas.
P á g in a 0
I n i c i a li z a ç ã o
P á g in a 1
W H ILE () D O
B EG IN
P á g in a 2
P á g in a 3
P á g in a 4
P aginação - W orking S et
Se um programa foi desenv olvido utilizando-se as técnicas
estruturadas, o conceito de localidade estará presente com
certeza.
W orking Set é o conjunto de páginas que um processo referencia
constantemente, e por isso deve permanecer na memória
principal.
Caso contrário, aumenta-se
desempenho.
paginação, comprometendo
I m p r im e r e s u lta d o s
P aginação - W orking S et
A localidade tem um forte relacionamento com a maneira com que
a aplicação foi escrita.
a
EN D ;
o
O Working Set deve possuir um limite de páginas.
Quanto maior for o W orking Set, menor será a probabilidade de
ocorrerem page faults.
Quanto maior o Working Set, maior o consumo de memória e
menor a quantidade de processos carregados na memória principal
ao mesmo tempo, consequentemente, menor o grau de
multiprogamação.
P aginação - Realocação de P áginas
O maior problema na gerência de memória virtual por paginação
não é decidir qual página carregar para a memória, mas sim, quais
páginas remov er.
Qualquer estratégia de realocação de página deve considerar se
uma página foi ou não modificada, antes de liberá-la para outro
processo.
P aginação - Realocação de P áginas
O sistema possui um arquivo de paginação ( page file ) onde as
páginas modificadas ficam armazenadas.
M e m ó r i a P r i n c ip a l
A r q u iv o d e
p a g i n a çã o
Pa g e
out
Possíveis alterações feitas na página quando ocupada podem ser
perdidas.
P a g e in
P aginação - Realocação de P áginas
Sempre que o sistema liberar uma página, deverá gravá-la no
arquiv o de páginas ( page out ), preservando o seu conteúdo.
P aginação - Realocação de P áginas
Quando
uma destas páginas alteradas for referenciada
nov amente, ela será recuperada do arquiv o de páginas e trazida
para o W orking Set do processo ( page in ).
M e m ó r i a P r i n c ip a l
M e m ó r i a P r i n c ip a l
A r q u iv o d e
p a g i n a çã o
Pag e
ou
t
A r q u iv o d e
p a g i n a çã o
Pa g e
ou
t
P a g e in
P a g e in
P aginação - Realocação de P áginas
O sistema sabe se uma página foi alterada ou não através do bit de
modificação (modify bit ou dirty bit), que existe na ETP de cada
tabela de página.
A melhor estratégia de realocação seria aquela onde a escolha
caisse sobre uma página que não fosse referenciada num futuro
próximo, porém o SO têm dificuldade em prev er isso.
Assim, algumas estratégias são adotadas pelos SOs para a
realocação de páginas.
P aginação - Realocação de P áginas
First In First Out (FIFO)
A página que primeiro foi utilizada será a primeira a ser
escolhida.
Implementação bastante simples, sendo necessário apenas
uma fila onde as páginas mais antigas estão no início da fila e
as mais novas no final.
As páginas podem ter que voltar várias vezes à fila.
P aginação - Realocação de P áginas
Aleatória (RANDOM)
Esta escolha não utiliza critério algum para a seleção.
Todas as páginas do working set tem as mesmas chances de
serem selecionadas, inclusiv e páginas que são freqüentemente
referenciadas.
Apesar de ser uma estratégia que consome poucos recursos
não é tão comum.
P aginação - Realocação de P áginas
Least Recently Used ( LRU )
Esta estratégia seleciona
a página utilizada menos
recentemente, ou seja, a página que está mais tempo sem ser
referenciada.
Gera ov erhead causado pela atualização em cada paragina
referenciada, do momento do último acesso, além do algoritmo
de busca das páginas.
P aginação - Realocação de P áginas
Not Used Recently ( NRU )
B astante semelhante a LRU.
Nesta estratégia existe um flag que permite ao sistema a
implementação do algoritmo. O flag de referência indica
quando a página foi referenciada ou não, e está associado a
cada entrada na tabela de páginas.
Inicialmente, todas as páginas estão com flag indicando que
não foram referenciadas (0).
A medida que as páginas são referenciadas, o flag é modificado
pelo hardware (1), depois de certo tempo é possível saber
quais páginas foram referenciadas ou não.
S egmentação
A segmentação é uma técnica de gerência de memória, onde os
processos são divididos logicamente em sub-rotinas e estruturas
de dados, e colocados em blocos de informações na memória.
Os blocos tem tamanhos diferentes e são chamados de segmentos,
cada um com seu próprio espaço de endereçamento.
P aginação - Realocação de P áginas
Least Frequently Used ( LFU )
Neste esquema, a página menos referenciada, ou seja, a
menos freqüentemente utilizada será a página escolhida.
Para isso, é mantido um contador di número de referências
feitas às páginas.
A página que contiver o contador com o menor número de
referências será a página escolhida.
Este algoritmo privilegia páginas que são mais utilizadas.
Páginas que acabaram de entrar na memória podem ser
escolhidas para deixar a mesma.
S egmentação
P r o c e d im e n to X
P RO G RA M S e g m e n to ;
V A R A : A R R A Y. . .
C : ...
PRO C ED U RE X;
Pr o g r a m a Prin cip a l
F u n çã o Y
EN D ;
A grande diferença entre a paginação e a segmentação é que,
enquanto a primeira div ide a memória em partes de tamanho fixos,
sem qualquer ligação com a estrutura do processo, a segmentação
permite uma relação entre a lógica do processo e sua divisão na
memória.
FU N C T IO N Y;
A rra y A
EN D ;
B E G IN
EN D .
V a r iá v e l C
.
.
.
S egmentação
Os segmentos são mapeados através de tabelas de mapeamento
de segmentos (TMS).
Os endereços são compostos pelo número do segmento e um
deslocamento dentro do segmento.
O número do segmento identifica unicamente uma entrada na
tabela de segmentos (E TS), onde estão as informações sobre o
segmento na memória real.
S egmentação
S e g m e n t o v ir tu a l
D e sl o c a m e n to
E n d e r e ç o v i r tu a l
D e s lo c .
T a b e la d e se g m e n t o s
ET S
E n d . d o s e g m e n to
D e s lo c .
S e g m e n to n a
m e m ó r i a p r in c ip a l
D e s lo ca m e n to
E n d e r e ç o f ís ico
S egmentação
O SO mantém uma tabela com áreas liv res e ocupadas da
memória.
Quando um novo processo é carregado para a memória, o sistema
localiza um espaço livre que o acomode.
As estratégias para escolha da área liv re podem ser as mesmas
utilizadas na Alocação Particionada Dinâmica, ou seja, best fit,
worst fit ou first fit.
O problema da fragmentação também ocorre nesse modelo.
Um outro problema é sua complexidade, pois o SO dev e manter
tabelas de segmentos que v ariam de acordo com o número de
segmentos.
S egmentação com paginação
S istemas que implementam a segmentação com paginação
permitem a divisão lógica dos processos em segmentos e, por sua
v ez, cada segmento é div idido, fisicamente, em páginas.
S egmentação com paginação
P roteção
S e g m e n to v ir tu a l
A proteção é necessária para impedir que um processo, ao obter
acesso a uma página ou segmento do sistema, a modifique ou
mesmo tenha acesso a ela.
E ste esquema é implementado utilizando-se as entradas das
tabelas de mapeamento, onde alguns bits especificam os acessos
permitidos a cada uma das páginas / segmentos.
E n d e r e ço vir tu a l
N u m .
se g m e n to
N um .
p á g in a
D e slo c a m e n to
Ta b e la d e se g m e n to s
ETS
E n d . d a t a b e l a d e p á g in a s
L
Ta b e la d e p á g in a s
G
En d ereço da
p á g i n a / se g m e n to
ETP
E n d e re ç o d o fr a m e
B it s d e p r o te ç ã o
E n d e r e ço d o fr a m e
D e slo c a m e n to
E n d e r e ço físico
P roteção
Compartilhamento de Memória
E m ambientes multiprogramáveis, é comum a utilização de códigos
reentrantes.
E sp a ço d e
e n d e r e ça m e n to
vir t u a l d e A
E n d e r e ço vir tu a l 1
LG
D e scriçã o
00
10
11
Se m a ce sso
A ce ss o d e le itu r a
A ce ss o p a r a le itu r a / g r a v a ç ã o
T a b e la d e
m a p e a m e n to
d e A
.
.
.
M e m ó r ia P r in cip a l
P r o c e sso A
P á g in a
E sp a ço d e
e n d e r e ça m e n to
v ir tu a l d e B
E n d e r e ço vir tu a l 1
.
.
.
P r o ce ss o B
T a b e la d e
m a p e a m e n to
de B
S wapping em Memória Virtual
S wapping em Memória Virtual
M e m ó r ia P r in c i p a l
O conceito de swapping continua válido quando aplicado à
memória virtual.
P ro ce sso A
Pr o c e s s o B
Em sistemas que utilizam esta técnica, quando existem novos
processos que devem ser processados e não existe mais memória
real suficiente, o SO seleciona um ou mais processos que dev erão
deixar a memória para ceder espaço aos nov os processos.
Na prioridade, escolhe-se, dentre os processos, os de menor
prioridade e no critério estado do processo escolhe-se aqueles
processos que estão aguardando algum ev ento (bloqueados).
Sw
Pr o c e s s o D
ap
t
Os critérios utilizados para escolha do processo são a prioridade e
o estado do processo.
P ro ce sso C
ou
P ro ce sso F
P r o ce s s o E
M e m ó r ia P r in c i p a l
Pr o c e s s o B
P r o ce s s o A
Sw
ap
in
A r q u iv o d e
sw a p p in g
Pr o c e s s o C
P ro ce sso F
P ro ce sso B
P r o c e ss o D
Trashing
Trashing pode ser definido como sendo a excessiva transferência
de páginas / segmentos entre a memória principal e a memória
secundária.
Esse problema aplica-se tanto a sistemas que implementam
paginação como para aqueles que implementam a segmentação.
O trashing ocorre quando existem mais processos competindo por
memória do que espaço disponível.
Trashing
O SO tenta administrar a memória de maneira que todos os
processos sejam atendidos.
De qualquer maneira, se existir mais processos para serem
executados do que memória disponível, a solução seria
acrescentar mais memória principal.
Memória Virtual
P rof. Dr. José Luís Ze m
P rof. Dr. Re nato Kraide S offner
P rof. Ms. Rossano P ablo P into
Faculda de de Tecnologia de Americana
Centro P aula S ouza