[OS] 22-2. Locks (2)

Park Yeongseo·2024년 1월 24일

OS Thread lock 운영체제

OS

목록 보기

25/54

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 하드웨어와 명령어들에 의존해야 한다. 우선은 한 플래그 변수를 이용해서 간단한 락을 만들어보도록 하자.

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으로 만들 때까지 루프를 스핀하며 대기한다. 첫 번째 스레드가 작업을 마치면, 대기 중인 스레드는 루프에서 빠져나와 플래그를 1로 바꾸고 임계 영역으로 진입한다.

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

(1) 정확성 문제

스레드 1이 루프를 빠져나와 플래그를 변경하기 직전에 문맥 전환이 이루어지면, 두 스레드 모두 플래그를 1로 설정할 수도 있다. 두 스레드가 모두 임계 영역에 진입할 수 있게 되는 것이다.

(2) 성능 문제

스레드는 이미 누군가가 소유하고 있는 락을 얻기 위해 끊임없이 플래그의 값을 확인하는데, 이를 가리켜 스핀-대기(spin-waiting)이라 부른다. 스핀-대기를 사용하면 락을 소유하지 못해 어떤 작업도 할 수 없는 스레드라 하더라도 문맥 전환이 일어나기까지의 CPU 시간을 계속하게 낭비하게 되는데, 이렇게 CPU를 낭비시킬 시간에 락을 소유한 스레드가 일을 할 시간을 더 많이 주는 게 낫다.

이렇게 락을 얻을 수 있을 때까지 CPU 사이클을 사용하며 스핀하는 락을 스핀 락이라 부른다.

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

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

인터럽트의 비활성화 방식이나 load-store이나 단점이 적지 않기 때문에, 시스템 디자이너들은 락을 위한 하드웨어 지원을 만들어냈다. 이는 멀티프로세서 시스템 초기에 만들어져, 오늘날의 모든 시스템들은 이러한 종류의 지원을 제공한다.

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

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-and-set을 원자적인 연산으로 만들면 오직 하나의 스레드가 락을 가지고 있음을 보장할 수 있게 된다.

4. Evaluating Spin Locks

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

(1) correctness

스핀 락은 한 시점에 오직 하나의 스레드만이 임계 영역에 들어갈 수 있게 한다. 즉 상호 배제를 제공한다.

(2) fairness

스핀 락은 대기 중인 스레드가 언젠가는 임계 영역에 들어갈 것임을 보장할 수 있을까? 그렇지는 않다. 스핀 중인 스레드는 영원히 스핀할 수 있어, 기아(starvation)를 발생시킬 수 있다.

(3) performance

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

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

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