Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

1. Too Much Spinning: What Now?

앞서의 하드웨어 기반 락들은 간단하고 작동도 잘하지만, 이 해결법들은 어떤 경우, 너무 비효율적이게 될 수 있다. 단일 프로세서에서 두 스레드를 실행한다고 해보자. 이 중 한 스레드(스레드 0)가 락을 가지고 임계 영역에 있는 상태에서 인터럽트를 받았다고 해보자. 다른 한 스레드(스레드 1)은 락을 얻으려 하지만, 이미 이것이 사용 중에 있음을 알게 되고, 스핀하기 시작하고, 스핀하고, 계속 스핀한다. 타이머 인터럽트가 발생하면 스레드 0이 다시 돌아가서 할 일들을 다 마치고, 락을 풀게 된다. 스레드 1이 다시 실행될 때, 스핀을 할 필요가 없어지고 락을 얻을 수 있게 된다.

이와 같이 스피닝 상태에 빠지면, 스레드는 전체 타임 슬라이스를 변하지 않는 값을 체크하기 위해서 낭비하게 된다. 만약 더 많은 N개의 스레드가 락을 얻기 위해 경쟁하는 상황이라면 더 나쁘다. N-1개의 타임 슬라이스가 스핀하고 락을 가지고 있는 스레드가 락을 풀어줄 때까지 같은 방식으로 낭비될 것이기 때문이다.

어떻게 CPU에서 스핀하면서 필요 이상으로 시간을 낭비하지 않고 락을 만들어 낼 수 있을까?

하드웨어 지원만으로는 이 문제를 해결할 수 없고, OS의 지원도 필요하다. 어떻게 해야할지 생각해보자.

2. A Simple Approach: Just Yield, Baby

하드웨어 지원은 작동하는 락, 심지어는 공정한 락 획득까지도 가능하게 했다. 하지만 아직 문제가 남아있다. 임계 영역에서 문맥 전환이 일어나서 락을 가지고 있는 스레드가 실행될 때까지 끊임없이 스핀해야만 하는 문제는 어떻게 해결해야 할까?

다음 첫 번째 시도는 간단하고 친숙하다. 스핀을 해야하면, 그 대신 CPU 소유권을 다른 스레드에게 넘겨주는 것이다.

void init(){
	flag = 0;
}

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

void unlock(){
	flag = 0;
}

이 접근법에서는 OS의 기본 명령어 yield()를 가정한다. 이는 스레드가 CPU 소유권을 포기해 다른 스레드가 실행될 수 있게 하고 싶을 때 호출한다.

스레드는 running, ready, blocked의 세 상태 중 하나에 있을 수 있다. yield()는 호출자 스레드를 running 상태에서 ready 상태로 바꿔 다른 스레드를 running 상태로 올리기 위한 시스템 콜이다. 그러므로 yield()를 호출하는 스레드는 반드시 자기 자신을 디스케줄해야 한다.

두 스레드가 한 CPU에서 돌아가는 예를 생각해보자. 이 경우 yield-기반 접근법은 잘 작동한다. 만약 한 스레드가 lock()을 호출하게 되어 락이 이미 사용되고 있다는 것을 알게 되면, 이는 간단히 CPU를 양보하고, 다른 스레드가 실행되어 임계 영역에서의 일을 마칠 수 있게 해준다.

그렇다면 이번에는 100개의, 많은 스레드들이 하나의 락을 얻기 위해 경쟁하는 경우를 생각해보자. 이 경우 만약 한 스레드가 락을 얻고, 락을 풀어주기 전에 CPU를 선점당하면, 나머지 99개 스레드들은 lock()을 호출하고, 락이 사용되고 있음을 알게되고, CPU를 양보한다.

라운드-로빈 스케줄러와 같은 것을 가정한다면, 99개의 각 스레드들은 락을 가지고 있는 스레드가 다시 실행될 때까지 이 run-and-yield 패턴을 실행할 것이다. 그냥 스핀시키던 접근법보다야 낫지만, 이 접근법 또한 비용이 많이 든다. 문맥 전환의 비용은 상당히 높을 수 있고, 따라서 낭비도 많을 수 있기 때문이다.

더 큰 문제는, 이 접근법이 기아 문제에 대해서는 다루고 있지 않다는 것이다. 한 스레드는 다른 스레드들이 반복적으로 임계 영역에 들어가고 나가는 동안, 무한한 yield 루프에 빠질 수 있다. 기아 문제를 직접 다루는 접근법이 필요해지는 이유다.

