[운영체제] 락 TAS vs CAS

병행성 문제와 락의 필요성

병행 프로그래밍에서는 여러 명령어를 동시에 실행하고 싶지만, 단일 프로세서의 인터럽트나 멀티 스레드 환경에서도 자원 공유로 인해 의도한 대로 병행 실행이 어려운 경우가 발생합니다.

이를 해결하기 위해서 락을 사용해 임계 영역을 보호하고, 해당 영역 내에서는 명령어들이 원자적으로 실행되도록 합니다.

즉, 개ㅁ발자는 동시 접근이 발생할 수 있는 코드 영역을 락을 감싸서, 하나의 스레드만 해당 영역을 실행할 수 있게 해야 합니다.

임계 영역 예제 코드

간단한 임계 영역의 예제를 통해서 락을 적용하는 과정을 확인해보겠습니다.

임계 영역의 코드는 다음과 같습니다.(코드는 C++을 기준으로 작성합니다.)

balance = balance + 1;

락을 사용하기 위해서 락으로 감싼 임계 영역의 코드는 다음과 같습니다.

lock_t mutex; // 글로벌 변수 락
...
lock(mutex); // 락 시작
balance = balance + 1; // 임계 영역
unlock(&mutex); // 락 해제

락의 상태와 동작 방식

락은 하나의 변수로 관리되며, 이를 사용하려면 락 변수(mutex 등) 를 먼저 선언해야 합니다. 이 변수는 락의 상태를 나타내는데, 보통 두 가지 상태가 있습니다.

사용 가능(available) 또는 해제(unlocked): 어떤 스레드도 락을 점유하고 있지 않은 상태
사용 중(acquired): 특정 스레드가 락을 점유하고 있는 상태

스레드가 임계 영역에 진입을 하기 위해선 락을 획득(lock)해야 하고, 락을 사용하고 나서는 해제(unlock)해야 합니다.

만약 락이 이미 다른 스레드에 의해 사용 중이라면, 다른 스레드는 락을 획득할 때까지 대기합니다. 락을 획득하고 임계 영역에 들어간 스레드는 락의 소유자(owner) 라고 부릅니다.

락 사용 중 대기와 해제 이후 처리

한 스레드가 락을 점유하고 있는 동안, 다른 스레드가 lock()을 호출하면 반환되지 않고 대기하게 됩니다.

이는 락을 보유한 스레드가 임계 영역에 진입 중일 때, 다른 스레드가 동시에 임계 영역에 들어가는 것을 방지하기 위해서입니다.

락의 소유자가 unlock()을 호출하면 락은 다시 사용 가능한 상태가 되고, 대기 중이던 다른 스레드가 락을 획득해 임계 영역에 진입할 수 있습니다. 이런 락 기반 제어 방식은 여러 스레드가 동시에 임계 영역에 접근하는 것을 막아, 데이터 무결성 보장과 순차적 실행 흐름의 제어가 가능하게 해줍니다.

실제 환경에서의 락 구현 방식

실제 운영체제나 라이브러리에서는 락을 직접 제공하거나, 이를 구현할 수 있는 API를 제공합니다.

대표적인 예가 바로 POSIX 스레드(POSIX thread, pthread)에서 제공하는 mutex 락입니다.

이제 POSIX 환경에서 락을 어떻게 사용하는지를 살펴보겠습니다.

POSIX 환경에서의 락, pthread_mutex

위에서 살펴본 락의 개념은 실제로는 POSIX 라이브러리의 pthread_mutex를 통해 구현할 수 있습니다.

이때 사용하는 락은 mutual exclusion의 약자로, 스레드 간 상호 배제를 보장해주는 역할을 합니다.

사용 예시

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);   // 임계 영역 진입 전 락 획득
balance = balance + 1;       // 공유 자원 접근
pthread_mutex_unlock(&lock); // 임계 영역 탈출 후 락 해제

pthread_mutex_lock() 함수를 호출하면 락이 걸리고, 락이 해제되기 전까지 다른 스레드는 임계 영역에 진입할 수 없습니다.

