Каковы алгоритмы GC с низкой паузой?

12

Некоторые языки, например Java, ввели GC с низкой паузой.

Эти GC могут сделать большую часть работы, не останавливая весь мир. Это, очевидно, довольно сложная проблема, потому что она требует анализа памяти, когда поток ее модифицирует, что приводит к получению данных, которые можно использовать в начале процесса, и не больше, когда он завершается, или к данным, которые кажутся ненужными, а потому, что ссылка была перенесена в память и никогда не появлялась там, где смотрел ГК.

Так в принципе, что за алгоритм (ы) за этим?

Исследовательские работы или действительно техническая ссылка на статью будут рассматриваться как правильный ответ, так как эта тема действительно техническая.

deadalnix
источник

Ответы:

16

Так в принципе, что за алгоритм (ы) за этим?

Это в основном алгоритм метки и развертки, который «просто» работает одновременно в отдельном потоке.

Что касается исследовательских работ на эту тему:

сокол
источник
5

Насколько я понимаю, сборщик мусора в Java G1 использует так называемые области кучи, чтобы не останавливать весь мир. Я вижу это так: хотя один из регионов заблокирован GC, выполняющим очистку, выделение памяти выполняется в другом регионе.

Вот объяснение от Джереми Мэнсона :

Принцип прост: сборщик разбивает кучу на области фиксированного размера и отслеживает текущие данные в этих областях. Он сохраняет набор указателей - «запомненный набор» - в и из региона. Когда GC считается необходимым, он сначала собирает регионы с меньшим количеством живых данных (следовательно, «мусор первым»). Зачастую это может означать сбор всей области за один шаг: если количество указателей на область равно нулю, тогда не нужно делать отметку или развертку этой области ...

комар
источник
5

JVM IBM в реальном времени использует сборщик мусора под названием Metronome, который разделяет действия GC на дискретные кванты и чередует их с обработкой приложений. Таким образом, в основном вместо периодических (и недетерминированных) остановок GC «остановка мира» приложение работает немного медленнее, в то время как GC выполняется параллельно.

Есть еще один GC, который выполняет динамическую дефрагментацию и отвечает жестким требованиям реального времени, но единственная ссылка, которую я могу найти, - здесь (требуется членство в ACM).

Интересный одновременный сборщик мусора в режиме реального времени без остановок . Он использует традиционный подход с разметкой и разверткой, но предназначен для использования в многопроцессорных системах и поддерживает параллельную многопоточность без блокировок.

TMN
источник
Ницца ! Жаль, что у меня нет доступа к ACM, эта статья выглядит действительно интересной.
Deadalnix
2

Причина этого в том, что в Java только GC может освободить память, которая может содержать ссылки GC. Это означает, что до тех пор, пока вы можете безопасно читать объекты в отдельном потоке, вам нужно будет только приостановить программу, чтобы просмотреть ссылки в стеке.

Я предложил бы для мутации, чтобы они внедрили некоторую форму копирования при записи, чтобы сообщить GC об изменении.

DeadMG
источник
Этого недостаточно, если эти ссылки могут быть обновлены в любое время любым потоком.
Deadalnix