Aula 06 Paginacao

Prévia do material em texto

Prof. Dr.Jean Miler Scatena
Gerenciamento de 
Memória - Paginação
● Dentro do sistema de paginação temos 2 
problemas:
– O mapeamento do endereço virtual para 
endereço físico deve ser rápido;
– Se o espaço de endereço virtual for grande, 
a tabela de páginas será a grande.
● O primeiro problema é consequência do 
fato de que o mapeamento virtual-físico 
deve ser feito em cada referência de 
memória
Paginação
● O segundo ponto decorre do fato de que 
todos os computadores modernos usam 
endereços virtuais e devido a isso, o 
espaço de endereçamento será muito 
grande com uma quantidade enorme de 
entradas
● Esses problemas levam a soluções que 
exigem mapeamentos de páginas de 
forma rápida, mesmo tendo tabelas 
extensas.
Paginação
● Uma solução simples é ter uma tabela 
de páginas consistindo de um arranjo 
de registradores de hardwares rápidos, 
com uma entrada para cada página 
virtual, indexada pelo número dessa 
página.
Paginação
● É um pequeno dispositivo de hardware 
para mapear os endereços virtuais para 
endereços físicos sem passar pela 
tabela de páginas.
● Esse hardware é chamado de TLB 
(Translation Lookaside Buffer) – Buffer 
para tradução de endereços
Memória Associativa 
ou TLB
● Em cada entrada da TLB contém 
informações sobre uma página, 
incluindo o número da página virtual, 
um bit que é colocado em 1 quando a 
página é modificada, o código de 
proteção (R,W,X) e a moldura de página 
 em que esta localizada.
