Какой алгоритм поиска объектов использует Garbage Collector?

Алгоритмы поиска объектов в Garbage Collector

Garbage Collector (сборщик мусора) использует несколько алгоритмов для обнаружения и удаления неиспользуемых объектов. Рассмотрим основные подходы и их реализацию в различных GC алгоритмах Java.

1. Mark-Sweep (Маркировка и Удаление)

Это один из самых старых и базовых алгоритмов, используемых в GC.

Фаза 1: Mark (Маркировка)

GC исходит из корневых объектов (root objects) и рекурсивно отмечает все достижимые объекты:

public class MarkSweepSimulation {
    // Корневые объекты (root references)
    static class Root {
        Object reference1;
        Object reference2;
    }
    
    // Пример GC маркировки (DFS)
    static class SimpleGarbageCollector {
        private Set<Object> marked = new HashSet<>();
        private Stack<Object> toProcess = new Stack<>();
        
        public void mark(Object root) {
            if (root == null || marked.contains(root)) return;
            
            marked.add(root);
            toProcess.push(root);
            
            // DFS - Depth-First Search через граф объектов
            while (!toProcess.isEmpty()) {
                Object current = toProcess.pop();
                
                // Получаем все ссылки из текущего объекта
                List<Object> references = getObjectReferences(current);
                for (Object ref : references) {
                    if (ref != null && !marked.contains(ref)) {
                        marked.add(ref);
                        toProcess.push(ref);
                    }
                }
            }
        }
        
        public void sweep(Collection<Object> allObjects) {
            // Удаляем все неотмеченные объекты
            List<Object> toRemove = new ArrayList<>();
            for (Object obj : allObjects) {
                if (!marked.contains(obj)) {
                    toRemove.add(obj);
                }
            }
            
            // Освобождаем память
            for (Object obj : toRemove) {
                deallocate(obj);
            }
            
            marked.clear();
        }
        
        private List<Object> getObjectReferences(Object obj) {
            // В реальности используется reflection или introspection
            return new ArrayList<>();
        }
        
        private void deallocate(Object obj) {
            // Освобождение памяти
        }
    }
}

Фаза 2: Sweep (Удаление)

Удаляются все объекты, которые не были отмечены на фазе маркировки.

Проблема: Фрагментация памяти

2. Generational GC (Поколенческий сборщик мусора)

Это самый распространённый алгоритм в современной Java (используется в G1GC, ZGC).

Принцип: Молодые объекты умирают быстро, старые объекты живут долго.

public class GenerationalGCExample {
    // Young Generation (Eden, Survivor S0, S1)
    // Old Generation (Tenured Space)
    
    static class GenerationalCollector {
        private Queue<Object> youngGeneration = new LinkedList<>();
        private Queue<Object> oldGeneration = new LinkedList<>();
        private int promotionThreshold = 15;  // После 15 GC переходит в Old Gen
        
        public void allocate(Object obj) {
            youngGeneration.add(obj);
        }
        
        public void collectYoungGeneration() {
            // Minor GC - часто, быстро
            markAndSweepYoung();
        }
        
        public void collectOldGeneration() {
            // Full GC - редко, медленно
            markAndSweepOld();
        }
        
        private void markAndSweepYoung() {
            Set<Object> alive = new HashSet<>();
            
            // Маркируем достижимые из Young Gen
            markReachableFromRoots(youngGeneration, alive);
            
            // Маркируем ссылки из Old Gen в Young Gen
            markReachableFromOldGen(alive);
            
            // Survivor objects переходят в Old Gen если возраст > threshold
            for (Object obj : youngGeneration) {
                if (alive.contains(obj)) {
                    int age = getObjectAge(obj);
                    if (age > promotionThreshold) {
                        oldGeneration.add(obj);
                    }
                }
            }
            
            youngGeneration.clear();
            youngGeneration.addAll(alive);
        }
        
        private void markReachableFromRoots(Queue<Object> gen, Set<Object> alive) {
            // Depth-First или Breadth-First Search
        }
        
        private void markReachableFromOldGen(Set<Object> alive) {
            // Проверяем ссылки из Old Gen
        }
        
        private int getObjectAge(Object obj) {
            return 0;  // Упрощённо
        }
    }
}

3. Concurrent Mark-Sweep (CMS)

Позволяет приложению работать параллельно с GC маркировкой (пока не на фазе Sweep):

public class CMSExample {
    // CMS Фазы:
    // 1. Initial Mark - отмечает объекты напрямую из root (STW)
    // 2. Concurrent Mark - отмечает остальные (параллельно с приложением)
    // 3. Remark - переотмечивает изменённые объекты (STW)
    // 4. Concurrent Sweep - удаляет мусор (параллельно)
    
