[운영체제 아주 쉬운 세 가지 이야기 - Concurrency] 28. Locks

Posted Sep 24, 2025

Operating System

By JJM

views 58 min read

이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.

개요

병행성에 대한 소개 이후 병행 프로그램의 근본적인 문제 몇 개를 살펴보았다. 여러 개의 명령어들을 원자적으로 실행해보고 싶지만 단일 프로세서의 인터럽트로 인해서 (또는 멀티 쓰레드를 여러 프로세서에 병행성하려고 해서) 그렇게 할 수 없었다. 이 장에서는 앞서 다룬 락(lock)을 이용하여 이 문제를 직접적으로 다루고자 한다. 프로그래머들은 소스 코드의 임계 영역을 락으로 둘러서 그 임계 영역이 마치 하나의 원자 단위 명령어인것처럼 실행되도록 한다.

락 : 기본 개념

예를 들어 다음의 임계 영역이 있다고 하자. 고전적인 공유 변수의 갱신이다.

  
balance = balance + 1;

연결 리스트에 노드를 삽입한다거나 공유 구조에 복잡한 갱신과 같은 다른 임계 영역을 사용할 수 있겠지만 간단한 예제를 사용해보자. 락을 사용하기 위해서 락으로 임계 영역을 다음과 같이 감쌌다.

  
lock_t mutex; // 글로벌 변수로 선언된 락

...

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

락은 하나의 변수이므로 떄문에 락을 사용하기 위해서는 락 변수를 먼저 선언해야 한다. 이 락 변수는 락의 상태를 나타낸다.

이 락은 어느 쓰레드도 락을 갖고 있지 않은 사용 가능(available) or 해제(unlocked) or free 상태일 수 있다. 또는 임계 영역에서 정확히 하나의 쓰레드가 락을 획득한 상태인 사용 중(acquired) 상태일 수 있다.

이 락 자료 구조에 락을 보유한 쓰레드에 대한 정보나 락을 대기하는 쓰레드들에 대한 정보를 저장할 수 있다. 물론, 이러한 정보는 락 사용자는 알 수 없다.

lock()과 unlock() 루틴의 의미는 간단하다. lock() 루틴 호출을 통해 락 획득을 시도한다. 만약 어떤 쓰레드도 락을 갖고 있지 않으면 그 쓰레드는 락을 획득하여 임계 영역 내로 진입한다. 이렇게 진입한 쓰레드를 락 소유자(owner)라고 부른다.

만약 다른 쓰레드가 lock()을 호출한다면 사용 중인 동안에는 lock() 함수가 리턴하지 않는다. 이와 같은 방식으로 락을 보유한 쓰레드가 임계 영역에 진입한 상태에는 다른 쓰레드들이 임계 영역 안으로 진입할 수가 없다.

락 소유자가 unlock()을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다. 어떤 쓰레드도 이 락을 대기하고 있지 않았다면 락의 상태는 사용 가능으로 유지된다. 만약에 대기 중이던 쓰레드가 있었다면 락의 상태가 변경되었다는 것을 인지하고 락을 획득하여 임계 영역 내로 진입하게 된다.

락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다. 일반적으로 쓰레드는 프로그래머가 생성하고 운영체제가 제어한다. 락은 쓰레드에 대한 제어권을 일부 이양 받을 수 있도록 해준다. 락을 코드로 감싸서 프로그래머는 그 코드 내에서는 하나의 쓰레드만 동작하도록 보장할 수 있다. 락을 통해 프로세스들의 혼란스런 실행 순서에 어느 정도 질서를 부여할 수 있다.

Pthread 락

쓰레드 간에 상호 배제(mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex라고 부른다. 상호 배제는 한 쓰레드가 임계 영역 내에 있다면 이 쓰레드의 동작이 끝날 때까지 다른 쓰레드가 임계 영역에 들어 올 수 없도록 제한한다고 해서 얻은 이름이다. 다음과 같은 POSIX 쓰레드 코드를 만나면 앞에서 언급한 것과 같은 동작을 이해하면 된다. (래퍼를 사용하여 락과 언락 시 에러를 확인하도록 하였다)

  
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock); // pthread_mutex_lock()을 위한 래퍼
balance = balance + 1;
Pthread_mutex_unlock(&lock);

POSIX 방식에서는 변수 명을 지정하여 락과 언락 함수에 전달하고 있다. 다른 변수를 보호하기 위해서 다른 락을 사용할 수도 있기 때문이다. 이러한 방식을 통해 동시에 더 많은 일을 처리할 수 있다.

하나의 락이 임의의 임계 영역에 진입할 때마다 사용하는 거친(coarse-grained) 락 사용 전략이 아니라, 서로 다른 데이터와 자료 구조를 보호하기 위해 여러 락을 사용하여 한 번에 여러 쓰레드가 서로 다른 락으로 보호된 코드 내에 각자가 진입 가능하도록 하는 세밀한(fine-grained) 락 사용 전략을 사용한다.

