여기서는 동기 처리가 필요한 이유(레이스 컨디션)을 설명하고 뮤텍스에서 조건 변수까지를 설명한다.

레이스 컨디션(race condition)

레이스 컨디션은 한국어로는 경합 상태라고 불리며 여러 프로세스가 동시에 공유하는 자원에 접근함에 따라 일어나는 예상치 않은 이상이나 상태를 의미한다.

레이스 컨디션의 예로 아래 그림을 들 수 있다. 아래 그림은 공유 메모리상의 변수를 여러 프로세스가 증가시키는 상황을 나타낸다,

프로세스 B가 2를 쓰는 시점까지는 문제가 없어 보이나, A 프로세스가 2를 읽어온 이후 A가 이를 다시 쓰기 전에 B가 공유 변수를 읽어와버린다. 결과적으로 B가 3이 아닌 2를 읽어오게 되고 기댓값인 4 대신 3을 내놓는다.

이처럼 동시성 프로그래밍에서 예기치 못한 결함에 빠지는 것을 레이스 컨디션이라고 한다. 그리고 레이스 컨디션을 일으키는 프로그램 코드 부분을 크리티컬 섹션이라고 하는데, 레이스 컨디션을 방지하기 위해서는 크리티컬 섹션을 보호하는 장치들이 필요할 것이다.

---

아토믹 처리

아토믹 처리란 더 이상 나눌 수 없는 단일한 작업 단위를 의미한다. 즉, 다른 쓰레드나 프로세스가 끼어들 수 없다는 것이다. 현대 컴퓨터상의 동기 처리 대부분은 이러한 아토믹 명령에 의존하고 있다.

Compare and Swap

Compare and Swap은 동기 처리 기능의 하나인 세마포어, 락프리, 웨이트프리한 데이터 구조를 구현하기 위해 이용하는 처리다. 줄여서 CAS라고 한다.

다음 코드를 통해 CAS의 의미를 파악해볼 수 있다.

bool compare_and_swap(uint64_t *p, uint64_t val, uint64_t newval)
{
    if (*p != val) {
    // *p의 값이 val과 다르면 false를 반환
        return false;    
    }
    // *p의 값이 val과 같으면 *p에 newval을 대입하고 true를 반환
    *p = newval;
    return true;
}

어셈블리에서도 같은 작업이 가능한데 기본적으로는 레지스터의 값을 비교하고 비교 결과를 통해 특정 라벨로 점프하는 로직이다. C코드는 이러한 작업을 사람이 읽기 쉬운 변수들로 구현하였으나 레지스터 단위에서 이 작업들이 일어나는 것이 다를 뿐 근본적으로 큰 차이는 없다.

    cmpq %rsi, (%rdi)
    jne LBB0_1
    movq %rdx, (%rdi)
    movl $1, %eax
    retq
LBB0_1:
    xorl %eax, %eax
    retq

위에서 rdi, rsi, rdx가 함수의 첫번째, 두번째, 세번째 인수로 이용된다. 즉 각각이 p, val, newval에 해당한다.

그런데 위의 C함수는 아토믹하지 않다! 이유는 *p != val검사와 *p = newval 사이에 다른 쓰레드가 끼어들 수 있기 때문이다. 따라서 여전히 레이스 컨디션이 발생할 여지가 있다.

그래서 gcc와 같은 컴파일러에서 이와 같은 조작을 아토믹으로 처리하기 위해 내장 함수 __sync_bool_compare_and_swap을 제공한다.

bool compare_and_swap(uint64_t *p, uint64_t val, uint64_t newval) 
{
    return __sync_bool_compare_and_swap(p, val, newval);
}

__sync_bool_compare_and_swap함수의 의미와 인수는 compare_and_swap함수와 완전히 동일하다. 이 함수는 다음 어셈블리 코드로 변환되는데

movq %rsi, %rax
xorl %ecx, %ecx
lock cmpxchgq %rdx, (%rdi)
sete %cl
movl %ecx, %eax
retq

두 번째 인수를 의미하는 rsi 레지스터의 값을 rax로 복사하고 ecx 레지스터 값을 0으로 초기화한다. 여기서 이제 차이가 발생하는데 cmpxchgq명령을 통해 아토믹하게 비교 및 교환된다.

cmpxchgq 명령은 다음 코드로 의미를 표현할 수 있는데

if (%rax == (%rdi)) {
    (%rdi) = %rdx
    ZF = 1
} else {
    %rax = (%rdi)
    ZF = 0
}

