이 노트의 핵심 경계는 링크에서 노드를 제거하는 시점과 메모리를 재사용할 수 있는 시점을 분리하는 것입니다. CAS가 주소 비교에 성공했는지는 객체가 아직 살아 있고 독자가 안전하게 역참조할 수 있는지와 별개의 질문이므로, 논리적 ABA와 물리적 수명 보호를 같은 문제로 뭉뚱그리지 않습니다.
CAS 성공과 메모리 수명의 분리
스택 top의 주소 A를 읽은 스레드가 멈춘 사이 다른 스레드가 A를 제거·해제하고 같은 주소에 새 노드를 만들 수 있습니다. 첫 스레드는 주소가 같다는 이유로 CAS에 성공해도 객체의 정체성과 연결은 달라졌을 수 있습니다. 값이 A에서 다른 값으로 갔다가 A로 돌아오는 ABA입니다.
더 빠른 문제도 있습니다. CAS를 하기 전에 이미 해제된 A의 next를 읽으면 그 순간 use-after-free입니다. 주소·세대를 함께 CAS하는 태그는 논리 재사용을 감지할 수 있지만 이미 끝난 메모리 수명을 연장하지 않습니다.
읽기 쪽의 선행 조건은 “포인터를 얻었다”와 “그 포인터를 역참조할 권리가 있다”가 다르다는 점입니다. 예를 들어 스레드 T1이 A를 읽은 뒤 멈추고 T2가 A를 unlink·free·재사용하면, T1의 CAS 실패 여부와 무관하게 T1이 A->next를 읽는 순간 수명 위반이 발생할 수 있습니다. 태그는 논리적 재사용을 감지하는 장치이고, 회수 지연은 물리적 수명을 보장하는 장치입니다.
제거와 회수 사이의 보호 단계
그림을 글로 읽기
- 자료구조에 연결됨
- unlink 후 retired: 옛 독자의 참조 가능
- 보호 독자 없음 확인
- 메모리 회수·재사용
- 자료구조에 연결됨 → unlink 후 retired: CAS로 링크 변경
- unlink 후 retired → 보호 독자 없음 확인: 회수 프로토콜
- 보호 독자 없음 확인 → 메모리 회수·재사용: 안전한 종결
노드를 공유 자료구조에서 제거하고 retired 목록에 넣었다고 해도, 이미 포인터를 읽은 독자의 사용이 끝났다는 뜻은 아닙니다. 그래서 hazard 슬롯, epoch 읽기 구간, 잠금처럼 어떤 독자가 어떤 참조를 보유하는지 확인한 뒤에만 free로 넘어가는 회수 프로토콜이 필요합니다. 디버그 순회와 통계 조회도 노드의 next를 읽는다면 같은 보호를 따라야 합니다.
Hazard pointer 게시와 원본 재검사
독자가 top을 읽고 hazard 슬롯에 게시하기 전에 writer가 그 노드를 회수할 수 있습니다. 따라서 읽은 포인터를 즉시 역참조하지 않고 보호 게시 후 현재 링크가 같은지 다시 검사합니다.
repeat:
candidate = load_root_using_library_contract()
publish_hazard(candidate)
current = reload_root_using_library_contract()
until candidate == current
# 검증된 회수 알고리즘의 순서·재사용 전제 아래에서만 역참조
use_protected_node(candidate)
clear_hazard()
이것은 메모리 순서를 생략한 교육용 단계이며 그대로 복사할 lock-free 구현이 아닙니다. 게시 store·원본 재읽기·reclaimer의 scan 사이 순서와 주소 재사용 조건은 검증된 라이브러리의 계약을 따라야 합니다. candidate가 달라졌으면 그 포인터의 내용을 읽지 않고 다시 시작합니다.
hazard는 unlink를 막는 것이 아니라 보호된 노드의 reclaim을 늦춥니다. 여러 노드를 동시에 참조하면 필요한 슬롯 수와 이동 중 보호 순서를 관리해야 합니다. 포인터 태그가 유한하면 wrap 가능성도 고려합니다.
실패 순서를 한 번 직접 적어 보면 재검사의 필요성이 분명해집니다. T1이 candidate=A를 읽고 멈춘 사이 T2가 A를 retire하고 hazard를 scan하면 A를 회수할 수 있습니다. T1이 hazard를 게시한 뒤 root를 다시 읽어 B를 확인하면 A를 사용하지 않고 반복해야 하며, 이 재검사 전에 A->next를 읽는 구현은 보호 절차를 우회합니다. 실제 코드는 원자 연산의 memory order와 reclaimer scan 계약을 함께 검토해야 합니다.
Epoch 회수와 오래된 독자의 종료 대기
epoch 기반 회수는 독자가 읽기 구간에 들어갔음을 표시하고, 제거된 노드를 볼 수 있는 이전 구간 독자들이 모두 끝난 뒤 회수합니다. 매 노드 hazard 게시 비용을 줄일 수 있지만 오래 멈춘 독자 하나가 많은 retired 메모리를 붙잡을 수 있습니다.
| 방식 | 독자 비용 | 회수 지연 요인 |
|---|---|---|
| Hazard pointer | 참조별 게시·재검사 | 보호 슬롯·scan 비용 |
| Epoch/RCU 계열 | 읽기 구간 등록·종료 | 오래 머무는 독자·grace period |
| 일반 잠금 | 획득·경합 | 긴 임계 구역·대기 |
정확한 RCU·epoch 변형은 서로 다르므로 같은 구현이라고 보지 않습니다. 독자를 시간 초과시켰다고 실제 실행이 종료되기 전 노드를 강제 free할 수 없습니다. 읽기 구간을 짧게 하고 그 안에서 무기한 I/O를 하지 않도록 설계하며, retired bytes와 가장 오래된 독자를 관찰합니다.
선택 기준은 독자가 보호할 참조 수와 멈춤 패턴입니다. 짧고 예측 가능한 읽기 구간에서 많은 노드를 훑는다면 epoch 계열이 단순할 수 있지만, 독자가 장시간 정지하거나 임의 callback을 수행한다면 retired bytes가 상한을 넘는 실패 모드를 먼저 계산해야 합니다. 참조가 드문 대신 보호 대상이 동적으로 많다면 hazard의 슬롯·scan 비용도 처리량 예산에 넣습니다.
메모리 상한과 진행성 보장의 범위
회수가 멈췄는데 writer가 계속 새 노드를 만들면 메모리가 무한히 증가할 수 있습니다. 새 작업 수락·갱신을 제한하거나 회수 방식·읽기 분할을 바꿀 수 있지만 그 선택이 전체 API의 진행 보장을 바꿀 수 있습니다. 안전성을 위해 대기한다면 그것을 숨기고 전체 함수가 언제나 lock-free라고 주장하지 않습니다.
Lock-free는 시스템 전체의 어떤 연산이 계속 완료되는 진행 성질이지 모든 스레드가 제한된 단계 안에 끝난다는 뜻은 아닙니다. Wait-free는 개별 연산의 단계 상한을 더 강하게 요구합니다. 둘 다 OS가 스레드를 언제 스케줄할지 포함한 벽시계 deadline 보장은 아닙니다. 할당기·회수·로그·콜백이 blocking이면 핵심 CAS 루프의 성질과 전체 API의 성질이 달라집니다.
주소 재사용·독자 정지 기반 회수 오류 시험
독자를 포인터 읽기 직후·hazard 게시 직후·검사 직후 멈추고 writer가 제거·재사용하도록 시험합니다. epoch 독자를 오래 유지한 채 갱신 부하를 주어 retired 메모리와 원본 처리량을 관찰합니다. ASan·TSan·모델 검사 등 도구는 도움되지만 테스트 통과가 모든 메모리 모델 실행의 증명은 아닙니다.
성능 목표를 일반 잠금 구조가 만족한다면 직접 회수 프로토콜을 증명하는 비용을 피하는 것이 합리적일 수 있습니다. CAS 성공률이 아니라 안전한 수명·최악 지연·메모리와 개별 기아까지 비교해야 합니다.
진단 지표는 CAS 성공률 하나로 충분하지 않습니다. candidate 읽기 전후의 retire 시각, hazard 게시와 scan 사이의 순서, 세대 재사용 횟수, retired bytes, 가장 오래 열린 읽기 구간을 기록하면 use-after-free와 단순 메모리 압박을 구분할 수 있습니다. ASan·TSan 통과는 특정 실행을 지지할 뿐, 검증하지 않은 메모리 순서의 안전성 증명으로 읽지 않습니다.