aula13 Paginacao Memoria

Prévia do material em texto

Sistemas operacionais
Paginação de memória
Prof. Alberlan Lopes
Paginação de memória
• O Espaço de Endereçamento lógico de um processo pode ser 
 não contínuo; aloca-se memória física ao processo sempre 
que esta é disponível. 
• A memória física (sistema) e a memória lógica (processo) 
 são divididos em blocos de tamanho fixo e idênticos: 
o Memória física dividida em blocos de tamanho fixo 
denominados de frames
o Memória lógica divide em blocos de tamanho fixo denominados de 
páginas 
Paginação de memória
• Sistema mantém o registro de todos os frames livres. 
• Para executar um processo do tamanho de n páginas, 
basta encontrar n frames livres na memória 
o Páginas são carregadas em qualquer frame livre 
• Necessidade de traduzir endereços lógicos (páginas) em endereços 
 físicos (frames) 
o Define-se uma tabela de página (page table) para traduzir 
 o endereço lógico em físico. 
• Elimina a fragmentação externa e reduz a fragmentação interna 
Paginação de memória
Paginação de memória
Características da paginação
• Paginação é um tipo de relocação (via 
hardware) 
• Não gera fragmentação externa 
• Fragmentação interna é restrita apenas a última 
página 
Paginação de memória
• Importante: 
o Visão do usuário: espaço de endereçamento contíguo 
o Visão do sistema: processo é “esparramado” na memória física 
• n páginas são alocadas a n frames implicando na criação 
 de uma tabela de correspondência 
o Tabela de páginas
Facilita implementação de proteção e compartilhamento
Paginação de memória
Tamanho da página
Páginas grandes significam:
o Processos compostos por menos páginas (tabela de páginas 
menores)
o Aumento da fragmentação interna na última página 
Páginas pequenas significam: 
o Processos compostos por mais páginas (tabela de página 
maiores) 
o Diminuição da fragmentação interna na última página.
Paginação de memória
• Objetivos conflitantes 
Tamanho da página é imposto pelo 
hardware (MMU) 
Valores típicos variam entre 1 kbyte e 8 
kbytes 
Paginação de memória
Questões relacionadas com a gerência de páginas
• A gerência de memória deve manter controle de áreas livres e 
ocupadas 
Inclusão de mecanismos de proteção 
 Evitar que um processo acesse área (páginas) de outros 
processos
 Garantir que um processo acesse apenas endereços válidos 
 Garantir acessos autorizados a uma posição de memória
e.g.: páginasread-only, read-write, etc.
 
Inclusão de mecanismos de compartilhamento
 Permitir que dois ou mais processos dividam uma área comum
e.g.: páginas de código de um aplicativo do tipo editor de texto
Paginação de memória
Proteção
• Proteção de acesso é garantida por definição: 
 Processos acessam somente suas páginas (end. válidos)
 Endereço inválido apenas na última página (Se houver fragmentação 
interna)
 Inclusão de bits de controle na tabela de página (por entrada).
 Indicação se a página é de leitura, escrita ou executável 
 Proteção de memória é implementada associando-se um bit 
 de proteção a cada frame. 
Paginação de memória
Bit Válido - Inválido anexado a cada entrada na tabela de página: 
• “válido” indica que a página associada está no espaço de 
endereçamento lógico do processo, assim, é a uma página legal. 
• “inválido” indica que a página não está no espaço de 
 endereçamento lógico do processo. 
Paginação de memória
Exemplo de proteção
Paginação de memória
Compartilhamento de páginas
Código compartilhado
o Uma cópia do código (read-only, re-entrante) pode ser 
compartilhada entre vários processos (e.g.; editores de texto, 
compiladores, etc...)
o O código compartilhado pertence ao espaço lógico de todos os 
processos 
Dados e código próprios 
o Cada processo possui sua própria área de código e seus dados 
Paginação de memória
Exemplo de compartilhamento:
Segmentação de memória
 Segmentação
 Técnica de gerência de memória, onde os programas são 
divididos logicamente e em sub-rotinas e estruturas de 
dados e colocados em blocos de informações na memória
 Segmentos – blocos de tamanhos diferentes com seu 
próprio espaço de endereçamento.
 Respeita a visão do programador.
Segmentação de memória
 Segmentação
 Segmentação X Paginação 
Paginação com partes de tamanho fixo e 
segmentos com blocos de tamanhos variados
permite uma relação entre a lógica do 
programa e sua divisão na memória.
Segmentação de memória
 Segmentação
 Cada entrada na tabela de segmentos possuí o endereço 
do segmento na memória física, informações sobre o 
tamanho do segmento, sua proteção e se ele está na 
memória ou não.
 O Sistema Operacional mantém uma tabela com as áreas 
livres e ocupadas da memória.
Segmentação de memória
 Segmentação
 A escolha da área livre a ser ocupada por um processo a 
