Metody realizacji języków programowania/MRJP Wykład 9

From Studia Informatyczne

Autor: Marcin Kowalczyk (qrczak@mimuw.edu.pl)

Spis treści

Odśmiecanie z punktu widzenia programisty

Obiekty i referencje

Relacja między obiektami a zmiennymi w różnych językach programowania jest najczęściej dwojakiego rodzaju:

  1. Zmienna zawiera obiekt, jest z nim nierozerwalnie związana. Czas życia (istnienia) obiektu pokrywa się z czasem aktywności zakresu bądź obiektu, w którym zdefiniowana jest zmienna.
  2. Zmienna wskazuje na obiekt. Utworzenie obiektu i utworzenie zmiennej to osobne operacje. Wiele zmiennych może wskazywać na ten sam obiekt, a ta sama zmienna może w różnym czasie wskazywać na różne obiekty. Czas życia obiektów nie jest ściśle związany z czasem życia zmiennych, które na nie wskazują.

W tym samym języku mogą współistnieć oba paradygmaty, choć różne języki wspierają te paradygmaty w różnym stopniu.

Pierwszy z nich, nazwijmy go paradygmatem wartości, jest zwykle stosowany do małych obiektów o prostej strukturze, których typ jest dokładnie znany statycznie (w czasie kompilacji) i których skopiowanie (wykonywane przy okazji przypisania zmiennej, przekazania argumentu funkcji albo zwrócenia wyniku funkcji) jest dla kompilatora łatwe — zwykle sprowadzające się do skopiowania kilku bajtów. Ten model sprawdza się na przykład przy liczbach i niewielkich rekordach.

Zajmiemy się bliżej drugim paradygmatem, paradygmatem referencji. Wartościami zmiennych są tutaj referencje nazywane też wskaźnikami.

Gospodarka pamięcią

Skoro czas życia obiektu nie pokrywa się z czasem życia zmiennych wskazujących na ten obiekt, pojawia się pytanie, co wyznacza czas życia obiektu; w szczególności kiedy pamięć zajmowana przez obiekt zostanie zwolniona. Najczęściej spotykane są dwa rozwiązania:

Ręczna gospodarka pamięcią

Programista ma do dyspozycji operację zwalniającą wskazany obiekt, nazwaną np. delete albo free. Każdy obiekt z grupy obiektów niezwiązanych z konkretnymi zmiennymi należy zwolnić dokładnie raz, po zakończeniu jego użycia.

Jeśli taki obiekt nie zostanie zwolniony w ogóle, to będzie zajmował pamięć aż do zakończenia działania programu. Sytuacja, w której program ciągle tworzy obiekty, o których potem zapomina, nazywa się wyciekiem pamięci (memory leak) i najczęściej skutkuje niepotrzebnym zajęciem bardzo dużej ilości pamięci, spowolnieniem systemu i w końcu zabiciem aplikacji przez system operacyjny. Wyciek pamięci jest niegroźny tylko jeśli dotyczy z góry ograniczonej liczby obiektów.

Z drugiej strony zwolnienie obiektu zanim program skończył go używać (w tym wielokrotne zwolnienie) powoduje, że referencje, które wskazywały na ten obiekt, wskazują teraz na miejsce w pamięci, w którym może już być coś zupełnie innego. Są to tzw. wiszące referencje (dangling references). Operacje na tych referencjach mają chaotyczne skutki: od niewidocznych, przez awaryjne zakończenie programu przez system operacyjny, do przekłamania wyników i utraty danych użytkownika albo złośliwego zdalnego położenia usługi sieciowej (denial-of-service attack).

Odśmiecanie

Język programowania automatycznie zwalnia pamięć obiektów, do których program już nie ma szans się odwołać. Takie obiekty nazywają się śmieciami (garbage) albo martwymi obiektami (dead objects), w odróżnieniu od pozostałych, żywych obiektów (live objects).

Ponieważ w ogólności nie da się automatycznie stwierdzić, których obiektów program będzie w przyszłości używał, stosowane są różne przybliżenia tego warunku. Oczywiście każde przybliżenie może odbiegać od tego nieosiągalnego ideału tylko w jedną stronę: może nie wykryć, że jakiś obiekt już nie będzie potrzebny, ale nie może uznać żywego obiektu za martwy.

Standarowym przybliżeniem kryterium żywotności, do którego można odnosić różne algorytmy odśmiecania, jest uznanie za żywe najmniejszego zbioru obiektów, z których każdy spełnia co najmniej jeden z warunków:

  • Jest wskazywany przez zmienną globalną albo aktywną zmienną lokalną.
  • Jest wskazywany przez pole jakiegoś żywego obiektu.

Odśmiecenie obiektu zwykle nie jest obserwowalne przez program, skutkuje tylko zwolnieniem pamięci. Odśmiecanie stwarza iluzję, że pamięci jest nieograniczona ilość, pod warunkiem, że w każdej chwili liczba żywych obiektów jest ograniczona.

Pojawia się drobne pytanie, czy aktywność zmiennej lokalnej liczy się do zakończenia wykonywania się zakresu, w którym ta zmienna jest zdefiniowana, czy do ostatniej instrukcji, w której zmienna jest używana, czy też do zakończenia wykonywania funkcji, która zawiera jej zakres, albo jeszcze inaczej. Zazwyczaj to i tak nie ma znaczenia, skoro fakt odśmiecania danego obiektu jest nieobserwowalny. Jak się jednak niżej okaże, czasem jednak bywa obserwowalny, a poza tym wiedza o zachowaniu się odśmiecania jest potrzebna do szacowania zajętości pamięci przez program. Otóż w praktyce bywa różnie. Co prawda pierwsze kryterium wydaje się najbardziej naturalne, ale programista nie może zakładać, że realizacje odśmiecania będą się ściśle zgodnie z tym kryterium zachowywać, o ile dana implementacja języka nie daje bardziej szczegółowych gwarancji.

Konsekwencje odśmiecania

Starsze języki częściej stosowały ręczną gospodarkę pamięcią, np. Fortran, Pascal, C i C++. Większość nowych języków stosuje odśmiecanie. Ale nie tylko nowe; odśmiecanie zostało wymyślone w 1959 roku dla potrzeb Lispa.

Przy ręcznej gospodarce pamięcią paradygmat wartości jest istotnie łatwiejszy w użyciu dla programisty niż paradygmat referencji, bo zwalnia programistę z obowiązku ustalenia, kiedy należy zwolnić dany obiekt. Dlatego w C++ paradygmat wartości jest bardzo rozwinięty. Wartościami zawartymi w zmiennych mogą być nawet bardzo złożone obiekty ze wskazywanymi przez wskaźniki podobiektami. Programista określa sposób kopiowania obiektów danej klasy (konstruktor kopiujący, operator przypisania) i zwalniania (destruktor). Zautomatyzowane jest generowanie takich implementacji tych operacji, które sprowadzają się do wykonania analogicznej operacji pole po polu.

