Garbage Collector Javy 2/5

Odśmiecacze pokoleniowe
Jedną z wad prostych odśmiecaczy typu “stop and copy” jest to, że wszystkie żywe obiekty muszą być kopiowane przy każdym sprzątaniu. Ten aspekt kopiujących algorytmów może być poprawiony biorąc pod uwagę dwa fakty, które zostały empirycznie obserwowane w większości programów w różnych językach:
  1. Większość obiektów tworzonych przez większość programów ma bardzo krótkie życie.
  2. Większość programów tworzy niewiele obiektów które mają bardzo długie życie. Głównym źródłem nieefektywności prostych kopiujących odśmiecaczy jest to że spędzają dużo czasu kopiując te same długo żyjące obiekty znowu i znowu.

Odśmiecacze pokoleniowe radzą sobie z tą nieefektywnością przez grupowanie obiektów ze względu na wiek i sprzątanie młodszych obiektów częściej niż starszych. W ramach tego podejścia sterta jest dzielona na dwie lub więcej mniejszych stert, z których każda obsługuje jedno “pokolenie” obiektów. Najmłodsza generacja jest sprzątana najczęściej. Ponieważ większość obiektów jest krótko żyjąca, jedynie mały procent młodych obiektów ma szansę na szansę przetrwania pierwszego sprzątania. Skoro obiekt przetrwał kilka sprzątań jako członek najmłodszej generacji, obiekt jest awansowany do następnej generacji: jest przenoszony do innej podsterty. Każde starsze pokolenie jest czyszczone rzadziej niż młodsze. Jako obiekty “starsze” (przetrwały wiele czyszczeń) w bieżącym pokoleniu są przemieszczane do starszego pokolenia.