3. Using Queues: Sleeping Instead Of Spinning

앞의 접근법들이 가지는 문제점은, 그것들이 너무 많은 것들을 우연에 맡긴다는 것이다. 스케줄러는 어떤 스레드가 다음으로 돌아갈지 결정한다. 만약 스케줄러가 나쁜 선택을 내리면, 스레드는 락을 기다리며 스핀하거나, CPU 소유권을 바로 양보해야 한다. 어떤 경우든 낭비가 일어날 가능성이 있고, 기아에 대한 대처도 없다.

그러므로 현재 락을 가지고 있는 스레드가 락을 놓아줬을 때, 어떤 스레드가 락을 얻게 할지에 대한 제어가 필요하다. 이를 위해서는 어떤 스레드들이 락을 얻기 위해 대기 중인지를 추적하기 위한 큐와 같이, 조금의 OS 지원이 필요하다.

간단하게 Solaris에서 제공하는 두 콜을 사용해보자. park()는 호출하는 스레드를 잠들게 하고, unpark(threadID)는 threadID로 지정되는 특정 스레드를 깨우는 데 쓰인다. 이 두 루틴들은 호출자가 이미 사용 중인 락을 얻으려 할 때 재우고, 락이 사용 가능해지면 깨우는 방식의 락을 구현하는 데 쓰인다. 이들이 어떻게 쓰이는지를 보기 위해 다음 코드를 살펴보자.

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;
}

이 예제에서는 두 가지 흥미로운 점이 있다.

1. 기존의 test-and-set의 아이디어를 사용하되, 좀 더 효율적인 락을 만들기 위해 락 대기자 큐를 이용한다.
2. 다음으로 누가 락을 얻을 것인지를 제어하고 기아를 피하기 위해 큐를 사용한다.

위 코드에서 guard가 어떻게 쓰이고 있는지를 알아챌 수 있을 것이다. 이는 기본적으로 가드는 락이 사용하고 있는 플래그와 큐 조작을 둘러싼 스핀-락이다. 따라서 이 접근법은 완전히 스핀-대기를 사용하지 않는 것이 아니다. 스레드는 락을 획득하거나 푸는 중에 인터럽트 당할 수 있고, 이를 얻기 위해 스핀-대기 중인 다른 스레드들을 재실행할 수 있다. 하지만 스피닝에 쓰이는 시간이 상당히 제한적이고, 따라서 이 접근법은 쓸 만하다.

lock() 안에서, 스레드가 락을 획득하지 못하는 경우, 상당히 조심스럽게 스레드를 큐에 넣고, 가드를 0으로 만들고, CPU 소유권을 양도한다는 것을 볼 수 있다. 만약 가드 락의 해제가 park()의 앞이 아니라 뒤에 나타난다면 어떤 일이 일어날까?

다른 스레드가 깨어났을 때 플래그가 다시 0으로 설정되지 않는다는 것도 알 수 있다. 왜 그럴까? 스레드가 깨어나는 것은 쓰레드가 park()로부터 리턴한 것처럼 보인다. 하지만 이때 스레드는 가드 락을 가지고 있지 않아, 플래그를 1로 설정하려는 시도조차 할 수 없다. 그러므로 락을 놓아주는 스레드로부터 이를 얻으려고 하는 스레드로 직접 락을 전달해줘야 한다. 이 사이에 플래그는 0이 되지 않는다.

마지막으로, 이 해결법에서는 park()를 호출하기 직전에 경쟁 조건이 발생한다는 것을 알아차릴 수 있을 것이다. 한 스레드가 락이 더 이상 사용되고 있지 않을 때까지 sleep한다 가정하고 park를 하려 한다해보자. 그때 타이밍 안 좋게 다른 스레드로(락을 가지고 있는 스레드라 해보자) 문맥 전환이 일어나면 문제가 발생한다. 만약 락을 가지고 있는 스레드가 락을 놓으면, park를 하려던 스레드는 영원히 sleep하게 될 수도 있다. 이러한 문제는 wakeup/waiting race라 불린다.

Solaris는 이 문제를 setpark()라는 세 번째 시스템 콜을 추가함으로써 해결한다. 스레드는 이 루틴을 호출함으로써 자신이 곧 park할 것임을 알릴 수 있다. 만약 이때 인터럽트가 일어나 다른 스레드가 park가 실제로 호출되기 전에 unpark를 호출하면, 이어지는 park는 sleep하지 않고 즉시 리턴한다. lock() 내의 수정된 코드는 다음과 같다.

