Paginação e memória virtual

Um programa usa endereços virtuais. A memória física armazena os bytes em quadros. A paginação divide o espaço de endereçamento virtual em páginas de mesmo tamanho e a memória física em quadros do mesmo tamanho. O sistema operacional pode colocar qualquer página em qualquer quadro livre. A página 0 pode ocupar o quadro 12 e a página 1 o quadro 3; o programa continua vendo endereços virtuais consecutivos.

Isso elimina a fragmentação externa para alocações de páginas individuais. Com segmentos de tamanho variável, uma requisição pode falhar porque o espaço livre está dividido em lacunas pequenas demais. Com paginação, um quadro livre sempre comporta uma página. Um espaço de endereçamento esparso pode deixar uma grande lacuna entre a área de alocação dinâmica e a pilha sem reservar quadros físicos para ela.

Meça o espaço não usado dentro das páginas

A paginação ainda apresenta fragmentação interna. Uma região deve ocupar páginas inteiras mesmo quando sua última página está parcialmente vazia. Uma região de 9.000 bytes precisa de três páginas de 4 KiB: duas páginas comportam 8.192 bytes, deixando 808 bytes para a terceira. A alocação ocupa 12.288 bytes, dos quais 3.288 bytes não são usados. KiB significa 1.024 bytes; MiB significa 1.048.576 bytes. Alguns livros usam KB e MB para essas quantidades binárias.

Divida o endereço em campos

Um endereço identifica tanto uma página quanto um byte dentro dela. Para uma página de $2^k$ bytes, os $k$ bits menos significativos são o deslocamento. Os demais bits mais significativos são o número da página virtual, ou VPN. Um endereço de 32 bits com páginas de 4 KiB tem 12 bits de deslocamento e 20 bits de VPN. Há $2^{20}$ páginas virtuais possíveis nesse espaço de endereçamento.

Para 0x00403A7C, os três últimos dígitos hexadecimais fornecem o deslocamento 0xA7C, pois cada dígito hexadecimal representa quatro bits. Os cinco primeiros dígitos fornecem a VPN 0x00403. Esse atalho funciona aqui porque o limite entre os campos fica entre dígitos hexadecimais. Para outro tamanho de página, conte os bits antes de dividir o valor hexadecimal escrito.

A aritmética decimal fornece o mesmo resultado:

Aqui, $P$ é o tamanho da página em bytes. Com páginas de 1.024 bytes, o endereço virtual 5.000 tem VPN 4 e deslocamento 904. Quatro páginas completas correspondem a 4.096 bytes; os 904 bytes restantes localizam o endereço dentro da página 4. Os deslocamentos começam em zero, então os deslocamentos dessa página vão de 0 a 1.023.

A tradução substitui a VPN por um número de quadro físico. Ela copia o deslocamento sem alteração: o byte 904 de uma página virtual é o byte 904 de seu quadro. O número da página sozinho não é um endereço de byte. Multiplique o número do quadro pelo tamanho da página para encontrar o endereço inicial do quadro e depois some o deslocamento.

Escolha um tamanho de página

Páginas maiores reduzem o número de mapeamentos e permitem que cada tradução em cache cubra mais bytes. Elas também desperdiçam mais espaço em páginas parcialmente usadas e transferem mais dados quando uma página é carregada. Um tamanho de página base comum é 4 KiB; outros sistemas usam 16 KiB ou 64 KiB. O x86-64 também oferece mapeamentos grandes, como páginas de 2 MiB.

Uma tabela de páginas registra os mapeamentos de um processo. Em uma tabela de páginas linear, a VPN indexa um array: a entrada 4 descreve a página virtual 4. Cada processo tem sua própria tabela, então o mesmo endereço virtual pode se referir a bytes físicos diferentes em processos diferentes. Em uma troca de contexto, o sistema operacional seleciona a tabela do novo processo por meio de um registrador base da tabela de páginas.

Leia o estado e as permissões da entrada

Uma entrada da tabela de páginas, ou PTE, contém um número de quadro físico (PFN) e informações de controle. No modelo didático, um bit de validade indica que a página pertence ao espaço de endereçamento; um bit de presença indica que seu conteúdo está residente na memória física. Os bits de proteção controlam leitura, escrita, execução e acesso de usuário. Um bit de modificação registra escritas desde que foi limpo pela última vez. Um bit de acesso registra o uso desde que foi limpo pela última vez; ele também é chamado bit de referência ou de uso.

Essas são funções conceituais, não uma garantia de organizações de hardware idênticas. O x86 não tem um bit de validade separado em uma PTE. Quando o bit de presença está limpo, o sistema operacional consulta seus próprios registros para distinguir um endereço não usado de uma página válida armazenada em outro lugar. No x86, o hardware define os bits de acesso e de modificação; o sistema operacional os gerencia e limpa.

Localize a entrada e o byte

Para traduzir um endereço com uma tabela linear:

1. Divida o endereço virtual em VPN e deslocamento.
2. Localize sua entrada em $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}+\mathrm{V}\mathrm{P}\mathrm{N}\times \mathrm{P}\mathrm{T}\mathrm{E}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}$.
3. Verifique se o mapeamento existe, está presente e permite esse acesso.
4. Forme o endereço físico a partir de $\mathrm{P}\mathrm{F}\mathrm{N}\times \mathrm{p}\mathrm{a}\mathrm{g}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}+\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}\mathrm{t}$.
5. Leia ou escreva o byte nesse endereço físico.

Com páginas de 1.024 bytes, o endereço virtual 5.000 fornece VPN 4 e deslocamento 904. Suponha que a PTE 4 esteja presente e permita a leitura solicitada, com PFN 9. O quadro 9 começa em 9.216, então o endereço físico do byte é 10.120. O endereço da própria entrada na tabela exige um cálculo separado: se as entradas ocuparem 4 bytes, a PTE 4 estará 16 bytes após a base da tabela.

Em um exemplo hexadecimal, páginas de 4 KiB dividem 0x00403A7C em VPN 0x403 e deslocamento 0xA7C. Se o mapeamento permitido contiver o PFN 0x1F2B5, o endereço físico será 0x1F2B5A7C. A PTE fica em base + 0x403 × 4 = base + 0x100C. Acrescentar o deslocamento forma um endereço de dados; multiplicar a VPN pelo tamanho da entrada localiza a PTE. Esses dois endereços têm finalidades diferentes.

