Gerenciamento de Memória - Parte III

Prévia do material em texto

Sistemas Operacionais
Gerenciamento Básico de Memória
Parte II
Prof. Sílvio Fernandes
UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO
DEPARTAMENTO DE CIÊNCIAS EXATAS E NATURAIS
CURSO DE CIÊNCIA DA COMPUTAÇÃO
Algoritmos de substituição de páginas
 Quando um falta de página ocorre, o SO precisa 
escolher uma página a ser removida da memória a 
fim de liberar espaço para uma nova a ser trazida.
 Se a pág. a ser removida tiver sido modificada 
enquanto esteve na memória, ela deverá ser 
reescrita no disco (atualizando a cópia virtual lá 
existente)
 A página a ser trazida sobrescreve a página que 
está sendo destituída
 Caso contrário, não é necessário reescrevê-la
2
Algoritmos de substituição de páginas
 Embora seja possível escolher aleatoriamente uma 
pág. a ser descartada a cada falta de pág., o 
desempenho do sistema será muito melhor se a 
pág. escolhida for uma que não estiver sendo 
muito usada
3
Algoritmos de substituição de páginas
 Uma questão importante
 Quando uma pág. vai ser removida, devemos 
remover do próprio processo que causou a falta ou 
podemos remover de outro?
 Algoritmos
 Ótimo
 Não usada recentemente (NUR)
 Primeira a entrar, primeira a sair
 Segunda chance (SC)
 Relógio
 Menos recentemente usada (MRU)
4
Algoritmos de substituição de páginas
 Ótimo
 O melhor dos algoritmos é fácil de descrever mas 
impossível de implementar
 Cada página pode ser rotulada com o número de 
instruções que serão executadas antes de aquela 
pág. ser referenciada pela primeira vez
 O algoritmo diz que deve se remover a pág. com 
maior rótulo
 Adia a ocorrência da próxima falta o máximo 
possível
 O único problema: é irrealizável
 Na falta e pág. o SO não tem como saber quando 
cada uma das pág. será referenciada novamente
5
Algoritmos de substituição de páginas
 Não usada recentemente (NRU)
 NRU (Not Recently Used)
 Quando um processo é iniciado os bits R
(referenciada) e M (modificada) são colocados em 0
para todas as páginas
 Periodicamente, o bit R é limpo de modo que 
diferencie as pág. que não foram referenciadas 
recentemente daquelas que foram
 Quando acontece uma falta de página, o SO 
inspeciona todas as páginas e as separa em quatro 
categorias, com base nos bits R e M
6
Algoritmos de substituição de páginas
 Não usada recentemente (NRU)
 Bit R Bit M
 Classe 0: não referenciada, não modificada
 Classe 1: não referenciada, modificada
 Classe 2: referenciada, não modificada
 Classe 3: referenciada, modificada
 O algoritmo remove aleatoriamente uma página de 
classe de ordem mais baixa que não esteja vazia
7
Algoritmos de substituição de páginas
 Primeira a entrar, primeira a sair
 FIFO é um algoritmo de baixo custo
 O SO mantém uma lista de todas as pág. atuais na 
memória, com a pág. mais antiga na cabeça da lista 
e a pág. que chegou mais recentemente situada no 
final dessa lista
 Na ocorrência de uma falta de pág., a 1ª pág. da 
lista é removida e a nova é adicionada no final
 Desvantagem: página há mais tempo na memória 
pode ser usada com muita frequência
8
Algoritmos de substituição de páginas
 Segunda Chance (SC)
 Uma modificação simples no FIFO evita o problema 
de se jogar fora uma pág. intensamente usada, 
simplesmente inspecionando o bit R da página mais 
antiga
 Se o bit R for 0, essa pág., além de mais antiga, não 
estará sendo usada, de modo que será substituída 
imediatamente
 Se for 1, será colocado em 0, e essa pág. será posta 
no final da lista como se ela tivesse acabado de ser 
carregada na memória
 A pesquisa continua
9
Algoritmos de substituição de páginas
 Segunda Chance (SC)
a) lista de páginas em ordem FIFO
b) 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)
10
Algoritmos de substituição de páginas
 Relógio
 SC é razoável e desnecessariamente ineficaz, pois 
permanece constantemente reinserindo pág. no final 
da lista
 Uma estratégia melhor é manter todas as pág. em 
uma lista circular em forma de relógio
 Um ponteiro aponta para a pág. mais antiga, ou seja, 
para a ‘cabeça’ da lista
 A lógica é a mesma da segunda chance
11
Algoritmos de substituição de páginas
 Relógio
12
Algoritmos de substituição de páginas
 Menos recentemente usada (LRU)
 LRU (Least Recenbly Used)
 Desempenho teórico do algoritmo ótimo baseia-se 
na observação de que páginas referenciadas 
intensamente nas últimas instruções provavelmente 
serão de novo referenciadas nas próximas instruções
 De modo oposto, é provável que pág. não foram 
referenciadas nas últimas instruções não o sejam nas 
próximas
 A implementação é possível mas onerosa
13
Algoritmos de substituição de páginas
 Menos recentemente usada (LRU)
 Possuir um hardware especial que incrementa um 
valor automaticamente a cada instrução executada
 A cada entrada da tabela de pág. deve ter um 
campo extra para armazenar o valor do contador
 Após cada referência a memória, o valor do 
contador é armazenado nesse campo
 Quando ocorre uma falta de pág., o SO examina 
