Odśmiecanie pamięci

Odśmiecanie pamięci
Polecane artykuły
Typizacja Prosty program CAD Poka yoke Testowanie oprogramowania Diagram stanów Ganttproject Alokacja pamięci Mapowanie strumienia wartości

Odśmiecanie pamięci (Garbage collection) metoda automatycznego zarządzania pamięcią. Proces ten polega na sprawdzeniu wszystkich obiektów, a następnie zwalnianiu, tych do których nie ma aktualnych referencji. Zwolniona pamięć może być wykorzystana przez kolejne obiekty. Odśmiecanie zostało wprowadzone przez Johna McCarthy około roku 1959. Szeroko stosowany w większości języków wysokiego poziomu, takich jak Java, C++, C#, Ruby, SmallTalk. Dzięki temu procesowi programista nie musi martwić się o zwrot pamięci - tworzy potrzebne mu obiekty, a gdy już ich nie potrzebuje, giną samoczynnie co zapobiega tzw. wyciekowi pamięci.

Wyróżnia się dwie fazy odśmiecania pamięci:

• Identyfikacja nieosiągalnych przez program obiektów w pamięci
• Odzyskiwanie pamięci

Fazy te mogą się przenikać.

Wady i zalety

Zalety:

• Brak konieczności ręcznego zarządzania pamięcią
• Eliminacja wycieków pamięci
• Zabezpieczenie przed dealokacją pamięci
• Wydajne implementacje trwałych struktur danych

Wady:

• Dodatkowy narzut
• Brak kontroli nad momentem niszczenia obiektu

Podstawowe algorytmy odśmiecania

Zliczanie referencji (Reference Counting) – jedna z prostych metod odśmiecania. Polega na powiązaniu obiektu z licznikiem, który przechowuje aktualna liczbę referencji na ten obiekt. Kiedy jest tworzona nowa referencja do obiektu, następuje zwiększenie także licznika. Z kolei kiedy referencja wskazująca na obiekt wychodzi poza zasięg lub jest ustawiana na null, licznik odwołań do tego obiektu jest zmniejszany. Wykorzystując ten algorytm pojawia się problem dotyczący grup obiektów, wewnątrz których występują cykle referencji, natomiast nie ma do nich dostępu z zewnątrz.

Zaznacz i zamieć (Mark and Sweep) - metoda odśmiecania polegająca na rezerwowaniu jednego bitu w każdym tworzonym obiekcie. Pierwsza faza polega na markowaniu obiektów, czyli na przeglądaniu od stosu i statycznej pamięci oraz śledzeniu wszystkich referencji, w celu wyszukania obiektów. Jest on znakowany poprzez ustawienie mu znacznika, gdy zakończ się cały proces przeglądania wówczas obiekt niszczony co stanowi drugą fazę procesu.

Dwie fazy algorytmu:

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

Zatrzymaj i kopiuj (Stop and Copy) - program jest zatrzymywany na czas pracy odśmiecania. Sterta jest podzielona na dwie części, z których w danej chwili jedna tylko jest aktywna. Jeżeli wolne miejsce w jednej części się wyczerpie, to następuje zatrzymanie programu, a następnie tyskie aktywne obiekty są kopiowane do drugiej części. Wszystkie referencje do przekopiowania obiektów muszą zostać zaktualizowane.

Zaznacz i upakuj (Mark and Compact) – składa się z dwóch etapów, przy czym pierwszy etap jest taki sam jak w algorytmie Mark and Sweep. Drugi etap polega na upakowaniu wszystkich obiektów w taki sposób aby wyeliminować fragmentację. Wszystkie odwołania do przeniesionych obiektów muszą zostać zaktualizowane.

Odśmiecanie generacyjne (Generational GC) - obiekty podzielone są na generacje. Początkowo obiekty należą do najmłodszej generacji. Po spełnieniu określonych warunków przenoszone są do następnej generacji. Dla każdej generacji można zastosować inny algorytm odśmiecania i wykonywać odśmiecanie oddzielnie.

Odśmiecanie kopiujące (Coping GC) - metoda polega na kopiowaniu całej pamięci w do innego obszaru. Metoda mało skuteczna.

Bibliografia

• Brucke Eckel, Thinking in C++, Helion, Gliwice, 2002
• Brucke Eckel, Thinking in Java Wyd. IV, Helion, Gliwice 2006
• Krzysztof Barteczko, Podstawy programowania w Javie, PJWSTK, Warszawa 2003

Autor: Magdalena Pietrzyk