Metody realizacji języków programowania/MRJP Wykład 9: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 18 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
autor: Marcin Kowalczyk (qrczak@mimuw.edu.pl)
+
Autor: Marcin Kowalczyk (qrczak@mimuw.edu.pl)
  
 
=Odśmiecanie z punktu widzenia programisty=
 
=Odśmiecanie z punktu widzenia programisty=
Linia 39: Linia 39:
 
* Jest wskazywany przez pole jakiegoś żywego obiektu.
 
* Jest wskazywany przez pole jakiegoś żywego obiektu.
  
Odśmiecenie obiektu z reguły 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.
+
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==
 
==Konsekwencje odśmiecania==
Linia 65: Linia 67:
 
==Zliczanie odwołań (''reference counting'')==
 
==Zliczanie odwołań (''reference counting'')==
  
Technika zliczania odwołań polega na powiązaniu z każdym obiektem
+
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ł.
licznika przechowującego aktualną liczbę referencji na ten obiekt.
 
Wraz z utworzeniem nowej referencji, np. kiedy obiekt jest
 
przekazywany jako argument jakiejś funkcji, licznik jest zwiększany
 
o 1. Usunięcie referencji na ten obiekt, np. przypisanie zmiennej,
 
która wcześniej wskazywała na ten obiekt, innej wartości, 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
+
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.
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ń,
+
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.
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
+
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.
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
+
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.
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.
 
  
Możliwe są wariacje podstawowego mechanizmu zliczania odwołań, np.
+
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).
połączenie go z okresowo wykonywanymi innymi algorytmami odśmiecania
 
w celu usunięcia cyklicznych śmieci (tak robi podstawowa implementacja
 
Pythona).
 
  
 
==Mark & sweep==
 
==Mark & sweep==
  
Algorytm mark & sweep wymaga zarezerwowania jednego dodatkowego bitu
+
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.
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ż
+
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.
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.
 
Faza I: mark.
  
# Na początku wszystkie obiekty mają ten bit ustawiony na „nieodwiedzony”.
+
# Na początku wszystkie obiekty mają wspomniany bit ustawiony na „nieodwiedzony”.
 
# 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”.
 
# 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”.
 
# Dopóki zbiór G jest niepusty:
 
# Dopóki zbiór G jest niepusty:
Linia 132: Linia 95:
 
Faza II: sweep.
 
Faza II: sweep.
  
# Zwalniamy wszystkie nieodwiedzone obiekty, a pozostałym ustawiamy bit z powrotem na „nieodwiedzony”. Zamiast fizycznego odwracania bitu w każdym żywym obiekcie można zamienić znaczenie bitów rolami.
+
# 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
+
Możliwe są różne realizacje zbioru G i w związku z tym różne strategie wyboru obiektu z niego:
wyboru obiektu z niego:
 
  
* Jako stos adresów obiektów, w formie jawnej struktury danych, np. tablicy. W efekcie graf obiektów jest przeglądany w głąb.
+
* 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 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.
 
* Jako kolejka. W efekcie graf obiektów jest przeglądany wszerz.
  
Wadą podstawowej formy tego algorytmu jest konieczność okresowego
+
Wadą podstawowej formy tego algorytmu jest konieczność okresowego wstrzymania programu na czas przejrzenia całej pamięci i odwiedzenia każdego obiektu.
wstrzymania programu na czas przejrzenia całej pamięci i odwiedzenia
 
każdego obiektu.
 
  
 
==Mark & compact==
 
==Mark & compact==
  
Zamiast zwalniać pojedyncze obiekty jak w algorytmie mark & sweep,
+
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.
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
+
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.
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
 
przejść, np. najpierw ustalamy nowy adres każdego obiektu, potem
 
uaktualniamy wskaźniki, wreszcie ostatecznie przesuwamy obiekty.
 
  
 
==Odśmiecanie kopiujące (''copying GC'')==
 