Technika odśmiecania pokoleniowego może być użyta zarówno do algorytmu zaznaczania i zamiatania jak i kopiowania. W każdym przypadku dzieląc stertę na pokolenia obiektów można poprawić wydajność podstawowego algorytmu.
Adaptujące się odśmiecacze
Algorytm adaptacyjny wykorzystuje fakt że pewne algorytmy odśmiecania działają lepiej w niektórych sytuacjach, podczas gdy inne działają lepiej w innych sytuacjach. Adaptacyjny algorytm monitoruje bieżąca sytuację na stercie i dostosowuje odpowiednio technikę odśmiecania. Może zmieniać parametry algorytmu podczas działania programu. Może przejść z jednego algorytmu do innego w locie lub może podzielić stertę na podsterty i używać równocześnie różnych algorytmów na różnych podstertach.
Z adaptacyjnym podejściem projektantów wirtualnej maszyny Javy implementacje nie potrzebują jednej techniki odśmiecania. Można stosować wiele technik dając każdemu algorytmowi pracować w tym w czym najlepiej działa.
Algorytm kolejowy
Jedną z potencjalnych wad zbierania nieużytków w porównaniu do jawnego zwalniania obiektów jest to, że odśmiecanie daje programistom mniejszą kontrolę nad przydziałem czasu CPU poświęconego odzyskowi pamięci. Jest ogólnie niemożliwe przewidzieć dokładnie kiedy (a nawet czy) będzie wywołany garbage collector i jak długo będzie działał. Ponieważ garbage collectory zwykle zatrzymują cały program podczas wyszukiwania i gromadzenia obiektów śmieci, mogą powodować dowolnie długie przerwy na dowolny czas w trakcie działania programu. Takie przerwy odśmiecania mogą być czasami wystarczająco długie by być zauważone przez użytkownika. Mogą również przeszkodzić szybkiemu reagowaniu na zdarzenia. Jeśli algorytm zbierania śmieci jest w stanie wytwarzać wystarczająco długie przerwy by być zauważonym przez użytkownika lub sprawiają że program nie nadaje się do środowiska czasu rzeczywistego, mówi się że algorytm powoduje zakłócenia. W celu zminimalizowania potencjalnych wad zbierania śmieci w porównaniu do jawnego zwalniania obiektów wspólnym celem algorytmów jest zminimalizowanie jeśli to możliwe ich zakłócającego charakteru.
Jednym ze sposobów osiągnięcia (lub przynajmniej próbą osiągnięcia) nie zakłócającego odśmiecania jest użycie algorytmów które zbierają przyrostowo. Przyrostowy garbage collector zamiast próbować znaleźć i usunąć wszystkie przedmioty niedostępne w każdym wywołaniu, tylko stara się znaleźć i usunąć część obiektów nieosiągalnych. Ponieważ tylko część sterty w każdym wywołaniu, teoretycznie powinien działać w krótszym czasie.
Garbage collector który może wykonywać przyrostowe sprzątania z których każde gwarantuje (lub przynajmniej jest to bardzo prawdopodobne) mniej niż określona ilość czasu, może pomóc uczynić wirtualna maszynę Javy odpowiednią dla środowiska czasu rzeczywistego. Garbage collector który wykonuje swoją prace w odstępach czasu jest również wskazany w środowisku użytkownika ponieważ może wyeliminować przerwy na sprzątanie zauważalne przez użytkownika.
Powszechnym przyrostowym odśmiecaczem jest odśmiecacz pokoleniowy który dla większości wywołań zbiera tylko część sterty. Jak wspomniano wcześniej w tym rozdziale, kolektor pokoleniowy dzieli stertę na dwa lub więcej pokoleń, z których każde jest przyznane swojej własnej podstercie. Korzystając z empirycznych obserwacji że większość obiektów ma bardzo krótki czas życia, pokoleniowy odśmiecacz zbiera podsterty młodsze częściej niż starsze pokolenia.
Ponieważ można podać maksymalny rozmiar każdej podsterty z wyjątkiem najstarszego pokolenia, odśmiecacz pokoleniowy może w ogólności zapewnić że przyrostowe czyszczenie wszystkich z wyjątkiem najstarszego pokolenia skończy się w określonym maksymalnym czasie. Powodem, że nie można podać maksymalnego rozmiaru przestrzeni najstarszych obiektów jest to że obiekty które nie pasują do podstert młodszych generacji muszą z definicji iść do przestrzeni dojrzałych obiektów. Takie obiekty nie mają pójść gdzie indziej.
Algorytm kolejowy który został po raz pierwszy zaproponowany przez Richarda Hudsona i Eliota Mossa i jest obecnie wykorzystywany przez wirtualna maszynę Hotspot Sun’a określa organizację dla przestrzeni dojrzałych obiektów. Celem algorytmu kolejowego jest dostarczyć ograniczone przez czas czyszczenia przestrzeni tych obiektów.
Wagony, pociągi i stacja kolejowa.
Algorytm kolejowy dzieli przestrzeń dojrzałych obiektów na bloki pamięci stałej wielkości, z których każdy jest zbierany indywidualnie w odrębnych wywołaniach algorytmu. Nazwa “algorytm kolejowy” pochodzi od sposobu w jaki algorytm organizuje bloki. Każdy blok należy do zestawu. Bloki w zestawie są sortowane i same zestawy są sortowane. Aby pomóc w wyjaśnieniu algorytmu, Hudson i Moss w ich oryginalnym artykule nazwali bloki “wagonami” a zestawy “pociągami”. W tej metaforze przestrzeń dojrzałych obiektów pełni rolę stacji kolejowej. Bloki w ramach tego samego zestawu są sortowane. Zestawy są sortowane w przestrzeni dojrzałych obiektów podobnie jak pociągi mogące ustawiać się na torze 1, torze 2, torze 3 i tak dalej na stacji kolejowej. Ta organizacja jest pokazana graficznie na rys. 9-2.
Rysunek 9-2. Organizacja stery dla algorytmu kolejowego.
Pociągi (zestawy bloków) noszą numery w kolejności w jakiej są tworzone. Na stacji kolejowej w związku z tym pierwszy pociąg przybywa na tor 1 i staje się pociągiem 1. Następny pociąg przybywa na tor 2 i staje się pociągiem 2. Następny przybywa na tor 3 i staje się pociągiem 3 i tak dalej. Biorąc ten porządek numeracji mniejszy numer pociągu zawsze oznacza starszy pociąg. W pociągu wagony (bloki) są dodawane jedynie do końca pociągu. Pierwszy wagon dodany do pociągu jest wagonem 1. Następny dodany do tego samego pociągu to wagon 2. W pociągu dlatego mniejszy numer wagonu oznacza starszy wagon. Ten porządek numeracji dostarcza ogólny porządek bloków w przestrzeni dojrzałych obiektów.
Rysunek 9-2 pokazuje trzy pociągi numerowane 1,2 i 3. Pociąg 1 ma cztery wagony oznaczone 1.1 do 1.4. Pociąg 2 ma trzy wagony oznaczone 2.1 do 2.3 a pociąg 3 ma pięć wagonów oznaczonych 3.1 do 3.5. Ten sposób oznakowania wagonów w którym etykiety składają się z numeru pociągu, kropki i numeru wagonu oznaczają ogólny porządek bloków zawartych w przestrzeni dojrzałych obiektów.
Wagon 1.1 poprzedza wagon 1.2 poprzedza wagon 1.3 i tak dalej. Ostatni wagon w pociągu 1 poprzedza pierwszy wagon w pociągu 2, tak więc wagon 1.4 poprzedza wagon 2.1. Podobnie wagon 2.3 poprzedza 3.1. Za każdym razem gdy algorytm jest wywoływany zbierze jeden i tylko jeden blok: blok o najniższym numerze. Tak więc gdy pierwszy raz algorytm jest wywołany na stercie pokazanej na rysunku 9-2 zbierze blok 1.1. Następnym razem zbierze blok 1.2. Po zebraniu ostatniego bloku pociągu 1 algorytm w następnym wywołaniu zbierze pierwszy blok pociągu 2.
Obiekty przybywają do przestrzeni dojrzałych obiektów kiedy są wystarczająco stare aby awansować z podsterty młodszego pokolenia. Gdy tylko obiekty awansują do przestrzeni dojrzałych obiektów z młodszych pokoleń są albo dodawane do istniejącego pociągu z wyjątkiem pociągu o najniższym numerze lub jeden lub więcej nowych pociągów jest tworzonych do przechowywania ich.
Zbieranie wagonów
Za każdym razem gdy jest wywołany algorytm kolejowy to albo zbiera wagon o najniższym numerze z pociągu o najniższym numerze lub zbiera cały pociąg o najniższym numerze. Algorytm na początku sprawdza odniesienia do każdego wagonu pociągu o najniższym numerze. Jeśli nie ma odniesień poza najniżej numerowanym pociągiem które odnoszą się do obiektów zawartych wewnątrz pociągu o najniższym numerze, cały pociąg zawiera śmieci i może zostać odzyskany. Ten pierwszy krok umożliwia algorytmowi zbieranie dużych cyklicznych struktur danych które nie mieszczą się w jednym bloku. Ze względu na drugi etap algorytmu który będzie opisany dalej jest zagwarantowane że takie duże cykliczne struktury danych w końcu znajdą się w tym samym pociągu.
Jeśli wszystko w pociągu o najniższym numerze było śmieciami, algorytm zwalnia miejsce zajmowane przez wszystkie obiekty we wszystkich wagonach w tym pociągu. (W tym momencie wywołanie algorytmu się kończy). Jeżeli w pociągu o najniższym numerze nie wszystko było śmieciami, algorytm zwraca uwagę na wagon o najniższym numerze w pociągu o najniższym numerze. W tym procesie algorytm albo przeniesie albo zwolni obiekt tego wagonu. Algorytm rozpoczyna się przeniesieniem obiektu, do którego jest odniesienie z zewnątrz wagonu o najniższym numerze, do innego wagonu. Jakiekolwiek obiekty pozostające w tym wagonie po tym procesie przeniesienia są bez odwołań i mogą być zebrane. Algorytm następnie zwalnia miejsce zajmowane przez cały wagon o najniższym numerze (uwalniając w ten sposób obiekty bez odwołań które nadal siedzą w wagonie o najniższym numerze) i wraca.
Kluczem do zagwarantowania że cykliczne struktury danych w całości skończą w tym samym pociągu leży w tym, jak algorytm przesuwa obiekty. Jeżeli do obiektu siedzącego w wagonie jest odniesienie spoza przestrzeni dojrzałych obiektów, obiekt jest przesuwany do dowolnego pociągu z wyjątkiem tego z którego się zbiera. Jeśli do obiektu jest odniesienie z innego pociągu z przestrzeni dojrzałych obiektów, obiekt jest przesuwany do pociągu skąd było odniesienie do niego. Przeniesione obiekty są następnie skanowane na odniesienia z powrotem do wagonu który jest zbierany. Obiekty do których na nowo mamy odniesienia są przenoszone do pociągu skąd mamy odniesienia. Nowo przeniesione obiekty są następnie skanowane na referencje z powrotem na wagon, który jest zwalniany i proces jest powtarzany aż nie będzie więcej referencji z innych pociągów do wagonu który jest zwalniany. Gdy w pociągu otrzymującym obiekty skończy się miejsce, algorytm utworzy nowy wagon (pusty blok) i doda na końcu tego pociągu.
Skoro nie będzie więcej odniesień spoza przestrzeni dojrzałych obiektów lub z innych pociągów z tej przestrzeni do wagonu będącego zwalnianym, wiadomo że do obiektów do których są odwołania spoza zwalnianego wagonu, odwołania są z innych wagonów tego samego pociągu. Algorytm przesuwa takie obiekty do ostatniego wagonu tego samego pociągu o najniższym numerze. Te obiekty są następnie skanowane na referencje z powrotem do zwalnianego wagonu. Obiekty do których na nowo mamy odniesienia są przenoszone na koniec tego samego pociągu i skanowane. Ten proces powtarza się dotąd aż nie będzie więcej referencji jakiegokolwiek rodzaju do wagonu który jest zwalniany. Algorytm następnie zwalnia miejsce zajmowane przez cały wagon o najniższym numerze zwalniając obiekty bez odniesień które nadal siedzą w wagonie i wraca.
Przy każdym wywołaniu więc, algorytm kolejowy albo zbiera najniższej numerowany wagon w najniżej numerowanym pociągu albo zbiera cały najniżej numerowany pociąg. Jednym z najważniejszych aspektów algorytmu jest to że gwarantuje że duże cykliczne struktury danych ostatecznie zostaną zebrane nawet jeśli nie mieszczą się w jednym bloku. Ponieważ obiekty są przenoszone do pociągów z których jest do nich referencja, powiązane obiekty mają tendencję do gromadzenia się razem. Ostatecznie wszystkie obiekty cyklicznej struktury danych nieużytków, nie ważne jak dużej, skończą w tym samym pociągu. Zwiększanie wielkości cyklicznej struktury danych spowoduje jedynie zwiększenie liczby wagonów które ostatecznie tworzą ten sam pociąg. Ponieważ algorytm kolejowy najpierw sprawdza czy pociąg o najniższym numerze całkowicie składa się z nieużytków przed skoncentrowaniem się na wagonie o najniższym numerze, jest możliwe zebrać cykliczne struktury danych dowolnego rozmiaru.