즉 rax 레지스터의 값과 rdi레지스터가 가리키는 메모리상의 값을 비교하고 같으면 rdi에 rdx의 값을 대입하고 ZF플래그를 1로 만든다. 만약 값이 다르면 rax에 rdi의 값을 대입하고 ZF플래그를 0으로 설정한다. 그러니까 의미 자체는 compare_and_swap함수와 같다는 건데 이것이 아토믹하게 일어날 뿐이다.

위의 로직이 하나의 시퀀스로 묶여 실행되고 중단되지 않는다. 그런데 멀티코어 환경에서 cmpxchgq만 쓰면 코어 간 레이스 컨디션은 보장되지 않을 수 있는데 lock 프리픽스를 붙여서 아토믹을 보장할 수 있다.

참고로 cmpxchgq에서 마지막 q의 의미는 명령어의 오퍼랜드 크기, 그러니까 64바이트를 의미하는 것이므로 위의 로직은 엄밀히는 cmpxchg를 설명한다고 보는 게 더 적절하겠다.

Test and Set

Test and Set은 TAS로 줄일 수 있다. 이는 코드로

bool test_and_set(bool *p) {
    if (*p) {
        return true;
    } else {
        *p = true;
        return false;
    }
}

즉 포인터 p가 가리키는 값이 true면 그대로 true를 반환하고 false를 가르키면 p가 가리키는 메모리의 값을 true로 설정하고 false를 반환한다.

아까 CAS처럼 이 자체로는 아토믹하게 실행되지 않는다. 또 gcc같은 C컴파일러에서는 내장 함수 __sync_lock_test_and_set을 제공해서 아토믹하게 작동할 수 있게 하는데, 이 함수는 아까와는 다르게 위의 test_and_set함수와 작동 원리가 다르다.

type __sync_lock_test_and_set(type *p, type val) {
    type tmp = *p;
    *p = val;
    return tmp;
}

아까와는 다르게 포인터 p에 더해 val이 두 번째 인자로 들어오고, tmp에 *p를 저장, *p에는 두 번째 인자인 val의 값을 넣어주고, 최종적으로 초기 *p의 값이 저장되었던 tmp가 반환된다.

이때 이 함수는 두번째 인수 val에 1(true)를 지정함으로써 TAS함수처럼 작동하게 된다.

따라서 __sync_lock_test_and_set을 이용해 아토믹으로 구현이 가능하다.

bool test_and_set(volatile bool *p) {
    return __sync_lock_test_and_set(p, 1);
}

Load-Link/Store-Conditional

x86-64와 x86에서는 lock명령 접두사를 사용해 메모리에 읽고 쓰기를 배타적으로 수행하도록 했다. 그 외 ARM, RISC-V 등에서는 Load-Link/Store-Conditional 명령을 이용해 아토믹 처리를 구현했다. 둘은 줄여서 LL과 SC라고 한다.

자세히 알아보자면, LL은 메모리를 배타적으로 읽도록 지정하는 명령어이고, SC명령어는 메모리 쓰기를 수행하는 명령어이다. LL명령어로 지정한 메모리로의 쓰기는 다른 CPU가 수행하지 않는 경우에만 쓰기가 성공한다.

---

뮤텍스

뮤텍스(Mutex) 는 MUTual EXecution의 약어로 배타 실행(Exclusive Execution)이라고도 하는 동기 처리 방법이다. 위에서 크리티컬 섹션은 레이스 컨디션이 발생할 수 있는 코드 영역이라고 했다. 뮤텍스는 이러한 크리티컬 섹션을 실행할 수 있는 프로세스 수를 최대 1개로 제한한다.

뮤텍스의 원리는 플래그를 이용해 크리티컬 섹션에서 실행될 프로세스를 제한하는 방식인데, 아래 코드와 같이 동작한다.

bool lock = false; // 공유 변수 정의

void some_func() {
retry: 
    if (!lock) { // 이미 다른 프로세스가 크리티컬 섹션 실행중인지?
        lock = true; // 사용중이다
    } else {
        goto retry;
    }
    lock = false; // 이제 사용중이 아님. 종료
}

언뜻 보기에 이 함수는 배타적 실행을 성공시킬 수 있을 것 같지만 잘 동작하지 않는 경우가 발생한다.

이러한 상황이다.

lock을 true로 바꾸기 전에 프로세스가 들어와 lock을 false로 인식하여 레이스 컨디션이 발생하게 되는 상황이다.