==Odśmiecanie kopiujące (''copying GC'')==
  
Kopiować obiekty pod nowe adresy można od razu w trakcie przechodzenia
+
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.
grafu obiektów. Po przeniesieniu obiektu pod nowy adres pod starym
 
adresem można zostawić odsyłacz do nowego adresu. Zwykły obiekt jest
 
zawsze odróżnialny od takiego pozostawionego odsyłacza.
 
  
Odśmiecanie używa tymczasowo zbioru G bieżących obiektów i odbywa
+
Odśmiecanie kopiujące używa tymczasowo zbioru G bieżących obiektów i odbywa się następująco:
się następująco:
 
  
 
# Alokujemy nowy obszar pamięci, do którego zostaną przeniesione żywe obiekty. Na początku zbiór G jest pusty.
 
# Alokujemy nowy obszar pamięci, do którego zostaną przeniesione żywe obiekty. Na początku zbiór G jest pusty.
 
+
# 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.
# Odwiedzamy korzenie odśmiecania. Odwiedzenie wskaźnika polega na sprawdzeniu, czy pod danym adresem znajduje się odsyłacz. Jeśli tak, to tylko uaktualniamy wskaźnik na adres podany w odsyłaczu. Jeśli nie, to przenosimy obiekt pod pierwszy wolny adres w nowym obszarze pamięci, pozostawiamy odsyłacz, uaktualniamy wskaźnik i dodajemy przeniesiony obiekt do zbioru G.
 
 
# Dopóki zbiór G jest niepusty:
 
# Dopóki zbiór G jest niepusty:
 
## Wyjmujemy jakiś obiekt z G.
 
## Wyjmujemy jakiś obiekt z G.
Linia 180: Linia 124:
 
# Zwalniamy stary obszar pamięci, który zawiera teraz same śmieci. Nowy obszar pamięci staje się bieżącą stertą.
 
# 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 warianty. Przetwarzanie zbioru G może się przeplatać
+
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).
z odwiedzaniem poszczególnych korzeni. Zbiór G może zawierać wskaźniki
 
zawarte w obiektach, a nie same obiekty, dzięki czemu znalezienie pól
 
obiektu dla potrzeb skopiowania oraz dla potrzeb zapamiętania tych pól
 
do późniejszego odwiedzenia może się odbyć równocześnie.
 
  
Na różne sposoby można również zrealizować znajdowanie pól mogących
+
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.
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 od wskaźnika na
 
statycznie zaalokowany deskryptor. 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
+
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.
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
+
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.
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.
+
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.
Odwiedzane i kopiowane są tylko żywe obiekty, a następnie cały obszar
 
sterty zawierający śmieci jest zwalniany jednym ruchem. Taka
 
charakterystyka pracy sprawdza się, 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
+
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ś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 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; natomiast jeśli 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 tam prawdopodobnie łatwo odzyskamy dużo pamięci. Stare obiekty odkładamy na bok i odwiedzamy je rzadko.
+
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. Obiekty, które przeżyją, 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.
+
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 są tylko dwa: młode obiekty, które nie przeżyły jeszcze żadnego odśmiecania, i pozostałe, stare obiekty. Są też dwa rodzaje cyklu odśmiecania: mniejsze, polegające na przejrzeniu wyłącznie młodych obiektów, oraz większe, które dotyczy wszystkich obiektów.
+
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ł, trzeba umieć znaleźć takie wskaźniki taniej niż przez przejrzenie wszystkich starszych 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 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, do której należy to pole. Podczas odśmiecania 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 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.
+
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, to zapis sprowadza się do prostego przypisania adresu. Taka statyczna gwarancja występuje na przykład w trakcie inicjalizacji dopiero co stworzonego obiektu wartościami istniejącymi przed jego utworzeniem.
+
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 też mogą podlegać barierze zapisu. Programowa bariera zapisu w przypadku zmiennych lokalnych znajdujących się na stosie byłaby dość kosztowna, bo zapis takich zmiennych jest częsty. Można jednak uniknąć przeglądania całego stosu przy każdym odśmiecaniu, jeśli zmiany zmiennych lokalnych dotyczą 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ć tylko ramki stosu między tą najdalszą a bieżącym wierzchołkiem.
+
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ę również połączenie różnych algorytmów w zależności od pokolenia, np. odśmiecanie kopiujące w młodszych pokoleniach i mark & sweep z ewentualnym okresowym kompaktowaniem w najstarszym (w którym obiekty już pozostają).
+
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, które muszą być skutkiem imperatywnego przypisania. Ale również nowoczesne implementacje języków obiektowych często stosują odśmiecanie pokoleniowe.
+
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'')==
 