todos os campos contadores da tabela a fim de 
encontrar o menor deles (menos recentemente 
usada)
14
Algoritmos de substituição de páginas
 Menos recentemente usada (LRU)
 Para uma máquina com n moldura de pág. deve ter 
um hardware auxiliar contendo uma matriz de nxn
bits, inicialmente todos com o valor 0
 Sempre que a moldura de pág. k for referenciada, 
marcará todos os bits da linha k com 1 e todos os bits 
da coluna k com 0
 Em um instante qualquer, a linha que possuir o menor 
valor binário será a pág. LRU, e a linha cujo valor 
binário seja o mais próximo do menor será a segunda 
menos recentemente usada e assim por diante
15
Algoritmos de substituição de páginas
 Menos recentemente usada (LRU)
 LRU usando uma matriz – páginas referenciadas na
ordem 0,1,2,3,2,1,0,3,2,3
16
Algoritmos de substituição de páginas
 Simulação do LRU em software
 Ambas as implementações do LRU são realizáveis 
mas poucas têm esse hardware
 Uma possibilidade em software é a substicuição de 
pág. não usada frequentemente (NFU – Not
Frequently Used)
 Requer contadores em SW, cada um deles associado 
a uma pág., inicialmente zerados
 A cada interrupção de relógio o SO percorre todas as 
pág. na memória
 Para cada pág., o bit R,que pode está em 0 ou 1, é 
adicionado ao contador correspondente
 Quando ocorrer uma falta, a pág. que tiver menor 
contagem será substituída
17
Algoritmos de substituição de páginas
 Simulação do LRU em software
 Uma pequena modificação possibilita a simulação 
do LRU
 Feita em 2 passos
 Contadores são deslocados um bit à direita
 O bit R de cada pág. é adicionado ao bit mais à 
esquerda do contador correspondente
 Quando ocorre falta de pág, a pág. que tem menor 
contagem é removida
 Esse algoritmo também é conhecido como algoritmo 
de envelhecimento (aging)
18
Algoritmos de substituição de páginas
 Simulação do LRU em software
19
Páginas 
que foram
referenciadas
Algoritmos de substituição de páginas
 Conjunto de Trabalho
 Os processos devem “roubar” pág. um dos outros ou 
devem “roubar” de si mesmo?
 Define-se o espaço de trabalho de um processo num 
determinado intervalo de tempo como sendo o 
conjunto de página acessadas pelo processo nesse 
intervalo
 Se um processo tiver na mem. menos pág. que o seu 
espaço de trabalho, estará constantemente gerando 
falta de páginas
 Se vários processos tiverem assim, o SOentra em 
colapso (thrashing)
20
Algoritmos de substituição de páginas
 Conjunto de Trabalho
 Os processos são inicializados sem qualquer de suas 
pág. presentes na memória
 Assim que a CPU tenta buscar a primeira instrução, 
ela detecta uma falta de pág. e continua buscando 
a medida que falta pág. (paginação por demanda)
 A ideia principal é encontrar uma pág. que não 
esteja presente no conjunto de trabalho e removê-la 
da memória
21
Algoritmos de substituição de páginas
 Conjunto de Trabalho
22
Algoritmos de substituição de páginas
 Conjunto de Trabalho
 Cada entrada contém (no mínimo) 2 itens de 
informação: 
 O instante aproximado em que a pág. foi 
referenciada pela última vez 
 o bit R
 Funcionamento
 Suponha que uma interrupção de relógio periódica 
ativa a execução do SW que limpe o bit R em cada 
tique de relógio
 A cada falta de pág., a tabela de pág. é varrida à 
procura de uma pág. adequada para ser removida 
da memória
23
Algoritmos de substituição de páginas
 Conjunto de Trabalho
 Funcionamento
 O bit R de cada entrada é examinado
 Se o bit R for 1, o tempo virtual atual é copiado no 
campo Instante de último uso na tabela de pág., 
indicando que a pág. estava em uso no instante em 
que ocorreu a falta de pág.
 Se o bit R é 0, a pág. não foi referenciada durante a 
interrupção de relógio atual e pode ser candidata à 
remoção da memória
24
Algoritmos de substituição de páginas
 WSClock
 Melhoramento do Conjunto de Trabalho com base 
no algoritmo do relógio
 Em virtude da simplicidade de implementação e do 
bom desempenho, é amplamente utilizado
 A estrutura de dados necessária é uma lista circular 
de molduras de pág.
 Inicialmente, essa lista encontra-se vazia
 Quando a 1ª pág. é carregada, ela é inserida nessa 
lista
 À medida que mais pág. são carregadas, elas são 
inseridas para formar um anel
25
Algoritmos de substituição de páginas
 WSClock
 Cada entrada dessa lista contém o campo Instante 
do Último Uso, bem como o bit R e o bit M
 Assim como o algoritmo do relógio, a cada falta de 
pág., a pág. que estiver sendo apontada será 
examinada primeiro
 Se o bit R for 1, a pág. foi referenciada durante a 
interrupção de relógio atual e não será candidata à 
remoção
 O bit R é então, colocado em zero, o ponteiro 
avança para a pág. seguinte e o algoritmo é 
repetido para essa nova pág.
26
Algoritmos de substituição de páginas
 WSClock
27
Algoritmos de substituição de páginas
 WSClock
28
Resumo dos algoritmos de substituição 
de página
29
Referências
 TANENBAUM, Andrew S. Sistemas Operacionais 
Modernos. 3. ed., Prentice Hall, 2009.
 MARQUES, José Alves; RIBEIRO, Carlos. Sistemas 
Operacionais. LTC, 2011. 
30