• Artykuł

          

Garbage Collector, cz. I   Udostępnij na: Facebook

Autor: Piotr Zieliński

Opublikowano: 2013-04-10

Wprowadzenie

Garbage Collector należy do tematów, które powinny być doskonale znane programiście zanim jeszcze zacznie uczyć się składni języka. Niestety ze względu na łatwość pisania kodu w takich językach, jak C# czy Java, programiści zapominają o tym, co w tle musi być wykonywane za nich. To nieprawda, że programista jest zwolniony z zarządzania obiektami w języku C#. Aplikacje .NET często muszą korzystać z zasobów niezarządzanych i z tego względu odpowiedzialność za ich zwolnienie spoczywa w całości na programiście. Nawet w przypadku obiektów zarządzanych niezbędna jest znajomość zasady działania GC, ponieważ umożliwia to pisanie optymalnego kodu i uniknięcia błędów na wczesnym etapie.

Zarządzanie pamięcią – C# a CPP

Największą chyba różnicą między C# a C++ jest sposób zarządzania pamięcią. W CPP programiści musieli samodzielnie zwalniać pamięć, aby nie doszło do tzw. wycieków pamięci (memory leak). W świecie zarządzanych języków, zadanie programisty jest dużo łatwiejsze, ponieważ Garbage Collector odpowiada za usuwanie niepotrzebnych elementów. Niestety, jak to z ułatwieniami bywa, nieumiejętne korzystanie z języka może poskutkować bardzo negatywnym wpływem na wydajność.

GC przechowuje dane na tzw. zarządzanej stercie (managed heap), gdzie alokacja pamięci jest bardzo szybka. W CPP, aby zaalokować jakiś element, najpierw trzeba było znaleźć wystarczający blok pamięci. W C# zarządzana sterta nie ma pustych miejsc między poszczególnymi obiektami. Struktura ma charakter uporządkowany i po kolekcji (GC.Collect) elementy są zawsze układane jeden za drugim. Z tego względu alokacja pamięci to nic innego, jak ustawienie wskaźnika na koniec listy – jest to bardzo szybkie.

Algorytm Mark & Sweep

Zasada działania GC jest dość skomplikowana, ale warto zacząć od podstaw, czyli od przedstawienia algorytmu Mark &Sweep. Każda implementacja GC bazuje na tym algorytmie.

Garbage Collector oczywiście służy do zwalniania pamięci i wyręcza programistów z pamiętania, jakie zasoby nie są już potrzebne. Wielu zapewne doskonale pamięta operator delete z CPP czy funkcję free z C. W językach zarządzanych, znalezieniem niepotrzebnych obiektów zajmuję się Garbage Collector.

Podstawowy algorytm mark and sweep sprowadza się do dwóch faz: mark (znakowanie) oraz sweep (usuwanie). W fazie znakowania specjalna flaga ustawiana jest dla tych obiektów, do których można było dojść po referencjach, pochodzących z korzeni. GC przechodzi zatem od korzenia przez wszystkie możliwe obiekty. Jeśli klasa A ma referencję do klasy B, wtedy GC przejdzie z A do B i ustawi odpowiednią flagę. Następnie, w fazie sweep, wszystkie nieoznaczone obiekty są usuwane. Faza MARK umożliwia znalezienie potrzebnych, używanych obiektów. Skoro można dotrzeć do jakiegoś obiektu od korzenia, to znaczy, że jest on używany. Korzenie to, m.in.:

  • pola statyczne,
  • parametry metod,
  • zmienne lokalne,
  • rejestry CPU.

Algorytm w pseudokodzie można naszkicować następująco:

void Collect()
{
    // Faza I
    for each root (r)
    Mark (r);
    // Faza II
    Sweep ();
}

Metoda Mark jest oczywiście rekurencyjna – jako parametr przyjmuje wskaźnik do korzenia, a następnie przeszukuje całe drzewo obiektów. Spróbujmy naszkicować metodę Mark:

void Mark (object objectPointer)
{
    if (objectPointer.IsMarked == false)
    {
        objectPointer.IsMarked = true; 
        for each Object child of objectPointer)
        {
            Mark(child);
        }
    }
}