따라서 이를 방지하려면

bool lock = false;

void some_func() {
retry: 
    if (!test_and_set(&lock)) { // 락 획득
        // 크리티컬 섹션
    } else {
        goto retry;
    }
    tas_release(&lock); // 락 해제
}

그것을 위해 TAS를 이용해 아토믹하게 검사와 값 변경을 수행하는 것이다. 그렇다면 중간에 다른 프로세스가 끼어드는 것을 방지할 수 있다.

스핀락

위에서는 락을 얻을 때까지 루프를 반복했다. 이렇게 리소스가 비는 것을 기다리며 확인하는 락 획득 방법을 스핀락이라고 한다.

전형적으로 스핀락용 API는 락 획득용과 락 해제용 함수 두 가지가 제공되고

void spinlock acquire(bool *lock) {
    while (test_and_set(lock));
}

void spinlock_release(bool *lock) {
    tas_release(lock);
}

일반적으로 아토믹 명령은 실행 속도상의 패널티가 있어 호출 전에 검사를 하고 나는 방식을 추가하면 조금 더 효율적이다.

void spinlock_acquire(volatile bool *lock) {
    for (;;) {
        while (*lock);
        if (!test_and_set(lock))
            break;
    }
}

void spinlock_release(bool *lock) {
    tas_release(lock);
}

Pthreads의 뮤텍스

C의 Pthreads에서도 뮤텍스를 이용할 수 있다. 일반적으로는 이렇게 직접 구현하는 것보다 라이브러리에서 제공하는 뮤텍스를 이용하는 것이 바람직하다.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;

