도달 가능성 - 닿을 수 있으면 살아 있다

앞 글의 고리는 방문 앞에서 숫자만 봐서는 안 풀린다. 방 하나가 아니라 건물 전체를 봐야 풀린다.

세는 대신 따라가 본다

관리인이 방식을 바꾼다. 숫자판을 보는 대신 로비에서 출발해 건물을 걸어 다닌다.

로비에는 지금 진행 중인 회의들의 안내판이 있다. 안내판이 가리키는 방으로 가 보고, 그 방 안에 다른 방을 가리키는 쪽지가 있으면 거기도 가 본다. 그렇게 갈 수 있는 데를 전부 다녀 본 다음, 한 번도 안 들른 방을 전부 비운다.

메모리도 똑같다. 정해진 출발점에서 참조를 타고 갈 수 있는 객체는 살아 있다고 본다. 못 가면 죽은 것으로 보고 회수한다. 이걸 도달 가능성(reachability) 이라 한다.

핵심은 판단의 범위가 바뀌었다는 데 있다. 세는 방식은 자기 문 앞만 봤다. 이 방식은 건물 전체를 한 번에 본다.

로비가 어디인가

그럼 출발점은 어디인가. 이 출발점들을 루트(root) 라고 부르고, 대충 이런 것들이다.

• 지금 실행 중인 함수들의 지역변수 - 스택에 살아 있는 것들이다. 지금 쓰는 중이니 당연히 루트다
• 스레드마다 하나씩 - 스레드는 자기 스택을 따로 갖는다. 살아 있는 스레드가 여럿이면 로비도 여럿인 셈이다
• 전역 변수와 정적 필드 - 프로그램이 사는 내내 있는 것들이다

루트의 공통점은 **“찾아갈 필요 없이 이미 손에 있는 것”**이다. 프로그램이 지금 이 순간 곧바로 쓸 수 있는 것들이 로비고, 나머지는 전부 로비에서 몇 걸음 걸어야 닿는다.

여기서 이 방식의 성격이 나온다. 살아 있음은 객체가 자기 안에 갖고 있는 성질이 아니다. 로비와의 관계다. 같은 객체가 어제는 살아 있었고 오늘은 죽은 것이 되는데, 객체는 하나도 안 바뀌었다. 바뀐 건 루트에서 거기까지 가는 길이다.

표시하고, 쓸어담는다

가장 기본적인 절차는 두 단계다. 이름도 그대로 표시하고 쓸어담기(mark and sweep) 다.

표시(mark) - 루트에서 출발해 참조를 따라 걸어 다니면서, 들르는 객체마다 “다녀갔다”고 표시를 남긴다. 이미 표시된 곳에 또 오면 되돌아간다.

쓸기(sweep) - 힙을 처음부터 끝까지 훑으면서 표시가 없는 것을 전부 회수한다. 그리고 표시를 지워 다음 회수를 준비한다.

두 단계의 성격이 정반대라는 게 재미있는 점이다. 표시는 살아 있는 것만 건드린다. 죽은 객체는 아예 안 만난다. 쓸기는 힙 전체를 훑는다.

여기서 실무에 바로 쓰이는 감각이 하나 나온다. 표시에 드는 시간은 죽은 객체가 몇 개든 상관없다. 살아 있는 것이 많을수록 오래 걸린다. 쓰레기가 많아서 회수가 느린 게 아니라, 살아남는 것이 많아서 느리다.

고리가 저절로 풀린다

세는 방식이 못 풀던 것을 이 방식은 아무 노력 없이 푼다.

서로를 가리키는 두 객체는 여전히 서로를 가리키고 있다. 카운트로 치면 각각 1이다. 그런데 로비에서 출발해서는 거기까지 갈 길이 없다. 표시 단계에서 한 번도 안 들르니 표시가 안 붙고, 쓸기 단계에서 그대로 회수된다.

고리를 찾아내는 코드를 따로 짠 게 아니다. 질문을 바꿨더니 고리가 문제가 아니게 된 것이다.

• “이걸 가리키는 곳이 있나” → 서로 가리키면 답이 예다
• “여기까지 갈 수 있나” → 서로 가리켜 봐야 바깥에서 못 오면 답이 아니오다

섬은 안에서 아무리 서로를 붙잡고 있어도 섬이다. 이 방식이 오늘날 대부분의 언어가 택한 길인 이유가 여기 있다.

”쓸 것”이 아니라 “닿는 것”이다

여기서 반드시 갈라 둘 것이 있다. 회수기가 판단하는 건 “앞으로 쓸 것인가”가 아니다. 그건 아무도 알 수 없다. 회수기가 아는 건 “지금 닿을 수 있는가” 하나다.

둘은 대개 겹치지만 항상은 아니다. 그리고 어긋나는 쪽이 늘 한 방향이다.

오른쪽 위 칸이 비어 있는 게 중요하다. 쓸 건데 회수되는 일은 없다. 회수기는 이 점에서 안전하다.

문제는 왼쪽 아래다. 앞으로 절대 안 쓸 객체인데 어딘가에서 여전히 닿을 수 있으면, 회수기는 그걸 살아 있는 것으로 본다. 회수기가 게을러서가 아니라 규칙대로 판단한 것이다.

