Como um coletor de lixo simultâneo lida com variáveis?

8

Digamos que seja um coletor de lixo simultâneo de marcação e varredura.

Quando esse GC lida com ponteiros constantes, apenas os percorre (a partir das raízes) e marca todos os blocos de dados encontrados. Em seguida, varre tudo sem marcação. Um código de cliente deve marcar os blocos de dados que ele usa como raízes.

Mas o que fazer com variáveis? Aqui está uma situação:

  1. Vé uma variável, que armazena um ponteiro para o objeto A.
  2. Thread 1Ve suspende.
  3. Thread 2modifica Ve faz apontar para o objeto B.
  4. O coletor de lixo executa sua fase de "marcação" e encontra os que Anão são mais referenciados, depois o desaloca durante a fase de "varredura".
  5. Thread 1desperta e tenta usar A(já lido Vna etapa 2) marcando-o como root. E falha , porque Anão existe mais.

Então, como lidar com isso?

O Thread 2pode marcar o objeto substituído Acom um sinalizador especial de não remover (um sinalizador semelhante é usado para objetos alocados recentemente). Mas quando esse sinalizador deve ser removido? Claro que Thread 1poderia fazer isso. Mas Thread 2não sabe nada Thread 1e, portanto, não pode ter certeza de que isso será feito sempre. Isso pode levar a Anunca será liberado. E se o GC remover esse sinalizador, nada impede que ele Aseja removido quando o GC for executado pela segunda vez ...

As descrições rápidas e rápidas de coletores de lixo que li e lembrei de mencionar que o objeto substituído deve estar "acinzentado". Mas sem detalhes específicos. Um link para uma descrição mais detalhada da solução seria muito apreciado.

lorus
fonte

Respostas:

4

Dependendo dos detalhes precisos da implementação do coletor de lixo, isso pode não ser um problema na etapa 4. Por exemplo, na etapa 2, o encadeamento 1 presumivelmente lê Vum registro. O coletor de lixo provavelmente precisará examinar o conteúdo dos registros para todos os segmentos ativos (em execução e suspensos) para verificar se há uma referência a qualquer objeto mantido nos registros.

Inevitavelmente, uma implementação de coletor de lixo está fortemente acoplada ao ambiente operacional (e segmentado) no qual é executado. Existem muitas técnicas de implementação para garantir que todas as referências armazenadas e transitórias sejam consideradas.

Greg Hewgill
fonte
Mas existe alguma maneira de fazer isso de forma independente da plataforma? O registro pode conter os dados, que apenas parecem um ponteiro, mas na verdade não são. A implementação do meu GC é exata e depende do fato de que qualquer ponteiro que ele processa aponta para um bloco de dados de determinada estrutura.
Lorus
Hmm, mas isso é uma ideia! Eu posso colocar esse ponteiro em algum lugar conhecido na pilha (ou variável local de thread) e fazer o GC examiná-lo.
Lorus 6/03
@lorus - para muitos coletores de lixo, as tabelas geradas pelo compilador informam ao GC o que os registradores contêm ponteiros em qualquer ponto do método. Para outros, o GC é executado apenas em um "ponto seguro" que invalida implicitamente o conteúdo do registro. Além disso, as implementações de GC são inerentemente dependentes da plataforma em algum nível.
Stephen C
@StephenC Bem, eu não penso assim algoritmo de propósito geral como coleta de lixo exige ser tão plataforma-dependente. Operações atômicas e barreiras de memória - sim. Mas acesso direto aos registros? Não, eu não penso assim. Seria eficiente, mas acredito que não é absolutamente necessário. Gostaria de saber mais sobre esses algoritmos independentes de plataforma.
Lorus
0

Você precisa marcar variáveis ​​locais em algum momento durante a fase de marcação. Todas as variáveis ​​locais, incluindo aquelas que normalmente vivem na pilha. De alguma forma.

Além disso, acho que isso deve ser feito durante a fase síncrona (todos os mutadores parados) da verificação de objetos modificados. De fato, o mesmo problema pode surgir mesmo sem considerar variáveis ​​/ registros locais. Considere o objeto A apontando para nulo e o objeto B apontando para C. Agora, você digitaliza o objeto A, um encadeamento mutador vem, copia a referência para C de B para A, anula B. E agora você começa a digitalizar B. E C escorregou debaixo dos seus dedos.

Não conheço nenhuma maneira de lidar com isso que não envolva parar os mutadores. A técnica usual é no final da fase de marcação para parar todos os mutadores e marcar novamente todos os objetos que eles sofreram mutação durante a fase principal de marcação. E inclua pilhas e registros nisso.

Normalmente, os registros de marcação são contornados, fazendo-o de forma síncrona chamando o coletor no encadeamento algumas vezes. Dentro da função de coletor, apenas suas próprias variáveis ​​locais (que não são raízes) podem estar nos registradores, todas as outras variáveis ​​locais na cadeia de chamadas estão na pilha, para que você possa caminhar pela pilha.

Como alternativa, você pode enviar um sinal para o thread. O manipulador de sinal forçará novamente todas as variáveis ​​na pilha, para que você possa acompanhá-las. A desvantagem desse método é que ele depende da plataforma.

Jan Hudec
fonte
Sim. Mas a situação de que se estava falando não se trata de uma variável local. Trata-se de um global, que pode ser acessado e modificado simultaneamente por diferentes threads.
Lorus
se depois de thread1 tem V leitura e um não é em uma variável local de thread1 então A não será acessível após thread2 V modificado, por isso vai estar pronto para a coleta de qualquer maneira
aberração catraca
@lorus: Se um thread carrega algo no registrador, o registro é sua variável local. Se foi mencionado na fonte de alto nível ou adicionado pelo compilador, não importa. Você apenas o trata como variável local.
Jan Hudec
@JanHudec Ok. Agora eu entendi. Então, chamar o coletor no encadeamento (cliente) é realmente algum tipo de bloqueio global?
Lorus
1
@JanHudec a menos que os tópicos trabalhar com o GC e pode adicionar objetos a uma fila-a marca, cada vez que um thread lê uma referência
aberração catraca