루트 집합은 도달 가능한 객체와 쓰이지 않는 할당을 나눈다.
명시적인 힙 그래프를 루트에서 추적해 참조되는 객체를 한 번씩 표시하고 어느 루트에서도 닿지 않는 할당을 분류할 수 있습니다.
참조가 그래프를 이룰 때 저장소 관리자는 어떤 할당을 보존해야 할까요?
- Represent heap objects as identifiers with outgoing references
- Trace every path starting from an explicit root set
- Stop revisiting marked objects when the graph contains a cycle
- Distinguish unreachable allocations without reclaiming them in this model
mark adds an object identifier before following its children. mark-list carries the growing marked set across sibling references, so an object reached through several paths appears once. The first heap leaves garbage and orphan allocated but unreachable from root a.
The second heap contains a cycle from a through b and c back to a. contains? stops the revisit, while mark-roots starts a second traversal from x. unreachable then scans every allocation and classifies only dead outside the marked set. This lesson models tracing and classification, not memory reclamation itself.
(begin
(define (contains? item items)
(cond ((null? items) #f)
((eq? item (car items)) #t)
(else (contains? item (cdr items)))))
(define (children object heap) (cdr (assoc object heap)))
(define (mark object heap marked)
(if (contains? object marked)
marked
(mark-list (children object heap) heap (cons object marked))))
(define (mark-list objects heap marked)
(if (null? objects)
marked
(mark-list (cdr objects) heap
(mark (car objects) heap marked))))
(define (unreachable heap marked)
(cond ((null? heap) '())
((contains? (car (car heap)) marked)
(unreachable (cdr heap) marked))
(else
(cons (car (car heap)) (unreachable (cdr heap) marked)))))
(define heap '((a b c) (b d) (c) (d) (garbage orphan) (orphan)))
(define marked (mark 'a heap '()))
(list (reverse marked) (unreachable heap marked)))- 출력
- —
- 값
- —
- 진단
- —
The first program returns ((a b d c) (garbage orphan)). The second returns ((a b c x y) (dead)).
In the first run, follow the root through b to d before returning to c, then watch the heap scan reject marked IDs. In the second run, find the contains? hit that stops the c-to-a cycle and the later traversal from root x.
힌트를 보기 전에 프로그램을 바꿔 보세요.
Add a reference from orphan to a while keeping root a. Predict whether garbage and orphan become reachable.
힌트 하나 보기
Reachability follows references outward from roots. A reference from an unreachable object toward a root does not make that object reachable.