ABA problem
About
Ozt88.tistory.com_-_ABA_problem.jpeg
위 그림이 문제가 발생하는 지점을 설명하고 있다. 기존의 TopNode는 A이다. Pop을 하려는 쓰레드 1은 top을 A로 저장하고 next를 B로 저장할 거다. 그런데 중간에 다른 쓰레드 2가 끼어들어서 A랑 B둘다 Pop해 버렸다. 일반적인 상황이면 CAS체크에서 Fail이 뜨겟지만 멀티쓰레드의 세계는 오묘하다. 우리가 최적화를 위한 메모리풀 또는 오브젝트풀을 사용한다면 A가 쓰던 메모리 공간을 그대로 재사용할 수 있는 상황이 충분히 있다. 그래서 쓰레드 3이 중간에 또 끼어들어서 원래 A의 주소 그대로 Push를 해버렸다. 그리고나서 쓰레드 1이 CAS체크를 하면 Fail이 뜨지를 않는다! 그럼 이미 Pop해서 FreeList에 있는 B가 어이없이 스택의 Top이 되는 괴현상이 발생한다.
이 문제는 CAS로 주소 값만 비교하다보니 자료구조 자체의 일관성을 보장하기 힘들다는 점에서 시작한다. 자료구조의 일관성은 단순히 하나의 주소만으로 체크하기 힘든 경우가 많기 때문이다. 따라서 일관성을 보장하는 다른 방법을 고안해야한다. stack pop에서도 마찬가지로 자료구조의 일관성을 체크하는 다른 방법을 고안해야한다.
void push(Stack *s, Node *n) {
while (1) {
Node *old_top = s->top;
n->next = old_top;
if (compare_and_swap(&s->top, old_top, n) == old_top)
return;
}
}
Node *pop(Stack *s) {
while (1) {
Node *top = s->top;
int pop_count = s->pop_count;
if (top == NULL)
return NULL;
Node *new_top = top->next;
if (double_compare_and_swap(&s->top, top, new_top, &s->pop_count,
pop_count, pop_count + 1));
return top;
}
}