    public static void main(String[] args) {
        // Запуск с CMS GC
        // java -XX:+UseConcMarkSweepGC MyApplication
        
        // CMS хорош для low latency приложений
        // но может привести к GC delays
    }
}

4. G1GC (Garbage First)

Современный стандарт (по умолчанию в Java 9+).

public class G1GCExample {
    // G1 разделяет кучу на регионы (regions)
    // Каждый регион может быть Young или Old
    // Маркирует и удаляет регионы с наибольшим мусором первыми
    
    static class G1Region {
        private Set<Object> objects;
        private double wastePercentage;  // % мусора в регионе
        
        public double getCollectionPriority() {
            // G1 сначала собирает регионы с максимальным мусором
            return wastePercentage;
        }
    }
    
    public static void main(String[] args) {
        // Запуск с G1GC (по умолчанию)
        // java -XX:+UseG1GC -XX:MaxGCPauseMillis=200 MyApplication
        
        // G1 хорош для:
        // - Больших куч (> 6GB)
        // - Низкой latency
        // - Предсказуемых GC паузы
    }
}

5. ZGC (Z Garbage Collector)

Модернейший GC для субмиллисекундных пауз:

public class ZGCExample {
    // ZGC использует:
    // - Colored pointers (цветные указатели)
    // - Load barriers для отслеживания объектов
    // - Concurrent marking и relocation
    
    public static void main(String[] args) {
        // Запуск с ZGC (требует Java 11+)
        // java -XX:+UseZGC -XX:ConcGCThreads=4 MyApplication
        
        // GC паузы < 10ms независимо от размера кучи
        // Идеально для high-throughput и low-latency систем
    }
}

6. Основные алгоритмы поиска достижимых объектов

Depth-First Search (DFS) — наиболее распространённый

static class DFSMarkingAlgorithm {
    private Set<Object> marked = new HashSet<>();
    private Stack<Object> stack = new Stack<>();
    
    void dfs(Object root) {
        stack.push(root);
        
        while (!stack.isEmpty()) {
            Object current = stack.pop();
            
            if (marked.contains(current)) continue;
            marked.add(current);
            
            // Получаем всех потомков
            for (Object child : getChildren(current)) {
                if (!marked.contains(child)) {
                    stack.push(child);
                }
            }
        }
    }
    
    private List<Object> getChildren(Object obj) {
        return new ArrayList<>();
    }
}

Breadth-First Search (BFS) — реже используется

static class BFSMarkingAlgorithm {
    private Set<Object> marked = new HashSet<>();
    private Queue<Object> queue = new LinkedList<>();
    
    void bfs(Object root) {
        queue.offer(root);
        marked.add(root);
        
        while (!queue.isEmpty()) {
            Object current = queue.poll();
            
            for (Object child : getChildren(current)) {
                if (!marked.contains(child)) {
                    marked.add(child);
                    queue.offer(child);
                }
            }
        }
    }
    
    private List<Object> getChildren(Object obj) {
        return new ArrayList<>();
    }
}

Root Objects в Java

public class RootObjectsExample {
    // Корневые объекты GC:
    
    // 1. Stack frames - локальные переменные
    public static void methodWithLocals() {
        Object local1 = new Object();  // ROOT
        Object local2 = new Object();  // ROOT
    }
    
    // 2. Static fields
    static Object staticReference = new Object();  // ROOT
    
    // 3. Monitor locks
    Object lockObj = new Object();  // ROOT (если locked)
    
    // 4. JNI references
    // Ссылки из native кода
}

Лучшие практики

• Минимизируй размер Young Generation для частых Minor GC
• Избегай долгоживущих объектов в Young Gen
• Используй G1GC по умолчанию для современных приложений
• Мониторь GC паузы с помощью -XX:+PrintGCDetails
• Оптимизируй allocation rate — снижай создание мусорных объектов

// GC мониторинг
java -XX:+UseG1GC \
     -XX:+PrintGCDetails \
     -XX:+PrintGCDateStamps \
     -Xloggc:gc.log \
     MyApplication

Заключение

Основные алгоритмы поиска объектов в GC:

• Mark-Sweep — базовый алгоритм (маркировка + удаление)
• Generational — молодые объекты часто, старые редко
• Concurrent — параллельная маркировка с приложением
• G1GC — сборка регионов с максимальным мусором
• ZGC — субмиллисекундные паузы

Все эти алгоритмы начинают с Depth-First Search от root objects (переменные в стеке, static поля, JNI ссылки) и рекурсивно отмечают все достижимые объекты. Неотмеченные объекты считаются мусором и удаляются из памяти.