OSTEP 28 Locks

여러 개의 명령어들을 atomic하게 실행하고 싶지만 단일 프로세스의 인터럽트로 인해 그렇게 할 수 없었다. 이 문제를 lock을 통해 직접적으로 다뤄보자. 프로그래머는 소스 코드의 임계 영역을 lock으로 둘러, 그 임계 영역이 마치 하나의 원자 단위 명령어인 것 처럼 실행되도록 한다.

1. 락: 기본 개념

balance = balance + 1;

다음과 같은 임계 영역이 있다고 하자.

락으로 임계 영역을 다음과 같이 감쌌다.

lock_t mutex; // 전역 변수로 선언된 락
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

락은 하나의 변수이므로, 락을 사용하기 위해 먼저 선언해야 한다. 이 락 변수는 사용 가능 상태, 즉 어느 쓰레드도 락을 가지고 있지 않거나, 사용 중, 즉 임계 영역에서 정확히 하나의 쓰레드가 락을 획득한 상태이다.

lock()과 unlock()의 의미는 간단하다. lock()을 호출하여 락 획득을 시도한다. 만약 어떤 쓰레드도 락을 가지고 있지 않다면 그 쓰레드는 락을 획득하여 임계 영역으로 진입한다. 이렇게 진입한 쓰레드를 락 소유자 (owner) 라고 부른다. 만약 다른 쓰레드가 lock()을 호출한다면, 사용 중인 동안에는 lock() 함수가 리턴하지 않는다.

락 소유자가 unlock()을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다. 어떤 쓰레드도 이 락을 대기하고 있지 않다면 (어떤 쓰레드도 lock()을 호출하여 멈춰 있던 상태가 아니라면) 락의 상태는 사용 가능으로 유지된다.

락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다. 쓰레드에 대한 제어권을 일부 받을 수 있다. 이를 통해 프로그래머는 그 코드 내에서 하나의 쓰레드만 동작하도록 보장한다. 혼란스런 실행 순서에 어느 정도 질서를 부여할 수 있는 것이다.

2. Pthread 락

