Odśmiecanie pamięci

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Garbage collection (zbieranie nieużytków, odśmiecanie) – jedna z metod automatycznego zarządzania dynamicznie przydzieloną pamięcią, w której za proces jej zwalniania odpowiedzialny jest nie programista, lecz programowy zarządca nazwany garbage collector[1]. Pierwsza metoda odśmiecania został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.

Jest wiele sposobów określania, które fragmenty pamięci są już niepotrzebne. Opis kilku ważniejszych znajduje się poniżej.

Zliczanie referencji[edytuj | edytuj kod]

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
                     # jesli (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.[3].

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, 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[edytuj | edytuj kod]

Mark and Sweep jest kolejną metodą odśmiecania. Przy zastosowaniu tej metody 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 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ść wynosi 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].

Garbage collection przez kopiowanie[edytuj | edytuj kod]

Ta metoda polega na tym, że wszystko zostaje rekursywnie przekopiowane do innego obszaru w pamięci - najpierw kopiujemy początkowy zestaw, potem wszystko co było przez niego wskazywane, itd. Na końcu zwalniamy początkową pamięć.

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 byłby bardziej praktyczny na systemach, na 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[edytuj | edytuj kod]

Rozpatrzmy 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 odnośników
  • 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 pisze się rozszerzenia do języka z 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 wypadku 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.

Przypisy

  1. 1,0 1,1 1,2 1,3 1,4 1,5 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 p. 264
  3. en:weak reference

Zobacz też[edytuj | edytuj kod]