Uma verificação malsucedida gera uma exceção. O sistema operacional pode carregar uma página válida não residente, fornecer memória preenchida com zeros ou corrigir outro mapeamento legítimo. Um endereço inválido ou um acesso proibido geralmente causa uma falha de segmentação. Uma página presente ainda pode rejeitar uma escrita se sua proteção a proibir.

Conte o espaço da tabela e as leituras de memória

Tabelas lineares são custosas mesmo para processos pequenos. Com endereços virtuais de 32 bits e páginas de 4 KiB, cada tabela precisa de 1.048.576 entradas. Com 4 bytes cada, isso corresponde a 4 MiB por processo, incluindo entradas para páginas virtuais não usadas. Cem processos precisam de 400 MiB apenas para essas tabelas.

Elas também acrescentam uma consulta a cada referência à memória. Em um modelo simples sem cache de tradução, o processador lê uma PTE e depois os dados solicitados: dois acessos à memória. O compartilhamento ainda é possível: dois processos podem mapear intencionalmente suas páginas virtuais separadas para o mesmo PFN, como no caso de código de programa somente para leitura.

Um buffer de tradução de endereços, ou TLB, é um pequeno cache de hardware de traduções de endereços na unidade de gerenciamento de memória (MMU). Ele contém mapeamentos recentes de VPN para PFN e informações de acesso. Ele armazena traduções em cache, enquanto um cache de dados contém bytes do programa. Um programa pode sofrer uma ausência em um cache e obter um acerto no outro.

Acompanhe acertos e ausências

Em um acerto na TLB, a MMU obtém o PFN da entrada em cache, verifica as permissões de acesso e combina o PFN com o deslocamento inalterado. Ela não precisa ler a tabela de páginas. Um acerto nunca elimina a necessidade de aplicar a proteção. O bit de validade da TLB informa que uma entrada em cache é utilizável; ele não informa se uma página virtual pertence ao espaço de endereçamento do processo.

Em uma ausência na TLB, o sistema precisa procurar a tradução na tabela de páginas. Se a página estiver presente e o acesso for permitido, ele insere a tradução e conclui ou executa novamente a referência. Nenhuma leitura do armazenamento é necessária. Se a tabela indicar um mapeamento ausente ou um acesso proibido, uma falta de página exigirá tratamento pelo sistema operacional. Uma ausência na TLB, por si só, não é uma falta de página.

Preveja a reutilização pela localidade

As TLBs podem conter muito menos entradas que o número de páginas virtuais, mas funcionam bem porque os programas apresentam localidade. Localidade espacial significa que endereços próximos são usados em momentos próximos. Uma vez que uma tradução está em cache, muitos endereços nessa página podem usá-la. Localidade temporal significa que endereços usados recentemente provavelmente serão usados novamente, como as instruções de um laço.

Considere 16.384 inteiros de quatro bytes armazenados consecutivamente em um array alinhado a uma página. Com páginas de 4 KiB, cada página contém 1.024 inteiros, então o array ocupa 16 páginas. Começando com uma TLB vazia e sem traduções que interfiram, o primeiro inteiro de cada página causa uma ausência. Os 1.023 seguintes nessa página resultam em acertos. Há 16 ausências e 16.368 acertos ao todo, o que dá uma taxa de acerto de cerca de 99,9%.

A ordem de acesso muda esse resultado. Em C, int a[1024][1024] armazena linhas consecutivamente. Suponha inteiros de quatro bytes, alinhamento a páginas, páginas de 4 KiB e uma TLB LRU de 64 entradas. Cada linha ocupa uma página. O percurso linha por linha tem uma ausência por linha, ou 1.024 ausências. O percurso coluna por coluna visita 1.024 páginas diferentes antes de retornar à primeira. Sua tradução já foi removida, então todas as 1.048.576 referências ao array resultam em ausência. O tamanho do array não mudou; a distância de reutilização mudou.

Calcule a média dos custos de acertos e ausências

O modelo de tempo deve indicar o custo de um acerto e de uma ausência. Suponha que a memória leve 100 ns, que a consulta à TLB não acrescente tempo e que uma ausência em uma tabela linear acrescente uma leitura de memória. Um acerto custa 100 ns e uma ausência resolvida custa 200 ns. Com uma taxa de acerto de 98%:

Essa média inclui o acesso final aos dados nos dois casos. Contar apenas a leitura extra da PTE como o custo total da ausência subestimaria o total. Com tabelas multinível, uma ausência pode exigir várias leituras de tabela, então a localidade importa ainda mais.

Uma ausência na TLB exige uma consulta à tradução, mas as arquiteturas dividem esse trabalho de maneiras diferentes. Com uma TLB gerenciada por hardware, como em x86 e ARM, a MMU percorre a tabela de páginas a partir da raiz da tabela selecionada. O hardware define o formato que consegue percorrer. Se o mapeamento for utilizável, ele preenche o cache de tradução sem chamar um tratador do sistema operacional para a ausência comum.

Uma TLB gerenciada por software, usada em projetos clássicos MIPS e SPARC, gera uma exceção em caso de ausência. Um tratador do sistema operacional encontra o mapeamento e o insere usando instruções privilegiadas. Isso dá ao sistema operacional mais liberdade sobre a estrutura da tabela. O retorno dessa exceção executa novamente a instrução que causou a ausência; o retorno de uma chamada de sistema normalmente continua após a chamada.

Mantenha o tratador de preenchimento acessível

O tratador de ausências precisa de acesso confiável às próprias instruções e aos próprios dados. Se o atendimento de uma ausência provocar imediatamente o mesmo tipo de ausência não resolvida dentro do tratador, o progresso pode falhar. Os projetos evitam isso com memória não traduzida ou traduções permanentemente fixadas para o código e os dados essenciais do tratador.

Selecione o espaço de endereçamento correto

Trocas de contexto introduzem outro problema. O processo A pode mapear a VPN 7 para o quadro 20, enquanto o processo B mapeia a VPN 7 para o quadro 90. Manter a entrada de A sem identificador após a troca para B enviaria B ao quadro errado. Carregar a raiz da tabela de páginas de B não torna seguro, por si só, um mapeamento em cache sem identificador.

Uma solução é invalidar as entradas relevantes da TLB em uma troca. Seus bits de validade são limpos, obrigando o novo processo a preenchê-las novamente. Outra solução identifica as entradas com um identificador de espaço de endereçamento (ASID). A consulta verifica então tanto a página virtual quanto o identificador de seu espaço de endereçamento. O x86 chama seu identificador de identificador de contexto de processo, ou PCID. Entradas de vários espaços de endereçamento podem permanecer em cache enquanto o hardware seleciona apenas as que pertencem ao contexto atual. A reutilização de identificadores ainda precisa ser gerenciada para que uma entrada antiga não seja confundida com um novo espaço de endereçamento.

Invalide mapeamentos alterados

Uma alteração de PTE também torna uma tradução em cache desatualizada. Suponha que o sistema operacional remova a permissão de escrita na memória, mas mantenha uma entrada gravável na TLB. O processador poderia continuar permitindo escritas por essa entrada antiga. O sistema operacional precisa invalidar as traduções afetadas. Em uma máquina com vários núcleos de processamento, todos os núcleos que possam manter o mapeamento em cache devem participar. Essa coordenação é chamada de invalidação coordenada de TLBs.

Calcule a cobertura das traduções

A capacidade importa, assim como a correção. O alcance da TLB é a quantidade de memória representada pelas traduções em cache:

Uma TLB de 64 entradas alcança 256 KiB com páginas de 4 KiB e 128 MiB com páginas de 2 MiB. O alcance descreve a cobertura dos mapeamentos, não a capacidade da memória física. Processadores reais podem ter capacidades de TLB diferentes para diferentes tamanhos de página, então esse cálculo compara um número fixo de entradas.

Quando uma TLB está cheia, ela substitui uma tradução. LRU favorece entradas usadas recentemente; a substituição aleatória escolhe sem acompanhar a recência. Percorrer repetidamente uma página a mais do que cabe na TLB derrota a LRU, pois cada tradução é removida pouco antes de ser necessária novamente.

Uma tabela de páginas linear reserva uma entrada para cada página virtual possível. A maioria dos processos usa apenas uma pequena parte de seu espaço de endereçamento: o código e a área de alocação dinâmica ficam perto de uma extremidade, a pilha perto da outra, e uma grande lacuna os separa. Uma tabela com milhões de entradas inválidas ainda consome memória. Reduzir esse custo significa mudar o tamanho da página, a organização da tabela ou ambos.

Reduza o número de páginas

Páginas maiores reduzem o número de VPNs. Com um espaço de endereçamento de 32 bits e páginas de 16 KiB, 14 bits formam o deslocamento e 18 bits formam a VPN. Uma tabela linear precisa então de 262.144 entradas. Com 4 bytes cada, ela ocupa 1 MiB, em comparação com 4 MiB para páginas de 4 KiB. Isso economiza espaço de tabela, embora o processo ainda possa endereçar 4 GiB de bytes virtuais.

O custo aparece em outro lugar. Uma pequena alocação pode desperdiçar mais espaço em sua última página, e trazer uma página para a memória transfere mais bytes. Aumentar o tamanho da página não distingue uma parte muito usada do espaço de endereçamento de uma lacuna sem uso; apenas dá menos entradas a ambas.

Omita lacunas com tabelas de segmento separadas

Um sistema híbrido de segmentação e paginação dá ao código, à área de alocação dinâmica e à pilha suas próprias tabelas de páginas. Cada segmento tem uma base de tabela e um limite para seus números de página. A lacuna entre os segmentos não precisa de entradas. A tradução primeiro seleciona o segmento, verifica seu limite e depois procura a página dentro desse segmento.

Essa abordagem depende de uma divisão útil em segmentos. Suas tabelas podem ter comprimentos diferentes e precisar de espaço físico contíguo, reintroduzindo a fragmentação externa para as próprias tabelas. As páginas de dados do processo continuam tendo tamanho fixo; os objetos fragmentados são agora as tabelas de páginas de tamanho variável.

Indexe quadros físicos

Uma tabela de páginas invertida muda o que uma entrada descreve. Ela tem uma entrada por quadro físico para toda a máquina, registrando o processo ocupante e a VPN. Com 16 GiB de memória física e quadros de 4 KiB, ela precisa de 4.194.304 entradas, independentemente de quantos processos tenham grandes espaços de endereçamento virtual. Ainda é necessário saber o tamanho da entrada para converter essa contagem em um total de bytes.

Uma tabela comum usa a VPN como índice direto de um array. Uma tabela invertida, por sua vez, procura o par formado pela identidade do espaço de endereçamento e pela VPN. Uma estrutura de dispersão pode tornar isso eficiente, mas colisões podem exigir consultas adicionais. Quadros compartilhados também precisam de tratamento adicional, pois um quadro pode ter vários nomes virtuais. Tabelas de páginas com dispersão, como as usadas em sistemas PowerPC, usam ideias de busca relacionadas; uma tabela com dispersão não é necessariamente uma tabela invertida com exatamente uma entrada por quadro.

Aloque tabelas por região usada

Tabelas de páginas multinível mantêm a consulta indexada enquanto alocam páginas de tabela de nível inferior apenas onde são necessários mapeamentos. Uma entrada de nível superior pode marcar uma faixa inteira sem uso sem alocar sua tabela de nível inferior. Essa é a solução comum em sistemas modernos. A economia é maior para espaços de endereçamento esparsos, enquanto uma ausência na TLB exige mais etapas de consulta.

Compare as opções perguntando o que determina o tamanho. Uma tabela linear cresce com as páginas virtuais por processo. Uma tabela invertida cresce com os quadros físicos do sistema. Uma hierarquia cresce com os ramos de tabela necessários para os mapeamentos. Nenhuma dessas contagens é o número de bytes de dados do programa atualmente residentes.

Uma tabela de páginas de dois níveis divide uma grande tabela linear em partes do tamanho de uma página. Um diretório de páginas aponta para essas partes. O diretório é alocado, mas uma página de tabela de páginas de nível inferior é alocada apenas quando sua região precisa de mapeamentos. Uma entrada de diretório ausente pode representar uma faixa inteira sem uso.

Derive a divisão 10/10/12

Considere um endereço virtual de 32 bits, páginas de 4 KiB e entradas de 4 bytes. Cada página de tabela de páginas contém 1.024 entradas, então um índice de 10 bits seleciona uma entrada. O endereço se divide em 10 bits de diretório, 10 bits de tabela e 12 bits de deslocamento. Cada tabela de nível inferior mapeia 1.024 páginas, cobrindo 4 MiB de endereços virtuais. O diretório também tem 1.024 entradas e ocupa uma página de 4 KiB.

Acompanhe as entradas do diretório e da tabela

O percurso segue ponteiros físicos:

1. Some $\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ à base física do diretório. Leia essa entrada do diretório de páginas (PDE).
2. Se ela apontar para uma página de tabela, multiplique seu PFN por 4.096 para obter a base física dessa tabela.
3. Some $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ e leia a PTE.
4. Verifique o mapeamento final e combine seu PFN com o deslocamento.

A PDE aponta para uma tabela, enquanto a PTE aponta para a página de dados solicitada. Confundir essas funções envia uma referência à memória da tabela de páginas em vez dos dados do programa.

Para o endereço virtual 0x00803ABC, o índice do diretório é 2, o índice da tabela é 3 e o deslocamento é 0xABC. Suponha que a entrada 2 do diretório aponte para o quadro 0xA1. Sua tabela começa em 0xA1000. A entrada 3 está 12 bytes após o início dessa tabela, em 0xA100C. Se a PTE presente e permitida contiver o PFN 0x2F3C4, o endereço dos dados será 0x2F3C4ABC.

Observe os dois multiplicadores diferentes. Um índice de tabela conta entradas, então multiplique-o pelo tamanho da entrada. Um PFN conta quadros, então multiplique-o pelo tamanho da página. O deslocamento conta bytes dentro da página final e não precisa de nenhum dos multiplicadores. A base do diretório e os ponteiros usados durante o percurso são endereços físicos; usar ponteiros virtuais exigiria outra tradução para realizar essa tradução.

Conte as tabelas e as leituras de consulta

O espaço depende de como os mapeamentos estão distribuídos. Suponha que um processo use os 8 MiB inferiores de seu espaço de 4 GiB e os 4 MiB superiores, com ambas as regiões alinhadas aos limites do diretório. A região inferior precisa de duas páginas de tabela, e a superior, de uma. Acrescentar o diretório resulta em quatro páginas, ou 16 KiB, em vez de uma tabela linear de 4 MiB. Mapear o mesmo número de páginas de dados de forma esparsa em muitas regiões do diretório poderia exigir mais páginas de tabela.

No esquema didático básico, uma PDE inválida significa que nenhuma das páginas em sua região de 4 MiB pertence ao espaço de endereçamento. O percurso para sem ler uma PTE. Sistemas operacionais completos também podem usar entradas ausentes para alocação tardia, então seus registros de software determinam o significado de uma entrada não presente para o hardware.

A hierarquia economiza espaço ao acrescentar trabalho em uma ausência na TLB. Um percurso de dois níveis sem entradas em cache lê uma PDE e uma PTE antes de acessar os dados: três leituras de memória ao todo, em comparação com duas para uma tabela linear. Um acerto na TLB dispensa essas leituras de tabela. Isso torna uma alta taxa de acerto especialmente valiosa à medida que a hierarquia fica mais profunda.

O número de níveis da tabela decorre de três grandezas: a largura implementada do endereço virtual, o tamanho da página e o tamanho da entrada. Primeiro, calcule a largura do deslocamento. Depois, calcule quantas entradas cabem em uma página de tabela e quantos bits selecionam uma entrada. Por fim, divida os bits restantes da VPN em campos de índice, arredondando o número de níveis para cima, se necessário.

Derive os quatro níveis

Na paginação x86-64 de quatro níveis, a largura implementada do endereço virtual é de 48 bits. Uma página de 4 KiB fornece 12 bits de deslocamento. Uma entrada de 8 bytes resulta em 512 entradas por página de tabela, selecionadas por 9 bits. A VPN tem 36 bits, então são necessários quatro índices de 9 bits. Um percurso bem-sucedido sem entradas em cache segue quatro entradas e depois acessa os dados.

Os níveis são PML4, tabela de ponteiros para diretórios de páginas, diretório de páginas e tabela de páginas. Seus índices ocupam os bits 47–39, 38–30, 29–21 e 20–12. CR3 identifica a raiz física. O Linux chama os níveis correspondentes de PGD, PUD, PMD e PTE; sua hierarquia genérica inclui um nível P4D, que é eliminado quando a arquitetura usa apenas quatro níveis.

Distinga a largura do endereço da RAM

Um espaço de endereçamento implementado de 48 bits contém 256 TiB de bytes endereçáveis. Os endereços ainda são mantidos em valores de 64 bits: na forma canônica comum, os bits acima do bit 47 repetem esse bit. As faixas válidas inferior e superior são separadas por uma lacuna não canônica. Chamá-lo de espaço de endereçamento de 48 bits não significa que todo padrão de 64 bits seja utilizável ou que um processo receba 256 TiB de RAM.

Uma tabela linear seria enorme. Há $2^{36}$ páginas virtuais; multiplicar por entradas de 8 bytes resulta em $2^{39}$ bytes, ou 512 GiB por processo. Uma hierarquia representa faixas não usadas com ramos ausentes em vez de reservar todas essas entradas.

Processadores com suporte à paginação de cinco níveis podem usar 57 bits de endereço virtual implementados quando esse modo está ativado. Mais um índice de 9 bits é acrescentado acima da PML4, fornecendo 128 PiB de bytes endereçáveis e mais uma possível leitura de tabela. Os bits superiores de um endereço canônico passam então a repetir o bit 56. O suporte do processador e o modo de paginação ativado determinam qual largura se aplica.

Encerre o percurso em uma página grande

Páginas grandes encerram o percurso antecipadamente. No x86-64, uma entrada no nível do diretório de páginas pode mapear diretamente uma página de 2 MiB, deixando 21 bits de deslocamento. Uma entrada da tabela de ponteiros para diretórios de páginas pode mapear uma página de 1 GiB, deixando 30 bits de deslocamento. Os bits menos significativos que, de outra forma, selecionariam entradas de nível inferior passam a selecionar bytes dentro dessa página grande.

Isso reduz tanto o comprimento do percurso quanto o número de traduções necessárias para uma determinada região. Aumenta o alcance da TLB, o que pode ajudar bancos de dados e outras grandes cargas de trabalho. O mapeamento físico precisa de uma sequência contígua de quadros adequadamente alinhada, e uma página grande parcialmente usada pode desperdiçar muito mais memória. O Linux oferece alocação explícita de páginas enormes e páginas enormes transparentes; os tamanhos disponíveis dependem da arquitetura.

A contagem simples de custo pressupõe que nenhuma entrada de tabela esteja em cache. Processadores reais armazenam estruturas de paginação em cache, e leituras de tabela podem encontrar dados nos caches comuns. Portanto, quatro níveis não garantem quatro esperas pela memória principal em cada ausência na TLB. Eles descrevem a cadeia de dependências e seu custo sem cache.

Os espaços de endereçamento virtual podem, juntos, exceder a memória física porque nem toda página precisa permanecer residente. A área de troca armazena o conteúdo de páginas removidas em um disco ou SSD. O Linux pode usar uma partição ou um arquivo de troca; o Windows usa um arquivo de paginação. A memória física contém o subconjunto de páginas atualmente residentes.

A paginação move páginas individuais. Uma saída de página escreve uma página no armazenamento de apoio antes que seu quadro seja reutilizado; uma entrada de página a lê de volta. Historicamente, a troca também significava mover um processo inteiro. Atualmente, o termo muitas vezes se refere ao movimento de páginas, portanto identifique o objeto que está sendo movido.

Interprete o mapeamento ausente

O bit de presença de uma PTE informa ao hardware se há um mapeamento residente disponível. Se uma página válida tiver sido transferida para a área de troca, o sistema operacional registra onde seu conteúdo pode ser encontrado, em bits da entrada definidos pelo software ou em metadados separados. Um bit de presença igual a zero não indica, por si só, a área de troca: ele também pode descrever memória não alocada ou de alocação tardia.

Uma falta de página é uma exceção causada por um acesso que não pode ser concluído com o mapeamento atual. Ela pode indicar ausência ou uma violação de proteção. O tratador decide se o acesso é legítimo e como resolvê-lo. Um tratamento bem-sucedido pode carregar bytes armazenados, fornecer memória preenchida com zeros, mapear um quadro residente existente ou fazer uma cópia privada. Um acesso realmente inválido geralmente resulta em uma falha de segmentação.

Restaure uma página salva

Acompanhe a leitura de uma página da área de troca com páginas de 1.024 bytes:

1. O endereço virtual 5.000 fornece VPN 4 e deslocamento 904.
2. A TLB não tem uma tradução utilizável. O percurso da tabela de páginas encontra a página válida, mas não presente; registros de software identificam o bloco 37 da área de troca.
3. O tratador obtém o quadro 9. Se nenhum quadro estiver livre, a recuperação de memória deverá primeiro abrir espaço.
4. O sistema operacional lê o bloco 37 para o quadro 9. O processo que causou a falta espera; outro processo pronto pode usar a CPU.
5. Ao concluir a leitura, o sistema operacional instala o PFN 9, marca o mapeamento como presente e coloca o processo em estado de pronto.
6. A instrução é executada novamente. A tradução agora chega ao endereço físico 10.120.

A instrução retoma a operação pretendida depois que os bytes estão disponíveis. Avançar além da instrução que falhou faria uma leitura ou escrita se perder. O processo pode perceber uma demora, mas seu endereço virtual não mudou.

Classifique a falta e preveja a demanda

Uma falta maior exige uma leitura do armazenamento. Uma falta menor é resolvida sem essa operação de entrada e saída, por exemplo, fornecendo um quadro preenchido com zeros ou mapeando um quadro já residente. Portanto, uma grande contagem de faltas menores não implica o mesmo tráfego no dispositivo que a mesma contagem de faltas maiores. No Linux, /usr/bin/time -v informa as duas contagens para um comando.

A paginação por demanda espera até que uma página seja acessada para fornecê-la. Isso permite que um programa comece sem carregar todo o seu conteúdo. A busca antecipada traz páginas que devem ser necessárias em breve. Boas previsões evitam esperas posteriores; previsões ruins consomem largura de banda e memória com páginas que nunca são usadas.

Mantenha os eventos distintos. Uma ausência na TLB exige uma consulta à tradução. Uma falta de página exige que o sistema operacional trate um problema de mapeamento. Uma falha de segmentação é um resultado comum de um acesso proibido. Uma página residente e permitida pode causar uma ausência na TLB sem nenhum dos outros eventos.

Uma leitura rara do armazenamento pode dominar o tempo médio de memória. Seja $p$ a probabilidade de uma referência causar uma falta maior, $M$ o tempo de acesso comum e $F$ o tempo total de atendimento de uma referência que causa falta. Um modelo simples de dois casos fornece:

Aqui, $F$ inclui a leitura do armazenamento, o trabalho do sistema operacional e qualquer escrita de retorno necessária de uma vítima modificada. É o custo total do caso de falta, não apenas uma pequena penalidade de consulta à PTE.

Calcule o efeito de faltas raras

Suponha que um acesso comum leve 100 ns e uma falta maior leve 8 ms no total. Converta 8 ms em 8.000.000 ns antes de calcular a média. Com uma falta a cada 1.000 referências:

Isso é cerca de 81 vezes o tempo de acesso comum. Uma taxa de faltas de 0,1% parece pequena, mas uma falta custa tanto quanto muitos milhares de referências à memória.

Para uma perda de velocidade abaixo de 10%, exija uma média abaixo de 110 ns. Reorganizando a expressão, obtemos:

Isso é menos de aproximadamente uma falta maior a cada 800.000 referências. A probabilidade permitida depende do tempo de atendimento considerado. Para um tempo ilustrativo de atendimento em SSD de 0,1 ms, a espera é menor, mas ainda é de 100.000 ns: mil acessos de 100 ns.

Mantenha quadros prontos

O sistema operacional tenta manter quadros prontos antes que uma falta precise de um. Um daemon de paginação em segundo plano, como o kswapd do Linux, recupera memória quando o número de quadros livres cai abaixo de um limiar inferior. No modelo básico de limiares, ele continua até atingir um limiar superior. Isso evita que toda falta espere pela escolha e preparação de uma vítima.

Preserve alterações antes da reutilização

Uma página modificada contém alterações feitas desde que o estado de modificação foi limpo pela última vez. Antes que seu quadro seja reutilizado, essas alterações precisam ser preservadas se a página continuar fazendo parte da memória de um processo. Sua escrita de retorno pode ocorrer em segundo plano. Após uma escrita de retorno bem-sucedida, a página residente pode ser marcada como limpa; uma escrita posterior a modifica novamente.