W C++ paradygmat wartości jest stosowany również dla obiektów ze zmieniających się stanem, których nie można kopiować. Powszechne jest przekazywanie funkcjom referencji na zmienne lokalne.

W nowoczesnym C++ odwołania do dynamicznie zaalokowanych obiektów coraz częściej odbywają się przez pomocnicze obiekty zajmujące się zarządzaniem czasem ich życia, tzw. sprytne wskaźniki (smart pointers). Automatyczne wykonanie destruktura w momencie zakończenia czasu życia zmiennej jest wykorzystywane do skojarzenia ze sobą akcji „zajmującej” i „zwalniającej” zasób, które są wykonywane odpowiednio przed i po jakimś fragmencie kodu, niezależnie od sposobu opuszczenia tego fragmentu (RAII — Resource Acquisition Is Initialization).

Z kolei odśmiecanie pozwala na swobodniejsze stosowanie paradygmatu referencji. Stosowanie referencji na niezmienialne obiekty (immutable objects) jest równoważne stosowaniu wartości zgodnie z paradygmatem wartości, o ile one nie mają niezależnie adresowalnej struktury wewnętrznej. Programiście jest wszystko jedno, czy operacja danego języka zapisywana przez coś podobnego do x := 5 w danym języku sprowadza się do skopiowania liczby 5, czy skopiowania referencji na któryś obiekt reprezentujący liczbę 5. Do pewnego stopnia to jest kwestia punktu widzenia, a nie semantyki języka: ta sama operacja może być opisywana tak albo tak. Dlatego odśmiecane języki często stosują paradygmat referencji jako podstawowy albo wręcz jedyny, a mimo to praca z liczbami wygląda w nich tak samo jak w językach stosujących przede wszystkim paradygmat wartości.

W odśmiecanych językach jest silniejsza tendencja do programowania w stylu funkcyjnym, przez tworzenie nowych obiektów i podmianę na nie referencji zamiast przez zmiany starych obiektów w miejscu. Również charakterystyczna dla programowania funkcyjnego możliwość tworzenia lokalnych funkcji i zwracania ich na zewnątrz (upward closures) w zasadzie wymaga odśmiecania, żeby te lokalne funkcje mogły używać lokalnych zmiennych funkcji, w której są zawarte, również po zakończeniu tej zewnętrznej funkcji.

Większość algorytmów odśmiecania nie zapewnia zwolnienia obiektu natychmiast po zniknięciu ostatniej żywej referencji do niego. Obiekt jest faktycznie zwalniany w jakimś późniejszym czasie, zależnym od intensywności alokacji innych obiektów przez program. Odśmiecanie służy przede wszystkim do automatyzacji zwalniania pamięci. Poleganie na wykonywaniu przez odśmiecacz innych czynności związanych z kończeniem życia obiektu niż zwolnienie pamięci jest ryzykowne. Jest jednak technicznie możliwe, o ile możemy sobie pozwolić na wykonanie tych czynności w późniejszym, bliżej nieokreślonym momencie.

Dlatego do określenia czynności do wykonania w momencie wejścia i wyjścia z zakresu odśmiecane języki oferują inne mechanizmy językowe niż RAII, np. unwind-protect i makra w stylu with-open-file w Lispie i using w C#.

Zatem różnice w stylu programowania między odśmiecanymi a nieodśmiecanymi językami nie sprowadzają się do jawnego stosowania bądź pomijania delete. Odśmiecanie wpływa na organizację obiektów, na projektowanie interfejsów, na stopień współdzielenia tudzież kopiowania obiektów przez różne fragmenty programu.

Implementacja odśmiecania

Zliczanie odwołań (reference counting)

Technika zliczania odwołań polega na powiązaniu z każdym obiektem licznika przechowującego aktualną liczbę referencji na ten obiekt. Wraz z utworzeniem nowej referencji, np. kiedy obiekt jest przekazywany jako argument funkcji, licznik jest zwiększany o 1. Usunięcie referencji na ten obiekt, np. przypisanie innej wartości zmiennej, która wcześniej wskazywała na ten obiekt, wymaga zmniejszenia licznika. Za każdym razem, kiedy zmniejszany licznik zejdzie do 0, odpowiedni obiekt jest zwalniany, zmniejszając przy tym liczniki obiektów, do których się odwoływał.

Zauważmy, że ten mechanizm powoduje osłabienie kryterium żywotności obiektów względem standardowego: obiekt jest uznawany za żywy, kiedy jest wskazywany przez pole jakiegokolwiek obiektu, niekoniecznie żywego. Innymi słowy, zbiór obiektów, które wskazują na siebie nawzajem, a przestaną być osiągalne z reszty programu, powoduje wyciek pamięci. Dlatego część ludzi w ogóle nie uznaje zliczania odwołań za technikę odśmiecania: algorytm nie spełnia podstawowego założenia ostatecznego zwalniania wszystkich nieosiągalnych obiektów.

Do wad trzeba zaliczyć wysoki koszt manipulacji licznikami odwołań, często większy niż narzut innych algorytmów odśmiecania. Co prawda pojedyncza operacja na liczniku jest tania, ale takich operacji jest bardzo dużo, a zwolnienie złożonej struktury danych wymaga obejścia całego grafu obiektów.

Mimo to, zliczanie odwołań jest używane w wielu projektach. Wynika to prawdopodobnie między innymi z tego, że jest łatwe do zintegrowania z językiem programowania nie wspierającym odśmiecania, zwłaszcza takim jak C++, gdzie manipulacje licznikiem odwołań przy okazji przekazywania referencji mogą być automatyzowane za pomocą konstruktorów kopiujących, operatorów przypisania i destruktorów.

Zliczanie odwołań umożliwia zwolnienie obiektu natychmiast, kiedy tylko zniknie ostatnie odwołanie do niego. Dzięki temu względnie bezpiecznie jest uwzględnić w zwalnianiu obiektu również inne czynności kończące jego życie, nie tylko zwolnienie pamięci. Co więcej, momenty i długości przerw w wykonywaniu programu w celu zwolnienia obiektów są przewidywalne, choć w przypadku dużej struktury przerwa może być długa.

Możliwe są wariacje podstawowego mechanizmu zliczania odwołań, np. połączenie go z okresowo wykonywanymi innymi algorytmami odśmiecania w celu usunięcia cyklicznych śmieci (tak robi podstawowa implementacja Pythona).

Mark & sweep

Algorytm mark & sweep wymaga zarezerwowania jednego dodatkowego bitu w każdym obiekcie. Przynajmniej koncepcyjnie, bo ta informacja nie musi mieć fizycznej formy bitu, wystarczy jakaś realizacja podziału obiektów na dwa podzbiory z możliwością przenoszenia obiektu między zbiorami.

