Garbage Collector Javy 1/5

Tłumaczenie 9-tego rozdziału “Inside the Java Virtual Machine” napisanego przez Billa Vennersa znajdującego się na http://www.artima.com/insidejvm/ed2/gcP.html

Sterta maszyny wirtualnej Javy przechowuje wszystkie obiekty tworzone przez działająca aplikację Javy. Obiekty są tworzone przez instrukcje new, newarray, anewarray i multianewarray ale nigdy nie są zwalniane jawnie przez kod. Odśmiecanie (garbage collection) jest procesem automatycznego zwalniania obiektów do których program już się nie odwołuje.

Ten rozdział nie opisuje oficjalnej sterty odśmiecania pamięci Javy bo taka nie istnieje. Jak wspomniano we wcześniejszych rozdziałach, specyfikacja maszyny wirtualnej Javy nie wymaga szczególnej techniki zbierania śmieci. Nie wymaga nawet zbierania śmieci w ogóle. Ale ponieważ nie wynaleziono nieskończonej pamięci, większość implementacji wirtualnej maszyny Javy będzie prawdopodobnie działać ze stertą zbierania śmieci. Ten rozdział opisuje różne techniki odśmiecania i wyjaśnia jak odśmiecanie działa w wirtualnych maszynach Javy.
Dostępny jest aplet który interaktywnie ilustruje materiał tutaj prezentowany. Applet nazwany Heap of Fish.

http://www.artima.com/insidejvm/applets/HeapOfFish.html symuluje stertę odśmiecania pamięci w wirtualnej maszynie Javy. Symulacja która demonstruje kompaktowanie, zaznaczanie i zamiatanie (mark-and-sweep), czyszczenie, pozwala na interakcję ze stertą tak jakbyś był programem Javy: możesz alokować obiekt i przypisać referencje do zmiennych. Symulacja również pozwala Ci na interakcję ze stertą jakbyś był wirtualna maszyną Javy: możesz sterować procesem zbierania śmieci i kompaktowaniem sterty. Na koniec tego rozdziału znajdziesz opis tego apletu i instrukcję jak go używać.
Dlaczego odśmiecanie?
Nazwa “odśmiecanie” oznacza że obiekty które dłużej już nie są potrzebne programowi są “śmieciami” i można je wyrzucić. Bardziej dokładną i aktualną metaforą może być “recykling pamięci”. Kiedy już do obiektu program się nie odwołuje, przestrzeń sterty którą zajmuje może być zutylizowana i być dostępna dla kolejnych nowych obiektów. Garbage collector musi w jakiś sposób określić do których obiektów nie ma już odwołań przez program i udostępnić przestrzeń sterty zajmowanej przez takie obiekty. W procesie zwalniania obiektów do których nie ma odwołania, garbage collector musi uruchomić finalizatory obiektów które są zwalniane.
Oprócz zwalniania obiektów do których nie ma odwołania, garbage collector może także walczyć z fragmentacją sterty. Fragmentacja sterty następuje w trakcie normalnego wykonywania programu. Nowe obiekty są alokowane a obiekty bez odwołań są zwalniane tak że wolne części stery pamięci zostają między częściami zajmowanymi przez żywe obiekty. Żądania alokowania nowych obiektów mogą być wypełnione przez rozszerzenie wielkości sterty chociaż jest wystarczająco w sumie nieużywanego miejsca w istniejącej stercie. To się stanie jeśli nie ma wystarczająco ciągłej wolnej przestrzeni dla nowego obiektu. W systemie wirtualnej pamięci dodatkowe stronicowanie lub zamiana zawsze rosnącej stery może obniżyć wydajność wykonywanego programu. W systemie wbudowanym z małą ilością pamięci, fragmentacja może spowodować że wirtualna maszyna wykona niepotrzebnie “run out of memory”.
Odśmiecanie zwolni Cię od ciężaru zwalniania zaalokowanej pamięci .Wiadomo że jawne zwalnianie zaalokowanej pamięci może być bardzo trudne. Przekazanie tego zadania do wirtualnej maszyny Javy ma wiele zalet. Po pierwsze. To czyni Cie bardziej produktywnym. Kiedy programujesz w językach które nie mają automatycznego zbierania śmieci możesz spędzać wiele późnych godzin (lub dni lub tygodni) polując na nieuchwytny problem z pamięcią. Kiedy programujesz w Javie możesz użyć ten czas bardziej korzystnie przed terminem lub po prostu iść do domu ciesząc się życiem.
Drugą zaletą odśmiecania jest że to pomaga zapewnić integralność programu. Odśmiecanie jest ważną częścią strategii bezpieczeństwa Javy. Programiści Javy nie są w stanie przypadkowo (lub celowo) spowodować awarię wirtualnej maszyny Javy przez nieprawidłowe zwalnianie pamięci.
Potencjalna wadą odśmiecanej sterty jest że dodaje pewien narzut który może wpłynąć na wydajność programu. Wirtualna maszyna Javy musi śledzić do których obiektów są odwołania przez wykonywany program i finalizować i zwalniać w locie obiekty do których nie ma odwołania. Ta aktywność może wymagać więcej czasu procesora niż było by to wymagane jeśli program jawnie zwalniał by niepotrzebną pamięć. W dodatku programiści w środowisku odśmiecania mają mniejszą kontrolę nad planowaniem czasu CPU poświęconego na zwalnianie obiektów które nie są już dłużej potrzebne.

