Algorytm mark-compact

Algorytm mark-compact – rodzaj algorytmu odśmiecania pamięci używany do odzyskiwania niedostępnej pamięci. Algorytmy rodzaju mark-compact mogą być traktowane jako połączenie algorytmu mark-sweep i algorytmu kopiowania Cheneya. Na początku oznakowane są dostępne obiekty a następnie faza kompaktowania przenosi osiągalne (oznaczone) obiekty w kierunku początku obszaru sterty. Kompaktujące odśmiecanie pamięci jest wykorzystywane przez Common Language Runtime firmy Microsoft i Glasgow Haskell Compiler.

Algorytmy

Po zaznaczeniu żywych obiektów w stercie w taki sam sposób jak w algorytmie mark-sweep sterta często będzie pofragmentowana. Celem algorytmów mark-compact jest przesunięcie żywych obiektów w pamięci tak by wyeliminować fragmentację. Wyzwaniem jest poprawnie zaktualizować wszystkie wskaźniki do przemieszczonych obiektów, z których większość będzie miała nowe adresy pamięci po kompaktowaniu. Kwestia obsługi aktualizacji wskaźnika jest traktowana w różny sposób.

Kompaktowanie oparte na tabeli

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

Kompaktowanie działa od dna sterty (niskie adresy) w górę (wysokie adresy). Gdy napotykane są żywe (czyli z oznaczeniem) obiekty, są przenoszone do pierwszego dostępnego niskiego adresu, a rekord jest dołączany do tablicy przerw dotyczącej informacji o relokacji. Dla każdego żywego obiektu rekord w tabeli przerw składa się z oryginalnego adresu obiektu przed zagęszczaniem i różnicą między oryginalnym adresu i nowy adres po zagęszczeniu. Tabela przerw jest przechowywany na stercie, który jest kompaktowany, ale w miejscu, które jest oznaczone jako niewykorzystane. Aby zapewnić, że zagęszczenie zawsze się uda, minimalny rozmiar obiektu na stercie musi być większy lub taka sam jak rekordu tabeli przerwy.

Wraz z postępem zagęszczania przeniesione obiekty są kopiowane w kierunku dna. Ostatecznie obiekt będzie musiał być kopiowany do przestrzeni zajmowanej przez tablicę przerw, która teraz musi być przeniesiona gdzie indziej. Te ruchy tabeli przerw, (zwane przez autorów. toczeniem się tabeli) powodują, że rekordy relokacji stają się nieuporządkowane, wymagające aby tabela przerw została posortowana gdy zakończy się zagęszczanie. Koszt sortowania tabeli przerw wynosi O (n log n), gdzie n jest liczbą żywych obiektów wykrytych na etapie zaznaczania.

Wreszcie, rekordy relokacji tabeli przerw służą do dopasowania pola wskaźników wewnątrz przeniesionych obiektów. Żywe obiekty są badane pod kątem wskaźników, which może być sprawdzone w posortowanej tablicy przerw rozmiaru n w czasie O (log n) w ogólnym czasie O (n log n). Wskaźniki te są następnie korygowane o ilość określoną w tabeli relokacji.

Algorytm LISP2

W celu uniknięcia złożoności O (n log n), algorytm LISP2 wykorzystuje 3 różne przejścia sterty. Dodatkowo obiekty sterty muszą mieć osobny slot na przekierowujący wskaźnik który nie jest używany poza odśmiecaniem pamięci.

Po standardowym zaznaczaniu, algorytm postępuje w 3 następujących przebiegach:

1. Wyznacz miejsce przekierowania żywych obiektów.
   • Śledź wskaźniki wolnego miejsca i żywych obiektów i zainicjuj oba na początek sterty.
   • Jeśli wskaźnik żywych obiektów wskazuje żywy obiekt, zaktualizuj przekierowujący wskaźnik tego obiektu na bieżącą wartość wskaźnika wolnego miejsca i zwiększ wskaźnik wolnego miejsca zgodnie z wielkością obiektu.
   • Przenieś wskaźnik żywych obiektów do następnego obiektu
   • Kończy się, gdy wskaźnik żywych obiektów dojdzie do końca sterty.
2. Aktualizuj wszystkie wskaźniki
   • Dla każdego żywego obiektu, aktualizuj jego wskaźniki zgodnie z przekierowującymi wskaźnikami obiektu na który wskazują.
3. Przesuń obiekty
   • Dla każdego żywego obiektu, przenieść jego dane na jego przekierowywane położenia.

Ten algorytm ma złożoność O (n) od wielkości sterty; ma niższą złożoność niż podejście oparte na tablicy, ale w metodzie z użyciem tabeli n jest wielkością jedynie użytego miejsca a nie całej sterty jak w algorytmie LISP2. Jednak algorytm LISP2 jest prostszy do implementacji.