==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, którego reakcja na jakieś zdarzenie jest akurat pilna. Można próbować zmniejszać dokuczliwość pauz przez automatyczne odśmiecanie, kiedy wydaje się, że czas jest bardziej odpowiedni, np. kiedy program właśnie czeka na zdarzenie zewnętrzne i procesor nie ma nic do roboty. Z kolei odśmiecanie pokoleniowe powoduje, że większość pauz jest krótka — co jakiś czas jednak musi wciąż odśmiecić całość. Bardziej atrakcyjne jest wyeliminowanie w ogóle konieczności odśmiecania całej sterty naraz.
+
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.
  
Odśmiecanie przyrostowe polega na przeplataniu odśmiecania z normalnym wykonaniem programu. 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 przeszkadza zmieniając co chwilę połączenia między obiektami i sam zbiór korzeni.
+
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ć zachowane, żeby odśmiecacz mógł pracować na zmieniającym się wciąż grafie obiektów, 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 pola jeszcze nie zostały odwiedzone, nazwijmy „szarymi”. Pozostałe, nieodwiedzone obiekty są „białe”.
+
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 białych 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.
+
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ć.
+
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 obiektów, które pogwałciłyby niezmiennik. Oprócz tego główny program musi dbać o to, żeby odśmiecacz mógł znaleźć wszystkie szare obiekty. Istnieje wiele strategii kolorowania nowo alokowanych obiektów i przywracania niezmiennika po przypisaniu.
+
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 ilość faktycznie żywych obiektów 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.
+
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'')=
 
=Odśmiecanie dokładne czy konserwatywne (''precise or conservative GC'')=
Linia 272: Linia 187:
 
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.
 
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, np. 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 pokazuje, że prościej jest, kiedy każdy obiekt jest samoopisywalny w stopniu potrzebnym odśmiecaczowi.)
+
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 obiektu bywa umożliwienie odśmiecaczowi odnalezienia zmiennych lokalnych. Można odkładać na stosie również informację o reprezentacji danej ramki stosu. Można też wnioskować to na podstawie adresu powrotu i przygotowanych przez kompilator map przyporządkowujących możliwym adresom powrotu informację o tym, która funkcja była wołana, czyli jakie są jej zmienne lokalne. Trzeba wybrać jakiś kompromis między szybkością wykonania właściwego programu a szybkością odśmiecania.
+
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ż 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ść popularne, 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.
+
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. Co prawda operacje na takiej tablicy 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 umożliwienie odśmiecaczowi skanowania zmiennych lokalnych.
+
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, a inne wartości, takie jak liczby całkowite, są reprezentowane przez wartości przesunięte w lewo z ustawionym najmłodszym bitem albo kilkoma bitami. 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. 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.
+
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 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 wie, 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.
+
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, tylko wystarczy na umieszczenie wskaźnika 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, wskazują poza pamięć programu, gdzieś w połowie obiektu, w kod programu itp.
+
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'').
 
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ę na podstawie niektórych obiektów, a inne przegląda konserwatywnie.
+
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 dany 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ę zmieni albo sam zostanie zwolniony). Takie wycieki zwykle są niegroźne, bo jest mało prawdopodobne, że znaczna liczba obiektów będzie miała takie fałszywe wskaźniki utrzymujące je 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.
+
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 wszelkie możliwe układy bajtów (np. skompresowany strumień video), może utworzyć taką liczbę fałszywych wskaźników, która uniemożliwi zwolnienie wystarczającej ilości pamięci przez konserwatywne odśmiecanie. Zwłaszcza na 32-bitowej architekturze, gdzie przestrzeń adresowa jest względnie mała.
+
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.
  