Okresowo, np. kiedy od ostatniego odśmiecania zaalokowano już odpowiednio dużo pamięci, wykonywane jest odśmiecanie, które składa się z dwóch faz. Odśmiecanie wykorzystuje tymczasowy zbiór bieżących obiektów G.

Faza I: mark.

  1. Na początku wszystkie obiekty mają wspomniany bit ustawiony na „nieodwiedzony”.
  2. Do zbioru G na początku należą obiekty wskazywane przez „korzenie” odśmiecania (roots), czyli przez zmienne lokalne każdego wątku i zmienne globalne. Ustawiamy bity tych obiektów na „odwiedzony”.
  3. Dopóki zbiór G jest niepusty:
    1. Wyjmujemy jakiś obiekt z G
    2. Dodajemy do G wszystkie nieodwiedzone obiekty wskazywane przez ten obiekt, ustawiając ich bity na „odwiedzony”.

Faza II: sweep.

  1. Zwalniamy wszystkie nieodwiedzone obiekty, a pozostałym ustawiamy bit z powrotem na „nieodwiedzony”. Zamiast fizycznego odwrócenia bitu w każdym żywym obiekcie można zamienić znaczenia bitu rolami.

Możliwe są różne realizacje zbioru G i w związku z tym różne strategie wyboru obiektu z niego:

  • Jako stos adresów obiektów zrealizowany w formie jawnej struktury danych, np. tablicy. W efekcie graf obiektów jest przeglądany w głąb.
  • Jako stos rekurencyjnych wywołań funkcji „mark”. To jest ryzykowne podejście, kiedy głębokość grafu obiektów może być większa niż maksymalna głębokość zagnieżdżonych wywołań funkcji.
  • Jako kolejka. W efekcie graf obiektów jest przeglądany wszerz.

Wadą podstawowej formy tego algorytmu jest konieczność okresowego wstrzymania programu na czas przejrzenia całej pamięci i odwiedzenia każdego obiektu.

Mark & compact

Zamiast zwalniać pojedyncze obiekty jak w algorytmie mark & sweep, pozostawiając żywe obiekty między zwolnionymi miejscami, można przenieść żywe obiekty do spójnego obszaru pamięci, „zsuwając” je na miejsca po zwolnionych obiektach. Dzięki temu alokacja nowych obiektów pobiera pamięć ze spójnego obszaru wolnej pamięci, co jest bardzo szybkie. Poza tym zgrupowanie używanych obiektów w spójnym kawałku pamięci ułatwia procesorowi efektywne cache’owanie pamięci.

Oczywiście zmiana fizycznego położenia obiektu wymaga uaktualnienia reprezentacji wszystkich wskaźników na niego, a wskaźniki są ze swojej natury „jednokierunkowe”: nie można szybko zlokalizować wszystkich wskaźników na dany obiekt. Faza „sweep” składa się więc z kilku etapów, np. najpierw ustalamy nowy adres każdego obiektu, potem uaktualniamy wskaźniki, wreszcie przesuwamy obiekty na ich docelowe miejsca.

Odśmiecanie kopiujące (copying GC)

Kopiować obiekty pod nowe adresy można od razu w trakcie przechodzenia grafu obiektów. Po przeniesieniu obiektu pod nowy adres pod starym adresem zostawiamy odsyłacz do nowego adresu. Zwykły obiekt jest zawsze odróżnialny od takiego pozostawionego odsyłacza.

Odśmiecanie kopiujące używa tymczasowo zbioru G bieżących obiektów i odbywa się następująco:

  1. Alokujemy nowy obszar pamięci, do którego zostaną przeniesione żywe obiekty. Na początku zbiór G jest pusty.
  2. Odwiedzamy korzenie odśmiecania. Odwiedzenie wskaźnika polega na sprawdzeniu, czy pod wskazywanym przez niego adresem znajduje się odsyłacz. Jeśli tak, to tylko uaktualniamy wskaźnik na adres podany w odsyłaczu. Jeśli nie, to przenosimy wskazywany obiekt pod pierwszy wolny adres w nowym obszarze pamięci, pozostawiamy odsyłacz, uaktualniamy wskaźnik i dodajemy przeniesiony obiekt do zbioru G.
  3. Dopóki zbiór G jest niepusty:
    1. Wyjmujemy jakiś obiekt z G.
    2. Odwiedzamy wskaźniki zawarte w tym obiekcie.
  4. Zwalniamy stary obszar pamięci, który zawiera teraz same śmieci. Nowy obszar pamięci staje się bieżącą stertą.

Możliwe są różne szczegółowe warianty. Przetwarzanie zbioru G może się przeplatać z odwiedzaniem poszczególnych korzeni. Zbiór G może zawierać adresy poszczególnych wskaźników zawartych w obiektach, a nie adresy samych obiektów, dzięki czemu znalezienie pól obiektu dla potrzeb skopiowania obiektu oraz dla potrzeb zapamiętania tych pól do późniejszego odwiedzenia może się odbyć równocześnie (sposób wykonania obu czynności zależy od typu obiektu).

Na różne sposoby można zrealizować znajdowanie pól mogących zawierać wskaźniki (pola, które na pewno nie zawierają wskaźników, trzeba tylko skopiować wraz z całą zawartością obiektu, ale oczywiście nie trzeba ich odwiedzać). Na przykład każdy obiekt może zaczynać się od nagłówka opisującego liczbę i położenie pól. Albo może się zaczynać od wskaźnika na statycznie zaalokowany deskryptor zawierający te informacje. Zamiast interpretowanego przez odśmiecacz opisu pól, nagłówek może też zawierać adres kodu, który wykonuje zależne od typu obiektu czynności kopiowania i odwiedzania pól.

Reprezentacja zbioru G i strategia wyboru przetwarzania obiektów czy wskaźników z G wpływa na kolejność ułożenia obiektów w pamięci. Kolejność stosowa i tym samym przeglądanie grafu obiektów w głąb powoduje ułożenie wskazujących na siebie obiektów blisko siebie, co ułatwia pracę sprzętowym mechanizmom cache’ującym.

Istnieje ciekawy sposób reprezentacji zbioru G, jeśli godzimy się na przeglądanie obiektów wszerz. Mianowicie obiekty te zajmują zawsze spójny obszar pamięci w nowej stercie. Wystarczy więc pamiętać dwa wskaźniki: na pierwszy nieprzetworzony jeszcze obiekt w nowej stercie i na początek wolnego miejsca. W miarę przetwarzania kolejnych obiektów pierwszy wskaźnik przesuwa się naprzód, a odnajdowanie wskazywanych przez nie nowych obiektów do przejrzenia powoduje przesuwanie się drugiego wskaźnika. Kiedy oba wskaźniki się spotkają, odśmiecanie można zakończyć. Jest to algorytm Cheneya.

Zauważmy, że odśmiecacz kopiujący nie odwiedza śmieci indywidualnie. Odwiedzane i kopiowane są tylko żywe obiekty, a następnie cały obszar sterty zawierający śmieci jest zwalniany jednym ruchem. Taka charakterystyka pracy dobrze się sprawdza, kiedy większość obiektów ma krótki czas życia i umiera przed następnym odśmiecaniem.

Koszt odśmiecania kopiującego nie ma oczywistego porównania z odśmiecaniem w stylu mark & sweep albo ze zliczaniem odwołań. Na niekorzyść przemawia fizycznie kopiowanie obiektów z miejsca w miejsce, ale z drugiej strony unikamy zwalniania indywidualnych obiektów. Koszt jest uzależniony od średniej ilości żywych obiektów i od czasu ich życia, a nie od tempa alokacji.

Odśmiecanie pokoleniowe (generational GC)

Odśmiecanie kopiujące opiera się na okresowym przechodzeniu całego grafu obiektów. Można zredukować częstość odwiedzania każdego obiektu wykorzystując statystyczną obserwację: wiele obiektów jest tworzonych tylko na chwilę i żyje krótko; jeśli natomiast dany obiekt przeżył już wiele cykli odśmiecania, to jest duża szansa, że przeżyje i następny. Zatem opłaca się koncentrować na odśmiecaniu młodych obiektów, bo od nich prawdopodobnie łatwo odzyskamy dużo pamięci. Stare obiekty odkładamy na bok i odwiedzamy je rzadziej.

Odśmiecanie pokoleniowe polega na segregacji obiektów względem ich wieku, najczęściej mierzonego liczbą przeżytych cykli odśmiecania, i odśmiecaniu młodszych obiektów częściej. Dany cykl odśmiecania dotyczy obiektów wybranego pokolenia oraz wszystkich młodszych pokoleń. Obiekty, które przeżyły, są przenoszone do starszych pokoleń od razu albo po przekroczeniu pewnej wartości licznika wieku obiektu. Wybór pokolenia do odśmiecenia jest jakąś funkcją wielkości poszczególnych pokoleń i ew. dotychczasowej statystycznej charakterystyki czasu życia obiektów danego programu.

W najprostszej wersji pokolenia wystarczą dwa: młode obiekty, które nie przeżyły jeszcze żadnego odśmiecania, i pozostałe, stare obiekty. Są wtedy dwa rodzaje cyklu odśmiecania: mniejsze odśmiecanie (minor GC), polegające na przejrzeniu wyłącznie młodych obiektów, oraz większe odśmiecanie (major GC), które dotyczy wszystkich obiektów.

Z punktu widzenia odśmiecania danego pokolenia wskaźniki na należące do niego obiekty, ale zawarte w starszych obiektach, są korzeniami odśmiecania, od których trzeba zacząć przechodzenie grafu obiektów. Co więcej, jeśli skopiowanie żywego obiektu łączy się ze zmianą jego fizycznego adresu, to odśmiecacz musi znaleźć wszystkie wskaźniki na dany obiekt, żeby uaktualnić ich reprezentację. Żeby podział sterty na pokolenia się opłacał, bardzo przydatna jest możliwość znalezienia takich wskaźników taniej niż przez przejrzenie wszystkich starszych obiektów.

Wskaźnik ze starszego obiektu na młodszy może powstać tylko przez przypisanie pola wcześniej istniejącego obiektu. Odśmiecacz musi przechwycić każde takie przypisanie, które skutkuje albo może skutkować powstaniem takiego wskaźnika, i zarejestrować położenie przypisanego wskaźnika albo adres obiektu, do którego należy to pole, albo adres strony pamięci, w której zawarte jest to pole. Podczas odśmiecania odpowiednich pokoleń zarejestrowane w ten sposób wskaźniki są dodatkowymi korzeniami. Takie przechwycenie zapisu nazywa się barierą zapisu (write barrier). Może ona być zrealizowana czysto programowo (przez wyemitowanie odpowiednich instrukcji wraz z tymi instrukcjami przypisania, które mogą tworzyć wskaźniki ze starszego pokolenia na młodsze) albo z wykorzystaniem udostępnionych przez system operacyjny sprzętowych mechanizmów wygenerowania przerwania, kiedy odpowiednio oznaczona strona pamięci jest zapisywana.

Nie każdy zapis do pola obiektu musi podlegać barierze; jeśli statycznie wiadomo, że obiekt zawierający dane pole nie jest starszy niż obiekt wskazywany przez to pole po przypisaniu, to zapis może sprowadzić się do prostego przypisania adresu. Taka statyczna gwarancja występuje na przykład w trakcie inicjalizacji dopiero co stworzonego obiektu wartościami istniejącymi na pewno przed jego utworzeniem.

Zmienne lokalne (czyli zwykle rejestry procesora i zawartość stosu) i zmienne globalne mogą być przeglądane w całości przy każdym odśmiecaniu albo mogą podlegać barierze zapisu razem z polami obiektów. Programowa bariera zapisu w przypadku zmiennych lokalnych znajdujących się na stosie byłaby dość kosztowna, bo zapis takich zmiennych jest częsty i trudno go wyeliminować w oparciu o statyczną wiedzę. Można jednak uniknąć przeglądania całego stosu przy każdym odśmiecaniu, jeśli zmiany zmiennych lokalnych dotyczą zawsze tylko najwyższej ramki stosu i jeśli można wykryć, jak głęboko od ostatniego odśmiecania danego pokolenia stos został najdalej zwinięty — wtedy wystarczy przejrzeć ramki stosu między tą najdalszą ramką a bieżącym wierzchołkiem.

Odśmiecanie pokoleniowe ma zastosowanie wobec różnych bazowych algorytmów odśmiecania. Stosuje się nawet połączenie różnych algorytmów odśmiecania w zależności od pokolenia, np. odśmiecanie kopiujące w młodszych pokoleniach i mark & sweep z ewentualnym okresowym kompaktowaniem w najstarszym pokoleniu (w którym żywe obiekty już pozostają).

Stopień prawdziwości wspomnianej na początku statystycznej obserwacji dotyczącej zróżnicowania wieku obiektów zależy od stylu programowania i od języka. Odśmiecanie pokoleniowe jest szczególnie opłacalne przy programowaniu funkcyjnym, które po pierwsze prowadzi do intensywnej alokacji nowych obiektów zamiast stopniowych zmian obiektów istniejących wcześniej, a po drugie ogranicza powstawanie wskaźników ze starszych obiektów do młodszych, bo takie wskaźniki muszą być skutkiem imperatywnego przypisania. Ale również nowoczesne implementacje języków obiektowych często stosują odśmiecanie pokoleniowe.