void* some_func(void *arg) {
    if (pthread_mutex_lock(&mut) != 0) {
        perror("pthread_mutex_lock"); exit(-1);
    }
    // 크리티컬 섹션

    if (pthread_mutex_unlock(&mut) != 0) {
        perror("pthread_mutex_unlock"); exit(-1);
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    //스레드 생성
    pthread_t th1, th2;
    if (pthread_create(&th1, NULL, some_func, NULL) != 0) {
        perror("pthread_create"); return -1;
    }
    // 스레드 종료 대기
    if (pthread_join(th1, NULL) != 0) {
        perror("pthread_join"); return -1;
    }
    if (pthread_join(th2, NULL) != 0) {
        perror("pthread_join"); return -1;
    }
    // 뮤텍스 객체 릴리즈
    if (pthread_mutex_destroy(&mut) != 0) {
        perror("pthread_mutex_destroy"); return -1;
    }
    return 0;
}

세마포어

뮤텍스에서는 락을 최대 1개 프로세스까지 획득할 수 있었다. 그렇다면 1개보다 많은 프로세스가 동시에 락을 획득하려면 어떻게 해야하는가? 세마포어를 쓰면 된다.

세마포어에서는 최대 N개 프로세스까지 동시에 락을 획득할 수 있는데, 여기서 N은 프로그램 실행 전에 임의로 결정할 수 있는 값이다.

그런고로 뮤텍스는 N이 1인 세마포어인 것으로, 세마포어는 일반화한 뮤텍스로도 볼 수 있겠다.

코드로 구현하면 아래와 같다.

#define NUM 4 // N

// 다수의 프로세스가 락을 획득했는지 알아야 하므로 int타입
void semaphore_acquire(volatile int *cnt) {
    for (;;) {
    // 공유 변숫값이 최댓값 NUM 이상이면 스핀하며 대기
        while (*cnt >= NUM);
        __sync_fetch_and_add(cnt, 1);
        // NULL 이하인지 검사하여 그렇다면 루프 벗어나기
        if (*cnt <= NUM) 
            break;
            __sync_fetch_and_sub(cnt, 1);
    }
}

void semapthore_release(int *cnt) {
    __sync_fetch_and_sub(cnt, 1);
}

세마포어는 물리적인 계산 리소스 이용에 제한을 적용하고 싶은 경우 등에 이용할 수 있다.

POSIX 세마포어

POSIX 규격을 따르는 세마포어 인터페이스이다. 표준적인 구현으로 볼 수 있다. POSIX 세마포어에서는 이름 있는 세마포어와 이름 없는 세마포어가 있는데, 이름 있는 세마포어는 슬래시로 시작해 널 문자열로 끝나는 문자열로 식별된다. 또한 이름 있는 세마포어는 파일로 공유 리소스를 지정할 수 있고, sem_open으로 생성과 열기, sem_close와 sem_unlink로 닫기와 파기를 수행한다.

---

조건 변수

조건 변수는 스레드 간의 동기화를 위한 도구로, 특정 조건이 만족될 때까지 스레드를 잠들게 했다가, 조건이 충족되면 스레드를 깨워 다시 실행하게 만드는 구조이다. 교차로에서 신호등같은 역할을 하는 것이다.

뮤텍스만 사용하게 되면 플래그가 true가 되었는지 반복해서 검사해야하기 때문에 Busy-Waiting 상태가 되는데, CPU 사용 면에서 비효율적이라고 할 수 있다. 확인하기 위해 CPU를 계속해서 깨워야하기 때문이다.

이를 위해 조건변수를 사용하게 된다.

---

Rust에서의 구현

러스트에서는 기본적인 동기 처리 라이브러리를 표준 라이브러리로 제공하는데, 아래와 같이 구현된다고 할 수 있다.

뮤텍스

아래 코드는 러스트에서 뮤텍스의 활용 예제를 나타낸다.

use std::sync::{Arc, Mutex}; //여기서 Arc는 참조 카운트 기반 스마트 포인터.
use std::thread; // 표준 스레드 생성 기능

fn some_func(lock: Arc<Mutex<u64>>) {
    loop {
        let mut val = lock.lock().unwrap(); // 락 획득
        *val += 1; // 값 증가
        println!("{}", *val); // 출력
    }
}

fn main() {
    let lock0 = Arc::new(Mutex::new(0)); 
    let lock1 = lock0.clone(); // Arc 복제(참조 카운트 증가)
    let th0 = thread::spawn(move || {
        some_func(lock0); // 첫 스레드 실행
    });
    let th1 = thread::spawn(move || {
        some_func(lock1); // 두 번째 스레드 실행
    });
    th0.join().unwrap();
    th1.join().unwrap();
}

러스트에서는 뮤텍스용 변수는 보호 대상 데이터를 보존하도록 되어 있어 접근하려면 반드시 lock을 해야한다.

C언어에서 보호 대상 데이터는 락을 하지 않아도 접근할 수 있는데, 그런 코드는 레이스 컨디션이 될 가능성이 있다.

자세히 설명하자면 러스트에서는

• Mutex<T> 자페가 T에 대한 소유권을 가지고 있다.

• 따라서 T에 직접 접근하려면 lock()을 통해 MutexGuard<T>를 획득해야 한다.

• 결론적으로 락 없이는 접근 불가가 된다.

그러나 C에서는 뮤텍스와 보호 대상 데이터를 따로 관리하므로 락 없이 접근하는 케이스가 생길 수 있고, 이 경우 레이스 컨디션이 된다.

한마디로 러스트에서는 락과 데이터를 결합해서 락을 통한 접근만 가능하고 타입에도 이를 강제하고 있으므로 safe하다.

조건 변수

use std::sync::{Arc, Mutex, Condvar}; //조건변수
use std::thread;

fn child(id: u64, p: Arc<(Mutex<bool>, Condvar)>) {
    // 대기 스레드용 함수 정의
    let &(ref lock, ref cvar) = &*p;
    // Arc 타입 내부에 포함된 뮤텍스와 조건변수를 꺼내기
    let mut started = lock.lock().unwrap();
    while !*started {
        // 시작 신호가 오기 전까지 대기
        started = cvar.wait(started).unwrap();
    }
    println!("Child thread {} started", id);
}

fn parent(p: Arc<(Mutex<bool>, Condvar)>) {
    // 시작 신호를 보내는 함수 정의
    let &(ref lock, ref cvar) = &*p;
    // 락을 한 뒤 공유 변숫값을 true로 설정하고 알림
    let mut started = lock.lock().unwrap();
    *started = true;
    cvar.notify_all();
    println!("Parent thread notified all children");
}

fn main() {
    let pair = Arc::new((Mutex::new(false), Condvar::new()));
    let pair0 = Arc::clone(&pair);
    let pair1 = Arc::clone(&pair);
    let pair2 = Arc::clone(&pair);

    let c0 = thread::spawn(move || {
        child(0, pair0);
    });
    let c1 = thread::spawn(move || {
        child(1, pair1);
    });
    let p = thread::spawn(move || {
        parent(pair2);
    });

    c0.join().unwrap();
    c1.join().unwrap();
    p.join().unwrap();
}