쓰레드 간 상호 배제 (mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex 라고 부른다. 상호 배제는 한 쓰레드가 임계 영역 내에 있다면, 이 쓰레드의 동작이 끝날 때까지 다른 쓰레드가 임계 영역에 들어올 수 없도록 제한한다고 해서 붙여진 이름이다.

래퍼를 사용하여 락과 언락시에 에러를 확인하도록 함

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

Pthread_mutex_lock(&lock); // pthread_mutex_lock()을 위한 래퍼.
balance = balance + 1;
Pthread_mutex_unlock(&lock);

POSIX 방식은 변수명을 지정하여 락과 언락 함수에 전달한다. 다른 변수를 보호하기 위해 다른 락을 사용할수도 있기 때문이다. 이를 통해 여러가지 방식으로 락을 구현할 수 있다.

세밀한 락과 거친 락 전략

거친 락 (Coarse-Grained Locking)

• 하나의 락이 큰 임계 영역을 제어함.
• 쉽게 구현할 수 있지만, 병렬성이 제한됨.

세밀한 락 (Fine-Grained Locking)

• 여러 락이 서로 다른 데이터나 자료구조를 보호함.
• 한 번에 여러 쓰레드가 서로 다른 락으로 보호된 코드 내에 진입 가능.
• 병렬성은 향상되지만, 데드락 등의 복잡한 이슈에 대처해야 함.

3. 락 구현

이번 장에서 어떻게 락을 만들어야 하는지, 어떤 종류의 하드웨어 지원이 필요한지, 운영체제는 무엇을 지원해야 하는지에 대해 다룰 것이다.

효율적인 락은 어떻게 만들어야 하는가? 효율적인 락은 낮은 비용으로 상호 배제 기법을 제공하고 다음에 다룰 몇 가지 속성들을 추가로 가져야 한다. 어떤 하드웨어 지원이 필요한가? 어떤 운영체제 지원이 필요한가?

4. 락의 평가

상호 배제 (mutual exclusion)

• 가장 기본 역할.
• 임계 영역 내로 다수의 쓰레드가 진입하는 것을 막을 수 있는지 검사해야 함.

공정성 (fairness)

• 여러 쓰레드들이 락을 번갈아가면서 획득할 수 있어야 함.
• 락을 전혀 얻지 못해 굶주리는 경우가 발생하면 안 됨.

성능 (performance)

• 락 사용에 대한 시간적 오버헤드를 평가해야 한다.
• 하나의 쓰레드가 실행 중에 락을 획득하고 해제하는 과정에서 발생하는 부하가 얼마나 되는가?

5. 인터럽트 제어

초창기 단일 프로세서 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서 인터럽트를 비활성화 하는 방법을 사용했다.

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

이 방법의 장점은 단순하다는 것이고, 단점은 많다.

1. 먼저, 이 요청을 하는 쓰레드가 인터럽트를 활성화/비활성화 하는 커널 모드 특권 연산을 실행할 수 있도록 허가해야 한다. 만약 어떤 프로그램이 시작과 동시에 lock()을 호출하고 무한 반복문에 들어간다면, 운영체제는 시스템의 제어권을 다시 얻을 수 없다.
2. 또, 멀티프로세서에서는 적용을 할 수 없다. 여러 쓰레드가 여러 CPU에서 실행 중이라면, 각 쓰레드가 동일한 임계 영역에 진입하려고 할 수 있다. 이 떄 인터럽트를 비활성화하는 것은 다른 프로세서에서 실행중인 프로그램에는 전혀 영향을 주지 않는다. 즉, 임계 영역에 진입하는 것을 막을 수 없다.
3. 장시간 인터럽트를 중지시키는 것은 중요한 인터럽트 시점을 놓치게 할 수 있다. CPU가 저장 장치에서 읽기 요청을 마친 사실을 모르고 지나갔다고 해보자. 운영체제는 읽기 결과를 기다리는 프로세스를 깨울 수 없을 것이다.
4. 마지막으로, 비효율적이다. 일반적인 명령어에 비해 인터럽트를 비활성화시키는 코드들은 최신 CPU에서는 느리게 실행된다.

따라서, 인터럽트 비활성화는 제한된 범위에서만 사용되어야 한다. 예를 들어, 운영체제가 내부 자료 구조에 atomic 연산을 하기 위해 등등..

6. Test-And-Set (Atomic Exchange)

멀티 프로세서 시스템에서는 인터럽트를 중지시키는 것이 의미가 없기 때문에 시스템 설계자들은 락 지원을 위한 하드웨어를 설계하기 시작했다. 오늘날에는 모든 시스템이 이러한 지원 기능을 가지고 있다.

하드웨어 기법 중 가장 기본은 Test-And-Set 명령어 또는 원자적 교체 (atomic exchange) 라고 불리는 기법이다. 이를 이해하기 위해 간단한 플래그 변수로 락을 구현해보자.

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
	// 0: 락 사용 가능
	// 1: 락 사용 중
	mutex−>flag = 0;
}

void lock(lock_t *mutex) {
	while (mutex−>flag == 1) // flag 변수를 검사 (test) 한다
	; // spin−wait (do nothing)
	mutex−>flag = 1; // 이제 설정 (set) 한다
}

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

간단한 변수를 사용해 쓰레드가 락을 획득했는지 나타낸다. 임계 영역에 진입하는 첫 쓰레드가 lock()을 호출하여 플래그가 1인지 검사(test) 하고 플래그의 값을 1로 설정(set) 하여 이 쓰레드가 락을 보유(hold) 하고 있다고 표시한다. 임계 영역에서 나오면 쓰레드가 unlock()을 호출하여 플래그 값을 초기화하고, 락을 더 이상 보유하고 있지 않다고 표시한다.

