Algorytm mark-compact

Algorytm mark-compact to typ algorytmu zajmującego się odśmiecaniem pamięci, który służy do odzyskiwania nieużywanej pamięci. Algorytmy te można postrzegać jako połączenie algorytmu mark-sweep oraz algorytmu kopiowania Cheneya. Proces rozpoczyna się od oznaczenia dostępnych obiektów, a następnie w fazie kompaktowania przenoszone są osiągalne (czyli oznaczone) obiekty w stronę początku obszaru sterty. Kompaktowe odśmiecanie pamięci znajduje zastosowanie w Common Language Runtime firmy Microsoft oraz w Glasgow Haskell Compiler.

Algorytmy

Po zaznaczeniu żywych obiektów w stercie, podobnie jak w algorytmie mark-sweep, sterta często staje się pofragmentowana. Głównym celem algorytmów mark-compact jest przesunięcie żywych obiektów w pamięci, aby zredukować fragmentację. Wyzwaniem jest prawidłowe zaktualizowanie wszystkich wskaźników do przeniesionych obiektów, które zazwyczaj będą miały nowe adresy pamięci po procesie kompaktowania. Kwestia aktualizacji wskaźników jest rozwiązywana na różne sposoby.

Kompaktowanie oparte na tabeli

Algorytm oparty na tabeli został po raz pierwszy zaprezentowany przez Haddona i Waite’a w 1967 roku. Utrzymuje on względne rozmieszczenie żywych obiektów w stercie i wymaga jedynie stałej wielkości nadwyżki pamięci.

Kompaktowanie odbywa się od dolnej części sterty (niskie adresy) do górnej (wysokie adresy). Gdy napotkane są żywe (czyli oznaczone) obiekty, są one przenoszone do pierwszego dostępnego niskiego adresu, a rekord dotyczący relokacji jest dodawany do tablicy przerw. Dla każdego żywego obiektu, rekord w tabeli przerw zawiera oryginalny adres obiektu przed kompaktowaniem oraz różnicę między oryginalnym a nowym adresem po kompaktowaniu. Tabela przerw jest przechowywana w stercie, która jest kompaktowana, ale w obszarze oznaczonym jako niewykorzystany. Aby zapewnić, że kompaktowanie zawsze się powiedzie, minimalny rozmiar obiektu w stercie musi być większy lub równy rozmiarowi rekordu w tabeli przerw.

W miarę postępu kompaktowania przeniesione obiekty są kopiowane w kierunku dolnej części sterty. Ostatecznie obiekt będzie musiał być skopiowany do obszaru zajmowanego przez tablicę przerw, która musi być wtedy przeniesiona w inne miejsce. Ruchy tabeli przerw (nazywane przez autorów „toczeniem się tabeli”) prowadzą do nieuporządkowania rekordów relokacji, co wymaga ich posortowania po zakończeniu kompaktowania. Koszt sortowania tabeli przerw wynosi O(n log n), gdzie n to liczba żywych obiektów wykrytych podczas etapu oznaczania.

Na koniec, rekordy relokacji w tabeli przerw służą do aktualizacji wskaźników wewnątrz przeniesionych obiektów. Żywe obiekty są sprawdzane pod kątem wskaźników, które mogą być weryfikowane w posortowanej tabeli przerw o rozmiarze n w czasie O(log n), co daje łączny czas O(n log n). Wskaźniki te są następnie korygowane zgodnie z wartościami określonymi w tabeli relokacji.

Algorytm LISP2

Aby uniknąć złożoności O(n log n), algorytm LISP2 wykorzystuje trzy różne przejścia przez stertę. Dodatkowo, obiekty w stercie muszą mieć osobny slot na przekierowujący wskaźnik, który nie jest używany poza procesem odśmiecania pamięci.

Po standardowym oznaczeniu, algorytm realizuje trzy następujące kroki:

Wyznaczenie miejsca przekierowania dla żywych obiektów.
Śledzenie wskaźników do wolnego miejsca i żywych obiektów oraz zainicjowanie obu na początku sterty.
Jeśli wskaźnik żywych obiektów wskazuje na żywy obiekt, aktualizuje się przekierowujący wskaźnik tego obiektu na bieżącą wartość wskaźnika wolnego miejsca oraz zwiększa wskaźnik wolnego miejsca zgodnie z wielkością obiektu.
Przeniesienie wskaźnika żywych obiektów do kolejnego obiektu.
Proces kończy się, gdy wskaźnik żywych obiektów dotrze do końca sterty.

Aktualizowanie wszystkich wskaźników polega na tym, że dla każdego żywego obiektu aktualizowane są jego wskaźniki zgodnie z przekierowującymi wskaźnikami obiektów, na które wskazują.

Przenoszenie obiektów polega na tym, że dla każdego żywego obiektu jego dane są przesuwane na odpowiednie przekierowywane miejsca.

Ten algorytm ma złożoność O(n) w odniesieniu do wielkości sterty; jest mniej złożony niż podejście oparte na tabeli, ale w metodzie z użyciem tabeli n odnosi się jedynie do wielkości używanej pamięci, a nie całej sterty, jak ma to miejsce w algorytmie LISP2. Niemniej jednak algorytm LISP2 jest prostszy do implementacji.