루트 집합은 도달 가능한 객체와 쓰이지 않는 할당을 나눈다.
명시적인 힙 그래프를 루트에서 추적해 참조되는 객체를 한 번씩 표시하고 어느 루트에서도 닿지 않는 할당을 분류할 수 있습니다.
참조가 그래프를 이룰 때 저장소 관리자는 어떤 할당을 보존해야 할까요?
- 힙 객체를 나가는 참조를 가진 식별자로 나타내기
- 명시적인 루트 집합에서 시작하는 모든 경로 추적하기
- 그래프에 순환이 있을 때 표시된 객체의 재방문 멈추기
- 루트 추적 결과를 바탕으로 도달 불가능한 할당 구분하기
mark는 자식을 따라가기 전에 객체 식별자를 추가합니다. mark-list는 형제 참조를 거치며 늘어나는 표시 집합을 전달하므로, 여러 경로로 도달한 객체도 한 번만 나타납니다. 첫 번째 힙은 garbage와 orphan을 할당된 상태로 남기지만 루트 a에서는 도달할 수 없습니다.
두 번째 힙은 a에서 b와 c를 거쳐 다시 a로 돌아오는 순환을 포함합니다. contains?는 재방문을 멈추고 mark-roots는 x에서 두 번째 순회를 시작합니다. 그런 다음 unreachable은 모든 할당을 훑어 표시 집합 밖의 dead만 분류합니다. 이 수업은 루트 집합을 기준으로 객체의 도달 가능성을 추적하고 분류하는 과정을 모델링합니다.
- 출력
- —
- 값
- —
- 진단
- —
첫 번째 프로그램은 ((a b d c) (garbage orphan))을 반환합니다. 두 번째 프로그램은 ((a b c x y) (dead))를 반환합니다.
첫 번째 실행에서는 c로 돌아오기 전에 루트에서 b를 거쳐 d로 이어지는 경로를 따라간 뒤 힙 스캔이 표시된 ID를 제외하는 모습을 관찰하세요. 두 번째 실행에서는 c에서 a로의 순환을 멈추는 contains? 적중과 이후 루트 x에서 시작하는 순회를 찾으세요.
프로그램을 수정하고 결과를 비교해 보세요.
루트 a를 유지한 채 orphan에서 a로 가는 참조를 추가하세요. garbage와 orphan이 도달 가능해지는지 예측하세요.
힌트 보기
도달 가능성은 루트에서 바깥쪽으로 나가는 참조를 따릅니다. 도달 불가능한 객체에서 루트 쪽으로 향하는 참조가 있다고 해서 해당 객체가 도달 가능해지지는 않습니다.