만약 첫 번째 쓰레드가 임계 영역 내에 있을 때 다른 쓰레드가 lock()을 호출하면 그 쓰레드는 while문으로 spin-wait을 하며 처음 쓰레드가 unlock()을 호출하여 플래그를 초기화하기를 기다린다. 처음 쓰레드가 플래그를 초기화하면 대기하던 쓰레드는 while 문에서 빠져나와 플래그를 1로 설정하고 임계 영역 내로 진입한다.

이 코드에는 두 가지 문제가 있다.

정확성

시작할 때 flag = 0이라 하자. 쓰레드 1이 flag = 1을 실행하기 직전에 인터럽트가 일어난다면? 두 쓰레드 모두 플래그를 1로 설정하도록 하는 인터럽트 타이밍이 존재한다. 두 쓰레드 모두 임계 영역에 진입하게 된다. 잘못 만들었다.

성능

spin wait을 통해 플래그의 값을 무한히 검사하는데, 이는 성능상 좋지 못하다. 특히 단일 프로세서에서. 락을 소유한 쓰레드조차 실행하기 힘들도록 한다.

7. 진짜 돌아가는 스핀 락의 구현

앞서 다룬 예제는 하드웨어 지원 없이는 동작이 불가능했다. 다행히도 어떤 시스템은 이 개념에 근간한 락 구현을 위한 어셈블리 명령어를 제공한다. SPARC에서는 ldstub, x86에서는 원자적 교체 명령어인 xchg이다. 기본적으로 동일한 일을 수행한다. 일반적으로 Test-And-Set 이라고 불린다. TestAndSet 동작을 정의해보자.

int TestAndSet(int *old_ptr, int new) {
	int old = *old_ptr; // old_ptr의 이전 값을 가져옴
	*old_ptr = new; // old_ptr 에 new 값을 저장함
	return old; // old의 값을 반환함
}

TestAndSet 명령어가 하는 동작은 다음과 같다. ptr이 가리키고 있던 예전의 값을 반환하고, 동시에 new 값을 ptr에 저장한다. 여기서의 핵심은 이 동작들이 원자적으로 수행된다는 것이다. 이전 값을 검사 (test -> 반환되는 값) 하는 동시에 메모리에 새로운 값을 설정 (set) 한다.

이 명령어만으로 간단한 spin lock을 만들 수 있다.

typedef struct __lock_t {
	int flag;
} lock_t;

void init(lock_t *lock) {
	// 0은 락이 획득 가능한 상태
	// 1은 락을 획득했음
	lock−>flag = 0;
}

void lock(lock_t *lock) {
	while (TestAndSet(&lock−>flag, 1) == 1)
	; // spin
}

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

작동 원리를 파악해보도록 하자.

처음 쓰레드가 lock()을 호출하고, 다른 어떤 쓰레드도 현재 락을 보유하고 있지 않다고 하자. 그럼 현재 flag의 값은 0이다. TestAndSet(flag, 1)을 호출하면 반환 값은 0 이라 while문을 탈출할 수 있다. 그리고 flag는 1이 된다. 이후 이 쓰레드가 동작을 끝마치면 unlock()을 호출하여 flag 값을 다시 0으로 변경한다.

처음 쓰레드가 락을 획득하여 flag가 1인 상태에서, 두 번째 쓰레드가 lock()을 호출한다고 해보자. TestAndSet(flag, 1)을 호출하면 반환 값이 1 이라 while문을 탈출할 수 없다. 락을 보유하고 있는 쓰레드가 존재하는 한 TestAndSet(flag, 1)은 계속 1을 반환한다.

락을 보유하고 있는 처음 쓰레드가 flag 값을 0으로 변경하면, 두 번째 쓰레드가 TestAndSet(flag, 1)을 호출했을 때 반환 값이 0이 되어 while문을 탈출할 수 있게 된다.

드디어 제대로 동작하는 상호 배제 함수를 만드는 방법을 배웠다. 이것이 가장 기초적인 형태의 락으로써, 락을 획득할 때까지 CPU 사이클을 소모하면서 회전한다. 단일 프로세서에서 이 방식을 제대로 사용하려면 선점형 스케줄러를 사용해야 한다. 다른 쓰레드가 실행될 수 있도록 타이머를 통해 인터럽트를 발생시킬 수 있기 때문이다. 선점형이 아니면 while문을 돌리며 대기하는 쓰레드가 CPU를 영원히 독점하게 될 것이다.

