Sistemas Operacionais

1Pearson Education Sistemas Operacionais Modernos – 2ª Edição

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


Gerenciamento de Memória

Capítulo 4

4.1 Gerenciamento básico de memória4.2 Troca de processos4.3 Memória virtual4.4 Algoritmos de substituição de páginas4.6 Questões de projeto para sistemas de paginação4.7 Questões de implementação4.8 Segmentação


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


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;


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


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;


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;


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


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;


Algoritmo de Substituição de Página Segunda Chance (SC)

• Operação do algoritmo segunda chancea) lista de páginas em ordem FIFOb) 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)


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;


Algoritmo de Substituição de Página Relógio


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;



• 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



• 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;



MRU usando uma matriz – páginas referenciadas na ordem 0,1,2,3,2,1,0,3,2,3


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


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)

Documents

Sistemas Operacionais