이처럼 락을 통해 임계 영역을 보호하면 동시에 여러 스레드가 하나의 공유 자원에 접근하는 문제를 방지할 수 있습니다.

또한 POSIX 방식은 변수명을 지정해 직접 락을 걸기 때문에, 락의 범위를 세밀하게 조절할 수 있는 장점이 있습니다.

락을 전체 범위에 걸어 동시성은 낮지만 구현이 쉬운 거친 락(Coarse-grained) 전략과, 락을 가능한 한 작게 분할하여 병렬성을 높이는 세밀한 락(Fine-grained) 전략으로 나눌 수 있습니다.

POSIX에서 제공하는 mutex와 같은 락을 사용하면 여러 스레드 간의 충돌을 효과적으로 제어할 수 있습니다. 프로그래머는 간단한 API 호출로 임계 영역을 보호할 수 있지만, 이처럼 간단한 사용법 뒤에는 운영체제와 하드웨어의 복잡한 동작이 숨어 있습니다.

그렇다면 이러한 락은 어떻게 만들어질까요?

단순히 락이라는 변수 하나로 동기화가 이뤄지는 것처럼 보이지만, 실제로는 하드웨어 명령어와 운영체제의 핵심 기능들이 뒷받침되고 있습니다.

락 구현, 효율적인 락을 만드는 방법

락은 단순히 변수 하나로 구성된 것처럼 보일 수 있지만, 실제로는 다양한 하드웨어와 운영체제의 지원이 필요합니다.

락이 효율적으로 작동하기 위해서는 아래와 같은 조건이 충족되어야 합니다.

낮은 비용의 상호 배제 기능을 제공
여러 스레드가 동시 접근을 해도 데이터 무결성 보장
가능한 병렬성을 해치지 않음

이를 위해 현대 운영체제는 하드웨어의 명령어 수준의 지원을 기반으로 락을 구현합니다. 예를 들어, CPU는 atomic한(read-modify-write) 연산을 제공하고, 운영체제는 이를 기반으로 상호 배제를 보장할 수 있는 라이브러리를 만듭니다.

효율적인 락을 구현하려면 단순히 동작하는 것만으로는 충분하지 않습니다.

락이 어떻게 동작해야 이상적인지, 즉 좋은 락의 기준이 무엇인지 먼저 명확히 이해해야 구현의 방향도 잡을 수 있습니다.

다음은 락의 핵심 목표와 평가 기준을 정리했습니다.

락의 평가 기준

락을 잘 만들기 위해서는 좋은 락의 조건을 정의해야 합니다. 운영체제에서는 주로 다음 3가지 기준을 고려합니다.

(1) 상호 배제

가장 기본적인 락의 기능으로, 하나의 임계 영역에 동시에 여러 스레드가 진입하지 못하도록 보장해야 합니다.

(2) 공정성

모든 스레드에게 락을 얻을 수 있는 기회를 공평하게 제공해야 합니다.

(3) 성능

락의 오버헤드가 낮고, 임계 영역에서 락을 얻기 위한 경쟁 지연을 최소화 해야 합니다.

특히, 락을 기다리는 동안 CPU 자원이 낭비되지 않아야 합니다.

앞서 락의 기본 목표와 구현 시 고려할 평가 기준에 대해 살펴보았습니다.이제부터는 이러한 기준을 바탕으로 실제 운영체제에서 사용된 다양한 락 구현 방식들을 구체적으로 살펴보겠습니다.

락의 구현 방식들

인터럽트 비활성 방식

인터럽트 비활성화 하는 방법을 구현한 코드는 아래와 같습니다.

void lock() {
    DisableInterrupts();
}
void unlock() {
    EnableInterrupts();
}

인터럽트 비활성 방식은 단일 CPU 환경에서 인터럽트를 막는 것으로 임계 구역을 보호합니다.

실행 중에 인터럽트가 발생하지 않기 때문에, 코드가 원자적으로 실행됩니다.

장점

코드도 짧고 이해하기 쉬워 간단합니다.
인터럽트가 발생하지 않기 때문에 다른 스레드가 끼어들 수 없습니다.

단점과 한계

