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

161

Pelo meu entendimento, a coleta de lixo em Java limpa alguns objetos se nada mais estiver "apontando" para esse objeto.

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, bE cdeve ser lixo coletado, mas todos eles estão sendo referenciado por outros objetos.

Como a coleta de lixo Java lida com isso? (ou é simplesmente um dreno de memória?)

AlexeyMK
fonte
1
Veja: stackoverflow.com/questions/407855/… , especificamente a segunda resposta do @gnud.
Seth

Respostas:

161

O GC de Java considera os objetos "lixo" se eles não puderem ser acessados ​​através de uma cadeia iniciada em uma raiz de coleta de lixo, para que esses objetos sejam coletados. Mesmo que os objetos possam apontar um para o outro para formar um ciclo, eles ainda serão lixo se forem cortados da raiz.

Consulte a seção sobre objetos inacessíveis no Apêndice A: A verdade sobre a coleta de lixo no desempenho da plataforma Java: Estratégias e táticas para obter detalhes sangrentos.

Bill the Lizard
fonte
14
Você tem uma referência para isso? É difícil testá-lo.
Tangens
5
Eu adicionei uma referência. Você também pode substituir o método finalize () de um objeto para descobrir quando ele é coletado (embora essa seja a única coisa que eu recomendo usar finalize () para).
Bill o Lagarto
1
Apenas para esclarecer esse último comentário ... coloque uma instrução debug print no método finalize que imprime um ID exclusivo para o objeto. Você poderá ver todos os objetos que se referem um ao outro serem coletados.
Bill o Lagarto
4
"... inteligente o suficiente para reconhecer ..." parece confuso. GC não tem que reconhecer ciclos - eles são apenas inacessível, daí lixo
Alexander Malakhov
86
@tangens "Você tem uma referência para isso?" em uma discussão sobre coleta de lixo. Melhor. Trocadilho. Sempre.
Michał Kosmulski
139

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

How?

Existem objetos especiais chamados raízes de coleta de lixo (raízes da GC). Estes são sempre alcançáveis, assim como qualquer objeto que os tenha em sua própria raiz.

Um aplicativo Java simples possui as seguintes raízes de GC:

  1. Variáveis ​​locais no método principal
  2. A linha principal
  3. Variáveis ​​estáticas da classe principal

insira a descrição da imagem aqui

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

  1. O algoritmo percorre todas as referências a objetos, começando pelas raízes do GC, e marca todos os objetos encontrados como vivos.
  2. Toda a memória heap que não é ocupada por objetos marcados é recuperada. É simplesmente marcado como livre, essencialmente livre de objetos não utilizados.

Portanto, se algum objeto não estiver acessível a partir das raízes do GC (mesmo que seja auto-referenciado ou cíclico), ele será submetido à coleta de lixo.

É claro que às vezes isso pode levar ao vazamento de memória se o programador esquecer de desreferenciar um objeto.

insira a descrição da imagem aqui

Fonte: Gerenciamento de Memória Java

Aniket Thakur
fonte
3
Explicação perfeita! Obrigado! :)
Jovan Perovic
Obrigado por vincular esse livro. Está cheio de ótimas informações sobre este e outros tópicos de desenvolvimento Java!
Droj
14
Na última figura, há um objeto não alcançável, mas está na seção de objetos alcançáveis.
La VloZ Merrill 16/08
13

Um coletor de lixo inicia a partir de um conjunto "raiz" de locais que são sempre considerados "alcançáveis", como registros da CPU, pilha e variáveis ​​globais. Ele funciona encontrando qualquer ponteiro nessas áreas e encontrando recursivamente tudo o que aponta. Uma vez encontrado tudo isso, tudo o resto é lixo.

É claro que existem algumas variações, principalmente por uma questão de velocidade. Por exemplo, a maioria dos coletores de lixo modernos é "geracional", o que significa que eles dividem objetos em gerações e, à medida que um objeto envelhece, o coletor de lixo fica cada vez mais longo entre as vezes em que tenta descobrir se esse objeto ainda é válido ou não. - apenas começa a supor que, se tiver vivido muito tempo, as chances são muito boas de que ele continue a viver ainda mais.

No entanto, a idéia básica permanece a mesma: tudo se baseia em partir de um conjunto raiz de coisas que é dado como certo ainda podem ser usadas e, em seguida, buscar todos os indicadores para descobrir o que mais poderia estar em uso.

Interessante à parte: muitas vezes as pessoas se surpreendem com o grau de semelhança entre essa parte de um coletor de lixo e o código para organizar objetos para coisas como chamadas de procedimentos remotos. Em cada caso, você está começando a partir de um conjunto raiz de objetos e perseguindo ponteiros para encontrar todos os outros objetos aos quais se refere ...

