스핀락, 뮤텍스, 세마포어, 모니터 모두 하나의 Thread가 임계영역을 Lock한 후 작업을 수행하는 절차이다.
하지만 sychronized화 하게 되면 한 개의 Thread가 해당 블락을 전체 lock(점유)하기 때문에 다른 Thread는 아무작업을 하지 못하게 되고
이로 인해서 기다리는 상황이 발생하고 낭비가 심해진다.
그래서 Non-blocking한 방법, Lock-Free한 방법으로 동기화 문제를 해결하기 위한 방법이 바로 Atomic연산이다.
그리고 이 동작의 핵심 원리는 CAS(Compare And Swap)에 있다.
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;
}
C
복사
Benefits
CAS, 그리고 다른 atomic instruction은 uniprocessor system에서는 필요가 없다.
왜냐하면 어떤 명령이든 atmoicity가 interrupts를 비활성화 함으로써 달성될 수 있기 때문이다. 하지만 interrupt를 비활성화하는 것은 매우 많은 단점들을 가진다.
예를 들면 interrupt를 비활성화 할 수 있는 코드들은 반드시 신뢰되는 코드여야 하고, CPU를 독점하지 않아야 하고, 또한 절대 무한 루프에 빠져서는 안된다. 게다가 interrupts를 비활성화 한다는 것은 현실적으로 매우 비쌀 수 있다. 그러므로 uniprocessor 머신에서 실행되는 프로그램이라고 할 지라도 atomic instructions로 부터 큰 이득을 얻을 수 있다. 예를 들면 Linux's futexes.
multiprocessor system에서는 보통 모든 프로세서에 대해 interrupts를 disable하는 것은 불가능 하다. 그것이 가능하다 할 지라도 2개 혹은 그 이상의 프로세서들은 같은 semaphore의 메모리에 동시에 접근할 수도 있기 때문에 atomicity가 확보되지 않는다. compare-and-swap 명령은 어떤 processor라도 atomic하게 메모리 위치를 수정하고 multiple-processor 충돌도 방지할 수 있다.