8. 스핀 락 평가

락에서 가장 중요한 측면은 상호 배제의 정확성 이다. 상호 배제가 가능하다면 스핀 락은 임의의 시간에 단 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 한다.

그 다음의 항목은 공정성이다. 대기 중인 쓰레드들에 있어서 스핀 락은 얼마나 공정할까? 스핀 락은 어떠한 공정성도 보장해줄 수 없다. while문을 돌리는 쓰레드가 경쟁에 밀려서 굶주릴 가능성이 존재한다.

마지막 항목은 성능이다. 스핀 락을 사용할 때 얼마나 비용을 지불해야 할까? 단일 CPU의 경우 스핀 락이 갖는 성능 오버헤드는 상당히 클 수 있다. $N$개 중 $N-1$개의 다른 쓰레드가 락을 획득하려고 할 때, 스케줄러가 이들을 한 번씩 깨울 수도 있다. CPU가 여러 개인 경우 (쓰레드의 개수와 CPU의 개수가 비슷하다면) 스핀 락은 꽤 합리적으로 동작한다. CPU 1에서 실행중인 A가 락을 획득한 후 B가 락을 획득하려고 한다면 CPU 2에서 기다리기 때문에 금방 락을 획득할 수 있을 것이다.

9. Compare-And-Swap

또 다른 하드웨어 기법은 SPARC의 Compare-And-Swap, x86의 Compare-And-Exchange가 있다.

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

Compare-And-Swap 기법의 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는 것이다. 만약 일치한다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경한다. 불일치한다면 변경하지 않는다. 원래의 메모리 값을 반환하여 CompareAndSwap을 호출한 코드가 락 획득의 성공 여부를 알 수 있도록 한다.

앞서 작성한 Test-And-Set 방법을 사용했을 때와 같은 방법으로 락을 만들 수 있다.

typedef struct __lock_t {
	int flag;
} lock_t;

void init(lock_t *lock) {
	// 0은 락이 획득 가능한 상태
	// 1은 락을 획득했음
	lock−>flag = 0;
}

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

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

맨 처음 락을 획득하는 쓰레드는, 0을 1로 바꾸는데 성공해서 0을 반환받고 (actual == 0) 루프를 탈출한다. 그 이후 접근하는 쓰레드는 expected는 0, flag는 1이라 1을 반환받고 (actual == 1) 루프를 탈출할 수 없다.

CompareAndSwap 명령어는 TestAndSet 명령어보다 더 강력하다. 대기없는 동기화 (wait-free synchronization) 을 다룰 때 강력함을 알게 될 것이다.

10. Load-Linked 그리고 Store-Conditional

어떤 플랫폼은 임계 영역 진입 제어 함수를 제작하기 위한 명령어 쌍을 제공한다. MIPS 구조에서는 load-linked와 store-conditional 명령어를 앞뒤로 사용하여 락이나 기타 병행 연산을 위한 자료 구조를 만들 수 있다.

int LoadLinked(int *ptr) {
	return *ptr;
}

int StoreConditional(int *ptr, int value) {
	if (no one has updated *ptr since the LoadLinked to this address) {
		*ptr = value;
		return 1; // 갱신 성공
	} else {
		return 0; // 갱신 실패
	}
}

LoadLinked는 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장한다. StoreConditional 명령어는 동일한 주소에 다른 store가 없었던 경우에만 저장을 성공한다. 성공한 경우 LoadLinked가 탑재했던 값을 갱신하고 1을 반환한다. 실패하면 갱신하지 않고 0을 반환한다.

void lock(lock_t *lock) {
while (1) {
	while (LoadLinked(&lock−>flag) == 1)
	; // 0이 될 때까지 spin
	if (StoreConditional(&lock−>flag, 1) == 1)
		return; // 1로 변경하는 것을 성공한 경우 완료
		// 아니라면 처음부터 다시 시도
	}
}

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