락 구현

그렇다면 효율적인 락은 어떻게 만들어야 하는가? 효율적인 락은 낮은 비용으로 상호 배제 기법을 제공하고 다음에 다룰 몇 가지 속성을 추가로 가져야 한다. 어떤 하드웨어 지원이 필요하고 어떤 운영체제 지원이 필요한가?

사용 가능한 락을 만들기 위해서는 하드웨어와 운영체제의 도움을 바당야 한다. 오랜 기간에 걸쳐 다양한 컴퓨터 구조의 명령어 집합에 여러 하드웨어 명령어들이 추가되었다.

락의 평가

어떤 락이든 만들기 전에 목표를 이해해야 하고 구현의 효율을 어떻게 평가할지 알아야 한다. 락이 잘 동작하는지 평가하기 위해 먼저 기준을 정해야 한다.

첫째. 상호 배제를 제대로 지원하는가

가장 기본 역할이다. 기본적으로 락이 동작하여 임계 영역 내로 다수의 쓰레드가 진입을 막을 수 있는지 검사해야 한다.

둘째. 공정성(fairness)

쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가? 이것을 보는 다른 관점은 좀 더 극단적인 상황을 평가해 보는 것이다. 락을 전혀 얻지 못해 굶주리는 기아 상태가 발생하는가?

셋째. 성능

특히 락 사용 시간적 오버헤드를 평가해야 한다. 이 주제에 대해서 고려해야 할 몇 가지 사항이 있다.

경쟁이 전혀 없는 경우의 성능. 하나의 쓰레드가 실행 중에 락을 획득하고 해제하는 과정에서 발생하는 부하는 얼마나 되는가?
여러 쓰레드가 단일 CPU 상에서 락을 획득하려고 경쟁할 때의 성능.
멀티 CPU 상황에서 락 경쟁 시의 성능

이런 서로 다른 상황의 성능을 평가하여야 앞으로 다룰 다양한 락 기법들이 성능에 미치는 영향을 이해할 수가 있다.

인터럽트 제어

초기 단일 프로세스 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용했었다.

  
void lock() {
    DisableInterrupts();
}
void unlock() {
    EnableInterrupts();
}

그렇게 동작하는 단일 프로세서를 사용한다고 가정해 보자. 임계 영역에 진입하기 전에 특별한 하드웨어 명령어를 사용하여 인터럽트를 막는다면 임계 영역 내의 코드에서는 인터럽트가 발생할 수 없기에 원자적으로 실행될 수 있다. 모든 동작이 끝난 후 에 다시 하드웨어 명령어를 사용하여 인터럽트를 사용 가능하도록 하여 프로그램이 이전처럼 진행할 수 있도록 한다.

이 방법의 장점은 단순하다는 것이다. 이 방법이 왜 제대로 동작하는지 이해하기 쉽다. 인터럽트가 발생하지 않으면, 코드가 실행 중에 다른 쓰레드가 중간에 끼어들지 않는다는 것을 보장할 수 있다.

하지만 이 방법은 단점이 많다. 먼저 이 요청을 하는 쓰레드가 인터럽트를 활성/비활성화하는 특권(privileged) 연산을 실행할 수 있도록 허가해야 한다. 또한 이를 다른 목적으로 사용하지 않음을 신뢰할 수 있어야 한다. 운영체제가 잘 알지 못하는 다른 프로그램을 신뢰해야 하는 경우가 생긴다면, 대부분 잘못된 것이라고 보면 된다.

몇 가지 경우의 형태를 살펴보자. 탐욕적(Greedy) 기법을 사용한 프로그램이 시작과 동시에 lock()을 호출하여 프로세서를 독점하여 사용할 수도 있다. 더한 경우라면 오류가 있거나 악의적인 프로그램이 lock()을 호출하고 무한 반복문에 들어갈 수도 있다. 후자의 경우라면 운영체제는 시스템의 제어권을 다시 얻을 수 없다. 동기화를 위해 인터럽트를 비활성화시키는 방법은 응용 프로그램을 너무 많이 신뢰해야 한다는 문제가 있따.

두 번째 단점은 멀티프로세서에서는 적용을 할 수가 없다는 것이다. 여러 쓰레드가 여러 CPU에서 실행 중이라면 각 쓰레드가 동일한 임계 영역에 진입하려고 시도할 수 있다. 이때에 특정 프로세서에서의 인터럽트 비활성화는 다른 프로세서에서 실행 중인 프로그램에는 전혀 영향을 주지 않는다. 결과적으로 임계 영역에 진입할 수 있다는 말이다. 멀티프로세서가 이제는 매우 흔하게 사용되고 있기 때문에 해결법은 더 정교해야 한다.

