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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(formatowanie)
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=
  
== Obiekty i referencje ==
+
==Obiekty i referencje==
  
 
Relacja między obiektami a zmiennymi w różnych językach programowania
 
Relacja między obiektami a zmiennymi w różnych językach programowania
 
jest najczęściej dwojakiego rodzaju:
 
jest najczęściej dwojakiego rodzaju:
  
1. Zmienna zawiera obiekt, jest z nim nierozerwalnie związana. Czas
+
# 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.
życia (istnienia) obiektu pokrywa się z czasem aktywności zakresu
+
# 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ą.
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
 
W tym samym języku mogą współistnieć oba paradygmaty, choć różne
Linia 25: Linia 18:
 
rekordach.
 
rekordach.
  
Skopiowanie takiej wartości - wykonywane przy okazji przypisania
+
Skopiowanie takiej wartości — wykonywane przy okazji przypisania
 
zmiennej, przekazania argumentu funkcji albo zwrócenia wyniku funkcji
 
zmiennej, przekazania argumentu funkcji albo zwrócenia wyniku funkcji
- jest dla kompilatora łatwe i często sprowadza się do skopiowania
+
— jest dla kompilatora łatwe i często sprowadza się do skopiowania
 
kilku bajtów.
 
kilku bajtów.
  
Linia 33: Linia 26:
 
Wartościami zmiennych są tutaj referencje nazywane też wskaźnikami.
 
Wartościami zmiennych są tutaj referencje nazywane też wskaźnikami.
  
== Gospodarka pamięcią ==
+
==Gospodarka pamięcią==
  
 
Skoro czas życia obiektu nie pokrywa się z czasem życia zmiennych
 
Skoro czas życia obiektu nie pokrywa się z czasem życia zmiennych
Linia 40: Linia 33:
 
zostanie zwolniona. Najczęściej spotykane są dwa rozwiązania:
 
zostanie zwolniona. Najczęściej spotykane są dwa rozwiązania:
  
1. Ręczna gospodarka pamięcią. Programista ma do dyspozycji operację
+
===Ręczna gospodarka pamięcią===
zwalniającą wskazany obiekt, nazwaną np. 'delete' albo 'free'.
+
 
 +
Programista ma do dyspozycji operację
 +
zwalniającą wskazany obiekt, nazwaną np. <code>delete</code> albo <code>free</code>.
 
Każdy obiekt z grupy obiektów niezwiązanych z konkretnymi zmiennymi
 
Każdy obiekt z grupy obiektów niezwiązanych z konkretnymi zmiennymi
 
należy zwolnić dokładnie raz, po zakończeniu jego użycia.
 
należy zwolnić dokładnie raz, po zakończeniu jego użycia.
Linia 48: Linia 43:
 
zajmował pamięć aż do zakończenia działania programu. Sytuacja,
 
zajmował pamięć aż do zakończenia działania programu. Sytuacja,
 
w której program ciągle tworzy obiekty, o których potem zapomina,
 
w której program ciągle tworzy obiekty, o których potem zapomina,
nazywa się wyciekiem pamięci (memory leak) i najczęściej skutkuje
+
nazywa się wyciekiem pamięci (''memory leak'') i najczęściej skutkuje
 
niepotrzebnym zajęciem bardzo dużej ilości pamięci, spowolnieniem
 
niepotrzebnym zajęciem bardzo dużej ilości pamięci, spowolnieniem
 
systemu i w końcu zabiciem aplikacji przez system operacyjny.
 
systemu i w końcu zabiciem aplikacji przez system operacyjny.
Linia 58: Linia 53:
 
które wskazywały na ten obiekt, wskazują teraz na miejsce w
 
które wskazywały na ten obiekt, wskazują teraz na miejsce w
 
pamięci, w którym jest już coś zupełnie innego. Są to tzw. wiszące
 
pamięci, w którym jest już coś zupełnie innego. Są to tzw. wiszące
referencje (dangling references). Operacje na tych referencjach
+
referencje (''dangling references''). Operacje na tych referencjach
 
mają chaotyczne skutki: od niewidocznych, przez awaryjne
 
mają chaotyczne skutki: od niewidocznych, przez awaryjne
 
zakończenie programu przez system operacyjny, do przekłamania
 
zakończenie programu przez system operacyjny, do przekłamania
 
wyników i utraty danych użytkownika albo złośliwego zdalnego
 
wyników i utraty danych użytkownika albo złośliwego zdalnego
położenia usługi sieciowej (denial-of-service attack).
+
położenia usługi sieciowej (''denial-of-service attack'').
 +
 
 +
