Atomic 연산, CAS (CompareAndSwap)에 대하여, ABA 문제

스핀락, 뮤텍스, 세마포어, 모니터 모두 하나의 Thread가 임계 영역을 Lock한 후 작업을 수행하는 절차이지만 synchronized화 하게 되면 한 개의 Thread가 해당 블락을 전체 lock(점유)하기 때문에 다른 Thread는 아무 작업을 하지 못하게 되고 이로 인해서 기다리는 상황이 발생하고 낭비가 심해진다.

그래서 Non-blocking한 방법, Lock-free한 방법으로 동기화 문제를 해결하기 위한 방법이 바로 Atomic 연산이고 이 동작의 핵심 원리는 CAS (Comparre ANd Swam)에 있다.

CAS (CompareAndSwap) 알고리즘이란?

멀티 쓰레드 환경, 멀티 코어 환경에서 각 CPU는 메인 메모리에서 변수값을 참조하는 것이 아닌 각 CPU에서 캐시 영역에서 메모리를 값을 참조하게 된다. 이때, 메인 메모리에 저장된 값과 CPU 캐시에 저장된 값이 다른 경우가 있다. 이를 가시성 문제라고 한다.

이때 사용되는 것이 CAS 알고리즘, 현재 쓰레드에 저장된 값과 메인 메모리에 저장된 값을 비교하여 일치하는 경우 새로운 값으로 교체하고 일치하지 않는다면 실패하고 재시도를 한다. 이렇게 하면 CPU캐시에서 잘못된 값을 참조하는 가시성 문제가 해결된다. 연산의 결과는 쓰기가 제대로 이루어졌는지 나타낸다. 이 연산은 atomic하기 때문에 새로운 값이 최신의 정보임을 보장한다.

 

구현은 다음과 같다. CAS란 특정 메모리 위치의 값이 주어진 값을 비교하여 같으면 새로운 값으로 대체된다.

 int compare_and_swap(int* reg, int oldval, int newval)
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval)
     *reg = newval;
  return old_reg_val;
}

ABA Problem

CAS연산에서 공유 객체에 대한 변화를 감지하지 못할 때 발생하는 현상을 ABA현상이라고 한다.

 

 

쓰레드 1와 쓰레드 2 그리고 쓰레드 3이 있다고 하자.

쓰레드1은 pop연산을 하려 한다. pop을 하려는 쓰레드1 1은 top을 A로 저장하고 next를 B로 저장할 것이다.

그러나 중간에 다른 쓰레드 2가 끼어들고 A랑 B를 둘다 pop을 해버린다. 그런데 다시 쓰레드 3이 중간에 A의 주소를 그대로 Push해버렸다. 그래서 CAS체크를 하면 Fail이 뜨지 않는다. CAS는 주소가 맞다고 감지하고 그럼 이미 pop해서 FreeList에 있는 B가 스택의 Top이 되어버린다. CAS만으로 주소 값을 비교하다보니 일관성을 보장하기 힘들다.

 

이러한 ABA문제의 해결책으로는 double check CAS 이 있다. pop의 Count를 포함한 double check를 통해서

주소값을 CAS해주고, pop한 count 또한 CAS해주면서 일관성을 보장해준다.

CAS(&s->top, top, new_top) && CAS(&->pop_count, pop_count, pop_count+1)

 

https://wannabe-gosu.tistory.com/29