Odśmiecanie przyrostowe (incremental GC)

Konieczność zatrzymania programu, żeby odśmiecić całą stertę, jest wadą wielu algorytmów odśmiecania. Moment takiej pauzy jest trudny do przewidzenia; może wypaść przy okazji dowolnej alokacji pamięci i tym samym może przeszkodzić programowi, kiedy reakcja na jakieś zdarzenie jest akurat pilna. Można próbować zmniejszać dokuczliwość pauz przez automatyczne odśmiecanie, kiedy moment wydaje się bardziej odpowiedni niż inne, np. kiedy program właśnie czeka na zdarzenie zewnętrzne, więc procesor i tak nie ma nic do roboty. Odśmiecanie pokoleniowe powoduje, że większość pauz jest krótka; co jakiś czas jednak trzeba odśmiecić całość. Bardziej atrakcyjne jest wyeliminowanie w ogóle konieczności odśmiecania całej sterty naraz.

Odśmiecanie przyrostowe polega na przeplataniu odśmiecania z normalnym wykonaniem programu, dzięki czemu pauzy na odśmiecanie są krótsze, za to jest ich więcej.

Z punktu widzenia odśmiecacza, który stara się obejść graf obiektów i wnioskować o ich osiągalności z korzeni, główny program mu przeszkadza zmieniając co chwilę połączenia między obiektami i sam zbiór korzeni. Odśmiecacz musi mimo tego przeszkadzania znaleźć jakieś górne przybliżenie wciąż zmieniającego się zbioru osiągalnych obiektów.

W ustaleniu niezmienników, które muszą być w tym celu zachowane, pomaga koncepcyjne przyporządkowanie każdemu obiektowi „koloru”. Obiekty, które zostały uznane za żywe i których wszystkie pola zostały już odwiedzone, nazwijmy „czarnymi”. Żywe obiekty, których nie wszystkie pola zostały odwiedzone, nazwijmy „szarymi”. Pozostałe, nieodwiedzone obiekty są „białe”.

Odśmiecacz mark & sweep zaczyna cykl odśmiecania od sytuacji, w której wszystkie obiekty są białe, tylko korzenie są szare. Praca polega na przemalowywaniu białych obiektów wskazywanych przez szare obiekty na szaro i na przemalowywaniu szarych obiektów, których wszystkie pola zostały już odwiedzone, na czarno. Innymi słowy, szare obiekty są cienką granicą między czarnymi a białymi obiektami, która przesuwa się naprzód w miarę kolorowania kolejnych białych obiektów na czarno. Kiedy nie pozostał już żaden szary obiekt, można zwolnić obiekty, które po przejściu tej fali pozostały białe, a pozostałe przemalować z powrotem na biało przed następnym cyklem.

Przy odśmiecaniu kopiującym stara kopia sterty zawiera białe obiekty, a nowa — szare i czarne. Szare obiekty to te z nowej kopii sterty, których pola należy jeszcze obejrzeć (wspomniany zbiór G).

Podstawowy niezmiennik brzmi: żaden czarny obiekt nie wskazuje bezpośrednio na biały obiekt. Jeśli odśmiecanie przeplata się z głównym programem, to program musi być wyposażony w bariery zapisu, które zapewniają zachowanie tego niezmiennika przez odpowiednie przemalowanie tych obiektów, które pogwałciłyby niezmiennik. Oprócz tego główny program musi dbać o to, żeby odśmiecacz mógł w każdej chwili znaleźć wszystkie szare obiekty. Istnieje wiele strategii kolorowania nowo alokowanych obiektów i przywracania niezmiennika po przypisaniu.

Trzeba jeszcze zapewnić, żeby odśmiecanie odbywało się w odpowiednim tempie. Z jednej strony odśmiecacz musi nadążyć ze znajdowaniem i zwalnianiem śmieci, żeby ograniczona w każdej chwili ilość obiektów faktycznie używanych przez program implikowała ograniczone zużycie pamięci. Z drugiej strony zbyt intensywne, wielokrotne przeglądanie obiektów, których sytuacja nie miała szans ulegać tak szybkim zmianom, marnuje czas procesora.

Odśmiecanie przyrostowe co prawda pozwala zmniejszyć długość pauz wprowadzanych przez odśmiecacz, ale skomplikowanie algorytmu z reguły skutkuje zwiększeniem całkowitego czasu przeznaczonego na odśmiecanie.

Odśmiecanie dokładne czy konserwatywne (precise or conservative GC)

Znajdowanie wskaźników

Typowe algorytmy odśmiecania wykorzystują to, że odśmiecacz ma możliwość:

  • znalezienia zmiennych lokalnych i globalnych, które są wskaźnikami,
  • dla każdego obiektu: znalezienia wszystkich jego pól, które są wskaźnikami.

Uzyskanie tych możliwości w zasadzie wymaga zaprojektowania takiej reprezentacji obiektów, która na podstawie samego adresu obiektu pozwala wywnioskować, jaki jest rozkład pól tego obiektu. Zazwyczaj obiekt zaczyna się od nagłówka, który zawiera te informacje.

Teoretycznie można tego uniknąć i dać odśmiecaczowi możliwość poznania typu obiektu na podstawie innych danych niż reprezentacja jego zawartości. Na przykład na podstawie osobnych struktur opisujących typy pól obiektów danego typu, po których to strukturach odśmiecacz chodzi równolegle z chodzeniem po konkretnych obiektach. Praktyka jednak pokazuje, że prościej jest, kiedy każdy obiekt jest samoopisywalny w stopniu potrzebnym odśmiecaczowi.

Większym problemem niż znalezienie pól każdego obiektu bywa umożliwienie odśmiecaczowi odnalezienia zmiennych lokalnych. Można odkładać na stosie dodatkową informację o reprezentacji danej ramki stosu. Można też ją wnioskować na podstawie adresu powrotu, który tak czy siak znajduje się na stosie, i przygotowanych przez kompilator map przyporządkowujących możliwym adresom powrotu informację o tym, z której funkcji odbywał się skok, czyli jaki jest układ jej zmiennych lokalnych. Trzeba wybrać jakiś kompromis między szybkością wykonywania właściwego programu a szybkością odśmiecania.

Panowanie nad reprezentacją ramek stosu jest kłopotliwe, kiedy kompilator generuje kod w C albo kiedy program używa bibliotek zaimplementowanych C. Generowanie kodu w C jest dość popularnym rozwiązaniem, bo taki kod jest niezależny od procesora. Jednak przenośny kod w C współpracujący z odśmiecaczem zwykle wymaga tworzenia dodatkowych struktur pozwalających odśmiecaczowi znaleźć wskaźniki na stosie. Trzeba też uważać, żeby wywołania „obcych” funkcji, które pozostawiają na stosie struktury o reprezentacji będącej poza naszą kontrolą, nie przeszkodziły odśmiecaczowi w rozpoznaniu ramek stosu funkcji należących do własnego języka.