===Odśmiecanie===
  
2. Odśmiecanie. Język programowania automatycznie zwalnia pamięć
+
Język programowania automatycznie zwalnia pamięć
 
obiektów, do których program już nie ma szans się odwołać. Takie
 
obiektów, do których program już nie ma szans się odwołać. Takie
obiekty nazywają się śmieciami (garbage) albo martwymi obiektami
+
obiekty nazywają się śmieciami (''garbage'') albo martwymi obiektami
(dead objects), w odróżnieniu od pozostałych, żywych obiektów
+
(''dead objects''), w odróżnieniu od pozostałych, żywych obiektów
(live objects).
+
(''live objects'').
  
 
Ponieważ w ogólności nie da się automatycznie stwierdzić, których
 
Ponieważ w ogólności nie da się automatycznie stwierdzić, których
Linia 82: Linia 79:
 
jeden z warunków:
 
jeden z warunków:
  
a) Jest wskazywany przez zmienną globalną albo aktywną zmienną
+
* Jest wskazywany przez zmienną globalną albo aktywną zmienną lokalną.
lokalną.
+
* Jest wskazywany przez pole jakiegoś żywego obiektu.
 
 
b) Jest wskazywany przez pole jakiegoś żywego obiektu.
 
  
 
Odśmiecenie obiektu z reguły nie jest obserwowalne przez program,
 
Odśmiecenie obiektu z reguły nie jest obserwowalne przez program,
Linia 92: Linia 87:
 
chwili liczba żywych obiektów jest ograniczona.
 
chwili liczba żywych obiektów jest ograniczona.
  
== Konsekwencje odśmiecania ==
+
==Konsekwencje odśmiecania==
  
 
Starsze języki częściej stosowały ręczną gospodarkę pamięcią,
 
Starsze języki częściej stosowały ręczną gospodarkę pamięcią,
Linia 116: Linia 111:
 
W nowoczesnym C++ odwołania do dynamicznie zaalokowanych obiektów
 
W nowoczesnym C++ odwołania do dynamicznie zaalokowanych obiektów
 
coraz częściej odbywają się przez pomocnicze obiekty zajmujące się
 
coraz częściej odbywają się przez pomocnicze obiekty zajmujące się
zarządzaniem czasem ich życia, tzw. sprytne wskaźniki (smart
+
zarządzaniem czasem ich życia, tzw. sprytne wskaźniki
pointers). Automatyczne wykonanie destruktura w momencie zakończenia
+
(''smart pointers''). Automatyczne wykonanie destruktura w momencie
czasu życia zmiennej jest wykorzystywane do skojarzenia ze sobą akcji
+
zakończenia czasu życia zmiennej jest wykorzystywane do skojarzenia
"zajmującej" i "zwalniającej" zasób, które są wykonywane odpowiednio
+
ze sobą akcji &bdquo;zajmującej&rdquo; i &bdquo;zwalniającej&rdquo;
przed i po jakimś fragmencie kodu, niezależnie od sposobu opuszczenia
+
zasób, które są wykonywane odpowiednio przed i po jakimś fragmencie
tego fragmentu (RAII - Resource Acquisition Is Initialization).
+
kodu, niezależnie od sposobu opuszczenia tego fragmentu
 +
(RAII &mdash; ''Resource Acquisition Is Initialization'').
  
 
Z kolei odśmiecanie pozwala na swobodniejsze stosowanie paradygmatu
 
Z kolei odśmiecanie pozwala na swobodniejsze stosowanie paradygmatu
referencji. Stosowanie referencji na niezmienialne obiekty (immutable
+
referencji. Stosowanie referencji na niezmienialne obiekty
objects) jest równoważne stosowaniu wartości z paradygmatu wartości,
+
(''immutable objects'') jest równoważne stosowaniu wartości z paradygmatu
o ile one nie mają samodzielnie adresowalnej struktury wewnętrznej.
+
wartości, o ile one nie mają samodzielnie adresowalnej struktury
Programiście jest zwykle wszystko jedno, czy operacja
+
wewnętrznej. Programiście jest zwykle wszystko jedno, czy operacja
zapisana przez coś podobnego do 'x := 5' w danym języku sprowadza się
+
zapisana przez coś podobnego do <code>x := 5</code> w danym języku
do skopiowania liczby 5, czy skopiowania referencji na któryś obiekt
+
sprowadza się do skopiowania liczby 5, czy skopiowania referencji
reprezentujący liczbę 5. Dlatego odśmiecane języki często stosują
+
na któryś obiekt reprezentujący liczbę 5. Dlatego odśmiecane języki
paradygmat referencji jako podstawowy albo wręcz jedyny.
+
często stosują paradygmat referencji jako podstawowy albo wręcz jedyny.
  
 
W odśmiecanych językach jest silniejsza tendencja do programowania
 
