Compare And Swap(CAS) 아주 간단하게 훑기

https://en.wikipedia.org/wiki/Compare-and-swap

Compare-and-swap - Wikipedia

 

Compare And Swap은 멀티스레딩 환경에서 동기화를 위해서 사용되는 원자적 연산이다.

원자적 연산이기 때문에 CPU에서 하나의 연산으로 실행되며, 실행 중간에 다른 연산이 끼어들 수 없도록 보장된다.

 

이러한 보장은 멀티스레드를 이용한 프로그래밍에서 중요한 단서로 사용된다.

 

 

기본 동작

이름 처럼 비교하고 값을 바꾸는 역할을 한다.

원자성이 보장되므로 연산 중 다른 스레드에 의해 값이 변경되었다면 이를 즉시 확인할 수 있고 변경됐으면 write 작업이 실패한다.

 

CAS 연산은 교체 작업의 성공 여부를 반환해야 한다. 방식은 크게 두 가지가 있다.

1. boolean값 반환: 연산 성공 시 true, 실패 시 false를 반환해 확인

2. 읽은 값 반환: 기존의 값을 반환해 읽은 값과 쓰려는 값을 swap하는 효과를 가짐

 

CAS는 락을 사용하지 않아도 동기화할 수 있게 하며, lock free 구조에서 핵심적으로 사용된다.

 

function cas(p: pointer to int, old: int, new: int) is
    if *p != old
        return false

    *p ← new

    return true

 

value가 old와 다르다면 false를 반환하고, 같다면 value에 new를 대입한 후 true를 반환한다.

이 과정이 원자적으로 일어난다.

 

 

ABA 문제

멀티스레드 환경에서 CAS 연산을 수행할 때 중간에 값이 두 번 변경되어 원래 값으로 돌아오는 경우 발생하는 문제이다.

 

#include <iostream>
#include <atomic>
#include <thread>
#include <chrono>

std::atomic<int> shared_value(100); // 공유 변수 초기값 100

void thread_A() {
    int old_value = shared_value.load(); // 현재 값 읽기 (100)
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // 다른 스레드가 개입할 시간 부여

    // CAS 시도: shared_value가 여전히 old_value(100)면 200으로 변경
    if (shared_value.compare_exchange_strong(old_value, 200)) {
        std::cout << "[Thread A] CAS 성공: " << shared_value.load() << std::endl;
    } else {
        std::cout << "[Thread A] CAS 실패: " << shared_value.load() << std::endl;
    }
}

void thread_B() {
    std::this_thread::sleep_for(std::chrono::milliseconds(50)); // Thread A보다 늦게 실행되도록 대기

    shared_value.store(150); // 값 변경 (100 → 150)
    std::cout << "[Thread B] shared_value = 150 변경" << std::endl;

    shared_value.store(100); // 다시 원래 값으로 복원 (150 → 100)
    std::cout << "[Thread B] shared_value = 100 복원 (ABA 발생)" << std::endl;
}

int main() {
    std::thread t1(thread_A);
    std::thread t2(thread_B);

    t1.join();
    t2.join();

    return 0;
}

 

멀티스레드 환경에서 여러 코드가 함께 실행될 때 순서를 알 수 없기 때문에 만약에 다음과 같은 순서로 진행된다고 생각해보자.

 

1. thread_A가 값을 100으로 읽는다.

2. thread_B가 값을 150으로 변경하고 다시 100으로 바꾼다.

3. thread_A는 값이 100이기 때문에 CAS를 사용해 200으로 바꾼다.

 

이러한 상황에서 100이라는 값 자체는 맞지만 그 사이에 B가 실행되면 안됐을 수도 있고, 할당하는 과정에서 메모리가 변경되었을 수도 있다. 

같은 100이지만 다른 의미를 가질 수도 있다는 것이다.

하지만 thread_A는 B에서 변경되었다는 사실을 인지할 수 없기 때문에 문제가 생긴다.

 

DCAS같은 것으로 해결한다고 하는데 일단은 이러한 문제가 있다는 것만 기억하고 넘어가야겠다.

 

 

프로그래밍 언어에서의 CAS

c#과 c++에서 지원하는 CAS 연산에 대해 간단하게 보면 다음과 같다.

 

c#은 Interlocked.CompareExchange()를 통해서 CAS를 수행할 수 있다.

CompareExchange(ref location, newValue, expectedValue)를 인자로 한다.

비교하려는 값(location)이 expectedValue와 같다면 newValue로 바꾸고 기존 값을 반환한다.

다르다면 변경 없이 기존 값을 반환한다.

 

c++은 두 가지 방법을 지원한다.

1. compare_exchange_strong: c#의 Interlocked.CompareExchange와 동작이 비슷하다.

2. compare_exchange_weak: CAS연산을 하지만 거짓 실패(Spurious Failure)가 발생할 수 있다.

c#의 함수 둘다 반환 값으로는 성공 여부를 나타내는 boolean 값을 반환한다.