UNIDADE 08 Gerência Memória Virtual

Prévia do material em texto

Unidade VIII: 
Gerência de Memória Virtual
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS
FACULDADE DE COMPUTAÇÃO
BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO
SISTEMAS OPERACIONAIS
Professor: Dr. Josivaldo Araújo
josivaldo@ufpa.br
Objetivos desta Unidade...
� Discutir várias técnicas de gerenciamento de memória,
incluindo a Paginação e a Segmentação;
� Descrever os benefícios de um sistema de memória
virtual;
� Explicar os conceitos de Paginação por demanda,
algoritmos de substituição de páginas e alocação de
quadros de páginas;
� Propostas para reduzir a fragmentação;
� Permitir com que o sistema possa alocar estruturas e
dados maiores que a memória;
Introdução
� As estratégias de gerenciamento de memória utilizadas
possuem um único objetivo: manter simultaneamente
muitos processos em memória para permitir
multiprogramação;
� Algumas dessas estratégias tendem a exigir que o
processo inteiro esteja na memória antes que possa ser
executado;
� A memória virtual é uma técnica que permite a execução
de processos que não estão completamente em memória;
� Uma das principais vantagens desse esquema é que os
programas podem ser maiores do que a memória física
disponível;
Introdução
� A alocação estática de memória resulta no problema da
fragmentação interna, ou seja, os processos não ocupam
completamente a partição para a qual são alocados;
� A alocação dinâmica de memória, por outro lado, apresenta o
problema da fragmentação externa, ou seja, os processos vão
deixando espaços cada vez menores, após serem finalizados,
impossibilitando a alocação de outros processos maiores;
� Uma solução para a fragmentação externa é permitir que o
espaço de endereçamento lógico não seja contíguo,
possibilidade de alocar o processo onde exista memória
disponível;
� Duas técnicas complementares utilizam essa solução:
1. Paginação;
2. Segmentação
1. Paginação
� É uma técnica de gerenciamento de memória que permite
que o espaço de endereçamento físico de um processo não
seja contíguo;
� A paginação evita a fragmentação externa e a necessidade
de compactação;
� Tradicionalmente, o suporte à paginação tem sido
manipulado pelo hardware;
� Entretanto, projetos recentes têm implementado a
paginação integrando fortemente o hardware e o sistema
operacional, principalmente em microprocessadores de 64
bits;
1. Paginação – Método Básico
� Para implementar a paginação, a memória física é dividida em
blocos de tamanhos fixo chamados quadros;
� A memória lógica também é dividida em blocos do mesmo
tamanho chamados páginas;
� Quando um processo está para ser executado, suas páginas são
carregadas em quaisquer quadros de memória disponível;
� Cada endereço gerado pela CPU é dividido em duas partes: um
número de página (p) e um deslocamento de página (d);
� O número de página é usado como um índice em uma
tabela de páginas;
� A tabela de páginas contém o endereço base de cada página
na memória física;
� Esse endereço é combinado com o deslocamento de página
para definer o endereço de memória física;
1. Paginação – Método Básico
� O suporte de hardware à paginação é ilustrado abaixo:
� O tamanho da página (como o tamanho do quadro) é definido
pelo hardware;
� Normalmente, o tamanho de uma página é uma potência de
2, variando entre 512 bytes e 16 MB por página, dependendo
da arquitetura do computador;
1. Paginação – Método Básico
� A seleção de uma potência de 2 como tamanho de página torna
fácil a conversão de um endereço lógico em um número de
página e um deslocamento de página;
� Se o tamanho do espaço de endereçamento lógico é de 2m e o
tamanho da página é de 2n unidades de endereçamento (bytes
ou palavras), então:
� (m – n) bits, designam o número da página;
� n, designa o deslocamento da página;
p d
Número de página Deslocamento
m - n n
1. Paginação – Método Básico
Lógico (p) Físico (f)
0 1
1 4
2 3
3 7
Página 0
Página 1
Página 2
Página 3
0
1 Página 0
2
3 Página 2
4 Página 1
5
6
7 Página 3
Memória Lógica
Tabela de Página
Memória Física
Número do
quadro
� Modelo de paginação de memória
lógica e física.
1. Paginação – Método Básico
Tabela de Página
Memória Lógica Memória Física
� Exemplo prático:
� Endereço Lógico: n = 2 e m = 4;
� Tamanho da página: 4 bytes;
� Memória Física: 32 bytes (8 páginas);
1. Paginação – Método Básico
� Quando se usa paginação, não se tem fragmentação externa,
qualquer quadro livre pode ser alocado a um processo que
precise dele;
� No entanto, pode-se ter 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 poderá não ficar
completamente cheio;
� Esse aspecto sugere que são
desejáveis tamanhos de páginas
pequenos;
• O I/O do disco é mais eficiente
quando a quantidade de dados
que estão sendo transferidos é
maior;
• Hoje as páginas têm, tipicamente,
entre 4 KB e 8 KB;
1. Paginação – Método Básico
� Quando um processo chega ao sistema para ser executado,
seu tamanho, expresso em páginas, é examinado;
� Cada página do processo precisa de um quadro, ou seja, se o
processo tem n páginas, pelo menos n quadros devem estar
disponíveis na memória;
� A primeira página do processo é carregada em um dos
quadros alocados, e o número do quadro é inserido na tabela
de páginas desse processo. E isso é feito para todas as
páginas desse processo;
� A diferença entre a visão que o usuário tem da memória e a
memória física é reconciliada pelo hardware de tradução de
endereços;
� Os endereços lógicos são traduzidos para endereços
físicos;
2. Segmentação
� Os programas são divididos logicamente em sub-rotinas
e estruturas de dados e colocados em blocos de
informação (segmentos) na memória;
� Segmentos possuem tamanhos variáveis;
� Permite uma relação entre a lógica do programa e sua
divisão na memória;
� Os segmentos são numerados e referenciados por um
número de segmento. Assim, um endereço lógico
consiste em:
s d
Número de segmento Deslocamento
2. Segmentação
E.L Base Limite 
0 1400 1000
1 6300 400
2 4300 400
3 3200 1100
4 4700 1000
Tabela de
segmentos
� Por exemplo, o segmento 2 tem 400
bytes e começa na localização 4300.
� Referência ao byte 53 do segmento 2: é
mapeado para a localização 4353;
Memória Virtual
� Executar problemas maiores do que a memória física
disponível, é uma questão antiga;
� A solução geralmente adotada era dividir o programa em
módulos, denominados overlays (módulos de
sobreposição);
� No entanto, percebeu-se que o tamanho total do programa
podia exceder a quantidade de memória física disponível
para ele, mas tarde, essa técnica ficou conhecida como
Memória Virtual;
� Por essa técnica, o sistema operacional mantém as
partes ativas do programa na memória principal;
� E o restante, que não está sendo utilizado, armazenado
em disco;
Memória Virtual
� Técnica que combina as memórias principal e
secundária de forma que o usuário tenha a impressão de
que existe uma memória principal maior do que
realmente existe;
� Desvincula o endereçamento feito nos programas dos
endereços físicos da memória principal;
� Os programas e suas estruturas de dados não ficam
limitados ao tamanho da memória física disponível;
� Pode utilizar duas formas de divisão da memória:
� Paginação e Segmentação
Memória Virtual
� Endereço Virtual
� Abstração de endereço utilizada nos programas e na
referência a seus dados.
� Espaço de Endereçamento Virtual
� Conjunto de endereços virtuais que um processo pode
endereçar.
� Não tem nenhuma relação direta com os endereços do
espaço real.
� Programas muito maiores que a memória física podem
ser executados;
� Apenas parte dos programas fica residente na memória
principal;� As outras partes ficam em memória secundária, até
serem referenciadas;
� Transparente para o programador;
� O sistema operacional cuida dos detalhes de execução;
� A conversão do endereço virtual em endereço real é
realizada através de um mapeamento;
Memória Virtual - Características
Memória Virtual - Mapeamento
� Um endereço gerado pela CPU é normalmente chamado
de endereço lógico;
� Já um endereço reconhecido pela unidade de memória
(registrador de endereço de memória) é chamado de
endereço físico;
� Assim, no esquema de vinculação de endereços realizados
em tempo de execução, os espaços de endereçamento
lógico e físico diferem;
� O mapeamento em tempo de execução de endereços
virtuais em reais é feito por um dispositivo de hardware
chamado Unidade de Gerenciamento de Memória
(MMU-Memory Management Unit);
� Cada processo possui a sua própria tabela de
mapeamento.
� Um registrador aponta a tabela de mapeamento do
processo corrente.
� As tabelas mapeiam blocos de informações:
� Fixos (páginas) ou Variáveis (segmentos).
Memória Virtual - Mapeamento
Memória Virtual - Mapeamento
� Técnica onde o espaço de endereçamento virtual e o
espaço de endereçamento real são divididos em
blocos do mesmo tamanho (páginas).
� Mapeamento realizado através de tabelas de páginas.
� Cada entrada na tabela de página possui informações
que permitem ao sistema localizar a página real
(frame) correspondente.
� Quando o programa é executado, as páginas virtuais
são transferidas da memória secundária para o
quadro real correspondente na memória principal;
Memória Virtual por Paginação
Memória Virtual por Paginação
� Endereço virtual é formado pelo número da página
mais o deslocamento dentro da mesma;
Memória Virtual por Paginação
Página virtual
Deslocamento
Endereço virtual
Desloc.NPV
End. do frame
ETP
Tabela de páginas
End. do frame Desloc.
Frame
Deslocamento
Endereço físico
Memória Virtual por Paginação
� A entrada na tabela de páginas possui campos que
indicam se a página...
� ... já está na memória principal (bit de validade).
� ... foi alterada (para atualização no page out).
� ... foi referenciada.
Memória Virtual por Paginação
� Se a página referenciada estiver fora da memória
principal é gerada uma “falha de página” (page fault);
� Elevado número de falha de páginas (page fault) é
denominado de Thrashing;
Working Set
� É o conjunto de páginas do processo presentes na
memória num determinado instante;
� Os processos tendem a utilizar um pequeno conjunto de
páginas – Princípio da Localidade;
� O processador tenderá a concentrar suas referências a
um conjunto de páginas do processo, por um
determinado tempo;
� O working set surgiu com o objetivo de reduzir o
problema do thrashing e está relacionado ao princípio da
localidade;
� Existem dois tipos de localidade:
1. Espacial;
2. Temporal;
Working Set
2. Temporal;
� É a tendência de que após a referência a uma
posição de memória esta posição seja novamente
referenciada em um curto intervalo de tempo;
1. Espacial;
� É a tendência de que após
uma referência a uma
posição de memória, sejam
realizadas novas referências a
endereços próximos;
Políticas de Busca de Páginas
� Determina quando uma página deve ser carregada para
a memória;
A. Paginação por demanda
� As páginas são transferidas apenas quando
referenciadas.
B. Paginação antecipada
� É feita uma “previsão” de quais páginas serão
utilizadas e estas são carregadas previamente na
memória principal
Políticas de Alocação de Páginas
� Determina quantos frames um processo pode ter na
memória;
A. Alocação Fixa
� Cada processo tem um número máximo de frames
que pode ser utilizado durante a execução do
programa;
B. Alocação Variável
� O número máximo de páginas alocadas ao
processo pode variar durante sua execução em
função de sua taxa de paginação e da ocupação da
memória principal;
Políticas de Substituição de Páginas
� Determina quais os processos são candidatas a ter
páginas realocadas;
A. Substituição Local
� Apenas as páginas do processo que gerou o page
fault são candidatas à realocação;
B. Substituição Global
� Todas as páginas alocadas na memória principal
são candidatas à substituição, independente do
processo que gerou o page fault;
Algoritmos de Substituição de Páginas
� O maior problema na gerência de memória virtual por
paginação não é decidir quais páginas carregar para a
memória principal, mas quais liberar;
� Na necessidade de alocar uma nova página e não
existem frames disponíveis, o sistema deverá selecionar,
dentre as diversas páginas já alocadas, qual deverá ser
substituída;
� Os algoritmos de substituição de páginas têm o objetivo
de selecionar os frames que tenham as menores chances
de serem referenciados em um futuro próximo;
� Para isso, levam em consideração o princípio da
localidade e tentam prever o comportamento futuro das
aplicações em função do comportamento passado;
Algoritmos de Substituição de Páginas
� Para isso, os algoritmos avaliam: o número de vezes que
uma página foi referenciada; o momento em que foi
carregada para a memória principal e o intervalo de
tempo da última referência;
� Os principais algoritmos existentes para a substituição
de páginas são:
1. Ótimo;
2. Aleatório;
3. FIFO;
4. LFU (Least-Frequently-Used);
5. LRU (Least-Recently-Used);
6. NRU (Not-Recently-Used);
7. FIFO com buffer de Páginas
8. FIFO Circular (clock)
Algoritmos de Substituição de Páginas
1. Ótimo:
� Seleciona para substituição uma página que não será
mais referenciada no futuro;
� Aquela que levará o maior intervalo de tempo para
ser novamente utilizada;
� Na prática, é impossível de ser implementado;
2. Aleatório:
� Não utiliza critério algum de seleção;
� Todas as páginas alocadas na memória principal têm
a mesma chance de serem selecionadas;
� Consome poucos recursos do sistema;
� Raramente utilizada;
Algoritmos de Substituição de Páginas
3. FIFO (First-In-First-Out)
� A página que primeiro foi utilizada será a primeira a
ser escolhida, ou seja, seleciona a página que está a
mais tempo na memória principal;
� Implementação bastante simples (baseada em fila ou
se pode associar a cada página, o momento que foi
carregada na memória);
� Páginas constantemente acessadas acabam
retornando várias vezes;
Algoritmos de Substituição de Páginas
4. LFU (Least-Frequently-Used)
� Seleciona a página menos referenciada;
� É mantido um contador com o número de
referências para cada página na memória principal;
� A página que possui o contador com menor número
de referências será escolhida;
5. LRU (Least-Recently-Used)
� Seleciona a página que está há mais tempo sem ser
referenciada;
� Gera grande overhead, pois cada página tem que ser 
atualizada com o momento do último acesso;
6. NRU (Not-Recently-Used)
� Elimina a página não referenciada recentemente;
� Utiliza dois bits de estado, R (referenciada) e M
(modificada) para auxiliar na decisão de que página
deve ser substituída;
� Na ocorrência de uma falta de página, o S.O.
inspeciona todas as páginas, classificando-as em:
• Classe 0: não referenciada, não modificada (0,0);
• Classe 1: não referenciada, modificada (0,1);
• Classe 2: referenciada, não modificada (1,0);
• Classe 3: referenciada, modificada (1,1);
� A página na classe de menor valor é excluída;
Algoritmos de Substituição de Páginas Algoritmos de Substituição de Páginas
7. FIFO com Buffer de Páginas
� Combina uma lista de páginas alocadas (LPA) com
uma lista de páginas livres (LPL);
� A LPA organiza todas as páginas que estão sendo
utilizadas na memória principal (lista única ou
individual para cada processo);
� A LPA organiza as páginas alocadas há mais tempona memória no início da lista, e as mais recentes no
final;
� A LPL organiza todos os frames livres da memória
principal, sendo que as páginas livres há mais
tempo ficam no início e as mais recentes no final;
� Para liberar uma página, o algoritmo seleciona o
frame em uso há mais tempo na memória, ou seja, o
primeiro da LPA, colocando-o no final da LPL;
Algoritmos de Substituição de Páginas
7. FIFO com Buffer de Páginas
� A LPL funciona como um buffer de páginas,
evitando o acesso à memória secundária;
� Com o passar do tempo, a página se não mais for
referenciada, irá chegar no início da LPL, e será
substituída por outra página;
Algoritmos de Substituição de Páginas
8. FIFO Circular (Algoritmo da Segunda Chance)
� Utiliza como base o FIFO, porém as
páginas alocadas na memória estão
em uma estrutura de lista circular;
� O algoritmo implementa um
ponteiro que guarda a posição da
página mais antiga na lista;
� Cada página possui associado um
bit de referência, indicando se a
página foi recentemente
referenciada;
� Esse algoritmo é implementado,
com pequenas variações, nos
sistemas UNIX;
Translation Lookside Buffer
� A gerência de memória virtual utiliza a técnica de
mapeamento para traduzir endereços virtuais em reais;
� Como a maioria das aplicações referencia um número
reduzido de frames na memória principal, seguindo o
princípio da localidade, somente uma pequena fração da
tabela de mapeamento é realmente necessária;
� Foi introduzida uma memória especial chamada de
Translation Lookside Buffer (TLB) com o intuito de
mapear endereços virtuais em físicos sem a necessidade
do acesso à tabela de páginas;
� O TLB funciona como uma cache, mantendo apenas as
traduções dos endereços virtuais das páginas mais
recentemente referenciadas;
Translation Lookside Buffer
Translation Lookside Buffer
� Como a TLB pode eliminar o acesso à tabela de
mapeamento, as informações de um endereço virtual
contidas na entrada da tabela de páginas devem também
estar na cache;
� A TLB contém apenas informações sobre endereços do
processo em execução, ou seja, quando houver mudança
de contexto a TLB deve ser reinicializada com informações
da tabela de mapeamento do novo processo;
Proteção de Memória - Paginação
� Um primeiro nível de proteção, cada processo tem a sua
própria tabela de mapeamento e a tradução dos endereços
é realizada pelo sistema;
� A proteção de acesso é realizada individualmente em cada
página da memória principal, utilizando-se as entradas
das tabelas de mapeamento, onde bits especificam os
acessos permitidos;
Compartilhamento de Memória - Paginação
� Basta que as entradas das
tabelas de mapeamento dos
processos apontem para os
mesmos frames;
� Evita várias cópias de um
mesmo programa na
memória;
� É importante em aplicações
que compartilham dados
na memória principal;
� Garantir o sincronismo;
Memória Virtual por 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 alocadas em segmentos na
memória principal;
� O tamanho do segmento pode ser alterado durante a
execução do programa;
� O mecanismo de mapeamento
é muito semelhante ao de
paginação;
Memória Virtual por Segmentação
� Os segmentos são mapeados
através de tabelas de mapeamento
de segmentos (TMS);
� Endereços são compostos pelo
número do segmento virtual (NSV)
e por um deslocamento;
� O NSV identifica unicamente o
segmento virtual que contém o
endereço, funcionando com um
índice na TMS;
� O deslocamento indica a posição
do endereço virtual em relação ao
início do segmento no qual se
encontra;
Memória Virtual por Segmentação
� A grande vantagem da segmentação em relação à
paginação é a sua facilidade em lidar com estruturas de
dados dinâmicos;
� Cada ETS possui, além do endereço virtual do segmento
na memória principal, informações adicionais;
� Mecanismo para Escolha de Área Livre:
� Sistema mantém uma tabela com todas as áreas livres e
ocupadas na memória principal;
� Podem ser utilizados os mesmos mecanismos de
Alocação Particionada Dinâmica:
• Best-fit
• Worst-fit
• First-fit
Memória Virtual por Segmentação Memória Virtual por Segmentação com Paginação
Endereço do frame Deslocamento
Deslocamento
Num.
segmento
Num.
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
� O sistema trata cada
segmento como um
conjunto de páginas de
mesmo tamanho;
� O endereço virtual é
formado pelo número do
segmento virtual (NSV), um
número de página virtual
(NPV) e um deslocamento;
� Através do NSV, obtém-se
uma entrada na tabela de
segmentos, que contém
informações da tabela de
páginas do segmento;
Swapping em Memória Virtual Thrashing
� Pode ser definido como sendo a excessiva transferência de
páginas/segmentos entre a memória principal e a
memória secundária;
� Problema presente em sistemas que utilizam tanto a
paginação quanto segmentação;
� Na memória virtual por paginação e segmentação, o
thrashing ocorre em dois níveis:
A. No próprio processo;
B. No sistema;
Thrashing
A. No próprio processo:
� A excessiva paginação ocorre devido ao elevado
número de page fault, gerado pelo programa em
execução;
� Faz com que o processo passe mais tempo
esperando por páginas que realmente em execução;
B. No sistema:
� Ocorre quando existem mais processos competindo
por memória principal que espaço disponível;
• Redução do número de páginas de cada processo,
pode levar ao thrashing do processo;
• Caso a redução não seja suficiente, o sistema inicia o
swapping;
Conclusão
� A memória virtual é uma técnica que nos permite mapear
um grande espaço de endereçamento lógico em uma
memória física menor;
� A memória virtual pode ser implementada utilizando as
técnicas de paginação e segmentação;
� Comparando essas técnicas, tem-se: