Chegamos à pergunta que os artigos passados deixaram no ar. Vimos que o kernel pode mover páginas "frias" para o swap quando a memória fica escassa. Mas como ele decide quais páginas são frias? Qual página remover quando você precisa de um frame livre e todos estão ocupados?
Essa é uma das perguntas mais estudadas em Sistemas Operacionais, e a resposta certa faz a diferença entre uma aplicação que voa e uma que passa a vida esperando o disco :D.
Vamos dos algoritmos teóricos (Tanenbaum) até o que o Linux realmente implementa, DISCLAIMER: Mano isso é muito nerdice mais eu adoro kkk
Sumário
- O problema da substituição de páginas
- Algoritmo Ótimo (OPT)
- NRU: Not Recently Used
- FIFO e a Anomalia de Belady
- Segunda Chance e o Algoritmo do Relógio
- LRU: Least Recently Used
- O Modelo do Working Set
- WSClock
- Thrashing
- Políticas de Alocação de Frames
- Referências Bibliográficas
O problema da substituição de páginas
O cenário é o seguinte: a memória física está cheia, e ocorre um page fault que exige trazer uma nova página do disco. Não há frames livres. O kernel precisa escolher uma página vítima para despejar (evict), liberando um frame.
Se a página vítima estiver suja (dirty bit = 1, lembra da Parte II?), ela precisa ser gravada no disco antes de descartada. Se estiver limpa, pode ser simplesmente descartada (o conteúdo pode ser relido da origem). A escolha da vítima é crucial:
- Se removermos uma página que será acessada logo em seguida, causamos um novo page fault imediato — desperdício.
- Se removermos uma página que não será mais usada, acertamos em cheio.
O objetivo de todo algoritmo de substituição é, portanto, prever o futuro: remover a página que ficará mais tempo sem ser acessada. Como não temos bola de cristal, os algoritmos são aproximações dessa previsão.
Algoritmo Ótimo (OPT)
O algoritmo ótimo é simples de enunciar: remova a página que só será usada mais longe no futuro (ou nunca mais). Ele é comprovadamente ótimo — gera o menor número possível de page faults.
O problema? É impossível de implementar. Exigiria saber, no momento da decisão, todos os acessos futuros do programa. Ele só pode ser calculado a posteriori, rodando o programa uma vez, registrando os acessos, e então analisando.
Então por que estudá-lo? Porque ele é o baseline teórico. Ao avaliar um algoritmo real, comparamos seu número de faults com o do OPT: quanto mais próximo, melhor o algoritmo.
Referências: 7 0 1 2 0 3 0 4 2 3 0 3 2
3 frames. Quando precisa despejar, OPT olha o FUTURO:
Acesso ao '3' com frames [7,0,1] cheios:
- 7 será usado? Não aparece mais → despeja o 7. ✔
NRU: Not Recently Used
O NRU é a primeira aproximação prática, e usa dois bits que já conhecemos da PTE (Parte II):
- R (Referenced/Accessed): ligado pelo hardware quando a página é lida ou escrita.
- M (Modified/Dirty): ligado pelo hardware quando a página é escrita.
Periodicamente (a cada tick de clock), o kernel zera o bit R de todas as páginas. Assim, R indica se a página foi acessada recentemente. Combinando R e M, formam-se 4 classes:
Classe 0: não referenciada, não modificada (R=0, M=0) ← melhor vítima
Classe 1: não referenciada, modificada (R=0, M=1)
Classe 2: referenciada, não modificada (R=1, M=0)
Classe 3: referenciada, modificada (R=1, M=1) ← pior vítima
O NRU remove uma página aleatória da classe não-vazia mais baixa. A intuição: prefira despejar páginas não usadas recentemente (R=0) e, entre elas, as limpas (M=0, que não precisam de write-back). Simples e razoável, ainda que grosseiro.
FIFO e a Anomalia de Belady
O FIFO (First-In, First-Out) é o mais ingênuo: mantém uma fila das páginas na ordem em que entraram e despeja a mais antiga.
O problema é óbvio: a página mais antiga pode ser justamente a mais usada (pense numa variável de configuração carregada no início e acessada o tempo todo). O FIFO a despejaria cegamente.
Mas o FIFO tem um defeito ainda mais bizarro e contraintuitivo: a Anomalia de Belady. Normalmente esperamos que mais frames de memória → menos page faults. Com o FIFO, em certas sequências de acesso, adicionar frames pode aumentar o número de page faults:
Sequência: 1 2 3 4 1 2 5 1 2 3 4 5
Com 3 frames: 9 page faults
Com 4 frames: 10 page faults ← MAIS frames, MAIS faults! (anomalia)
Essa anomalia é o que motivou o estudo dos stack algorithms (algoritmos de pilha), como o LRU, que possuem a propriedade de inclusão: o conjunto de páginas com $n$ frames é sempre um subconjunto do conjunto com $n+1$ frames. Algoritmos de pilha nunca sofrem da Anomalia de Belady.
Segunda Chance e o Algoritmo do Relógio
O Segunda Chance é um FIFO esperto. Antes de despejar a página mais antiga, ele checa o bit R:
- Se R = 0: a página não foi usada recentemente → despeja.
- Se R = 1: dá uma "segunda chance" — zera o R, move a página para o fim da fila (como se tivesse acabado de chegar) e continua procurando.
Assim, páginas frequentemente usadas sobrevivem, enquanto páginas realmente antigas e não usadas são despejadas.
O Algoritmo do Relógio (Clock) é a implementação eficiente do Segunda Chance. Em vez de mover páginas numa fila (caro), organiza os frames num anel com um ponteiro (o "ponteiro do relógio"):
┌──────┐
┌───▶│ P0 R1│───┐
│ └──────┘ │
┌──────┐ ┌──────┐
│ P7 R0│ │ P1 R1│
└──────┘ └──────┘
▲ │
│ ┌──────┐ ▼
└────│ P... │◀──┘
└──────┘
▲
ponteiro
Ao precisar de vítima, o ponteiro avança:
- R=1 → zera R e avança (segunda chance)
- R=0 → despeja esta página, ponteiro para no próximo
O Clock é a base conceitual do que o Linux realmente usa (com refinamentos que veremos na Parte VII, nas LRU lists).
LRU: Least Recently Used
O LRU (Least Recently Used) parte de uma aposta poderosa: o passado recente é um bom preditor do futuro próximo. Ele despeja a página que há mais tempo não é acessada.
O LRU é excelente — muito próximo do ótimo na prática — mas caro de implementar exatamente. Manter a ordem exata de último acesso exigiria atualizar uma estrutura de dados a cada acesso à memória. Tanenbaum descreve as opções:
- Com timestamps/contador: cada página guarda o "tempo" do último acesso. Despejar = achar o menor timestamp. Requer hardware que escreva o contador a cada acesso — caro.
- Com matriz de bits: uma matriz $n \times n$ para $n$ frames, manipulada a cada referência. Inviável para muitos frames.
Por isso, sistemas reais usam LRU aproximado:
Aging (envelhecimento)
O algoritmo de aging aproxima o LRU com um contador por página. A cada tick, o kernel desloca o contador à direita e insere o bit R no topo:
Página A, ao longo de 5 ticks (bit R de cada tick à esquerda):
tick 1 (R=1): 10000000
tick 2 (R=0): 01000000
tick 3 (R=1): 10100000
tick 4 (R=0): 01010000
tick 5 (R=0): 00101000
Página com MENOR valor de contador = usada há mais tempo = vítima.
O aging captura bem a noção de "recentemente usada" com custo baixo, e é a inspiração direta do mecanismo de LRU do Linux. Uma limitação: o contador tem tamanho finito, então ele "esquece" o histórico além de N ticks — mas na prática isso é suficiente.
O Modelo do Working Set
Os algoritmos acima decidem qual página despejar. Mas Peter Denning propôs uma pergunta mais profunda: quantas páginas um processo realmente precisa ter na memória para rodar bem?
O working set $W(t, \Delta)$ é o conjunto de páginas que um processo acessou nas últimas $\Delta$ unidades de tempo (ou referências). É a formalização do "conjunto de trabalho atual":
$$W(t, \Delta) = {\text{páginas referenciadas no intervalo } (t - \Delta,\ t)}$$
A ideia-chave: se mantivermos o working set inteiro de um processo na memória, ele terá pouquíssimos page faults, porque suas referências, pela localidade, caem quase todas dentro do working set. Se não conseguirmos manter o working set na memória, o processo sofre — muito.
O tamanho do working set varia conforme o programa muda de fase (inicialização, hot loop, shutdown). O parâmetro $\Delta$ (a janela) é um trade-off: muito pequeno perde páginas ainda úteis; muito grande retém páginas já frias.
Conexão backend: aquele exemplo da Parte I volta com força. Uma API pode ter 500 MB carregados, mas seu working set num dado segundo é talvez 50 MB. Dimensionar a RAM (ou o limite do container) abaixo do working set é a receita para thrashing.
WSClock
O WSClock combina o melhor de dois mundos: a eficiência do algoritmo do relógio com a inteligência do working set. É o algoritmo prático de referência em muitos sistemas.
Ele percorre os frames em anel (como o Clock), mas para cada página examina:
Para a página sob o ponteiro:
- R = 1? → zera R, atualiza "tempo do último uso", avança.
- R = 0? → calcula idade = tempo_atual - tempo_último_uso
- idade ≤ Δ? → está no working set, NÃO despeja, avança.
- idade > Δ? → fora do working set:
- limpa? → despeja (ótima vítima!)
- suja? → agenda write-back, avança (despeja na próxima volta)
O WSClock só despeja páginas que estão fora do working set (não usadas há mais que $\Delta$), respeitando a localidade e evitando despejar páginas que serão logo reusadas. É, em essência, a filosofia que o Linux persegue com suas LRU lists e o mecanismo de reclaim (Parte VII).
Thrashing
Quando o working set combinado de todos os processos excede a memória física disponível, acontece o pesadelo: thrashing.
No thrashing, o sistema passa mais tempo movendo páginas entre RAM e disco do que executando trabalho útil. Cada processo despeja páginas de que ainda precisa; ao acessá-las de novo, dispara major faults; para atendê-los, despeja páginas de outro processo, que também sofre — uma reação em cadeia:
CPU útil
100% │────────╲
│ ╲
│ ╲ ← "penhasco" do thrashing
│ ╲________________
0%│
└────────────────────────────▶ grau de multiprogramação
▲
ponto de thrashing: demanda de memória > capacidade
Como detectar: a assinatura clássica do thrashing é CPU baixa + I/O de disco (swap) altíssimo. A CPU está ociosa não por falta de trabalho, mas porque todo mundo está esperando o disco.
# Sinais de thrashing:
vmstat 1
# r b swpd free ... si so ... us sy id wa
# 1 8 512000 2000 15000 18000 3 5 2 90
# ▲ ▲ ▲ ▲
# muito swap usado swap in/out ALTOS CPU 90% em I/O wait!
# A ferramenta moderna e muito mais precisa (PSI) veremos na Parte VII.
Prevenção: PFF (Page Fault Frequency)
Uma técnica de controle é o PFF (Page Fault Frequency): monitorar a taxa de page faults de cada processo e ajustar dinamicamente quantos frames ele recebe:
- Taxa de faults acima de um limite superior → o processo precisa de mais frames.
- Taxa abaixo de um limite inferior → o processo tem frames demais; pode ceder alguns.
Se não há frames suficientes para todos, o remédio drástico é suspender (fazer swap-out completo de) um processo inteiro, liberando seus frames para os demais rodarem sem thrashing — melhor sacrificar um do que travar todos. Essa ideia ecoa no OOM Killer do Linux (Parte VII).
Políticas de Alocação de Frames
Por fim: como distribuir os frames disponíveis entre os processos?
Alocação Global vs Local
Alocação local: cada processo tem um conjunto fixo de frames; ao precisar despejar, escolhe a vítima apenas entre suas próprias páginas. Oferece isolamento (o comportamento de um processo não afeta os outros), mas pode ser ineficiente — um processo pode ter frames sobrando enquanto outro passa fome.
Alocação global: a vítima é escolhida entre as páginas de todos os processos. Mais eficiente no uso agregado da memória, mas processos competem entre si — um processo "faminto" pode roubar frames de outros.
O Linux usa fundamentalmente uma abordagem global (o reclaim opera sobre LRU lists globais por zona/nó), mas os cgroups v2 (Parte VIII) reintroduzem fronteiras locais, permitindo limitar e isolar a memória por grupo de processos — o melhor dos dois mundos para containers.
Igual vs Proporcional
Ao alocar globalmente, como dividir? Igualmente entre processos é injusto (um processo pequeno não precisa do mesmo que um grande). A alocação proporcional dá frames na proporção do tamanho de cada processo, e variantes consideram prioridade — processos mais importantes recebem mais memória.
Esses conceitos teóricos são exatamente o que os controles de cgroup (memory.low, memory.high, memory.max) implementam na prática moderna — veremos na Parte VIII.
Continua na Parte VI, onde saímos da teoria e entramos numa das estruturas mais importantes (e menos compreendidas) do Linux: o page cache — o motivo pelo qual sua segunda leitura de um arquivo é instantânea — e o slab allocator, como o próprio kernel gerencia sua memória interna.
:D
Conteúdo parcialmente gerado com auxílio de IA generativa (me ajudou a organizar tudo isso kkkk)
Top comments (0)