특권 권한이 필요합니다.
- 일반 사용자 프로세스가 사용할 수 없고 ,운영체제만 사용할 수 있는 명령어입니다.
악용이 가능합니다.
- 어떤 프로세스가 DisableInterrupt() 후 무한 루프에 빠지게 되면, 운영체제가 제어권을 잃습니다.
멀티코어에서는 무효입니다.
- 하나의 CPU에서 인터럽트를 막아도 다른 CPU의 실행에는 영향을 주지 못합니다.
- 멀티코어 환경에서는 동기화가 깨질 수 있습니다.
실시간 응답성이 저하됩니다.
- 오랜 시간 인터럽트를 막는 경우, 중요한 하드웨어 이벤트를 놓칠 수 있습니다.
비효율적입니다.
- 현대 CPU에서는 인터럽트 제어 명령이 비교적 느립니다.

Test-And-Set 기반의 스핀락

단일 CPU에서는 DisableInterrupt()를 통해 임계 영역을 보호할 수 있었지만, 멀티프로세서 환경에서는 무의미합니다.

이러한 문제를 해결하기 위해 시스템 설계자들이 하드웨어 수준의 동기화 명령어를 도입합니다. Test-And-Set이 대표적인 예시입니다.

먼저 Test-And-Set을 활용하지 않는 간단한 플래그 락 구현 코드는 아래와 같습니다.

typedef struct { int flag; } lock_t;

void init(lock_t *mutex) {
    mutex->flag = 0; // 0: lock free, 1: lock held
}

void lock(lock_t *mutex) {
    while (mutex->flag == 1); // spin-wait
    mutex->flag = 1;          // acquire lock
}

void unlock(lock_t *mutex) {
    mutex->flag = 0;          // release lock
}

flag == 0 이면 락을 획득할 수 있고, 1이면 다른 스레드가 점유중임을 나타냅니다. 또한, 스레드는 락이 풀릴 때까지 spin-wait 하며 기다립니다.

문제점

(1) 정확성 문제

두 스레드가 flag == 0 인 걸 동시에 확인한 뒤, 동시에 flag = 1을 실행하는 동시성 문제가 발생할 수 있습니다. 이로 인해서 둘 다 임계 구역에 들어가게 되는 오류가 발생하게 됩니다.

(2) 성능 문제

while(mutex -> flag == 1) 구문은 락이 풀릴 때까지 계속 CPU를 사용합니다. 즉, 단일 프로세서 시스템에서는 락을 가진 스레드조차 CPU를 점유하지 못하는 문제가 발생됩니다.(기다리는 스레드만 무한 루프를 돌며 CPU 자원 낭비)

플래그 기반의 스핀락이 가지는 문제점을 해결하기 위해 Test-And-Set 명령어를 사용한 스핀락이 등장하게 됩니다.

Test-And-Set은 하드웨어가 제공하는 원자적 연산으로, 메모리 값을 읽으면서 동시에 새로운 값을 설정할 수 있습니다.

즉, 두 개의 연산이 하나로 묶여 있기 때문에 동시성 문제 없이 상호 배제를 보장해줍니다.

Test-And-Set을 활용한 스핀락은 아래와 같이 구현할 수 있습니다.

typedef struct { int flag; } lock_t;

void init(lock_t *lock) {
    lock->flag = 0;
}

// 가상의 TestAndSet 함수
int TestAndSet(int* ptr, int new) {
    int old = *ptr; // old_ptr의 이전 값을 가져옵니다.
    *ptr = new; // old_ptr에 new값을 저장합니다.
    return old; // old의 값을 반환합니다.
}

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1); // flag가 0이 될 때까지 spin
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

동작 방식

락을 보유한 스레드가 flag = 1 상태를 유지하고 있는 동안, 다른 스레드들은 while (TestAndSet(flag, 1) == 1) 구문을 반복해서 실행합니다.

이때, 락을 이미 보유 중인 상태라면, TestAndSet() 호출은 1을 반환하며 다시 1을 쓰게 됩니다.

반면, 락이 해제되어 flag가 0이 되는 순간, 대기 중인 스레드 중 하나가 TestAndSet()을 호출하여 0을 반환받고 동시에 flag를 1로 설정하여 임계 영역에 진입하게 됩니다.

