[OS] Lock으로 Mutual Exclusion(상호 배제) 구현하기 - OS 공부 19

안녕하세요 Pingu입니다!

 

지난 글에서는 동시성 프로그래밍에서 사용하는 스레드를 쉽게 사용할 수 있는 C언어 API들을 알아봤었는데요! 이번 글에서는 동시성 프로그래밍을 구현할 때 스레드를 사용하면 발생하는 문제점 중 하나인 공유 자원에 여러 스레드가 동시에 접근하려고 할 때 발생하는 문제를 해결하는 방법인 Lock에 대해 알아보려고 합니다. 제가 공부할 때 참고하는 책인 OSTEP에서는 Chapter 28 - Lock 부분 입니다!

Locks

지난 글들에서 Concurrency(동시성)에 대해 알아봤을 때 문제점들이 몇 가지 존재했었습니다. 그중 하나는 명령을 원자적으로 (여기서 원자적이라는 말은 특정 작업을 수행할 때 시작을 했으면 끝나는 것을 보장하는 것을 말합니다.) 수행하고 싶지만 프로세서에는 인터럽트라는 것이 존재하여 원자적으로 수행하기에 문제가 있었습니다. 원자적으로 진행하지 못한다면 스레드의 특징 중 하나인 데이터를 공유한다는 것 때문에 데이터 무결성이 보장되지 못할 수 있습니다. 이러한 문제를 해결하기 위해 이번 글에서는 Lock이라는 개념을 도입하여 이를 해결하는 방법에 대해 알아보겠습니다.

Locks: The Basic Idea

그럼 간단하게 Lock의 아이디어를 보고 넘어가겠습니다. 아래와 같이 Critical section(임계 영역)에 접근하는 코드가 있다고 해보겠습니다.

balance = balance + 1;

이 코드에 lock을 사용하려면 아래와 같이 코드를 추가하면 됩니다.

lock_t mutex;

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

Lock 변수를 하나 선언하고 임계 영역에 접근하기 전에 lock을 걸어줍니다. 만약 다른 스레드가 lock을 가지고 있지 않다면 현재 스레드가 lock을 가지고 임계 영역에 접근하게 됩니다. 임계영역에서의 작업이 끝나면 unlock으로 Lock을 해제하여 다른 스레드들이 임계영역에 접근할 수 있도록 하면 됩니다. 이렇게 간단하게 임계영역에 대한 접근을 lock으로 제어할 수 있는 것이죠!

Pthread Locks

POSIX 라이브러리에서 lock에 사용하는 이름은 스레드 간에 mutual exclusion을 제공하므로 이를 줄인 mutex입니다. 따라서 아까 봤던 lock을 사용하는 코드를 POSIX 라이브러리 코드로 바꾸면 아래와 같아집니다.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);
balance = balance + 1;
pthread_mutex_unlock(&lock);

Building A Lock

이제 간단히 코드로 어떻게 lock을 사용하는지 봤으니 이젠 해당 코드가 어떻게 작동하는지에 대해 알아보겠습니다. Lock은 어떻게 만들어질까요? 필요한 하드웨어의 지원과 OS 지원은 어떤 것이 있을까요?

 

Lock을 만들기 위해서는 하드웨어의 지원과 OS의 지원이 필요합니다. 이를 위한 몇 가지 명령어 세트들이 있고 이것들과 OS의 지원을 받아 Lock을 만드는 방법을 지금부터 알아보겠습니다.

Evaluating Locks

Lock을 만드는 방법을 알아보기 전에 어떤 Lock이 좋은 지부터 알아보겠습니다. 효율적인 Lock을 구현하기 위해서는 세 가지를 고려해야 합니다.

 

첫 번째는 lock이 mutual exclusion(상호 배제)를 제공하는지 여부입니다. Lock이 필요한 이유가 상호 배제를 지원하기 위해서였으니 이 부분은 반드시 수행해야 합니다.

 

