Sistemas operacionais
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
Cada acesso necessita, no mínimo, dois acessos a memória
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
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