Mark And Sweep Nedir - Nesne Olduğu Yerde Bırakılır

Giriş

Mark-Sweep yönteminde nesne olduğu yerde bırakılır. Aynı bloktaki nesneler arasında boşluklar oluşur.

Mark Nedir Sweep Nedir?
Açıklaması şöyle.

Mark-and-sweep algorithms work in two phases:
- Mark Phase: Every time an object is created, its mark bit is set to 0 (false). In the Mark Phase, the mark bit of every ‘reachable’ object is changed and set to 1 (true).

- Sweep Phase: All those objects whose mark bit is still set to 0 (false) after the Mark Phase are unreachable objects and hence are garbage collected and freed from memory by the algorithm.

Mark Phase

Sadece erişilebilir olan nesneri 1 veya true olarak işaretler. Mark aşamasında sadece canlı yani erişilebilir olan nesneler dolaşılıyor ve bu nesneler işaretleniyor. Tüm graph dolaşılmadığı için sweep aşamasına göre maliyeti biraz daha düşüktür. Açıklaması şöyle

Marking doesn’t reclaim the garbage, it only identifies the alive objects. And this is relatively a fast cycle — we visit only a small sub-set of the alive data. In contrast, the sweep phase has to traverse the whole heap.

Sweep Phase - Nesneyi Gerçekten Graph'tan Silme Aşaması

Bu aşamaya süpürme aşaması diyelim. Şu işleri yapar:

1. Canlı olan nesnelerin bitini tekrar 0 yapar. 

2. Canlı olmayan nesneleri süpürür.

Kod olarak şuna benzer. Süpürme aşamasında tüm graph dolaşılmak zorundadır. Bu yüzden Mark aşamasına göre maliyeti daha yüksektir.

//Sweep phase.
void sweep() {
  auto it = traceInfo.cbegin();
  while (it != traceInfo.cend()) {
    if (it->second->marked) {        // (1) Nesne halen erişilebilir
      it->second->marked = false;
      ++it;
    } else {
      it = traceInfo.erase(it);
      delete it->first;              // (2) Nesne erişilemez
    }
  }
}

Açıklaması şöyle

So here in (1) we check if an object is alive, that is, its mark-bit is set. In this case we reset the mark-bit (for the future collection cycles), and proceed further, keeping the object on the heap.

Otherwise, the object wasn’t visited during the trace, and it means it’s a garbage, so in (2) we immediately reclaim it.

Concurrent Mark-Sweep Nedir?

Klasik Mark-Sweep yöntemine yapılan bir iyileştirmedir. 

Sıkıntılar

Açıklaması şöyle. Bloktaki nesneler arasındaki boşluklar heap fragmentation denilen sıkıntıya sebep oluyor.

In addition, the Mark-Sweep being a non-moving collector, has an issue of heap fragmentation,...

Bu yüzden Concurrent Mark-Sweep genellikle Old Generation için kullanılır. 

Ayrıca bu sıkıntıyı aşmak için Mark-Compact ve Copying algoritmaları geliştirildiler.