두 번째는 fairness(공정성)입니다. 여러 개의 스레드가 lock을 획득하려고 할 때 스레드들이 공평하게 lock을 얻을 수 있는지에 대한 것이죠. 만약 우선순위에 밀려 특정 스레드가 계속해서 lock을 획득하지 못한다면 문제가 될 수 있습니다. Lock을 획득하지 못한다는 것은 임계 영역에 접근할 수 없는 말이기 때문이죠. 이러한 상황을 starve(기아상태)라고 합니다.

 

세 번째는 performance(성능)입니다. Lock을 만들고 사용하는 것도 당연하게 자원이 사용됩니다. 특히 시간이라는 자원이 중요한데요, 만약 스레드가 한 개만 존재할 때 lock을 획득하고 해제하는 것은 오히려 성능을 저하시키는 이유가 될 것입니다. 또한 CPU가 한 개 있을 때 여러 개의 스레드가 lock을 경쟁하는 상태, CPU가 여러개일 때 여러개의 스레드가 lock을 획득하기 위해 경쟁하는 경우에서의 성능을 살펴볼 필요가 있습니다.

Controlling Interrupts

어떠한 명령어가 원자성을 가지지 못한 채 진행되는 이유 중 하나는 interrupt입니다. 명령어가 진행 중 인터럽트를 받게 되면 명령어의 진행을 잠깐 멈추고 인터럽트를 처리하고 오기 때문인데요, 따라서 가장 간단하게 원자성을 구현할 수 있는 방법은 아래와 같이 인터럽트를 비활성화하는 것입니다.

// lock을 획득 할 땐 인터럽트를 무시하도록 만듭니다.
void lock() {
    DisableInterrupts();
}

// unlock 할 때는 다시 인터럽트를 받도록 만듭니다.
void unlock() {
    EnableInterrupts();
}

위와 같이 lock, unlock을 만들면 인터럽트를 제어하여 원자성을 보장하고 이는 상호 배제의 구현 방법이 될 수 있습니다. 즉 이 방법은 스레드가 임계 영역에 접근 중 일 때는 인터럽트를 받지 않는 것이죠. 정말 간단하게 구현할 수 있는 게 이 방법의 장점입니다만, 인터럽트를 받지 않는다는 것은 문제가 많아 보이지 않나요?

 

이 방법의 문제점은 무엇일까요? 먼저 이 방법을 사용하려면 스레드가 인터럽트를 켜고, 끌 수 있는 권한이 있어야 하며 이러한 권한을 줄 만큼 신뢰성이 있어야 합니다. 하지만 스레드는 임의의 프로그램을 수행하므로 신뢰성을 보장한다고 할 수 없죠. 따라서 Lock을 악의적으로 호출하여 프로세서를 독점한다거나 무한루프를 생성하여 OS가 시스템의 제어권을 다시 얻지 못하게 할 수도 있습니다.

 

다음 문제점은 위의 방법은 멀티 프로세서에서는 작동하지 않습니다. 여러 개의 스레드가 다른 CPU에서 실행 중이고 각 스레드가 동일한 임계 영역에 들어가려고 한다면 인터럽트의 비활성화 여부는 중요하지 않습니다. 따라서 멀티 프로세서에서 동작하는 방법을 찾아야 합니다.

 

또 다른 문제점은 인터럽트를 끈다는 것 자체의 문제입니다. 인터럽트에는 중요한 것들이 많은데 이를 무시한다는 것 자체가 문제인 것이죠. 예를 들어 CPU가 디스크 읽기 요청을 완료한 사실을 인터럽트로 보냈는데 이를 무시하여 OS가 이를 요청한 프로세스를 영원히 대기 상태로  유지하는 문제가 발생할 수 있습니다.

 

마지막 문제점은 효율성입니다. 인터럽트를 활성화하고 비활성화하는 명령어는 많이 느리기 때문에 이를 lock을 사용할 때마다 사용하는 것은 비효율적입니다.

 

