Odśmiecanie z algorytmem Mark and Sweep

Aplikacja musi często alokować zasoby, czyli pamięć, połączenie z bazą danych, gniazda, uchwyty plików itp. Wysyła ona do systemu operacyjnego żądanie o te zasoby, a w momencie, w którym aplikacja kończy z przydzielonym zasobem, musi koniecznie zwrócić to samo systemowi operacyjnemu. Na przykład, jeśli istnieje program, który używa listy do przechowywania danych, powinien on zwolnić pamięć przydzielaną dynamicznie, gdy węzeł zostanie usunięty z listy.

Jeśli pamięć nie zostanie zwolniona, spowoduje to wyciek pamięci i zmarnowanie zasobów. Zobaczmy na prawdziwym przykładzie, w jaki sposób alokowanie pamięci bez jej zwalniania powoduje marnotrawstwo zasobów i może prowadzić do problemów z wydajnością.

struct Node {
  Node(int value) {
    this.value = value;
    this.next = nullptr;
  }
  int value; 
  struct Node* next;
}

Node* removeNode(int value, Node* head) {
  Node* newHead = head;
  if (head->value == value) {
    newHead = head->next;
    delete head;
  }
    
  while(head->next != nullptr && head->next->value != value)
    head = head->next;
  if(head->next) {
    Node* temp = head->next;
    head->next = head->next->next;
    delete temp;
  }
  return newHead;
}

int main() {
  Node* head = new Node(5); 
  head->next = new Node(6);
  head->next->next = new Node(7);
  
  removeNode(7, head);
  removeNode(6, head);
  
  return 0;
}

Powyższy kod pokazuje listę z wyciekiem pamięci. Gdy węzeł zostanie z niej usunięty, to nie wywoła na węźle delete, tylko pozbędzie się wskaźnika do tego węzła. Oto poprawka: 

Naprawiony wyciek pamięci

Weźmy na przykład poniższy kod, który stale alokuje pamięć, ale jej nie zwalnia.

#include <iostream>
using namespace std;

struct Node {
  int value;
  struct Node* next;
  Node(int value) {
    this.value = value;
  }  
};
int main(void) {
        while(true)
        Node* node = new Node();
        return 0;

}

Powyższy program został skompilowany i uruchomiony przy użyciu g++. Poniższe rzuty ekranu pokazują listę procesów posortowanych według procentu zużycia pamięci w ciągu 30 sekund po uruchomieniu pliku binarnego (a.out) zawierającego powyższy kod.

Początkowo zużycie pamięci, które wynosiło 5%, wzrasta do 9,2%, a następnie do 13,7% (ostatnie zdjęcie). Jak widać, procentowe zużycie pamięci rośnie, jeśli obiekty, które nie są już używane, nie zostaną usunięte, co ostatecznie powoduje crash lub spowolnienie innych aplikacji w systemie z powodu braku pamięci.

Odśmiecanie

Odśmiecanie to technika używana do usuwania śmieci. Śmieci oznaczają zbiór obiektów, które nie są już używane oraz nie będą potrzebne. W C to programista jest odpowiedzialny za alokację i dealokację obiektów. Język ten nie zapewnia automatycznego pozbywania się niepotrzebnych obiektów. Dlatego dla każdego malloc() lub calloc() powinna istnieć funkcja free() wywoływana po usunięciu obiektu. Łatwo tutaj o błąd, ponieważ programista musi cały czas śledzić obiekty, które są alokowane i zwalniane.

Podobnie jak C, C++ również nie obsługuje automatycznego odśmiecania, ale ułatwia programistom automatyczne zwolnienie zasobów, udostępniając taką semantykę, jak RAII, Smart Pointers oraz zliczenie referencji. Podstawową koncepcją w RAII i Smart Pointers jest to, że zasoby są pozyskiwane w konstruktorze i uwalniane w destruktorze. Język gwarantuje, że destruktory są wywoływane, gdy obiekt wyjdzie z zasięgu, a pamięć jest zwalniana w momencie, gdy obiekt zostanie zniszczony.

struct Node {
  int value; 
  Node* next;
}

class AutoPtr<T> {
  AutoPtr(T* node) {
    this.node = node;
  }
  ~AutoPtr() {
    delete node;
  }
private:
  T* node;
}
void allocateMemory() {
  AutoPtr<Node> autoPtr = new AutoPtr(new Node());
}
int main(void) {
  while(true)
    allocateMemory();
}

W powyższym fragmencie kodu autoPtr wyjdzie z zasięgu, gdy funkcja replaceateMemory() zakończy wykonywanie. Obiekt, do którego odwołuje się autoPtr, zostanie usunięty przez swój destruktor. Uniknęliśmy tutaj wycieku pamięci. Techniki takie jak zliczanie referencji śledzą liczbę referencji do konkretnego obiektu. Ich liczba jest zwiększana dla każdej alokacji lub przypisaniu, a gdy liczba referencyjna osiągnie zero, obiekt jest usuwany.