Odśmiecanie konserwatywe nie może zmieniać adresów obiektów w pamięci, tzn. odpadają wszelkie warianty odśmiecania kopiującego, bo 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.
+
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łęgo 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.
+
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. Można też zakładać, że każdy obiekt zaczyna się od adresu podzielnego przez wielkość słowa maszynowego i każdy 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.
+
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.
 
Dobrej jakości konserwatywny odśmiecacz do języka C został zaimplementowany przez Hansa J. Boehma i jest dostępny na licencji BSD-like.
Linia 308: Linia 223:
 
==Finalizacja==
 
==Finalizacja==
  
Pewne obiekty reprezentują zewnętrzne zasoby, istniejące poza programem, takie jak 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.
+
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:
 
W języku programowania z odśmiecaniem stosowane są dwa podstawowe style zwalniania zewnętrznych zasobów:
# Jawnie w określonym miejscu w programie. 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.
+
# 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.
 
# Kiedy obiekt danego rodzaju jest odśmiecany, wykonywane są dodatkowe czynności sprzątające.
 
# 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 liczby, 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, np. kiedy plik jest otwarty do zapisu na wyłączność jednego procesu.
+
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ć.
  
Mimo wszystko są sytuacje, kiedy możemy sobie pozwolić na faktyczne zwolnienie zasobu z opóźnieniem względem momentu, kiedy 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.
  
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''), a sama zarejestrowana czynność sprzątająca skojarzona z danym obiektem — finalizatorem (''finalizer'').
+
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ę.
  
Poprawne zaprojektowanie mechanizmu finalizacji, którego można użyć nie tylko do zwolnienia zewnętrznych zasobów, ale także do wyrejestrowania obiektu ze struktur danych używanych przez resztę programu, jest trudniejszym problemem, niżby się na pierwszy rzut oka wydawało. Ale najpierw warto sobie powiedzieć o słabych referencjach.
+
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.
  
==Słabe referencje (''weak references'')==
+
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.
  
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.
+
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.
  
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. Przydałby się słownik, który nie utrzymuje swoich kluczy przy życiu, a kiedy taki klucz umiera, jest automatycznie usuwany ze słownika.
+
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.
  
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.
+
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.
  
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 go już nie ma.
+
==Słabe referencje (''weak references'')==
  
Do słownika ze słabymi referencjami na klucze potrzebna 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 samego 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.
+
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.
 
 
Zrealizowanie słownika ze słabymi kluczami za pomocą takich słabych referencji wymagałoby okresowego przeglądania słownika w celu usunięcia nieaktywnych słabych referencji. Żeby tego uniknąć, warto wzbogacić mechanizm słabych referencji o finalizację. Słaba referencja jest tworzona z trzech obiektów: klucza, wartości i finalizatora. Finalizator jest bezargumentową funkcją, która jest wykonywana dla swoich skutków ubocznych, kiedy słaba referencja jest deaktywowana z powodu śmierci klucza. Powiązanie między kluczem, wartością a finalizatorem pozostaje w mocy nawet kiedy program porzucił samą słabą referencję.
 
 
 
