인프런 커뮤니티 질문&답변
작성한 질문수
Lock-Free Stack #2 강의 질문
24.08.08 19:26 작성
·
101
0
TryPop에서 compare_exchange_weak를 지난 시점에서 oldHead에 저장된 노드는 나만 가지고 있는게 아닌가요? 다른 애들은 접근하려고해도 이미 head가 바뀌어서 compare_exchange_weak를 통과하지 못하고 다음 것을 가져오는게 아닌가요?
답변 1
0
2024. 08. 09. 17:04
저도 비슷한 생각을 했었는데 생각을 좀 정리해본 결과 이러한 상황을 고려해보면 될 것 같습니다.
Node<T>* OldHead = Head.load();
while (OldHead && !Head.compare_exchange_weak(OldHead, OldHead->Next)) {};
두 스레드가 같이 pop함수에 들어온 상태라고 했을 때, 먼저 한 스레드가 oldHead를 획득하고 카운팅을 하지 않고 이 oldHead를 삭제한다고 해봅시다.
그런데, 삭제하기 전에 이미 획득한 스레드 말고 다른 스레드가 같은 Head를 참조하여 같은 oldHead를 획득한 상태라고 하고, 이후 다른 스레드에서 이것을 삭제하고 나머지 스레드가 뒤늦게 CAS 함수를 호출한다면 OldHead->Next에서 크래쉬가 날 것 같습니다.
즉,
1. Node* oldHead = _head 줄을 거의 동시에 진행하여 같은 oldHead를 획득한 스레드가 두 개가 있다. (PopCount 2개)
이 때 한 스레드가 CAS를 통과하고 매우 빠르게 삭제를 했는데 이와 동시에 나머지 스레드가 CAS를 들어간다면, 이 아디리가 터진다면 크래쉬가 발생한다.
(거의 동시에 들어왔지만 한 쪽은 CAS를 통과하고 delete하는 동안 다른 한 쪽은 가만히 있다가 이제서야 CAS를 시도하는 이 아다리가 무수히 많은 스레드에서 낮은 확률로 발생하지 않을까..? 싶습니다)
2024. 08. 11. 16:16
이런 상황을 생각해보지 못했는데 알려주셔서 감사합니다!
CAS하는 부분전에 삭제가 일어난다면 oldHead->next부분에서 크래시가 일어날 수 있다는 것을 이해했습니다.
이런 문제를 해결하기 위해 popCount를 두어 밑에서 바로 삭제 하지 않고 _popCount가 0 일 때만 삭제를 한다고 생각해 보면, 강의처럼 TryDelete가 만들어 질 수 있을 것 같습니다.
그냥 삭제 하면 안될까 생각하며 따라가니까 강의처럼 체크하는 부분들이 이해가 되는 것 같습니다!!!
정말 감사합니다