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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 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.

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ą ten 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 odwracania bitu w każdym żywym obiekcie można zamienić znaczenie bitów 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, 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 przejść, np. najpierw ustalamy nowy adres każdego obiektu, potem uaktualniamy wskaźniki, wreszcie ostatecznie przesuwamy obiekty.

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 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 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.
  1. 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.
  2. Dopóki zbiór G jest niepusty:
    1. Wyjmujemy jakiś obiekt z G.
    2. Odwiedzamy wskaźniki zawarte w tym obiekcie.
  3. 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ć 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 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 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 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 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; 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 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.

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.

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.

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.

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.

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.

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ą).

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.

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.

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.

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”.

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.

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ć.

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.

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.

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, 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.)

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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, 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.

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. 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 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.

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), a sama zarejestrowana czynność sprzątająca skojarzona z danym obiektem — finalizatorem (finalizer).

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.

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. 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.

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.

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.

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).

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.

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.

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.

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.

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ć.

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:

  • Obiekt słabej referencji ma trzy pola: klucz, wartość i finalizator.
  • Aktywne słabe referencje 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.

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 klucz którejś referencji jest żywy, to oznaczamy jego wartość jako żywą (wraz z innymi obiektami, na które 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. 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.

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.

Odśmiecacz pokoleniowy może mieć osobne listy 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

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Metody_realizacji_języków_programowania/MRJP_Wykład_9&oldid=61594”