이렇게 많은 문제점이 존재하는데 이 방법이 많이 사용될까요? 이 방법은 신뢰성이 높은 작업, 즉 OS 자체 작업에서 lock, unlock을 사용할 때에나 사용할 수 있습니다.

A Failed Attempt: Just Using Loads/Stores

그럼 인터럽트를 제어하는 방법은 별로였으니 다른 방법을 알아보겠습니다. 이번에는 하드웨어의 지원을 받아 단일 flag 변수를 사용하여 간단하게 lock을 구현해보겠습니다. 물론 제목에서부터 failed attempt라고 적혀있긴 하지만 Lock을 구현하는데 필요한 몇 가지 아이디어를 볼 수 있기 때문에 한 번 살펴보도록 하겠습니다.

typedef struct __lock_t { int flag; } lock_t;

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

void lock(lock_t *mutex) {
    // mutex flag가 1인 경우엔 아무것도 안하고 무한루프만 돕니다.
    while(mutex->flag == 1)
    
    // while문을 벗어나면 mutex flag를 1로 수정하여 lock을 얻습니다.
    mutex->flag = 1;
}

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

위와 같이 flag를 하나 만들어서 Lock을 구현하는 방법입니다. Flag의 값이 0이면 아무도 lock을 가지고 있지 않은 것이고 1이라면 누군가 lock을 가진 상태라고 정의합니다. 처음 lock을 생성할 때는 flag를 0으로 설정하고 lock을 획득하고자 할 때는 flag의 값을 확인합니다. 이때 while문으로 무한 루프를 돌면서 flag가 0이 되기를 기다립니다. 그러다 0이 되면 flag를 1로 수정하면서 lock을 획득하고 작업을 수행합니다. 임계 영역에서의 작업을 마치면 unlock을 호출하여 flag를 0으로 만들어 주면 끝입니다.

 

이 방법에는 어떠한 문제점이 있을까요? 첫 번째 문제점은 어떤 스레드가 lock을 획득한 시점부터는 다른 스레드들은 모두 lock을 얻지 못하고 무한루프를 돌고 있습니다. 이를 spin wait이라고 하며 이는 성능적으로 좋지 않습니다. 두 번째 문제점은 정확성의 문제입니다. 이 문제는 아래 그림을 보며 이해해보겠습니다.

 

 

위와 같이 2개의 스레드가 lock을 얻으려고 합니다. Thread1이 lock을 얻으려고 하는 과정에서 flag가 0이라서 이제 flag를 1로 수정하려고 할 때 인터럽트가 발생하여 Thread 2로 context switch 됩니다. 이때 현재까지 진행한 곳을 기억하므로 Thread1은 다음에 수행될 때 flag를 1로 수정하는 작업부터 수행하게 됩니다. 그럼 이제 Thread 2가 수행되는데 여기서도 lock을 얻으려고 하고 flag를 봤더니 아직 0입니다. 그래서 lock을 획득합니다. 그런 뒤 다시 context switch가 되어 Thread1으로 돌아오면 Thread 1 역시 flag를 1로 수정하고 lock을 획득합니다. 어떤가요? lock을 획득한 스레드는 한 개뿐이어야 하는데 이미 위와 같은 상황에서는 2개의 스레드가 lock을 가지게 되었습니다. 이는 원자성이 보장되지 않아 발생하는 문제이며 그렇기 때문에 지금 flag가 1개인 방법은 좋지 못한 방법인 것이죠.

Building Working Spin Locks with Test-And-Set

지금까지 알아본 간단한 방법들이 좋지 않았기 때문에 사람들은 lock을 위한 새로운 방법을 만들기 위해 하드웨어 지원을 사용하게 됩니다. 가장 간단한 하드웨어 지원을 받는 방법은 test-and-set혹은 atomic exchange 명령어를 사용하는 방법입니다. Test-and-set 명령어를 간단하게 C언어 코드로 표현하면 아래와 같습니다.

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

