# 스레드 & 락 (chap.25-29)

### 멀티 스레드 프로그램

- 하나의 프로세스가 하나 이상의 실행 지점을 가진다. (독립적으로 불러 들여지고 실행될 수 있는 여러 개의 PC 값)

## 스레드

- 각 스레드는 프로세스와 유사하지만, 주소공간을 공유한다. → 동일한 자원에 접근할 수 있다.
- 각 스레드는 프로그램 카운터(PC)와 연산을 위한 레지스터들을 가지고 있다.
- 스레드 간의 문맥 교환은 프로세스의 문맥 교환과 유사
   - PCB 대신 TCB 사용
   - 하지만 주소 공간은 그대로 사용
- 스레드마다 스택이 할당
   - 스택에는 지역변수, 매개변수, 반환 값 등이 들어간다.

### 왜 스레드를 사용하는가?

1. 하나의 프로세스 내에서 병렬처리가 필요하다. → 병렬화 : 단일 스레드 프로그램을 멀티프로세서 상에서 같은 작업을 하는 프로그램으로 변환하는 작업
2. 스레딩은 하나의 프로세스 안에서 I/O와 다른 작업이 중첩될 수 있게 한다. 하나의 스레드가 I/O 작업으로 대기하는 동안 다른 스레드가 작업을 수행할 수 있다.

### 스레드의 문제점

1. 스레드의 실행 순서는 우리가 알 수 없다.

메인 스레드에서 두 개의 스레드를 생성하여 동작을 수행하도록 해보자.

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

#include "common.h"
#include "common_threads.h"