쓰레드가 while문을 돌며 flag가 0이 되기를 기다린다. 0이 되면 락이 해제된 것이다. 락이 획득 가능 상태가 되면 쓰레드는 StoredConditional 명령어로 락 획득을 시도하고 성공한다면 flag 값을 1로 변경하고, 임계 영역으로 진입한다.

StoredConditional 이 실패할 수도 있다. 이 점이 중요하다.

1. 쓰레드가 lock()을 호출하여 LoadLinked를 실행. 락이 사용 가능한 상태이므로 0을 반환. 루프 탈출
2. StoredConditional 명령어를 시도하기 전에 인터럽트
3. 다른 쓰레드가 lock()을 호출. LoadLinked를 실행. 락이 사용 가능한 상태이므로 0을 반환. 루프 탈출
4. 이 시점에 두 쓰레드는 모두 LoadLinked 명령어를 실행하였고 각자가 StoredConditional을 호출하려는 상황

이 명령어의 주요 기능은 오직 하나의 쓰레드만 flag값을 1로 설정한 후에 락을 획득할 수 있도록 하는 것이다. 두 번째로 StoredConditional을 실행한 쓰레드는 락 획득에 실패하고 다음 기회를 기다려야 한다.

이렇게 쓰면 더 짧아진다.

void lock(lock_t *lock) {
	while (LoadLinked(&lock−>flag)||!StoreConditional(&lock−>flag, 1))
	; // spin
}

11. Fetch-And-Add

마지막 하드웨어 기법은 Fetch-And-Add 명령어로, 원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시킨다.

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

FetchAndAdd 명령어를 사용하여 티켓 락 이라는 재미있는 것을 만들어보자!

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) {
	FetchAndAdd(&lock−>turn);
}

ticket과 turn 조합을 사용해 락을 만든다. 하나의 쓰레드가 락 획득을 원하면, ticket 변수에 atomic 연산인 FetchAndAdd 명령어를 실행한다. 결과 값은 해당 쓰레드의 차례를 나타낸다.

전역 공유 변수인 lock->turn을 사용하여 어느 쓰레드의 차례인지 판단한다. 만약 한 쓰레드가 myturn == lock->turn조건에 부합하면, while 문을 벗어나 락을 획득한다. unlock()은 turn 변수의 값을 증가시켜서 대기 중인 다음 쓰레드에게 임계 영역 진입 차례를 넘겨 준다.

이전까지 접근 방법과의 가장 중요한 차이점은 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이다. 쓰레드가 티켓 값을 할당받았다면, 미래의 어느 시점에 실행되기 위해 스케줄되어 있다는 것이다. 이전까지는 이러한 보장이 없었다. 예를 들어 Test-And-Set의 경우 다른 쓰레드들은 락을 획득/해제하더라도 어떤 쓰레드는 계속 회전만 하고 있을 수 있다. 즉 이번 해법은 공정성이 있다.

12. 요약: 과도한 스핀

지금까지 다룬 해법이 효율적이지 않은 경우도 있다. 특히 프로세서가 하나인 경우 비효율적이다. $N$개의 쓰레드가 하나의 락을 획득하기 위해 경쟁하게 된다면? $N-1$개의 쓰레드가 계속 spin할 것이다.

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

13. 간단한 접근법: 무조건 양보!

하드웨어의 지원을 받아 많은 것을 해결하였다. 동작이 검증된 락과 락 획득의 공정성까지도 해결했다. 하지만 스핀만 무한히 하는 경우는 어떻게 해결해야 할까?

첫 번째로, 락이 해제되기를 기다리며 스핀해야 하는 경우 자신에게 할당된 CPU를 다른 쓰레드에게 양보하도록 할 수 있다.

void init() {
	flag = 0;
}

void lock() {
	while (TestAndSet(&flag, 1) == 1)
		yield(); // CPU 양보
}

void unlock() {
	flag = 0;
}