Algorytmy odśmiecania
Wszelki algorytm odśmiecania musi robić dwie podstawowe rzeczy. Po pierwsze, musi wykryć niepotrzebne obiekty. Po drugie musi odzyskać miejsce na stercie używane przez niepotrzebne obiekty i udostępnić to miejsce programowi.
Wykrywanie śmieci jest zwykle realizowane przez określenie zbioru korzeni i określenia dostępności idąc od korzeni. Obiekt jest osiągalny jeżeli jest jakaś droga referencji od korzeni którą wykonywany program może mieć dostęp do obiektu. Korzenie są zawsze dostępne przez program. Obiekty które są osiągalne od korzeni są uważane ze “żywe”. Obiekty które nie są osiągalne są uważane za śmieci ponieważ nie mogą mieć wpływu na dalszy przebieg programu.
Zbiór korzeni w wirtualnej maszynie Javy jest zależny od implementacji, ale zawsze zawiera referencje obiektów w lokalnych zmiennych i operandach stosu w każdej ramce stosu i referencje obiektu w każdej zmiennej obiektowej. Innym źródłem korzeni są odwołania do obiektów takie jak stringi w puli stałych ładowanych klas. Pula stałych ładowanej klasy może odwoływać się do stringu umieszczonego na stercie takiego jak nazwa klasy, nazwa nadklasy, nazwa interfejsu z którego dziedziczy, nazwy pól, sygnatury pól, nazwy i sygnatury metod. Innym źródłem korzeni mogą być dowolne odwołania do obiektu które były przekazane do natywnych metod albo nie zostały “zwolnione” przez natywną metodę. (W zależności od interfejsu metody natywnej, metoda ta może mieć możliwość zwolnienia referencji po prostu przez powrót, przez jawne wywołanie callbacku który zwolni przekazaną referencję lub kombinację tych sposobów). Innym potencjalnym źródłem korzeni jest jakakolwiek część obszarów danych runtime maszyny wirtualnej Javy które są alokowane na odśmiecanej stercie. Na przykład, dane klasy w obszarze metody mogłyby być wprowadzone do sterty w niektórych implementacjach pozwalając tym samym na algorytm odśmiecania który zwalnia obiekty aby wykrywać i zwalniać klasy do których nie ma odwołania.
Każdy obiekt do którego odwołuje się korzeń jest osiągalny a zatem jest to żywy obiekt. Ponadto obiekty do których odwołują się żywe obiekty są również osiągalne. Program ma możliwość dostępu do jakiegokolwiek osiągalnego obiektu więc te obiekty muszą pozostać na stercie. Obiekty które nie są dostępne mogą być zebrane ponieważ nie ma sposobu aby program miał do nich dostęp.
Maszyna wirtualna Javy może być implementowana tak, że garbage collector zna różnicę między prawdziwą referencją do obiektu a pierwotnym typem (na przykład int) który wydaje się prawidłowym odniesieniem do obiektu. (Jednym z przykładów jest int, jeśli byłby interpretowany jako natywny wskaźnik, wskazywałby obiekt na stercie). Niektóre garbage collectory mogą nie odróżnić prawdziwych referencji do obiektów wyglądających podobnie. Takie garbage collectory zwane są konserwatywnymi ponieważ mogą nie zawsze zwolnić obiekt do którego nie ma odniesień. Czasami nieużyteczny obiekt będzie nieprawidłowo uważany za żywy przez konserwatywny odśmiecacz ponieważ referencja do obiektu wygląda podobnie do niego. Konserwatywne odśmiecacze idą na kompromis zwiększając prędkość zwalniania śmieci, okazjonalnie nie zwalniając rzeczywistych nieużytków.
Dwa podstawowe podejścia do rozróżniania żywych obiektów od nieużytków to licznik referencji i śledzenie. Garbage collectory liczące referencje rozróżniają żywe obiekty od śmieci przez trzymanie licznika dla każdego obiektu na stercie. Licznik śledzi ilość odwołań do tego obiektu. Śledzące garbage collectory faktycznie wytyczają wykres odniesień zaczynając od korzeni. Obiekty które występują na na śladzie są zaznaczane. Gdy ślad jest kompletny, wiadomo że niezaznaczone obiekty są nieosiągalne i mogą być zebrane.

