Mark and Sweep
মার্ক অ্যান্ড সুইপ
দুই-phase tracing GC — আগে roots থেকে সব reachable object-এ mark, তারপর পুরো heap scan করে unmarked মুক্ত করা।
mark: roots থেকে DFS — প্রতিটা পৌঁছানো object-এর mark bit বসে
sweep: heap-এর উপর linear scan — mark নেই মানে free, mark আছে মানে bit reset- সুবিধা: cycle ঠিকভাবে মোকাবেলা করে, object জায়গায় থাকে (cache-friendly pointer অপরিবর্তিত)
- দাম: sweep-এ পুরো heap ছোঁয় — heap বড় হলে pause বড়, live কম হলেও
- Free block পাশাপাশি হলে coalesce না করলে external fragmentation জমে
- Mark phase-এ recursion না করে explicit worklist — deep structure-এ stack overflow এড়াতে