ser carregado na memória pode ser a mesma utilizada no 
item Alocação Particionada Dinâmica (best-fit, worst-fit ou 
first-fit).
 Apenas os segmentos referenciados são transferidos para 
a memória real.
 Os programas devem ser bem modularizados para uma 
maior eficiência.
Segmentação de memória
  Segmentação com Paginação
 Permite a divisão lógica dos programas e segmentos e, 
cada segmento é dividido fisicamente em páginas.
 Um endereço é formado pelo número do segmento, pelo 
número de página, contida nesse segmento, e pelo 
deslocamento dentro dessa página.
 O endereço físico é obtido somando-se a posição inicial 
do frame e o deslocamento.
Paginação de memória
Implementação da tabela de páginas
• Sistema operacional deve manter: 
o Frames livres/alocados 
o Número de frames e de páginas de um processo o Uma entrada 
para cada frame e para cada processo 
• Como implementar a tabela de páginas? 
o Registradores e Memória 
Paginação de memória
Implementação da tabela de páginas via registradores
Tabela de páginas é mantida por um conjunto de registradores
o Cada página um registrador
o No descritor de processo devem ser mantidas cópias dos 
registradores
Troca de contexto: atualização dos registradores
Desvantagem é o número de registradores
Paginação de memória
Implementação da tabela de páginas em memória
Tabela de páginas é mantida em memória
o Page-table Base Register (PTBR): início da tabela de páginas 
o Page-table Length Register (PTLR): tamanho em número de 
entradas.
Cada acesso necessita, no mínimo, dois acessos a memória
Paginação de memória
Cada acesso necessita, no mínimo, dois acessos a memória
Paginação de memória
Translation look-aside buffers (TLBs)
• Uma espécie de meio termo entre implementação via registradores e 
via memória 
• Baseada em uma memória cache especial (TLB) composta por 
um banco de registradores (memória associativa) 
• Idéia é manter a tabela de páginas em memória com uma cópia 
 parcial da tabela em um banco de registradores (TLB) 
o Página acessada está na TLB (hit): similar a solução de 
registradores
o Página acessada não está na TLB (miss): similar a solução via 
memória 
Paginação de memória
Implementação da tabela de páginas via TBL
Paginação de memória
Aspectos relacionados com o uso de TLB
• Melhora o desempenho no acesso a tabela de páginas o Tempo de 
acesso 10 vezes menor que uma memória RAM 
• Desvantagem é o seu custo 
oTamanho limitado (de 8 a 2048 entradas) 
o Uma única TLB (pertence a MMU) que é compartilhada entre 
todos processos
Paginação de memória
TBL - Um acesso é feito em duas partes: 
o Se página está presente na TLB (hit) a tradução é feita 
o Se página não está presente na TLB (miss), consulta a tabela 
em memória e atualiza entrada na TLB
Paginação de memória
Tabelas multinível 
 Cada processo tem associado ao seu espaço de endereçamento 
uma tabela de páginas 
 A tabela de páginas de cada processo tem que estar carregada em 
memória 
 Para minimizar o espaço em memória ocupado pelas tabelas de 
páginas, utilizam-se habitualmente tabelas multí-nivel 
 Guardam-se na memória uma tabela principal, e as tabelas dos 
restantes níveis, que contém os descritores das páginas que estão a 
ser utilizadas pelo processo 
 Estas tabelas têm uma dimensão muito mais pequena do que se 
fosse utilizado um esquema com um só nível 
 
Paginação de memória
Tabelas multi-nível : exemplo
Paginação de memória
Page-faults:
 Quando é pedida uma página que não se encontra na memória 
principal, ocorre uma page fault 
 Uma page fault é uma exceção que causa bloqueio ao processo em 
questão 
 Inicia-se o de carregamento da página em falta, da memória 
secundária para a memória principal 
 Efetuam-se as alterações necessárias na page table, de modo a esta 
continuar consistente 
 Pode ser necessário transferir uma outra página para a memória 
secundária, de modo a libertar-se uma page frame – nesse caso 
corre-se o algoritmo de substituição de páginas 
 
Paginação de memória
Algoritmos de substituição de páginas 
O algoritmo ideal:
 Sempre que for necessária uma substituição de páginas, a que 
deveria sair será aquela que só será utilizada daqui a mais tempo 
 Este algoritmo não é realizável, pois os S.O.s não conseguem prever 
o futuro... 
 A aproximação é tentar descartar as páginas que são pouco 
utilizadas, ou que já não são utilizadas há muito tempo, na esperança 
de que não venham a ser utilizadas brevemente 
Paginação de memória
Algoritmos de substituição de páginas 
Not recently used – NRU
Quando ocorre uma page fault, este algoritmo classifica as páginas 
carregadas em memória. Para tal utiliza dois bits: 
R (Referenced) – indica que a página foi acedida desde a última interrupção 
do relógio 
M (Modified) – indica que a página foi modificada desde que foi carregada 
na memória principal 
Estabelecem-se 4 classes diferentes, de acordo com R e M 
Classe 0: R=0 e M=0 
Classe 1: R=0 e M=1 
Classe 2: R=1 e M=0 
Classe 3: R=1 e M=1 
A página a substituir será uma pertencente à classe mais baixa encontrada 
Paginação de memória
Algoritmos de substituição de páginas 
FIFO (First-in, first-out) 
 A página a substituir é a que se encontra carregada há mais tempo 
