Sistemas operacionais

Sistemas operacionais

Paginação de memória

Prof. Diovani Milhorim


• 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


• 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



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


• 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


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.


• Objetivos conflitantes

Tamanho da página é imposto pelo hardware (MMU)

Valores típicos variam entre 1 kbyte e 8 kbytes

Paginação de memóriaQuestõ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áginasread-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óriaProteçã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.


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óriaExemplo de proteção

Paginação de memóriaCompartilhamento 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óriaExemplo 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 X Paginação Paginação com partes de tamanho fixo e

segmentos com blocos de tamanhos variadospermite uma relação entre a lógica do

programa e sua divisão na memória.


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.


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óriaImplementaçã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óriaImplementaçã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


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

Paginação de memóriaTranslation 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óriaImplementação da tabela de páginas via TBL

Paginação de memóriaAspectos 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


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


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


Tabelas multi-nível : exemplo


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


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óriaAlgoritmos 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


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...


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.


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


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


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


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óriaThrashing

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óriaWorking 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óriaPolí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

Documents

Sistemas operacionais