Quais são os algoritmos por trás do GC de baixa pausa?

12

Alguns idiomas, por exemplo, java, introduziram um GC de baixa pausa.

Esses GC podem fazer a maior parte do trabalho sem fazer uma pausa no mundo inteiro. Obviamente, esse é um problema bastante difícil, pois exige a análise da memória quando o thread está sendo modificado, resultando em dados que podem ser usados ​​no início do processo e não mais quando ele termina ou em dados que parecem ser lixo, mas porque o a referência foi movida na memória e nunca apareceu para onde o GC estava olhando.

Então, basicamente, qual é o algoritmo por trás disso?

Trabalhos de pesquisa ou link de artigo realmente técnico seriam considerados uma resposta válida, pois esse tópico é realmente técnico.

deadalnix
fonte

Respostas:

16

Então, basicamente, qual é o algoritmo por trás disso?

É basicamente um algoritmo de marcação e varredura que "apenas" é executado simultaneamente em um thread separado.

Quanto aos trabalhos de pesquisa sobre esse assunto:

Falcão
fonte
5

Até onde eu entendi, o coletor de lixo Java G1 usa as chamadas regiões de heap para evitar pausar o mundo inteiro. A meu ver, enquanto uma das regiões está bloqueada pelo GC executando a limpeza, a alocação de memória é feita em outra região.

Aqui está uma explicação de Jeremy Manson :

O princípio é simples: o coletor divide a pilha em regiões de tamanho fixo e rastreia os dados ativos nessas regiões. Ele mantém um conjunto de indicadores - o "conjunto lembrado" - dentro e fora da região. Quando um GC é considerado necessário, ele coleta primeiro as regiões com menos dados ativos (portanto, "primeiro o lixo"). Freqüentemente, isso pode significar coletar uma região inteira em uma única etapa: se o número de ponteiros em uma região for zero, não será necessário marcar ou varrer essa região ...

mosquito
fonte
5

A JVM da IBM em tempo real usa um coletor de lixo chamado Metronome que divide a atividade do GC em quanta discretos e os intercala com o processamento do aplicativo. Então, basicamente, em vez de pausas periódicas (e não determinísticas) do GC de parada mundial, o aplicativo é executado um pouco mais devagar enquanto o GC é feito em paralelo.

Há outro GC que faz a desfragmentação dinâmica e atende aos requisitos de tempo real, mas a única referência que posso encontrar é aqui ( é necessária a associação ao ACM).

Um interessante coletor de lixo simultâneo em tempo real é ininterrupto . Ele usa a abordagem tradicional de marcação e varredura, mas foi projetado para uso em sistemas multiprocessadores e suporta multithreading simultâneo sem bloqueio.

TMN
fonte
Agradável ! Pena que não tenho acesso ao ACM, este artigo parece realmente interessante.
Deadalnix
2

O motivo pelo qual ele funciona é porque, em Java, apenas o GC pode liberar memória que pode conter referências ao GC. Isso significa que, desde que você possa ler objetos em um encadeamento separado com segurança, você só precisará pausar o programa para observar as referências na pilha.

Eu sugeriria por mutação que eles implementassem alguma forma de copiar na gravação para informar o GC sobre a mudança.

DeadMG
fonte
Isso não é suficiente, desde que essas referências possam ser atualizadas a qualquer momento por qualquer encadeamento.
Deadalnix