위와 같은 동작으로 test-and-set 명령어가 동작합니다. Test-and-set 명령어가 하는 일은 이전에 ptr이 가리키던 값을 반환하고 현재 ptr은 새로운 값으로 설정합니다. 가장 중요한 것은 test-and-set 명령어는 하드웨어에서 원자적으로 동작하는 명령어라는 것이죠! 여기서 test-and-set이라고 하는 이유는 ptr값을 새로운 값으로 수정하면서 이전에 가리키던 값을 반환하여 lock을 얻기에 적합한 스레드인지를 확인할 수 있기 때문입니다. 이를 사용하면 spin-wait를 쉽게 구현할 수 있는데요, 아래 코드를 보겠습니다.

typedef struct __lock_t { int flag; } lock_t;

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

void lock(lock_t *lock) {
    // TestAndSet의 반환값이 1일 경우에만 while 탈출합니다.
    while(TestAndSet(&lock->flag, 1) == 1)
    
    // while문을 벗어나면 lock flag를 1로 수정하여 lock을 얻습니다.
    lock->flag = 1;
}

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

그럼 아까와 어떻게 다른지 확인해보겠습니다. 만약 어떤 스레드가 lock을 가지고 있을 때 (lock flag가 1) lock을 요청하면 어떻게 될까요? 우선 lock()이 호출되고 TestAndSet(flag, 1)도 호출됩니다. TestAndSet에서 현재 값을 새로운 값으로 수정하고 현재 값은 반환합니다. 즉 1을 반환하는 것이죠. 그러다 lock을 가지고 있던 스레드에 unlock을 호출하여 flag 가 0이 되면 0을 반환하고 flag를 1로 수정하며 lock을 획득하게 됩니다. 이러한 작업이 문제없이 동작하는 이유는 test-and-set이 원자적으로 동작하는 명령어이기 때문입니다. 따라서 test-and-set은 시작했다면 수정과 반환까지 아무 방해도 받지 않고 수행하는 것이죠. 이렇게 spin wait를 사용하는 lock을 spin lock이라고 합니다.

 

하지만 아직도 spin wait 상태는 남아있습니다. Spin wait 상태는 CPU를 사용하지 않는 상태가 아닌 사용 중인 상태이며 단일 프로세서에서 선점형 스케줄러가 없다면 혼자 계속 spin wait만 하며 다른 프로세스의 CPU 사용을 막을 수 있습니다. 따라서 스케줄링을 해줘서 독점을 하지 못하도록 해줘야 합니다.

Evaluating Spin Locks

그럼 이제 지금까지 알아본 spin lock을 한 번 평가해볼까요? 아까 lock을 평가할 땐 3가지 기준이 있다고 했습니다. 우선 첫 번째는 정확하냐는 것이었죠. 상호 배제를 잘 제공하는지에 대한 질문에 대해 spin lock은 잘 수행했었습니다.

 

두 번째는 fairness(공정성)였습니다. 스레드들이 lock을 획득하기에 공평한 상황인가에 대한 것인데, 사실 지금까지 공정성을 고려하진 않았기 때문에 아직 공정성은 만족하지 않습니다. 실제로 Spin lock은 공정성을 보장하지 않습니다.

 

마지막은 performance(성능)입니다. 계속 언급한 대로 Spin lock에 사용하는 spin wait 방법은 CPU를 계속 사용하며 대기를 하는 것이기 때문에 좋은 방법은 아닙니다. 특히나 하나의 CPU만 있는 상황에서는 오버헤드가 아주 클 수 있습니다. 하지만 여러 개의 CPU가 있는 상황에서는 잘 동작할 수도 있지만 spin lock이 성능적으로도 좋다고 할 수는 없습니다.

Compare-And-Swap

일부 시스템에서 제공하는 compare-and-swap 혹은 compare-and-exchange 명령어를 사용하는 방법도 있습니다. 간단하게 이 명령어가 하는 일을 C언어 코드로 나타내면 아래와 같습니다.