Aby uniknąć zapętleń, należy sprawdzać, czy obiekt został już oznakowany. Przyjrzyjmy się drugiej fazie (sweep):

void Sweep ()
{
    foreach objectPointer in the heap
    {
        if (objectPointer.IsMarked)
        {
            objectPointer.IsMarked = false
        }
        else
        {
            Release(objectPointer);
        }
    }
}

Proszę zwrócić uwagę, że flaga ustawiana jest na false – dzięki temu, przy następnym uruchomieniu GC, będzie możliwa pierwsza faza. Wszystkie obiekty nieoznakowane są usuwane z pamięci.

Podział na generacje

Automatyczne zarządzanie pamięcią może być bardzo czasochłonne i bez wątpienia jest trudnym zadaniem. Uruchamianie algorytmu Mark&Sweep za każdym razem, gdy brakuje pamięci nie jest optymalnym podejściem. Aplikacja w końcu może alokować tysiące obiektów. Z tego względu, pamięć alokowana w .NET przechowywana jest w tzw. generacjach. Istnieją trzy generacje:

  • Generation 0 – zwolnienie obiektu z GEN0 jest szybkie i mało kosztowne. Przechowywane są w niej obiekty używane tylko przez krótki czas,
  • Generation 1 – obiekty, które „awansowały” z GEN0. Zwolnienie zasobów w GEN1 jest wolniejsze,
  • Generation 2 – analogicznie do GEN1 – usuwanie zasobów jest wolniejsze niż ma to miejsce w GEN0 lub GEN1.

Powyższa strategia została opracowana na podstawie następujących przypuszczeń i obserwacji:

  • im nowszy obiekt, tym większe szanse, że wkrótce zostanie on zwolniony,
  • starsze obiekty – skoro nie zostały jeszcze zwolnione, może to oznacza, że ich czas życia będzie dłuższy niż dla nowo zaalokowanych,
  • wykonanie algorytmu Mark&Sweep na całym grafie jest zbyt czasochłonne. Lepiej podzielić operacje na podgrupy.

Jeśli obiekt używany jest przez krótki czas, a potem zwalniany, to działanie odbywa się w GEN0. Jeśli podczas zwalniania zasobów, czyli w momencie wywołania metody GC.Collect(), któreś obiekty przetrwają, wtedy awansowane są do następnej generacji.  GC analizuje ile razy obiekt musi przetrwać wywołanie GC.Collect, aby zostać awansowany do następnej generacji. Wartości tych progów przydzielane są przez GC dynamicznie, aby zapewnić maksymalną wydajność działania aplikacji.