Odśmiecacze liczące odwołania
Liczenie odwołań było wczesną strategią zbierania nieużytków. W tym podejściu licznik odwołań jest utrzymywany dla każdego obiektu na stercie. Kiedy obiekt jest stworzony i referencja do niego jest przypisywana zmiennej, licznik referencji jest ustawiony na jeden. Kiedy innej zmiennej jest przypisywana referencja to tego obiektu, licznik obiektu jest zwiększany. Kiedy referencja do obiektu wychodzi z zakresu lub jest przypisywana nowa wartość, licznik obiektu jest zmniejszany. Obiekt z licznikiem referencji zero może być usunięty. Kiedy obiekt jest zwalniany, obiekty na które wskazywał powinny mieć zmniejszony licznik referencji. W ten sposób odśmiecanie jednego obiektu pociąga za sobą zbieranie innych obiektów.
Zaletą tego podejścia jest to że odśmiecacz liczący referencje może pracować w małych porcjach czasu blisko powiązanych z wykonywaniem programu. Ta cecha czyni go szczególnie odpowiednim dla środowisk czasu rzeczywistego gdzie program nie może być przerwany na bardzo długo. Wadą jest to że licznik referencji nie wykrywa cykli dwóch lub więcej obiektów które odnoszą się do siebie. Przykładem cyklu jest obiekt rodzic który ma referencję to obiektu potomnego który ma referencję znowu na rodzica. Te obiekty nigdy ie będą miały wyzerowanego licznika referencji nawet jeśli byłyby nieosiągalne przez korzenie wykonywanego programu. Inną wadą licznika referencji jest obciążenie zwiększaniem i zmniejszaniem licznika cały za każdym razem.
Ze względu na wady związane z podejściem liczenia referencji ta technika jest obecnie w niełasce. Jest bardziej prawdopodobne że wirtualne maszyny Javy w realnym świecie będą wykorzystywać algorytm śledzenia.
Odśmiecacze śledzące
Odśmiecacze śledzące wytyczają ślad odwołań obiektów zaczynając od korzeni. Obiekty które występują na śladzie są zaznaczane, Zaznaczanie jest ogólnie zrobione przez ustawienie flagi w obiektach albo w oddzielnej bitmapie. Po wytyczeniu śladu wiadomo że nieoznakowane obiekty są nieosiągalne i mogą być zebrane.
Podstawowy algorytm śledzenia jest nazwany “mark and sweep.” ta nazwa odnosi się do dwóch faz procesu zbierania śmieci. W fazie zaznaczania garbage collector przemierza drzewo referencji i zaznacza każdy obiekt który napotka. W fazie wymiatania nieoznaczone obiekty są zwalniane i pamięć staje się dostępna dla programu. W wirtualnej maszynie Javy faza wymiatania musi zawierać finalizację obiektów.
Odśmiecacze kompaktujące
Garbage collectory wirtualnych maszyn Javy będą prawdopodobnie miały strategie walki z fragmentacją sterty. Dwie strategie powszechnie używane przez odśmiecacze typu mark and sweep to kompaktowanie i kopiowanie. Oba te podejścia przesuwają obiekty w locie w celu zmniejszenia fragmentacji sterty. W wyniku tego procesu na stosie powstaje jeden wielki wolny obszar. Wszystkie referencje do przesuwanych obiektów są aktualizowane do wskazywania nowej lokalizacji.
Aktualizowanie referencji do przesuwanych obiektów jest czasem robione prościej przez dodawanie poziomu pośredniego do referencji obiektu. Zamiast odwoływać się bezpośrednio do obiektu na stercie, odwołujemy się do tablicy uchwytów. Uchwyty obiektów odwołują się do aktualnych obiektów na stercie. Kiedy obiekt jest przesuwany, jedynie uchwyt obiektu musi być uaktualniony do nowej lokalizacji. Wszystkie referencje do obiektu w programie nadal odnoszą się do zaktualizowanego uchwytu który się nie przesuwa. Takie podejście ułatwia pracę defragmentacji sterty. Jednak dodaje obciążenie do każdego dostępu do obiektu.
Odśmiecacze kopiujące.
Kopiujące odśmiecacze przenoszą wszystkie żywe obiekty do nowego miejsca. Skoro obiekty są przenoszone do nowego miejsca, są umieszczone obok siebie co eliminuje wolne miejsce które było między nimi. Wiadomo wtedy że stary obszar jest cały wolnym miejscem. Zaletą tego podejścia jest że obiekty mogą być kopiowane gdy tylko są odkryte przez przejście z korzeni. Nie ma oddzielnej fazy znakowania i wymiatania. Obiekty są kopiowane do nowego obszaru w locie a na starych miejscach pozostają wskaźniki do nowej pozycji. Wskaźniki te pozwalają garbage collectorowi wykryć referencje do obiektów które już zostały przeniesione. Garbage collector może wtedy przypisać wartość tych wskaźników do referencji która wskazuje nową lokalizację obiektu.
Wspólny algorytm odśmiecacza kopiującego jest zwany “zatrzymaj się i kopiuj”. W tym systemie sterta jest dzielona na dwa regiony. Jedynie jeden z dwóch jest używany w dowolnym momencie. Obiekty są alokowane z jednego z tych regionów dotąd aż miejsce w tym regionie się wyczerpie. W tym miejscu wykonanie programu zatrzymuje się i zaczyna się przejście sterty. Żywe obiekty są kopiowane do innego regionu gdy zostają napotkana podczas przejścia. Kiedy procedura zatrzymaj się i kopiuj się skończy, wznawia się wykonanie programu. Pamięć będzie przyznawana z nowego regionu sterty aż także zabraknie miejsca. W tym miejscu program będzie ponownie zatrzymany. Sterta będzie przemierzona i żywe obiekty będą znowu kopiowane do oryginalnego regionu. Kosztem związanym z tym podejściem jest to ze potrzeba dwa razy więcej pamięci dla danej ilości miejsca na stercie, ponieważ tylko połowa dostępnej pamięci jest używana w dowolnym momencie.
Możesz zobaczyć graficzny wizerunek odśmiecanej sterty która używa algorytmu zatrzymaj się i kopiuj na rysunku 9-1. Rysunek pokazuje dziewięć migawek sterty. Na pierwszej migawce dolna połowa sterty jest niewykorzystanym miejscem. Górna połowa jest częściowo wypełniona przez obiekty. Część sterty która zawiera obiekty jest rysowana przekątnymi szarymi liniami. Druga migawka pokazuje że górna połowa sterty jest stopniowo wypełniana przez obiekty aż będzie pełna jak pokazano na trzeciej migawce.
W tym momencie garbage collector zatrzymuje program i śledzi żywe obiekty zaczynając od korzeni. Kopiuje każdy żywy obiekt który napotka do dolnej części sterty, wprowadzając każdy jako następny do poprzednio kopiowanego. Ten proces jest pokazany w czwartej migawce.
Piąta migawka pokazuje stertę po tym jak odśmiecanie się skończyło. Teraz górna połowa sterty jest nieużywana a dolna połowa jest częściowo wypełniona żywymi obiektami. Szósta migawka pokazuje dolną połowę która jest stopniowo wypełniana obiektami aż będzie pełna – migawka siedem.
Po raz kolejny garbage collector zatrzymuje program i śledzi żywe obiekty. Tym razem kopiuje każdy żywy obiekt który napotka do górnej połowy co pokazane w migawce osiem. Migawka dziewięć pokazuje wynik zbierania nieużytków: dolna połowa jest po raz kolejny nieużywanym miejscem a górna połowa jest częściowo wypełniona przez obiekty. Proces powtarza się znowu i znowu podczas wykonywania programu.