[Concurrency] Test And Set (TAS)

Test And Set(이하 TAS)는 동시성 환경에서의 동기화를 구현하기 위한 기법 중 하나다.

Compare And Swap이 Lock-free를 구현하기 위한 연산 단위로 응용된다면, TAS는 Spin-Lock을 구현하는데 주로 사용된다. Mutex 같은 lock 기반의 동기화 매커니즘은 보통 이런걸 통해 구현된다고 보면 된다.

아래는 TAS의 원리를 나타내는 C 코드다.

// lock을 획득하지 못했으면 true 반환
// lock을 획득했다면 true로 설정하고 false 반환
bool test_and_set(bool* locked) {
    if(*locked) {
        return true;
    } else {
        *locked = true;
        return false;
    }
}

이미 lock을 점유하고 있다면 true를 반환하고, 아니라면 false를 반환한다.

이걸 응용하면 바로 Spin-Lock을 통해 동기화를 구현할 수 있다.
아래는 방금 작성한 test_and_set을 이용한 spin-lock의 구현례다.

... 
bool lock = false; // lock용 공유변수
...

// A thread
void spawn_thread(bool* lock) {
    // lock을 점유할 때까지 무한루프로 대기 (Spin-Lock)
    while(!test_and_set(lock));

    // 점유했을 경우 진입
    ...작업

    // lock 해제
    *lock = false;
}

다만 이 코드는 개념을 보여주기 위해 작성한 것이라 실제로 atomic하게 동작하지는 않는다.

대신 gcc나 clang에서는 atomic한 TAS 함수로 __sync_lock_test_and_set이라는 함수를 제공한다.
저런걸 쓰면 된다.

어셈블리 수준 (x86-64)

C에서 특수한 함수의 형태로만 구현이 가능한 것을 보면 알겠지만, 이건 CPU의 명령에 의존적인 기능이다.
x86 프로세서에서 TAS는 "xchgb"와 같은 명령을 통해 제공된다.

movb $1, %al
xchgb %al, (%rdi) ; TAS
...

효율성?

사실 TAS 기반의 스핀락은 효율성이 딱히 좋은편이 아니다.

일반적인 소프트웨어 수준에서는 Mutex 같은 기본 락을 사용하는 것보다 훨씬 느리고 비효율적이다.
스핀락이 좋은 성능을 보여주는 것은 매우 극단적인 상황 뿐이니, 일반적으로는 쓰지 않는 것을 권장한다.

스레드의 수가 물리 코어의 수를 넘지 않고, 할당이 많지 않을 경우에는 스핀락이 좋을 수 있다고 한다.

참조
https://en.wikipedia.org/wiki/Test-and-set
https://stackoverflow.com/questions/3659336/compare-and-swap-vs-test-and-set
https://mmomtchev.medium.com/spinlock-vs-mutex-performance-3f73de53a460