W odśmiecanych językach jest silniejsza tendencja do programowania
Linia 137: Linia 133:
 
referencji zamiast przez zmiany starych obiektów w miejscu.
 
referencji zamiast przez zmiany starych obiektów w miejscu.
 
Również charakterystyczna dla programowania funkcyjnego możliwość
 
Również charakterystyczna dla programowania funkcyjnego możliwość
tworzenia lokalnych funkcji i zwracania ich na zewnątrz (upward
+
tworzenia lokalnych funkcji i zwracania ich na zewnątrz
closures) w zasadzie wymaga odśmiecania, żeby te lokalne funkcje
+
(''upward closures'') w zasadzie wymaga odśmiecania, żeby te lokalne funkcje
 
mogły używać lokalnych zmiennych funkcji, w której są zawarte,
 
mogły używać lokalnych zmiennych funkcji, w której są zawarte,
 
również po zakończeniu tej zewnętrznej funkcji.
 
również po zakończeniu tej zewnętrznej funkcji.
Linia 155: Linia 151:
 
Dlatego do określenia czynności do wykonania w momencie wejścia
 
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
 
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'
+
niż RAII, np. <code>unwind-protect</code> i makra w stylu <code>with-open-file</code>
w Lispie i 'using' w C#.
+
w Lispie i <code>using</code> w C#.
  
 
Zatem różnice w stylu programowania między odśmiecanymi a
 
Zatem różnice w stylu programowania między odśmiecanymi a
 
nieodśmiecanymi językami nie sprowadzają się do jawnego stosowania
 
nieodśmiecanymi językami nie sprowadzają się do jawnego stosowania
bądź pomijania 'delete'. Odśmiecanie wpływa na organizację obiektów,
+
bądź pomijania <code>delete</code>. Odśmiecanie wpływa na organizację obiektów,
 
na projektowanie interfejsów, na stopień współdzielenia tudzież
 
na projektowanie interfejsów, na stopień współdzielenia tudzież
 
kopiowania obiektów przez różne fragmenty programu.
 
kopiowania obiektów przez różne fragmenty programu.
  
= Implementacja odśmiecania =
+
=Implementacja odśmiecania=
  
== 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
Linia 180: Linia 176:
 
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
 
obiektów względem standardowego: obiekt jest uznawany za żywy, kiedy
jest wskazywany przez pole *jakiegokolwiek* obiektu, niekoniecznie
+
jest wskazywany przez pole '''jakiegokolwiek''' obiektu, niekoniecznie
 
żywego. Innymi słowy, zbiór obiektów, które wskazują na siebie
 
żywego. Innymi słowy, zbiór obiektów, które wskazują na siebie
 
nawzajem, a przestaną być osiągalne z reszty programu, powoduje wyciek
 
nawzajem, a przestaną być osiągalne z reszty programu, powoduje wyciek
Linia 212: Linia 208:
 
Pythona).
 
Pythona).
  
== Mark & sweep ==
+
==Mark &amp; sweep==
  
Algorytm mark & sweep wymaga zarezerwowania jednego dodatkowego bitu
+
Algorytm mark &amp; sweep wymaga zarezerwowania jednego dodatkowego bitu
 
w każdym obiekcie. Przynajmniej koncepcyjnie, bo ta informacja nie
 
w każdym obiekcie. Przynajmniej koncepcyjnie, bo ta informacja nie
 
musi mieć fizycznej formy bitu, wystarczy jakaś realizacja podziału
 
musi mieć fizycznej formy bitu, wystarczy jakaś realizacja podziału
Linia 227: Linia 223:
 
Faza I: mark.
 
Faza I: mark.
  
1. Na początku wszystkie obiekty mają ten bit ustawiony na
+
# Na początku wszystkie obiekty mają ten bit ustawiony na &bdquo;nieodwiedzony&rdquo;.
"nieodwiedzony".
+
# Do zbioru G na początku należą obiekty wskazywane przez &bdquo;korzenie&rdquo; odśmiecania (roots), czyli przez zmienne globalne i lokalne. Ustawiamy bity tych obiektów na &bdquo;odwiedzony&rdquo;.
 
