Hery's devlog

Jednym z głównych problemów związanych z wykorzystaniem garbage collectora jest możliwość dość drastycznego spadku wydajności w nieoczekiwanych momentach. Z tego powodu odśmiecanie pamięci zwykle nie może zostać zastosowane w systemach czasu rzeczywistego, a także w innych sytuacjach gdzie wydajność programu jest istotna. Twórcy systemu Inferno stworzyli algorytm Very Concurrent Garbage Collection (VCGC), którego zadaniem jest zminimalizowanie tych problemów.

Równoległe przetwarzanie

System Inferno jest systemem rozproszonym. Powoduje to, że programowanie równoległe jest zalecanie i potrafi przynieść dość duży wzrost wydajności. Dlatego też istotą VGCG jest możliwość wykonywania procesu odśmiecania na wielu wątkach. Każdy z trzech elementów garbage collectora typu mark & sweep (jakim jest VGCG) jest całkowicie niezależny od pozostałych i może działać w oddzielnym wątku bez potrzeby używania dodatkowych mechanizmów synchronizacji.

Niezależność poszczególnych operacji związanych z odśmiecaniem pozwala przenieść je na inny procesor dzięki czemu właściwe wykonywanie programu nie jest w żaden sposób dodatkowo spowalniane i działa tak samo wydajnie jak w sytuacji gdy garbage collector nie jest używany.

Mark & sweep

Najpopularniejszym rodzajem algorytmów odśmiecania pamięci jest mark & sweep. Polega on na zlokalizowaniu i oznaczeniu wszystkich używanych obszarów pamięci (czyli takich do których istnieją odwołania) a następnie zwolnieniu pozostałego miejsca. Zwykle garbage collector tego typu składa się z trzech elementów:

• mutator - właściwy kod programu, w nim znajduje się kod zajmujący się przydzielaniem pamięci na żądanie aplikacji
• marker - wyszukuje i oznacza nieużywane obiekty w pamięci
• sweeper - zwalnia obiekty które marker uznał za nieużywane

Epoki

Czas działania programu jest podzielony na epoki. Podczas każdej z nich w osobnych wątkach uruchomione zostają poszczególne elementy garbage collectora (muatator, marker i sweeper). Dodatkowo każdej epoce jest przyporządkowany jeden z trzech kolorów: COLOR(epoch) = epoch mod 3.

Przydzielanie pamięci

Pamięć jest przydzielana przy użyciu free lists. Jest to lista wskazujących na siebie wolnych bloków pamięci. Dzięki temu, że każdy wolny blok zawiera wskaźnik na następny, nie ma potrzeby tworzenia dodatkowych struktur danych do przechowywania tego typu informacji. Każdy przydzielany w ten sposób obiekt jest oznaczony kolorem aktualnie trwającej epoki.

Marker

W każdej epoce marker porusza się po wskazujących na siebie obiektach. Jeżeli kolor obiektu jest inny niż kolor aktualnej epoki marker uaktualnia go a następnie rekursywnie przegląda wszystkie bloki na które wskazuje dany obiekt. Gdy marker zakończy działanie wszystkie używane obiekty mają kolor danej epoki.

Warto zauważyć że mutator i marker w żaden sposób nie wpływają na swoje działanie. Mutator oznacza wszystkie nowe obiekty kolorem aktualnej epoki, a ten jest przez markera ignorowany. Istotny jest także fakt, że marker nigdy nie spotka bloku oznaczonego kolorem innym niż kolor aktualnej, bądź poprzedniej epoki.

Sweeper

Sweeper przegląda listę przydzielonych bloków w poszukiwaniu obiektów oznaczonych kolorem epoki COLOR(epoch-2). Jeśli natrafi na taki obszar pamięci to jest on zwalniany. Jest to operacja całkowicie bezpieczna ponieważ ani marker ani mutator nie mają dostępu do obiektów oznaczonych takim kolorem.

W przypadku natrafienia przez sweeper bloków o innym kolorze są one ignorowane, ponieważ wciąż mogą być w użyciu przez pozostałe elementy programu.

Zakończenie epoki

Gdy sweeper i marker zakończą pracę program przechodzi do kolejnej epoki o nowym kolorze i cały proces zaczyna się od nowa. Dzięki całkowitej niezależności poszczególnych elementów od siebie mutator, marker i sweeper mogą działać równolegle bez potrzeby wprowadzania blokad, co korzystnie wpływa na wydajność systemu.

Podsumowanie

Obecnie bardzo wiele języków programowania oferuje wbudowany garbage collector dlatego rozwój algorytmów tego typu nie jest niczym dziwnym. Dlatego taż warto dowiedzieć się na jakiego rodzaju rozwiązania można w tej dziedzinie natrafić.