int CompareAndSwap(int *ptr, int expected, int new) {
    // 기존 값을 original에 저장합니다.
    int original = *ptr;
    // 만약 기존 값과 expected 값이 같다면 ptr의 값을 new로 수정합니다.
    if(original == expected)
        *ptr = new;
    // 기존 값을 반환합니다.
    return original;
}

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

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

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

이 방법 역시 spin wait를 사용하는 것을 볼 수 있습니다.

Load-Linked and Store-Conditional

일부 플랫폼에서는 Load-Linked and Store-Conditional 명령어를 사용하여 Lock을 구현하기도 합니다. 두 개의 명령어를 C언어로 나타내면 아래와 같습니다.

int LoadLinked(int *ptr) {
    return *ptr
}

int StoreConditional(int *ptr, int value) {
    if(이코드가 실행될 때까지 *ptr에 변화가 없다면) {
    // 그제서야 *ptr의 값 변경
        *ptr = value;
        return 1;
    } else {
        return 0;
    }
}

Load-Linked 명령어는 일반적인 load 명령어와 비슷하게 작동하고 메모리에서 값을 가져와서 레지스터에 배치하기만 합니다. 하나의 차이점은 저장 조건이 존재하며 여기서의 조건은 주소에 대한 값이 변경되지 않은 경우에만 값을 업데이트합니다. 이 두 개의 명령어를 활용해서 lock을 만들면 아래와 같습니다.

void lock(lock_t *lock) {
    while(1) {
        // flag 값이 1인지 확인합니다. 만약 아니라면 spin
        while (LoadLinked(&lock->flag) == 1)
            ;
        // flag 값이 0이므로 lock을 획득 가능하고
        // flag 값을 1로 다시 설정하는데 StoreConditional 명령어를 사용합니다.
        if (StoreConditional(&lock->flag, 1) == 1)
            return;
        }
    }
}

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

위의 코드에서 스레드는 lock을 얻기 위해 flag가 0으로 설정되기를 기다리며 계속 무한 루프를 돕니다. 그러다 flag가 0이 되면 lock을 얻고 flag를 1로 바꾸려고 하는데, 여기서 StoreConditional 명령어를 사용합니다. 이 명령어로 인해 여러 개의 스레드가 동시에 시도하더라도 하나의 스레드만 lock을 얻을 수 있도록 해줍니다. 그 이유는 만약 어떤 스레드가 먼저 값을 바꿔 lock을 획득했다면 다른 스레드는 저장 조건에 실패하여 lock을 획득하지 못하기 때문입니다.

Fetch-And-Add

마지막으로 살펴볼 하드웨어 기반 lock 방법은 fetch-and-add 명령어를 사용하는 방법입니다. 이 명령어를 C언어로 나타내면 아래와 같습니다.

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

이는 약간의 ticket lock 방법으로 먼저 이를 사용하는 lock, unlock 코드를 보도록 하겠습니다.

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);
    // lock의 turn과 자신의 티켓이 같을 때까지 spin
    while (lock->turn != myturn)
        ;
}

// unlock을 하게 되면 turn+1을 하여 특정 스레드에게 lock 획득 권한을 줍니다.
void unlock(lock_t *lock) {
    lock->turn = lock->turn + 1;
}

이 방법의 특징은 turn이라는 개념을 도입하여 모든 스레드가 언젠가는 lock을 얻을 수 있을 수 있습니다. lock을 호출하면 스레드에게는 자신의 ticket 넘버를 받게 됩니다. 번호표 느낌으로 이해하시면 되는데요, lock을 이미 가진 스레드가 unlock을 호출하면 turn 값이 1씩 증가하여 해당 turn 값을 가진 스레드가 lock을 얻게 됩니다.

Too Much Spinning: What Now?