Uma página limpa só pode ser descartada sem uma nova escrita quando seu conteúdo puder ser recuperado ou regenerado. Código de programa não modificado pode ser lido novamente do executável. Uma página com uma cópia atualizada na área de troca pode ser lida dessa área. Uma página anônima limpa sem uma cópia recuperável não pode simplesmente ser esquecida. O bit de modificação, por si só, não prova que exista armazenamento de apoio.

Se uma falta precisar remover uma página modificada de forma síncrona, pode ser necessária uma escrita da vítima seguida pela leitura solicitada. Preferir uma vítima limpa e recuperável evita essa escrita no caminho crítico da falta. O agrupamento de transferências combina várias escritas em transferências maiores, especialmente úteis em discos.

Faltas de página são pontos de controle úteis para adiar trabalho. Um mapeamento pode pertencer a um processo antes que o sistema operacional lhe atribua um quadro privado. Com o preenchimento com zeros sob demanda, o primeiro acesso obtém memória preenchida com zeros. Isso evita alocar e limpar antecipadamente todas as páginas reservadas. O preenchimento com zeros também impede que um processo veja dados deixados por outro.

A falta não precisa de leitura de disco porque o conteúdo necessário é composto de zeros, não de bytes salvos. É uma falta menor. Um sistema pode otimizar a implementação, mas o resultado visível continua sendo que a memória recém-fornecida contém os zeros necessários.

Compartilhe código somente para leitura

Tabelas de páginas separadas não exigem cópias separadas de todas as páginas. Duas PTEs podem conter o mesmo PFN, mesmo em endereços virtuais diferentes. Processos que executam o mesmo programa podem compartilhar código somente para leitura. Cinquenta processos usando um editor podem se referir a uma cópia residente de cada página de código compartilhada. A proteção somente para leitura impede que um processo altere essas instruções para todos.

Crie conteúdo privado em uma escrita

A cópia na escrita (COW) permite o compartilhamento inicial de páginas que mais tarde podem precisar de conteúdo privado. Após fork(), pai e filho têm espaços de endereçamento separados, mas podem compartilhar seus quadros de dados privados comuns. O sistema operacional marca seus mapeamentos privados graváveis como somente para leitura e registra que são mapeamentos COW. As leituras são concluídas sem cópia.

Quando qualquer um dos processos escreve pela primeira vez em uma página COW compartilhada, a escrita viola sua proteção atual e causa uma falta de página. O tratador reconhece o caso legítimo de COW, aloca um quadro privado, copia a página, instala um mapeamento gravável para quem escreveu e executa novamente a instrução. O outro processo mantém o conteúdo original. O sistema operacional também precisa manter as traduções em cache coerentes com os mapeamentos alterados.

Para um processo com 400 MiB de dados privados residentes, suponha que seu filho escreva em três páginas distintas de 4 KiB antes de chamar exec(). Os dados copiados por causa dessas escritas totalizam 12.288 bytes. Escritas repetidas em uma página que já é privada não causam uma nova cópia completa da página a cada vez. A criação da tabela de páginas e outros registros do processo ainda têm custos; a COW evita copiar antecipadamente todos os 400 MiB de dados.

Isso é especialmente útil quando fork() é seguido logo por exec(), que substitui o espaço de endereçamento do filho. Copiar todos os dados antigos imediatamente realizaria um trabalho que o filho talvez nunca use. Mapeamentos graváveis compartilhados intencionalmente têm outra semântica: a COW descreve os mapeamentos privados que devem se tornar distintos em uma escrita.

Uma PTE somente para leitura, por si só, não estabelece COW. Uma escrita em código de programa realmente somente para leitura é um erro; uma escrita em uma página de dados protegida por COW pode ser corrigida. Registros de software distinguem os casos, então a mesma exceção de proteção do hardware pode resultar em uma nova tentativa bem-sucedida ou em uma falha de segmentação.

Proteja os mapeamentos do núcleo

Os mapeamentos do núcleo também usam proteção. Um projeto tradicional mapeia a memória do núcleo no espaço de endereçamento de cada processo com acesso exclusivo do modo supervisor, permitindo a entrada no núcleo sem selecionar um mapeamento inteiramente diferente. Código em modo usuário não pode acessar essas páginas apenas porque elas têm endereços. O isolamento das tabelas de páginas do núcleo, introduzido em sistemas afetados depois que o Meltdown se tornou público em 2018, remove a maioria dos mapeamentos do núcleo enquanto o código de usuário é executado e troca os mapeamentos na entrada no núcleo.

Uma política de substituição escolhe uma página residente para remover quando uma página necessária não tem um quadro livre disponível. A memória física funciona como um cache do conteúdo das páginas. A política tenta manter páginas cujo uso futuro evitará faltas custosas. Uma falta de substituição é um evento abstrato de ausência da memória; a necessidade de entrada e saída depende da origem do conteúdo ausente.

Registre acertos e faltas

Compare políticas usando a mesma sequência de referências, o mesmo número de quadros e o mesmo estado inicial. Uma sequência de referências lista números de página na ordem de acesso. Para cada referência, pergunte primeiro se a página está residente. Se estiver, registre um acerto. Caso contrário, registre uma falta, carregue a página e remova uma vítima somente se a memória já estiver cheia.

As primeiras referências são faltas mesmo enquanto ainda há quadros livres. Essas faltas compulsórias não podem ser evitadas escolhendo outra vítima. Faltas posteriores causadas por capacidade insuficiente são faltas por capacidade. A substituição de páginas não tem conflitos de posicionamento: uma página pode ocupar qualquer quadro. Faltas por conflito pertencem a caches com posicionamento restrito, não a esse modelo de quadros com posicionamento totalmente flexível.

Escolha o uso futuro mais distante

A política ótima, OPT ou MIN, escolhe a página cujo próximo uso está mais distante no futuro. Uma página que nunca será usada novamente é uma vítima ideal. Isso produz o menor número de faltas para uma sequência de referências conhecida, mas um sistema operacional em execução não pode conhecer referências futuras arbitrárias. OPT fornece uma referência de comparação para políticas práticas.