+
# Dopóki zbiór G jest niepusty:
2. Do zbioru G na początku należą obiekty wskazywane przez "korzenie"
+
## Wyjmujemy jakiś obiekt z G
odśmiecania (roots), czyli przez zmienne globalne i lokalne.
+
## Dodajemy do G wszystkie nieodwiedzone obiekty wskazywane przez ten obiekt, ustawiając ich bity na &bdquo;odwiedzony&rdquo;.
Ustawiamy bity tych obiektów na "odwiedzony".
 
 
 
3. Dopóki zbiór G jest niepusty:
 
 
 
a) Wyjmujemy jakiś obiekt z G
 
 
 
b) Dodajemy do G wszystkie nieodwiedzone obiekty wskazywane przez
 
ten obiekt, ustawiając ich bity na "odwiedzony".
 
  
 
Faza II: sweep.
 
Faza II: sweep.
  
1. Zwalniamy wszystkie nieodwiedzone obiekty, a pozostałym ustawiamy
+
# Zwalniamy wszystkie nieodwiedzone obiekty, a pozostałym ustawiamy bit z powrotem na &bdquo;nieodwiedzony&rdquo;. Zamiast fizycznego odwracania bitu w każdym żywym obiekcie można zamienić znaczenie bitów rolami.
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
 
Możliwe są różne realizacje zbioru G i w związku z tym różne strategie
wyboru obiektu x:
+
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, 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.
  
Linia 260: Linia 244:
 
każdego obiektu.
 
każdego obiektu.
  
== Mark & compact ==
+
==Mark &amp; compact==
  
Zamiast zwalniać pojedyncze obiekty jak w algorytmie mark & sweep,
+
Zamiast zwalniać pojedyncze obiekty jak w algorytmie mark &amp; sweep,
 
pozostawiając żywe obiekty między zwolnionymi miejscami, można
 
pozostawiając żywe obiekty między zwolnionymi miejscami, można
przenieść żywe obiekty do spójnego obszaru pamięci, "zsuwając" je na
+
przenieść żywe obiekty do spójnego obszaru pamięci, &bdquo;zsuwając&rdquo; je na
 
miejsca po zwolnionych obiektach. Dzięki temu alokacja nowych obiektów
 
miejsca po zwolnionych obiektach. Dzięki temu alokacja nowych obiektów
 
pobiera pamięć ze spójnego obszaru wolnej pamięci, co jest bardzo
 
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
 
szybkie. Poza tym zgrupowanie używanych obiektów w spójnym kawałku
pamięci ułatwia procesorowi efektywne cache'owanie pamięci.
+
pamięci ułatwia procesorowi efektywne cache&rsquo;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
 
reprezentacji wszystkich wskaźników na niego, a wskaźniki są ze swojej
natury "jednokierunkowe": nie można szybko zlokalizować wszystkich
+
natury &bdquo;jednokierunkowe&rdquo;: nie można szybko zlokalizować wszystkich
wskaźników na dany obiekt. Faza "sweep" składa się więc z kilku
+
wskaźników na dany obiekt. Faza &bdquo;sweep&rdquo; składa się więc z kilku
 
przejść, np. najpierw ustalamy nowy adres każdego obiektu, potem
 
przejść, np. najpierw ustalamy nowy adres każdego obiektu, potem
 
uaktualniamy wskaźniki, wreszcie ostatecznie przesuwamy obiekty.
 
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
Linia 287: Linia 271:
 
się następująco:
 
się następująco:
  
1. Alokujemy nowy obszar pamięci, do którego zostaną przeniesione żywe
+
# Alokujemy nowy obszar pamięci, do którego zostaną przeniesione żywe obiekty. Na początku zbiór G jest pusty.
obiekty. Na początku zbiór G jest pusty.
 
 
 
2. 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.
 
 
 
3. Dopóki zbiór G jest niepusty:
 
 
 
a) Wyjmujemy jakiś obiekt z G.
 
 
 
b) Odwiedzamy wskaźniki zawarte w tym obiekcie.
 
  
4. Zwalniamy stary obszar pamięci, który zawiera teraz same śmieci.
+
# 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.
Nowy obszar pamięci staje się bieżącą stertą.
+
# Dopóki zbiór G jest niepusty:
 +
## Wyjmujemy jakiś obiekt z G.
 +
## Odwiedzamy wskaźniki zawarte w tym obiekcie.
 +
# 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 warianty. Przetwarzanie zbioru G może się przeplatać
Linia 326: Linia 299:
 
Kolejność stosowa i tym samym przeglądanie grafu obiektów w głąb
 
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,
 