지금까지 알아본 여러 가지 방법들은 하드웨어 기반 lock이었으며 간단하게 코드 몇 줄로 작동됐습니다. 하지만 이는 모두 spin wait를 사용하는 방법으로 lock을 획득하지 못한 스레드는 lock을 얻을 때까지 무한루프를 돌게되는 방법이었습니다. 하지만 이렇게 무한루프를 도는 것 자체가 cpu 낭비인데 굳이 spin lock을 사용해야할까요? 하드웨어의 지원만으로는 이를 해결할 수 없기에 이제는 OS의 지원도 받아 이 문제를 해결해보도록 하겠습니다.

A Simple Approach: Just Yield, Baby

하드웨어의 지원만 받던 spin lock은 잘 작동하지만 spin wait라는 스레드를 lock을 얻을 때 까지 실행해야 하는 문제가 있었습니다. 이는  계속되는 context switch, cpu의 낭비와 같은 문제로 인해 성능 저하를 발생했습니다. 이를 해결하기 위해서는 어떻게 해야 할까요?

 

우선 먼저 가장 익숙한 방식인 spin을 하는 동안에는 다른 스레드에게 cpu를 양보하는 것입니다. 즉 spin 중인 스레드가 CPU를 포기하고 다른 스레드가 실행할 수 있도록 OS에서 제공하는 yield() system call을 사용하면 됩니다. 스레드는 ready, running, blocked의 세 가지 상태가 존재하는데, yield는 running 상태의 스레드를 ready 상태로 변경하는 system call입니다.

 

void init() {
    flag = 0;
}

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

void unlock() {
    flag = 0;
}

위와 같이 yield를 사용하면 스레드가 lock을 획득하지 못했을 때 spin을 도는 게 아닌 다른 스레드에게 cpu를 양보하게 됩니다. 만약 하나의 cpu에 두 개의 스레드가 있다면 이 방법이 아주 잘 동작합니다. 그렇다면 lock을 획득하려는 스레드가 100개라면 어떻게 될까요? 100개의 스레드 중 1개만 lock을 얻을 수 있으므로 99개의 스레드는 기다려야 합니다. 나머지 99개의 스레드는 위의 코드대로라면 다른 스레드에게 cpu를 양보해야 하는 것이죠. 하지만 다른 99개의 스레드도 모두 lock을 기다리는 상태이므로 계속해서 다른 스레드에게 양보하게 되고 이렇게 양보하는 과정에서 context switch 비용이 계속해서 발생한다는 문제가 있습니다.

 

또한 이 방법은 starvation(기아) 문제도 해결하지 못했습니다. 어떤 스레드는 계속해서 양보만 해야하는 상황이 될지도 모르기 때문입니다. 따라서 다른 방법이 필요합니다.

Using Queues: Sleeping Instead Of Spinning

방금 알아본 방법은 spin은 돌지 않는 대신 계속 다른 스레드에 양보만 하게 되어 context switch 비용이 크게 발생할 수 있는 문제와 기아 문제를 해결하지 못한 문제가 존재했습니다.

 

따라서 현재 lock을 가진 스레드가 unlock 한 후에 lock을 얻을 스레드를 정해준다면 어떨까요? 이러한 방법을 위해서는 현재 lock을 얻고자 하는 스레드들을 추적하기 위한 queue와 OS 지원이 좀 더 필요합니다.

 

이를 위해 Solaris 시스템에서 제공하는 system call인 스레드를 절전 모드로 전환하는 park(), threadID로 특정 스레드를 깨우는 unpark()를 사용해보겠습니다. 이를 사용하여 어떤 스레드가 lock을 획득하지 못하면 절전 모드로 전환했다가 lock을 가진 스레드가 unlock을 호출하면 unpark()로 특정 스레드를 깨워주는 방법을 사용할 수 있습니다. 코드로 보면 아래와 같습니다.

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) {
    // guard가 0이 될 때까지 spin
    while(TestAndSet(&m->guard, 1) == 1)
        ;
    
    // guard가 0이고 flag가 0이면 lock을 얻어도 되는 시점
    if (m->flag == 0) {
        m->flag = 1;
        m->guard = 0;
    // guard는 0이지만 flag가 1이면 queue에 자신을 추가후 대기상태로
    } else {
        guard_add(m->q, gettid());
        m->guard = 0;
        park()
    }
}