Use três quadros inicialmente vazios e a sequência 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. As três primeiras referências preenchem a memória e causam faltas. A próxima referência a 1 resulta em acerto. Na referência 5, chega a página 4: as páginas residentes 1, 2 e 3 serão usadas novamente nas posições 6, 8 e 11. Remova 3, cujo próximo uso é o mais distante.

Depois que a referência a 1 resulta em acerto, a página 5 chega na posição 7. As páginas residentes 1, 2 e 4 serão usadas novamente nas posições 9, 8 e 10, então OPT remove 4. As próximas referências a 2 e 1 resultam em acertos. A página 4 causa uma falta na posição 10; 2 ou 5 pode ser removida porque nenhuma das duas será usada novamente. A página 3 causa então uma falta e remove outra página sem uso futuro. A referência final a 1 resulta em acerto.

Compare totais e cargas de trabalho

A simulação tem 7 faltas e 5 acertos. Contando todas as 12 referências, a taxa de acerto é 5/12, ou cerca de 41,7%. Há cinco páginas distintas, portanto cinco faltas compulsórias. Se a taxa informada excluir essas faltas, ela passa a ser 5/7, ou cerca de 71,4%. As duas taxas podem descrever a mesma simulação, então sempre identifique o denominador.

Para não perder sua posição, mantenha a referência atual separada da sequência futura. OPT compara o próximo uso de cada página residente após a posição atual; ela não escolhe a página que tem o maior número ou que foi carregada primeiro. Se duas páginas nunca forem usadas novamente, qualquer uma das escolhas preserva o resultado ótimo.

As cargas de trabalho afetam o quanto a política importa. Quando as referências têm a mesma probabilidade em todas as páginas, o uso passado oferece pouca orientação. Com localidade, um pequeno conjunto muito usado recebe muitas referências, e preservá-lo melhora a taxa de acerto. A diferença entre a contagem de faltas de uma política prática e a de OPT mede a melhoria possível nessa carga de trabalho.

FIFO remove a página carregada há mais tempo entre as residentes atuais. Uma fila controla a ordem de chegada. Um acerto não move a página para o fim dessa fila. Isso torna FIFO fácil de manter, mas ela pode remover uma página ainda usada com frequência simplesmente porque chegou há muito tempo.

Acompanhe o último uso em vez da chegada

LRU, a substituição da página menos recentemente usada, acompanha o uso mais recente de cada página residente. Em um acerto, essa página passa a ser a mais recentemente usada; em uma falta com a memória cheia, sai a página cujo último uso é o mais antigo. Isso segue a localidade temporal: o uso recente muitas vezes prevê o uso no futuro próximo. O momento de chegada e o momento do último uso são históricos diferentes.

A substituição aleatória escolhe uma vítima residente ao acaso, sem manter uma ordem de recência. Seu resultado varia entre execuções. Ela pode evitar o padrão determinístico de falha da LRU em uma carga de trabalho cíclica, mas ainda pode fazer escolhas infelizes. A LFU, substituição da página menos frequentemente usada, acompanha contagens em vez de recência. Sem envelhecimento, ela pode manter uma página que foi popular em uma fase anterior do programa, mas agora não é usada.

Acompanhe políticas na mesma sequência

Compare três quadros vazios na sequência 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. As páginas 1, 2 e 3 primeiro preenchem a memória. O acerto em 1 deixa a ordem de FIFO inalterada, então a chegada de 4 remove 1. A LRU, por sua vez, trata 1 como recente e remove 2. Portanto, a referência seguinte a 1 resulta em falta com FIFO e em acerto com LRU.

Na LRU, as faltas posteriores removem 3 pela página 5, 4 pela página 2, 5 pela página 4 e 2 pela página 3. Ela termina com 8 faltas e 4 acertos. FIFO produz 10 faltas e 2 acertos. OPT produz 7 faltas na mesma sequência. Aqui, LRU melhora em relação a FIFO, mas não alcança o resultado ótimo que conhece o futuro.

Explique a anomalia de Belady

Mais quadros não melhoram toda política em toda sequência. A anomalia de Belady é um aumento de faltas quando FIFO recebe mais quadros. Para 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, FIFO tem 9 faltas com três quadros e 10 com quatro. A capacidade extra muda as vítimas posteriores da fila, então seus conjuntos residentes não estão necessariamente contidos uns nos outros.

LRU e OPT são algoritmos de pilha: com tratamento consistente de empates, o conjunto residente para um número menor de quadros está contido no conjunto para um número maior. Portanto, aumentar a capacidade não pode transformar um acerto com menos memória em uma falta com mais memória. Na sequência da anomalia, LRU produz 10 faltas com três quadros e 8 com quatro.

Reconheça cargas de trabalho desfavoráveis à recência

A LRU ainda tem cargas de trabalho desfavoráveis. Percorra três vezes as páginas 1, 2, 3, 4 com três quadros. Cada nova página remove aquela que será necessária em seguida, produzindo 12 faltas. OPT precisa de 6. A substituição aleatória pode manter páginas úteis ao longo de um ciclo e tem desempenho melhor em média nesse caso. Uma varredura única pode igualmente expulsar um conjunto útil e muito usado de um cache LRU.

Uma comparação de políticas deve incluir sua carga de trabalho e o número de quadros. A localidade torna a recência útil em muitos programas, o que motiva aproximações da LRU em sistemas reais. Um laço periódico que excede a capacidade por pouco favorece outra escolha; nenhuma vantagem observada em uma única sequência curta estabelece uma classificação universal.

A LRU exata exige trabalho em cada referência à memória. Com marcas de tempo, cada referência atualiza uma marca e a seleção da vítima procura a mais antiga. Com uma lista ordenada, a vítima está disponível no final, mas cada referência precisa mover sua página para o início. Atualizar essa estrutura por software em cada leitura e escrita seria custoso demais.

Leia o bit de referência

O hardware oferece um sinal mais barato: o bit de referência, também chamado bit de acesso ou de uso. O hardware o define quando uma página é lida ou escrita. O sistema operacional o limpa para iniciar outro intervalo de observação. Um bit definido significa pelo menos um uso desde a última limpeza; ele não é uma contagem de frequência e não revela a ordem exata do último uso.

Procure uma vítima

O algoritmo do relógio coloca os quadros em círculo e mantém um ponteiro apontado para o próximo candidato. Na substituição, ele examina o bit de referência do candidato. Se o bit for 1, o ponteiro o limpa e avança. Se o bit for 0, esse quadro é a vítima. A nova página entra com seu bit de referência definido, e o ponteiro avança além dela. Um acerto define o bit da página referenciada sem mover o ponteiro.

