Sistemas operacionais
Paginação de memória
Prof. Diovani Milhorim
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
denominados de frames
em
blocos
de
tamanho
fixo
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
o
Define-se uma tabela de página (page table) para traduzir
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
endereçamento lógico do processo.
não
está
no
espaço
de
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
o Tamanho 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