세 번째 단점은 장 시간 동안 인터럽트를 중지시키는 것은 중요한 인터럽트의 시점을 놓칠 수 있다는 것이다. 때로는 시스템에 심각한 문제를 가져올 수 있다. 예를 들어 CPU가 저장 장치에서 읽기 요청을 마친 사실을 모르고 지나갔다고 해보자. 운영체제가 이 읽기 결과를 기다리는 프로세스를 언제 깨울 수 있을까?

마지막으로 덜 중요할 수도 있겠지만, 이 방법은 비 효율적이다. 일반적인 명령어의 실행에 비해 인터럽트를 비활성화시키는 코드들은 최신의 CPU들에서는 느리게 실행되는 경향이 있다.

위의 이유로 상호 배제를 위하여 인터럽트를 비활성화하는 것은 제한된 범위에서만 사용되어야 한다. 예를 들어 운영체제가 내부 자료 구조에 대한 원자적 연산을 위해 인터럽트를 비활성화할 수 있다. 또는 적어도 복잡하게 보이는 인터럽트 발생을 방지하기 위해서 운영체제가 인터럽트를 비활성화할 수 있다. 운영체제 내부에서는 신뢰라는 문제가 사라지기에 운영체제가 특혜 받은 동작을 어떤 방식으로 처리하든 인터럽트를 비활성화하더라도 용인할 수 있다.

Test-And-Set (Atomic Exchange)

멀티프로세서에서는 인터럽트를 중지시키는 것이 의미가 없기에 시스템 설계자들은 락 지원을 위한 하드웨어를 설계하기 시작했다.

하드웨어 기법 중 가장 기본은 Test-And-Set 명령어 또는 원자적 교체(atomic exchange) 라고 불리는 기법이다. Test-And-Set의 동작을 이해하기 위해서 간단한 플래그 변수로 락을 구현해 보자.

위의 그림에서 사용한 아이디어는 간단하다. 간단한 변수를 사용하여 쓰레드가 락을 획득하였는지를 나타낸다.

임계 영역에 진입하는 첫 쓰레드가 lock()을 호출하여 플래그 값이 1인지 검사(test)하고, 플래그의 값을 1로 설정(set)하여 이 쓰레드가 락을 보유(hold)하고 있다고 표시한다. 임계 영역에서 나오면 쓰레드가 unlock()을 호출하여 플래그 값을 초기화하여 락을 더 이상 보유하고 있지 않다고 표시한다.

만약 첫 번째 쓰레드가 임계 영역 내에 있을 때 다른 쓰레드가 lock()을 호출하면, 그 쓰레드는 while 문으로 spin-wait을 하며 처음 쓰레드가 unlock()을 호출하여 플래그를 초기화하기를 기다린다. 처음 쓰레드가 플래그를 초기화하면 대기하던 쓰레드는 while 문을 빠져나와 플래그를 1로 설정하고 임계 영역 내로 진입한다.

이 코드는 두 가지 문제가 있는데, 정확성과 성능이다. 정확성의 문제는 병행 프로그래밍에 익숙해지면 쉽게 알아 볼 수 있을 것이다.

위 그림에서 코드가 동작 중이고 시작할 때 flag = 0이라고 해보자. 적시에 인터럽트가 발생하면 두 쓰레드 모두 플래그를 1로 설정하는 경우가 생길 수 있어서 임계 영역에 두 쓰레드 다 진입할 수 있게 된다. 상호 배제 제공이라는 기본 요구 조건 보장에 실패했기에 잘못 만들어진거다.

성능의 문제는 사용 중인 락을 대기하는 방법에 문제가 있다. spin-wait라는 방법을 사용하여 플래그의 값을 무한히 검사하는데, 이 방법은 다른 쓰레드가 락을 해제할 때까지 시간을 낭비한다. 이 방법은 단일 프로세서에서 특히 매우 손해가 크다. 락을 소유한 쓰레드조차 실행할 수 없기 때문이다.

진짜 돌아가는 스핀 락의 구현

앞으로 다룬 예제의 아이디어는 좋았지만 하드웨어 지원 없이는 동작이 불가능하다. 다행히 어떤 시스템은 이 개념에 근간한 락 구현을 위한 명령어(어셈블리 명령어)를 제공한다는 것이다. 이 강력한 명령어는 시스템마다 다른 이름을 갖고 있다. SPARC에서는 load/store unsigned byte 동작을 하는 ldstub, x86에서는 원자적 교체 명령어인 xchg이다. 기본적으로 동일한 일을 수행하며 일반적으로 Test-And-Set라고 불린다. 다음의 C 코드의 일부를 사용하여 TestAndSet의 동작을 정의해보자.

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

