Kodujże!

blog krakoskiego programisty

Tag: Performance

Algorytmy GC. Serial, Parallel, CMS

Wpis ten jest kontynuacją wątku o podstawach działania mechanizmów GC w HotSpot JVM. Informacje zawarte tutaj odnoszą się do wiedzy przedstawionej w poprzednim artykule, w związku z czym tych wszystkich, którzy nie mieli okazji go przeczytać, zapraszam tutaj: JVM Garbage Collector. Wprowadzenie. 🙂

1. JVM Garbage Collector. Wprowadzenie.
2. Algorytmy GC. Serial, Parallel, CMS

Algorytmy GC

HotSpot JVM oferuje cztery algorytmy działania Garbage Collectora: SerialParallelMostly-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.Algorytmy GC - Struktura sterty. Mark-Sweep.
  • Mark-Sweep-Compact – mark-sweep z dodatkowym kompaktowaniem sterty.Algorytmy GC - Struktura sterty. Mark-Sweep-Compact.
  • Mark-Copy – kopiowanie żywych obiektów do nowego miejsca na stercie.Algorytmy GC - Struktura sterty. Mark-Copy.

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, bo 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.

JVM Garbage Collector. Wprowadzenie.

W ramach pierwszego technicznego wpisu postanowiłem zagłębić się w temat Garbage Collectorów. Praktycznie każdy programista pracujący z technologiami stworzonymi w oparciu o JVM słyszał o GC – że jest to mechanizm, który pracuje w tle, sprząta po nas, i… to w zasadzie tyle. Oczywiście mocno to uogólniam, ale prawdą jest, że jest to rodzaj specjalistycznej wiedzy, niewymaganej w przypadku większości stanowisk developerskich. Nie znaczy to oczywiście, że znajomość pracy GC jest nieprzydatna. Wręcz przeciwnie! Jest kluczowa, jeżeli chcemy „podkręcić” działanie aplikacji.

Post ten jest tylko wprowadzeniem do tematu. Różne algorytmy działania „odśmiecacza pamięci” (czy tylko mnie gryzie ta polska nazwa? :)) postaram się opisać w osobnych wpisach.

1. JVM Garbage Collector. Wprowadzenie.
2. Algorytmy GC. Serial, Parallel, CMS

Czym jest Garbage Collector?

Garbage Collector to program, którego głównym zadaniem jest usuwanie z pamięci nieużywanych obiektów. Gdyby nie jego działanie, sterta, na którą trafiają nowo tworzone obiekty, szybko by się zapełniała i tym samym uniemożliwiała dalsze funkcjonowanie aplikacji. Często nie zdajemy sobie sprawy ze skali tego problemu, a wystaczy zerknąć na pierwszy lepszy przykład.

BigDecimal jest immutable, w związku z czym wszelkie operacje arytmetyczne związane z tą klasą zwracają jako rezultat działania nowe obiekty. Powyższa metoda wywołana dla listy tysiąca elementów dołoży do sterty (za sprawą metody add) co najmniej tyle samo nowych instancji BigDecimal. Gdyby nie Garbage Collector, powtarzające się wykonania sum zapchałyby w końcu przestrzeń adresową programu i zakończyły jego działanie z wypisanym na konsoli  OutOfMemoryError.

Zasada działania

Różne implementacje maszyny wirtualnej Javy stosują różne podejście w kwestii automatycznego zarządzania pamięcią. Opis działania zamieszczony poniżej dotyczy HotSpot JVM, czyli maszyny wirtualnej dostarczanej przez firmę Oracle. Wybór tej implementacji podyktowany jest tym, że jest ona po prostu najpopularniejsza.

HotSpot oferuje cztery algorytmy GC: SerialParallelCMS (Concurrent Mark-Sweep)Garbage First (G1). Szczegóły implementacyjne każdego z nich opiszę w późniejszych wpisach. Póki co jednak spojrzymy na nie z dalszej perspektywy, ponieważ o ile pomiędzy poszczególnymi algorytmami istnieją poważne różnice, tak wszystkie z nich działają według podobnego schematu.

W pierwszym kroku Garbage Collector znajduje wszystkie żywe obiekty. W drugim usuwa pozostałe i ewentualnie reorganizuje pamięć programu, aby uniknąć problemu fragmentacji.

Problem fragmentacji

Zanim przyjrzymy się z bliska procesom znajdowania i usuwania obiektów, zatrzymajmy się na chwilę przy problemie fragmentacji.

W miarę tworzenia nowych obiektów zabieramy coraz więcej miejsca ze sterty. Pamięć alokowana jest w sposób ciągły i, tuż przed wkroczeniem do akcji Garbage Collectora, wygląda jak na obrazku poniżej.

JVM Garbage Collector - Sterta przed czyszczeniem przez GC

Gdyby GC nie przejmował się fragmentacją i zakończył swoją pracę po zwolnieniu pamięci, to mogłoby się okazać, że struktura sterty jest mocno „podziurawiona”.

JVM Garbage Collector - Sterta po czyszczeniu przez GC

