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

1. Controlling Interrupts

상호 배제를 제공하기 위한 초기의 해결법들 중 하나는 임계 영역에서의 인터럽트를 비활성화하는 것이었다. 이 해결법은 싱글-프로세서 시스템들을 위해 만들어졌으며, 코드는 다음과 같다.

void lock(){
	DisableInterrupts();
}

void unlock(){
	EnableInterrupts();
}

싱글 프로세서 시스템에서 임계 영역에 진입하기 전에 인터럽트가 일어나지 않도록 설정한다면, 임계 영역 내부의 코드가 방해를 받지 않고 원자적으로 실행될 수 있도록 할 수 있다. 해당 영역에서의 작업을 마치면 다시 인터럽트를 재활성화하고, 프로그램은 평소처럼 진행된다.

이 접근법은 단순하다는 장점을 가지고 있고, 어떻게 작동하는지에 대해 크게 고민할 필요도 없다. 스레드는 자신이 실행하고 있는 코드를 다른 스레드의 방해없이 실행할 수 있을 것이다. 문제는 단점들이 더 많다는 것이다.

우선 이 접근법은 모든 호출 스레드가 특권 연산을 수행할 수 있게 해야 하고, 그러한 허용이 오용되지 않을 것이라 믿어야 한다. 어떤 프로그램이 실행 초반에 lock()을 호출해 프로세서를 독점하는 경우를 생각해보자. 심지어는 오류가 있거나 악의적인 프로그램이 lock()을 호출해 무한 루프에 빠지게 하는 경우를 생각해보자. 후자의 경우, OS는 시스템에 대한 제어권을 다시 얻지 못한다. 범용 동기화를 위해 인터럽트 비활성화를 사용하는 것은 응용 프로그램에 대한 과한 신뢰를 필요로 한다.

다음으로, 이 해결법은 멀티프로세서 환경에서는 동작하지 않는다. 여러 스레드들이 다른 CPU에서 실행되고, 각자가 같은 임계 영역에 진입하고자 하는 경우를 생각해보자. 이때 한 프로세서에서의 인터럽트 비활성화 여부는 다른 프로세서의 스레드에 영향을 주지 못하므로, 다른 프로세서의 스레드는 임계 영역에 진입할 수 있게 된다. 멀티프로세서 시스템이 흔해진 오늘날, 이 접근법은 사용할 수 없다.

세 번째로, 오랫동안 인터럽트를 중지시키는 것은 인터럽트를 잃어버리게 만들 수 있고, 이는 심각한 시스템 문제로 이어질 수 있다. 디스크 장치가 읽기 요청을 완료했다는 사실을 CPU가 알지 못한다면, CPU는 해당 읽기 작업이 완료되기만을 기다리는 프로세스를 깨울 수 없게 될 것이다.

위와 같은 이유로, 인터럽트 비활성화는 상호 배제 기능을 위한 제한적인 맥락에서만 쓰여야 한다. 예를 들어, 어떤 경우 OS는 자신의 자료 구조에 접근하거나, 혹은 적어도 복잡한 특정 인터럽트 처리 상황이 일어나는 것을 방지하기 위해서 인터럽트를 비활성화할 수 있다. OS 내부에서는 어떤 특권 연산이라도 수행될 수 있으므로 신뢰 이슈가 발생하지 않는다. 이와 같은 제한적인 경우에서 만큼은 인터럽트를 비활성화해도 좋다.

2. A Failed Attempt: Just Using Loads / Stores

인터럽트 기반의 테크닉을 넘어, 제대로 된 락을 만들기 위해서는 CPU 하드웨어와 이것이 제공하는 명령어들에 의존해야 한다. 우선은 한 플래그 변수를 이용해서 간단한 락을 만들어보도록 하자. 이 실패한 시도를 통해, 락을 만들기 위해 필요한 기본적인 아이디어들에는 무엇이 있는지, 그리고 하나의 변수와 이에 접근하기 위한 일반적인 load, store의 사용이 왜 충분하지 않은 것인지에 대해 살펴본다.

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()을 호출해, 플래그가 1인지를 확인(이 경우에는 0일 것)하고, 플래그를 1로 바꾸어 해당 스레드가 락을 가지고 있다고 가리킨다. 임계 영역에서의 일이 끝나면 스레드는 unlock()을 호출하고 플래그를 0으로 만들어 락이 사용가능하다고 가리킨다.

