ABA Problem

 

 

1. ABA Problem이란?

 

간단히 말하자면 CAS(Compare And Swap)를 사용해서 자료구조의 아이템을 변경할 때,

포인터가 시스템에 의해 재사용되면서 생기는 문제다.

 

일단 CAS를 비교할 때 포인터 변수를 가지고 작업을 수행하기 때문에 결국 주소값을 비교하게 된다.

 

다음 예문을 보자.

 

 class Stack

   {
       volatile Obj* m_topPtr;

       Obj* Pop()

       {
           while(1)

           {
               Obj* preTopPtr = m_topPtr;                                                              // (1)
               if (!preTopPtr) return NULL;                                                   // (2)
               Obj* nextPtr = preTopPtr->next;                                               // (3)
               if (CompareAndExchange( m_topPtr, preTopPtr, nextPtr))                       // (4) 
                   return preTopPtr;
           }
       } // CAS는 m_topPtr과 preTopPtr이 같으면 nextPtr로 m_topPtr을 교체.

       void Push( Obj* obj_ptr )

       {

        ...  
   }

 

 

 

 

 

[출처] ABA Problem 에 관해|작성자 쫌조

문제되는 상황을 설명하면 이렇다.

지금은 현재 스택 객체의 상태이다.

 

① Thread1이 (3)번 까지를 수행한다. (4)은 아직 실행하지 않은 상태.

② Thread2가 Pop()을 2번 수행한다.

 

 

③ Thread2(또는 Thread3이)가 Push()를 1번 수행한다.

 

④ Thread1이 (4)를 마저 수행한다.

 

 

이 과정을 살펴보면 Thread2가 Pop()을 두번 수행하면서 변수 2개를 삭제했을것이다. 그리고 다시 Push()를 한번하여 변수를 하나 추가했는데.

이때 추가한 변수의 주소값이 메모리할당자에 의해 첫번째 Pop()한 변수의 주소값으로 할당되고, 이 주소값은 m_topPtr에의해 가리켜 질것이다.

④번에서 이미 로컬에 저장되어있는 preTop주소값과 현재 top주소값인 m_topPtr이 같으니 넘어가자~ 하게되면 문제가 발생하게 되는것이다.

 

 

주의 사항부터 설명하자면,

Stack을 예로 들고 있기때문에 우리는 마치 이것이 스택에서 위치 주소 문제인걸로 착각하게 된다.

하지만 이것은 결국 LinkedList로 이루어져 있고, next값을 통해 다음 아이템을 찾아간다.

가장 중요한 포인트는 스택에서의 위치 주소가 아니라 Value의 주소값이 메모리 관리자(개발자가 만든것이든 OS가 제공하는 것이든)에 의해 재활용되기 때문에 생기는 문제라는 것이다.

많은 예에서 pop을 두번하고 push를 한번 하는 이유는 그래야 현재 가리키는 top의 값이 삭제된 메모리를 가리켜 문제가 생기기 때문이다.

pop 한번 push 한번인 예제였다면 Value값이 바뀌어있을지는 모르지만 메모리 침범 문제는 일어나지 않을것이다. (자료구조 특성상 문제될 부분은 없다)

 

 

 

 

 

 

 

 

 

 

 

 

 

2. 해결 방법

 

① DCAS (Double compare-and-swap)

 

말 그대로 두번 체크를 하는것이다. 

위 ABA Problem에서 보면 단순히 변수의 주소값만으로는 해당 변수가 새로 들어온 녀석인지 기존에 있던 녀석인지를 판단하기 어렵다.

그래서 PopCount를 가지고 한번더 검증을 하는 작업을 수행하여 이런 ABA Problem을 막을 수 있다.

 

 

하지만 CAS를 두 번 쓴다면 어떻게 될까?

당연히 한번 CAS를 수행한 후에 또 다른 스레드에서 공유 데이터를 변경 시킬 가능성이 생긴다.

 

우리가 64비트 주소 체계를 사용하게되면 InterlockedCompareExchange64로는 두 값을 넣을 수 없다.

그래서 interlockedCompareExchange128 함수를 사용해야 하지만

이 함수는 Windows 8, Windows Server 2012 이상에서만 사용 가능하므로 재원을 잘 확인하여 사용해야 할것이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

② Hazard Pointer

 

해제하면 안되는 위험한 포인터를 Hazard Pointer라하며, 주 내용은 다른 스레드가 해당 변수를 사용하고 있다면 메모리를 해제하지 않는것이다.

이렇게되면 MemoryManager는 메모리를 반환받지 못할것이고 메모리 재활용을 통한 ABA Problem은 발생하지 않을것이다.

구현내용은 다음과 같다

 

 

HazardPointerList - Lock-Free List 인데 일정량의 리스트를 만들어 두고, Active 여부만을 체크하여 계속 돌려 사용한다. 리스트 안의 모든 HazardPointer들이 다 사용되었다면 하나를 새로 만들어서 Head앞에 붙여 사용한다. 그러므로 HP를 할당받기 위해 리스트의 처음부터 발견할때까지 순회를 해야한다. 하지만 하나의 스레드가 사용하는 HP의 수는 1~2개 이므로 그렇게 많은 루프를 돌일은 없을것이다.

 

RetireList - 스레드 별(TLS)로 가지고있는 리스트. 현재 자신의 스레드에서 Pop()이 수행되었다면 해당 포인터 변수는 바로 삭제되는것이 아니라 일단 retireList에 들어가게된다.

Pop() 수행과 함께 삭제되어야할 변수를 말 그대로 은퇴만 시켜놓는 것이다. 이렇게 은퇴 시켜놓은 변수는 HazardPointer 리스트를 돌며 존재 유무를 확인 한 후 삭제한다.

만약 HP List에 존재한다면 해당 변수는 아직 다른 스레드에서 사용중이라는 것이고, 존재하지 않으면 사용중이지 않다는 것이므로 삭제해도 문제가 되지 않는다는 뜻이다.

즉, RetireList는 Pop()에서만 사용된다고 볼수 있다.

 

순서를 보자면 이렇다.

 

① Thread1이 (3)번까지 수행한다(Pop()). 이때 로컬변수들은 topPtr, nextPtr 변수를 Hazard Pointer List에 집어넣는다. 

② 집어넣을때는 HPList를 처음부터 돌아서 빈 공간(Deactive)을 찾아 넣어둔다. (조금 소모적일수 있다.)

③ Thread2가 Pop()을 두번 수행한다. Pop()을 수행이 끝났다면 Pop()된 변수는 바로 삭제되지 않고 RetireList로 들어간다.

④ 물론 위 과정에서 역시 로컬변수들은 HP List로 들어간다. 그리고 CAS가 끝나면 HPList에서 Deactive된다.

⑤ RetireList로 들어간 변수 리스트를 모아서 HP List에 존재하는지 확인한다.

⑥ 있다면 아직 다른 스레드에서 사용 중이므로 삭제하지 않고 없다면 다른 스레드에서 사용중이 아니므로 삭제한다.

⑦ 사용중이었다면 메모리가 삭제되지 않았으므로 MemoryManager로 들어갈 일도 없을 것이므로, 주소를 비교하는 상황에서 예전에 사용된 주소가 다시 튀어나올 일은 없다.

 

조금 길지만 순서에 따라 쭉 읽어보도록한다.

주요 핵심은 이렇다. 이 모든 문제는 주소값을 비교하여 자료구조의 변화를 체크하기 때문이며, MemoryManager가 그 변화를 인지하지 못하고 이미 삭제된 메모리 주소를 재할당하면서 발생하는 문제이다.

그러므로 이미 사용중인 메모리를 삭제하지 않고 가지고 있는다면 아무 문제될것이 없다!

위에서 매번 Pop() 할때마다 RetireList와  HPList를 비교한다면 성능적인 부담이 있을 수 있으므로, 일정양 모아서 수행하도록 하는것이 좋다.

 

 

GC가 있는 환경에서 ABA Problem이 일어나지 않는 이유도 이와 같다.

해당 포인터 변수가 어딘가의 로컬변수에 의해 사용중인것을 알고 있기때문에 메모리로 반환이 되지 않는것이다.

 

 

 

 

 

 

 

 

[참고]

http://devnote.tistory.com/207

http://blog.naver.com/PostView.nhn?blogId=jjoommnn&logNo=130127286459&parentCategoryNo=&categoryNo=&viewDate=&isShowPopularPosts=false&from=postList