운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 하는 yield() 기법이 있다고 가정한다. 하나의 쓰레드는 running, ready, blocked 세 가지 상태가 있다. yield 라는 시스템 콜은 호출 쓰레드 상태를 running에서 ready로 변환하여 다른 쓰레드가 running 상태로 전이하도록 한다.

단일 CPU 시스템에서 두 개의 쓰레드를 실행하는 경우, 적절하게 동작하는 것을 알 수 있다. (계속 양보)

100개 정도의 쓰레드들이 락을 획득하기 위해 경쟁하는 경우를 살펴보자. 한 쓰레드가 락을 획득하면 나머지 99개의 쓰레드가 각자 lock()을 호출하고 CPU를 양보한다. 라운드 로빈 기법을 사용하는 경우, 락을 갖고 있는 쓰레드가 다시 실행되기까지 99개의 쓰레드가 실행하고 양보하는 패턴으로 동작하는데, 이는 비용이 만만치 않게 든다.

또, 굶주림 문제도 해결하지 못했다. 어떤 쓰레드는 무한히 양보만 하게 될지도 모른다.

14. 큐의 사용: 스핀 대신 잠자기

이전 방법들은 너무 많은 부분을 운에 맡겼다. 스케줄러가 좋지 않은 선택을 한다면 기다리거나 CPU를 양보해야 한다. 둘 다 낭비의 여지가 있고 쓰레드가 굶주릴 수 있다.

어떤 쓰레드가 다음으로 락을 획득할지를 명시적으로 제어할 수 있어야 한다. 이를 위해 운영체제로부터 적절한 지원을 받고, 큐를 이용한 대기 쓰레드들을 관리할 것이다.

간단히 Solaris의 방식으로 해보자.

park(): 호출하는 쓰레드를 잠재우는 함수 unpark(threadID): threadID로 명시된 특정 쓰레드를 깨우는 함수

이 두 루틴은 이미 사용 중인 락을 요청하는 프로세스를 재우고 해당 락이 해제되면 깨우도록 하는 락을 제작하는 데 앞뒤로 사용할 수 있다.

TestAndSet 개념을 락 대기자 전용 큐와 함께 사용하여 효율적인 락을 만들 것이고, 큐를 사용하여 굶주림 현상을 방지할 것이다.

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)
	; // 회전하면서 guard 락을 획득
	if (m−>flag == 0) {
		m−>flag = 1; // 락 획득
		m−>guard = 0;
	} else {
		queue_add(m−>q, gettid());
		m−>guard = 0;
		park(); // 잠재우기
	}
}

void unlock(lock_t *m) {
	while (TestAndSet(&m−>guard, 1) == 1)
	; // 회전하면서 guard 락을 획득
	if (queue_empty(m−>q))
		m−>flag = 0; // 락을 포기함. 누구도 락을 원치 않음.
	else
		unpark(queue_remove(m−>q)); // 락을 획득함 (다음 쓰레드를 위해)
	m−>guard = 0;
}

guard 변수를 사용하여 flag와 큐의 삽입과 삭제 동작을 스핀 락으로 보호한다. 이 방법은 스핀을 완전히 배제하지는 못했다. 하지만 스핀 대기 시간은 꽤 짧다. 사용자가 지정한 임계 영역에 진입하는 것이 아니라 락과 언락 코드 내의 몇 개의 명령어만 수행하면 되기 때문이다.

lock() 에 추가된 동작이 있다. lock()을 호출했는데 다른 쓰레드가 이미 락을 보유중이라면, gettid()를 호출하여 현재 실행 중인 쓰레드 ID를 얻고, 락 소유자의 큐에 자기 자신을 추가하고 guard 변수를 0으로 변경한 후 CPU를 양보한다.

다른 쓰레드가 깨어났을 때 flag 변수가 0으로 설정되지 않는다. 깨어날 때는 guard 락을 획득한 상태가 아니기 때문에 flag를 1로 변경할 수 없다. 따라서 그냥 1인 채로 두고 락을 획득하려는 다음 쓰레드로 직접 전달한다. flag는 0이 되었다 다시 1이 되는게 아니라 그냥 계속 1이다.