이 과정은 하드웨어 수준의 원자적 연산으로 보장되므로, 두 스레드가 동시에 락을 획득하는 일은 없습니다.

스핀락의 단점

Test-And-Set 기반 스핀락은 정확성을 보장하지만, 성능 상의 단점이 존재합니다.

락을 얻지 못한 스레드는 계속 루프를 돌면서 CPU를 점유합니다.
단일 프로세서 환경에서는 락을 보유한 스레드조차 CPU를 얻지 못해 진행 불가 상태가 될 수 있습니다.

이러한 단점으로 인해서 단일 CPU 환경에서는 반드시 선점형 스케줄러가 필요합니다. 그래야만 타이머 인터럽트로 CPU를 다른 스레드에게 넘길 수 있기 때문입니다.

스핀 락 평가

스핀 락은 공정성을 보장하지 않으며, 경쟁에서 밀린 스레드는 락을 영원히 얻지 못할 수 있습니다. 또한 락을 얻기 위해 CPU를 점유한 채 while 루프를 도는 구조이기 때문에 단일 CPU 환경에서는 상당한 오버헤드를 유발합니다. 반면, 다중 CPU 환경에서 락 대기 시간이 짧고 락이 자주 해제되는 상황이라면 스핀 락은 빠르고 효율적인 락 구현이 될 수 있습니다.

즉, 스핀 락은 멀티코어 환경에서 락 대기 시간이 짧고 빠른 응답성이 중요한 상황에서 사용할 때 효과적인 동기화 방식입니다. 하지만 락을 기다리는 시간이 길어질 가능성이 있거나, 단일 CPU 환경이라면 적절한 동기화 방식이 아닐 수 있습니다.

Compare-And-Swap(CAS)

Compare-And-Swap은 여러 CPU 아키텍처(SPARC, x86등)에서 제공하는 원자적 연산입니다. 이 연산은 다음 3가지 인자를 받습니다.

ptr : 값을 바꾸고 싶은 대상 주소
expected : 기대하는 기존 값
new : 바꾸고자 하는 새로운 값

int CompareAndSwap(int* ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

이 코드는 *ptr값이 expected와 같으면 new로 바꾸고, 결과적으로 실제 값을 반환합니다

만약 값이 다르면 아무 것도 하지 않고 기존 값만 반환하게 됩니다.

즉, 메모리 상의 값이 기대값과 일치할 때만 변경하는 방식입니다. 이 과정은 하드웨어 수준에서 원자적으로 보장되기 때문에 스레드 간 경쟁 상황에서도 안전하게 사용할 수 있습니다.

void lock(lock_t* lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1);
}

이 코드는 스핀 락을 구현할 때 매우 자주 사용됩니다.

1. lock->flag가 0이면 CAS는 성공하여 락을 획득하고 루프를 빠져나옵니다.

2. 이미 누군가 락을 잡고 있어서 값이 1이라면 CAS는 실패하고 다시 반복합니다.

해당 방식은 Test-And-Set과 유사하지만, 더 강력한 조건 비교를 통해 락 획득 경쟁을 보다 정밀하게 제어할 수 있습니다.

어셈블리 레벨 구현(x86)

char CompareAndSwap(int* ptr, int old, int new) {
    unsigned char ret;
    __asm__ __volatile__ (
        "lock\n"
        "cmpxchgl %2, %1\n"
        "sete %0\n"
        : "=q" (ret), "=m" (*ptr)
        : "r" (new), "m" (*ptr), "a" (old)
        : "memory"
    );
    return ret;
}

이 코드는 어셈블리 수준에서 원자성 보장과 함께, CPU 사이클 하나로 변경 여부를 결정합니다.

Compare-And-Swap의 장점

Compare-And-Swap은 Test-And-Set 보다 더 강력한 동기화 매커니즘을 가집니다.

Wait-Free Synchronized을 구현할 수 있는 기반 연산이 되고, 스핀 락, 뮤텍스, 락 프리 큐(lock-free queue)등 다양한 병렬 프로그래밍 기법에서 기본적으로 사용됩니다.