Jerry Coffin
fonte
O que você está descrevendo é um coletor de rastreamento. Existem outros tipos de colecionadores. De particular interesse para esta discussão são colecionadores de contagem de referência, que não tendem a ter problemas com ciclos.
Jörg W Mittag
@ Jörg W Mittag: Certamente verdade - embora eu não conheça uma JVM (razoavelmente atual) que use contagem de referência, por isso parece improvável (pelo menos para mim) que faça muita diferença para a pergunta original.
Jerry Coffin
@ Jörg W Mittag: Pelo menos por padrão, acredito que o Jikes RVM atualmente use o coletor Immix, que é um coletor de rastreamento baseado em região (embora também use contagem de referência). Não tenho certeza se você está se referindo a essa contagem de referência ou a outro coletor que usa contagem de referência sem rastreamento (eu acho que o último, já que nunca ouvi falar do Immix chamando de "reciclador").
Jerry Coffin
Eu me confundi um pouco: o Recycler é (foi?) Implementado em Jalapeno, o algoritmo em que eu estava pensando, que é (foi?) Implementado em Jikes é a contagem de referência ulterior . Atlhough, é claro, dizer que o Jikes usa esse ou aquele coletor de lixo é bastante inútil, já que o Jikes e especialmente o MMtk são projetados especificamente para desenvolver e testar rapidamente diferentes coletores de lixo na mesma JVM.
Jörg W Mittag
2
O Ulterior Reference Counting foi projetado em 2003 pelas mesmas pessoas que criaram o Immix em 2007, então acho que o último provavelmente substituiu o primeiro. O URC foi projetado especificamente para poder ser combinado com outras estratégias e, de fato, o documento do URC menciona explicitamente que o URC é apenas um trampolim para um colecionador que combina as vantagens do rastreamento e da contagem de referências. Eu acho que Immix é aquele colecionador. De qualquer forma, o reciclador é uma pura colector de contagem de referência, o qual, no entanto, pode detectar e ciclos cobrar: WWW.Research.IBM.Com/people/d/dfb/recycler.html
Jörg W Mittag
13

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

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

E essa estratégia simples tem exatamente o problema que você descreve: se A fizer referência a B e B fazer referência a A, ambas as contagens de referência nunca poderão ser inferiores a 1, o que significa que nunca serão coletadas.

Existem quatro maneiras de lidar com esse problema:

  1. Ignore isto. Se você tiver memória suficiente, seus ciclos são pequenos e pouco frequentes e seu tempo de execução é curto, talvez você possa se safar simplesmente não coletando ciclos. Pense em um intérprete de script de shell: normalmente, os scripts de shell são executados por alguns segundos e não alocam muita memória.
  2. Combine seu coletor de lixo de contagem de referência com outro coletor de lixo que não tenha problemas com os 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 exigiria, assim você poderia usar um desses.
  4. Não implemente o algoritmo da maneira ingênua que você e eu: desde a década de 1970, foram desenvolvidos vários algoritmos bastante interessantes que combinam detecção de ciclo e contagem de referência em uma única operação, de maneira inteligente e significativamente mais barata do que qualquer um deles. separadamente ou executando um coletor de rastreamento.

A propósito, a outra maneira principal de implementar um coletor de lixo (e eu já sugeri isso algumas vezes acima) é traçar . Um coletor de rastreamento é baseado no conceito de alcançabilidade . Você começa com um conjunto raiz que você sabe que está sempre acessível (constantes globais, por exemplo, ou a Objectclasse, o escopo lexical atual, o quadro de pilha atual) e a partir daí você rastreia todos os objetos que são acessíveis a partir do conjunto raiz. todos os objetos acessíveis a partir dos objetos acessí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, mas não é acessível a partir do conjunto raiz, ele será coletado.

Jörg W Mittag
fonte
1
Como a pergunta é específica do Java, acho que vale a pena mencionar que o Java não usa contagem de ref e, portanto, o problema não existe. Também o link para a wikipedia seria útil como "leitura adicional". Caso contrário, excelente visão geral!
Alexander Malakhov
Acabei de ler seus comentários ao post de Jerry Coffin, então agora eu não sou tão certo :)
Alexander Malakhov
8

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

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

Portanto, no seu caso, quando as variáveis ​​locais a, bec estiverem fora do escopo no final do seu método, não haverá mais raízes do GC que contenham, direta ou indiretamente, uma referência para qualquer um dos seus três nós, e eles serão elegíveis para a coleta de lixo.

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

Sbodd
fonte
"... atualmente na pilha de um encadeamento em execução ..." não está varrendo pilhas de todos os encadeamentos para não corromper os dados de outros encadeamentos?
Alexander Malakhov
6

Este artigo (não está mais disponível) detalha o coletor de lixo (conceitualmente ... existem várias implementações). A parte relevante para sua postagem é "A.3.4 Inacessível":

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

TofuBeer
fonte
1
link direto para essa seção #
Alexander Malakhov
1
os links não estão mais disponíveis
titus
1

Coleta de lixo geralmente não significa "limpar algum objeto se nada mais estiver" apontando "para esse objeto" (isso é contagem de referência). A coleta de lixo significa aproximadamente encontrar objetos que não podem ser alcançados no programa.

Portanto, no seu exemplo, depois que a, bec estão fora do escopo, eles podem ser coletados pelo GC, pois você não pode mais acessar esses objetos.

Amnon
fonte
"Coleta de lixo significa aproximadamente encontrar objetos que não podem ser alcançados pelo programa". Na maioria dos algoritmos de GC, é realmente o contrário. Você começa com as raízes do GC e vê o que pode encontrar, o resto é considerado lixo não referenciado.
11119 Fredrik
1
A contagem de referência é uma das duas principais estratégias de implementação para coleta de lixo. (A outra é traçado.)
Jörg W Mittag
3
@ Jörg: Atualmente, na maioria das vezes, quando as pessoas falam sobre coletores de lixo, estão se referindo a coletores com base em algum tipo de algoritmo de mark'n'sweep. A contagem de referências normalmente é o que você fica preso se não tiver um coletor de lixo. É verdade que a contagem de ref é, de certo modo, uma estratégia de coleta de lixo, mas dificilmente existe um GC atualmente construído sobre ele, dizendo que é uma estratégia de GC apenas confundindo as pessoas porque, na prática, não é mais um GC estratégia, mas uma maneira alternativa de gerenciar a memória.
11409 Fredrik
1

Bill respondeu sua pergunta diretamente. Como Amnon disse, sua definição de coleta de lixo é apenas uma contagem de referência. Eu só queria acrescentar que mesmo algoritmos muito simples, como marcar e varrer e copiar coleção, lidam facilmente com referências circulares. Então, nada de mágico nisso!

Claudiu
fonte