Como o Java Garbage Collection trabalha com referências circulares?

Pelo que entendi, a garbage collection em Java limpa algum object, se nada mais estiver “apontando” para esse object.

Minha pergunta é: o que acontece se tivermos algo assim:

class Node { public object value; public Node next; public Node(object o, Node n) { value = 0; next = n;} } //...some code { Node a = new Node("a", null), b = new Node("b", a), c = new Node("c", b); a.next = c; } //end of scope //...other code 

a , b e c devem ser coletados como lixo, mas todos eles estão sendo referenciados por outros objects.

Como a garbage collection Java lida com isso? (ou é simplesmente um dreno de memory?)

O GC do Java considera objects “lixo” se eles não puderem ser acessados ​​através de uma cadeia que começa em uma raiz de garbage collection, então esses objects serão coletados. Mesmo que os objects apontem um para o outro para formar um ciclo, eles ainda são lixo se forem cortados da raiz.

Consulte a seção sobre objects inacessíveis no Apêndice A: A verdade sobre a garbage collection no desempenho da plataforma Java: estratégias e táticas para obter detalhes importantes.

sim coletor de lixo de Java lida com referência circular!

 How? 

Existem objects especiais chamados de raízes de garbage collection (raízes do GC). Estes são sempre alcançáveis ​​e assim é qualquer object que os tenha em sua própria raiz.

Um aplicativo Java simples tem as seguintes raízes do GC:

  1. Variáveis ​​locais no método principal
  2. O segmento principal
  3. Variáveis ​​estáticas da class principal

insira a descrição da imagem aqui

Para determinar quais objects não estão mais em uso, a JVM executa intermitentemente o que é muito apropriadamente chamado de algoritmo de marca e varredura . Funciona da seguinte maneira

  1. O algoritmo percorre todas as referências de objects, começando pelas raízes do GC, e marca cada object encontrado como ativo.
  2. Toda a memory heap que não é ocupada por objects marcados é recuperada. É simplesmente marcado como livre, essencialmente livre de objects não utilizados.

Portanto, se algum object não puder ser acessado a partir das raízes do GC (mesmo que seja auto-referenciado ou cíclico), ele será submetido à garbage collection.

É claro que, às vezes, isso pode levar a memory leaks se o programador se esquecer de cancelar a referência a um object.

insira a descrição da imagem aqui

Fonte: Gerenciamento de Memória Java

Um coletor de lixo inicia a partir de um conjunto “raiz” de locais que são sempre considerados “acessíveis”, como os registradores da CPU, pilha e variables ​​globais. Ele funciona encontrando quaisquer pointers nessas áreas e, de forma recursiva, encontra tudo o que eles apontam. Uma vez encontrado tudo isso, todo o resto é lixo.

Existem, claro, algumas variações, principalmente por causa da velocidade. Por exemplo, a maioria dos coletores de lixo modernos é “geracional”, o que significa que eles dividem objects em gerações e, à medida que um object envelhece, o coletor de lixo demora cada vez mais tempo para tentar descobrir se esse object ainda é válido ou não – apenas começa a supor que, se viveu muito tempo, é muito provável que continue a viver ainda mais.

No entanto, a idéia básica permanece a mesma: tudo é baseado em começar de um conjunto de coisas que ele toma como garantido ainda pode ser usado, e depois perseguir todos os pointers para encontrar o que mais poderia estar em uso.

Interessante de lado: as pessoas geralmente ficam surpresas com o grau de semelhança entre essa parte de um coletor de lixo e o código para empacotamento de objects para coisas como chamadas de procedimento remoto. Em cada caso, você está iniciando a partir de um conjunto de objects raiz e perseguindo pointers para encontrar todos os outros objects aos quais eles se referem …

Você está certo. A forma específica de garbage collection que você descreve é ​​chamada de ” contagem de referência “. O modo como funciona (conceitualmente, pelo menos, as implementações mais modernas de contagem de referência são realmente implementadas de forma bastante diferente) no caso mais simples, é assim:

  • sempre que uma referência a um object é adicionada (por exemplo, é atribuída a uma variável ou um campo, passada para o método e assim por diante), sua contagem de referência é aumentada em 1
  • sempre que uma referência a um object é removida (o método retorna, a variável sai do escopo, o campo é reatribuído a um object diferente ou o object que contém o campo se coleta como lixo), a contagem de referência é diminuída em 1
  • assim que a contagem de referência atinge 0, não há mais referência ao object, o que significa que ninguém pode usá-lo mais, portanto é lixo e pode ser coletado

