락프리큐 관련해서 문의드립니다

작성한 질문수 3

1

안녕하세요,

우선 버그 제보를 주셔서 감사드립니다.
Lock-Free 알고리즘 특성상 직접 설계는 하지 않고
[C++ Concurrency In Action] 책의 코드를 '거의 그대로' 옮겨왔는데,
너무 난이도가 높아 보이는 후반부 완전한 코드를 제외하고 일부만 발췌했더니,
다중 Push 쪽에서 결함이 있는 것 같네요.
원인 파악과 수정이 완료 되는대로 수정 코드를 업데이트 하고
다시 댓글을 드리도록 하겠습니다.

꼼꼼히 확인 해주셔서 감사드립니다.

0

안녕하세요,
오랜 헤딩 끝에 겨우 찾았는데, 놀랍게도 책이 잘못되어 있었습니다 (!?)

현재 LockFreeQueue 코드에서 Push가 경합할 때,
1) 먼저 [참조권(강의에서 사용하는 이름)]을 획득한 다음,
2) 데이터를 먼저 교환하는 쪽이 승리자가 됩니다.

데이터가 처음에는 nullptr인데, 이를 nullptr이 아닌 값으로
먼저 CAS 세팅하는 쪽이 최종 승자가 되는 원리입니다.
패배자는 다음 while 루프에서 다시 도전을 하게 됩니다.

그런데 TryPop 쪽 코드에서 데이터를 꺼내갈 때,
하필 exchange(nullptr)을 사용해서
기존 데이터를 nullptr로 밀어주면서 데이터를 꺼내가고 있었습니다.
때문에 Push 쪽에서 실제로는 앞서서 데이터를 설정한 쓰레드가 있음에도 (data != nullptr),
Pop에 의해 data가 nullptr로 리셋되면서,
Push가 동일한 노드에 대해 2명의 승리자가 생기는 버그가 있었습니다.

Pop 코드에서 exchange(nullptr)이 아니라
일반 load()를 이용해서 데이터를 꺼내가면 문제는 간단히 해결됩니다.

LockFreeQueue는  일부 내용을 덜어냈는데도
코드가 매우 괴랄해서 그냥 커리큘럼에서 뺄까도 고민중이니
가볍게 보고 남어가시기 바랍니다.