Embed Size (px)
Citation preview
Sistemas Operacionais
- Gerência de Memória -
Memória Virtual
É uma técnica sofisticada de gerência de memória
As memórias principal e secundária são combinadas,
dando ao usuário a impressão de existir uma memória
muito maior do que a MP
O conceito da memória virtual está em desvincular o
endereçamento feito pelo programa dos endereços
físicos da MP
Assim, o programa não fica limitado ao tamanho da memória
física disponível
Memória Virtual
Anteriormente, vimos que o uso de registradores base e
limite eram usados para criar uma abstração de espaços
de endereçamento
Porque usar a memória virtual?
Ainda existe um outro problema: gerenciar programas que
utilizam quantidades excessivas de memória
Solução: usar a técnica de overlay?
A técnica de overlay exige que o programador se preocupe em
dividir o seu código de forma que os módulos possam ser trazidos
para a memória de forma independente → trabalho árduo e lento
A ideia é atribuir esta tarefa ao sistema
Memória Virtual
Um programa em um ambiente de memória virtual faz
referência a endereços virtuais
No momento da execução de uma instrução, o endereço
virtual é traduzido para um endereço físico
Esta tradução é chamada mapeamento
O conjunto de endereços virtuais que um processo pode
endereçar é chamado de espaço de endereçamento
virtual
Analogamente o conjunto de endereços reais é
chamado espaço de endereçamento real
Memória Virtual
O espaço de endereçamento virtual não possui relação
direta com o espaço de endereçamento real
Um programa pode fazer referência a endereços virtuais
que estejam fora dos limites do espaço real
Esp
aço
de e
nd
ere
ça
me
nto
vir
tua
l
Esp
aço
de e
nd
ere
çam
en
to r
ea
l
Endereço virtual 0
Endereço virtual 1
Endereço virtual 2
Endereço virtual 3
Endereço virtual 4
Endereço virtual 5
.
.
.
Endereço virtual V
Endereço real 0
Endereço real 1
Endereço real 2
Endereço real 3
.
.
.
Endereço real R
Mapeamento
Nos sistemas modernos a tarefa de tradução de endereços
virtuais é realizada pelo HW juntamente com o sistema
operacional
O dispositivo de HW responsável por esta tradução é
conhecido como MMU (Memory Management Unit)
O MMU é acionado sempre que é feita referência a um
endereço virtual
Cada processo tem seu próprio espaço de endereçamento
virtual
O mecanismo de tradução deve manter tabelas de mapeamento
exclusivas para cada processo
Mapeamento
O sistema deve fazer
referência a tabela de
mapeamento do processo
em execução
Um registrador é usado para
guardar o endereço da
tabela de mapeamento
corrente
As tabelas mapeiam blocos
de dados
O tamanho do bloco da
memória irá definir o
número de entradas da
tabela de mapeamento
Processo A
Espaço deendereçamento
virtual de A
Endereço virtual 1
.
.
.
Tabela demapeamento
de A
Espaço deendereçamento
virtual de B
Endereço virtual 1
.
.
.
Tabela demapeamento
de B
Processo B
Memória Principal
Memória Virtual
Quando o programa é executado só uma parte do código fica
residente na memória principal
O restante do código fica na memória secundária até o
momento em que for referenciado
Assim, o sistema operacional utiliza a memória secundária
como uma extensão da MP
O sistema operacional deve ser responsável por
Trazer parte do código referenciado que esteja na MP
Escolher qual parte do código residente na MP ira sofrer um
swap out
Paginação
A memória virtual por paginação é uma técnica onde o
espaço de endereçamento virtual e real são divididos
em blocos do mesmo tamanho
Divide a memória física em blocos de tamanho fixo chamados
quadros (frames)
Divide a memória lógica em blocos de mesmo tamanho
chamados páginas
Evita o problema de ajustar trechos de memória de
tamanhos variáveis
Nos esquemas anteriores as partições tinham tamanhos
variáveis
Paginação
Quando um processo precisa ser executado, suas páginas
são carregadas em qualquer quadro disponível
O mapeamento do endereço virtual em real é feito através da
tabela de páginas
Cada processo possui
sua própria tabela de
páginas
A MMU é responsável
por fazer a tradução
Memória Virtual
.
.
.
.
Página virtual 0
Página virtual 1
Página virtual 2
Página virtual V
Tabela depáginas
ETP
Memória Principal
Memória Secundária
.
.
.
Página real 0
Página real 1
Página real R
Paginação
Cada endereço virtual é dividido em duas partes: número da
página (p) e deslocamento dentro da página (d)
O número da página é usado como índice da tabela de
página, que conterá o endereço base de cada quadro (f) na
memória física
O endereço real é
obtido combinando o
endereço do frame (f)
com o deslocamento
dentro da página (d)
Paginação
Exemplo:
Memória lógica de 16 bytes
(16 bytes = 128 bits = 27 bits)
Páginas de 4 bytes
(4 bytes = 32 bits = 25 bits)
Memória física de 32 bytes
(32 bytes = 256 bits = 28 bits)
Entrada da tabela de páginas
possui 3 bits e pode referenciar
até 23 frames
f f f d d d d d
p p d d d d d
Paginação
Em geral, uma entrada da
tabela de páginas possui
4 bytes
Com 4 bytes (32 bits) pode-se
referenciar até 232 quadros
Se o tamanho de um quadro é
4 Kbytes (4096 bits = 212 bits),
então é possível endereçar:
212 x 232 = 244 bits = 4Tbytes
Tabela de Páginas
Além da informação sobre a localização da página, a tabela
de páginas possui outras informações como:
Bit de validade: indica se uma página está (1) ou não (0) na
memória principal
Bit de proteção: indica qual tipo de acesso é permitido na
página, onde 3 bits podem ser usados para habilitar e desabilitar
cada uma das operações básicas em uma página (leitura,
escrita e execução)
Bit de modificação: indica 1 quando a página foi escrita na
memória principal
Bit de referência: indica 1 quando a página foi referenciada na
memória principal
Paginação
Quando um processo faz referência a um endereço virtual, a MMU
verifica através do bit de validade se a página está na memória
Se for feita referência a um endereço de uma página que não está
carregada na MP, então ocorre um page fault (falha de página)
Neste caso, o sistema transfere a página da memória secundária para
a memória principal
O número de page faults gerados por cada processo em um
determinado intervalo de tempo é definido como taxa de paginação
do processo
Se a taxa de paginação dos processos atingir valores elevados, o
excesso de operação de E/S poderá comprometer o sistema
Paginação Endereço virtual
Tabela de páginas
Bit de validade
0
Memória Principal
Memória secundária
Page fault
Tabela de páginas
Bit de validade
1
Memória Principal
Memória secundária
Page in
Política de Busca de Páginas
Ao se carregar uma página para a memória pode-se adotar
duas estratégias diferentes: paginação por demanda e
paginação antecipada
Paginação por Demanda
As páginas do processo são transferidas da memória
secundária para a principal apenas quando são referenciadas
Leva para a MP apenas as páginas realmente necessárias à
execução do programa
Política de Busca de Páginas
Paginação Antecipada
Além da página referenciada, carrega para a memória principal
outras páginas que podem ser necessárias ao processo ao
longo do processamento
Se o programa estiver armazenado sequencialmente no disco,
economiza-se tempo ao levar um conjunto de páginas
Caso o programa não necessite da paginação antecipada, o
sistema terá perdido tempo e ocupado memória
desnecessariamente
Política de Busca de Páginas
Pode se usar uma estratégia combinada:
A técnica de paginação antecipada pode ser empregada no
momento da criação de um processo
Quando um processo é criado, diversas páginas do programa
que estão na memória secundária devem ser carregadas para a
MP gera um alto número de page faults
Se o sistema optar por carregar um conjunto de páginas, a taxa
de paginação do processo deverá cair imediatamente
Ao diminuir o número de page faults, diminui-se o tempo gasto
com operações de E/S e o desempenho do sistema aumenta
Working Set
MP contém páginas de diferentes processos
Durante a execução de um processo, algumas páginas são
carregadas e outras são swapped out
Ao se escolher uma página para ser retirada da MP, existe a
possibilidade de enviar para MS uma página de outro processo,
logo antes desta ser utilizada
É importante reduzir a taxa de page faults, sem prejudicar os
outros processos
Quando o sistema gasta a maior parte do tempo fazendo
swapping, ocorre um problema conhecido como thrashing
Working Set
Para evitar o thrashing é necessário adivinhar qual parte de
código será mais necessária no futuro → princípio da
localidade
Princípio da Localidade:
É a tendência do processador
referenciar instruções e
dados na memória principal
localizados em endereços
próximos
Por exemplo, esta tendência
pode ser justificada pela alta
incidência de estruturas de
repetição e acessos a vetores
Página 0
Página 1
Página 2
Página 3
Página 4
Inicialização
WHILE () DO BEGIN
END;
Imprime resultados
Princípio da Localidade
Localidade espacial:
quando um item é referenciado, existe grande
probabilidade que itens com endereços próximos
sejam referenciados em seguida
Localidade temporal:
Quando um item é referenciado, existe grande
probabilidade que ele seja referenciado novamente
em breve
Working Set
O conceito de working set está diretamente ligado ao
princípio da localidade
O working set de um processo é o conjunto de páginas
constantemente referenciadas pelo processo
O working set deve
permanecer na MP para que o processo execute eficientemente
ter um limite máximo de páginas permitidas
Se o tamanho do working set for muito grande
Então, menor será a chance de falhas de página
Porém, menos processos irão compartilhar a memória
Working Set
Uma maneira de implementar o modelo de working set é
analisar a taxa de paginação de cada processo
Caso um processo tenha uma taxa de paginação acima
de um limite definido pelo sistema
o limite de páginas reais deve ser aumentado na tentativa de
alcançar o working set
Caso um processo tenha uma taxa de paginação abaixo
de um certo limite
O sistema pode reduzir o limite de páginas sem comprometer o
seu desempenho
Política de Alocação de Páginas
Determina quantos quadros (frames) um processo pode
manter na memória principal
Existem duas alternativas: fixa e variável
Na Política de Alocação Fixa
Cada processo tem um número máximo de frames que pode ser
usado durante a execução
Na Política de Alocação Variável
O número máximo de frames alocado para um processo durante
a sua execução pode variar
Política de Alocação de Páginas
Política de Alocação Fixa
Se o número de frames alocado para um processo for pouco,
uma página do próprio processo deve ser descartada para que
outra seja carregada
O limite de frames deve ser definido no momento da criação do
processo com base no tipo de aplicação que será executada
Se o limite for pequeno → o processo terá alto índice de page faults
Se o limite for alto → poucos processos compartilharão a memória, podendo
aumentar o swapping de processos
O no de frames pode ou não ser igual para todos os processos
Alocar o mesmo número de frames parece justo, porém pode não ser uma
boa opção, pois os processos possuem necessidades diferentes
Política de Alocação de Páginas
Política de Alocação Variável
Durante a execução dos processos o número máximo de frames
pode variar em função de sua taxa de paginação e ocupação da
memória principal
Um processo com alta taxa de paginação
Pode ter o limite máximo de frames aumentado para diminuir o alto índice de
page faults
Um processo com baixa taxa de paginação
Pode ter seus frames alocados para outros processos
Este mecanismo é mais flexível, porem exige que o SO monitore
constantemente o comportamento dos processos
Política de Substituição de Páginas
A política de substituição pode ser classificada segundo
o seu escopo: local ou global
Escopo Local
Apenas as páginas do processo que gerou o page fault podem
ser candidatas a substituição
As páginas dos demais processos não são avaliadas para
substituição
Escopo Global
Todas as páginas alocadas na MP são candidatas a substituição
Política de Substituição de Páginas
Existe uma relação entre o escopo da política de
alocação e de substituição
A política de alocação fixa permite apenas a política de
substituição com escopo local
A política de alocação variável permite as políticas de
substituição com escopo local e global
Variável e Local: de tempos em tempos, o número de frames
pode ser recalculado, mas a substituição é só local
Variável e Global: o número de frames varia quando os
processos alocam frames de outros processos → Mais adotada
Algoritmos de Substituição de Páginas
O maior problema na gerência da memória virtual com
paginação não é decidir qual página será carregada na
memória principal
A dificuldade é decidir qual página será retirada da memória
principal
Os algoritmos de substituição de página têm o objetivo
de selecionar os frames que tenham menor chance de
serem referenciados em um futuro próximo
Quanto mais sofisticado o algoritmo de substituição de
páginas, maior será a sobrecarga para o sistema
operacional
Algoritmos de substituição de páginas
OPT ou MIN: Algoritmo Ótimo
Possui a melhor taxa de falha de página dentre todos os
algoritmos
Substitui a página que ficará mais tempo sem ser referenciada
no futuro
Difícil saber de antemão a string de referência (a ordem em que
as páginas serão referenciadas durante a execução)
Como produz um resultado ótimo, é usado para estudos
comparativos para se testar a eficiência de outros algoritmos
OPT
String de Referência:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
9 falhas de página
Algoritmos de substituição de páginas
FIFO (First In First Out)
Quando uma página precisar ser substituída, a página mais
antiga será escolhida para sair da memória
Fácil de entender e programar
É razoável pensar que uma página que já foi carregada para a
MP há mais tempo, já tenha sido referenciada o suficiente
Porém, isto nem sempre é verdade e seu desempenho pode não
ser bom
Pode ser que a primeira página carregada seja a mais utilizada no
sistema
FIFO
String de Referência:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
15 falhas de página
FIFO
Anomalia de Belady: a taxa de falha de página pode
aumentar enquanto a quantidade de quadros aumenta
String de Referência: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Algoritmos de substituição de páginas
LRU (Least Recently Used)
Substitui a página menos recentemente usada, ou seja aquela
cuja última referência foi feita há mais tempo
Se for considerado o princípio da localidade, é provável que
uma página que não tenha sido referenciada recentemente não
seja usada novamente em um futuro próximo
Boa estratégia
Possui maior sobrecarga pois deve manter atualizado o
momento do último acesso a cada página (usa um timestamp)
LRU
String de Referência:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
12 falhas de página
Algoritmos de substituição de páginas
NRU (Not Recently Used)
Usa um bit de referência para indicar se a página foi usada
recentemente ou não
Inicialmente, quando uma página é trazida para a memória, o
seu bit de referência é zero
Quando uma página que já está na memória é referenciada o
seu bit muda para 1
O algoritmo substitui a página que não foi usada recentemente
Pode ser mais eficiente ao se usar bits de referência adicionais
Algoritmos de substituição de páginas
Bits de Referência adicionais (NRU diferenciado)
Ao invés de utilizar um bit para indicar se a página foi referenciada
recentemente, utiliza-se uma cadeia de bits
Por exemplo, uma cadeia de 1 byte poderia indicar a referência a
uma página nos 8 últimos períodos
Uma página com bits de referência:
00000000 Indica que a página não teve acesso nos 8 últimos
períodos
11111111 Indica que uma página teve pelo menos 1 referência a
cada período
11000100 foi usada mais recentemente do que a página 01110111
Algoritmos de substituição de páginas
Bits de referência adicionais (NRU diferenciado)
Neste caso o algoritmo NRU trabalha com o bit de referência e o
bit de modificação (dirty bit), criando 4 classes de páginas:
(0,0) não usada recentemente, nem modificada melhor página
para substituir
(0,1) não usada recentemente, mas modificada não tão boa,
pois precisará ser escrita antes da substituição
(1,0) usada recentemente, porém não modificada é provável que
logo seja usada novamente
(1,1) usada e modificada recentemente é provável que logo seja
usada novamente, além de ter que ser escrita no disco antes de ser
substituída
Algoritmos de substituição de páginas
No algoritmo que usa o bit de referência e o bit de
modificação
A página substituída será aquela de menor classe
Considera também as páginas modificadas, tentando minimizar
a quantidade de E/S necessária
Algoritmos de substituição de páginas
Segunda Chance
Cria uma modificação no algoritmo FIFO, com o objetivo de não
substituir uma página intensamente usada
O bit de referência da página mais antiga é inspecionado:
Se o bit = 0, então a substituição prossegue
Se o bit = 1, então a página recebe uma segunda chance, seu bit
de referência é zerado e sua hora de chegada é reiniciada (vai pro
fim da fila)
Se uma página é usada com frequência, e seu bit está sempre
1, então ela não será substituída
Algoritmos de substituição de páginas
Segunda Chance
Suponha uma falha de página no tempo 20
A página mais antiga é A
Suponha que A possui o bit de referência = 1 e não será
substituída
Algoritmos de substituição de páginas
Algoritmo do Relógio (Segunda Chance Melhorado)
É utilizado o mesmo algoritmo
do segunda chance
Inspeciona o bit de referência
Porém, ao invés de inserir
uma página que obteve uma
segunda chance no final da
fila, utiliza-se uma fila
circular para melhorar o
desempenho
Algoritmos de substituição de páginas
Algoritmos baseados em contadores
São mantidos contadores com o número de referências feito a
cada página
LFU (Least Frequently Used)
A página com a menor contagem é substituída
Privilegia páginas bastante utilizadas
Páginas recém trazidas terão contadores com valores baixos
MFU (Most Frequently Used)
A página com maior contagem é substituída
Baseia-se no argumento que a página com menor contagem acabou de ser
trazida para a memória e ainda está para ser usada
Tamanho da Página
Na paginação não existe fragmentação externa: todo quadro
livre de memória poderá ser alocado a algum processo
Pode acontecer alguma fragmentação interna se os requisitos
de memória de um processo não coincidirem com os limites
da página
O último quadro alocado pode não estar completamente cheio
Exemplo:
Tamanho de Página = 2.048 bytes
Memória requerida pelo processo = 21.480 bytes
Processo alocará 11 quadros 10 completos (20.480 bytes) + 1.000 bytes
Resulta em uma fragmentação interna de 1.048 bytes, no último quadro
Tamanho da página
O tamanho da página está associado a arquitetura do
hardware
O tamanho da página é uma potência de 2
Normalmente está entre 512bytes e 16Mbytes
Se o tamanho da página é pequeno:
a fragmentação interna é menor
porém a tabela de páginas pode ficar muito grande
custos de E/S são menos eficientes
Tamanho da Página
Considere o seguinte exemplo
32 bits para endereçamento virtual (232 endereços)
páginas de tamanho = 4 Kbytes = 212 bits
Qual seria o tamanho da tabela de página por processo se cada
entrada da tabela de páginas ocupasse 4 bytes?
Desta forma teríamos o endereço virtual configurado da
seguinte forma:
20 bits para indicar o número da página
12 bits para indicar o deslocamento dentro da página
Tamanho da página = 220 4 bytes = 4 Mbytes
p = 20 bits d = 12 bits
Exercício 1
Um sistema operacional implementa gerência de memória virtual
por paginação.
Considere endereços virtuais com 16 bits e a tabela de páginas de
um processo com no máximo 256 entradas.
Indique para cada endereço virtual a seguir a página virtual em que
o endereço se encontra e o respectivo deslocamento dentro da
página
a) 30710
b) 204910
c) 230410
256 entradas = 28 entradas
São necessários: 8 bits para referenciar o
número da página
Sobram 8 bits para o deslocamento
16 bits
p p p p p p p p d d d d d d d d
Exercício 1
a) 30710
b) 204910
c) 230410
0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1
Página Virtual: 1
Deslocamento: 51
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
Página Virtual: 8
Deslocamento: 1
0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0
Página Virtual: 9
Deslocamento: 0
Exercício 2
Uma memória virtual possui páginas de 1024 endereços (para este
exemplo, 1024 bytes).
Existem 8 páginas virtuais e 4096 bytes de memória real.
A tabela de páginas de um processo está descrita abaixo, sendo
que o asterisco indica que a página não está na MP.
a) Faça a lista/faixa de todos os
endereços virtuais que irão
causar page fault.
b) Indique o endereço real
correspondente aos
seguintes endereços virtuais:
0, 1023, 1024, 6500 e 3728.
Página Frame
0 3
1 1
2 *
3 *
4 2
5 *
6 0
7 *
Exercício 2
1024 endereços = 210 → 10 bits de deslocamento
8 páginas = 23 páginas → 3 bits para indicar o número da página
Endereço Virtual:
4096 bytes de memória virtual dividida em páginas de 1024 bytes
→ 4 frames = 22 frames → 2 bits para indicar o número do frame
Endereço Real:
p p p d d d d d d d d d d
f f d d d d d d d d d d
Exercício 2
Faça a lista/faixa de todos os endereços virtuais que irão causar
page fault.
Considerando que cada página possui 1024 endereços e as
páginas 2, 3, 5 e 7 não estão na MP, então as seguintes faixas de
endereços causarão page fault:
2048 – 3071
3072 – 4095
5120 – 6143
7168 – 8191
Página Frame
0 3
1 1
2 *
3 *
4 2
5 *
6 0
7 *
Exercício 2
Indique o endereço real correspondente
aos seguintes endereços virtuais:
0
1023
1024
6500
3728
virtual 0 0 0 0 0 0 0 0 0 0 0 0 0
real 0 0 0 0 0 0 0 0 0 0 0 0
Página Frame
0 3
1 1
2 *
3 *
4 2
5 *
6 0
7 * virtual 0 0 0 0 0 0 0 0 0 0 0 0 0
real 0 0 0 0 0 0 0 0 0 0 0 0
virtual 0 0 0 0 0 0 0 0 0 0 0 0 0
real 0 0 0 0 0 0 0 0 0 0 0 0
virtual 0 0 0 0 0 0 0 0 0 0 0 0 0
real 0 0 0 0 0 0 0 0 0 0 0 0
virtual 0 0 0 0 0 0 0 0 0 0 0 0 0
real 0 0 0 0 0 0 0 0 0 0 0 0
TLB
Suporte do HW
Normalmente cada processo possui a sua própria tabela de páginas
A tabela de páginas pode ser implementada como um conjunto de
registradores dedicados
Porém, se a tabela de páginas for muito grande o uso de registradores
se torna inviável
Nestes casos, a tabela de página é mantida na MP e um registrador
(PTBR - Page Table Base Register) guarda o endereço da tabela de
página
O problema é o tempo gasto para acessar um local de memória
referenciado pelo usuário: são necessários dois acessos à memória (um
para a tabela de página e outro para o endereço efetivo)
TLB
Solução padrão é usar a TLB (Translation Look-aside buffer)
A TLB é implementada em um cache especial e fornece uma
pesquisa rápida
Cada entrada da TLB consiste em duas partes: uma chave e um valor
A TLB contém apenas algumas entradas da tabela de páginas
Quando um endereço lógico é gerado pela CPU, seu número de página
é buscado na TLB
Se o número de página for encontrado, seu número de quadro estará
disponível imediatamente
Se o número de página não for encontrado (TLB miss), deve então ser feita
uma referência a tabela de página
Hardware de Paginação com TLB
Paginação em Múltiplos Níveis
Em sistemas que implementam apenas um nível de
paginação, o tamanho das tabelas de páginas pode ser um
problema
Por exemplo, em um sistema
onde vários processos estejam residentes na MP, é difícil e
custoso gerenciar tabelas de 4 Mbytes
0
1
2
(2 -1)20
Tabela de páginas
Desloc.NPV
12 bits20 bits
Endereço Virtual
32 bits
4 Mb
Paginação em Múltiplos Níveis
Uma boa solução é usar tabelas de páginas em múltiplos
níveis
No esquema da paginação com dois níveis existe uma tabela
diretório que possui uma entrada para cada tabela de página
Neste caso, cada entrada da tabela diretório possuirá:
O número da página de nível 1 (entrada da tabela de diretório)
Permite localizar e endereço da tabela de páginas na tabela diretório
O número da página de nível 2 (entrada da tabela de página)
Permite localizar o endereço do frame na tabela de páginas
O deslocamento dentro da página
Paginação em Múltiplos Níveis
Paginação em 1 nível
220 entradas na TP e cada
entrada com 4 bytes
220 x 4 bytes = 4 Mbytes
Tamanho da TP = 4 Mbytes
Paginação em 2 níveis
210 entradas na tabela de
diretório e cada entrada
com 4 bytes
210 x 4 bytes = 4 Kbytes
Tamanho da Tabela de
diretório = 4 Kbytes
Tabela diretório
Desloc.12 bits
NPV 110 bits
Endereço Virtual
NPV 210 bits
Tabela de páginas
frame
Paginação em Múltiplos Níveis
A paginação em 2 níveis pode ser estendida para mais
níveis
A vantagem da paginação em múltiplos níveis é que
estarão residentes na MP apenas as tabelas de páginas
realmente necessárias
Reduz o espaço ocupado na memória principal
Para evitar que ocorra muito page fault, a ideia é que o
princípio da localidade também seja aplicado às tabelas
de mapeamento
TLB
A gerência de memória virtual utiliza a técnica de
mapeamento para traduzir endereços virtuais em reais
O mapeamento implica em pelo menos dois acessos à MP
Um acesso para a tabela de páginas
E outro acesso no endereço efetivo (frame)
Para agilizar o acesso:
A tabela de páginas pode ser implementada como um conjunto
de registradores dedicados
Porém, se a tabela de páginas for grande o uso de registradores
se torna inviável
TLB
A solução:
Seguindo o princípio da localidade, a maioria das aplicações
referencia um número reduzido de frames na MP por vez
Logo, apenas uma parte da tabela de páginas é realmente
necessária na memória principal
Com base neste princípio foi introduzida uma memória
especial chamada TLB (Translation Lookaside Buffer)
A TLB é implementada como uma memória cache
Possui o mapeamento apenas dos endereços virtuais mais
recentemente referenciados
TLB
A TLB fornece uma pesquisa rápida
Cada entrada da TLB consiste em duas partes: uma chave e um
valor
A TLB contém apenas algumas entradas da tabela de páginas
Quando um endereço lógico é gerado pela CPU, seu número de
página é buscado na TLB
Se o número de página for encontrado, seu número de quadro
estará disponível imediatamente
Se o número de página não for encontrado (TLB miss), deve então
ser feita uma referência a tabela de página
Hardware de Paginação com TLB
Segmentação
É a técnica de gerência de memória onde o espaço de
endereçamento virtual é dividido em blocos de tamanhos
diferentes chamados segmentos
Um programa é dividido logicamente em sub-rotinas e
estruturas de dados, que são alocados em segmentos na
memória principal
PROGRAM Segmento;
VAR A: ARRAY... C: ...
PROCEDURE X;
END;
FUNCTION Y;
END;
BEGIN
END.
Procedimento X
Programa Principal
Função Y
Array A
Variável C
.
.
.
Segmentação
A principal diferença entre paginação e segmentação é:
Na paginação os programas são divididos em páginas de
tamanho fixo sem qualquer ligação com a sua estrutura do
programa
A segmentação permite uma relação entre a lógica do
programa e a sua divisão na memória
Segmentação
A definição dos segmentos é realizada pelo compilador
O espaço de endereçamento virtual de um processo possui
um número máximo de segmentos
Cada segmento pode variar de tamanho dentro de um limite
O tamanho do segmento pode ser alterado durante a
execução do programa
Espaço de endereçamento independentes permitem que uma
sub-rotina seja alterada sem a necessidade de recompilar o
programa principal e outras sub-rotinas
Segmentação
Segmentos possuem espaço de endereçamento
independentes
Segmentação
O mecanismo de mapeamento é semelhante ao da
paginação, neste caso, os segmentos são mapeados através
de tabelas de segmentos
Cada processo possui sua própria tabela de segmentos
Os endereços virtuais são compostos pelo número do segmento virtual
e por um deslocamento
O número do segmento virtual identifica a entrada da tabela de
segmentos que contém o endereço do segmento físico
O deslocamento indica a posição do endereço virtual em relação ao
endereço inicial do segmento
O endereço físico é a combinação do endereço do segmento e do
deslocamento
No do segmento (sv) Deslocamento (d)
Segmentação
Tradução do
endereço virtual
Deslocamento
Endereço virtual
Desloc.
End. do segmento
ETS
Tabela de segmentos
Desloc.
Segmento namemória principal
Deslocamento
Endereço físico
Segmento virtual
Segmentação
Cada entrada da tabela de segmentos possui
informações adicionais como:
Tamanho: especifica o tamanho do segmento
Bit de validade: indica se o segmento está na MP
Bit de modificação: indica se o segmento foi alterado
Bit de referência: indica se o segmento foi referenciado
recentemente
Bit de proteção: indica o tipo de acesso ao segmento
Segmentação
Uma vantagem da segmentação em relação a
paginação é
A facilidade em lidar com estruturas de dados dinâmicas
O tamanho do segmento pode ser facilmente alterado
Na paginação, a expansão de um vetor implica na alocação de
novas páginas e consequentemente no ajuste da TP
Diferentemente da paginação, a segmentação não
possui fragmentação interna
Existe a fragmentação externa, quando áreas livres não são
grandes o suficiente para alocar novos segmentos
Segmentação
Fragmentação externa
Segmentação
Apenas os segmentos referenciados são levados para a MP
Se as aplicações não forem desenvolvidas em módulos,
grandes segmentos estarão na MP desnecessariamente
Para alocar segmentos na MP, o sistema operacional
mantém informações com as áreas livres e ocupadas da
memória
Quando um novo segmento é referenciado o SO seleciona
um espaço livre suficiente para que o segmento seja alocado
na MP
Pode ser adotada a política best-fit, first-fit ou worst-fit
Segmentação com Paginação
Tem o objetivo de combinar vantagens das duas
técnicas
Paginação
Evita a fragmentação externa
Segmentação
Mais fácil para lidar com estruturas de dados dinâmicas, já
que o tamanho do segmento pode ser facilmente alterado
Segmentação com Paginação
Divide o espaço de endereçamento virtual em segmentos
Cada segmento é dividido em páginas
Na visão do programador a sua aplicação continua mapeada
em segmentos de tamanhos diferentes
Por outro lado, o sistema trata cada segmento como um
conjunto de páginas do mesmo tamanho
Assim, um segmento não precisa estar contíguo na memória
Elimina o problema da fragmentação externa encontrado na
segmentação pura
Segmentação com Paginação
O endereço virtual é formado por:
Número do segmento virtual
Número da página virtual
Deslocamento
O número do segmento virtual indica a entrada da tabela de
segmentos
A tabela de segmentos indica o endereço da tabela de páginas que contém o
endereço
O número da página identifica a entrada da tabela de páginas
O deslocamento indica a posição do endereço dentro da página
O endereço real é o endereço do frame encontrado na TP
combinado com o deslocamento
No do segmento (sv) No da página (p) Deslocamento (d)
Segmentação
com Paginação
Tradução do
endereço virtual
Endereço do frame Deslocamento
DeslocamentoNum.
segmentoNum.
página
Endereço virtual
Segmento virtual
End. da tabela de páginas
ETS
Tabela de segmentos
Endereço do frame
ETP
Tabela de páginas
Endereço físico
Paginação ✕ Segmentação
Consideração Paginação Segmentação
O programador precisa saber qual técnica
está sendo usada? Não Sim
O espaço de endereçamento virtual pode
exceder o tamanho da memória física? Sim Sim
Quantos espaços de endereçamento
lineares existem? 1 Vários
Os procedimentos e dados podem ser
distinguidos e protegidos separadamente? Não Sim
O compartilhamento de procedimentos é
facilitado? Não Sim
Paginação ✕ Segmentação
Consideração Paginação Segmentação
Os programas são divididos em
pedaços de tamanhos iguais Sim Não
Possui fragmentação Sim, interna Sim, externa
Por que esta técnica foi inventada?
Para se obter um
espaço de
endereçamento maior
do que a memória
física
Para permitir a divisão
dos programas
logicamente e facilitar o
compartilhamento e
proteção
