ABA Problem
2009. 5. 21. 18:49 in programming

위키디피아에서의 ABA Problem 설명은 lock free stack구현에서의 문제점을 예제로 들고 있습니다.
01.
<code>/* Naive lock-
free
stack which suffers from ABA problem.*
02.
03.
class
Stack {
04.
05.
06.
volatile
Obj* top_ptr;
07.
08.
// Pops the top object and returns a pointer to it.
09.
Obj* Pop() {
10.
while
(1) {
11.
Obj* ret_ptr = top_ptr;
12.
13.
if
(!ret_ptr)
return
NULL;
14.
// ** 실행 구간 1
15.
Obj* next_ptr = ret_ptr->next;
16.
// ** 실행 구간 2
17.
if
(CompareAndSwap(top_ptr, ret_ptr, next_ptr)) {
18.
return
ret_ptr;
19.
}
20.
// The stack has changed, start over.
21.
}
22.
}
23.
};
24.
</code>
언뜻 봐서는 코드상으로는 크게 문제가 없어 보이며, 실제로도 자체 구현상으로는 거의 완벽한 lock free stack이 구현된것으로 생각됩니다.
(** CompareAndSwap()은 인자 1,2가 같은값일때, 1번인자의 값을 3번 값으로 swap시킵니다. Atomic Operations 이므로 매우 빠릅니다.)
그러나, 아래의 시나리오를 봅시다.
스택이 top->A->B->C 로 초기화되어 있다고 가정했을때,
01.
// --- 1번 Thread 작업 --
02.
03.
// 1번 Thread가 pop을 실행합니다.
04.
05.
ret = A;
06.
next = B;
07.
08.
// --- 1번 Thread 작업 중 작업전환 --
09.
10.
// --- 2번 Thread 작업 --
11.
12.
// 2번 스레드의 pop이 실행됩니다.
13.
14.
{
15.
ret = A;
// 1번 스레드의 pop이 끝까지 실행되지 못했으므로, top은 A입니다
16.
next = B;
17.
CompareAndSwap(A, A, B)
// 성공, top은 B가 됩니다.
18.
return
A;
19.
}
// 스택상태는 top -> B -> C 이 됩니다.
20.
{
// 2번 쓰레드가 한번더 pop을 실행합니다.
21.
ret = B;
22.
next = C;
23.
CompareAndSwap(B, B, C)
// 성공, top은 C가 되었습니다.
24.
return
B;
25.
}
// 스택상태는 top -> C 이 됩니다.
26.
delete
B;
// 2번 쓰레드에서 B값을 삭제 합니다.
27.
{
// 2번 쓰레드에서 아까 위해서 pop된 A를 push합니다.
28.
A->next = C;
29.
CompareAndSwap(C, C, A)
// 성공, top은 A가 됩니다.
30.
}
// 스택상태는 top -> A -> C 이 됩니다.
31.
32.
// --- 2번 Thread 작업 중 작업전환--
33.
34.
35.
// --- 1번 Thread 작업 다시 실행-- CompareExchange(A, A, B);
36.
// top과 return값이 모두 A이므로 성공이 됩니다.
37.
// 그러나 B는 2번 Thread에서 삭제가 되어 있으므로, 이 구간 부터, stack은 잘못된 메모리
38.
// 를 참조하게 됩니다.
39.
// 이 상황을 ABA Problem 이라고 합니다.
쉽게 일어나지 않을 상황 같지만, 일어나지 않는다는 보장도 없는 상황입니다.
물론 C#이나, Java같이 가비지컬렉션을 사용하는 언어에서는 발생되지 않을 문제이지만,
C계열에서는 반드시 고려가 되어야 될 문제이기도 합니다.
당장 생각나는 해법으로는
1. 그냥 sync를 시키면서, 표준 stack을 사용
2. smart pointer를 사용
정도가 될거 같지만, 좀더 고민이 필요한 문제일거 같습니다
역시 병렬프로그래밍의 길은 멀고도 험한거 같네요 :)