[OS] 22-4. Locks (4)

Park Yeongseo·2024년 1월 26일
OSThreadlock운영체제
1

OS

목록 보기
27/54
post-thumbnail

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에서 돌아가는 예를 생각해보자. 만약 한 스레드가 lock()을 호출한 후, 락이 이미 사용되고 있다는 것을 알게 되면, 이 스레드는 yield()를 호출해 다른 스레드가 임계 영역에서의 일을 마칠 수 있도록 CPU를 양보한다.

그렇다면 이번에는 100개 정도로 많은 스레드들이 하나의 락을 얻기 위해 경쟁하는 경우를 생각해보자. 이 경우 한 스레드가 락을 얻고, 락을 풀어주기 전에 CPU를 선점당하면, 나머지 99개 스레드들은 lock()을 호출하고, 락이 사용되고 있음을 알게되고, yield()를 호출해 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. 다음으로 누가 락을 얻을 것인지를 제어하고 기아를 피하기 위해 큐를 사용한다.

위 코드에는 눈여겨 볼 만한 것들이 여러 가지 있다.

  1. 가드는 락이 사용하고 있는 플래그와 큐 조작을 둘러싼 스핀 락이다.
    스레드는 락을 획득하거나 푸는 중에 인터럽트 당할 수 있고, 이를 얻기 위해 스핀-대기 중인 다른 스레드들을 재실행할 수도 있지만, 스피닝에 쓰이는 시간이 상당히 제한적이기에 낫기는 하다.

  2. lock() 안에서 스레드가 락을 획득하지 못하는 경우, 스레드를 큐에 넣고 가드를 0으로 만들고 CPU 소유권을 양도한다.

Q. 만약 가드 락의 해제가 park()의 앞이 아니라 뒤에 나타난다면 어떻게 될까?
A. 가드가 1인 상태로 남아있어 나머지 스레드들은 큐에 들어가지 못하게 된다.

  1. 큐의 다른 스레드를 깨울 때 따로 플래그를 0으로 설정하지는 않는다.
    큐 안의 스레드를 깨울 때 플래그는 계속 1로 유지하고 큐가 비어 어떤 스레드도 락을 필요로 하지 않을 때에만 비로소 플래그를 0으로 설정한다. 간단히 생각하면 깨우는 스레드가 깨어나는 스레드에게 락을 전달해주는 것이라고 생각해도 좋다.

  2. park()를 호출하기 직전에 경쟁 조건이 발생한다.
    락을 갖지 못한 스레드 A가 park()를 호출하기 직전에 락을 가지고 있는 스레드 B로의 문맥 전환이 일어난다고 해보자. B는 임계 영역의 코드를 실행하고 unlock()을 호출해 A를 큐에서 꺼내지만, A는 아직 잠들지 않은 상태다. 이후 A가 park()를 호출하고 잠들면 A를 깨워줄 수 없어진다. 이러한 문제를 wakeup/waiting race라 불린다.

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

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

그런데 이렇게만 하면 setpark()전에 문맥 전환이 났을 때 동일한 문제가 발생할 수도 있다. setpark()와 park()를 하나로 묶어서 원자적으로 처리해 주는 게 가능해진다면 해결 가능하기는 하다.

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

4. Different OS, Different Support

다른 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 락이라고 불리며, 락이 곧 풀리려 하는 경우에는 오히려 스피닝이 유용할 수도 있다는 점에 착안하고 있다.

  1. 첫 번째 단계에서는 곧 락을 얻을 수 있을 거라 기대하며 잠시 스핀한다.
  2. 만약 락이 첫 번째 단계에서 획득되지 못하면, 두 번째 단계로 들어간다.
  3. 두 번째 단계에서 호출자는 잠들게 되고, 나중에 락이 사용 가능해질 때에 일어난다.

위의 futex 락은 이러한 two-phase 락의 한 형태로 단 한 번만 스핀하지만, 일반적으로는 잠들기 위한 futex 지원을 사용하기 전에 일정 시간동안 반복문을 돌며 스핀하는 방식을 사용하곤 한다.

two-phase 락은 두 가지 유용한 기법을 결합해 더 나은 결과를 얻고자 하는, 일종의 하이브리드 접근법이다. 물론 이 방식이 실제로 잘 작동할지는 하드웨어 환경, 스레드의 수, 작업의 세부 특성 등에 따라 달라진다.

언제나 그렇듯, 모든 상황에 완벽히 들어맞는 범용 락을 만드는 것은 쉽지 않은 일이다.

6. Summary

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

profile
Park Yeongseo
블로그 이전 준비 중
이전 포스트

[OS] 22-3. Locks (3)

다음 포스트

[OS] 23. Lock-based Concurrent Data Structures

0개의 댓글