5 - Gerencia de memória virtual

Prévia do material em texto

1 
SISTEMAS 
OPERACIONAIS 
 
 
Memória Virtual 
 
Prof. Mateus Novaes 
(Adaptação dos slides de Silberschatz) 
SUMÁRIO 
 Fundamentos 
 Paginação em demanda 
 Substituição de página 
 Alocação de quadros 
 Thrashing 
 
 
 
2 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
 FUNDAMENTOS 
 Utilizado com a separação da memória física da 
memória lógica 
 Somente parte dos programas precisam estar na 
memória principal 
 Espaço de endereçamento lógico pode ser bem maior do que 
o físico 
 Um paginador é utilizado para colocar na memória 
somente as páginas que o processo vai utilizar 
 Utiliza-se um paginador (pager) em vez de swapper 
 Uma memória virtual pode ser implementada com: 
 Paginação sob demanda 
 Segmentação sob demanda 
3 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
 FUNDAMENTOS 
4 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
PAGINAÇÃO SOB DEMANDA 
 É utilizado um esquema de carregamento de 
paginas preguiçoso 
 
 Páginas só são carregadas quando requisitadas 
 Menor uso de E/S 
 Menor uso de memória 
 Resposta mais rápida 
 Mais usuários podem utilizar o sistema 
 
5 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
PAGINAÇÃO SOB DEMANDA 
6 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
PAGINAÇÃO SOB DEMANDA 
 Existe a necessidade de saber se a página está na 
memória ou no disco 
 O bit de validade contido na tabela de página 
pode ser utilizado para este fim 
 O bit válido indica que a 
página está na memória 
 O bit inválido indica que a 
página está no disco ou 
ocorreu um “page fault” 
 
7 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
1 
1 
1 
1 
0 
0 
0 
... 
Frame # valid-invalid bit 
page table 
 
MEMÓRIA VIRTUAL 
PAGINAÇÃO SOB DEMANDA 
8 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
 A falta da página (page fault) gera um trap, 
passando o controle ao S.O. 
1. Verifica-se se o acesso é válido ou não 
 Page fault ou violação de acesso 
2. Se o acesso for indevido termina o processo 
3. Busca um quadro livre 
4. Escalona uma operação para ler a página no quadro 
5. Modifica a tabela para indicar para o quadro 
6. Reinicia a instrução 
 
9 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
10 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
 Em algumas situações pode não existir quadros 
de memória livre para carregar a página 
 
 Solução: Substituição de página 
 Encontrar um página pouco utilizada para trocar 
 Utiliza um algoritmo de seleção de vítima 
 
11 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
12 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
 A substituição gera duas cópias 
 Um carregamento e um descarregamento 
 
 Um bit de modificação pode ser utilizado para 
diminuir a quantidade de E/S 
 
 Somente páginas modificadas são descarregadas 
13 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
14 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
 A escolha da página a ser descarregada exige a 
adoção de um algoritmo de substituição 
 
 Existem diversos algoritmos e um critério de 
seleção normalmente utilizado é a taxa de falta 
de página 
 
 A avaliação de um algoritmo de substituição é 
feita com o uso de uma string de referencia 
 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. 
 
 
15 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
16 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
 FIFO 
 3 quadros 
 
 
 
 
 
 4 quadros 
 
 
 
 
 
 
 
 Belady’s Anomaly: A quantidade de faltas de página pode 
aumentar com o aumento da quantidade de quadros 
 
 
 
17 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
1 
2 
3 
5 
10 page faults 
4 
2 
1 
3 
4 
5 
1 
2 
3 
4 
9 page faults 
2 
1 
5 
3 
4 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
18 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 FIFO 
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
19 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 FIFO 
 
 Algoritmo ótimo 
 Trocar a página que será utilizada mais tardiamente 
possível 
 4 quadros 
 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 
 
 
 
 
 
 
 
 Algoritmo base para comparação 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
20 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
1 
2 
3 
4 
6 page faults 
4 5 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
21 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Algoritmo ótimo 
 
 Algoritmo LRU 
 Trocar a página que não foi utilizada por mais tempo 
 String de referência: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 
 MRU – Menos Recentemente Utilizado 
 
 
 
 
 
 
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
22 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 1 
2 
3 
5 
4 
4 3 
5 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
23 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Algoritmo LRU 
 
 Duas implementações são possíveis para 
determinar a última página utilizada: 
 Contadores: 
 A CPU utiliza um contador incrementado a cada referencia 
de memória. 
 Cada página acessada guarda o valor deste contador. 
 Pilha: 
 É criada uma pilha de páginas acessadas 
 Cada página acessada é colocada no topo da pilha, assim a 
última página na pilha será a última página utilizada 
 Atualizações a cada acesso geram grande sobrecarga, 
por isso a necessidade de assistência de hardware 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
24 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
 Algoritmo LRU 
 
25 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Aproximações do algoritmo LRU 
 Uso de um suporte de hardware chamado bit de 
referencia 
 
 Assim existe um bit associado a cada página que é 