만약 첫 번째 스레드가 임계 영역이 있을 때 다른 스레드가 lock()을 호출하게 되면, 해당 스레드는 첫 번째 스레드가 unlock()을 호출하고 플래그를 0으로 만들 때까지 while 루프에서 스핀-대기한다. 첫 번째 스레드가 작업을 마치면, 대기 중인 스레드는 while 루프에서 빠져나와 플래그를 1로 바꾸고 임계 영역으로 진입한다.

하지만 이 코드는 정확성(correctness)과 성능(performance), 두 측면에서 문제점을 가진다.

1. 정확성

시작할 때 flag = 0이라고 하자. 어떤 시점에 인터럽트가 발생하면, 두 스레드 모두 플래그를 1로 설정해, 두 스레드가 모두 임계 영역에 진입할 수 있게 될 수 있다.

2. 성능
   이 문제는 나중에 다시 다루게 될 것이다. 문제는 스레드가 이미 어떤 스레드에 의해 소유되고 있는 락을 얻기 위해 대기하는 방식에 있다. 이는 끊임없이 플래그의 값을 확인하는데, 이를 가리켜 스핀-대기(spin-waiting)이라 부른다. 스핀 대기는 다른 스레드가 락의 소유권을 놓을 때까지의 시간을 낭비한다. 이 낭비는 단일 프로세서에서 특히 심해, 락을 가지고 있는 스레드도 실행할 수 없게 만들기 때문이다(적어도 문맥 전환이 일어나기 전까지는). 앞으로는 이러한 종류의 낭비를 피할 수 있는 방법들을 고려하며, 좀더 정교한 해결법들을 만들어 가보도록 하자.

3. Building Working Spin Locks with Test-And-Set

인터럽트의 비활성화가 멀티프로세서에서는 작동하지 않고, 위와 같이 load-store를 사용하는 간단한 접근법도 작동하지 않기 때문에, 시스템 디자이너들은 락을 위한 하드웨어 지원을 만들어내기 시작했다. 이러한 지원은 멀티프로세서 시스템 초기에 만들어졌고, 오늘날의 모든 시스템들은 (싱글 CPU 시스템조차도) 이러한 종류의 지원을 제공한다.

가장 간단한 하드웨어 지원은 test-and-set(또는 atomic exchange) 명령어라 불리는 것인데, 다음의 C 코드 스니펫을 통해 이 명령어가 어떤 일을 하는지 보자.

int TestAndSet(int * old_ptr, int new){
	int old = *old_ptr; //old_ptr에 있는 오래된 값을 가져옴
	*old_ptr = new; // old_ptr에 새로운 값을 저장
	return old; // 오래된 값을 반환/
}

test-and-set 명령어가 하는 일은 다음과 같다. old_ptr이 가리키는 값을 반환하고, 동시에 new의 값으로 업데이트한다. 핵심은 이 연산 시퀀스가 원자적으로 수행된다는 것이다. 이것이 "test and set"으로 불리는 이유는 오래된 값을 테스트하면서, 동시에 메모리 위치에 새로운 값을 설정하기 때문이다. 이 조금 더 강력해진 명령어는 간단한 스핀 락을 만드는 데에 충분하다.

이 락이 왜 작동하는지에 대해 제대로 이해해보자. 한 스레드가 lock()을 호출하고 어떤 다른 스레드도 락을 가지고 있지 않은 상태를 가정한다. 스레드가 TestAndSet(flag, 1)을 호출하면, 해당 루틴은 flag의 오래된 값(0)을 반환한다. 그러므로 플래그의 값을 테스트하는 호출 스레드는는 while 루프의 스피닝에 빠지지 않고 락을 획득한다. 스레드는 또한 원자적으로 값을 1로 설정해, 해당 락이 현재 사용되고 있음을 가리킨다. 해당 스레드가 임계 영역에서의 일을 마치면, 이는 unlock()을 호출해 플래그를 다시 0으로 바꾼다.

