Sistemas Operacionais
Prof.: Filipe T. Marques
[email protected]
UNIPÊ
O professor Gustavo Wagner
(www.gustavowagner.com) também fez
adaptações sobre os slides originais
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
1
Capítulo 4
Gerenciamento de Memória
4.1 Gerenciamento básico de memória
4.2 Troca de processos
4.3 Memória virtual
4.4 Algoritmos de substituição de páginas
4.6 Questões de projeto para sistemas de paginação
4.7 Questões de implementação
4.8 Segmentação
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
2
Algoritmos de Substituição de
Páginas
• A falta de página força uma escolha
– qual página deve ser removida
– alocação de espaço para a página a ser trazida
para a memória
• A página modificada deve primeiro ser salva
– se não tiver sido modificada é apenas sobreposta
• Melhor não escolher uma página que está
sendo muito usada
– provavelmente precisará ser trazida de volta logo
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
3
Algoritmo de Substituição de
Páginas Ótimo
• Se uma página foi acessada há 10000
instruções, e outra há 5000, a primeira deve
ser substituída numa falta de página;
• Problema: não há como o SO saber quando
uma página será novamente acessada;
• E se a próxima instrução for para acessar a
primeira página citada acima?
• Algoritmo impossível de ser implementado;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
4
O Algoritmo de Substituição de Página
Não Usada Recentemente (NUR)
•
Cada página tem os bits Referenciada (R) e
Modificada (M)
– Bits são colocados em 1 quando a página é
referenciada e modificada
•
As páginas são classificadas, pelo SO




•
Classe 0: não referenciada, não modificada
Classe 1: não referenciada, modificada
Classe 2: referenciada, não modificada
Classe 3: referenciada, modificada
NUR remove página aleatoriamente
– da classe de ordem mais baixa que não esteja vazia
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
5
O Algoritmo de Substituição de Página
Não Usada Recentemente (NUR)
• É melhor remover uma página modificada,
mas que não foi referenciada;
• Algoritmo fácil de entender e implementar;
• Desempenho não é ótimo, mas adequado;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
6
Algoritmo de Substituição de Página
Primeira a Entrar, Primeira a Sair
• Imagine retirar um produto de um supermercado,
dado que um novo chegou, e não tem mais
espaço nas prateleiras;
• O supermercado mantém uma lista de todos os
produtos, por ordem de chegada;
• Deve-se retirar o produto estocado a mais tempo;
• Se o produto retirado for cera para bigode, ok;
• Mas e se for açúcar?
• Situação análoga a FIFO;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
7
Algoritmo de Substituição de Página
Primeira a Entrar, Primeira a Sair
• Mantém uma lista encadeada de todas as
páginas
– página mais antiga na cabeça da lista
– página que chegou por último na memória no final
da lista
• Na ocorrência de falta de página
• página na cabeça da lista é removida
• nova página adicionada no final da lista
• Desvantagem
– página há mais tempo na memória pode ser
usada com muita freqüência
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
8
Algoritmo de Substituição de Página
Segunda Chance (SC)
• Modificação de FIFO;
• Desta vez, se o bit R for 1, a página será poupada,
o bit R é colocado em 0 e a página vai para o final
da fila;
• Se não, a página será removida;
• Dá-se chance às páginas que estão sendo
utilizadas, mesmo sendo antigas;
• Se todas as páginas forem referenciadas, o
algoritmo degenera-se para FIFO;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
9
Algoritmo de Substituição de Página
Segunda Chance (SC)
•
Operação do algoritmo segunda chance
a)
b)
lista de páginas em ordem FIFO
estado da lista em situação de falta de página no instante 20,
com o bit R da página A em 1 (números representam instantes
de carregamento das páginas na memória)
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
10
Algoritmo de Substituição
de Página Relógio
• Difere-se do Segunda Chance apenas na
implementação;
• O SC é desnecessariamente ineficaz, já que
coloca constantemente no final da fila de
páginas;
• O Relógio cria simplesmente uma lista
circular;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
11
Algoritmo de Substituição
de Página Relógio
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
12
Menos Recentemente
Usada (MRU)
• Aproximação do desempenho teórico do algoritmo
ótimo;
• Assume que páginas usadas recentemente
logo serão usadas novamente
– retira da memória página que há mais tempo não
é usada
• Implementação por SW muito onerosa, pois
tem-se que atualizar uma lista encadeada;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
13
Menos Recentemente
Usada (MRU)
• Uma lista encadeada de páginas deve ser mantida
– página mais recentemente usada no início da lista, menos
usada no final da lista
– atualização da lista à cada referência à memória
• Implementação por HW:
– Contador de 64 bits, que é incrementado a cada instrução
– Mantem-se contador em cada entrada da tabela de página
– escolhe página com contador de menor valor
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
14
Menos Recentemente
Usada (MRU)
• Outra maneira em HW:
– Para uma máquina com n molduras, gera-se
matriz de n x n, inicialmente com todos os
valores 0;
– Sempre que a moldura k for referenciada, o
HW marcará os bits da linha k com 1, e todos
os bits da coluna k com 0;
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
15
Menos Recentemente
Usada (MRU)
MRU usando uma matriz – páginas referenciadas
na ordem 0,1,2,3,2,1,0,3,2,3
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
16
Simulação do MRU em Software
• Embora implementações anteriores sejam
realizáveis, não há máquinas com o HW
descrito;
• Usa-se o algoritmo do envelhecimento:
– Coloca-se o bit R no bit mais à esquerda do
contador, a cada tic;
– Desloca-se à direita todos os bits
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
17
Simulação do MRU em Software
• O algoritmo do envelhecimento (aging) simula o MRU
em software
• Note 6 páginas para 5 tiques de relógio, (a) – (e)
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
18