Test-And-Set vs Compare-And-Swap

이처럼 락을 구현하는 원자적 연선에는 대표적으로 TAS와 CAS가 있습니다.

하지만, 두 방식은 구현은 비슷해 보여도 성능과 효율 면에서 큰 차이가 존재합니다.

먼저, TAS 코드는 아래와 같습니다.

int TestAndSet(int* ptr) {
    int old = *ptr;
    *ptr = 1;  // 무조건 1로 덮어씀
    return old;
}

void lock(lock_t* lock) {
    while (TestAndSet(&lock->flag) == 1);  // flag가 0이 될 때까지 반복
}

TAS의 문제점은 락을 이미 누군가가 잡고 있어도 무조건 flag = 1로 덮어씁니다.

여러 스레드가 계속해서 메모리에 쓰기 연산을 하기 때문에 CPU 캐시 병목이 발생하여 성능이 급격하게 떨어질 수 있습니다.

int CompareAndSwap(int* ptr, int expected, int new) {
    int old = *ptr;
    if (old == expected) {
        *ptr = new;  // 기대한 값일 때만 바꿈
    }
    return old;
}

void lock(lock_t* lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1);
}

CAS는 flag == 0 일때만 1로 바꾸므로, 조건이 맞을 때만 쓰기 연산이 일어납니다.

락을 이미 누군가 잡고 있으면 단순하게 읽기만 하기 때문에, 캐시 충돌이 줄고 성능이 향상됩니다.

또한, 정밀하게 락 획득 경쟁 제어가 가능합니다.

만약 1000만개의 스레드가 동시에 하나의 자원에 접근을 하게되는 극한 상황에서는 TAS는 1000만개 스레드가 전부 메모리에 쓰기 연산을 시도하게 됩니다. 이로 인해 CPU간 캐시 일관성 프로토콜이 폭발적으로 작동하면서 성능이 급격히 저하 됩니다.

반면, CAS는 락이 풀릴 순간에만 단 하나의 스레드만 write를 시도하게 디고, 나머지 스레드들은 캐시 일관성에 거의 영향을 주지 않아서, 불필요한 메모리 버스 트래픽이 크게 줄어듭니다,

'CS' 카테고리의 다른 글

[운영체제] 캐시 일관성과 MESI 프로토콜 (0)	2025.04.25
[OS] 메모리 관리 전략 (0)	2025.03.09
[네트워크] TCP 제어 방법 (0)	2025.02.15
프로세스와 스레드 (2)	2025.02.12
[DB] 트랜잭션 (0)	2025.02.09

꼬질꼬질

[운영체제] 락 TAS vs CAS

병행성 문제와 락의 필요성

임계 영역 예제 코드

락의 상태와 동작 방식

락 사용 중 대기와 해제 이후 처리

실제 환경에서의 락 구현 방식

POSIX 환경에서의 락, pthread_mutex

사용 예시

락 구현, 효율적인 락을 만드는 방법

락의 평가 기준

락의 구현 방식들

인터럽트 비활성 방식

Test-And-Set 기반의 스핀락

문제점

동작 방식

스핀락의 단점

스핀 락 평가

Compare-And-Swap(CAS)

어셈블리 레벨 구현(x86)

Compare-And-Swap의 장점

Test-And-Set vs Compare-And-Swap

'CS' 카테고리의 다른 글

티스토리툴바

[운영체제] 락 TAS vs CAS

병행성 문제와 락의 필요성

임계 영역 예제 코드

락의 상태와 동작 방식

락 사용 중 대기와 해제 이후 처리

실제 환경에서의 락 구현 방식

POSIX 환경에서의 락, pthread_mutex

사용 예시

락 구현, 효율적인 락을 만드는 방법

락의 평가 기준

락의 구현 방식들

인터럽트 비활성 방식

Test-And-Set 기반의 스핀락

문제점

동작 방식

스핀락의 단점

스핀 락 평가

Compare-And-Swap(CAS)

어셈블리 레벨 구현(x86)

Compare-And-Swap의 장점

Test-And-Set vs Compare-And-Swap

'CS' 카테고리의 다른 글

관련글

티스토리툴바