Niektóre kompilatory w ogóle rezygnują z używania systemowego stosu wywołań i emulują stos w osobnej tablicy albo na osobnej liście ramek. Co prawda operacje na takiej jawnej strukturze danych nie mają szans korzystać ze zoptymalizowanych instrukcji maszynowych przeznaczonych do operacji na systemowym stosie, ale wśród problemów, które dzięki temu można łatwo rozwiązać, jest pełna kontrola nad reprezentacją ramek stosu i tym samym łatwość umożliwienia odśmiecaczowi skanowania zmiennych lokalnych.

Często stosowane (zwłaszcza w dynamicznie typowanych językach, ale nie tylko) jest założenie, że każda wartość mieści się w słowie maszynowym. Małe wartości niebędące wskaźnikami są reprezentowane w sposób dający się łatwo odróżnić od wskaźników. Na przykład zakładamy, że wskaźniki na obiekty są podzielne przez wielkość słowa maszynowego, czyli 2 albo 3 najmłodsze bity mają zerowe. Pewne małe wartości, takie jak liczby całkowite, są reprezentowane przez odpowiednie reprezentacje przesunięte w lewo i z ustawionym najmłodszym bitem albo kilkoma bitami informującymi o typie. Natomiast większe wartości są reprezentowane przez wskaźniki na obiekty. Dzięki temu opis reprezentacji obiektu i opis ramki stosu nie muszą uwzględniać tego, które pola są wskaźnikami, a które nie, a wystarczy sama liczba pól zaczynających się w danym miejscu. Osobnego potraktowania wymaga tylko kilka specjalnych typów, których obiekty nie składają się z ciągu pól wielkości słowa maszynowego, np. stringi i liczby zmiennoprzecinkowe.

Odśmiecanie konserwatywne

Odśmiecanie można realizować też w trudniejszych warunkach: kiedy na stosie nie ma żadnych wskazówek odnośnie tego, które miejsca stosu zawierają wskaźniki na odśmiecane obiekty, i kiedy wskaźniki na obiekty mogą być umieszczane w obiektach o reprezentacji będącej poza naszą kontrolą. Odśmiecacz musi tylko być w stanie znaleźć wszystkie miejsca, w których mogą być wskaźniki, ale nie musi wiedzieć, które z tych wartości rzeczywiście są wskaźnikami, a które są np. fragmentami napisów o takim samym układzie bajtów jak wskaźnik na jakiś obiekt.

Zrealizowanie odśmiecania w takich warunkach ułatwia integrację z ręcznie pisanym kodem w C, który nie musi dzięki temu pozostawiać informacji dla odśmiecacza o tym, które zmienne czy pola obiektów zawierają wskaźniki; wystarczy, żeby umieścił wskaźnik w dowolnej zmiennej języka C. Sam odśmiecacz ma za to trudniejsze zadanie, bo w miejscach, w których szuka wskaźników, mogą być też inne układy bajtów, które gdyby interpretować je jako adres w pamięci, wskazywałyby poza pamięć programu, gdzieś w połowie obiektu, w kod programu itp.

Odśmiecacz, który nie może mieć pewności, które wartości są wskaźnikami, nazywa się odśmiecaczem konserwatywnym (conservative GC), w odróżnieniu od odśmiecacza dokładnego (precise GC).

Zdarza się, że konserwatywne jest tylko przeglądanie stosu, natomiast reprezentacja obiektów jest samoopisywalna i tutaj odśmiecacz chodzi tylko po faktycznych wskaźnikach. Może też się przydać odśmiecacz, który ma informację o rozkładzie pól niektórych obiektów, a inne przegląda konserwatywnie.

Jeśli jakaś wartość wygląda jak wskaźnik na dany obiekt, to odśmiecacz konserwatywny musi utrzymać ten obiekt przy życiu, nawet jeśli ta wartość tylko przypadkiem ma taki układ bajtów. Może to skutkować czymś w rodzaju wycieków pamięci (choć obiekt może zostać w końcu zwolniony, jeśli ten układ bajtów się kiedyś zmieni albo jeśli sam zostanie zwolniony). Takie wycieki zwykle są niegroźne, bo jest mało prawdopodobne, że dla znacznej liczby obiektów znajdą się takie fałszywe wskaźniki utrzymujące te obiekty przy życiu dłużej niż trzeba. Zwłaszcza jeśli na danej architekturze typowy zakres adresów pamięci sterty nie obejmuje małych liczb całkowitych.

Jednak program, który trzyma w pamięci dużą ilość danych zawierających losowo wyglądające układy bajtów, może utworzyć tak dużą liczbę fałszywych wskaźników, że uniemożliwi ona konserwatywnemu odśmiecaczowi zwolnienie wystarczającej ilości pamięci. Zwłaszcza na 32-bitowej architekturze, gdzie przestrzeń adresowa jest względnie mała.

Oczywiście odśmiecanie konserwatywe nie może zmieniać adresów obiektów w pamięci, tzn. wykluczone jest odśmiecanie kopiujące. Nie można sobie pozwolić na samoczynną zmianę danych, które nie są wskaźnikami, a tylko miały pecha wyglądać jak wskaźnik.

Poza tym algorytm odśmiecania konserwatywnego nie różni się istotnie od algorytmów zwykłego odśmiecania, np. może to być mark & sweep zwykły bądź pokoleniowy. Trzeba tylko przy oglądaniu każdego wskaźnika upewnić się najpierw, że wskazuje on na poprawny obiekt, np. na podstawie map pamięci, które opisują, w których miejscach znajdują się początki obiektów. Oraz trzeba znaleźć sposób na przeskanowanie całego stosu i zmiennych globalnych, co wymaga konstrukcji zależnych od procesora i systemu operacyjnego.

W większości realizacji języków można zakładać, że każdy wskaźnik wskazuje na początek obiektu, czyli znaleziony gdzieś adres wypadający w połowie istniejącego obiektu musi być fałszywym wskaźnikiem. W ogólności nie zawsze tak jest, np. naturalna implementacja wielodziedziczenia w C++ nie ma tej własności. Można też zwykle zakładać, że każdy obiekt zaczyna się od adresu podzielnego przez wielkość słowa maszynowego i że każdy prawdziwy wskaźnik sam znajduje się pod tak wyrównanym adresem. Jeśli te założenia nie mogą być spełnione, to fałszywe wskaźniki stają się bardziej prawdopodobne.

