Disciplina: Sistemas Operacionais - CAFW-UFSM
Professor: Roberto Franciscatto
Introdução
• Técnica onde memória principal e
secundária são combinadas de
forma a “emular” uma memória de
tamanho maior que a memória
principal (real);
• Não vincula o endereçamento
dos programas aos endereços
físicos da memória principal;
• Programas não ficam mais
• A memória secundária é usada
como extensão da memória
principal;
limitados ao tamanho da
memória principal disponível;
• Minimiza o problema de
• Permite um maior número de
processos compartilhando a
memória principal;
fragmentação.
Memória Virtual
Espaço de Endereçamento:
Memória Principal
Espaço de
Endereçamento Real
Estrutura Vetorial
Mapeamento
Memória
Secundária
Memória Virtual
• Mapeamento:
• Realizado por hardware
e sistema operacional
nos sistemas atuais,
através da MMU
(Memory Management
Unit - Unidade de
Gerenciamento de
Memória).
• Cada processo com uma
tabela de mapeamento
própria.
• No momento da execução, o
endereço virtual é mapeado
para o endereço físico, pois o
processador só acessa
endereços do espaço real;
• Nas trocas de contexto, um
registrador é responsável por
indicar qual a tabela que deve
ser utilizada.
Memória Virtual
• Memória Virtual por Paginação:
• Memória Virtual e Real
divididas em blocos de
mesmo tamanho
(páginas);
• As tabelas de páginas
mapeiam os blocos de
informações:
• Quanto maior o bloco, menor
o tamanho das tabelas;
• Quanto maior o bloco, maior
• Páginas virtuais;
• Páginas reais ou frames;
o tempo de transferência do
bloco entre memória
principal e secundária.
Memória Virtual
Memória Principal
Espaço de
Endereçamento Real
Paginação:
Memória Virtual
Espaço Virtual
do Processo A
Espaço Virtual
do Processo B
Tabela de
Páginas de A
Tabela de
Páginas de B
Memória
Page In
Secundária
Page Fault
Memória Virtual
• Memória Virtual por Paginação:
• Endereço Virtual = Nº
da página virtual +
deslocamento;
• Um bit de validade (na
tabela de páginas)
indica se a página já se
encontra na memória
principal ou não.
•
Taxa de Paginação = Nº de Page
Fault em um intervalo de tempo.
•
Quando ocorre um page fault, o
processo em questão passa ao
estado de espera.
Memória Virtual
Memória Virtual
Endereçamento Virtual:
Memória Principal
Espaço de
Endereçamento Real
Espaço Virtual
do Processo A
Página virtual
1
...
2
deslocamento
203
...
067
Tabela de
Páginas de A
Validade
1
0
End. do Frame
2
2 64 4096
Endereço
Físico
2
203
Memória
Secundária
Page In
Políticas de Busca de Páginas
• Determinação de quando uma
página deve ser carregada para a
memória.
• Paginação por
demanda:
•
Paginação antecipada:
• Além da página referenciada,
são carregadas outras páginas
que também podem (ou não)
ser referenciadas futuramente.
• Economia de tempo na cópia
• Transferência de páginas
para memória principal
quando são referenciadas.
do conjunto de páginas.
• Risco de trabalho
desnecessário.
• Apenas as páginas
necessárias são
transferidas.
Políticas de Alocação de Páginas
• Determina quantos frames cada
processo pode manter na
memória principal.
•
Limite de páginas mal
dimensionado:
• Se for pequeno:
• Alocação Fixa:
• Número máximo de
frames (páginas) por
processo.
• Caso o limite seja
atingido, alguma página
deve ser descartada.
• O limite de páginas é
determinado na criação
do processo.
• Muitos page faults;
• Degradação do sistema;
• Se for grande:
• Espaço ocupado maior que
o necessário;
• Reduz o grau de
multiprogramação.
Políticas de Alocação de Páginas
• Alocação Variável:
• O número máximo de
frames de um processo
pode variar em função
de sua taxa de
paginação.
• Processos com alta taxa
de paginação podem
aumentar o seu limite
máximo de frames.
• Processos com baixa taxa
de paginação podem ter os
seus limites máximos de
frames reduzido.
Políticas de Substituição de Páginas
• Seleção de qual, entre as
diversas páginas alocadas deve
ser liberada.
• Necessidade de verificação se a
página foi alterada (bit de
modificação)
• No caso da página liberada
tiver sofrido modificação, esta
deverá antes ser gravada no
Arquivo de Paginação (page out).
• Note que as páginas de
código não podem ser
modificadas, logo não
sofrem page out.
Políticas de Substituição de Páginas
• Política de Substituição Local:
• Apenas as páginas do
processo que gerou o
page fault são
candidatas à
relocação.
• Política de Substituição Global:
• Todas as páginas de
todos os processos são
candidatas à
relocação.
• Algumas páginas nunca
são candidatas à relocação,
como por exemplo as do
núcleo do S.O.
Políticas de Alocação x Políticas de Substituição
• Relacionamento entre as
Políticas de Alocação e Políticas
de Substituição de páginas.
• Alocação Variável:
• Substituição Global.
• Substituição Local.
• Alocação Fixa:
• Substituição Local.
• O SO avalia a taxa de
paginação de um processo
e altera o seu limite
máximo de frames.
Working Set
• Conjunto das páginas
referenciadas por um processo
em um determinado intervalo de
tempo.
• Princípio da localidade
• Localidade Espacial:
• Após a referência à um
endereço, existe a
tendência à serem
feitas referências à
endereços próximos.
• Localidade Temporal:
• Após a referência à um
endereço, existe a tendência
à serem feitas referências ao
mesmo endereço em um
curto intervalo de tempo.
• Para programas
desenvolvidos utilizando
técnicas estruturadas, o
princípio da localidade é
quase sempre válido.
Working Set
• Exemplo:
• Períodos de alta taxa de
paginação, intercalados por
períodos de estabilidade.
• Trashing: Problema provocado
quando um processo possui um
número insuficiente de frames na
memória, resultando em uma
alta taxa de paginação.
Páginas de
um Processo
Pagina 1
Pagina 2
Pagina 3
Pagina 4
Pagina 5
Pagina 6
Pagina 7
Pagina 8
Working Set
Algoritmos de Substituição de Páginas
• Seleção do frame com a menor
chance de ser referenciado.
• Principais algoritmos de
substituição de páginas:
• Ótimo:
• Hipotético;
• Somente para efeito
de avaliação de outros
algoritmos.
• Aleatório:
• Escolhe uma página
qualquer do working set,
sem critério;
• Qualquer página tem a
mesma chance de ser
escolhida;
• Pouco Eficiente.
Algoritmos de Substituição de Páginas
• First-In-First-Out (FIFO):
• A página que estiver
há mais tempo na
memória será a
próxima página a ser
escolhida para sair do
Working Set;
• Implementado por
uma fila FIFO;
• Pode ser desvantagem
para:
• Caso de haver loops
(página constantemente
referenciada, que foi
carregada no início);
• Caso de utilitários do
sistema operacional que
são constantemente
utilizados.
Algoritmos de Substituição de Páginas
• Least-Recently-Used (LRU):
• Boa estratégia, mas gera
muito overhead:
• Seleciona a página há
mais tempo sem ser
referenciada;
• Devido à necessidade de
atualizar o momento do
último acesso, de cada
página referenciada;
• Devido à complexidade do
algoritmo de busca destas
páginas
Algoritmos de Substituição de Páginas
• Not-Recently-Used (NRU):
• Seleciona páginas não
usadas recentemente;
• Inicialmente todas as
páginas estão com Flag = 0
indicando que ainda não
foram acessadas;
• Um Flag de referência
• À medida que forem sendo
é associado a cada
entrada na tabela de
páginas e indica se a
página foi
referenciada ou não;
• Depois de um certo tempo
referenciadas o Flag é
modificado pelo hardware;
pode-se saber que páginas
não foram referenciadas.
Algoritmos de Substituição de Páginas
• Least-Frequently-Used (LFU):
• A página menos
referenciada é
selecionada;
• Um contador controla o
número de referências
feitas a cada página;
• Será selecionada a
página com o menor
contador;
• Problema:
• As páginas que entraram
mais recentemente no
Working Set terão maior
probabilidade de serem
selecionadas.
Algoritmos de Substituição de Páginas
FIFO com Buffer de páginas:
Lista de Páginas Livres
início
fim
Página
Referenciada
Página
Liberada
início
fim
Lista de Páginas Alocadas
Algoritmos de Substituição de Páginas
• FIFO Circular (CLOCK):
• Combinação de uma
Br=1
lista circular com um
bit de referência.
Br=0
Br=0
Br=1
Br=0
• Caso Br=1,
incrementa o ponteiro;
BR=0.
Br=0
• Caso BR=0,
A página
é selecionada.
Segmentação
• Técnica de gerência de
memória onde os processos são
divididos logicamente em:
• Blocos de sub-rotinas;
• Blocos de estruturas
de dados.
• Cada bloco possui um tamanho
diferente e é chamado de
Segmento;
• Existe uma relação direta
entre a lógica do programa
e divisão em segmentos.
Segmentação
Memória principal
Programa Segmento;
Var A: array...
C: ...
Procedimento X;
...
End;
Function Y;
...
End;
Begin
...
End.
S.O.
Procedimento X
Programa Principal
Função Y
Array A
programa A
Variável C
...
Segmentação
• A Segmentação possui
funcionamento análogo à
Paginação.
• O Endereço virtual é
formado pelo:
• Número do segmento;
• Mapeamento:
• Os segmentos são
mapeados através da
tabela de mapeamento
de segmento (TMS);
• Deslocamento dentro do
segmento;
Segmentação com Paginação
• Técnica onde os processos são
divididos logicamente em
Segmentos e cada segmento é
dividido fisicamente em Páginas.
• Endereço virtual é formado
por:
• Número do segmento;
• Número de página dentro do
segmento;
• Deslocamento dentro da
página.
Compartilhamento de Memória
• Código reentrante:
• Código único,
compartilhado por
diversos usuários.
• Sistemas com memória virtual:
• As tabelas de
páginas/segmentos de
processos distintos,
apontam para os
mesmos frames na
memória principal.
• Benefício:
• Utilização mais eficiente da
memória, permitindo que
mais usuários utilizem o
recurso.
Compartilhamento de Memória
• No compartilhamento, técnica
da segmentação leva vantagem
em relação à paginação pois:
• O compartilhamento é
de segmentos
(compartilhamento
lógico);
• Cada processo possui
segmentos próprios,
com suas respectivas
estruturas de dados.