definido como 1 a cada referencia a página 
 
 Não é possível saber a ordem de acesso, mas sabe-se 
quais páginas foram utilizadas e quais não foram 
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
26 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Aproximações do algoritmo LRU 
 Pode-se obter informações adicionais guardando na 
memória 1 byte para guardar os últimos bits de 
referencia de cada página 
 O S.O. periodicamente lê os bits e coloca na posição maissignificativa dos bytes de cada página 
 Ex: A página com o byte 10001000 foi mais recentemente 
utilizada que a página com o byte 01110111 
 Segunda chance 
 Utiliza-se o algoritmo FIFO, mas se o bit de referencia for 1 
é dada uma nova chance a essa página. 
 Quando obtiver uma segunda chance o bit é zerado 
 
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
27 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
28 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Algoritmo de contagem 
 Cada acesso a página é contada e guardada 
 LFU (Least frequently Used) – A página com menor 
quantidade de acesso deve ser removida primeiro 
 Problema de páginas muito acessadas que não serão mais 
utilizadas 
 MFU (Most Frequently Used) – A página com maior 
contagem deve ser substituída. 
 Ela possivelmente acabou de chegar e deverá ser utilizada 
logo. 
 
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
29 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Algoritmo do buffer de páginas 
 Manter um pool de quadros livres 
 Numa falta um quadro destes é utilizado antes de 
proceder a gravação da página vítima 
 A página vítima é depois gravada e colocada na lista 
de quadros livres 
 Quando o dispositivo de paginação estiver ocioso 
 Uma variação guarda a página que era associada a 
este quadro 
 Se ela for requisitada mais tarde será retirada da lista sem 
haver substituição 
 
 
MEMÓRIA VIRTUAL 
SUBSTITUIÇÃO DE PÁGINA 
30 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Cada processo precisa de número mínimo de 
quadros 
 
 A depender de como o S.O. distribuí os quadros 
para os processos podemos ter: 
 Alocação fixa: Pode ser utilizada uma solução 
igualitária ou proporcional 
 Alocação por prioridade: Adota a prioridade como 
critério para distribuir os quadros 
 
MEMÓRIA VIRTUAL 
ALOCAÇÃO DE QUADROS 
31 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Alocação fixa: 
 Igualitária: Processos recebem a mesma quantidade 
de quadros 
 100 quadros e 5 processos = 20 quadros por processo 
 Proporcional: Alocação é de acordo com o tamanho do 
processo 
 
 
MEMÓRIA VIRTUAL 
ALOCAÇÃO DE QUADROS 
32 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
m
S
s
pa
m
sS
ps
i
ii
i
ii





 para Alocação 
quadros de totalNúmero 
 processo do Tamanho 
5964
137
127
564
137
10
127
10
64
2
1
2
1





a
a
s
s
m
 Alocação por prioridade 
 Usa o esquema de alocação proporcional, com a 
prioridade no lugar do tamanho do processo 
 É possível utilizar o tamanho e a prioridade juntos 
 
 Alocação global versos local 
 Alocação global: Os processos selecionam para troca 
quadros de qualquer processo 
 
 Alocação local: Os processos só podem escolher dentre 
suas próprias páginas 
 
 
MEMÓRIA VIRTUAL 
ALOCAÇÃO DE QUADROS 
33 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Se um processo não tem o mínimo de páginas 
necessário, sua taxa de falta de página cresce 
muito 
 Baixa utilização da CPU 
 O S.O. pode pensar então em aumentar o grau de 
multiprogramação 
 Acrescentar um novo processo a lista de processos prontos 
 
 É dito que um processo está no estado de 
thrashing quando gasta mais tempo paginando 
do que executando 
 
 
MEMÓRIA VIRTUAL 
THRASHING 
34 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
THRASHING 
35 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Para não ocorrer thrashing o processo precisa 
obter uma quantidade mínima de quadros 
 
 Como saber qual a quantidade de quadros 
suficientes para um processo? 
 Conjunto de trabalho 
 Freqüência de falta de páginas 
 
MEMÓRIA VIRTUAL 
THRASHING 
36 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Conjunto de trabalho 
 Define um modelo de localidade da execução de um 
processo 
 Um processo se move de uma localidade para outra 
durante sua execução 
 Várias etapas de processamento 
 
 
MEMÓRIA VIRTUAL 
THRASHING 
37 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 
MEMÓRIA VIRTUAL 
THRASHING 
38 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Conjunto de trabalho 
 Definir o conjunto de trabalho de um processo 
 Analisar os últimos quadros utilizados 
 Qual o range deve ser utilizado 
 
MEMÓRIA VIRTUAL 
THRASHING 
39 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is
 
 Frequencia de Falta de páginas 
 Estipula um limite para a taxa de falta de páginas 
 Se a taxa do processo passa do limite superior 
 O processo ganha mais quadros 
 Se a taxa do processo cai do limite inferior 
 O processo perde quadros 
 
MEMÓRIA VIRTUAL 
THRASHING 
40 
S
is
te
m
a
s
 O
p
e
r
a
c
io
n
a
is