● Esses campos tem uma 
correspondência de um para um 
Memória Associativa 
ou TLB
Memória Associativa 
ou TLB
● Quando um endereço virtual é 
apresentado ao MMU para tradução, o 
hardware verificar se o número de sua 
página virtual esta presente no TLB 
comparando-o com todas as entradas 
da TLB Simultaneamente
● Se uma correspondência é encontrada e 
o acesso não viola os bits de proteção, 
o número da moldura de página, é, 
então, obtido do TLB
Memória Associativa 
ou TLB
● Se o número de página virtual estiver 
presente no TLB, mas a instrução tenta 
escrever em uma página que permite 
somente leitura, uma falta por violação 
de proteção ocorrerá.
● Quando ocorrer uma ausência de página 
no TLB, a MMU detecta a ausência e faz 
uma busca na tabela de páginas. Ao 
encontrar, a MMU desaloca uma entrada 
da TLB e aloca essa nova página
Memória Associativa 
ou TLB
● As TLBs são utilizada para acelerar as 
trocas de endereços virtuais para 
endereços físicos, mas esse não é o 
único problema.
● Existe o problema de como lidar com 
espaços de endereço virtual muito 
grandes. 
● Uma solução são as tabelas de páginas 
multinível e tabelas de páginas 
invertidas
Tabela de Páginas para 
Memórias Grandes
● Esse método é evitar que todas as 
páginas sejam mantidas na memória 
todo tempo, especialmente as que não 
sejam necessárias.
● Ness caso, as referências para a 
memória terão 2 ponteiros, um para a 
página principal e a um segundo para o 
segundo nível da página e um 
deslocamento
Tabela de Páginas 
Multinível
Tabela de Páginas 
Multinível
● Esse método é evitar que todas as 
páginas sejam mantidas na memória 
todo tempo, especialmente as que não 
sejam necessárias.
● Ness caso, as referências para a 
memória terão 2 ponteiros, um para a 
página principal e a um segundo para o 
deslocamento dentro da página 
principal
Tabela de Páginas 
Multinível
● Com o aumento para o endereçamento 
de 64 bits as tabelas de páginas 
multiníveis, pois a quantidade de 
elementos necessários para representar 
os elementos da tabela podem 
ultrapassar 30PB (PentaByte)
● Uma solução é utilizar a tabela de 
páginas invertidas.
Tabela de Páginas 
Invertidas
● Na tabela de páginas invertidas existe 
apenas uma entrada por moldura de 
página na memória real, em vez de 
uma entrada por página do espaço de 
endereçamento virtual.
● Embora esse sistema possa economizar 
espaço, a tradução do endereço virtual 
para o endereço física se torna muito 
mais difícil, devido ao tamanho da 
tabela
Tabela de Páginas 
Invertidas
● São algoritmos utilizados para 
relacionar qual página deverá sair de 
sua moldura(RAM) para a entrada de 
uma nova página.
● Esses algoritmos tem como finalidade a 
escolha da saída de uma página, sendo 
que essa escolha minimize a defasagem 
do desempenho do sistema
Algoritmos de 
Substituição de Páginas
● Esse algoritmo tem como principal 
característica a análise das próximas 
solicitações de memória que cada processo 
irá solicitar, escolhendo o processo que não 
solicitará a memória nas próximas execuções
● A vantagem desse algoritmo é que ele 
removerá da memória sempre o processo 
mais inativo
● A desvantagem é que o algoritmo não 
consegue calcular as futuras execuções de 
cada processo
Algoritmo Ótimo de 
Substituição de Página
● Esse algoritmo tem como principal 
característica utilizar 2 bits, os bits R e 
M, onde o bit R → Referenciado e M → 
Modificado.
● Esses bits são utilizados para marcar as 
posições de memória que foram 
alteradas ou simplesmente acessadas
Algoritmo de Substituição de 
Página Não Usada 
Recentemente
● Com esses bits, o algoritmo organiza as 
páginas na seguinte forma:
– Classe 0: Não Referenciada, Não 
Modificada
– Classe 1: Não Referenciadas, Modificada
– Classe 2: Referenciadas, Não Modificada
– Classe 3: Referenciada, Modificada
Algoritmo de Substituição de 
Página Não Usada 
Recentemente
● O uso das páginas serão realizadas a partir 
dos elementos encontrados na classe 0, 
caso não tenha elementos nessa classe, 
será utilizada as próximas classes.
● Por mais estranho que possa parecer, a 
classe 1 pode exister, pois a cada ciclo de 
execução dos processos o estado do bit R 
sofre alterações, sendo assim, caso um 
processo tem sido modificado e após 2 
ciclos de execução não tenha sido 
acessado, o bit R ficará em 0 e M em 1
Algoritmo de Substituição de 
Página Não Usada 
Recentemente
● Esse algoritmo é chamado de Primeiro a 
entrar, Primeiro a Sair
● Para realizar tal operação, o algoritmo 
organiza todos os processos em uma 
fila de acesso as molduras de páginas.
● Como essa fila, o primeiro elemento é o 
elemento é o mais velho, ele será o 
primeiro elemento a ser retirado 
● Assim ocorrerá sucessivamente.
Algoritmo de Substituição de 
Página FIFO
● É o mesmo algoritmo FIFO, contudo não 
apresenta uma defasagem crucial no 
algoritmo.
● O algoritmo FIFO tem o problema de 
não verificar se o primeiro elemento da 
fila foi utilizado recentemente ou não.
● Com isso, o algoritmo FIFO pode retirar 
uma página de memória altamente 
referenciada, gerando alto fluxo de 
swap
Algoritmo de Substituição de 
Página Segunda Chance
● Esse algoritmo é organizado da mesma 
forma, através de um fila.
● Contudo, antes de retirar o primeiro 
elemento da fila, é verificado se o bit R, 
se ele estiver em 0, a página será 
retirada, caso contrário, o bit R da 
página será modificado para 0 e a 
página entrará no final da fila
Algoritmo de Substituição de 
Página Segunda Chance
● O problema desse algoritmo é que a 
retirada do elemento da fila para a 
alocação para o final da fila consome 
operações de processador, gerando um 
custo computacional adicional
Algoritmo de Substituição de 
Página Segunda Chance
● O problema do algoritmo de segunda 
change é que ele fica inserindo, a todo 
momento, elementos no final da lista 
gerando um custo computacional 
adicional
● No algoritmo do relógio sera utilizada uma 
fila circular semelhante a um relógio, 
onde quando o bit R=0, ele é retirado da 
memória, caso seja 1, esse bit é zerado e 
passado para a próxima página
Algoritmo de Substituição dePágina de Relógio
● Uma boa aproximação do algoritmo ótimo 
é baseada na observação de que as 
páginas muito utilizadas nas últimas 
instruções provavelmente serão muito 
utilizadas novamente nas próximas 
instruções.
● Da mesma forma, de que, as páginas que 
não estão sendo utilizadas por um longo 
período de tempo, provavelmente 
permanecerão inutilizadas por um longo 
tempo. 
Algoritmo de Substituição de 
Página usada menos 
recentemente
● Para funcionar o algoritmo LRU elimina a 
página que faz mais tempo que não é 
utilizada
● O problema desse algoritmo é que para 
realizar tal tarefa ele precisa manter uma 
lista de todas as páginas, sendo as páginas 
mais utilizadas colocadas na frente e as 
menos utilizadas na traseira da lista.
● O problema é que a lista deve ser 
atualizada a cada referência de memória
Algoritmo de Substituição de 
Página usada menos 
recentemente
● A melhor forma de paginação é carregar 
as páginas conforme são solicitadas, ou 
seja, quando o processo solicitar uma 
página, ela será carregada na memória
● Isso é chamada de paginação por 
demanda
● Um conjunto de páginas que estão 
sendo utilizadas por um processo é 
chamado de conjunto de trabalho
Algoritmo de Substituição de 
Página do conjunto de trabalho
● Caso a memória seja pequena, ocorrerá 
constantemente a troca de páginas na 
memória gerando faltas de página 
frequentemente e continuamente 
provocando ultrapaginação (thrashing)
● Nesse algoritmo ocorre o pré-
carregamento do conjunto de páginas 
de um processo, antes que ele seja 
executado
Algoritmo de Substituição de 
Página do conjunto de trabalho
● Clock + Working Set
● Amplamente usado, devido à sua simpli
cidade e performance
● Utiliza lista circular de páginas
– Inicialmente vazia
– À medida que mais páginas são carregadas
, entram na lista, formando um anel
– Cada entrada contém o tempo de último us
o, além dos bits R e M
Algoritmo de Substituição de 
Página WSClock
● Funcionamento:
– A cada page fault, a página da 
cabeça é examinada primeiro
– Se R=1
● A página foi usada durante o ciclo
 de clock corrente   → 
