가비지 컬렉션

현대 프로그래밍 언어에는 프로그래머의 부담을 덜어 주기 위해 "가비지 컬렉션(garbage collection)" 또는 "GC"라 불리는 자동 메모리 관리 시스템이 포함되어 있다.

지금까지 다양한 GC 알고리즘이 제안되었다. 적어도 모두 다음 원칙은 공통적으로 따른다. "프로그램 실행 중 나중에 참조될 가능성이 있는 메모리는 해제하지 않는다. 절대 사용되지 않을 메모리만 해제한다." 달리 말하면 GC의 핵심은 어떤 메모리 블록이 프로그램에서 여전히 참조될 수 있는지(살아 있는 메모리), 그렇지 않은지(죽은 메모리)를 분류하는 알고리즘이다. 그러나 일반적으로 가비지 컬렉터가 어떤 블록이 살아 있는지 정확히 판단하는 것은 불가능하다. 따라서 모든 가비지 컬렉터는 생존 여부에 대한 효율적인 근사를 사용한다.

여러분의 친구인 George Collins 교수는 가비지 컬렉션 연구자다. 어느 날 그는 생존 분류를 효율적으로 근사할 새로운 아이디어를 떠올렸다. 그의 근사는 다음과 같다.

• 아직 끝나지 않은 함수에서 선언된 변수인 활성 지역 변수로부터 직접 가리켜지는 메모리 블록은 모두 살아 있는 것으로 간주한다.
• 메모리 블록 N의 포인터가 메모리 블록 M을 가리키면 두 블록의 수명은 동일해진다. 즉, N이 살아 있으면 M도 살아 있고, 그 반대도 성립한다. 이상해 보일 수 있다. 프로그램에서 M은 참조될 수 있지만 N은 그렇지 않은 상황이 있을 수 있기 때문이다. 이는 사실이지만, 생존 여부의 근사에서는 살아 있다고 과잉 분류하는 것이 치명적인 문제가 되지 않는다. Collins 교수는 이 근사가 가비지 컬렉터의 속도를 크게 높여 줄 것이라고 믿는다.
• 위 두 규칙으로 살아 있다고 판단할 수 없는 다른 모든 메모리 블록은 죽은 것으로 본다.

그림 2: 스택 프레임 3개와 객체 5개가 있는 상태의 예.

그림 3: 함수 g에서 반환한 뒤 객체 4가 죽은 상태가 되었다.

Collins 교수는 프로그래밍에 능숙하지 않아, 여러분에게 새 알고리즘의 성능을 시험할 프로그램을 작성해 달라고 부탁했다. 그는 실행할 기계 명령어의 나열을 읽고, 새 알고리즘에 의해 죽은 것으로 분류된 메모리 블록의 개수를 기록하는 프로그램이 필요하다.

입력은 명령어의 나열이다. 예를 들어 다음과 같다.

alloc
call
alloc
alloc
link 1 2
return
return

명령어는 네 종류가 있다.

여러분의 프로그램은 각 return 명령어마다 Collins 교수의 방식으로 새로 죽은 것으로 분류된 메모리 블록의 개수를 출력해야 한다.

1
2

위 샘플 입력의 경우 첫 번째 return에서 3번째 메모리 블록이 죽은 상태가 된다. 그 블록이 의존하던 함수가 return 명령어로 종료되기 때문이다. 2번째 블록은 여전히 활성 스택 프레임에 있는 1번째 블록이 가리키고 있으므로 살아 있다. 따라서 1을 출력해야 한다. 다음 return은 1번째와 2번째 블록을 죽이므로 출력은 2이다.

이 문제의 입력에는 여러 테스트 케이스가 들어 있다. 각 케이스는 명령어 나열의 길이를 나타내는 정수 L (1 ≤ L ≤ 100000)이 한 줄에 주어지며 시작한다. 그다음 L개의 줄이 이어진다. 각 줄에는 위에서 설명한 형식의 명령어가 하나씩 들어 있다.

입력의 모든 명령어 나열은 유효하다. 즉,

• link 명령어의 두 인수는 모두 살아 있는 메모리 블록이다.
• 마지막 return을 제외한 모든 return 명령어에는 그 앞에 대응하는 call 명령어가 있다.
• 마지막 명령어는 항상 return이며, 프로그램의 끝을 나타낸다.

입력은 정수 0 하나만 있는 줄로 끝난다.

각 테스트 케이스마다 먼저 샘플에 나온 것처럼 테스트 케이스 번호가 있는 줄을 출력한다. 그런 다음 입력 나열의 각 return 명령어에서 새로 죽은 블록의 개수를 한 줄에 출력한다.