TestAndSet 명령어가 하는 동작은 다음과 같다. ptr이 가리키고 있던 예전의 값을 반환하고 동시에 new에 새로운 값을 저장한다. 여기서의 핵심은 이 동작들이 원자적으로 수행된다는 것이다. test and set라고 부르는 이유가 이전 값을 검사하는 동시에 메모리에 새로운 값을 설정하기 때문이다. 약간 더 강력해진 이 명령어만으로 아래 그림에서 보인 간단한 스핀 락(spin lock)을 만들 수 있다.

이 락이 동작하는 이유를 재확인하자. 처음 쓰레드가 lock()을 호출하고 다른 어떤 쓰레드도 현재 락을 보유하고 있지 않다고 하자. 그리고 현재의 flag의 값은 0이다. 이 쓰레드가 TestAndSet(flag, 1)을 호출하면 이 루틴의 flag의 이전 값인 0을 반환한다. flag 값을 검사한 쓰레드는 while문에서 회전하지 않고 락을 획득할 수 있게 된다. 이 쓰레드는 flag 값을 1로 설정하여 락을 보유하고 있음을 표시한다. 이 쓰레드가 임계 영역 내의 동작을 끝마치면 unlock()을 호출하여 flag를 다시 0으로 변경한다.

생각해 볼 수 있는 두 번째 경우는 처음 쓰레드가 락을 획득하여 flag 값이 1인 상태이다. 두 번째 쓰레드가 lock()을 호출하여 TestAndSet(flag, 1) 루틴을 실행한다. 이번에는 TestAndSet()는 이미 락을 다른 쓰레드가 보유하고 있기 때문에 예전 값으로 1을 반환하는 동시에 flag 값을 1로 설정한다. 락을 보유하고 있는 쓰레드가 있는 한 TestAndSet는 계속 1을 반환한다. 두 번째 쓰레드는 락이 해제될 때까지 계속 while 문을 반복한다. 락이 보유하고 있는 쓰레드에 의해 flag 값이 0이 되면, 대기 중인 두 번째 쓰레드가 TestAndSet()를 호출하여 0을 받는 동시에 원자적으로 값을 1로 변경한다. 락을 획득하였으므로 임계 영역 내로 진입한다.

락의 값을 검사하고 새로운 값으로 설정하는 동작을 원자적 연산으로 만듦으로써 오직 하나의 쓰레드만 락을 획득할 수 있도록 만들었다. 이제 제대로 동작하는 상호 배제 함수를 만드는 방법을 배웠다.

지금 설명한 방법이 스핀 락이라고 불리는 이유를 이제 이해할 수 있을 것이다. 이것이 가장 기초적은 형태의 락으로서, 락을 획득할 때까지, CPU 사이클을 소모하면서 회전한다. 단일 프로세서에서 이 방식을 제대로 사용하려면 선점형 스케줄러(preemptive scheduler)를 사용해야 한다.

선점형 스케줄러는 필요에 따라 다른 쓰레드가 실행될 수 있도록 타이머를 통해 쓰레드에 인터럽트를 발생시킬 수 있다. 선점형이 아니면, 단일 CPU에서 스핀 락의 사용은 불가능하다. 왜냐하면 while 문을 회전하며 대기하는 쓰레드가 CPU를 영원히 독점하기 때문이다.

스핀 락 평가

기본적인 스핀 락을 이해했으니 이전 장에서 명시한 기준에 의해 스핀 락의 효율을 이제 평가해 볼 수 있다. 락에서 가장 중요한 측면은 상호 배제의 정확성이다. 상호 배제가 가능하다면 스핀 락은 임의의 시간에 단 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 한다. 제대로 동작하는 락이다.

그 다음의 항목은 공정성이다. 대기 중인 쓰레드들에 있어서 스핀 락은 얼마나 공정한가? 대기 중인 쓰레드에게 임계 영역에 진입할 기회가 주어진다는 것을 보장할 수 있겠는가? 여기서의 대답은 좋지 않다. 스핀 락은 어떠한 공정성도 보장해 줄 수 없다. 실제로 while 문을 회전 중인 쓰레드는 경쟁에 밀려서 계속 그 상태에 남아 있을 수 있다. 스핀 락은 공정하지 않으며 쓰레드가 굶주리게 만들 수 있다.

마지막 항목은 성능이다. 스핀 락을 사용할 때 지불해야 하는 비용은 무엇인가? 단일 프로세서를 사용할 때 락을 획득하기 위해 경쟁하는 경우와 여러 프로세서에 쓰레드가 퍼져 있는 경우를 생각해 보자.

