Существует множество различных алгоритмов, которые можно использовать для реализации сборки мусора. Не все из них демонстрируют поведение, которое вы упоминаете.
В случае вашего вопроса вы имеете в виду алгоритмы, которые используют форму разметки. Если мы возьмем JSM HostSpot в качестве примера, старое поколение может быть собрано с помощью сборщика CMS. При этом используется фаза маркировки, на которой помечаются все объекты, доступные из кода приложения. Первоначально создается root набор непосредственно доступных объектов (ссылки на объекты в стеке, регистры и т. Д. c.). Каждый объект в этом наборе имеет бит метки, установленный в его заголовке, чтобы указать, что он все еще используется. Все ссылки из этих объектов отслеживаются рекурсивно, и в конечном итоге каждый доступный объект имеет установленный бит метки. Время, необходимое для этого, пропорционально количеству живых объектов, а не размеру кучи.
Затем фаза развертки должна охватить всю кучу, найти объекты с установленным битом метки и определить промежутки между ними, чтобы их можно было добавлять в свободные списки. Они используются для выделения места для объектов, продвигаемых молодым поколением. Так как вся куча должна быть очищена, время, которое занимает , пропорционально размеру кучи, независимо от того, сколько данных в куче находится в реальном времени.
В случае G1, алгоритм аналогичен, но каждое поколение кучи разделено на регионы, чтобы пространство можно было использовать более эффективным образом.