Algorytm Cheneya

Algorytm Cheneya, po raz pierwszy opisany w 1970 roku w artykule stowarzyszenia ACM przez C.J. Cheneya, stanowi metodę do odśmiecania pamięci w systemach programowych. W tym podejściu, sterta jest podzielona na dwie części, z których w danym momencie używana jest tylko jedna. Proces odśmiecania polega na kopiowaniu żywych obiektów z jednej połowy do drugiej, która staje się nową stertą. Stara sterta jest z kolei odrzucana w całości.

Proces odzyskiwania pamięci

Algorytm Cheneya odzyskuje elementy w następujący sposób:

Referencje do obiektów na stosie są analizowane. Dla każdej referencji, która wskazuje na obiekt w starej stercie, podejmowane jest jedno z dwóch działań:

Jeżeli obiekt nie został jeszcze przeniesiony do nowej sterty, tworzona jest jego identyczna kopia w nowej stercie, a referencja do starej wersji jest aktualizowana do wskazywania na nową kopię. Następnie referencja obiektu jest zmieniana tak, aby odnosiła się do nowej wersji w nowej stercie.
Jeśli obiekt został już przeniesiony do nowej sterty, wystarczy zaktualizować referencję zgodnie z przekierowującym wskaźnikiem ze starej sterty.

Wszystkie odniesienia do obiektów, które zostały przeniesione do nowej sterty, są sprawdzane przez garbage collectora, który wykonuje jedno z powyższych działań.

Po sprawdzeniu i zaktualizowaniu wszystkich odniesień w nowej stercie, proces odśmiecania pamięci kończy się.

Wskaźniki i działanie algorytmu

Algorytm nie wymaga stosu, a jedynie dwóch wskaźników: jeden do początku wolnego miejsca, a drugi do następnego obiektu wymagającego sprawdzenia, oba w nowej stercie. Z tego powodu często określany jest jako „kolektor o dwóch palcach” – potrzebuje jedynie „dwóch palców”, aby śledzić swój stan w nowej stercie. Przestrzeń między dwoma palcami reprezentuje pozostałą do zrobienia pracę.

Gdy odniesienie do obiektu w nowej stercie jest już znalezione (czyli ma przekierowujący wskaźnik w starej stercie), aktualizacja referencji może być przeprowadzona szybko i prosto poprzez zmianę wskaźnika według wskaźnika przekierowującego.

Podstawy algorytmu i jego rozwój

Cheney oparł swoją pracę na algorytmie odśmiecania pamięci semispace, który został opublikowany rok wcześniej przez R.R. Fenichela i J.C. Yochelsona.

Równoważność do trójkolorowej abstrakcji

Pierwszym elementem szarego zbioru jest sam stos. Obiekty referencjonowane na stosie są kopiowane do nowej sterty, która zawiera elementy zbiorów czarnych i szarych.

Algorytm przenosi obiekty białe (odpowiadające obiektom w starej stercie bez przekierowujących wskaźników) do szarego zbioru, kopiując je do nowej sterty. Obiekty znajdujące się pomiędzy wskaźnikiem skanowania a wskaźnikiem wolnego miejsca są uznawane za szare i będą nadal skanowane. Obiekty poniżej wskaźnika skanowania należą do czarnego zbioru. Obiekty są przenoszone do czarnego zbioru poprzez przesuwanie wskaźnika skanowania nad nimi.

Kiedy wskaźnik skanowania osiąga pozycję wskaźnika wolnego miejsca, szary zbiór staje się pusty, co kończy działanie algorytmu.