단일 CPU의 경우에 스핀 락이 갖는 성능 오버헤드는 상당히 클 수 있다. 임계 영역 내에서 락을 갖고 있던 쓰레드가 선점된 경우를 생각해 보자. N-1개의 다른 쓰레드가 있다고 가정할 때 스케줄러가 락을 획득하려고 시도하는 나머지 쓰레드들을 하나씩 깨울 수도 있다. 이런 경우, 쓰레드는 할당받은 기간 동안 CPU 사이클을 낭비하면서 락을 획득하기 위해 대기한다.

반면에 CPU가 여러 개인 경우 (쓰레드의 개수와 CPU의 개수가 대충 같다면) 스핀 락을 꽤 합리적으로 동작한다. 쓰레드 A는 CPU 1에 쓰레드 B는 CPU 2에 락을 획득하기 위해 경쟁 중이라고 해 보자. 만약 CPU 1에 실행 중인 쓰레드 A가 락을 획득한 후에 쓰레드 B가 획득하려고 시도했다고 하면 B는 CPU 2에서 기다린다. 임계 영역의 구간이 매우 짧다고 하면 락은 곧 획득 가능한 상태가 될 것이고 쓰레드 B는 락을 획득하게 된다. 다른 프로세서에서 락을 획득하기 위해 while 문을 회전하면서 대기하는 것은 그렇게 많은 사이클을 낭비하지 않기 떄문에 효율적일 수 있다.

Compare-And-Swap

또 다른 하드웨어 기법은 SPARC의 Compare-And-Swap, x86에서는 Compare-And-Exchange가 있다. C로 작성된 이 명령어의 의사 코드는 다음과 같다.

  
int CompareAndSwap(int *ptr, int expected, int new) {
  int actual = *ptr;
  if (actual == expected)
    *ptr = new;
  return actual;
}

Compare-And-Swap 기법의 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는 것이다. 만얄 일치한다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경하고, 아니라면 아무 것도 하지 않는다. 원래의 메모리 값을 반환하여 CompareAndSwap를 호출한 코드가 락 획득의 성공 여부를 알 수 있도록 한다.

Compare-And-Swap 방법을 사용하면 Test-And-Set 방법을 사용했을 때와 같은 방식으로 락을 만들 수 있다. 예를 들면 앞서 사용한 lock() 루틴을 다음과 같이 변경할 수 있다.

  
void lock(lock_t *lock) {
  while (CompareAndSwap(&lock->flag, 0, 1) == 1)
    ; // 회전
}

그 이후의 코드는 앞서 사용한 Test-And-Set에서 사용한 예제와 동일하다. 이 코드는 앞선 예와 상당히 유사하게 동작한다. flag 변수가 0인지 검사하고 만약 그렇다면 자동적으로 1로 바꾸어 락을 획득한다. 다른 쓰레드가 락을 보유하고 있다면 락을 획득하려고 시도하는 쓰레드는 락이 획득 가능한 상태가 될 때까지 while문에서 회전하게 된다.

CompareAndSwap 명령어는 TestAndSet 명령어보다 더 강력하다. 대기없는 동기화(wait-free synchronization)를 다룰 때 이 루틴이 갖는 능력을 알게 될 것이다. 단순 스핀 락과 같은 식으로 만들어 사용하면 앞서 분석한 스핀 락과 다를 바 없이 동작한다.

Load-Linked와 Store-Conditional

어떤 플랫폼은 임계 영역 진입 제어 함수를 제작하기 위한 명령어 쌍을 제공한다. MIPS 구조에서는 load-linked와 store-conditional 명령어를 앞뒤로 사용하여 락이나 기타 병행 연산을 위한 자료 구조를 만들 수 있다. 아래 그림은 이 명령어들에 대한 C 의사 코드를 나타내었다.

load-linked는 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장한다. 실제 차이는 store-conditional 명령어에서 나타난다. store-conditional 명령어는 동일한 주소에 다른 스토어가 없었던 경우에만 저장을 성공한다. 저장이 성공하면, load-linked가 탑재했던 값을 갱신한다.

성공한 경우에는 store-conditional은 1을 반환하고, ptr이 가리키는 value의 값을 갱신한다. 실패한 경우에는 ptr이 가리키는 value의 값이 갱신되지 않고 0을 반환한다.

load-linked와 store-conditional을 상요하여 락을 만드는 방법을 살펴보자.

lock() 부분의 코드를 보면 쓰레드가 while 문을 돌며 락이 해제되어 flag가 0이 되기를 기다린다. 락이 획득 가능한 상태가 되면 쓰레드는 store-conditional 명령어로 락 획득을 시도하고 만약 성공한다면 쓰레드는 flag 값을 1로 변경한다. 그리고 임계 영역 내로 진입한다.

