락 프리 자료구조 (lock-free data structure)
쉽게 풀면
여러 스레드가 같은 자료를 고칠 때 보통은 자물쇠를 걸어 한 번에 한 명만 들어가게 합니다. 락 프리 자료구조는 자물쇠 대신, 값을 읽고 바꾸는 일을 하드웨어가 통째로 보장하는 원자적 명령으로 처리합니다. 다른 스레드가 먼저 바꿔 버렸으면 실패를 감지해 다시 시도하는 방식으로, 누구도 멈춰 기다리지 않습니다.
왜 중요한가
락을 쥔 스레드가 중간에 멈추면 나머지 전부가 기다려야 하는 문제를 없애 주어, 지연이 중요한 시스템이나 인터럽트 처리 경로에서 유리합니다. 어떤 스레드가 죽거나 지연되어도 전체 시스템은 반드시 진전한다는 보장이 성립합니다. 고성능 큐, 메모리 할당기, 런타임 내부 구조 등에서 실제로 널리 쓰입니다.
논문에서는 이렇게 쓰입니다
경쟁이 심한 상황에서 자물쇠를 쓰지 않는 방식이 최악 지연을 줄였다는 뜻입니다.
조금 더 깊게 보면
핵심 도구는 비교 후 교환 명령으로, 기대한 값과 현재 값이 같을 때만 새 값으로 바꾸고 결과를 알려 줍니다. 진행 보장은 강도에 따라 나뉘어, 적어도 한 스레드는 반드시 진전하는 락 프리와 모든 스레드가 유한 단계 안에 끝나는 웨이트 프리로 구분됩니다. 값이 A에서 B로 갔다가 다시 A로 돌아와 변화를 눈치채지 못하는 ABA 문제와, 다른 스레드가 참조 중인 노드의 안전한 회수 문제가 구현의 최대 난점이며 태그 포인터나 위험 포인터로 대응합니다.
주의할 점
뮤텍스를 쓰지 않는다고 해서 항상 빠른 것은 아니며, 경합이 낮은 상황에서는 잘 만든 잠금 구현이 더 빠른 경우도 흔합니다. 올바른 구현에는 메모리 배리어에 대한 정확한 이해가 필수라서, 직접 작성하기보다 검증된 라이브러리를 쓰는 것이 권장됩니다.