Revisão da Coleta de Lixo

Os algoritmos de coleta de lixo fundamentam-se em três abordagens principais: marcação-varredura, marcação-cópia e marcação-compactação. A introdução de gerações (jovem e idosa) permite a utilização de diferentes estratégias por faixa etária, otimizando a eficiência global de alocação e recuperação de memória.

Independentemente da técnica escolhida, a fase de marcação é indispensável, pois identifica quais objetos estão ativos e quais podem ser descartados. O processo geral do coletor de lixo compreende:

1. Identificar objetos vivos versus recicláveis;
2. Executar a limpeza (varredura, cópia ou compactação), atualizando referências se os objetos forem relocados.

Marcação Tridimensional

Fnudamentos do Algoritmo

Através da análise de alcançabilidade, inicia-se a partir das GC Roots uma travessia pelos objetos referenciados. Durante este percurso, cada objeto é categorizado conforme seu estado de visitação:

• Branco: Ainda não visitado.
• Preto: Visitado e todas as suas referências também foram processadas.
• Cinza: Visitado, mas suas referências ainda não foram completamente verificadas. Ao finalizar, torna-se preto.

Considerando conjuntos para cada cor, o algoritmo procede da seguinte forma:

1. Inicialmetne, todos os objetos pertencem ao conjunto branco;
2. Objetos diretamente acessíveis pelas GC Roots são movidos para o conjunto cinza;
3. Para cada objeto cinza:
   • 3.1. Transferir seus referenciados para o conjunto cinza;
   • 3.2. Mover o próprio objeto para o conjunto preto.
4. Repetir o passo 3 até esvaziar o conjunto cinza;
5. Objetos remanescentes no branco são inalcançáveis e elegíveis para coleta.

Em modo Stop The World (STW), as referências permanecem estáticas, simplificando a marcação. Contudo, em marcação concorrente, alterações nas referências podem levar a imprecisões como objetos flutuantes ou omissões.

Excesso de Marcação - Lixo Flutuante

Suponha que o objeto E, já marcado como cinza, tenha sua referência removida por uma thread da aplicação (objD.campoE = null). Os objetos E, F e G tornam-se inacessíveis, mas como E já foi processado, permanecem marcados como vivos nesta rodada, sendo coletados apenas posteriormente. Esta memória não recuperada imediatamente constitui o lixo flutuante, que não compromete a correção do programa. Novos objetos criados durante a marcação concorrente são geralmente tratados como pretos, também podendo gerar lixo flutuante.

Submarcação - Barreiras de Acesso

Considere o cenário onde a thread de coleta está no objeto cinza E quando a aplicação executa:

var obj = objE.campoG;
objE.campoG = null;   // Rompe referência de E para G
objD.campoG = obj;    // D, já preto, referencia G branco

Retomando a coleta, E não mais referencia G, impedindo sua adição ao cinza. Apesar de D referenciar G, sua cor preta impede nova verificação. Consequentemente, G permanece branco e é incorretamente coletado. Isto viola a integridade da aplicação.

A submarcação ocorre sob duas condições simultâneas:

1. Um objeto cinza perde a referência a um branco;
2. Um objeto preto passa a referenciar esse mesmo branco.

Intervenções nas operações de leitura ou escrita podem registrar o objeto G para processamento posterior, assegurando sua marcação adequada.

Barreiras de Escrita

A operação de escrita em um campo é interceptável através de barreiras, que adicionam lógica antes ou após a atribuição:

void escrever_campo(oop* campo, oop novo_valor) {
    pre_barreira_escrita(campo);   // Ação pré-escrita
    *campo = novo_valor;
    pos_barreira_escrita(campo, novo_valor);  // Ação pós-escrita
}

Barreira com SATB

Ao alterar uma referência, registra-se o valor anterior para preservar o estado original do grafo de objetos (Snapshot At The Beginning):

void pre_barreira_escrita(oop* campo) {
    oop valor_antigo = *campo;
    conjunto_remark.adicionar(valor_antigo);
}

Esta abordagem assegura que referências rompidas sejam reconsideradas, prevenindo submarcação.

Barreira com Atualização Incremental

Novas referências inseridas são capturadas para processamento posterior:

void pos_barreira_escrita(oop* campo, oop novo_valor) {
    if(fase_gc == MARCA_CONCORRENTE && !esta_marcado(campo)) {
        conjunto_remark.adicionar(novo_valor);
    }
}

Desta forma, referências recentes a objetos brancos são marcadas adequadamente.

Barreiras de Leitura

Interceptando operações de leitura, objetos acessados são registrados preventivamente:

oop ler_campo(oop* campo) {
    pre_barreira_leitura(campo);
    return *campo;
}

void pre_barreira_leitura(oop* campo) {
    if(fase_gc == MARCA_CONCORRENTE && !esta_marcado(campo)) {
        oop valor_lido = *campo;
        conjunto_remark.adicionar(valor_lido);
    }
}

Esta técnica conservadora garante que objetos lidos durante a marcação não sejam omitidos.

Aplicação em Coletores Modernos

Coletores contemporâneos empregam variações da marcação tridimensional e barrieras de acesso:

• CMS: Utiliza barreira de escrita com atualização incremental;
• G1: Adota barreira de escrita com SATB;
• ZGC: Implementa barreira de leitura.