store-conditional 명령어가 실패할 수도 있다는게 중요하다. 쓰레드가 lock()을 호출하여 load-linked를 실행하고 락이 사용 가능한 상태이므로 0을 반환한다. store-conditional 명령어를 시도하기 전에 이 쓰레드는 인터럽트에 걸렸고 다른 쓰레드가 락 코드를 호출하고 load-linked 명령어는 실행하여 0을 반환 받은 후에 계속 진행한다고 해 보자. 이 시점에 두 쓰레드는 모두 load-linked 명령어를 실행하였고 각자가 store-conditional를 부르려는 상황이다.

이 명령어의 주요 기능은 오직 하나의 쓰레드만 flag 값을 1로 설정한 후에 락을 획득할 수 있도록 하는 것이다. store-conditional을 두 번째로 실행하는 쓰레드는 락 획득에 실패하고 다음 기회를 기다려야 한다. (load-linked와 store-conditional 명령어 사이에 다른 쓰레드가 flag의 값을 갱신했기 때문)

아래 코드처럼 간결하게 작성할 수도 있다.

  
void lock(lock_t *lock) {
  while (LoadLinked(&lock->flag) || !StoreConditional(&lock->flag, 1))
    ; // 회전
}

Fetch-And-Add

마지막 하드웨어 기반의 기법은 Fetch-And-Add 명령어로 원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시킨다. Fetch-And-Add 명령어의 C 언어로 된 의사 코드는 다음과 같다.

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

이 예제에서는 티켓 락을 소개한다.

하나의 변수만을 사용하는 대신 이 해법에서는 티켓(ticket)과 차례(turn) 조합을 사용하여 락을 만든다. 기본 연산은 간단하다. 하나의 쓰레드가 락 획득을 원하면, 티켓 변수에 원자적 동작인 fetch-and-add 명령어를 실행한다. 결과 값은 해당 쓰레드의 차례를 나타낸다. 전역 공유 변수인 lock->turn을 사용하여 어느 쓰레드의 차례인지 판단한다. 만약 한 쓰레드가 (myturn == turn)이라는 조건에 부합하면 그 쓰레드가 임계 영역에 진입할 차례인 것이다. 언락 동작은 차례 변수의 값을 증가시켜서 대기 중인 다음 쓰레드에게 임계 영역 진입 차례를 넘겨준다.

이전까지의 접근 방법과 이번 해법의 중요한 차이 중 하나는 모든 쓰레드들이 각자의 순서에 따라 진행된다는 것이다. 쓰레드가 티켓 값을 할당받았다면 미래의 어느 때에 실행되기 위해 스케줄되어 있다는 것이다. 이전까지의 해법들에서는 이러한 보장이 없었다. 예를 들어 Test-And-Set의 경우 다른 쓰레드들은 락을 획득/해제하더라도 어떤 쓰레드는 계속 회전만하고 있을 수 있다.

요약 : 과도한 스핀

이제까지 소개한 하드웨어 기반의 락은 간단하고, 제대로 동작한다는 큰 장점을 가지고 있다. 하지만 때로는 이러한 해법이 효율적이지 않은 경우도 있다. 두 개의 쓰레드를 프로세서가 하나인 시스템에서 실행한다고 해보자.

쓰레드 0이 임계 영역 내에 있어서 락을 보유한 상태에서 인터럽트에 걸렸다고 해보자. 두 번째 쓰레드인 쓰레드 1이 락을 획득하려고 시도하는데, 누군가 이미 갖고 있는 것을 알았다. 그래서 락을 대기하며 스핀하기 시작한다. 마침내 타이머 인터럽트에 의해서 쓰레드 0이 다시 실행하게 되고 락을 해제하게 된다. 마지막으로 쓰레드 1이 다시 실행하게 되면 그렇게 많이 스핀하지 않아도 락을 획득할 수 있게 된다. 쓰레드가 스핀 구문을 실행하면서 변경되지 않을 값을 변경되기 기다리며 시간만 낭비한다.

N개의 쓰레드가 하나의 락을 획득하기 위해 경쟁하게 되면 상황은 더욱 심각해진다. N-1개의 쓰레드에 할당된 CPU시간 동안, 비슷한 이유로 낭비하게 된다. 스판하면서 락 해제를 기다린다.

그렇다면 어떻게 스핀에 CPU 시간을 낭비하지 않는 락을 만들 수 있을까?

하드웨어의 지원으로만 이 문제를 해결할 수가 없다. 운영체제로부터의 지원이 추가로 필요하다.

간단한 접근법 : 무조건 양보!

하드웨어의 지원을 받아 많은 것을 해결하였다. 동작이 검증된 락과 티켓 락을 사용한 경우 락 획득의 공정성까지도 해결할 수 있었따. 하지만 문맥 교환이 되어 쓰레드가 실행이 되었지만 이전 쓰레드가 인터럽트가 걸리기 전에 락을 이미 획득한 상태라서 그 쓰레드가 락을 해제하기를 기다리며 스핀만 무한히 하는 경우에는 어떻게 해야 할 것인가?

