The Pauseless GC Algorithm

Usenix VEE 2005
Cliff Click, Gil Tene, Michael Wolf

개요

인터럽트를 User-level에 효율적으로 전달할 수 있고, Read-barrier를 하드웨어적으로 구현할 수 있는 특수 CPU를 사용하여서, Garbage collection의 고질적인 문제인 Stop-the-world시간을 최소한 (이론상 0)으로 만들 수 있는 GC를 설계함

Motivation

기존 시스템에서 GC의 Stop-the-world는 Real-time시스템이나 Latency sensitive한 시스템에서 예측할 수 없는 Latency peak을 가져온다. 이를 줄이기 위한 많은 연구가 수행중이지만, 완전히 없앨 수 있는 방식은 연구된바 없었다.

Design

Hardware modification

• Not-marked-through (NMT)라는 VA상의 하드웨어의 8byte비트를 재사용하여서, mark coloring을 가능하게 하였다. 즉 이 VA가 마크되었는지, 아니면 마크되지 않았는지를 판단하기 위한 bit로 저 bit의 값이 per-thread mark value와 같으면 page fault가 나지 않지만, 만약 다르면 GC-fault를 발생시켜 User-level에 구현된 인터럽트 핸들러로 바로 Invoke시켜준다.

Garbage collection 방식

전통적인 Garbage collection은 Mark phase, Relocate phase, 그리고 Remap phase로 구성된다.

• Mark Phase: Marking은 Heap memory를 흝으며, Live memory와 Dead object를 체크한다.
• Relocate Phase: Marking결과 페이지의 대부분이 Dead object이면, 이 Compaction을 위해서, 이 페이지를 메모리의 새로운 영역으로 옮긴다.
• Remap Phase: 메모림가 Relocate되면, Relocate되기 전의 VA가 stale, 즉 새로운 곳으로 옮겨같지만, 아직 옮겨지지 않은 상태로 놓이는데, 이를 옮겨진 포인터로 다시 엎어써주는 단계가 필요하다.

이 각각의 단계는 Synchronization이 매우 중요하다. 그렇다면 어떻게 Stop-the-world없이 Main Application thread가 Concurrency bug를 일으키는 것을 막을 것인가?

Concurrency Handling

• Mark Phase: Mark Phase시작전에, NMT비트를 새롭게 설정한다. Marking이 계속 진행되면, Marking된 포인터의 NMT값은 그 값으로 업데이트 된다. 아직 Mark가 되지 않은 VA와 같은 경우에는, 하드웨어가 Read가 일어나는 순간 User-level GC-handler로 넘긴다. 이 User-level GC Handler는 포인터에 대한 Marking을 수행하고, 만약 Remap이 필요한 Pointer를 가지고 있으면, Remap을 수행한다.
• Relocate Phase: 아직 Relocate되지 않은 영역에 대한 접근이 read barrier가 확인후, 있으면 GC-trap이 발생하고, User-level handler가 Relocating을 수행한다.
• Remap Phase: Pauseless GC에서는 Remap과 Mark를 동시에 수행하기 때문에, 최초의 Mark phase이외에는 Remap은 Mark와 함께 진행된다.

그래서 Stop-the-world가 정말로 없나요?

이론적으로는 Stop-the-world를 완전히 없앨 수 있지만, Initialization같은 단계에서 쉽게 구현하기 위해서 약간의 Stop-the-world가 발생한다.

Conclusion

특수 하드웨어를 사용해야 한다는 단점이 있지만, 후대의 ZGC나 C4 GC에 영향을 미친 중요한 논문이다.