다른 스레드가 읽고 있을 수 있는 락 프리 스택의 노드를 제거했습니다. 왜 그 메모리를 바로 해제하면 안 되나요?

락 프리 자료구조에서 CAS로 링크를 바꾸는 성공과 노드 메모리를 안전하게 회수하는 일은 별개입니다. 스레드 A가 top의 노드 주소를 읽고 멈춘 사이 스레드 B가 그 노드를 제거·해제한 뒤 같은 주소에 새 노드를 배치하면, A가 예전에 읽은 주소와 현재 주소가 같다는 이유로 CAS에 성공할 수 있습니다. 주소는 A→B→A로 돌아왔지만 객체의 내용과 수명이 달라진 현상이 ABA입니다. 이를 ABA 문제라고 합니다.

값 비교와 수명을 분리합니다

포인터에 버전 태그를 붙여 (주소, 세대)를 함께 CAS하면 A→B→A의 주소 재사용을 감지할 수 있습니다. 그러나 A가 이미 해제된 메모리를 역참조하는 순간이 있다면 태그만으로 use-after-free를 막을 수 없습니다. 읽는 스레드는 hazard pointer에 현재 사용 중인 노드를 게시하고 링크를 다시 읽어 아직 보호되는지 확인한 뒤 접근해야 합니다. epoch나 RCU는 독자가 안전 구간을 벗어날 때까지 retired node의 회수를 미루는 방식입니다. 전자는 읽기 경로의 게시·검증 비용, 후자는 멈춘 스레드 때문에 회수 대기 메모리가 쌓이는 비용을 가집니다.

전형적인 pop의 논리는 top을 읽고 next를 계산한 뒤 CAS로 top을 바꾸는 것이지만, top을 읽은 직후 노드가 제거될 수 있으므로 보호 표식이 먼저 유효한지 확인하는 재시도가 필요합니다. 보호 표식을 게시하기 전에 읽은 포인터를 그대로 역참조하면 게시가 늦어 이미 해제된 노드를 사용할 수 있습니다. 회수 목록을 별도로 두는 경우에도 어떤 스레드가 어느 epoch·hazard record에 있지 않은지 확인한 뒤 free해야 합니다. lock-free라는 이름은 시스템 어딘가가 진행한다는 뜻이지 각 스레드의 FIFO나 기아 방지를 보장하지 않습니다.

복잡성을 정당화합니다

오래 멈춘 reader, 스케줄 중단, 주소 재사용, 높은 contention, 회수 지연을 재현하고 ASan·TSan과 검증 가능한 회수 구현으로 확인합니다. CAS 성공률만 보지 않고 use-after-free, 회수 대기 메모리, 꼬리 지연과 starvation을 봅니다. 경쟁이 충분하지 않거나 락으로 요구 처리량을 만족할 수 있다면, hazard/epoch와 메모리 모델을 직접 증명해야 하는 비용 때문에 일반 락 구조를 우선하겠습니다.

tagged pointer는 주소와 세대를 함께 비교해 A→B→A의 논리적 재사용을 감지할 뿐, 읽는 스레드가 이미 해제된 노드를 역참조하지 않게 만들지는 않습니다. hazard pointer를 게시하기 전에 읽은 포인터를 역참조하면 이미 수명이 끝났을 수 있으므로, 표식을 게시하고 현재 링크를 다시 읽어 보호가 유효한지 확인한 뒤 접근해야 합니다. 그 재검사와 hazard 게시 유지의 조합은 노드가 제거되더라도 회수를 미루는 절차이지 과거의 use-after-free를 복구하는 수단은 아닙니다.

모든 순회·조회·디버그 경로도 hazard record나 epoch 보호를 통과해야 하며, epoch에 오래 머무는 스레드는 retired list를 키울 수 있습니다. 주소 재사용을 빠르게 하는 할당자, 오래 멈춘 reader, 높은 contention을 시험하고 use-after-free·회수 대기 메모리·최악 지연을 봅니다. 락으로 처리량과 지연 목표를 만족할 수 있다면 회수 안전성을 증명해야 하는 lock-free의 복잡성을 선택하지 않겠습니다.

tagged pointer는 논리적 ABA를 감지하는 장치이고, hazard pointer·epoch는 메모리 수명을 보장하는 장치입니다. hazard를 게시하기 전 역참조한 포인터는 이미 해제됐을 수 있으며, 재검사는 미래 경합을 다룰 뿐 그 UB를 되돌리지 않습니다. 모든 읽기 경로가 보호 절차를 통과하는지 확인하겠습니다.