Odśmiecanie pamięci

Odśmiecanie pamięci (ang. garbage collection), zbieranie nieużytków, automatyczna dealokacja – jedna z metod automatycznego zarządzania dynamicznie przydzielaną pamięcią, w której za proces jej zwalniania odpowiedzialny jest nie programista, lecz programowy zarządca noszący nazwę garbage collector^[1]. Pierwsza metoda odśmiecania była opracowana w 1959 roku przez Johna McCarthy’ego w celu rozwiązania problemu ręcznego zarządzania pamięcią w Lispie. Mechanizm ten następnie został szeroko rozpowszechniony i jest wykorzystywany w wielu wysokopoziomowych językach programowania, takich jak: Smalltalk, Python, Ruby, Java, C# czy D.

Istnieje wiele sposobów określania, które fragmenty pamięci są już niepotrzebne i można je zwolnić; opis kilku ważniejszych znajduje się poniżej.

Zliczanie referencji

Zliczanie referencji (ang. reference counting) jest jedną z najprostszych metod odśmiecania. W metodzie tej alokowane obiekty posiadają dodatkowe pole, które wykorzystywane jest do zliczania odwołań do danego obiektu, co pozwala stwierdzić czy jest on jeszcze wykorzystywany. Podczas alokowania obiektu pole to ustawiane jest na 1, następnie za każdym razem, gdy do obiektu dodawane jest odwołanie, licznik ten jest zwiększany o jeden, a gdy odwołanie jest usuwane – licznik jest zmniejszany o jeden. Wyzerowanie licznika oznacza, że w programie nie istnieje żadne odwołanie do tego obiektu – nie jest on używany oraz nie ma możliwości ponownego, poprawnego odwołania się do niego, w związku z czym przydzielona mu pamięć może zostać zwolniona^[1].

Poniższy przykład napisany w pseudokodzie ilustruje tę metodę^[2]:

zmienna1 = 5         # tworzony jest obiekt A, przechowujący liczbę 5
                     # jego licznik odwołań = 1
...
                     # zmienna2 wskazuje na obiekt B, jego licznikB = k
zmienna2 = zmienna1  # zmienna2 „otrzymuje” identyfikator obiektu A,
                     # licznikB zmniejsza swą wartość o 1
                     # jeśli (licznikB == 0) to obiekt B zostanie usunięty
                     # licznik odwołań obiektu A zwiększa się i jest równy 2
                     # licznik odwołań = 2

usuń zmienna1        # licznik odwołań jest zmniejszany o 1
                     # licznik odwołań = 1
                     # obiekt A wciąż istnieje
...
usuń zmienna2        # licznik odwołań jest zmniejszany o 1
                     # licznik odwołań = 0
                     # obiekt A zostaje usunięty z pamięci

Metoda ta nie gwarantuje zwolnienia wszystkich niepotrzebnych obszarów w sytuacji, gdy występują tzw. wzajemne (cykliczne) odwołania. Przykładowo, jeśli X zawiera wskaźnik na Y, a Y zawiera wskaźnik na X (np. są to dwa komunikujące się ze sobą obiekty), to licznik odwołań w każdym z tych obiektów może nigdy nie osiągnąć zera. W związku z tym wiele języków programowania (np. Java, Python) wprowadza tzw. słabe wskaźniki.

W zliczaniu odnośników dodatkowe obliczenia związane z pracą kolektora nieużytków są rozłożone w czasie, gdyż wszystkie operacje na obiektach muszą dbać o ich liczniki, co może skutkować znacznie mniejszym – lub też przeciwnie – znacznie większym, obciążeniem w porównaniu z innymi metodami.

Metoda ta jest używana m.in. przez system plików w Uniksie (jednostka to i-węzeł, odnośniki to twarde dowiązania), GTK+ (do widgetów), Perl 5 czy Python. Jest również implementowana w C++ za pomocą wskaźników dzielonych z biblioteki Boost (boost::shared_ptr), a od C++11 dostępna w bibliotece standardowej jako std::shared_ptr.

Mark and Sweep

Mark and Sweep jest kolejną metodą odśmiecania. W niej, z każdym dynamicznie zaalokowanym obiektem związany jest tzw. markbit określający czy dany obiekt jest jeszcze używany (markbit ustawiony na 1), czy też jest już niepotrzebny (ustawiony na 0). W metodzie tej pamięć nie jest odzyskiwana bezpośrednio po stwierdzeniu, że obiekt jest już niepotrzebny, lecz dopiero w momencie przekroczenia pewnego progu wykorzystania pamięci. Działanie programu jest wtedy zatrzymywane i uruchamiana jest faza odśmiecania^[1].