Jeśli np. obiekt nie został zwolniony po wywołaniu GC.Collect dziesięć razy (Mark&Sweep), wtedy jest bardzo prawdopodobne, że przez większość czasu działania aplikacji będzie on potrzebny – a co za tym idzie, szkoda marnować czas na mieszanie go z obiektami krótkotrwałymi. Ktoś może zadać pytanie, ale co za problem trzymać wszystkie zasoby w jednej generacji? GC po każdym zwalnianiu pamięci porządkuje zasoby tak, że nie ma wolnej przestrzeni pomiędzy obiektem A a obiektem B (patrz różnice między C# a CPP). Jeśli obiekt A zużywa zasoby pomiędzy przestrzenią adresową 0-4, to obiekt B będzie zajmował od 5-9. Dzięki temu, jak to zostało już wspomniane we wprowadzeeniu, deklaracja nowych obiektów będzie szybka, ponieważ bardzo łatwo wyznaczyć adres w pamięci – jest to po prostu następna liczba (w tym przypadku obiekt trzeci byłby zadeklarowany w polu 10). Dzięki takiej strategii, również fragmentacja pamięci przestanie być problemem. Obiekty długotrwałe powodowałyby problem, ponieważ należałoby je “przesuwać” po każdym GC.Collect. Po za tym, po co wykonywać algorytm Mark&Sweep dla drzewa obiektów, które jest potrzebne przez 90% czasu działania aplikacji?

Kolejne pytanie brzmi: jaki jest rozmiar poszczególnych generacji? Dokładne dane ciężko jest określić, ponieważ zależy to od implementacji wewnętrznej, a w różnych wersjach .NET może to wyglądać inaczej. GC określa budżet dla generacji. Często przyjmuje się, że dla GEN0 jest to 256 KB. Kolekcja wywoływana jest w momencie, gdy nie ma miejsca dla następnego obiektu. Jeśli zatem użytkownik chce utworzyć obiekt A i nie ma wystarczająco dużo miejsca w GEN0, wywoływany jest GC.Collect. Następnie, jeżeli po kolekcji jest już miejsce, wtedy obiekt jest po prostu alokowany. W przeciwnym wypadku, część obiektów musi zostać wypromowana do GEN1, aby powstało miejsce dla nowych danych.

Rozmiar 256 jest doskonałym wyborem. Procesor posiada własny cache, który jest rozdzielony na kilka warstw. Jeśli GEN0 ma rozmiar 256, istnieje duże prawdopodobieństwo, że w całości zmieści się na warstwie L2.

Podsumowując:

  1. Wprowadzono trzy generacje w celu optymalizacji. GEN0 jest szybka i zawiera obiekty często deklarowane i zwalniane.
  2. Pamięć jest deklarowana w sposób zwarty – nie ma wolnej przestrzeni między obiektami (brak fragmentacji).
  3. Obiekty w tej samej generacji są używane w aplikacji przez taki sam czas.
  4. Tylko część pamięci jest przeznaczona dla aplikacji .NET (tzw. commited memory space). Jeśli potrzeba więcej, wtedy system operacyjny przydziela pamięć z “uncommited space” do “commited space”.
  5. GC.Collect uruchamiany jest, gdy pewien próg zużycia pamięci zostanie przekroczony – a nie natychmiast, gdy któryś z obiektów jest już niepotrzebny.

Destruktory

Jeśli miał ktoś do czynienia np. z CPP, z pewnością kojarzy pojęcie destruktora. Jest to metoda wywoływana w momencie zwalniania obiektu z pamięci (przeciwieństwo konstruktora). Zarówno w CPP, jak w C#,  nazwa destruktora stanowi tylda ‘~’ plus nazwa klasy. Przykład:

class MyClass
{
    MyClass(){}// standardowy konstruktor
    ~ MyClass()
    {
           // obiekt zwalniany z pamięci
    }
}

Jednak sam sposób działania destruktorów w C# różni się całkowicie od CPP.  Przede wszystkim, destruktor to nic innego jak metoda Finalize:

protected override void Finalize()
{
   try
   {
      // ciało destruktora
   }
   finally
   {
      base.Finalize();
   }
}

Na poziomie kompilacji generowana jest metoda Finialize (zamiast destruktora), a więc metoda typu protected, w której można umieścić wszelkie zwalniane zasoby (głównie niezarządzane).

Powyższe rozważania wyglądają prosto i klarownie. W rzeczywistości jednak, problem nie jest tak prosty. Klasy z destruktorem\Finalize są DUŻO trudniejsze do usunięcia z pamięci:

  • gdy seria obiektów nie ma Finalize, wtedy GC po prostu czyści pamięć od początkowego adresu aż do końca. W przypadku Finalize musi po kolei wywoływać Finalize i zwalniać pamięć – nie da się tego zrobić za jednym podejściem (w pojedynczym „batchu”),
  • istnieje duża szansa, że obiekt z Finalize dostanie promocję do GEN1 lub nawet GEN2. Zwolnienie pamięci z GEN1 jest dużo wolniejsze niż z GEN0. A dlaczego to może się zdarzyć?

Przede wszystkim GC oprócz listy obiektów zawiera również specjalną kolejkę (finalization queue), która posiada wskaźniki do obiektów zawierających metodę Finalize. Załóżmy, że wywołana jest metoda GC.Collect. GC sprawdza, które obiekty są nieosiągalne. Załóżmy również, że obiekt zawierający Finalize jest teraz nieosiągalny. GC przeszukuje finalization queue i dodaje dany obiekt do następnej kolejki, nazwanej freachable queue (finalization reacheable). Jeśli zwalniany obiekt nie znajdowałby się w finalization queue (ponieważ nie ma destruktora), wtedy po prostu standardowo zostałby zwolniony. W tym przypadku został jednak przeniesiony do freachable queue i z tego względu będzie ponownie widziany jako obiekt osiągalny – nie został w końcu jeszcze zwolniony. I to jest właśnie moment, kiedy GC może ponownie przeszukać GEN0 i awansować obiekt do następnej generacji – ponieważ obiekty w freachable queue traktowane są jako osiągalne.

Zatem, wszystkie obiekty z destruktorem (a właściwie ich wskaźniki) umieszczane są domyślnie w finalization queue. Jeśli staną się one nieosiągalne, wtedy umieszczane są w freachable queue i w tym momencie znów widziane są jako osiągalne. Co dalej? Do dyspozycji jest osobny wątek, który wywołuje metodę Finalize po kolei dla wszystkich obiektów w freachable queue. Po wywołaniu Finalize, obiekt może zostać zwolniony już całkowicie z pamięci. Ale to pokazuje, że potrzeba przynajmniej dwóch GC.Collect, aby usunąć obiekt z pamięci: najpierw, aby przenieść go do freachable queue, potem osobny wątek wywoła Finalize, a dopiero wtedy, następna kolekcja (GC.Collect) zwolni obiekt całkowicie. Ponadto, jest bardzo prawdopodobne, że w międzyczasie obiekt zostanie zawansowany do następnej generacji, co spowoduje znaczący spadek wydajności.

Jak zostało wspomniane, tylko jeden wątek jest odpowiedziany za wywoływanie destruktora z listy freachable. Co zatem się stanie w przypadku, gdy umieścimy niekończącą się pętlę w destruktorze? Niestety, istnieje wówczas zagrożenie, że nie wszystkie destruktory zostaną wywołane. Nie należy jednak pisać metod Finalize w ten sposób, że polegają one na tym, że tylko jeden wątek je wykonuje. W przyszłości Microsoft może zmienić architekturę i wprowadzić wielowątkowość.

Interfejs IDisposable

Destruktory są dobrym sposobem na zwalnianie zasobów. Niestety mają one charakter niedeterministyczny, co oznacza, że nie wiadomo, kiedy zostaną wywołane. Czasami jednak taka informacja jest bardzo cenna. Jeśli kod odpowiada za połączenie z bazą danych, zwolnienie zasobów powinno nastąpić natychmiast po skończeniu pracy z bazą.

W języku C# interfejs IDisposable służy do zwalniania zasobów. Dzięki niemu, programista sam może zdecydować, kiedy zwolnić zasoby (zwykle niezarządzane) i nie musi czekać na wywołanie destruktora.  Jeśli destruktor został zdefiniowany, dobrą praktyką jest implementowanie IDisposable. Jak najbardziej dopuszczalne jest jednak implementowanie wyłącznie IDisposable, bez destruktora – tylko przeciwna praktyka jest błędna. Sporo programistów niestety źle implementuje wspomniany interfejs, a mianowicie:

public class MyClass : IDisposable
{
   #region IDisposable Members

   public void Dispose()
   {
       // zwalnianie zasobow
   }
   #endregion
}

Niestety, sam interfejs wymusza jedynie implementację metody Dispose. Powyższe rozwiązanie jest zdecydowanie niewłaściwe. Prawidłowa wersja powinna wyglądać następująco:

public class MyClass:IDisposable
{
    private bool IsDisposed=false;
    public void Dispose()
    {
        Dispose(true);
        GC.SupressFinalize(this);
    }
    protected void Dispose(bool diposing)
    {
        if(!IsDisposed)
        {
            if(disposing)
            {
                // zwalniaj zasoby zarządzalne
            }
            // zwalniaj zasoby niezarządzalne
        }
        IsDisposed=true;
    }
    ~MyClass()
    {
        Dispose(false);
    }
}

Powyższa implementacja gwarantuje, że gdy obiekt będzie automatycznie czyszczony przez GarbageCollector, to zasoby niezarządzane i tak zostaną zwolnione. Udało się to uzyskać dzięki implementacji destruktora, który wywołuje się zawsze, gdy GC zwalnia obiekt. W przypadku, gdy to GC zwalnia obiekt, a nie użytkownik ręcznie, metoda Dispose nie jest wywoływana, więc jedynym miejscem na zrobienie tego jest destruktor.

Następny scenariusz to przypadek, gdy to sam użytkownik chce zwolnić obiekt. W tym przypadku należy poinformować GC, że programista bierze na siebie odpowiedzialność za obiekt (metoda SupressFinalize), a tym samym destruktor nie zostanie wywołany (co uchroni przed zapętleniem i zwiększy wydajność).

Ponadto, dodano flagę IsDisposed, która umożliwia np. wyrzucenie wyjątku w przypadku, gdy użytkownik drugi raz chce zwolnić obiekt.

Duże obiekty

Wcześniejsze rozważania dotyczyły przechowywania i zwalniania małych obiektów. GC posiada optymalizacje dla obiektów zajmujących więcej niż 85 000 bajtów. Ten próg (85 k) może oczywiście się zmienić wraz z nowymi implementacjami GC. Należy jednak pamiętać, że bardzo duże obiekty zostaną umieszczone na osobnej stercie – Large Objects Heap. Dlaczego zdecydowano się na takie posunięcie?

Przede wszystkim małe obiekty w .NET są często przemieszczane w pamięci. Zwiększa to wydajność i likwiduje problemy z fragmentacją. Przesunięcie tak dużych obiektów jak 85 kilobajtów wymagałoby czasu. Z tego względu, wszystkie obiekty na tej specjalnej stercie nie zmieniają swojego adresu (pinned). Ponadto, sterta dużych obiektów należy do generacji numer 2, co należy mieć na uwadze. Zapotrzebowanie na duże obiekty tylko na krótki czas spowoduje częste kolekcje. Decydując się na użycie dużych obiektów, należy tak zaprojektować systemy, aby były one potrzebne przez dłuższy czas. Częste deklarowanie krótkotrwałych, dużych obiektów spowolni znacząco działanie GC. Należy pamiętać, że kolekcja GEN2 jest najbardziej czasochłonna.

W celu potwierdzenia tezy o istnieniu specjalnej sterty warto napisać mały eksperyment:

public static void Main()
{
    byte data=new byte();
    Console.WriteLine(GC.GetGeneration(data));
}

Na ekranie wyświetli się 0 – jest to jak najbardziej zrozumiałe. Obiekty małe należą na początku do GEN0. Następnie, analogiczny test można wykonać z tablicą danych:

public static void Main()
{
    byte[] data=new byte[90000];
    Console.WriteLine(GC.GetGeneration(data));
}

Tablica zostanie zadeklarowana w GEN2, a konkretnie na wspomnianej, specjalnej stercie.

Zakończenie

Znajomość GC jest niezbędna, aby napisać optymalny kod. Dzięki zrozumieniu GC można uniknąć poważnych błędów już na etapie pisania kodu. Oczywiście, nawet perfekcyjna umiejętność posługiwania się GC, nie zwalnia programistów z ciągłego profilowania aplikacji pod kątem zużycia zasobów, procesora czy liczby wątków. Zrozumienie destruktorów pomaga w prawidłowym i optymalnym zwalnianiu zasobów. Dzięki temu, dla programisty powinno być jasne, że interfejs IDisposable jest bardzo ważny, jeśli klasa potrzebuje zaimplementowania metody Finalize.

 

          

Piotr Zieliński

Absolwent informatyki o specjalizacji inżynieria oprogramowania Uniwersytetu Zielonogórskiego. Posiada szereg certyfikatów z technologii Microsoft (MCP, MCTS, MCPD). W 2011 roku wyróżniony nagrodą MVP w kategorii Visual C#. Aktualnie pracuje w General Electric pisząc oprogramowanie wykorzystywane w monitorowaniu transformatorów . Platformę .NET zna od wersji 1.1 – wcześniej wykorzystywał głównie MFC oraz C++ Builder. Interesuje się wieloma technologiami m.in. ASP.NET MVC, WPF, PRISM, WCF, WCF Data Services, WWF, Azure, Silverlight, WCF RIA Services, XNA, Entity Framework, nHibernate. Oprócz czystych technologii zajmuje się również wzorcami projektowymi, bezpieczeństwem aplikacji webowych i testowaniem oprogramowania od strony programisty. W wolnych chwilach prowadzi [blog o .NET i tzw. patterns & practices]http://www.pzielinski.com/.