na memória principal 
 Algoritmo de fácil implementação, bastando ter uma lista com índices 
de páginas, com a mais antiga no topo e a mais recente no fim 
 À medida que as páginas vão sendo carregadas na memória, os seus 
índices vão também sendo acrescentados ao fim da lista mantida 
pelo algoritmo 
 
Problema: a página que foi carregada há mais tempo pode estar a ser 
utilizada... 
Paginação de memória
Algoritmos de substituição de páginas 
Bit de referência
 A cada frame e associado um bit “R” com valor inicial 0.
 Quando uma página é referenciada o Bit “R” é alterado para 1.
 Ao fim de algum tempo todas as páginas tem bit “R” igual a 1. Neste 
momento deve entrar em ação um algoritmo de “esquecimento” que 
torna todos os bits 1 em 0.
 O frame escolhido para a substituição é aquele primeiro que ao ser 
verificado tiver o bit “R” igual a 0.
Paginação de memória
Algoritmos de substituição de páginas 
Segunda chance 
 Algoritmo baseado no FIFO, mas que utiliza o bit de referência (R) 
 Antes de uma página ser descartada, analisa-se o bit R e, caso este 
se encontre a “1”, então é posto a “0”, mas a página não é 
descartada, analisando-se a próxima. 
 A página a descartar será a primeira que for encontrada com R=0 
Paginação de memória
Algoritmos de substituição de páginas 
LRU (Least recently used) 
 A página a substituir será a que não é acedida à mais tempo 
 Para tal, guarda-se para cada página uma marca temporal com o 
tempo do último acesso 
 Teoricamente este algoritmo é o que efetua a melhor escolha na 
página a substituir 
 Bom desempenho a um custo elevado: 
 Na prática, este algoritmo obriga à existência de um temporizador 
extra (pois as interrupções do relógio são demasiado “lentas”) 
 Para além disso, exige bastante espaço para guardar as marcas 
temporais (e.g. 64 bits) sempre que uma página é acedida 
Paginação de memória
Algoritmos de substituição de páginas 
NFU (Not frequently used) 
 Algoritmo que tenta efectuar uma aproximação ao algoritmo LRU 
 Associado um contador a cada página carregada em memória, 
inicializado a zero quando a página é carregada 
 Sempre que ocorre uma interrupção do relógio, e para cada página, 
soma-se o valor do bit R ao contador 
 
Problema: uma página muito acedida no início, mas que depois deixe de 
ser acedida fica com um valor elevado no contador, pelo que poderá 
persistir na memória 
Paginação de memória
Algoritmos de substituição de páginas 
Aging 
 Variante do algoritmo NFU, que tenta resolver o problema descrito 
anteriormente 
 Em vez de somar o bit R ao valor do contador, desloca-se o seu 
conteúdo para a direita com entrada série do bit R 
 Deste modo consegue-se que uma página muito acedida no 
passado, mas que já não está a ser utilizada, fique com o valor do 
contador a zero após algumas interrupções do relógio 
 
Algoritmo com melhor relação custo/desempenho 
Paginação de memória
Thrashing 
Um CPU atual executa cada instrução em menos de 1 nano-segundo 
 Quando ocorre uma page fault, o carregamento de uma página para 
a memória principal poderá demorar um tempo na ordem mili-
segundos 
 O carregamento de uma página é cerca de 1.000.000 de vezes mais 
lento que a execução de uma instrução... 
 Quando um grupo de processos começa a gerar page faults a um 
ritmo muito elevado diz-se que se entrou numa fase de thrashing – 
esta situação deve ser evitada a todo o custo 
Paginação de memória
Working Set 
 O Working Set é o conjunto de páginas que estão a ser utilizadas por 
um processo 
 Se todo o Working Set de um processo está carregado em memória, 
então não ocorrem page faults 
 Tirando partido deste facto, existem algoritmos de substituição de 
páginas que funcionam tendo em conta o working set de um processo 
 A ideia será substituir páginas que não se encontrem dentro do 
working set de um processo 
Paginação de memória
Política de carregamento de páginas 
 
Paginação a pedido (Demand paging) 
As páginas de um processo vão sendo carregadas à medida que 
ocorrem page faults – esta abordagem faz com que ocorram page 
faults inicialmente, até ser estabelecido o working set do processo 
 
Paginação por antecipação (Prepaging) 
Antes do processo correr, o SO carrega para a memória um conjunto de 
páginas – a sua previsão do working Set 
	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
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41