Jak działa Java Garbage Collection z odwołaniami cyklicznymi?

Z mojego zrozumienia, odśmiecanie pamięci w Javie czyści niektóre obiekty, jeśli nic innego nie wskazuje na ten obiekt.

Moje pytanie brzmi, co się stanie, jeśli mamy coś takiego:

class Node {
    public object value;
    public Node next;
    public Node(object o, Node n) { value = 0; next = n;}
}

//...some code
{
    Node a = new Node("a", null), 
         b = new Node("b", a), 
         c = new Node("c", b);
    a.next = c;
} //end of scope
//...other code

a, bi cpowinny zostać wyrzucone, ale wszystkie są przywoływane przez inne obiekty.

Jak radzi sobie z tym wyrzucanie elementów bezużytecznych Java? (czy to po prostu wyczerpanie pamięci?)

Java GC traktuje obiekty jako „śmieci”, jeśli nie są one osiągalne przez łańcuch rozpoczynający się w katalogu głównym wyrzucania elementów bezużytecznych, więc te obiekty zostaną zebrane. Nawet jeśli obiekty mogą wskazywać na siebie nawzajem, tworząc cykl, nadal są śmieciami, jeśli zostaną odcięte od korzenia.

Zobacz sekcję o nieosiągalnych obiektach w Dodatku A: Prawda o usuwaniu elementów bezużytecznych w wydajności platformy Java: strategie i taktyki, aby uzyskać szczegółowe informacje.

tak Java Garbage collector obsługuje odwołania cykliczne!

How?

Istnieją specjalne obiekty nazywane korzeniami czyszczenia pamięci (korzenie GC). Są one zawsze osiągalne, podobnie jak każdy obiekt, który ma je u swojego źródła.

Prosta aplikacja Java ma następujące korzenie GC:

1. Zmienne lokalne w metodzie głównej
2. Główny wątek
3. Zmienne statyczne klasy głównej

Aby określić, które obiekty nie są już używane, JVM sporadycznie uruchamia tak zwany algorytm oznaczania i przeciągania . Działa w następujący sposób

1. Algorytm przechodzi przez wszystkie odniesienia do obiektów, zaczynając od korzeni GC i oznacza każdy znaleziony obiekt jako żywy.
2. Cała pamięć sterty, która nie jest zajęta przez zaznaczone obiekty, jest odzyskiwana. Jest po prostu oznaczony jako wolny, zasadniczo usunięty z nieużywanych obiektów.

Więc jeśli jakikolwiek obiekt nie jest osiągalny z korzeni GC (nawet jeśli odwołuje się do siebie lub odwołuje się cyklicznie), zostanie poddany czyszczeniu.

Oczywiście czasami może to prowadzić do wycieku pamięci, jeśli programista zapomni wyłuskać obiekt.

Źródło: Java Memory Management

Moduł odśmiecania pamięci zaczyna się od jakiegoś „głównego” zbioru miejsc, które są zawsze uważane za „osiągalne”, takich jak rejestry procesora, stos i zmienne globalne. Działa poprzez znajdowanie wszelkich wskaźników w tych obszarach i rekurencyjne znajdowanie wszystkiego, na co wskazują. Kiedy już to wszystko znajdzie, wszystko inne to śmieci.

Oczywiście istnieje kilka odmian, głównie ze względu na szybkość. Na przykład większość współczesnych modułów odśmiecania pamięci jest „pokoleniowych”, co oznacza, że ​​dzielą obiekty na pokolenia, a gdy obiekt się starzeje, moduł odśmiecania działa coraz dłużej między okresami, w których próbuje dowiedzieć się, czy ten obiekt jest nadal ważny, czy nie. - zaczyna po prostu zakładać, że jeśli żył długo, są całkiem duże szanse, że będzie żył jeszcze dłużej.

Niemniej jednak podstawowa idea pozostaje ta sama: wszystko opiera się na rozpoczęciu od jakiegoś podstawowego zestawu rzeczy, które wydaje się oczywiste, nadal mogą być używane, a następnie gonienie za wszystkimi wskazówkami, aby znaleźć to, co jeszcze może być w użyciu.

Interesujące na marginesie: często ludzie mogą być zaskoczeni stopniem podobieństwa między tą częścią garbage collectora a kodem służącym do organizowania obiektów dla rzeczy takich jak zdalne wywołania procedur. W każdym przypadku zaczynasz od jakiegoś głównego zestawu obiektów i gonisz wskaźniki, aby znaleźć wszystkie inne obiekty, do których się odnoszą ...

Masz rację. Specyficzna forma czyszczenia pamięci, którą opisujesz, nazywa się „ zliczaniem odwołań ”. Sposób, w jaki to działa (przynajmniej koncepcyjnie większość nowoczesnych implementacji liczenia referencji jest faktycznie implementowanych zupełnie inaczej) w najprostszym przypadku wygląda tak:

• za każdym razem, gdy dodawane jest odniesienie do obiektu (np. jest przypisywane do zmiennej lub pola, przekazywane do metody itd.), jego liczba odwołań jest zwiększana o 1
• za każdym razem, gdy odwołanie do obiektu jest usuwane (metoda zwraca, zmienna wychodzi poza zakres, pole jest ponownie przypisywane do innego obiektu lub obiekt, który zawiera pole, zostaje usunięty), liczba odwołań jest zmniejszana o 1
• jak tylko liczba referencji osiągnie 0, nie ma już odniesienia do obiektu, co oznacza, że ​​nikt nie może go już używać, dlatego jest to śmieci i można je zbierać

