현재 CRuby GC의 한계
CRuby의 GC는 마크-스윕(Mark-Sweep) 방식을 사용합니다. 루트(Root)를 따라 접근 가능한 객체에 마크를 하고, 마크되지 않은 객체들을 스윕하여 회수하는 방식입니다. 이 과정은 단일 스레드로 실행되며, 모든 애플리케이션 스레드를 멈추는 스톱-더-월드 방식으로 동작합니다. 멀티코어 프로세서가 보편화된 환경에서 단일 코어 GC는 나머지 코어 자원을 낭비하게 됩니다.
병렬 마킹 도입
이러한 문제를 해결하기 위해 GC의 마킹 단계를 병렬화하는 ‘병렬 마킹’이 제안되었습니다. 이는 네이티브 스레드를 활용하여 객체 마킹 작업을 병렬로 수행하는 것으로, 스루풋(Throughput)과 응답성(Responsiveness) 향상을 목표로 합니다. 뮤테이터 프로그램(애플리케이션)의 정지 시간 자체는 변하지 않지만, 정지 시간 내 GC 처리 속도를 높이는 방식입니다.
구현 과제: 작업 분배 및 락-프리
병렬 마킹 구현에는 두 가지 주요 과제가 있습니다:
-
작업 분배 (Task Stealing): 단순히 루트의 각 가지를 스레드에 할당하는 방식은 작업량 불균형(파레토 법칙)으로 인해 일부 스레드가 유휴 상태가 될 수 있습니다. 이를 해결하기 위해 ‘태스크 스틸링(Task Stealing)’ 기법을 도입합니다. 작업이 일찍 끝난 스레드가 다른 스레드의 작업을 ‘훔쳐’ 와서 처리하는 방식입니다.
-
락-프리 알고리즘: 암달의 법칙(Amdahl’s Law)에 따르면, 시스템의 직렬 처리 비중이 높을수록 병렬화 효과가 크게 제한됩니다. 따라서 병렬 GC의 효율을 극대화하기 위해서는 락(Lock)을 사용하지 않는 락-프리(Lock-Free) 알고리즘을 적용하여 직렬화 비중을 최소화해야 합니다.
락-프리 덱(Deque)을 이용한 태스크 스틸링
태스크 스틸링을 락-프리로 구현하기 위해 ‘덱(Deque, Double-Ended Queue)’ 데이터 구조를 활용합니다. 각 GC 워커 스레드는 자신만의 덱을 가지며, 다음과 같은 작업을 수행합니다:
-
push_bottom: 자신의 덱의 ‘바닥(bottom)’에 새로운 작업을 추가합니다.
-
pop_bottom: 자신의 덱의 ‘바닥’에서 작업을 가져와 처리합니다.
-
pop_top: 다른 워커 스레드의 덱의 ‘상단(top)’에서 작업을 ‘훔쳐’ 옵니다.
경쟁 조건 및 해결: 덱의 요소가 1개만 남았을 때 pop_bottom과 pop_top이 동시에 호출되면 경쟁 조건이 발생할 수 있습니다. 이를 해결하기 위해 ‘age’와 ‘태그(tag)’가 포함된 1워드 크기의 ‘에이지(Age)’ 필드를 사용하고, compare-and-swap (CAS) 명령어를 활용하여 원자적(Atomic)으로 덱의 상태를 업데이트합니다. 이를 통해 동시성 문제를 해결하고 락-프리를 유지합니다.
성능 최적화: 로컬 마크 스택
순수한 덱 알고리즘은 compare-and-swap 호출 오버헤드가 높아 오히려 GC 시간이 느려지는 문제가 발생했습니다. 이를 개선하기 위해 덱에는 개별 객체 포인터 대신, 고정 길이의 ‘로컬 마크 스택(Local Mark Stack)’ 포인터를 저장합니다. 이 스택은 개별 객체 마킹 시 compare-and-swap을 사용하지 않으므로 오버헤드를 줄일 수 있습니다. 태스크 스틸링도 이 스택 단위로 이루어집니다. 이 방식은 compare-and-swap 호출 횟수를 줄여 성능을 향상시키지만, 덱에 들어가는 작업 단위가 커지므로 병렬 처리의 세밀함이 떨어져 병렬 가동률이 다소 감소할 수 있습니다.
전체적인 흐름
루비의 다양한 루트(클래스, VM 스택 등)를 ‘태스크’로 분할합니다. 각 워커는 태스크를 하나씩 가져와 처리하며, 이 태스크 획득 단계에서는 락이 필요합니다. 획득한 태스크 내에서 덱과 로컬 마크 스택을 활용하여 객체를 마킹합니다. 자신의 태스크가 모두 소진되면, 다른 워커의 덱에서 작업을 스틸링하여 처리합니다.