Jest to bardzo zła sytuacja z co najmniej dwóch powodów. Po pierwsze, kiedy tworzymy nowy obiekt, to JVM spędza więcej czasu na szukaniu odpowiedniego obszaru do alokacji. Po drugie, może być tak, że żaden z wolnych bloków nie jest na tyle duży, by ten obiekt zmieścić.

Szukanie żywych obiektów

Garbage Collector Roots to obiekty osiągalne spoza sterty, czyli takie, do których możemy odwołać się w sposób bezpośredni, a nie tylko poprzez łańcuch referencji.

W powyższym przykładzie  user  traktowany jest jako GC Root, ale  user.creationDate  już nie, ponieważ aby użyć tego obiektu potrzebujemy referencji do  usera .

Kiedy JVM uzna, że należy wykonać cykl GC, to w ramach szukania żywych obiektów najpierw zdefinuje listę takich GC Roots, a następnie przeszuka zakorzenione w nich drzewa referencji i zaznaczy wszystkie napotkane obiekty jako osiągalne. Te, których w tym czasie nie oznaczy, zostaną w późniejszym etapie usunięte ze sterty.

JVM Garbage Collector - GC Roots

GC Roots to na przykład zmienne lokalne i parametry metody wykonywanej w momencie uruchomienia Garbage Collectora, aktywne wątki, zmienne statyczne załadowanych klas (oczywiście pod warunkiem, że ich classloadery same w sobie są osiągalne), zasoby JNI.

Generacje

Gdyby GC miał za każdym razem przeglądać w ten sposób wszystkie zaalokowane obiekty, to czas spędzony przez niego na wykonywaniu odśmiecania miałby poważny wpływ na wydajność aplikacji. Aby zaradzić temu problemowi, twórcy JVM w trakcie projektowania struktury sterty wzięli pod uwagę prostą obserwację, że większość obiektów zaraz po utworzeniu jest niepotrzebna (przykład z początku tego wpisu dotyczący instancji klasy BigDecimal dobrze to obrazuje) i zdecydowali się podzielić ją na obszary zwane generacjami.

JVM Garbage Collector - Generacje

Young Generation to obszar, w którym żyją nowe obiekty. Dzieli się na trzy strefy: edensurvivor one, oraz survivor two. Kiedy tworzymy nowy obiekt, pamięć przeznaczona dla niego alokowana jest w strefie eden. Wraz z działaniem aplikacji strefa ta zapełnia się coraz bardziej, aż w końcu jest w niej na tyle mało miejsca, że do akcji wkracza Garbage Collector. Garbage Collector przeprowadza marking edenu i przenosi do survivor one żywe obiekty, jednocześnie odrzucając te nieosiągalne. Cykl zaczyna się od nowa, z tą różnicą, że GC analizuje teraz również strefę survivor one, a na koniec przenosi wszystkie żywe obiekty do survivor two. W każdej następnej iteracji role stref survivor się odwracają. Takie podejście rozwiązuje problem fragmentacji, ponieważ eden nieustannie ulega całkowitemu czyszczeniu.

Obiekty ze stref survivor, które przetrwały w nich wystarczająco długo, przenoszone są do obszaru nazwanego Old Generation. Jest on znacznie większy w porównaniu do Young Generation*, dlatego też GC odbywa się w nim rzadziej. Old Generation nie podlega takiemu samemu podziałowi na strefy jak Young Generation, a sposób jego czyszczenia zależy od implementacji Garbage Collectora.

Procesy czyszczenia generacji YoungOld nazywają się odpowiednio Minor GCMajor GC.

Usuwanie nieosiągalnych obiektów

Istnieją trzy główe strategie dotyczące usuwania nieosiągalnych obiektów. Możemy:

  • oznaczyć zajmowane przez nie obszary pamięci jako wolne do alokacji,
  • zrobić to, co wyżej i dodatkowo przesunąć żywe obiekty w powstałe wolne miejsca, aby uniknąć problemu fragmentacji,
  • skopiować wszystkie żywe obiekty do nowego obszaru pamięci.

Przykład implementacyjny ostatniej strategii został przedstawiony przy okazji definiowania czym jest Young Generation. Prawie wszystkie algorytmy przeprowadzają w ten sposób Minor GC. Major GC natomiast zależy od konkretnej wersji algorytmu.

Podsumowanie

Jest to koniec części wprowadzającej do tematu Garbage Collectorów. O ile pomiędzy poszczególnymi algorytmami GC istnieją poważne różnice, tak opisane tutaj zagadnienia stanowią swoistego rodzaju fundament ich działania. W późniejszych wpisach postaram się szczegółowiej opisać te algorytmy, a tymczasem wszystkich zainteresowanych tematem zachęcam do lektury poniższych źródeł. 🙂

 

* Jak zauważył w komentarzu Bartek Kowalczyk, dzięki tzw. Adaptive Size Policy rozmiary generacji mogą się zmieniać w zależności od potrzeb aplikacji.

© 2019 Kodujże!

Theme by Anders NorenUp ↑