이번에는 락이 이미 어떤 스레드에 의해 소유되고 있는 상태, 즉 flag가 1인 상태를 생각해보자. 이 경우 락을 가지고 있는 스레드는 lock()을 호출하고나서 TestAndSet(flag, 1)을 호출한다. 이번에는 TestAndSet()이 플래그의 오래된 값, 즉 1을 반환하고, 동시에 이를 또 1로 설정한다. 락이 다른 스레드에 의해 소유되고 있는 동안 TestAndSet()은 반복적으로 1을 반환하고, 따라서 이 스레드는 락이 풀릴 때까지 스핀한다. 플래그가 다른 스래드에 의해 0으로 설정되면, 이 스레드는 TestAndSet()을 다시 호출한다. 이 TestAndSet()은 0을 반환하고, 또한 원자적으로 값을 1로 바꿔 락을 얻어 임계 영역에 진입한다. test와 set을 원자적인 연산으로 만듦으로써, 오직 하나의 스레드가 락을 가지고 있음을 보장할 수 있는 것이다.

왜 이런 종류의 락이 스핀 락(spin lock)이라고도 불리는지에 대해 이해할 수 있을 것이다. 스핀 락은 가장 만들기 쉬운 종류의 락으로, 락이 사용 가능해질 때까지 계속해서 CPU 사이클을 사용하며 스핀한다. 이 방식이 싱글 프로세서에서 잘 작동하려면 선점적인 스케줄러를 필요한데, 선점이 없으면 CPU에서 스핀 중인 스레드가 CPU 소유권을 포기하지 않고 독점하게 될 것이기 때문이다.

4. Evaluating Spin Locks

스핀 락이 얼마나 효과적인지에 대해 평가해보자.

(1) correctness

락에 있어서 가장 중요한 측면은 정확성, 즉 이것이 상호 배제를 제공하는지다. 스핀 락은 한 시점에 오직 하나의 스레드만이 임계 영역에 들어갈 수 있게 한다. 즉 상호 배제를 제공한다.

(2) fairness

스핀 락은 대기 중인 스레드가 언젠가는 임계 영역에 들어갈 것임을 보장할 수 있을까? 불행히도 스핀 락은 공정성(fairness)을 보장하지는 못한다. 스핀 중인 스레드는 영원히 스핀할 수 있다. 간단한 스핀 락은 공정하지 못해, 기아(starvation)를 발생시킬 수 있다.

(3) performance

성능을 분석하기 위해 여러 다른 경우들을 생각해보자. 우선은 여러 스레드들이 단일 프로세서에서 락을 얻기 위해 경쟁하고 있는 상황을 생각해보고, 다음으로는 스레드들이 여러 CPU에 퍼져있는 경우를 생각해본다.

단일 CPU의 경우, 스핀 락의 성능 오버헤드는 꽤 클 수 있다. 락을 가지고 있는 스레드가 임계 영역에 있는 상태에서 CPU 제어권을 뺏긴 경우를 생각해보자. 스케줄러는 다른 모든 스레드들을 실행할 것이고, 이 스레드들은 모두 락을 얻으려 할 것이다. 이 경우 이 모든 스레드들은 CPU 소유권을 포기할 때까지 계속해서 스핀할 것이고, 이는 CPU 사이클의 낭비로 이어진다.

반대로, 여러 개의 CPU를 쓰는 경우 스핀 락은 꽤 잘 작동한다. CPU1에 스레드 A가 있고, CPU2에 스레드 B가 있으며, 이 두 스레드 모두가 락을 두고 경쟁하고 있다고 해보자. 만약 스레드 A가 락을 가지고 있고 스레드 B가 락을 얻으려고 한다면, B는 CPU2에서 스핀한다. 임계 영역이 짧다고 가정해보자. 락은 곧 사용 가능해지고 스레드 B에 의해 획득될 것이다. 이 경우 락이 다른 프로세서에서 락을 얻을 때까지 기다리려 스핀하는 것은 그리 많은 CPU 사이클을 소모하지 않고, 따라서 효과적이다.