인프런 커뮤니티 질문&답변

_pendingList에 값을 밀어넣을 때

	while (_pendingList.compare_exchange_weak(last->next, first) == false)
		{
		}

를 이용해서 밀어넣고 _pendingList를 통한 다른 포인터에 대한 접근은 없는데
exchange로 _pendingList를 가져오게되니 원자적으로 조작된 이후의 포인터를 가져오든,  조작되기 전에 포인터를 가져와 nullptr로 바꿔치기하든
if (--_popCount == 0) 를 검사하지 않아도 안전한 거 아닌가요?

_pendingList는 삭제 예약할 애들이 양꼬치처럼 줄줄이 연결 리스트 형태로 있는데,
[1]->[2]->[3]->[4]->[5]처럼 된 상태에서
Node* node = _pendingList.exchange(nullptr)을 하면
node가 [1]을 가리키고 있을테고 이럴 DeleteNodes로 줄줄히 삭제를 시도하는건데요.
ChainPendingList(first, last)
는 추가적으로 삭제 예약을 하는 함수이고 이를테면 ChainPendingList(6, 7)로 인해
[6]->[7]->[1]->[2]->[3]->[4]->[5]처럼 늘어날 수 있습니다.

질문주신 부분은 DeleteNodes와 ChainPendingList가
동시에 실행되는 것을 방지하기 위함인데요.
사실 얼핏보면 아무런 문제가 없는게 맞지만
자료구조상 아주아주 지구 멸망 수준의 극단적인 상황도 가정을 할 필요가 있습니다.

_pendingList가 [0]을 가리키고,
[0]->[1]->[2]로 이어지는 삭제 대기가 존재한다 가정해봅시다.

Thread A : last->next = _pendingList 호출
Thread B : Node* node = _pendingList.exchange(nullptr);

위 상황에서 ThreadB가 popCount 체크없이 node를 삭제한다면,
Thread A의 last->next는 삭제된 데이터를 가리키고 있을겁니다.
물론 99.999999999999999%의 확률로 Thread B 가 다음 코드인
while (_pendingList.compare_exchange_weak(last->next, first) == false)
~를 실행하면서 _pendingList != last->next이기 때문에 바뀐 상황을 탐지할 수 있습니다.

그러나 100%가 아닌 이유는 아주 극단적인 상황도 생각해야 하기 때문입니다.
delete로 날린 메모리 주소가, 다시 new로 (메모리 풀 등의 사용을 이유)로 동일한 주소로
할당되고 또 다시 삭제된다면, 돌고 돌아 _pendingList가 절묘하게 [0]을 가리킬 수도 있겠죠.

ThreadB가 실행하려고 기다리던
while (_pendingList.compare_exchange_weak(last->next, first) == false)
는 이러한 상태 변화를 탐지하지 못하고 그냥 순전히 _pendingList의 값이 last->next와 같은지만
판별하기 때문에 문제가 있을 수도 있습니다.

아주 극단적인 상황 같지만, 이런 상황을 대표적으로 ABA Problem이라고 합니다.
CAS 하는 연산 도중 분명히 무엇인가 바뀐 상황임에도
A->B->A 상태로 돌아가서 아무 것도 바뀐 것이 없는 것으로 오탐할 수도 있다는 얘기죠.

상황의 변경을 탐지하는 여러가지 방법이 있지만,
대표적으로 단순 64비트 주소를 사용하지 않고 128비트로
확장해서 0, 1, 2... 같은 카운터를 섞어 넣어서 현실적인 시간 내에
동일한 키값이 사용되지 않게 한다거나 뭐 다양한 방법이 있을 수 있습니다.

LockFree 코드는 오랜만에 보면 저도 많이 헷갈려서
추가로 놓친 부분이 있을 수도 있긴 합니다.
강의에서 다룬 코드는 제가 직접 만든게 아니고
C++ Concurrency In Action 책에서 발췌한 것입니다.
저도 함부로 LockFree 자료구조를 만들지 않는 이유는
정말 극한의 상황까지 생각하고, 절대 실수가 없어야 하는데
LockFree 특성상 쉽지 않기 때문입니다.

답변 못보고 작성했네요.
아래 케이스는 ABA 문제와는 또 다른 케이스입니다.

================================================================================================

아아악 TryPop에 동시에 접근하는 스레드 3개 있다고 가정해서 찾아보니 if (--_popCount == 0) 검사 안하면 터지는 상황 찾았습니다.

누군가 또 이걸로 방황하면 이 이미지든 해당 링크든 마음껏 써주시고 더이상 같은 고통을 받는 사람이 없도록 해주세요.

_pendingList가 [0]을 가리키고,
[0]->[1]->[2]로 이어지는 삭제 대기가 존재한다 가정해봅시다.

Thread A : last->next = _pendingList 호출
Thread B : Node* node = _pendingList.exchange(nullptr);

위 상황에서 ThreadB가 popCount 체크없이 node를 삭제한다면,
Thread A의 last->next는 삭제된 데이터를 가리키고 있을겁니다.
물론 99.999999999999999%의 확률로 Thread B 가 다음 코드인
while (_pendingList.compare_exchange_weak(last->next, first) == false)
~를 실행하면서 _pendingList != last->next이기 때문에 바뀐 상황을 탐지할 수 있습니다.

그러나 100%가 아닌 이유는 아주 극단적인 상황도 생각해야 하기 때문입니다.
delete로 날린 메모리 주소가, 다시 new로 (메모리 풀 등의 사용을 이유)로 동일한 주소로
할당되고 또 다시 삭제된다면, 돌고 돌아 _pendingList가 절묘하게 [0]을 가리킬 수도 있겠죠.

ThreadB가 실행하려고 기다리던
while (_pendingList.compare_exchange_weak(last->next, first) == false)
는 이러한 상태 변화를 탐지하지 못하고 그냥 순전히 _pendingList의 값이 last->next와 같은지만
판별하기 때문에 문제가 있을 수도 있습니다.

그 답변해주신 내용의 _pendingList에 ThreadB가 last->next에 _pendingList를 이어붙이려는 상황에서 절묘하게 똑같이 _pendingList가 [0]을 가르키고 있는 상황에서는
ThreadB가 들고있는 first부터 last까지(삭제해야되고 아직 삭제된적 없는 데이터들)
_pendingList가 다시 [0]을 가리키고있고 이후 [0]이 무엇을 가리키고있을지 모르는 List(삭제해야되는 데이터들)
이면 ABA 문제가 생기더라도 _pendingList에 들어온 이상 삭제해야될 데이터들이니 List를 이어주는데에 문제는 없지 않나요?
제가 달아둔 케이스와는 다르게 터질 위험은 없어보입니다.

그나저나 LockFree자료구조 재미는 있는데 너무 어렵습니다.