ABA problem
lastmod 2018-11-28created 2017-06-136 edits
About
Ozt88.tistory.com_-_ABA_problem.jpeg
The figure above explains where the problem occurs. The original TopNode is A. Thread 1, about to Pop, will save top as A and next as B. But in the meantime another thread, Thread 2, cuts in and Pops both A and B. Normally the CAS check would Fail, but the multithreaded world is subtle. If we use a memory pool or object pool for optimization, there are plenty of situations where the memory space A used can be reused as is. So Thread 3 cuts in again and Pushes at exactly the same address A had. Then, when Thread 1 does its CAS check, it doesn't Fail! The bizarre result is that B, already Popped and sitting in the FreeList, absurdly becomes the Top of the stack.
The problem starts from the fact that comparing only address values with CAS makes it hard to guarantee the consistency of the data structure itself, because the consistency of a data structure often cannot be checked with a single address alone. So another way of guaranteeing consistency has to be devised. Likewise, for stack pop, another way of checking the data structure's consistency has to be devised.
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;
}
}