Suponha que o círculo contenha A com bit 1, B com bit 0 e C com bit 1, com o ponteiro em A. Uma falta em D limpa o bit de A e avança para B. B já tem bit 0, então D substitui B com bit 1, e o ponteiro termina em C. Se a próxima referência causar uma falta em E, o ponteiro limpa o bit de C, encontra A com 0 e substitui A. Se A tivesse sido acessada entre essas faltas, seu bit seria 1 e ela receberia outra chance.

Se todos os bits forem 1 e nenhum novo acesso ocorrer nesse intervalo, uma volta limpa todos eles. O ponteiro então remove sua página inicial quando retorna. Essa escolha específica se assemelha à próxima vítima de FIFO na ordem de chegada, mas o relógio geralmente segue o histórico de uso e a posição do ponteiro; ele nem sempre equivale a FIFO.

Uma simulação completa do relógio precisa de uma convenção de inicialização. Aqui, os quadros vazios são preenchidos em ordem com bit 1; o ponteiro permanece no quadro 0 até a primeira substituição. Acertos definem bits. Cada substituição faz o ponteiro avançar. Segundo essa convenção, três quadros na sequência 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1 produzem 10 faltas. Uma sequência curta pode ocultar o benefício de uma aproximação de recência; o relógio costuma acompanhar bem a localidade em execuções mais longas.

Considere o custo de escrita e variantes reais

O estado de modificação acrescenta o custo de preservar uma vítima. Uma preferência do relógio aprimorado classifica pares (referência, modificação) como (0,0), (0,1), (1,0) e depois (1,1). Isso favorece uma página sem uso recente nem alterações não salvas. As implementações diferem na maneira como as varreduras limpam bits e programam escritas. A escrita de retorno em segundo plano pode tornar um candidato modificado limpo antes que a substituição precise dele.

Sistemas reais usam variantes mais elaboradas. O VAX/VMS colocava páginas removidas em listas de páginas limpas ou modificadas para que um processo pudesse recuperar uma delas antes que seu quadro fosse reutilizado. O Linux já usou listas de páginas ativas e inativas e oferece a LRU multigeracional, que agrupa páginas pela recência observada. Esses sistemas usam informações do hardware para orientar decisões do sistema operacional; o bit de referência do hardware não escolhe uma vítima por si só.

A hiperpaginação ocorre quando processos passam a maior parte do tempo trazendo páginas para a memória após faltas e removendo páginas que serão necessárias novamente em breve. O dispositivo de armazenamento permanece ocupado enquanto a utilização da CPU cai, embora os programas ainda tenham trabalho a fazer. Uma baixa carga de CPU, por si só, não identifica hiperpaginação; a combinação de paginação intensa e pouco progresso é o indício.

A causa é uma demanda de memória que excede os quadros disponíveis. Um processo precisa de um conjunto útil de páginas residentes para concluir sua fase atual. Se os conjuntos ativos de vários processos não couberem juntos, suas faltas repetidamente deslocam páginas úteis. Iniciar ainda mais processos pode piorar essa pressão, embora a CPU pareça subutilizada.

Estime a demanda atual por páginas

O conjunto de trabalho, escrito $W(t,\mathrm{\Delta })$, estima as necessidades atuais de um processo. No modelo de janela de referências, ele é o conjunto de páginas distintas nas últimas $\mathrm{\Delta }$ referências que terminam no instante $t$. Conte cada página uma vez, mesmo que apareça várias vezes na janela. O tamanho do conjunto de trabalho é um número de páginas, não o número de referências.

Com janela 5 e a sequência 1, 2, 1, 3, 2, 1, 4, 5, 4, 5, 4, 6, 5, 4, examine o estado após a referência 6. As últimas cinco referências são 2, 1, 3, 2, 1, resultando em {1, 2, 3}, de tamanho 3. Após a referência 8, a janela é 3, 2, 1, 4, 5, resultando em tamanho 5. Após a referência 11, ela é 4, 5, 4, 5, 4, resultando em tamanho 2. A demanda atinge temporariamente um pico enquanto as fases antiga e nova se sobrepõem.

Controle a demanda ativa e a alocação

Uma janela curta pode omitir páginas ainda necessárias; uma longa demais pode incluir páginas de uma fase concluída. O modelo de conjunto de trabalho de Peter Denning relaciona essas necessidades variáveis à alocação. Uma política de conjunto de trabalho executa processos apenas quando seus conjuntos de trabalho combinados cabem na memória. Se não couberem, ela suspende um ou mais processos e libera seus quadros. Isso é controle de admissão.

O controle da frequência de faltas de página (PFF) usa taxas de faltas medidas. Acima de um limiar superior, um processo precisa de mais quadros. Abaixo de um limiar inferior, alguns quadros podem ser redistribuídos. Se um processo precisar de quadros e nenhum estiver disponível, pode ser necessário suspender um processo. Dois limiares reduzem ajustes contínuos em torno de um único limite.

Com substituição global, uma falta pode remover a página de outro processo. Isso se adapta de forma flexível à demanda variável, mas permite que um processo aumente as faltas de outro. Com substituição local, as vítimas vêm apenas da alocação do processo que causou a falta. Isso limita a interferência, mas não pode ajudar um processo com poucos quadros atribuídos sem uma mudança de alocação.

Escolha soluções para a pressão de memória

Soluções úteis reduzem a demanda ou aumentam a capacidade: executar menos programas, acrescentar memória física ou melhorar a localidade, por exemplo, percorrendo arrays na ordem de armazenamento. Uma área de troca mais rápida reduz o custo de cada falta maior; ela não faz um conjunto ativo grande demais caber na memória. Substituir um disco por um SSD pode melhorar o progresso sem eliminar a causa.

Sob pressão extrema, o mecanismo de encerramento por falta de memória do Linux pode encerrar um processo selecionado quando a recuperação de memória e a troca de páginas não conseguem liberar memória suficiente. A seleção usa uma pontuação de inadequação relacionada à memória e ajustes de política, não simplesmente a identidade do maior processo. A memória pode ser recuperada quando o processo termina, e seu trabalho é perdido. Essa é uma liberação de recursos em último caso, diferente de suspender um processo para que ele possa retomar mais tarde.