Algoritmo de troca de página

Em sistemas operacionais de computador que usam paginação para o gerenciamento da memória virtual, os algoritmos de troca de página decidem que páginas da memória serão gravadas no disco quando uma nova página precisa ser alocada. A paginação ocorre quando uma falha de página acontece e uma página livre não pode ser usada para satisfazer a alocação, geralmente porque não há páginas suficientes para tal.

Quando uma página selecionada e jogada para o disco é referenciada novamente, ela é novamente carregada do disco, o que envolve uma operação de entrada/saída. Isto determina a qualidade do algoritmo de paginação: quanto menos tempo for gasto com as recargas de páginas, mais eficiente e melhor é o algoritmo. Um algoritmo de troca de página dispõe de uma quantidade limitada de informação sobre os acessos disponibilizada pelo hardware, e tenta adivinhar que páginas devem ser substituídas para minimizar o total de faltas de página, balanceando os custos das operações envolvidas.

História

Algoritmos de troca de página renderam muitas pesquisas nas décadas de 60 e 70. A maioria delas terminou com o desenvolvimento dos sofisticados algoritmos de aproximação LRU (Least Recently Used, Menos Recentemente Usado). Desde então, alguns pressupostos básicos feitos pelas trocas de página tradicionais tornaram-se inválidos, resultando numa nova retomada de pesquisas. Particularmente, as seguintes tendências de comportamento do hardware e do software de usuário passaram a afetar os algorimos de paginação:

• o tamanho da memória primária aumentou em várias ordens de magnitude; com tantos gigabyte de memória primária, os algoritmos que demandavam checagem periódica de cada quadro passaram a ser menos práticos;

• a hierarquia de memória cresceu, e o custo da memória cache de CPU é muito maior, o que exacerba o problema anterior; e

• a localidade de referência dos softwares enfraqueceu, principalmente devido à proliferação de técnicas de programação orientada a objeto que favorecem um grande número de pequenas funções e o uso de estruturas sofisticadas como árvores e tabelas hash, que tendem a resultar em padrões caóticos de referência à memória, e o advento do coletor de lixo que mudou drasticamente o comportamento de acesso à memória dos programas.

Os requisitos para os algoritmos de troca de página têm mudado devido às diferenças de arquitetura dos kernels dos sistemas operacionais. Em particular, muitos sistemas operacionais modernos possuem um sistema de memória virtual unificado ao cache do sistema de arquivos, demandando ao algoritmo de paginação selecionar uma página dentre os dois ambientes. Entretanto, o cache de arquivos tem características peculiares como o travamento de escrita ou a fila de journaling. Mais ainda, como o objetivo do algoritmo é otimizar o tempo de espera por memória, ele deve levar em consideração requisitos impostos pelos outros subsistemas do kernel que alocam memória. Como resultado, a paginação em kernels modernos, como Linux, FreeBSD e Solaris, tende a trabalhar no nível do alocador de memória genérico do kernel, ao invés de um nível mais alto, como o do subsistema de memória virtual.

Local ou global

Os algoritmos de troca podem ser globais ou locais.

Quando um processo incorre numa falta de página, um algoritmo de troca local seleciona para a troca uma outra página que pertença ao mesmo processo (ou grupo de processos compartilhando uma mesma partição de memória). Uma troca de página global é livre para selecionar qualquer página em toda a extensão da memória.

A troca local assume implicitamente um particionamento da memória que determina quantas páginas ficam disponíveis para um dado processo ou grupo de processos. As formas mais populares deste tipo de particionamento são os algoritmos de partição fixa e balanceada, ambos baseados no modelo working set. A vantagem da troca de página local é a escalabilidade: cada processo pode cuidar de suas próprias faltas de página de forma independente, sem concorrer com outros processos numa estrutura centralizada.

Limpeza prévia

Muitos algoritmos de troca de página simplesmente retornam a página-alvo como resultado. Isto significa que se a página alvo está suja — isto é, se contém dados que devem ser escritos em disco antes da página ser reclamada —, as operações de entrada/saída devem ser iniciadas para enviar a página para o disco (limpando-a). Nos primórdios da memória virtual, o tempo gasto nas limpezas não causava preocupação, porque as primeiras memórias virtuais foram implementadas em sistemas com canais full duplex para o armazenamento de disco, e a limpeza era normalmente mais rápida que a paginação em si. O hardware, entretanto, evoluiu na direção oposta, deixando de suportar transferências full duplex, e a limpeza de página acabou por tornar-se um problema.

Para lidar com a situação, várias políticas de limpeza prévia são implementadas. Essas políticas são o mecanismo que aciona a entrada/saída em páginas que (presume-se) serão substituídas em breve. A ideia é que, quando chegar o momento da página ser substituída, ela já terá sido limpa. A limpeza prévia assume que é possível identificar as páginas que serão substituídas primeiro. A eficiência máxima do mecanismo é alcançada quando a página é trocada no exato momento após ser limpa — quanto mais cedo uma página for limpa, mais tempo ela ficará esperando e mais sobrecarregado ficará o sistema, escrevendo-as em disco sem necessidade.