Algorytmy GC. Serial, Parallel, CMS

Informacje zawarte tutaj odnoszą się do wiedzy przedstawionej w poprzednim artykule - JVM Garbage Collector. Wprowadzenie. W związku z tym wszystkich, którzy nie mieli okazji go przeczytać, zapraszam wstępnej do lektury. 

Algorytmy GC

HotSpot JVM oferuje cztery algorytmy działania Garbage Collectora: Serial, Parallel, Mostly-Concurrent (CMS), G1. Dzisiaj zajmiemy się pierwszymi trzema z tej listy. Zasady ich działania są zbliżone do siebie, więc postanowiłem zgrupować je w ramach jednego wpisu.

Usuwanie nieosiągalnych obiektów 

Zanim jednak zagłębimy się w szczegóły działania poszczególnych algorytmów, pragnę jeszcze na moment powrócić do tematu usuwania nieosiągalnych obiektów. W pierwszym wpisie z tej serii wspomniałem o trzech strategiach przeprowadzania tej operacji. O ile nie uważam, że jest to zagadnienie wymagające nie wiadomo jakich opisów, tak wizualizacja w postaci przedstawienia struktury stery przed i po zaaplikowaniu konkretnej strategii jest czymś, czego w poprzednim wpisie zabrakło, a co znacznie ułatwia zrozumienie tematu. Pozwólcie zatem, że uzupełnię tutaj tę lukę.

• Mark-Sweep – oznaczanie obszarów zajmowanych przez nieosiągalne obiekty jako wolnych do alokacji

• Mark-Sweep-Compact – mark-sweep z dodatkowym kompaktowaniem sterty

• Mark-Copy – kopiowanie żywych obiektów do nowego miejsca na stercie

 

Serial GC

Serial GC stosuje strategię mark-copy podczas czyszczenia młodszej generacji i mark-sweep-compact podczas czyszczenia starszej generacji*. Obydwie te operacje odśmiecania wykonywane są na jednym wątku i powodują całkowite wstrzymanie pracy pozostałych wątków aplikacji (jest to tzw. stop-the-world event).

W związku z powyższym algorytm ten znajduje zastosowanie głównie w przypadku aplikacji posiadających niewielkich rozmiarów sterty (do kilkudziesięciu MB) i maszyn z jednym rdzeniem – w tych sytuacjach tworzenie nowych wątków może nie tylko nie przyspieszyć procesu odśmiecania, ale i nawet go spowolnić. Jest to spowodowane dodatkowym narzutem związanym z przełączaniem kontekstu i synchronizacją. Inną sytuacją, w której Serial GC może okazać się przydatny, jest uruchamianie wielu instancji JVM na jednym urządzeniu. Użycie tego algorytmu minimalizuje wtedy wpływ, jaki operacje odśmiecania mają na pracujące w tym samym czasie pozostałe maszyny wirtualne.

Parallel GC

Parallel GC działa tak jak Serial GC, z tą różnicą, że do sprzątania obydwu generacji wykorzystuje wiele wątków. Co więcej, pozwala on na spojrzenie na proces odśmiecania z dalszej perspektywy i zdefiniowanie celów, jakie GC powinien osiągać w trakcie swej pracy. Zamiast empirycznego sprawdzania jakie rozmiary generacji najlepiej wpływają na wydajność aplikacji, możemy zdefiniować:

• jaki maksymalny czas trwania pauz typu stop-the-world jest dla nas akceptowalny,
• jaki maksymalny stosunek czasu spędzonego przeprowadzając GC do czasu normalnego działania aplikacji dopuszczamy,
• jaki powinien być maksymalny rozmiar sterty

Cele te mają priorytety zgodne z powyższą kolejnością i GC próbuje realizować każdy z nich tylko wtedy, gdy wszystkie poprzednie są osiągnięte.

Parallel GC jest dobrym wyborem, jeżeli nasz program bardzo szybko zapełnia stertę i nie przeszkadzają nam sporadyczne przerwy w jego działaniu. Przykładem może być tutaj dowolna aplikacja raportingowa, cyklicznie generująca sprawozdania na podstawie danych zawartych w bazie.

CMS

Mostly Concurrent Mark and Sweep GC - bo tak brzmi pełna nazwa tego algorytmu - stosuje wielowątkowy mark-copy podczas czyszczenia młodszej generacji. Jeżeli zaś chodzi o starszą generację, to sprawa jest nieco bardziej skomplikowana. Algorytm ten stara się skrócić czas trwania pauz typu stop-the-world, i w tym celu stosuje „głównie współbieżną” wersję strategii mark-sweep.

Każdy cykl pracy tej zmodyfikowanej strategii składa się z sześciu etapów. Są nimi kolejno:

1. Initial Mark
   Jeden z dwóch etapów, które wstrzymują działanie aplikacji. W fazie tej identyfikowane są GC roots, od których rozpocznie się proces oznaczania żywych obiektów.
   
   
2. Concurrent Mark
   Przeszukiwanie drzew referencji zakorzenionych w GC roots i oznaczanie odwiedzonych obiektów jako żywych.
   
   
3. Concurrent Preclean
   Przeszukiwanie drzew referencji zakorzenionych w obiektach, które uległy zmianie od czasu rozpoczęcia fazy Concurrent Mark.
   
   
4. Concurrent Abortable Preclean
   Jest to przedłużenie poprzedniej fazy. CMS chce zminimalizować szansę na to, że Final Remark rozpocznie pracę w tym samym momencie, w którym rozpocznie się odśmiecanie młodszej generacji, więc bazując na danych dotyczących poprzednich cykli sztucznie wydłuża czas trwania Concurrent Preclean, aby rozpocząć Final Remark mniej więcej w połowie czasu między kolejnymi operacjami czyszczenia edenu.
   
   
5. Final Remark
   Jest to drugi i zarazem ostatni etap, który wstrzymuje pracę wątków aplikacji. Jego celem jest ostateczne zlokalizowanie i oznaczenie wszystkich żywych obiektów w starszej generacji.
   
   
6. Concurrent Sweep
   Oznaczanie obszarów zajmowanych przez nieużywane obiekty jako wolnych do alokacji.

CMS minimalizuje czas trwania pauz typu stop-the-world kosztem zwiększonego obciążenia procesora. W związku z tym jest to algorytm stosowany w przypadku programów takich jak serwery aplikacyjne czy aplikacje desktopowe, gdzie responsywność jest najważniejszym priorytetem.

 

* Zarówno w przypadku Serial, jak i Parallel GC czyszczenie starszej generacji zawsze poprzedzone jest odśmiecaniem młodszej generacji, więc efektywnie mówimy tutaj o full gc.