마지막으로, park() 직전에 경쟁 조건이 발생한다. 한 쓰레드는 락이 사용중이라 park()를 실행하려고 한다. 그 직전에 락 소유자한테 CPU가 할당되면 문제가 생길 수 있다.

경쟁 조건이 어떻게 발생하는가?

1. B가 park()를 호출하기 바로 직전에 CPU 스케줄링이 발생하여 A가 실행된다.
2. A가 락을 해제하고 B를 깨우기 위해 unpark()를 호출한다.
3. 하지만 B는 아직 park()를 호출하지 않았으므로, 실제로는 깨워질 수 없다. 따라서 B는 락이 해제되었음에도 불구하고 계속 대기 상태에 머물게 된다.

이러한 문제를 해결하기 위해 Solaris 운영체제는 setpark() 시스템 콜을 도입했다.

setpark()는 어떻게 동작하는가?

setpark()는 쓰레드가 “이제 곧 park()를 호출할 것이다”라고 시스템에 알리는 역할을 한다. 이렇게 하면, 만약 setpark() 호출 후에 락이 해제되어 unpark()가 호출되면, 시스템은 이 정보를 캐시에 저장한다. 따라서 실제 park()가 호출될 때, 쓰레드는 잠들지 않고 바로 깨어나게 된다. 이런 방식으로 setpark()는 락을 해제하고 나서 쓰레드를 깨우는 동작 사이에서 발생할 수 있는 경쟁 조건을 해결한다.

guard 변수의 역할을 커널에서 담당하는 것도 하나의 방법이다. 커널은 락 해제와 실행 중인 쓰레드를 큐에서 제거하는 동작을 atomic하게 처리하기 위해 주의를 기울여야 한다.

15. 다른 운영체제, 다른 지원

Linux의 경우 futex라는 것을 지원한다. 각 futex는 특정 물리 메모리 주소와 연걸이 되어 있으며 futex마다 커널 내부의 큐를 가지고 있다. 호출자는 futex를 호출하여 필요에 따라 잠을 자거나 깨어날 수 있다.

void mutex_lock (int *mutex) {
	int v;
	
	if (atomic_bit_test_set (mutex, 31) == 0)
		return;
	atomic_increment (mutex);
	while (1) {
	if (atomic_bit_test_set (mutex, 31) == 0) {
		atomic_decrement (mutex);
		return;
	}

	v = *mutex;
	if (v >= 0)
		continue;
	futex_wait (mutex, v);
	}
}

void mutex_unlock (int *mutex) {

	if (atomic_add_zero (mutex났 0x80000000))
		return;
	
	futex_wake (mutex);

16. 2단계 락

2단계 락 기법은 락이 곧 해제될 것 같은 경우라면 회전 대기가 유용할 수 있다는 것에서 착안하였다.

1. 회전 단계(Spinning Phase): 락을 곧 획득할 수 있을 것이라는 기대하에, 쓰레드는 “회전” 하면서 대기한다. 즉, 쓰레드는 일정 시간 동안 루프를 돌면서 락의 상태를 확인하고, 가능하면 락을 획득하려고 시도한다.
2. 잠김 단계(Sleeping Phase): 첫 단계에서 락을 얻지 못한 경우, 이제는 쓰레드가 잠에 들어서 락이 해제될 때까지 기다린다. 락이 해제되면 쓰레드는 깨어나서 작업을 계속합니다.

앞서 본 Linux의 락은 이러한 형태를 밖는 락이지만 한 번만 회전한다. 일반화된 방법은 futex가 잠재우기 전에 일정 시간 동안 반복문 내에서 회전하도록 하는 것이다. 2 단계 락은 두 개의 좋은 개념을 사용하여 개선된 하나를 만들어 내는 하이브리드 방식의 일종이다.

뜬금없지만 책 추천

동시성 프로그래밍 - Rust, C, 어셈블리어로 구현하며 배우는 동시성 프로그래밍 A to Z