첫 번째 시도는 단순하고 친근한 방법이다. 락이 해제되기를 기다리며 스핀해야 하는 경우 자신에게 할당된 CPU를 다른 쓰레드에게 양보하는 것이다.

이 방법에서는 운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 하는 yield() 기법이 있다고 가정한다. 하나의 쓰레드는 실행 중(running), 준비(ready), 막힘(blocked)이라는 세 가지 상태가 있다. 양보(yield)라는 시스템 콜은 호출 쓰레드 상태를 실행 중 상태에서 준비상태로 변환하여 다른 쓰레드가 실행 중 상태로 전이하도록 한다. 결과적으로 양보 동작은 스케줄 대상에서 자신을 빼는 것(deschedule)이나 마찬가지다.

단일 CPU 시스템에서 두 개의 쓰레드를 실행하는 예를 생각해 보자. 이 경우 양보를 기반으로 한 기법은 잘 동작한다. 만약 쓰레드가 lock()을 호출하였지만 다른 쓰레드가 락을 보유한 상호아이었다면 이 쓰레드가 갖고 있던 CPU 시간을 단순히 양보하여 먼저의 쓰레드가 동작하여 임계 영역 밖으로 나올 수 있도록 하는 것이다.

이번에는 100개 정도의 쓰레드들이 락을 획득하기 위해 경쟁하는 경우를 살펴보자. 이 경우 한 쓰레드가 락을 획득하고 선점되었다. 이때에 나머지 99개의 쓰레드가 각자 lock()을 호출하고 다른 쓰레드가 락을 보유하고 있기에 CPU를 양보한다. 라운드 로빈(round-robin) 스케줄러를 사용하는 경우라면 락을 갖고 있는 쓰레드가 다시 실행되기까지 99개의 쓰레드가 실행하고 양보하는 패턴으로 동작하게 된다. 99개의 시간 간격을 낭비하게 되는 회전 방식보다는 좀 더 좋기는 하지만 아직도 이 기법을 사용하는 비용이 만만치 않다. 문맥 교환 비용이 상당하며 낭비가 많다.

더 안좋은 것은 기아 문제는 전혀 손도 대지 못한 상황이라느 ㄴ것이다. 나머지 쓰레드들은 임계 영역에 반복적인 출입을 하고 있는데, 어떤 쓰레드는 무한히 양보만 하고 있는 경우가 있을 수 있어 해법이 필요하다.

큐의 사용 : 스핀 대신 잠자기

이전 방법들의 근본 문제는 너무 많은 부분을 운에 맡긴다는 것이다. 스케줄러가 다음으로 실행될 쓰레드를 선정하는데, 만약 스케줄러가 안 좋은 선택을 한다면 실행되는 스케줄러는 회전을 하면서 대기를 하거나, 또는 CPU를 즉시 양보해야 한다. 어느 것이 되었든 낭비의 여지가 있고 쓰레드가 굶주리게 되는 상황을 막지 못한다.

어떤 쓰레드가 다음으로 락을 획득할지를 명시적으로 제어할 수 있어야 한다. 이를 위해서는 운영체제로부터 적절한 지원과 큐를 이용한 대기 쓰레드들의 관리가 필요하다.

간단한 설명을 위해 Solaris의 방식을 사용하겠다. 두 개의 호출 문이 있는데, park()는 호출하는 쓰레드를 잠재우는 함수이고 unpark(threandID)는 명시된 특정 쓰레드를 깨우는 함수이다. 이 두 루틴은 이미 사용 중인 락을 요청하는 프로세스를 재우고 해당 락이 해제되면 깨우도록 하는 락을 제작하는 데 앞뒤로 사용할 수 있다. 아래 그림에 나타난 코드를 사용하여 예를 이해해 보자.

이 예제에서는 두 가지 흥미로운 것을 해볼 것이다. 첫 번째, 앞서 배운 Test-And-Set 개념을 락 대기자 전용 큐와 함께 사용하여 좀 더 효율적인 락을 만들 것이다. 두 번째, 큐를 사용하여 다음으로 락을 획득할 대상을 제어하여 기아 현상을 피할 수 있도록 해보겠다.

그림에서 guard 변수를 사용하여 flag와 큐의 삽입과 삭제 동작을 스핀 락으로 보호하는 데 사용한다. 이 방법은 회전 대기를 완전히 배제하지는 못했다. 이 쓰레드는 락을 획득하거나 해제하는 과정에서 인터럽트에 걸릴 수 있다. 다른 쓰레드는 락의 해제를 기다리며 회전 대기하게 된다. 하지만, 회전 대기 시간을 꽤 짧다. 사용자가 지정한 임계 영역에 진입하는 것이 아니라 락과 언락 코드 내의 몇 개의 명령어만 수행하면 되기 때문이다. 그렇기 때문에 이 접근법은 합리적이다.