Java zapewnia automatyczny mechanizm odśmiecania, dzięki czemu programiści nie muszą śledzić alokacji i dealokacji obiektów tak jak w C, ani używać wrapperów (takich jak autoPtr) do zarządzania obiektami podczas działania programu tak jak w C++. W Javie Garbage Collector jest częścią środowiska wykonawczego i działa osobno, dzięki czemu śledzi obiekty, które są osiągalne, i usuwa te, które są poza zasięgiem.

Algorytm Mark & Sweep

Algorytm ten działa w dwóch fazach:

• Faza Mark— tutaj obiekty osiągalne z poziomu programu są oznaczone jako osiągalne. Garbage Collector rozpocznie przejście od wszystkich referencji w programie (na stosie, rejestrach, zmiennych statycznych) i odwiedzi wszystkie wewnętrzne referencje w sposób nazwany Depth First Search (DFS), oznaczając przy tym obiekty jako reachable. Każdy alokowany obiekt na stercie ma flagę, nazwijmy ją marked, ustawianą na false, w momencie alokacji. Podczas fazy mark flaga ta zmienia się na true, jeśli obiekt jest osiągalny.
• Faza Sweep— tutaj usuwa wszystkie obiekty, które nie zostały oznaczone w fazie Mark. Nieosiągalne obiekty są usuwane, dzięki czemu program może później zaalokować więcej obiektów.

Przyjrzyjmy się prostemu przykładowi tego algorytmu.

public class Main {
    public static void main(String[] args) {
        Employee e = new Employee("Jerry", new City("London"));
        e = new Employee("Abraham", new City("San Fransisco"));
        e = new Employee("Tom", new City("NewYork"));
    }
    private static class City {
        private String city;

        public City(String city) {
            this.city = city;
        }

        public String getCity() {
            return city;
        }

    }
    private static class Employee {
        private String firstName;
        private City city;

        public Employee(String firstName, City city) {
            this.firstName = firstName;
            this.city = city;
        }

        public String getFirstName() {
            return firstName;
        }

        public City getCity() {
            return city;
        }
    }
}

W powyższym przykładzie definiujemy dwie klasy Employee oraz City. Dalej mamy jedną referencję e w głównej funkcji. Tworzymy 3 różne obiekty Employee i aktualizujemy referencję za każdym razem, gdy tworzymy nowy obiekt.

Faza Mark

Jak pisałem wcześniej, w fazie Mark Garbage Collector szuka referencji w stosie, rejestrze lub zmiennych statycznych. W powyższym przypadku znajdzie on referencję do obiektu Employee z firstName „Tom” po uruchomieniu wiersza 5. Garbage Collector poszuka jeszcze wszystkich obiektów osiągalnych z obiektu Employee. W tym przypadku mamy obiekt City o nazwie „New York” oraz obiekt String (FirstName) o nazwie „Tom”.

Garbage Collector analizuje rekurencyjnie każdą referencję. Za każdym razem, gdy Garbage Collector napotka obiekt osiągalny przez referencję, flaga marked jest ustawiana na wartość true. Pozostałe dwa obiekty będą miały domyślnie zaznaczoną flagę false podczas inicjalizacji.

Koniec fazy Mark

Faza Sweep

Garbage Collector będzie liniowo iterował wszystkie wpisy w stercie i znajdzie wszystkie obiekty, który są nieosiągalne lub mają flagę marked o wartości false. Spowoduje to usunięcie wszystkich takich obiektów, a program będzie kontynuować wykonanie.

W tym przykładzie dwa obiekty Employee o nazwach „Jerry” i „Abraham” zostaną usunięte ze sterty wraz z odpowiadającymi im obiektami City i firstName. 

Koniec fazy Sweep

// Pseudo Code for Mark 
Mark(root)
If root.marked = false then
root.marked = true
For each v root.references()
Mark(v)

Powyższy fragment kodu zawiera pseudokod dla fazy Mark. Wykonuje przejście DFS po wszystkich wewnętrznych referencjach, a następnie odwraca flagę marked.

Sweep()
For each object in heap
If object.marked = true then
object.marked = false
else
heap.release(object)

Faza Sweep liniowo skanuje stertę i zwalnia obiekty, które mają flagę marked o wartości false.

Zalety algorytmu Mark i Sweep

• Brak dodatkowych narzut
• Algorytm dobrze obsługuje cykliczne referencje i nigdy nie skutkuje nieskończoną pętlą

Wady Mark i Sweep

• Podczas wykonywania algorytmu GC normalne wykonywanie programu jest zawieszane
• Po wielu cyklach Mark & Sweep, osiągalne obiekty są rozdzielane przez małe nieużywane segmenty pamięci, co prowadzi do fragmentacji