I ta prosta strategia ma dokładnie ten problem, który opisałeś: jeśli A odwołuje się do B, a B do A, to ich liczba nigdy nie może być mniejsza niż 1, co oznacza, że ​​nigdy nie zostaną zebrane.

Istnieją cztery sposoby rozwiązania tego problemu:

1. Zignoruj ​​to. Jeśli masz wystarczająco dużo pamięci, twoje cykle są małe i rzadkie, a czas pracy krótki, może po prostu nie będziesz zbierać cykli. Pomyśl o interpretatorze skryptów powłoki: skrypty powłoki zwykle działają tylko przez kilka sekund i nie przydzielają dużo pamięci.
2. Połącz swój garbage collector zliczający referencje z innym garbage collector, który nie ma problemów z cyklami. CPython robi to, na przykład: główny moduł odśmiecania pamięci w CPythonie jest zbieraczem zliczania referencji, ale od czasu do czasu jest uruchamiany moduł odśmiecania śledzenia w celu zebrania cykli.
3. Wykryj cykle. Niestety, wykrywanie cykli na wykresie jest dość kosztowną operacją. W szczególności wymaga prawie takiego samego obciążenia, jak kolektor śledzenia, więc równie dobrze możesz użyć jednego z nich.
4. Nie implementuj algorytmu w naiwny sposób: od lat 70. XX wieku opracowano wiele całkiem interesujących algorytmów, które łączą wykrywanie cykli i liczenie referencji w jednej operacji w sprytny sposób, który jest znacznie tańszy niż ich wykonywanie. zarówno osobno, jak i robiąc kolektor śledzenia.

Nawiasem mówiąc, innym głównym sposobem implementacji garbage collectora (o czym wspomniałem już kilka razy powyżej) jest śledzenie . Kolektor śledzenia opiera się na koncepcji osiągalności . Zaczynasz z pewnym zestawem głównym , o którym wiesz, że jest zawsze osiągalny (na przykład stałe globalne lub Objectklasa, bieżący zakres leksykalny, bieżąca ramka stosu) i stamtąd śledzisz wszystkie obiekty, które są osiągalne z zestawu głównego, a następnie wszystkie obiekty, które są osiągalne z obiektów osiągalnych z zestawu głównego i tak dalej, aż uzyskasz domknięcie przechodnie. Wszystko, czego nie ma w tym zamknięciu, jest śmieciem.

Ponieważ cykl jest osiągalny tylko w sobie, ale nie jest osiągalny z zestawu głównego, zostanie zebrany.

GC Java w rzeczywistości nie zachowują się zgodnie z opisem. Dokładniej jest powiedzieć, że zaczynają się od podstawowego zestawu obiektów, często nazywanych „korzeniami GC”, i zbierają każdy obiekt, do którego nie można dotrzeć z katalogu głównego.
Korzenie GC obejmują takie rzeczy, jak:

• zmienne statyczne
• zmienne lokalne (w tym wszystkie odnośniki „this”) aktualnie na stosie działającego wątku

Tak więc w twoim przypadku, gdy zmienne lokalne a, b i c wyjdą poza zakres na końcu twojej metody, nie ma już korzeni GC, które zawierają, bezpośrednio lub pośrednio, odniesienie do któregokolwiek z twoich trzech węzłów i będą kwalifikować się do czyszczenia pamięci.

Link TofuBeer zawiera więcej szczegółów, jeśli chcesz.

Ten artykuł (już niedostępny) dogłębnie na temat garbage collectora (koncepcyjnie ... istnieje kilka implementacji). Odpowiednia część Twojego posta to „A.3.4 Nieosiągalna”:

A.3.4 Nieosiągalny Obiekt przechodzi w stan nieosiągalny, gdy nie istnieją silniejsze odniesienia do niego. Gdy obiekt jest nieosiągalny, jest kandydatem do kolekcji. Zwróć uwagę na sformułowanie: Tylko dlatego, że przedmiot jest kandydatem do kolekcji, nie oznacza, że ​​zostanie on natychmiast odebrany. JVM może opóźnić gromadzenie danych, dopóki nie będzie natychmiastowej potrzeby wykorzystania pamięci przez obiekt.

Wyrzucanie elementów bezużytecznych zwykle nie oznacza „wyczyść jakiś obiekt, jeśli nic innego nie wskazuje” na ten obiekt (to jest liczenie referencji). Wyrzucanie elementów bezużytecznych z grubsza oznacza znajdowanie obiektów, do których nie można dotrzeć z programu.

W twoim przykładzie, gdy a, b i c wyjdą poza zakres, mogą zostać zebrane przez GC, ponieważ nie masz już dostępu do tych obiektów.

Bill odpowiedział bezpośrednio na twoje pytanie. Jak powiedział Amnon, twoja definicja czyszczenia pamięci to po prostu zliczanie referencji. Chciałem tylko dodać, że nawet bardzo proste algorytmy, takie jak zaznaczanie i zamiatanie oraz kopiowanie, z łatwością obsługują odwołania cykliczne. Więc nie ma w tym nic magicznego!