Lock보다 가벼운 Atomic 연산자를 이용한 Critical Section 처리

출처 : http://blog.daum.net/junek69/5

 

통상 Critical Section을 처리하는데 Lock을 많이 사용한다.

그런데 성능이 굉장히 중요한 부분에 있어서 Lock을 사용하기에는 성능 저하가 우려 되는 경우가 있다.

이럴 때 활용할 수 있는 것이 Atomic 연산자를 이용한 Critical Section처리이다.

Atomic 연산이란 기본적으로 연산 수행 중 thread 전환이 되지 않는 것을 보장하는 연산을 일컫는다.

흔히 하는 실수로 성능 때문에 lock을 사용하지 않고 flag 변수를 하나 두고,

flag 변수를 이용하여 critical section을  처리할려 하는데,  이 경우 flag변수에 대한 읽고 쓰는 연산이 

atomic 하지 않으면 critical section이 제대로 보호 받지 못한다.

예를 들어 아래와 같이 코딩을 하여 critical section 처리를 한다면...

unsigned int semaphore  = 0;

while (semaphore) {

    // flag 풀릴 때 까지 yield하면서 기다림

}

semaphore  = 1;

// critical section 처리 함

semaphore  = 0;

위의 코드를 수행하는 여러 thread에서 semaphore flag변수가 0임을 동시에 확인 하면

여러 thread가 동시에 critical section에 진입하게 되어 문제를 일으키게 된다.

이를 해결하기 위해서는 semaphore변수가 0이면 바로 1로 바꿔 버리는 연산이 atomic하게 thread 전환없이

처리되어야 한다.

unsigned int swap(unsigned _new)

{

   unsigned int old = semaphore;

   semaphore = _new;

   return old;

}

while (swap(1)) {

       // flag 풀릴 때 까지 yield하면서 기다림

}

// critical 처리함

swap(0);

위의 코드에서 swap() 함수가 atomic 하게 처리되면 critical section 보호가 된다.

Windows의 경우는 <boost/detail/interlocked.hpp> 에서 이러한 atomic operation들이 지원되어 이를 활용하면 된다.

안타깝게 windows가 아닐 경우는 "Interlocked intrinsics not available" 이라는 에러 메세지가 출력된다.

Linux의 경우는 x86 계열 CPU에서는 gcc에서 제공하는 __exchanged_and_add를 사용할 수 있다.

이 __exchange_and_add의 경우 gcc 4.0.2 이전에는 

arm-none-linux-gnueabi/include/c++/4.0.2/bits/atomicity.h

이후에는 아래와 같이 있다.

arm-none-linux-gnueabi/include/c++/4.5.1/ext/atomicity.h

최근에 Android 폰등에서 ARM CPU를 많이 사용하는데 위의 __exchange_and_add() 이 컴파일은 되기는 하나,

정작 테스트해보면 atomic하지 않아 critical section보호가 제대로 되지 않거나,

아니면 일반적인 pthread mutex로 구현되어 성능이 좋지 않은 것을 확인하였다.

ARMv6 이상 CPU에서는 kernel쪽을 뒤져 보면 아래와 같은 atomic operation inline assembly함수를 찾을 수 있다.

inline unsigned long testAndSwap(volatile int *ptr, unsigned long old, unsigned long  _new)

{

    unsigned long oldval, res;

    do {

        __asm__ __volatile__("@ testAndSwap\n"

        "ldrex  %1, [%2]\n"

        "mov    %0, #0\n"

        "teq    %1, %3\n"

        "strexeq %0, %4, [%2]\n"

            : "=&r" (res), "=&r" (oldval)

            : "r" (ptr), "Ir" (old), "r" (_new)

            : "cc");

    } while (res);

    return oldval;

}

ARMv5te 이하의 CPU의 경우에는 multi-core를 지원하지 않는 CPU로 kernel쪽에서는 

단순히 interrupt를 disable시킨 상태에서 flag 변수 test and swap으로 구현되어 있는데,  

이러한 방식은 user space에서는 활용할 수 없다.

그런데 swap assembly command가 지원되어서 이를 이용하여 swap 함수를 만들어서 활용할 수 있다.

inline unsigned long swap(volatile int *ptr, unsigned long _new)

{

      unsigned long oldval;

        __asm__ __volatile__("@ swap\n"

        "swp %0, %1, [%2]\n"

            : "=&r" (oldval)

            : "r" (_new), "r" (ptr) );

        return oldval;

}

ARM Cortext-A8 CPU에서 간단히 구현해서 pthread_mutex_trylock()과 성능 비교를 해보면 

위의 atomic 연사자를 이용한 critical section 보호가 4배이상 빠른 것을 확인할 수 있었다.

그러나 성능 최적화에서 무엇보다도 중요한 것은 Profiling을 먼저 해보고 

어떤 SW 부분이 bottleneck인지 확인하고 성능 최적화에 들어가야 한다.

성능에 크게 문제가 되지 않을 경우에는 표준적인 pthread_mutex_trylock()등을 활용하면

critical section진입을 위해서 yield하면서 busy waiting하지 않고 suspend되고 resume되는 이점이 있어서

전체적으로 성능상에 오히려 이점이 될 수도 있다.