void *mythread(void *a[Irg) {
    printf("%s\n", (char *) arg);
    return NULL;
}

int main(int argc, char *argv[]) {                    
    if (argc != 1) {
	fprintf(stderr, "usage: main\n");
	exit(1);
    }

    pthread_t p1, p2;
    printf("main: begin\n");
    Pthread_create(&p1, NULL, mythread, "A"); 
    Pthread_create(&p2, NULL, mythread, "B");
    // join waits for the threads to finish
    Pthread_join(p1, NULL); 
    Pthread_join(p2, NULL); 
    printf("main: end\n");
    return 0;
}
```

위 코드가 어떻게 실행될지는 아무도 확정할 수 없다.

스레드의 동작이 스레드 두 개가 모두 생성된 후일지 전일지 모르며,
스레드 1이 2보다 생성은 먼저 되겠지만 그렇다고 “A” 가 “B” 보다 먼저 출력되는건 아니다. 스케줄러가 스레드 2를 먼저 실행하면 출력 순서는 반대가 된다.

> 스레드가 먼저 생성되었다고 해서 먼저 실행될 것이라는 가정을 할 어떤 이유도 없다.

스레드의 생성은 함수 호출처럼 생겼지만 동작은 그것과 다르다.

**스레드의 생성에는 실행할 명령어들을 갖고 있는 새로운 스레드가 생성되고, 생성된 스레드는 호출자와는 별개로 실행된다.**

2. 공유 데이터에 접근하면서 발생하는 문제

> 여러 스레드가 하나의 공유 데이터에 접근할 시 해당 코드는 결정론적인 결과를 보장할 수 없다.

두 개의 스레드가 하나의 counter 변수에 접근하여 값을 1 올리는 코드를 생각해보자. 두 스레드 모두 반복문을 천만번 돌면 우리는 counter 변수가 끝내 2천만이 될거가 예상하지만 결과는 그렇지 않다. 2천만이 되지 못할 뿐더러 그 결과값이 항상 다르다. 왜 이런 현상이 발생할까?

counter 변수를 증가시키는 코드를 어셈블리어로 보자.

```cpp
mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c
```

counter 변수의 위치의 주소는 0x8049a1c 라고 가정한다.

만약 스레드 1이 위 어셈블리 코드를 실행하는 중간에 (eax 레지스터에 counter 변수를 복사한 후) 타이머 인터럽트가 발생했다면, 운영체제는 스레드 1의 PC 값과 eax를 포함한 레지스터 값들을 TCB 에 저장하고 스레드 2가 실행된다. 스레드 문맥교환이 일어나는 것이다.
스레드 2도 똑같은 어셈블리 코드에 진입할 것이고 똑같이 카운터 값을 얻어와서 1을 더하고 저장할 것이다. 스레드 1이 위에서 1을 증가시켰지만 아직 저장하는 코드를 실행하지 않았으므로 스레드 2가 처음에 가져온 값은 처음 값 그대로이다.

그래서 결국 두 개의 스레드가 똑같은 데이터의 값을 1씩 증가시키고 저장까지 완료했지만 최종적으로 증가된 값은 2가 아니라 2인 것이다.

이처럼 명령어의 실행 순서에 따라 결과가 매번 달라지는 상황을 **경쟁 조건(race condition)**이라고 부른다.

그리고 이런 경쟁 조건이 발생하는 코드 부분을 임계 영역(critical section)이라고 부른다.

이러한 코드에서 필요한게 **상호 배제(mutual exclusion)** 이다.

### 상호 배제(Mutual Exclusion)

상호 배제란 하나의 스레드가 임계 영역 내의 코드를 실행 중일 때는 다른 스레드가 해당 코드를 실행할 수 없도록 보장하는 것을 말한다.

### 원자성(atomicity)

원자성이란 "완전히 실행되거나 혹은 전혀 실행되지 않거나” 이다. 일련의 동작이 전부 실행되거나 중간에 문제가 발생한다면 전혀 실행되지 않은 상태로 돌리는 것이다.

그리고 여러 동작을 하나로 묶어 그 묶음에 대해 원자성을 보장하는 것을 "트랜잭션" 이라고 부른다.

> **결국 시도 때도 없이 발생하는 인터럽트가 위에서 언급한 모든 문제의 원인이다.**

### 용어 정리

- Critical Section(임계 영역) : 공유 자원에 접근하는 코드 일부분
- Race Condition(경쟁 조건) : 여러 스레드가 공유 자원에 접근함으로 인해서 비결정론적인 결과를 유발하는 현상
- Mutual Exclusion(상호 배제): 하나의 스레드만이 임계 영역에 진입할 수 있도록 보장하는 것

## 락

> 임계 영역을 락으로 보호하여 그 임계 영역이 하나의 atomic 한 하나의 명령어인 것처럼 실행되도록 하자.

```cpp
lock_t mutex; // 글로벌 변수로 선언된 락
...
lock(&mutex)
counter = counter + 1;
unlock(&mutex)
```

락은 락의 상태를 나타내는 일종의 변수다. 사용 가능한 상태이거나 혹은 사용 중인 상태이거나

lock() 을 통해 **락 획득을 시도**한다. 어떤 스레드도 락을 소유하고 있지 않은 상태라면 해당 스레드가 락을 획득한다. 이  때 다른 스레드가 lock() 을 호출할 경우 lock() 함수는 리턴하지 않고 대기한다.
락을 획득했던 스레드가 unlock()으로 락을 해제한다면 락은 이제 다시 사용가능한 상태가 된다.

> 락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다.

**스레드는 프로그래머가 생성하고 운영체제가 제어한다.** 락으로 코드를 감싸서 프로그래머는 그 코드 내에서는 하나의 스레드만 동작할 수 있도록 보장한다.

스레드 간에 상호 배제(mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 **락을 mutex 라고 부른다.**

### 락의 평가 기준

> 효율적인 락은 낮은 비용으로 상호 배제 기법을 제공해야한다.

1. 상호 배제를 제대로 지원하는가
2. 스레드들이 락 획득에 대한 공정한 기회가 주어지는가 → 공정성
   - 경쟁에 밀려서 굶주리는 스레드가 존재하지는 않는가
1. 락 사용의 시간적 오버헤드 → 성능
   - 경쟁이 전혀 없는 경우의 성능
   - 여러 스레드가 락을 획득하려고 경쟁할 때의 성능

### 락의 구현

### 인터럽트 비활성화

사실 인터럽트가 발생하지 않도록 비활성화하면 원자성은 보장된다. 아주 간단하다. 하지만 문제도 많다.

스레드가 인터럽트를 활성/비활성화할 수 있도록 특권을 허가해야하는데, 스레드가 이를 다른 목적으로 사용하지 않음을 신뢰할 수 있어야 한다. 만약 스레드가 인터럽트를 비활성화하고 CPU를 독점한다고 해도 이를 막을 수가 없다.

그리고 멀티 프로세서에서는 사용할 수 없다. 특정 프로세서에서의 인터럽트 비활성화는 다른 프로세서에 영향을 주지 않는다.

### 단일 변수만 사용(load-store)

```cpp
typedef struct __lock_t { int flag; } lock_t;

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

void lock(lock_t *mutex) {
	while (mutex->flag == 1) // TEST the flag
 	; // spin-wait (do nothing)
 	mutex->flag = 1; // now SET it!
}

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

이 아이디어도 간단하다. 변수(flag) 하나를 사용해서 스레드가 락을 획득했는지를 나타낸다.

락을 획득하고 변경할 때 마다 변수를 변경한다. 다른 스레드가 이미 락을 획득했는데 lock() 으로 락을 획득하려고 하면 **while 문에서 spin-wait 하며** 락을 가지고 있는 스레드가 unlock() 으로 락을 해제해주기를 (변수를 초기화 해주기를) 기다린다.

이 방식의 문제는 두 스레드가 동시에 임계 영역에 진입할 수 있다는 것이다. 이는 상호 배제라는 기본적인 기능 요구 조건조차 보장하지 못했음을 의미한다.

그리고 위에서 spin-wait 는 while 문에서 변수의 값을 무한히 검사하는데, 이 방법은 다른 스레드가 락을 해제해줄 때 까지 시간을 낭비한다.

### Test-And-Set

이제 하드웨어의 도움을 받아보자.

하드웨어의 도움을 받는 락 구현 기법 중 가장 기본적인 방법이 test-and-set (또는 원자적 교체)으로 잘 알려진 명령어이다. test-and-set 명령어의 동작을 C 로 표현하면 다음과 같다.

```cpp
int TestAndSet(int *old_ptr, int new) {
	int old = *old_ptr; // fetch old value at old_ptr
	*old_ptr = new; // store 'new' into old_ptr
	return old; // return the old value
}
```

포인터가 가리키던 예전 값을 반환하고 동시에 새로운 값을 그 포인터에 저장한다. 말그래도 test하고 set하는 동작을 한다. 중요한건 이 동작은 하드웨어의 도움을 받아 원자적으로 실행한다는 것이다.

```cpp
typedef struct __lock_t {
	int flag;
} lock_t;

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

void lock(lock_t *lock) {
	while (TestAndSet(&lock->flag, 1) == 1)
	; // spin-wait (do nothing)
}

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

위 코드에서 spin-wait하는 코드를 다시 보자. 앞선 load-store 방식과는 달리 락 값을 검사(test)하고 새롭게 설정(set)하는 동작을 원자적으로 수행한다. 그래서 오직 하나의 스레드만 락을 획득할 수 있도록 한것이다. 이제 상호 배제라는 기본적인 기능 요구 조건을 보장한다.

하지만 spin-wait 문제는 해결하지 못했기 때문에 CPU 사이클을 낭비하면서 대기하는건 여전하다.

### Fetch-And-Add

또 다른 하드웨어 기반의 기법인 Fetch-And-Add 명령어는 원자적으로 특정 주소의 예전 값을 반환하며서 동시에 값을 증가시킨다. 이 동작을 C 로 표현하면 다음과 같다.

```cpp
int FetchAndAdd(int *ptr) {
	int old = *ptr;
	*ptr = old + 1;
	return old;
}
```

이를 이용해 **ticket lock** 이라는 것을 만들어보자.

지금까지 하나의 변수(flag)만 사용해서 락을 구현했던것과 달리 ticket 과 turn 이라는 두 변수의 조합으로 락을 구현해보자. 로직은 생각보다 간단하다.

```cpp
typedef struct __lock_t {
	int ticket;
	int turn;
} lock_t;

void lock_init(lock_t *lock) {
	lock->ticket = 0;
	lock->turn = 0;
}

void lock(lock_t *lock) {
	int myturn = FetchAndAdd(&lock->ticket);
	while (lock->turn != myturn)
; // spin
}

void unlock(lock_t *lock) {
	lock->turn = lock->turn + 1;
}
```

1. 락 획득을 원하는 스레드는 전역 티켓 변수(lock->ticket)에 fetch-and-add 명령어를 실행한다.
2. 그 결과값은 내 차례(myturn)이 된다.
3. 현재 락을 획득할 스레드는 전역 차례 변수(lock->turn)로 판단한다. (lock-turn == myturn)
4. 락을 해제하는 스레드는 전역 차례 변수에 fetch-and-add 명령어를 실행한다.

이전까지의 락 구현 방법과의 가장 큰 차이는 **모든 스레드가 각자의 순서를 가진다는 것**이다. 스레드가 티켓을 항당 받은 순간 미래의 어느 때에 실행될지 스케줄링이 되는것이다. 이전까지의 방법에서는 이런 보장이 없었다.

### 과도하고 비효율적인 스핀

지금까지 소개한 락 구현 방법들의 공통점은 스핀이다. 간단하지만 비효율적이다.

스레드가 스핀 구문을 실행하면서 변경되지 않을지도 모를 값을 하염없이 기다리며 시간만 낭비한다.

N개의 스레드가 하나의 락을 획득하기 위해 경쟁하면 N-1개의 스레드는 CPU 시간을 낭비하며 락 해제를 기다린다.

> 어떻게 하면 스핀에 CPU 시간을 낭비하지 않는 락을 만들 수 있을까?

### 일단 양보하기

아주 단순한 방법이다. 락이 해제되기를 기다리며 스핀해야하는 경우 자신에게 할당된 CPU를 다른 스레드에게 바로 양보하는 것이다.

```cpp
void lock() {
	while (TestAndSet(&flag, 1) == 1)
	yield(); // give up the CPU
}
```

우선 운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 스레드에게 CPU 를 양보하도록 하는 yield() 명령어가 있다고 가정한다.

yield 시스템 콜은 호출한 스레드의 상태를 running 상태에서 ready 상태로 변환한다. 스케줄 대상에서 자신을 빼는 것이다.

spin 방식 보다는 좀 더 낫지만 문맥 교환 비용 또한 상당하며 낭비가 많다. 더군다나 굶주림 문제는 해결하지도 못했다. 어떤 스레드는 무한히 양보만 하는 경우가 생길 수 있다.

### 큐의 사용

이전까지의 방법들은 스케줄링의 많은 부분을 운에 맡기기 때문에 굶주림 문제를 해결하지 못했다.

다수의 스레드가 락을 대기하고 있을 경우, **다음 차례로 락을 획득할 스레드를 명시적으로 선택**할 수 있어야한다.

앞서 배웠던 Test-And-Set 개념을 락 대기자 큐와 함께 사용해보자. 다음으로 락을 획득할 대상을 제어하여 굶주림 현상을 피할 수 있다.

### Spin 대신 Sleep

위 큐 방식과 함께 spin 대신 sleep 을 사용해보자. 스레드를 무한히 spin 하면서 대기시키는게 아니라 잠재우면 효율적이지 않을까?

Solaris의 방식을 예시로 들겠다. park() 는 호출하는 스레드를 잠재우는 함수이고, unpark(threadId) 는 명시된 특정 스레드를 깨우는 함수이다.

다음 코드는 guard 변수를 스핀락으로 대기 큐와 flag 변수를 보호한다. 여전히 스핀락을 사용한다. 하지만 기존과 큰 차이가 있다. 스핀락으로 보호하는 변수를 flag 가 아니다! guard 변수이다. 이말은 여전히 스핀으로 대기를 하기는 하지만 그 스핀 대기시간이 훨씬 짧다는 뜻이다. 이 스핀락은 lock() 과 unlock() 코드 내의 몇개의 명령어만 수행하면 풀린다.

```cpp
typedef struct __lock_t {
     int flag;
     int guard;
     queue_t *q;
} lock_t;

 void lock_init(lock_t *m) {
     m->flag = 0;
     m->guard = 0;
     queue_init(m->q);
}

 void lock(lock_t *m) {
     while (TestAndSet(&m->guard, 1) == 1)
     ; //acquire guard lock by spinning
     if (m->flag == 0) {
         m->flag = 1; // lock is acquired
         m->guard = 0;
     } else {
         queue_add(m->q, gettid());
         m->guard = 0;
         park();
     }
}

 void unlock(lock_t *m) {
     while (TestAndSet(&m->guard, 1) == 1)
     ; //acquire guard lock by spinning
     if (queue_empty(m->q))
          m->flag = 0; // let go of lock; no one wants it
     else
          unpark(queue_remove(m->q)); // hold lock
          // (for next thread!)
          m->guard = 0;
}
```

### 2 단계 락

요즘은 2단계 락이라는 기법이 자주 쓰이는데, 이는 락이 빨리 풀릴 것 같으면 오히려 스핀 대기가 더 효율적이라는 점이 착안한 기법이다.

1 단계 에서는 일단 스핀하며 대기한다. 락이 빨리 풀릴거라 기대하는 것이다.

하지만 1 단계에서 락을 획득하지 못한다면 2 단계로 진입한다. 2 단계에서는 호출 스레드는 잠자게된다. 락 해제시 잠자는 스레드 중 하나를 깨운다.

> 2 단계 락은 두 개의 좋은 개념을 사용하여 개선된 하나를 만들어 내는 하이브리드 방식이다.


