Жады басқару алгоритмдерінде объектілерді іздеу кезінде автоматты қоқыс жинау қалай жүзеге асырылады?

Java сияқты тілдерде автоматты қоқыс жинау (Garbage Collection, GC) объектілерге арналған жадыны тауып, босататын алгоритмдер арқылы жүзеге асырылады, олар енді сілтемелері жоқ.

Негізгі идея — түпкі көздерден (root set), мысалы, жергілікті айнымалылар, статикалық өрістер және т.б., қол жетімді объектілерді іздеу. Барлық сілтемелер арқылы жетуге болатын объектілер тірі деп саналады. Қалғандары — қоқыс және олар жойылуы мүмкін.

Алгоритмнің мысалы — графтың тереңдік немесе енін обход, түпкі көздерден бастау арқылы тірі объектілерді белгілеу. Содан кейін белгісіз объектілердің жадысы босатылады.

Java-да жиі қолданылатын — ұрпақтық жинағыш, ол объектілерді ұрпақтарға бөледі (жас, ескі) және жинауды оңтайландырады, себебі көп объектілер тез қоқысқа айналады.

Тірі объектілерді іздеу үшін қарапайым псевдокод мысалы:

void markReachableObjects(Set<Object> roots) {
    Set<Object> reachable = new HashSet<>();
    Deque<Object> stack = new ArrayDeque<>(roots);
    while (!stack.isEmpty()) {
        Object obj = stack.pop();
        if (!reachable.contains(obj)) {
            reachable.add(obj);
            for (Object ref : obj.getReferences()) {
                stack.push(ref);
            }
        }
    }
    // reachable-те жоқ барлық объектілер — қоқыс
}