Faza odśmiecania dzieli się na dwa etapy^[1]:

Mark – w której program GC identyfikuje wszystkie obiekty, które są jeszcze wykorzystywane i ustawia ich markbity na 1;
Sweep – w której program GC usuwa nieużywane obiekty (te, których markbit był ustawiony na 0) oraz resetuje markbit obiektów pozostawionych.

Zaletą tej metody jest fakt, że w przeciwieństwie do zliczania referencji, nie istnieje problem cyklicznych zależności^[1].

Wadą jest natomiast to, że potrzebne jest wstrzymanie działania programu podczas fazy GC. Sprawia to, że metoda ta jest mało przydatna w systemach czasu rzeczywistego. Prowadzi ona także do fragmentacji pamięci. Jej złożoność obliczeniowa wynosi $\mathrm {O} (V+E),$ gdzie $V$ to liczba istniejących obiektów, a $E$ – referencji (faza „mark” wykonuje DFS, a faza „sweep” odwiedza wszystkie obiekty)^[1].

Odśmiecanie pamięci przez kopiowanie

Ta metoda polega na tym, że wszystko zostaje rekursywnie przekopiowane do innego obszaru w pamięci – najpierw kopiowany jest początkowy zestaw, potem – wszystko, co było przez niego wskazywane itd. Na końcu zwalniany jest początkowy obszar pamięci.

W ten sposób oszczędza się na konieczności ustawiania bitów w „mark and sweep” i – co ważniejsze – regularnie defragmentuje się pamięć.

Problemy to koszt kopiowania oraz, co znacznie poważniejsze, konieczność posiadania dużej ilości wolnej pamięci. Ten sposób jest bardziej praktyczny w systemach, w których możliwa jest tymczasowa alokacja dużej ilości pamięci.

Wirtualna maszyna Javy stosuje to rozwiązanie, lecz gdy uzna, że program generuje mało „śmieci”, przechodzi do trybu „Mark and sweep”, przez co zyskuje na wydajności kosztem niewielkiej fragmentacji sterty pamięci.

Problem śmiertelności niemowląt

Rozpatrywany jest następujący kod:

x = foo (new X(parametry), new Y(parametry))

alokowany jest obiekt typu X
alokowany jest obiekt typu Y
- jeśli podczas tej alokacji system zdecyduje się przeprowadzić „garbage collection”, obiekt typu X zostanie zwolniony, ponieważ nie ma do niego żadnych odwołań
wywoływane jest foo. Jeśli X zostało zwolnione, może nastąpić naruszenie ochrony pamięci lub inny poważny i trudny do wykrycia lub usunięcia błąd.

Istnieje kilka metod radzenia sobie z tym problemem, m.in. dodanie stosu (na którym znajduje się odnośnik do obiektu typu X) do zbioru początkowego.

Problem jest poważniejszy, jeśli pisane są rozszerzenia do języka z mechanizmem garbage collection w innym języku, np. w C:

{
 LangObject x, y, z;
 x = lang_create_X(parametry);
 y = lang_create_Y(parametry);
 z = foo(x, y);
 return z;
}

W tym przypadku język ten zdecydowanie „nie wie”, że do x są odwołania. Dość powszechną metodą jest dodawanie stosu systemowego (używanego przez C) do zbioru początkowego (oczywiście nie wszystko na nim jest odwołaniem do jednostki pamięci). Jednak nie ma gwarancji, że ten odnośnik w ogóle będzie znajdował się na stosie – kompilator mógł postanowić trzymać go np. w rejestrze.

Zobacz też

Przypisy

↑ ^a ^b ^c ^d ^e ^f Richard Jones, Rafael Lins: Garbage Collection: Algorithms For Automatic Dynamic Memory Mamagement. John Wiley & Sons, 1996. ISBN 0-471-94148-4.
↑ A. Appel, Modern Compiler Implementation in Java, Cambridge University Press, 1998, s. 264.

[JonesLins-1] ↑ ^a ^b ^c ^d ^e ^f Richard Jones, Rafael Lins: Garbage Collection: Algorithms For Automatic Dynamic Memory Mamagement. John Wiley & Sons, 1996. ISBN 0-471-94148-4.

[2] A. Appel, Modern Compiler Implementation in Java, Cambridge University Press, 1998, s. 264.

[1]

[2]