두 번째로 lock() 내에 추가된 동작이 있다. lock()을 호출하였는데, 다른 쓰레드가 이미 락을 소유했기 때문에 자신은 락을 획득할 수 없다면, gettid()를 호출하여 현재 실행 중인 쓰레드 ID를 얻고, 락 소유자의 큐에 자기 자신을 추가하고 guard 변수를 0으로 변경한 후에 CPU를 양보한다.

그렇다면 park() 호출 전이 아니라 호출 후에 guard 락을 해제하면 어떤 일이 생길까? 좋지 않은 일이 발생한다.

다른 쓰레드가 꺠어났을 때 flag 변수가 0으로 설정되지 않는다는 사실을 깨달았을 것이다. 이건 필요에 의한 것인데 쓰레드가 깨어날 때는 마치 쓰레드가 park()에서 리턴하는 것과 같이 보인다. 하지만 그 시점에서는 guard 락을 획득한 상태가 아니기 때문에 flag 변수의 값을 1로 변경하는 것을 시도조차 할 수 없다. 그렇기 때문에 락을 획득하려는 다음 쓰레드로 직접 전달한다. 그 사이에 flag는 0으로 바뀌지 않는다.

마지막으로 이 해법에서 park() 직전에 경쟁 조건이 발생한다는 것을 인지 했을것이다. 이것을 인지하는 것은 사실 쉽지 않다. 한 쓰레드는 락이 사용 중이라 park() 문을 수행하려고 한다. 그 직전에 락 소유자한테 CPU가 할당된다면 문제가 발생할 수 있다. 예를 들어 락을 보유한 쓰레드가 그 락을 해제했다고 해 보자. 쓰레드가 자기 차례에 park()를 수행하면 깨어날 방법이 없다. 이 문제는 깨우기/대기 경쟁(wakeup/waiting race)이라고도 불린다. 이 문제를 피하기 위해서는 뭔가 더 해야 한다.

Solaris는 이 문제를 세 번째 시스템 콜인 setpark()를 추가하여 해결하였다. 이 루틴은 park()를 호출하기 직전이라는 것을 표시한다. 만약 그때 인터럽트가 수행되고 park()가 실제로 호출되기 전에 다른 쓰레드가 unpark()를 먼저 호출한다면, 추후 pakr() 문은 잠을 자는 대신 바로 리턴된다. lock() 내에서 변경되는 부분은 그리 많지 않다.

  
queue_add(m->q, gettid());
setpark(); // 새로운 코드
m->guard = 0;

guard 변수의 역할을 커널에서 담당하는 것도 하나의 방법이다. 그런 경우 커널은 락 해제와 실행 중인 쓰레드를 큐에서 제거하는 동작을 원자적으로 처리하기 위해 주의해야 한다.

다른 운영체제, 다른 지원

Linux의 경우 futex라는 것을 지원한다. 각 futex는 특정 물리 메모리 주소와 연결이 되어 있으며 futex마다 커널 내부의 큐를 갖고 있다. 호출자는 futex를 호출하여 필요에 따라 잠을 자거나 깨어날 수 있다.

futex에는 두 개의 명령어가 제공된다. futex_wait(address, expected) 명령어는 address의 값과 expected 값이 동일한 경우 쓰레드를 잠재운다. 같지 않다면 즉시 리턴한다.

futex_wake(address) 명령어를 호출하면 큐에서 대기하고 있는 쓰레드 하나를 꺠운다.

2단계 락

2단계 락(two-phase lock)은 락이 곧 해제될 것 같은 경우라면 회전 대기가 유용할 수 있다는 것에서 착안하였다. 첫 번째 단계에서는 곧 락을 획득할 수 있을 것이라는 기대로 회전하며 기다린다. 만약 첫 회전 단계에서 락을 획득하지 못했다면 두 번째 단계로 진입하여 호출자는 잠에 빠지고 락이 해제된 후에 깨어나도록 한다.

앞서 본 Linux의 락은 이러한 형태를 갖는 락이지만 한 번만 회전한다. 일반화된 방법은 futex가 잠재우기 전에 일정 시간 동안 반복문 내에서 회전하도록 하는 것이다.

2단계 락은 두 개의 좋은 개념을 사용하여 개선된 하나를 만들어 내는 하이브리드 방식의 일종이다. 물론 이 기법이 좋은지는 하드웨어 환경이나, 쓰레드 개수, 그리고 세부 작업량 등과 같은 많은 것들에 의존하기 때문에 확실하지 않다. 항상 그렇듯이, 모든 경우에 다 잘 동작하는 하나의 범용적인 락을 만든다는 것은 상당히 어려운 일이다.

참고

https://pages.cs.wisc.edu/~remzi/OSTEP/Korean/28_threads-locks.pdf

Computer Science, Operating System