Słaba referencja udostępnia jeszcze dwie operacje: jawna deaktywacja wraz z finalizacją oraz sama deaktywacja. Deaktywacja oznacza usunięcie powiązania między czasami życia obiektów skojarzonych ze słabą referencją. Finalizacja już nieaktywnej słabej referencji jest operacją pustą.
 
  
Mechanizm finalizatorów związanych ze słabymi referencjami wystarcza do zaimplementowania finalizacji w sensie zwolnienia zewnętrznych zasobów. Wystarczy stworzyć słabą referencję z odpowiednim finalizatorem i dowolną wartością. Nie trzeba jej nigdzie przechowywać, chyba że chcemy udostępnić operację jawnego zwolnienia zasobów obiektu (za pomocą operacji deaktywacji z finalizacją wykonanej na odpowiedniej słabej referencji).
+
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.
  
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. 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ę synchronizować muteksami. Jawna deaktywacja słabej referencji z finalizacją powinna sprawdzić, czy ta słaba referencja nie jest przypadkiem właśnie finalizowana przez inny wątek, i jeśli tak, to poczekać, aż finalizator się skończy.
+
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.
  
Do poprawnego działania finalizatora, jak każdej funkcji, wymagane jest, żeby obiekty, których on używa, były utrzymywane przy życiu, dopóki finalizator ma szansę zostać użyty. 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.
+
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.
  
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 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.
+
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.
  
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.
+
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 mają często mocno ograniczone mechanizmy finalizacji i słabych referencji albo źle zaprojektowane reguły zależności między czasem życia obiektów i ich finalizatorów. Wybór innych 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ć.
+
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==
 
==Implementacja==
  
Algorytmy odśmiecania, których zasada działania polega na chodzeniu po grafie obiektów, z reguły łatwo uzupełnić o obsługę słabych referencji i finalizacji:
+
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 słabej referencji ma trzy pola: klucz, wartość i finalizator.
+
* Obiekt finalizatora ma dwa pola: klucz i funkcja czyszcząca.
* Aktywne słabe referencje są powiązane w listę, która jest cały czas utrzymywana przy życiu.
+
* Aktywne finalizatory są powiązane w listę, która jest cały czas utrzymywana przy życiu.
* Odwiedzanie pól obiektu w przypadku słabych referencji odwiedza tylko finalizator.
+
* 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:
 
Odśmiecanie ma dodatkowe czynności między stwierdzeniem, które obiekty są żywe, a zwolnieniem ich pamięci:
  
# Przeglądamy listę wszystkich słabych referencji: jeśli klucz którejś referencji jest żywy, to oznaczamy jego wartość jako żywą (wraz z innymi obiektami, na które wskazuje).
+
# 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).
 
# Powtarzamy poprzedni punkt aż zbiór żywych obiektów nie przestanie się powiększać.
 
# Powtarzamy poprzedni punkt aż zbiór żywych obiektów nie przestanie się powiększać.
 
# Teraz można dokończyć odśmiecanie zwalniając pamięć.
 
# Teraz można dokończyć odśmiecanie zwalniając pamięć.
# Jeśli pozostały jakieś słabe referencje z martwymi kluczami, to odłączamy je od listy wszystkich słabych referencji i tworzymy wątek finalizujący, który wykona finalizatory tych słabych referencji.
+
# Odłączamy od listy finalizatorów te finalizatory, których klucze są martwe (zachowujemy je na osobnej liście).
 +
# 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).
 +
# 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.
  
Powtarzanie przeglądania 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 można go zmodyfikować i nie przeglądać za każdym razem wszystkich słabych referencji, tylko zbudować słownik przyporządkowujący słabe referencje ich kluczom, w miarę oznaczania wartości słabych referencji i ich podobiektów jako żywe kolejkować słabe referencje wyzwalane przez te obiekty, a potem przeglądać tylko kolejkowane słabe referencje, a nie wszystkie.
+
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 słabych referencji należących do każdego pokolenia.
+
Odśmiecacz pokoleniowy może mieć osobne listy finalizatorów i słabych referencji należących do każdego pokolenia.
  
 
=Literatura=
 
=Literatura=

Aktualna wersja na dzień 16:35, 19 lis 2006

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

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