동기화 연산과 CAS

이전시간 리뷰

현실의 공유 메모리는 Atomic 하지 않다. 하지만 프로그래밍은 Atomic Memory를 가정해야한다.

• 성능 향상을 위해 멀티쓰레드 프로그래밍을 해야한다. -> Data Race 발생
• Data Race를 최소화 해야한다. -> Data Race는 모든 오동작의 근원
• 어쩔 수 없이 남은 Data Race를 Lock 없이 해결해야한다. -> Data race를 모두 없앨 순 없고, lock으로 해결하는 것은 성능 패널티가 크다.
• Data Race는 공유 객체 때문에 발생한다. -> 객체 int, float, struct, class, container ,,, 따라서 논블로킹 멀티쓰레드 객체가 필요하다.

 

Q. 기존의 싱글쓰레드 자료구조도 Atomic Memory를 사용해서 멀티쓰레드 자료구조로 변환하는것이 가능한가? (Wait-Free 유지하면서)

A. CompareAndSet() 연산을 사용하자. / 고성능 자료구조는 논블로킹 자료구조로 구현해야한다.

• Atomic memory를 사용해서는 논블로킹 자료구조를 만들 수 없다. 읽고 쓰는것만으로는 안되고 CAS라는 연산을 사용해야한다.
• CPU가 제공하는 CAS를 사용하면 모든 싱글쓰레드 알고리즘을 lock free한 멀티쓰레드 알고리즘으로 변경가능하지만, 속도가 너무 느리다.
  • 최적화를 일일이 개발해주어야한다.
  • 다른데서 api를 사용할 수도 있다. (Intel TBB / VS2015 PPL에서 멀티쓰레드 lock free 논블로킹 자료구조 라이브러리를 제공하고 있음.)

 CAS (메모리, expected, update)

• 메모리의 값이 expected면 update로 바꾸고 true를 리턴한다.
• 메모리의 값이 expected가 아니면 false를 리턴한다.

if(*메모리 == expected){
	*메모리 = update;
    return true;
} else return false;

 

CAS (CompareAndSet) 구현 : C++11

atomic_compare_and_set은 없고 atomic_compare_exchange를 대신 사용한다.

bool CAS(atomic_int* addr, int expected, int new_val)
{
	return atomic_compare_exchange,_strong(addr, &expected, new_val);
}

bool CAS(volatile int* addr, int expected, int new_val)
{
	return atomic_compare_exchange,_strong(
    	reinterpret_cast<volatile atomic_int*> (addr), &expected, new_val);
}

---

실습

CAS를 사용해서 lock과 unlock을 구현하고 1억 만들기 프로그램을 실행해보자.

• CAS는 논블로킹 자료구조를 만드는데 필수인 연산이다.
• n개의 쓰레드에서 lock을 구현하기 위해서 빵집알고리즘일경우 모든 쓰레드의 flag를 검사하는데 오버헤드도 크고, 오류도 많다.
• intel에서는 lock과 unlock을 구현하기 위해서 CAS를 사용한다.

lock이란 한 쓰레드만 자원에 접근할 수 있도록 하는 용도인데 CAS로 이거를 어떻게 구현할 것인가?

volatile int sum;
volatile int X = 0;

bool CAS(volatile int* addr, int expected, int new_value)
{
    return atomic_compare_exchange_strong(reinterpret_cast<volatile atomic_int*>(addr), &expected, new_value);
}

void cas_lock()
{
    while (false == CAS(&X, 0, 1));
}

// X = 1 누가 lock을 얻었다. 0이면 아무도 lock을 얻지 않았다.
void cas_unlock()
{
    X = 0;
}


void thread_func(int t_num, int t_count)
{
    for (int i = 0; i < 500'0000 / t_count; ++i)
    {
        cas_lock();
        sum += 2;
        cas_unlock();
    }
}

CAS를 실행시킬때 오직 하나의 쓰레드에서만 리턴값 true를 반환하면된다.

 

실행결과

쓰레드가 늘어나면 늘어날수록 성능이 떨어짐

• CAS를 실패했을때 계속해서 CAS를 함. (CAS는 mutex보다는 아니지만 오버헤드가 있는 편)
• 쓰레드가 늘어날수록 배로 계속해서 CAS를 진행하게 됨 (메모리버스는 CAS연산을 하느라 다른짓을 못하고 성능이 떨어지게 된다.)

 

다음으로 할일

CAS를 사용하며 멀티코어 프로그래밍시 성능향상을 위한 자료구조 linked list를 구현해보자

 

---

출처

한국산업기술대학교 게임공학부 정내훈 교수님 강의 - 멀티코어 프로그래밍