Pamiętane zestawy i popularne obiekty

Jak wspomniano wcześniej, celem algorytmu kolejowego jest dostarczenie odśmiecacza pokoleniowego ograniczonego przez czas zbierania w przestrzeni dojrzałych obiektów. Ponieważ bloki (wagony) mogą mieć ustalony maksymalny rozmiar i jedynie jeden blok jest zbierany w każdym wywołaniu, algorytm kolejowy może najczęściej zapewnić że każde wywołanie będzie wymagało mniej niż maksimum czasu. Niestety, algorytm nie może zagwarantować że każde wywołanie zajmie mniej niż ustalone maksimum czasu ponieważ algorytm musi robić więcej niż tylko kopiować obiekty.
W celu usprawnienia procesu zbierania, algorytm korzysta z pamiętanych zestawów. Pamiętany zestaw jest strukturą danych zawierającą informacje o wszystkich odniesieniach znajdujących się poza wagonem ale wskazujących na wagon lub pociąg. Algorytm utrzymuje jeden pamiętanych zestaw dla każdego wagonu i każdego pociągu w przestrzeni dojrzałych obiektów. Pamiętany zestaw dla danego wagonu w związku z tym zawiera informacje o zbiorze referencji które odnoszą się do (lub “pamiętają”) obiekty w wagonie. Pusty zbiór pamiętanych wskazuje że obiekty zawarte w wagonie lub pociągu nie mają odniesień (są “zapomniane”) przez obiekty lub zmienne poza wagonem lub pociągiem. Zapomniane obiekty są nieosiągalne i mogą być zebrane.
Pamiętany zestaw jest techniką implementacji która pomaga algorytmowi kolejowemu działać bardziej efektywnie. Kiedy algorytm odkrywa wagon z pustym zbiorem pamiętanych, wie że wagon zawiera jedynie śmieci i może natychmiast zwolnić całą pamięć zajmowaną przez wagon. Podobnie kiedy algorytm odkrywa pociąg z pustym zbiorem pamiętanych może natychmiast zwolnić całą pamięć zajmowaną przez cały pociąg. Kiedy algorytm przenosi obiekt do innego wagonu lub pociągu, informacja w zbiorze pamiętanych pomaga mu efektywnie zaktualizować wszystkie odniesienia do przenoszonego obiektu tak że odnoszą się do nowej lokalizacji obiektu.
Chociaż liczba bajtów, którą algorytm kolejowy ma skopiować podczas jednego wywołania jest ograniczona wielkością bloku, ilość pracy wymaganej do przeniesienia popularnego obiektu, który ma wiele odniesień do niego nie da się ograniczyć. Za każdym razem gdy algorytm przesuwa obiekt, musi przemierzyć pamiętany zestaw tego obiektu i zaktualizować każdą referencję do tego obiektu na taką która wskazuje na nową lokalizację. Ponieważ ilość referencji na obiekt nie może być ograniczona, ilość czasu wymaganego do zaktualizowania referencji do przesuwanego obiektu nie może być ograniczona. Tak więc w niektórych przypadkach algorytm kolejowy może nadal powodować zakłócenia. Niemniej jednak poza zdegenerowanym przypadkiem popularnych obiektów algorytm w przeważającej części wykonuje bardzo dobrą pracę pokoleniowego garbage collectora zbierania w przestrzeni dojrzałych obiektów w inkrementalny nie zakłócający sposób.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *