멀티 스레드 환경에서의 락(Lock) 메커니즘

개요 

멀티 스레드 환경에서는 여러 스레드가 동시에 공유 자원에 접근할 수 있다. 이때 하나의 스레드가 값을 읽거나 수정하는 도중에 다른 스레드가 접근하게 되면 정합성에 문제가 발생할 수 있다. 이러한 구역을 임계영역(Critical Section)이라 하며, 반드시 동시에 하나의 스레드만 접근할 수 있도록 상호배제(mutual exclusion)이라는 기법을 지켜야한다.

 

balance라는 공유 변수를 1증가시키는 연산을 수행하고 있다. 이때 소스코드의 임계영역을 락으로 둘러 그 임계구역을 마치 하나의 원자 단위 명령어인 것처럼 실행되도록 한다.

lock_t mutex;
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

락은 상호배제(mutual exclusion)기능을 제공하기 때문에, POSIX라이브러리는 락을 mutex라 부른다. 상호배제는 한 스레드가 임계영역 내에 있다면 다른 스레드가 해당 임계영역에 들어 올 수 없어서 이러한 이름이 붙었다.

 

초기에 단일 프로세스 시스템에서는 상호배제를 지원하기 위해 임계영역 내에 인터럽트를 비활성화하는 방법을 사용했다.
임계 영역에 진입하기 전에 인터럽트를 차단하면, 그 안에서 인터럽트가 발생할 수 없기 때문에 해당 코드 블록을 원자적(atomic)으로 처리할 수 있다.

void lock() {
	DissableInterrupts();
}

void unlock() {
	EnableInterrupts();
}

이 방법은 단순하다는 장점이 있으나, 치명적인 단점이 존재한다. 먼저스레드가 인터럽트를 활성화/비활성화하려면 특권(privileged)명령을 실행할 수 있어야 한다. 만약 악의적인 프로그램이 시작과 동시에 lock()을 호출하고 독점하여 사용할 수도 있을 것이다.

 

두 번째 단점은 단일 CPU환경에서만 유효한 방법이라는 것이다. 멀티프로세서 환경에서는 제대로 동작하지 않는다. 예를 들어, 여러 스레드가 각각 다른 CPU에서 실행 중이고, 동일한 임계 영역에 진입하려고 한다고 가정하자. 이 경우 한 CPU에서 인터럽트를 비활성화해도, 다른 CPU에서 실행되는 스레드의 동작에는 아무런 영향을 주지 못한다.

 

세 번째 단점은 장기간 인터럽트를 중단시키는 것은 비효율을 가져온다. CPU가 저장장치에서 읽기 요청을 마친 사실을 모르고 지나갔다고 가정해보자. 그렇다면 언제 대기중인 프로세스를 깨워야할까? 결국 언제 대기 중인 프로세스를 깨워야 할지 알 수 없게 되며, 시스템 자원이 낭비된다.

 

이러한 문제들로 인해, 인터럽트를 비활성화하는 방식은 현대 운영체제에서 제한된 경우에만 사용된다. 주로 운영체제 커널 내부에서 짧은 시간 동안 내부 자료구조를 보호할 필요가 있을 때 사용되며, 일반적인 사용자 코드나 멀티코어 환경에서는 보다 정교한 락 메커니즘(예: 스핀락, 세마포어 등)이 활용된다.

 

Test-And-Set(Atomic Exchange)

멀티프로세서 환경에서는 단일 CPU의 인터럽트를 비활성화하는 방식만으로는 상호배제를 보장할 수 없다. 따라서 시스템 설계자들은 하드웨어 수준에서 락(Lock)을 지원하는 명령어들을 도입하기 시작했고, 그 중 가장 기본적인 방법이 바로 Test-And-Set 혹은 Atomic Exchange라고 불리는 기법이다.

 

이러한 하드웨어 명령어가 존재하지 않는 환경에서는, 보통 다음과 같이 단순한 플래그(flag) 변수를 이용해 락을 구현하는 것을 생각해 볼 수 있다.

typedef struct__lock_t {int flag; } lock_t;

void init(lock_t *mutex) {
	mutex -> flag = 0;
}

void lock(lock_t *mutex) {
	while (mutex -> flag == 1);
	mutex -> flag = 1;
}

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

위 구현은 flag 값이 1인 경우 다른 스레드는 계속 대기하게 되어 상호배제를 보장하는 것처럼 보인다. 그러나 실제로는 원자성(atomicity)이 보장되지 않기 때문에 Race Condition이 발생할 수 있다.

 

예를 들어, 두 개의 스레드가 거의 동시에 while (mutex->flag == 1) 조건을 검사하여 false(=0)라고 판단하고, 연이어 둘 다 mutex->flag = 1을 수행할 수 있다. 이 경우 락을 동시에 획득하는 오류가 발생하며, 결국 임계 영역이 보호되지 않게 된다.

단순한 flag 변수 사용(출처: https://pages.cs.wisc.edu/~remzi/OSTEP/Korean/28_threads-locks.pdf)

 

 

앞에 아이디어는 하드웨어 지원 없이는 동작이 불가능하다. 이를 해결하기 위해 하드웨어 수준에서 제공되는 Test-And-Set 명령어를 사용할 수 있다. 이 명령어는 원자적(atomic)연산을 제공한다.

 

TestAndSet 명령어가 동작하는 방식은 다음과 같다. ptr이 가르키고 있던 예전의 값을 반환하고, 동시에 new에 새로운 값을 저장한다. 여기서 핵심은 이 작업이 원자적으로 처리된다는 것이다.

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

 

스핀 락(Spinlock) 구현

앞서 살펴본 Test-And-Set 명령어를 기반으로 실제 락을 구현해보자. 이를 스핀락(spinlock)이라고 부른다. 이름 그대로, 락을 획득할 때까지 반복 루프를 돌며 계속 기다리는 방식이기 때문에 스핀(spin)이라는 이름이 붙었다. 이 방식은 락을 오래 기다리지 않는 상황에 효과적이다.

typedef struct __lock_t {
    int flag;
} lock_t;

void init(lock_t *lock) {
    lock->flag = 0;
}

int TestAndSet(int *old_ptr) {
    int old = *old_ptr;
    *old_ptr = 1;
    return old;
}

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag) == 1);  // flag가 1이면 락이 잡혀있는 상태
}

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

첫 번째 스레드가 lock()을 호출하고, 현재 락을 아무도 보유하지 않은 상황(flag = 0)이라고 가정하자. TestAndSet(&lock->flag, 1)이 호출되면, 이 명령어는 원자적으로 flag의 현재 값(0)을 반환하고 그 값을 즉시 1로 바꾼다. while문의 조건이 (0 == 1)이 되어 거짓이므로, 스레드는 루프를 돌지 않고 락을 획득하게 된다.

 

이제 두 번째 스레드가 lock()을 호출한다고 가정해보자. 락은 이미 첫 번째 스레드가 보유하고 있으므로 flag값은 1이다. 이때 TestAndSet(&lock->flag, 1)을 호출하면, 명령어는 flag의 현재 값인 1을 반환하고 그 값을 다시 1로 설정한다. while문의 조건이 (1==1)로 참이므로, 두 번째 스레드는 첫 번째 스레드가 락을 해제할 때까지 계속 루프를 돌게 될 것이다.

 

이처럼 값 검사(test)와 설정(set)이 하나의 원자적 동작으로 보장되기 때문에, 오직 하나의 스레드만 임계 영역에 진입할 수 있다. 스핀락은 정확히 임계 영역에 하나의 스레드만 진입할 수 있으므로 상호배제를 지킨다. 그러나 스핀락은 While문 회전 중인 스레드는 경쟁에 밀려 계속 그 상태로 남아 있을 수도 있다. 즉, 기아 상태(starvation)가 발생할 수 있다. 또한 while문을 돌며 대기하는 것은 효율적이지 않은 방식이다.

 

Compare-And-Swap(CAS)

CAS(Compare-And-Swap)기법은 원자적 연산을 제공하는 하드웨어 명령어 중 하나로, 락을 사용하지 않고도 공유 자원에 대한 경쟁 조건(Race Condition)을 제어할 수 있어, 비관적 락(Pessimistic Lock)이 아닌 낙관적 동시성 제어(Optimistic Concurrency Control)를 구현하는데 자주 사용된다.

 

CAS의 핵심 동작은 다음과 같다. ptr이 가리키는 메모리 주소의 값이 expected와 일치하는지 검사하고, 일치할 경우에만 해당 값을 새로운 값(new)으로 교체한다. 일치하지 않으면 아무 작업도 수행하지 않는다. 이때 기존 값을 반환함으로써, CAS를 호출한 쪽에서는 성공 여부를 판단할 수 있다.

 

아래 코드는 CAS 명령어의 동작 방식을 논리적으로 표현한 것이다. (실제 명령어는 하드웨어 수준에서 원자적으로 처리된다.)

int CompareAndSwap(int *ptr, int expected, int new) {
	int actual = *ptr;
	if (actual == expected) 
		*ptr = new;
	return actual;  // 작업 이전의 원래 값(actual)을 반환
}

 

이를 활용한 간단한 락 구현은 아래와 같다. 단순히 스핀락처럼 동작하도록 구현했기 때문에, 실제로는 스핀락과 동작 방식에 큰 차이가 없다.

void lock(lock_t *lock) {
	// flag의 현재 값이 0일 것이라 "예상"하고 1로의 변경을 시도한다.
	// 반환 값이 1이면, 예상과 달리 이미 락이 잡힌 상태이므로 계속 시도한다.
	while (CompareAndSwap(&lock->flag, 0, 1) == 1)
	; // busy waiting (spin)
}

하지만 CompareAndSwap 명령어는 TestAndSet보다 더 강력한 기능을 제공한다. 특히 락을 사용하지 않고 경쟁 조건을 제어하는 락 프리 동기화(lock-free synchronization)를 구현할 때, CAS의 진가가 발휘된다.

 

Fetch-And-Add

Fetch-And-Add 명령어는 메모리 주소가 가리키는 값에 대해 원자적으로 1을 증가시키고, 증가하기 전의 기존 값을 반환하는 연산이다.

이 연산은 여러 스레드가 동시에 접근해도 경쟁 없이 순서를 보장할 수 있는 특징이 있다.

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

 

이제 이 명령어를 활용하여, 공정한 순서 기반 락인 티켓 락(ticket lock)을 구현해보자. 티켓 락은 락을 요청하는 스레드에게 티켓 번호를 발급하고, 그 순서대로 락을 획득하도록 보장하는 방식이다. 따라서 공정성(fairness)을 중요하게 여기는 상황에서 유용하게 사용된다.

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)
	; // busy waiting
}

void unlock(lock_t *lock) {
	FetchAndAdd(&lock -> turn);
}

lock을 호출한 스레드는 FetchAndAdd를 통해 자신만의 myturn 번호를 할당받는다. 그리고 현재 차례를 나타내는 lock->turn 값이 자신의 번호와 같아질 때까지 while문에서 대기한다. unlock 동작은 lock->turn 값을 증가시켜, 대기 중인 다음 스레드에게 임계 영역에 진입할 차례를 넘겨주는 것이다.

 

이전의 접근 방법과 가장 큰 차이는 모든 스레드가 각자의 순서에 따라 진행된다는 점이다. 스레드가 티켓 값을 할당받는 순간, 미래의 어느 시점에는 반드시 실행될 것이 보장된다.

 

busy waiting 피하기

지금까지 살펴본 락 구현 방식들은, 락을 획득할 수 없는 경우 while문을 돌며 계속해서 확인하는 busy waiting(스핀) 방식을 사용해왔다. 하지만 이 방식은 심각한 비효율을 초래할 수 있다.

 

예를 들어, 스레드 0이 락을 보유한 상태로 인터럽트에 의해 CPU 실행이 중단되었다고 가정하자. 이때 스레드 1이 락을 획득하기 위해 진입하지만, 락은 이미 스레드 0이 점유 중이므로 스레드 1은 계속해서 스핀(루프)을 돌며 대기하게 된다.

이 상황에서 문제가 발생한다. 스레드 0은 실행 중단된 상태이기 때문에 락을 반환할 수 없고, 반면 스레드 1은 락이 언제 풀릴지도 모른 채 무한히 CPU 자원을 소비하게 된다. 결국 스레드 0이 타이머 인터럽트로 인해 다시 스케줄링되어 실행되고 락을 해제해야만, 스레드 1은 스핀을 멈추고 락을 획득할 수 있다. 이런 구조에서는 락을 기다리는 스레드가 많아질수록 상황은 더 나빠진다. 

 

양보 기반 락(yielding lock)

busy-waiting의 비효율성을 완화하기 위해, 스레드가 락을 획득하지 못했을 경우 CPU를 자발적으로 양보(yield)하는 방식을 사용할 수 있다. 

 

예를 들어, yield()는 자신에게 할당받은 CPU시간을 포기하고 다른 스레드가 실행될 수 있는 명령어라 가정한다. yield() 시스템 콜은 스레드의 실행중(running), 준비(ready), 막힘(blocked)이라는 세 가지 상태 중에 실행 중(running) 상태에서 준비(ready)상태로 전이하도록 한다.

 

만약 스레드1이 lock()을 호출하였지만 스레드 0이 락을 보유한 상황이면, 스레드 1은 계속해서 회전하지 않고 CPU 시간을 양보함으로써 스레드 0이 먼저 임계 영역을 빠져나올 수 있도록 돕는 것이다.

void init() {
	flag = 0;
}

void lock() {
	while (TestAndSet(&flag, 1) == 1)
		yield();
}

void unlock() {
	flag = 0;
}

하지만 이 방식도 한계는 명확하다. 100개의 스레드가 락 획득을 위해 경쟁하는 상황을 상상해보자. 스레드 0이 락을 보유하고 있다면, 나머지 99개의 스레드는 lock()을 호출했다가 모두 yield()를 실행하여 준비(Ready) 상태로 돌아갈 것이다.

 

만약 스케줄러가 이 99개의 스레드를 순서대로 한 번씩 다시 실행시킨다면(라운드 로빈 방식), 정작 락을 풀어줘야 할 스레드 0은 아주 한참 뒤에나 실행 기회를 얻게 된다. 결국 99번의 불필요한 문맥 교환(Context Switching)만 반복하는 셈이다. 따라서 yield 방식은 바쁜 대기보다는 낫지만, 여전히 문맥 교환 비용이 커서 비효율적인 상황이 발생할 수 있다.

 

큐의 사용

다수의 스레드가 락을 대기하고 있을 경우, 락을 획득할 스레드를 명시적으로 제어할 수 있어야한다. 이를 위해 운영체제의 지원을 기반으로, 대기 중인 스레드들을 큐로 관리하는 방식이 활용된다.

 

이러한 방식에서는 보통 park()와 unpark(threadID)같은 시스템 콜을 이용한다. park()는 스레드를 잠재우는 함수, unpark(threadID)는 threadID에 명시된 특정 스레드를 깨우는 함수이다. 

 

이 두가지를 활용하면 TestAndSet과 같은 하드웨어 지원 락 방식에서 대기 큐를 결합하여 보다 효율적인 락 구현이 가능해진다. 즉, 락을 획득하지 못한 스레드는 불필요한 busy waiting 대신 큐에 들어가 sleep 상태로 대기하고, 락이 해제될 때 선택된 스레드만 깨워 실행함으로써 CPU자원을 절약하고 기아(starvation)도 방지할 수 있다.

 

아래의 코드는 guard변수를 이용한 스핀락으로 큐와 flag변수를 보호하고 있다. 이때 스핀락을 사용하는데 이 스핀락은 기존과 다르게 락과 언락 내부의 몇개의 명령어만 수행한 뒤 곧바로 해제되므로, 전통적인 스핀락에 비해 busy waiting 비용이 매우 작다.

typedef struct __lock_t {
    int flag;        // 락 보유 여부
    int guard;       // queue 및 flag 보호용 스핀락
    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); // 회전하면서 락 획득
	if (m -> flag == 0) {
		m -> flag = 1; // 락을 획득함
		m -> guard = 0;
	} else {
		queue_add(m->q, gettid());
		m -> guard = 0; // guard락 해제
		park();  // 스레드 재우기
	}
}

void unlock(lock_t *m) {
	while (TestAndSet(&m -> guard, 1) == 1);
	if (queue_empty(m->q))
		m->flag = 0;
	else 
		unpark(queue_remove(m->q));
	m->guard = 0;
}

 

2단계 락

2단계 락은 락이 곧 해제될 가능성이 높은 경우, 무조건 sleep이나 yield로 빠지는 것보다 일정 시간 동안 busy waiting을 허용하는 것이 오히려 효율적일 수 있다는 것이 출발한 기법이다.

스핀락은 간단하고 빠르지만, 락을 오래기다려야 하는 상황에서 CPU 자원을 낭비한다. 반면, Sleep기반 락은 자원은 아끼지만 락이 실행 상태(running)에서 대기 상태(blocked)로 전환시키고, 다시 스케줄러가 해당 스레드를 깨워 실행 상태로 복귀시키는 과정을 거친다.

즉, 락이 빠른 시간 내에 해제 될 것이라면 스핀락이 더 좋을 수 있다. 이러한 트레이드 오프를 절충 시킨 방식이 바로 2단계 락이다.

1단계에서는 busy waiting으로 스핀하면서 대기하고 이 기간에 락을 획득하면, 빠른 락 획득을 한다. 2단계에서는 1단계에서 일정 횟수 이상 스핀했음에도 불구하고 락을 획득하지 못한 경우, park(), yield() 등의 메커니즘으로 CPU를 양보하거나 Sleep 상태로 전환한다.

 

마무리

멀티스레드 환경에서 락 구현은 단순히 상호배제만을 보장하는 것으로 끝나지 않는다. CPU자원의 효율성, 컨텍스트 스위칭 비용, 기아(starvation)방지를 위한 공정성(fairness) 등 다양한 고려사항이 함께 수반된다.

 

초기의 Test-And-Set, Compare-And-Swap 등 하드웨어 지원의 원자적 연산 지원을 바탕으로 스핀락 처럼 비교적 단순했다. 이는 상호배제를 보장했지만, busy waiting으로 인한 CPU 낭비와 기아 상태(starvation)를 유발하는 공정성 문제를 가지고 있었다.

 

이러한 문제들을 해결하기 위해 스레드를 양보(yield)시키거나 잠재우는(sleep)방식이 도입되었다. 이 방식은 CPU낭비와 공정성 문제를 해결하게 되었지만 문맥 교환(Context Switching)이라는 또 다른 오버헤드를 발생시켰다. 락을 기다리는 시간이 매우 짧을 경우, 스레드를 재우고 깨우는 비용이 오히려 스핀락보다 비쌀 수 있기 때문이다.

 

결국, 현대 운영체제에서는 두 방식의 장점을 결합한 하이브리드 방식인 2단계 락과 같은 형태로 진화했다. 좋은 락을 만드는 과정은 트레이드 오프 속에 시스템에 적합한 균형점을 찾아 나가는 과정이라 생각 할 수 있다. 따라서 각 락의 기본 동작과 장단점을 이해하고 자신이 마주한 상황에 가장 적합한 동기화 기법을 선택하는 것이 실전에서 핵심이라 생각된다.

 

참고 자료

- Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-dusseau, 운영체제 아주 쉬운 세 가지 이야기(ostep), 2020.09.10 홍릉, 333p - 357p