Dobrej jakości konserwatywny odśmiecacz do języka C został zaimplementowany przez Hansa J. Boehma i jest dostępny na licencji BSD-like.

Finalizacja i słabe referencje

Finalizacja

Pewne obiekty reprezentują zewnętrzne zasoby, istniejące poza programem, np. otwarte pliki albo aktywne połączenia z bazą danych. Interfejs systemu operacyjnego bądź biblioteki C pozwalający używać takiego zasobu z reguły wymaga zamknięcia zasobu po użyciu, żeby zwolnić pamięć zarządzaną poza programem, zamknąć połączenia sieciowe, zakończyć pomocnicze wątki itp.

W języku programowania z odśmiecaniem stosowane są dwa podstawowe style zwalniania zewnętrznych zasobów:

  1. Jawnie w określonym miejscu w programie. Przy czym po wykonaniu czynności zamknięcia obiekt reprezentujący zasób jest w ogólności żywy, bo trudno zabronić programowi przechowania referencji do tego obiektu i próby użycia go później, ale skojarzonego z obiektem zasobu już nie ma, więc większość operacji na tym obiekcie skutkuje od tego momentu błędem wykonania.
  2. Kiedy obiekt danego rodzaju jest odśmiecany, wykonywane są dodatkowe czynności sprzątające.

Drugi sposób jest wygodniejszy dla programisty, ale ryzykowny, kiedy zasób jest „drogi”. Program może zająć wiele egzemplarzy takiego zasobu w sytuacji, kiedy faktycznie używa małej ich liczby naraz, a pozostałe egzemplarze nie zostały jeszcze znalezione przez odśmiecacz. Poleganie na odśmiecaniu jest jeszcze gorszym pomysłem, kiedy użycie danego zasobu przez jeden proces uniemożliwia równoczesne wykorzystywanie go przez inne procesy albo powtórnie przez ten sam proces, np. kiedy plik jest otwarty do zapisu na wyłączność. Mimo wszystko są sytuacje, kiedy możemy sobie pozwolić na faktyczne zwolnienie zasobu z opóźnieniem względem momentu, w którym program przestał go rzeczywiście używać.

Do rejestrowania czynności do wykonania przy odśmiecaniu obiektu potrzebny jest odpowiedni mechanizm językowy, którego implementacja jest zintegrowana z odśmiecaczem. Dodatkowe sprzątanie po odśmiecanych obiektach nazywa się finalizacją (finalization). Może to wyglądać w taki sposób, że programista ma do dyspozycji operację kojarzącą z danym obiektem czynność sprzątającą; czynność ta, wyrażona bezargumentową funkcją, zostanie automatycznie wykonana kiedyś po odśmieceniu tego obiektu.

Często sensowne jest umożliwienie użytkownikowi danej biblioteki jawnego zwalniania zasobów wymagających nietrywialnej finalizacji, ale w taki sposób, że jeśli obiekt skojarzony z zasobem zginie bez wcześniejszego jawnego zwolnienia, to zostanie sfinalizowany automatycznie. Zatem niech owo skojarzenie czynności sprzątającej daje w wyniku obiekt (finalizator, ang. finalizer), za pomocą którego można wykonać finalizację danego obiektu jawnie. Jeśli jawna finalizacja nie jest przewidziana, to obiekt finalizatora wolno zgubić; nie ma to wpływu na automatyczną finalizację.

Po jawnej bądź automatycznej finalizacji finalizator staje się nieaktywny i automatycznie już nie zostanie wykonany. Jawne wykonanie nieaktywnego finalizatora jest pustą czynnością. Żądanie jawnego wykonania finalizatora, który właśnie jest wykonywany przez inny wątek, powinno zaczekać, aż finalizacja tego obiektu się zakończy.

Odśmiecanie, a tym samym finalizacja, mogą się odbyć w dowolnym momencie programu. Jeśli finalizator używa obiektów współdzielonych z resztą programu (np. usuwa element słownika, do którego reszta programu ma dostęp), to trzeba zapewnić wzajemne wykluczenie równoczesności operacji na takim obiekcie, o ile one same z siebie nie są atomowe. Dlatego implementacja finalizatora powinna używać odpowiednich mechanizmów wykluczania wątków przy operacjach na obiektach współdzielonych z resztą programu, np. muteksów, a finalizator powinien być wykonywany przez odśmiecacz w osobnym wątku. Jeden wątek może służyć do finalizacji wielu obiektów po kolei, ale nie powinien być tutaj użyty żaden wątek stworzony przez program jawnie, żeby wątki finalizujące i wątki głównego programu mogły się wzajemnie synchronizować muteksami.

Do poprawnego działania funkcji sprzątającej, jak każdej funkcji, wymagane jest, żeby obiekty, których ona używa, były utrzymywane przy życiu, dopóki funkcja ma szansę zostać użyta. Oznacza to, że finalizator nie powinien odwoływać się do samego obiektu, którego „pilnuje”, bo inaczej ten obiekt będzie żył wiecznie. Finalizator powinien używać tylko tych składników tego obiektu, które są potrzebne do finalizacji, i żaden z tych składników nie powinien wskazywać z powrotem na pilnowany obiekt.

Próba pozwolenia na to, żeby obiekty, do których odwołują się finalizatory, były finalizowalne, miałaby przykrą konsekwencję: finalizator nie miałby pewności, czy obiekty, których on używa, nie zostały już wcześniej sfinalizowane. Wtedy fakt istnienia finalizatora byłby widocznym aspektem implementacji obiektu, uniemożliwiającym bezpieczne używanie takich obiektów przez inne finalizatory.

Opisana tutaj semantyka finalizacji nie pozostawia możliwości wskrzeszenia obiektu (resurrection), czyli utworzenia silnej referencji na obiekt w odpowiedzi na jego finalizację, co wstrzymałoby zwolnienie jego pamięci. Semantyka, która dopuszcza wskrzeszanie obiektów (np. kiedy finalizator jest metodą finalizowanego obiektu), jest kłopotliwa i w zależności od innych decyzji nie zabezpiecza przed użyciem już sfinalizowanego obiektu albo nie umożliwia zwolnienia cyklicznych struktur obiektów z finalizatorami.

Słabe referencje (weak references)

Załóżmy, że chcemy dodać pole do jakiejś klasy bez ingerowania w definicję tej klasy (klasa przychodzi z gotowej biblioteki, której nie możemy zmieniać). W typowych językach programowania nie da się zrobić tego wprost, ale można uzyskać taką samą funkcjonalność przez stworzenie zewnętrznego słownika indeksowanego obiektami tej klasy, przyporządkowującego im wartość dodanego pola.