이 칸이 이 시리즈의 마지막 글 전체다. 자동 회수가 있는 언어에서도 메모리가 새는 이유가 통째로 여기서 나온다.

쓸고 나면 자리가 조각난다

쓸기가 끝난 힙을 떠올려 보자. 살아남은 것들 사이사이에 회수된 자리가 구멍처럼 뚫려 있다. 빈 자리를 다 합치면 넉넉한데 연속으로 붙은 자리는 얼마 안 된다.

이 상태에서 큰 객체를 하나 만들려 하면 들어갈 데가 없다. 전체로는 남는데 한 덩어리로는 모자란 것이다. 이걸 단편화(fragmentation) 라 한다.

그래서 많은 회수기가 한 단계를 더 한다. 살아남은 것들을 한쪽으로 몰아 붙이는 것이다. 회의실로 치면 흩어져 쓰던 팀들을 앞쪽 방으로 옮겨 모아 뒤쪽을 통째로 비우는 일이다.

이러면 두 가지가 좋아진다. 빈 자리가 한 덩어리로 남아 큰 객체도 들어가고, 새 자리를 얻는 일이 아주 싸진다. 빈 자리 목록을 뒤질 필요 없이 끝을 가리키는 표시만 밀면 되기 때문이다.

대가도 분명하다. 객체를 실제로 옮기므로 그 객체를 가리키던 모든 참조를 다 고쳐야 한다. 그리고 옮기는 도중에 프로그램이 그 객체를 건드리면 안 된다. 이 “건드리면 안 되는 시간”이 다음 글의 주제다.

세는 방식과의 거래

두 방식을 나란히 놓으면 무엇을 주고 무엇을 받았는지가 보인다.

공짜로 얻은 게 아니다. 고리를 푸는 대신 즉시성을 잃었다. 객체가 죽는 순간과 그 자리가 돌아가는 순간이 갈라졌고, 그 사이에 죽은 객체가 힙을 차지하고 있다. 그래서 자동 회수를 쓰는 프로그램은 대체로 필요한 것보다 넉넉한 힙을 쥐고 산다.

한 가지 더 잃은 것이 있다. 객체가 사라지는 시점에 무언가를 하는 코드를 믿을 수 없게 됐다. 파일을 닫거나 연결을 반납하는 일을 “객체가 회수될 때 하자”고 짜 두면, 그게 언제 도는지 아무도 모른다. 영영 안 돌 수도 있다. 그래서 이 시리즈가 거듭 말한 것처럼 메모리가 아닌 자원은 여전히 명시적으로 닫아야 한다.

실무에서: 무엇이 붙들고 있나를 찾는다

도달 가능성을 알면 메모리 문제를 보는 눈이 바뀐다. 질문이 “왜 안 치워지나”에서 “루트에서 여기까지 무슨 길이 있나”로 바뀌기 때문이다. 그리고 그 길은 실제로 볼 수 있다.

• 힙 덤프를 뜬다. 어느 시점의 힙을 통째로 파일에 받아 두는 것이다. 안에는 객체들과 그 사이의 참조가 전부 들어 있다
• 참조 경로를 본다. 분석 도구가 “이 객체가 루트에서 어떤 참조를 타고 닿는지”를 그려 준다. 답이 대개 여기서 나온다. 잡고 있던 게 어떤 정적 필드인지, 어떤 컬렉션인지가 그 경로에 찍힌다
• 혼자 붙들고 있는 크기를 본다. 어떤 객체를 지웠을 때 같이 사라질 것들의 합계를 재는 값이 있다. 목록 자체는 작아도 그 목록이 붙들고 있는 것이 클 수 있어서, 크기 순으로 보면 범인이 위로 올라온다
• 두 시점을 비교한다. 한 번 뜬 덤프로는 “원래 많은 것”과 “늘고 있는 것”이 구별이 안 된다. 시간을 두고 두 번 떠서 늘어난 쪽을 본다

같은 판단이 데이터베이스에도 있다. 옛 버전을 언제 치울지를 정할 때, DB는 “아직 그 버전을 볼 수 있는 트랜잭션이 하나라도 있나”를 본다. 아무도 볼 수 없게 된 것만 치운다 - 도달 가능성과 같은 모양의 질문이다.

정리

• 세는 대신 정해진 출발점(루트)에서 참조를 따라가 본다. 닿으면 살아 있고, 못 닿으면 회수한다.
• 루트는 지금 곧바로 손에 있는 것들이다. 실행 중인 함수의 지역변수, 스레드의 스택, 전역·정적 필드.
• 절차는 표시하고 쓸어담기다. 표시는 살아 있는 것에만 시간을 쓰고, 쓸기는 힙 전체를 훑는다.
• 고리는 저절로 풀린다. 안에서 서로 붙잡고 있어도 바깥에서 못 오면 섬이다.
• 판단 기준은 “앞으로 쓸 것인가”가 아니라 **“지금 닿는가”**다. 쓸 건데 회수되는 일은 없고, 안 쓸 건데 회수 안 되는 일은 있다.
• 고리를 푼 대신 즉시성을 잃었다. 죽은 객체가 다음 회수까지 힙에 남는다.

다음 글은 그 “회수기가 도는 동안”을 연다. 치우는 사이에 프로그램은 무엇을 하고 있는지가 응답 시간에 그대로 나온다.