lock-free aba problem

예전에 게임 서버 포폴 만드는 공부에서 IOCP 구조로 만든 네트워크 스레드(n개)에서 받아들여온 패킷들을 Lock-Free Queue에 넣고, 게임 로직 스레드에서 꺼내다가 로직처리하도록 만들었었다.
I have developed my game server portfolio using IOCP structure. That server receives packets from network threads and pushes the lock-free queue. Then game logic thread pop a message from the lock-free queue and perform a suitable process.

그 때 겪었던 문제 중 하나가 ABA problem이었는데, stack을 가지고

간단하게 설명 글을 만들어보고자 한다.
One of the problems is the ABA problem. So, I explain the problem using the stack.


아 일단은 stack에 대해 알고 있다는 가정하에 설명하고 있다.

일단 MrRobot이라는 클래스를 보관하는 stack 이 있다고 가정하겠다.

스택이니까 간단하게 푸시를 먼저 해보자.

아래의 0x100, 0x200, 0x300은 MrRobot 객체가 할당된 메모리 주소를 예시로 든 것이다.

First I am explaining on the assumption that you know about the stack.

We have a stack that stores object of `MrRobot` class. The first step, push an object of 'MrRobot' class. The following 0x100, 0x200, 0x300 are examples of memory addresses assigned to MrRobot objects.

최초 스택 상태1개 Push한 상태2개 Push한 상태3개 Push한 상태

그럼 이제 pop하는 과정을 살펴보자. 일단은 간단한 pop 코드는 아래와 같다.

물론 일부러 ABA problem 문제가 발생하는 코드와 과정을 예시로 들 것이다.

Now let's take a look at the pop process. My sample pop code is following.
Of course, I will deliberately present code that has ABA problem.

  class Stack
   {
       volatile MrRobot* topPtr_;

       MrRobot* Pop()
       {
           while(1)
           {
               MrRobot* _retPtr = topPtr_;      
                                           
               if (nullptr == _retPtr) 
               {
                   return NULL;                                              
               }

               MrRobot* _nextPtr = _retPtr->next;   
                         
               if(_InterlockedCompareExchange( topPtr_, _nextPtr, _retPtr ))
                   return _retPtr;
           }
       }
   }

   class MrRobot
   {
   public:
      int var_;
   }​

위의 코드에서 _InterlockedCompare() 함수에 대해 간략히 설명하면 아래와 같다.
첫 번째 인자: 비교할 값의 메모리 주소

A description of the _InterlockedCompare() function is shown below.

first parameter



 : compare the value's memory address.


두 번째 인자: 첫 번째 인자와 세 번째 인자의 비교 결과가 같을 경우 첫 번째 인자값을 이 값으로 교체한다.

second parameter

 : If the comparison results of the first and third parameters are the same, replace the first parameter with this value.


세 번째 인자: 첫 번째 인자와 비교할 대상

third parameter

 : compare with first parameter.


아래는 해당 함수에 대한 msdn 링크다.

Interlocked.ComapreExchange method



간단한 샘플 코드는 요렇다.

Simply sample code is below to use _InterlockedCompareExchange function.

//예시 코드
int main()
{
    volatile long *pLong = new long(5);

    // pLong이 가리키는 값이 5 -> 3으로 변경된다.
    _InterlockedCompareExchange(pLong, 3, 5);
}

 

동시에 다른 스레드에서 push와 pop하는 과정도 살펴볼 것이다.우리가 중점적으로 살펴볼 스레드는 1번이다.

And at the same time, we will look at the push and pop process on multi-threads.

we will focus on the first thread.

4번 스레드의 빨간 글씨와 1번 스레드의 마지막 부분을 자세히 살펴보면

아래와 같은 내용을 알 수 있다.

0x200은 이미 pop되고 없는데?
게다가 0x300번지는 1번 스레드에서 pop했을 때와 이미 다른 정보다.

반납한 메모리가 금새 다시 재할당되서 들어올 수 있냐고 하는데,
전혀 가능성이 없는 일이 아니다.

시스템에서 제공하는 메모리 관련 연산자를 사용해서 할당하던,
개인적으로 만든 메모리 풀을 사용하던 가능성이 있는 일은 배제해야되니까..

정리해보면 ABA 문제는 멀티스레드 환경에서 동기화 과정에서
현재 진행 중인 스레드(위의 예시에서는 1번 스레드)에서 두 번의 읽기 사이에
다른 스레드가 실행되어 값을 변경하게 되는데, 첫 번째 스레드에서는
아무것도 변하지 않았다고 인식하게 되어 속는 문제를 말한다.

 

 

ref : http://cutup9999.blogspot.com/2018/08/lock-free-aba-problem.html