To rozwiązanie ma przykrą wadę: obiekty z dodanymi polami, które są już niepotrzebne, wciąż zajmują miejsce w słowniku, a słownik uniemożliwia ich odśmiecenie. Program zaprojektowany w odśmiecanym języku zwykle jawnie nie określa, w którym miejscu dany obiekt przestaje być używany; należy usunąć obiekt ze słownika wtedy, kiedy on przestanie być używany przez pozostałą część programu. Przydałby się słownik, który nie utrzymuje swoich kluczy przy życiu, a kiedy taki klucz umiera, jest automatycznie usuwany ze słownika.

Taki słownik może być dostarczony jako gotowa konstrukcja przez implementację języka programowania, ale można go też zbudować z bardziej elementarnego pojęcia: słabej referencji, nazywanej też słabym wskaźnikiem, w odróżnieniu od silnej referencji, czyli zwyczajnej.

Najprostszy wariant słabej referencji to specjalny obiekt, który odwołuje się do innego obiektu w taki sposób, że nie utrzymuje go przy życiu, tzn. nie zapobiega jego odśmieceniu. Słaba referencja ma zdefiniowaną operację dereferencji, która zwraca wskazywany obiekt, o ile on jeszcze żyje, bądź informację, że już go nie ma.

Do zrealizowania słownika ze słabymi referencjami na klucze potrzeba ogólniejszego wariantu słabej referencji, który jest związany z dwoma obiektami: kluczem i wartością. Istnienie słabej referencji między jakimś kluczem a wartością utrzymuje w mocy zależność: dopóki klucz żyje, skojarzona z nim wartość jest utrzymywana przy życiu. Sama słaba referencja nie utrzymuje przy życiu swojego klucza ani wartości. Dereferencja słabej referencji zwraca jej wartość, o ile odpowiedni klucz jeszcze żyje, bądź informację, że słaba referencja jest nieaktywna. Uproszczony wariant słabej referencji jest szczególnym przypadkiem tego ogólniejszego wariantu, w którym kluczem i wartością jest ten sam obiekt. Ogólniejszy wariant jest potrzebny, bo wartość w słowniku ze słabymi kluczami, która odwołuje się z powrotem do odpowiadającego jej klucza, nie powinna zapobiegać odśmieceniu tego klucza, a więc słownik nie powinien trzymać wartości silnymi referencjami.

Zrealizowanie słownika ze słabymi kluczami za pomocą takich słabych referencji wymagałoby okresowego przeglądania słownika w celu sprzątania nieaktywnych słabych referencji. Żeby tego uniknąć, warto wzbogacić mechanizm słabych referencji o funkcję służącą do usuwania słabej referencji ze struktury, w której jest zawarta. Słaba referencja jest więc tworzona z trzech obiektów: klucza, wartości i funkcji czyszczącej. Bezargumentowa funkcja czyszcząca jest wykonywana dla swoich skutków ubocznych, kiedy słaba referencja jest deaktywowana z powodu śmierci klucza. Jeśli słaba referencja umrze przed swoim kluczem albo razem z nim, to funkcja czyszcząca nie jest wykonywana.

Istniejące języki programowania często mają mocno ograniczone mechanizmy finalizacji i słabych referencji albo mają źle zaprojektowane reguły zależności między czasem życia obiektów i ich finalizatorów. Wybór niewłaściwych reguł ogranicza stosowalność finalizacji do zwalniania zewnętrznych zasobów albo ogranicza finalizację do interakcji z obiektami, o których implementacji wiemy więcej niż rozsądne prawa modularyzacji programu pozwalają wiedzieć.

Implementacja

Algorytmy odśmiecania, których zasada działania polega na chodzeniu po grafie obiektów i znajdowaniu żywych obiektów, z reguły łatwo uzupełnić o obsługę finalizacji i słabych referencji:

  • Obiekt finalizatora ma dwa pola: klucz i funkcja czyszcząca.
  • Aktywne finalizatory są powiązane w listę, która jest cały czas utrzymywana przy życiu.
  • Obiekt słabej referencji ma trzy pola: klucz, wartość i funkcja czyszcząca.
  • Aktywne słabe referencje są powiązane w listę.
  • Odwiedzanie pól obiektu w przypadku finalizatorów i słabych referencji odwiedza tylko funkcję czyszczącą.

Odśmiecanie ma dodatkowe czynności między stwierdzeniem, które obiekty są żywe, a zwolnieniem ich pamięci:

  1. Przeglądamy listę wszystkich słabych referencji: jeśli słaba referencja jest żywa i jej klucz jest żywy, to oznaczamy jej wartość jako żywą (wraz z innymi obiektami, na które ona wskazuje).
  2. Powtarzamy poprzedni punkt aż zbiór żywych obiektów nie przestanie się powiększać.
  3. Teraz można dokończyć odśmiecanie zwalniając pamięć.
  4. Odłączamy od listy finalizatorów te finalizatory, których klucze są martwe (zachowujemy je na osobnej liście).
  5. Odłączamy od listy słabych referencji martwe słabe referencje (zapominamy o nich) oraz te, które same są żywe, ale których klucze są martwe (zachowujemy je na osobnej liście).
  6. Jeśli lista odłączonych finalizatorów lub słabych referencji jest niepusta, to tworzymy wątek finalizujący, który wykona ich funkcje czyszczące.

Wielokrotne przeglądanie listy słabych referencji powoduje, że przy pewnych konfiguracjach obiektów odśmiecanie może mieć koszt proporcjonalny do kwadratu liczby słabych referencji. Dlatego warto zmodyfikować ten algorytm i nie przeglądać za każdym razem wszystkich słabych referencji, tylko zbudować słownik przyporządkowujący słabe referencje obiektom, które je „wyzwalają”, czyli ich kluczom oraz im samym; w miarę oznaczania wartości słabych referencji i ich podobiektów jako żywych kolejkować słabe referencje wyzwalane przez te obiekty; następnie przeglądać tylko zakolejkowane słabe referencje, a nie wszystkie, i tym z nich, które są żywe i których klucze są żywe, oznaczać ich wartości jako żywe; tak postępować aż kolejka zostanie opróżniona.

W przypadku niektórych implementacji odśmiecacza można uniknąć wyszukiwania obiektów oznaczanych jako żywych w słowniku. Zamiast niego w momencie oznaczania słabej referencji jako żywej, jeśli jej klucz jeszcze nie był oznaczony jako żywy, podmieniamy nagłówek klucza, tak żeby uznanie go później za żywy spowodowało przy okazji oznaczenie odpowiedniej wartości jako żywej.

Odśmiecacz pokoleniowy może mieć osobne listy finalizatorów i słabych referencji należących do każdego pokolenia.

Literatura

Paul R. Wilson, Uniprocessor Garbage Collection Techniques

Hans J. Boehm, A garbage collector for C and C++

Hans J. Boehm, Destructors, Finalizers, and Synchronization

Bruno Haible, Weak References, Data Types and Implementation