# 동기 처리 1

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

# 레이스 컨디션(race condition)

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

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

![](https://i.imgur.com/bhPAqcp.png align="left")

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

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

---

# 아토믹 처리

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

## Compare and Swap

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

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

```C
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코드는 이러한 작업을 사람이 읽기 쉬운 변수들로 구현하였으나 레지스터 단위에서 이 작업들이 일어나는 것이 다를 뿐 근본적으로 큰 차이는 없다.

```plaintext
	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`을 제공한다.

```C
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`함수와 완전히 동일하다. 이 함수는 다음 어셈블리 코드로 변환되는데

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

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

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

```c
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로 줄일 수 있다. 이는 코드로

```C
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`함수와 작동 원리가 다르다.

```C
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`을 이용해 아토믹으로 구현이 가능하다.

```C
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개**로 제한한다.

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

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

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

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

![](https://i.imgur.com/a69xgXR.png align="left")

이러한 상황이다.

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

따라서 이를 방지하려면

```C
bool lock = false;

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

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

## 스핀락

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

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

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

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

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

```C
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에서도 뮤텍스를 이용할 수 있다. 일반적으로는 이렇게 직접 구현하는 것보다 라이브러리에서 제공하는 뮤텍스를 이용하는 것이 바람직하다.

```C
#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인 세마포어인 것으로, 세마포어는 일반화한 뮤텍스로도 볼 수 있겠다.

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

```C
#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에서의 구현

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

## 뮤텍스

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

```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**하다.

## 조건 변수

```rust
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();
}
```