não é candidata a remoção
● Faz R = 0 e avança a cabeça à 
próxima página, repetindo o algor
itmo para esta página
Algoritmo de Substituição de 
Página WSClock
● Funcionamento:
– Se R=0
● Se a idade for maior que o tam
anho do working set e a página 
estiver limpa (M=0) → 
não está no working set e uma 
cópia válida existe no disco
– A página é substituída
– A cabeça da lista avança
Algoritmo de Substituição de 
Página WSClock
● Funcionamento:
– Se R=0
● Se, contudo, a páginaestiver suja → não possui 
cópia válida no disco
– Agenda uma escrita ao disco, evitando a 
troca de processo
– Avança a cabeça da lista, prosseguindo da página 
seguinte
Algoritmo de Substituição de 
Página WSClock
● Funcionamento:
– Se R=0
● Se, contudo, a páginaestiver suja → não possui 
cópia válida no disco
– Agenda uma escrita ao disco, evitando a 
troca de processo
– Avança a cabeça da lista, prosseguindo da página 
seguinte
Algoritmo de Substituição de 
Página WSClock
● Funcionamento:
– Se a cabeça der uma volta completa na lista 
sem substituir:
● E pelo menos uma escrita no disco foi agendada
– A cabeça continua se movendo, em busca de uma página 
limpa
– Em algum momento a escrita agendada será executada, 
marcando a página como limpa
● E nenhuma escrita foi agendada
– Todas as páginas estão no working set
– Na falta de informação adicional, substitua qualquer págin
a limpa
– Se nenhuma página limpa existir, escolha qualquer outra 
e a escreva no disco
Algoritmo de Substituição de 
Página WSClock
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35