E essa estratégia simples tem exatamente o problema que você descreve: se A faz referência às referências B e B A, então ambas as contagens de referência nunca podem ser menores que 1, o que significa que elas nunca serão coletadas.

Existem quatro maneiras de lidar com esse problema:

  1. Ignore isto. Se você tiver memory suficiente, seus ciclos são pequenos e pouco freqüentes e seu tempo de execução é curto, talvez você consiga simplesmente não acumular ciclos. Pense em um interpretador de script de shell: os scripts de shell geralmente são executados apenas por alguns segundos e não alocam muita memory.
  2. Combine seu coletor de lixo de contagem de referência com outro coletor de lixo que não tenha problemas com ciclos. O CPython faz isso, por exemplo: o coletor de lixo principal no CPython é um coletor de contagem de referência, mas, de tempos em tempos, um coletor de lixo de rastreamento é executado para coletar os ciclos.
  3. Detecte os ciclos. Infelizmente, detectar ciclos em um gráfico é uma operação bastante cara. Em particular, requer praticamente a mesma sobrecarga que um coletor de rastreamento, então você pode usar um deles.
  4. Não implemente o algoritmo da maneira ingênua que você e eu faríamos: desde a década de 1970, existem vários algoritmos bastante interessantes desenvolvidos que combinam detecção de ciclo e contagem de referência em uma única operação de uma maneira inteligente que é significativamente mais barata do que ambos separadamente ou fazendo um coletor de rastreamento.

By the way, a outra maneira importante para implementar um coletor de lixo (e eu já sugeri que algumas vezes acima), está traçando . Um coletor de rastreamento é baseado no conceito de acessibilidade . Você começa com algum conjunto de raízes que você sabe que está sempre acessível (constantes globais, por exemplo, ou a class Object , o escopo léxico atual, o quadro de pilha atual) e a partir daí você rastreia todos os objects alcançáveis ​​a partir do conjunto raiz. então todos os objects que são alcançáveis ​​a partir dos objects alcançáveis ​​a partir do conjunto raiz e assim por diante, até que você tenha o fechamento transitivo. Tudo o que não está nesse fechamento é lixo.

Como um ciclo é acessível apenas dentro de si mesmo, mas não alcançável a partir do conjunto raiz, ele será coletado.

Os Java GCs não se comportam como você descreve. É mais correto dizer que eles começam a partir de um conjunto básico de objects, freqüentemente chamados de “raízes do GC”, e coletam qualquer object que não possa ser alcançado a partir de uma raiz.
As raízes do GC incluem coisas como:

  • variables ​​estáticas
  • variables ​​locais (incluindo todas as referências ‘this’ aplicáveis) atualmente na pilha de um encadeamento em execução

Então, no seu caso, uma vez que as variables ​​locais a, b e c saem do escopo no final do seu método, não há mais raízes do GC que contenham, direta ou indiretamente, uma referência a qualquer um dos seus três nós, e eles estarão qualificados para a garbage collection.

O link do TofuBeer tem mais detalhes, se você quiser.

Este artigo (não está mais disponível) entra em profundidade sobre o coletor de lixo (conceitualmente … existem várias implementações). A parte relevante para o seu post é “A.3.4 Inacessível”:

A.3.4 Inacessível Um object entra em um estado inacessível quando não existem mais referências fortes a ele. Quando um object é inacessível, ele é um candidato para coleta. Observe a redação: só porque um object é um candidato para coleta não significa que ele será imediatamente coletado. A JVM está livre para atrasar a coleta até que haja uma necessidade imediata de a memory ser consumida pelo object.

A garbage collection geralmente não significa “limpar algum object se nada mais estiver ‘apontando’ para esse object” (isso é contagem de referência). A garbage collection significa, aproximadamente, encontrar objects que não podem ser acessados ​​pelo programa.

Portanto, no seu exemplo, depois que a, b e c saem do escopo, eles podem ser coletados pelo GC, já que você não pode mais acessar esses objects.

Bill respondeu sua pergunta diretamente. Como Amnon disse, sua definição de garbage collection é apenas contagem de referência. Eu só queria acrescentar que mesmo algoritmos muito simples, como marcar, varrer e copiar, manipulam facilmente referências circulares. Então, nada de magia nisso!