개요
ABA Porblem이란, 동기화 과정에서, 같은 위치의 메모리가 두번 읽는 스레드 A가 데이터를 읽고 공유 메모리의 값을 판단하는 과정에서 A가 Preemption되고 스레드 B가 그 공유 메모리의 값을 바꾸는 조건에서 B가 A가 CAS값을 혼동할 수 있도록 값을 바꾸면 다시 A로 스케쥴링이 돌아 왔을때 예측하지 못한 행동을 할 수 있는 문제를 말한다. ABA프로그램은 다음과 같은 과정에서 발생한다:
- 프로세스 P1이 값 A를 공유 메모리에서 읽는다.
- 프로세스 P1이 preempted되어서 P2가 스케쥴링된다.
- 프로세스 P2가 값 B를 공유 메모리에 작성한다.
- 프로세스 P1이 다시 실행되었을때, 프로세스 P1은 공유 메모리의 조건이 바뀌지 않았다고 생각하지만 실은 변경되어 있다.
주로 ABA문제는 Lock-free 데이터 구조에서 포인터에 의해서 생긴다. 예를 들어서 lock free list에 오브젝트를 삭제하고 다시 추가하면 Tail pointer가 같은 위치를 가르키고 있는데 이경우 new item의 pointer가 old item의 pointer와 같아서 ABA문제를 일으킨다.
예제
/* Naive lock-free stack which suffers from ABA problem.*/
class Stack {
std::atomic<Obj*> top_ptr;
//
// Pops the top object and returns a pointer to it.
//
Obj* Pop() {
while (1) {
Obj* ret_ptr = top_ptr;
if (!ret_ptr) return nullptr;
// For simplicity, suppose that we can ensure that this dereference is safe
// (i.e., that no other thread has popped the stack in the meantime).
Obj* next_ptr = ret_ptr->next;
// If the top node is still ret, then assume no one has changed the stack.
// (That statement is not always true because of the ABA problem)
// Atomically replace top with next.
if (top_ptr.compare_exchange_weak(ret_ptr, next_ptr)) {
return ret_ptr;
}
// The stack has changed, start over.
}
}
//
// Pushes the object specified by obj_ptr to stack.
//
void Push(Obj* obj_ptr) {
while (1) {
Obj* next_ptr = top_ptr;
obj_ptr->next = next_ptr;
// If the top node is still next, then assume no one has changed the stack.
// (That statement is not always true because of the ABA problem)
// Atomically replace top with obj.
if (top_ptr.compare_exchange_weak(next_ptr, obj_ptr)) {
return;
}
// The stack has changed, start over.
}
}
};
에서 스레드 1이 현재 바라보는 큐의 상태가 Top->A->B->C라고 하자. 만약 스레드 1이 pop를 하게 된다면, CAS는 현재 Top이 A이면 B를 다음 Top으로 할려고 할 것이다. (A는 큐를 Top->B->C로 바꾸는 것을 예측한다.)
이조건에서 스레드 1이 Block되고, 만약 스레드 2가 pop, pop, insert A로 큐의 상태를 Top->A->C로 만들었다고 하자. 만약 다시 스레드 1로 넘어가게 된다면, 스레드 1의 CAS인 Top check는 통과하게 되고 B즉 이미 Drop된 Pointer가 큐의 Top으로 지정되게 된다.
결국 스레드 1로 인하여 큐는 Top->(Dropped B)->C가 되며, 이는 원하지 않는 상황이다.