void unlock(lock_t *m) {
    // guard가 0이 될 때까지 spin
    while(TestAndSet(&m->guard, 1) == 1)
        ;
    // 만약 queue가 비었다면 flag = 0
    if (queue_empty(m->q))
        m->flag = 0;
    // queue가 빈 것이 아니라면 queue에서 하나를 run상태로 수정
    else
        unpark(queue_remove(m->q));
    m->guard = 0;
}

우선 위의 코드에서는 아까 알아본 test-and-set 아이디어도 사용합니다. 그리고 queue를 사용하여 starvation(기아) 문제를 해결합니다. 또한 guard라는 변수가 lock_t 구조체에 추가된 것 을 볼 수 있는데요, guard가 사용되는 방식은 flag, queue에 대한 spin lock에서 알아볼 수 있습니다. 간단하게 말하면 flag와 queue는 모든 스레드가 사용하는 공유자원인데 이를 보호하기 위한 변수라고 할 수 있습니다. 이를 위해 test-and-set을 사용하며 spin wait도 발생합니다. 즉 이 방법은 spin wait을 완전히 해결한 것은 아니며 lock을 획득하거나 해제하는 동안 스레드가 중단되어 다른 스레드가 spin wait 하게 하는데, spin wait을 하는 시간이 제한되게 됩니다.

 

어떤 스레드가  lock을 획득하지 못하면 queue에 자신을 추가하고 guard를 0으로 수정 후 park()를 호출하여 cpu를 다른 스레드에게 양보합니다. 여기서 guard값을 수정하는 코드가 park() 이전이 아닌 이후에 한다면 어떤 문제가 발생할까요? 일단 이는 다른 스레드가 깨어날 때 flag를 1로 설정하려고 시도할 수 없게 되는 문제가 발생합니다. guard가 1이기 때문이죠. 따라서 lock을 획득하지 못한다고 여기고 다른 스레드에게 cpu를 양보합니다. lock을 얻을 수 있는 상태인데도 말이죠!

 

위의 코드에서 park()가 호출되기 전에 queue에 넣기 때문에 발생하는 문제가 있습니다. queue에 먼저 자신을 넣은 뒤에 park()를 호출하는데, 이때 queue에 넣자마자 다른 스레드에서 unpark()를 해버리면 어떻게 될까요? 그런 뒤 park()를 호출하여 대기상태로 들어가게 된다면 queue에는 자신이 없기 때문에 영원히 대기상태에 머무르는 문제가 발생합니다. 이를 wakeup/waiting race 문제라고 부릅니다. 이 문제를 해결하기 위해 Solaris는 setpark()라는 시스템 콜을 사용하여 문제를 해결합니다. setpark()를 호출하면 스레드가 곧 대기상태가 되는 것을 나타낼 수 있습니다. 그런 다음 대기 상태로 바뀌고 실제 park()가 호출되기 전에 다른 스레드가 unpark()를 호출하면 해당 스레드를 대기상태로 바꾸는 것이 아닌 바로 lock을 획득하게 만드는 것입니다. setpark()는 아래와 같이 사용할 수 있습니다.

guard_add(m->q, gettid());
setpark(); // 아까 park()의 문제점을 해결한 것
m->guard = 0;

Summary

이번 글에서는 상호 배제를 위한 lock을 구현하는 방법, lock을 구현할 때 고려해야 할 점들에 대해 알아봤습니다. Lock은 하드웨어와 OS의 지원을 모두 받아 구현 가능했으며 다양한 시스템마다 각자의 lock도 존재한다는 것을 알 수 있었습니다. 다음 글에서는 lock을 일반적인 자료구조에서 사용하는 방법을 알아보겠습니다. 

 

감사합니다.