powoduje ułożenie wskazujących na siebie obiektów blisko siebie,
co ułatwia pracę sprzętowym mechanizmom cache'ującym.
+
co ułatwia pracę sprzętowym mechanizmom cache&rsquo;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
Linia 345: Linia 318:
  
 
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
+
odśmiecaniem w stylu mark &amp; sweep albo ze zliczaniem odwołań. Na
 
niekorzyść przemawia fizycznie kopiowanie obiektów z miejsca w
 
niekorzyść przemawia fizycznie kopiowanie obiektów z miejsca w
 
miejsce, ale z drugiej strony unikamy zwalniania indywidualnych
 
miejsce, ale z drugiej strony unikamy zwalniania indywidualnych
Linia 351: Linia 324:
 
i od czasu ich życia, a nie od tempa alokacji.
 
i od czasu ich życia, a nie od tempa alokacji.
  
== Odśmiecanie pokoleniowe (generational GC) ==
+
==Odśmiecanie pokoleniowe (''generational GC'')==
  
 
TODO
 
TODO
  
== Odśmiecanie przyrostowe (incremental GC) ==
+
== Odśmiecanie przyrostowe (''incremental GC'') ==
  
 
Wspólne dla wielu algorytmów odśmiecania, które polegają na chodzeniu
 
Wspólne dla wielu algorytmów odśmiecania, które polegają na chodzeniu
 
po grafie obiektów przez odśmiecacz, jest koncepcyjne przyporządkowanie
 
po grafie obiektów przez odśmiecacz, jest koncepcyjne przyporządkowanie
każdemu obiektowi "koloru". Obiekty, które zostały uznane za żywe
+
każdemu obiektowi &bdquo;koloru&rdquo;. Obiekty, które zostały uznane za żywe
i których wszystkie pola zostały już odwiedzone, nazwijmy "czarnymi".
+
i których wszystkie pola zostały już odwiedzone, nazwijmy &bdquo;czarnymi&rdquo;.
 
Żywe obiekty, których pola jeszcze nie zostały odwiedzone, nazwijmy
 
Żywe obiekty, których pola jeszcze nie zostały odwiedzone, nazwijmy
"szarymi". Pozostałe, nieodwiedzone obiekty są "białe".
+
&bdquo;szarymi&rdquo;. Pozostałe, nieodwiedzone obiekty są &bdquo;białe&rdquo;.
  
 
TODO
 
TODO
  
= Niskopoziomowe aspekty implementacji odśmiecania =
+
=Niskopoziomowe aspekty implementacji odśmiecania=
  
== Odśmiecanie dokładne / konserwatywne (precise / conservative GC) ==
+
==Odśmiecanie dokładne / konserwatywne (''precise / conservative GC'')==
  
 
TODO
 
TODO
  
== Cheney on the MTA ==
+
==Cheney on the MTA==
  
 
TODO
 
TODO
  
= Obiekty specjalne =
+
=Obiekty specjalne=
  
== Finalizacja ==
+
==Finalizacja==
  
 
TODO
 
TODO
  
== Słabe referencje ==
+
==Słabe referencje==
  
 
TODO
 
TODO

Wersja z 16:15, 28 wrz 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 najczęściej stosowany do małych obiektów o prostej strukturze, których typ jest dokładnie znany statycznie (w czasie kompilacji), np. przy liczbach i niewielkich rekordach.

Skopiowanie takiej wartości — wykonywane przy okazji przypisania zmiennej, przekazania argumentu funkcji albo zwrócenia wyniku funkcji — jest dla kompilatora łatwe i często sprowadza się do skopiowania kilku bajtów.

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 jest już 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, którym programista określa sposób kopiowania (konstruktor kopiujący, operator przypisania) i zwalniania (destruktor). Zautomatyzowane jest generowanie implementacji tych operacji wykonujących analogiczną operację 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 z paradygmatu wartości, o ile one nie mają samodzielnie adresowalnej struktury wewnętrznej. Programiście jest zwykle wszystko jedno, czy operacja zapisana 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. Dlatego odśmiecane języki często stosują paradygmat referencji jako podstawowy albo wręcz jedyny.

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 jednaj technicznie możliwe, jeśli 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 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 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.

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 globalne i lokalne. 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)

TODO

Odśmiecanie przyrostowe (incremental GC)

Wspólne dla wielu algorytmów odśmiecania, które polegają na chodzeniu po grafie obiektów przez odśmiecacz, jest 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”.

TODO

Niskopoziomowe aspekty implementacji odśmiecania

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

TODO

Cheney on the MTA

TODO

Obiekty specjalne

Finalizacja

TODO

Słabe referencje

TODO