Paginação de memória

No contexto dos sistemas operacionais, paginação é um esquema de gerenciamento de memória pelo qual um computador armazena e recupera dados de um armazenamento secundário para uso na memória principal. Neste esquema, o sistema operacional recupera os dados do armazenamento secundário em blocos de mesmo tamanho chamados de páginas.

Para simplificar, a memória principal é chamada de "RAM" (um acrônimo de "memória de acesso aleatório") e armazenamento secundário é chamado de "disco" (uma abreviação de "disco rígido"), mas os conceitos não dependem se esses termos aplicam-se literalmente a um sistema de computador específico.

Funcionamento

Consiste na subdivisão da memória física em pequenas partições (frames), para permitir-lhe uma utilização mais eficiente. As frames da memória física correspondem a páginas de memória virtual. A alocação de memória é requisitada por páginas, a menor unidade deste método. Cada página é mapeada numa frame de memória através de um processo que chama paginação.^[1]

A paginação é implementada normalmente por unidades dedicadas de hardware integradas nos processadores. No caso dos processadores da família Intel x86, esta funcionalidade está atribuída à MMU. A paginação é obtida através de consulta a tabelas que relacionam os endereços lineares das páginas de memória com os endereços físicos das frames de memória respectivas.

Neste sistema, cada processo no computador tem a sua própria tabela de páginas, em que a cada endereço virtual corresponde o endereço físico em que a informação está efectivamente armazenada. Visto que a informação está dividida em pequenas unidades, o seu armazenamento não tem de ser necessariamente sequencial, o que elimina a fragmentação externa da memória.

Implementação em Hardware

O registro Page-table base register (PTBR) aponta para a tabela de páginas.
O registro Page-table length register (PRLR) indica o tamanho da tabela de páginas.

Um endereço lógico (em máquinas com endereçamento de 32 bits e páginas de 4 KB) divide-se em:

Número da página: número de 20 bits.
Deslocamento na página (offset): número de 12 bits (2^12 = 4 x 1024 = 4 KB).

O acesso à memória, por este método, processa-se em duas fases:

Acesso à tabela de páginas, para tradução do endereço virtual para endereço físico.
Acesso à memória propriamente dito.

Deste modo, de cada vez que é necessária uma página de informação há necessidade de dois acessos à memória, o que é bastante penalizador, dado que há uma considerável diferença em termos de velocidade entre o processador e a memória. Para evitar este problema, desempenha um papel fundamental uma cache especial, denominada Translation Look-Aside Buffer (TLB) onde se encontram os endereços mais utilizados, e cujo tempo de acesso é muito inferior ao da memória principal. A TLB tem usualmente um número relativamente pequeno de entradas (entre 64 e 4096), porque se pretende que a pesquisa seja extremamente rápida.

A informação pretendida não tem de estar forçosamente em memória RAM, podendo estar na memória secundária (disco), através do mecanismo de swap, controlado pelo sistema operativo. Para controlar isso, as tabelas de páginas costumam ter um bit, chamado bit de presença, que assinala se determinada página se encontra ou não em memória RAM. No caso de a página não estar presente, o próprio hardware desencadeia o mecanismo chamado de page fault, notificando o sistema operativo, que se encarrega de colocar a página necessária na memória, num local acessível ao processador.

Estratégias de paginação

Paginação por demanda: As páginas são carregadas apenas quando são referenciadas. O programa começa sua execução com nenhuma de suas páginas carregadas na memória RAM. Assim que falta de páginas acontecem, o sistema operacional copia as páginas necessárias para a memória.

Paginação antecipada: Esta técnica prevê quais são as próximas páginas a serem referenciadas, minimizando falta de páginas. Por exemplo, após a leitura de uma página para tratar uma falta de página, o sistema operacional pode ler as próximas páginas, mesmo ainda não sendo necessárias (usando localidade de referência). Se um processo é terminado, o sistema operacional pode atrasar a liberação de páginas, caso o usuário decida executar o programa novamente.

Estrutura da tabela de páginas

O tamanho típico de uma página é de 4 KiB. Assim, para um espaço de endereçamento de 32 bits, cada processo tem acesso a 4 GiB de memória virtual, o que corresponde a 1 MB de páginas de memória.

Como normalmente cada entrada tem 4B de tamanho (32 bits), cada processo teria uma tabela de 4MiB de tamanho. Dado o elevado número de processos que correm simultaneamente num sistema, rapidamente uma significativa parte da memória serviria apenas para tabelas de páginas, ao invés da informação propriamente dita.

Para resolver este problema recorre-se a algumas estratégias que tentam minimizar a memória utilizada para a indexação de endereços bem sem prejudicar o desempenho.

Paginação hierárquica

Neste esquema, a tabela de páginas é dividida em partes, ou seja, a própria tabela é paginada. Deste modo, uma parte da tabela pode ficar em memória secundária (disco).

A cada entrada da primeira tabela de páginas corresponde o endereço da segunda tabela, onde está indicado finalmente o endereço físico.

Dado que a tabela de páginas é ela própria paginada, o número da página, com 40 bits, divide-se ainda em:

Número de página (p1) de 20 bits.
Deslocamento (offset) (p2) de 20 bits.

Os 12 bits de deslocamento dentro da página física completam o endereço de 32 bits da página.

Visto que aqui se aumenta o número de acessos intermédios, às várias tabelas, as TLB desempenham um papel essencial no desempenho dos acessos à memória.

Em sistemas de endereçamento de 64 bits são sempre necessários pelo menos 3 níveis de tabelas, com o endereço tipicamente dividido em 32+10+9+8.

A tabela de primeiro nível, neste sistema, tem de estar sempre presente em memória física primária (RAM), caso contrário o sistema não teria modo de saber onde se encontrava mapeada determinada parcela de informação.