queue_add(m->q, gettid());
setpark();
m->guard;

다른 해결법으로는 가드를 커널로 전달하는 방법도 있겠다. 이 경우, 커널은 원자적으로 락을 해제하고 실행인 스레드를 큐에서 없애기 위해 주의해야한다

4. Different OS, Different Support

지금까지 스레드 라이브러리에서 좀 더 효율적인 락을 만들기 위해 OS가 제공할 수 있는 지원의 한 종류에 대해 알아봤다. 다른 OS들은 비슷한 지원을 제공하는데, 디테일은 조금 다르다.

예를 들어 리눅스는 Solaris의 인터페이스와 비슷하지만, 더 많은 커널 내부 기능을 제공하는 futex를 제공한다. 구체적으로 각 futex는 특정 물리 메모리 위치와 연관되어 있고, futex 마다의 커널 내부 큐를 가진다. 호출자는 futex 콜을 이용해 필요에 따라 자거나 깨어날 수 있다.

구체적으로는 두 콜을 사용할 수 있다. futex_wait(address, expected)는 주소 address의 값이 expected와 같은 경우 호출 스레드를 잠에 들게 한다. 만약 이 값이 서로 다르면, 이 콜은 즉시 리턴한다. 루틴 futex_wake(address)의 호출은 큐에서 대기 중인 한 스레드를 꺠운다. 리눅스에서 이 콜들을 사용한 뮤텍스 구현 코드를 보자.

void mutex_lock (int *mutex) {
	int v;
	// Bit 31 was clear, we got the mutex (fastpath)
	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;
		}
		// Have to waitFirst to make sure futex value
		// we are monitoring is negative (locked).

		v = *mutex;
		if (v >= 0) continue;

		futex_wait (mutex, v);
	}
}
void mutex_unlock (int *mutex) {
	// Adding 0x80000000 to counter results in 0 if and
	// only if there are not other interested threads
	if (atomic_add_zero (mutex, 0x80000000)) return;

	// There are other threads waiting for this mutex,
	// wake one of them up.
	futex_wake (mutex);
}

이 코드는 몇 가지 이유로 흥미롭다.

1. 이 코드는 하나의 정수 변수를 통해 락이 사용되고 있는지의 여부(변수의 최상위 비트)와 락 대기자의 수(나머지 비트)를 추적한다.
   • 만약 락이 음수라면, 이는 사용 중이라는 것을 의미한다.
2. 이 코드는 일반적인 경우, 구체적으로는 락에 대한 경쟁이 없는 경우를 어떻게 최적화 할 것인지를 보여준다.

5. Two-Phase Locks

리눅스 접근법에서는 1960년대 초기의 Dahm Locks로까지 거슬러올라가는, 오래된 접근법의 정취를 느낄 수 있다. 이는 two-phase 락이라 불리는데, 이는 특히 락이 곧 풀리려 하는 경우 스피닝이 유용할 수 있다는 것에서 착안한다. 첫 번째 단계에서 락을 얻을 수 있을 거라 기대하며 잠시동안 스핀한다.

만약 락이 첫 번째 단계에서 획득되지 못하면, 두 번째 단계로 들어간다. 이 단계에서 호출자는 잠들게 되고, 나중에 락이 사용 가능해질 때에 일어난다. 위의 리눅스 락은 이러한 락의 한 형태인데, 한 번만 스핀한다. 일반화된 방법은 잠들기 위한 futex의 지원을 사용하기 전에 고정된 시간 동안 반복문에서 스핀하는 것이다.

two-phase 락은 두 좋은 아이디어의 조합이 더 나은 것을 얻을 것이라는, 하이브리드 접근법의 일종이다. 물론 이것이 잘 작동할지는 하드웨어 환경, 스레드의 수, 세부 작업량 응의 여러 가지에 의존한다. 항상 그랬듯, 모든 가능한 경우에 사용할 수 있는 하나의 범용 락을 만드는 것은 어려운 일이다.

6. Summary

위의 접근법은 현대의 실제 락이 어떻게 만들어지고 있는지를 보여준다. 락을 만들기 위해서는 하드웨어 지원은 물론 OS의 지원도 필요하다. 물론 세부 내용은 달라질 수 있고, 이러한 락을 수행하기 위한 실제 코드들은 고도로 조정되어있다.