이번에는 read-modify-write (이하 RMW)에 대해 정리할거야.


이전 글에서 load는 relaxed나 acquire, store는 relaxed나 release 오더를 쓸 수 있다고 했었어.


rmw는 좀 특이한데, read-modify-write 이름에서도 알 수 있듯이 (load, 변경, 변경한 값을 store)하는 과정이 atomic하게 수행되는건데, 그래서 이 operation은 load이면서 store이기도 해.


그래서 acquire나 release 오더 외에 acq_rel 이라는 오더도 사용할 수 있어. 이건 acquire이면서 release이기도 한 오더를 뜻해.


표준에서 제공하는 간단한 rmw 함수인 atomic<>::fetch_add()를 한번 보자. 이 함수는 기본적으로 x++과 같은 역할을 하는데, x++과는 다르게 atomic하기 때문에 thread-safe해.


다음 코드를 보자.


int x = 0;

std::atomic<int> y(0);

int z = 0;


void f() {

  x = 1;

  y.fetch_add(std::memory_order_release);

  z = 1;

}


이러면 외부의 관측자가 관측 가능한 (x, y, z)는 어떻게 될까? release order가 사용되었기 때문에 y++은 무조건 x=1 이후에 일어나야하고, z는 순서에 상관없이 수행될 수 있겠지? 그러니까 외부의 관측자가 관측 가능한 (x, y, z)는 (0, 0, 0), (0, 0, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)일거야. (0, 1, 0)이나 (0, 1, 1)은 절대로 관측될 수 없지.


fetch_add(std::memory_order_acquire)로 변경하면 z=1이 y++ 이후에 일어나야하니까 (0, 0, 1)이나 (1, 0, 1)은 절대 관측될 수 없겠지.


fetch_add(std::memory_order_acq_rel)이라면? 이러면 acquire이면서 release이니까, x = 1이 y++ 이전에 일어나야하고, z = 1은 y++ 이후에 일어나야할테니까 외부의 관측자가 관측 가능한 (x, y, z)는 (0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1) 밖에 없어.


표준에서 제공하는 기본적인 rmw operation은 fetch_add(), fetch_sub(), fetch_and(), fetch_or(), fetch_xor() 뿐인데, 그럼 fetch_multiply()같은건 왜 없냐? 라고 물을 수 있어. 사실 이런 함수들은 Compare-and-Swap (이하 CAS) 로 쉽게 구현이 가능한데, 이러한 구현을 위해 표준에서는 compare_and_exchange()라는 함수를 제공해.


compare_and_exchange 함수의 원형을 보자. 이 함수는 _weak 버전과 _strong 버전을 제공하는데, 이 차이점을 설명하기는 좀 귀찮으니 필요하면 검색해봐.


bool compare_and_exchange_{weak,strong}(T& expected, T desired, std::memory_order success, std::memory_order failure);


expected : atomic variable의 예상되는 현재값

desired    : 변경할 값

success    : 성공시 메모리 오더

failure     : 실패시 메모리 오더


이 함수는 atomic variable의 현재값이 expected와 같으면(성공) desired를 store(success order)한 후 true를 리턴하고, expected와 다르면(실패) 현재값을 expected로 load(failure order)하고 false를 리턴해.


이 함수를 이용해서 spinlock을 구현해볼 건데, 일단 spinlock에서 필요한 메모리 오더를 살펴보자.


lock();

// mutually exclusive region: do whatever you want

unlock();


여기서 lock()과 unlock()사이에서의 연산은 반드시 lock을 잠근 후에 일어나야하고, lock을 풀기 전에 일어나야겠지? 그러니까 lock()은 acquire semantic이어야할거고, unlock은 release semantic이어야 해.


간단하게 구현해보자.


std::atomic<int> spinlock{0}; // 1이면 잠긴 상태.


void lock() {

  do {

    int expected = 0; // 안잠겨 있다고 예상

  } while(!spinlock.compare_and_exchange_weak(expected, 1,         // 이미 락이 잠겨 있으면 실패하고 spin

                                                                                    std::memory_order_acquire,   // 락을 잠그는데 성공하면 acquire semantic

                                                                                    std::memory_order_relaxed)); //                        실패하면 어차피 spin할 테니까 relaxed semantic

}


void unlock() {

  int expected = 1; // lock()한 후에만 unlock()을 수행할 테니 잠겨 있다고 예상.

  int ret = spinlock.compare_and_exchange_strong(expected, 0, // strong 버전을 써서 spurious fail을 막음

                                                                                      std::memory_order_release,  // 락을 푸는데 성공하면 release semantic

                                                                                      std::memory_order_relaxed); //                    실패하면(그럴리 없겠지만) relaxed semantic

  assert(ret);

}


int shared_resource = 0;


void f()

{

  lock();

  shared_resource++;

  unlock();

}


간단하지? lock()이 acquire semantic이니까 shared_resource++은 lock() 후에 일어나고, unlock()이 release semantic이니까 shared_resource++은 unlock() 이전에 일어남이 보장되겠지?


pthread_mutex 라던지 std::mutex 라던지 기존에 사용하는 락들은 대부분 lock()과 unlock() 구현에 각각 acquire, release semantic이 이미 들어가 있어.


자 그런데 이 코드는 문제가 하나 있어. 스핀락을 사용하는 주된 목적은 프로세스가 block되지 않도록 하기 위함인데, atomic<int>::compare_and_exchange가 lock free하지 않을 수 있다는 거야. block되지 않기 위해 스핀락을 사용하려했는데 스핀락 구현 자체에서 block 되어버릴 수 있다는거지.


atomic<int>가 lock free한지는 atomic<int>::is_lock_free() 함수를 통해 알 수 있는데, 환경에 따라 atomic<int>가 lock free하지 않을 수 있어.


그럼 어째야 하는가? 그래서 표준에서는 무조건 lock free한 boolean 타입인 std::atomic_flag라는 애를 제공해. std::atomic<bool>과 비슷한 역할을 수행하는데, std::atomic<bool>이 lock free하지 않을 수 있는 것에 반해 std::atomic_flag는 무조건 lock-free 해야 해.


std::atomic_flag는 test_and_set(RMW), clear(STORE) 두 함수만을 제공하는데, test_and_set()은 atomic flag를 true로 세팅하면서 기존의 값을 리턴하고, clear()는 atomic flag를 false로 세팅해. 표준에 의해 이 두 함수는 무조건 lock free함이 보장돼.


atomic_flag를 사용해서 위의 spinlock을 개선해보자.


std::atomic_flag spinlock = ATOMIC_FLAG_INIT; // true면 잠긴 상태.


void lock() {

  while(lock.test_and_set(std::memory_order_acquire)); // 기존값이 1이면 spin

}


void unlock() {

  lock.clear(std::memory_order_release);

}


atomic_flag를 이용해서 lock free가 보장되는 spinlock이 만들었어.


lock free나 wait free나 설명하자면 한도 끝도 없어서 그냥 넘어갔는데, 필요하면 구글링해보면 자료 많으니까 찾는데 어렵지 않을거야.


다음에는 가장 강한 메모리 오더인 seq_cst에 대해 정리해볼게.


다들 환절기 감기 조심.