Garbage collection
Z Wikipedii
Garbage collection (zbieranie nieużytków) to architektura zarządzania pamięcią, w której proces zwalniania nieużywanych jej obszarów odbywa się automatycznie. Mechanizm taki stosuje się na przykład w wysokopoziomowych językach (Python, Ruby i Java). Jest wiele sposobów określania które fragmenty pamięci są już niepotrzebne. Opis kilku ważniejszych znajduje się poniżej.
Spis treści |
[edytuj] Liczenie odnośników (reference counting)
W tej metodzie każda jednostka zarezerwowanej pamięci ma licznik, w którym jest zapisana liczba odwołań do tej jednostki.
Za każdym razem, kiedy dodajemy odwołanie, zwiększamy licznik we wskazywanej jednostce, a kiedy odwołanie usuwamy, zmniejszamy licznik. Jeśli wartość licznika osiągnęła zero, to usuwamy wszystkie odnośniki wychodzące z tego obszaru pamięci i zwalniamy go.
Poniższy przykład, w abstrakcyjnym języku, ilustruje tę metodę:
zmienna1 = 5 # tworzony jest obiekt A, przechowujący liczbę 5
# jego licznik odwołań = 1
...
zmienna2 = zmienna1 # zmienna2 "dostaje" identyfikator obiektu A,
# licznik odwołań tego obiektu zwiększa się
# 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 jeśli 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), licznik w żadnym z nich nigdy nie osiągnie zera.
W liczeniu odnośników dodatkowe obliczenia związane z pracą kolektora nieużytków są rozłożone w czasie, gdyż wszystkie operacje muszą dbać o 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żywane m.in. przez system plików w Uniksie (jednostka to "inode", 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).
[edytuj] Mark and Sweep
W Mark and Sweep każda jednostka pamięci zawiera pojedynczy bit, który jest na początku czysty. Kiedy system postanowi wejść w fazę "garbage collection", zaczyna od pewnego zbioru komórek, o których wie, że istnieją do nich odwołania, zaznacza w nich ten bit i rekursywnie przechodzi przez wszystkie komórki przez nie wskazywane. Kiedy już wszystko zostało oznaczone, komórki bez znacznika są zwalniane, bo na pewno nic na nie nie wskazuje, po czym znacznik jest czyszczony wszystkim komórkom.
Mark and Sweep jest obecnie najpopularniejszą metodą.
[edytuj] Garbage collection przez kopiowanie
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.
[edytuj] Problem śmiertelności niemowląt
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 na nie ż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
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.
