[운영체제] Locks

전윤혁·2024년 12월 18일
OSconcurrency
0

OS

목록 보기
14/18

이번 글에서는, 이전 글에 이어 Lock에 대해 더 자세히 알아보도록 하겠다.

1. Locks: The Basic Idea

직전 글에서 살펴봤지만, 간단하게 Lock의 기본적인 아이디어를 점검해보자.

balance = balance + 1;

위와 같이 balance라는 공유 자원이 있다고 했을 때, 아래의 추상화된 코드를 살펴보자.

lock_t mutex; // some globally-allocated lock ‘mutex’
…
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

전역적으로 작동하는 mutex라는 Lock을 통해, 해당 공유 자원에 대한 Mutual Exclusion을 보장할 수 있다. 이때, 공유 자원 접근하거나 수정하는 코드 영역을 Critical Section이라고 한다고 했다.

Lock 변수는 Lock의 상태를 보유한다. 사용 가능(available) 또는 잠금 해제(unlocked, free) 상태인 경우 Lock을 어떤 스레드도 가지고 있지 않음을 의미한다. 획득됨(acquired) 또는 잠금됨(locked, held) 상태인 경우 정확히 하나의 스레드가 Lock을 가지고 있으며, 대부분의 경우 해당 스레드는 Critical Section에 있다고 볼 수 있다.

아래는 POSIX 라이브러리를 활용한 Lock의 실제 예시이다.

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

여러 변수나 자원을 보호하려면 여러 개의 Lock을 사용할 수 있다. 각 자원마다 Lock을 따로 사용하면, 서로 다른 스레드가 다른 자원에 접근할 수 있어, 더 많은 스레드가 동시에 실행될 수 있다.

2. Building A Lock

효율적인 Lock은 Mutual Exclusion 제공하면서도 낮은 비용으로 동작해야 한다. 즉, Lock을 얻는 데 드는 시간이 최소화되어야 하며, 이를 통해 여러 스레드가 동시에 동작할 수 있도록 보장해야 한다.

효율적인 Lock을 평가하는 중요한 기준은 아래의 3가지가 있다.

  • Mutual Exclusion (상호 배제)
    락이 제대로 동작하는지, 즉 여러 스레드가 동시에 critical section에 들어가는 것을 실제로 방지하는지 평가한다.

  • Fairness (공정성)
    정의: 락을 기다리고 있는 스레드들이 공평하게 락을 얻을 기회를 가지는지, 즉 Starvation 문제가 발생하지 않는지 평가한다.

  • Performance (성능)
    락을 사용하는 데 따른 시간적 오버헤드를 평가한다. 이 때 오버헤드에는 락을 걸고 푸는 비용, Race Condition을 처리하는 비용이 포함된다.

위의 3가지 기준을 토대로, Lock을 구현하는 다양한 방법들을 하나씩 평가해보자.

✅ Controlling Interrupts

Critical Section에서 인터럽트 자체를 막아버리는 방식으로, 가장 무식하지만 확실한 방법이다! 먼 옛날 단일 프로세스 시스템에서는 실제로 해당 방법으로 Lock이 구현되었다고 한다.

void lock() {
    DisableInterrupts();
}

void unlock() {
    EnableInterrupts();
}

문제는 무엇일까?

  • 애플리케이션에 대한 과도한 신뢰가 요구된다. 욕심이 많은 프로그램이 시스템을 독점해버린다면?

  • 다중 프로세서 시스템에서 작동하지 않는다. 한 CPU에서 인터럽트를 비활성화한다고 해서 다른 CPU에서 동일한 락을 사용하는 스레드를 제어할 수 없다.

  • 성능상 좋지 않다. 인터럽트를 활성화/비활성화하는 작업은 현대 CPU에서 굉장히 느린 작업이 될 수 있다.

📌 Hardware 지원이 필요한 이유?

여기서 잠깐! Lock을 구현하기 위해 하드웨어의 지원이 필요한 이유를 짚고 넘어가보자.

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;
}

위 코드는 단순히 0, 1로 식별되는 flag 값을 기준으로 Lock을 구현하려고 한 시도이다. 결과를 살펴보자.

  • 초기 flag의 값은 0이다. (Idle한 상태)
  • Thread1에서 flag의 값이 0인 것을 확인하고, while 루프에 빠지지 않는 것이 확정되었다.
  • 이 때, Thread2로 컨텍스트 스위칭이 발생했고, Thread2 또한 flag 값이 0인 것을 확인한 후, while 문에 빠지지 않고 flag 값을 1로 변경하였다.
  • 다시 Thread1로 컨텍스트 스위칭이 발생하여, Thread1 또한 flag 값을 1로 변경하였다.

왜 위와 같은 문제가 발생했을까? 맞다! 애초에 Lock을 검증하는 flag 값의 접근 자체가 Atomic하게 이루어지지 않았기 때문이다.

또다른 문제도 있다. 위와 같이 코드를 구현할 경우 Lock을 얻지 못한 스레드는 while문에서 공회전을 하며 CPU 자원을 낭비할 것이다!

해당 예시를 통해, Lock을 검증하는 작업 또한 Atomic하게 동작하도록 보장해줘야 한다는 점을 알 수 있는데, 실제로 명령어를 Atomic하게 실행하는 것은 하드웨어의 영역이다. 따라서, Lock을 구현하기 위해서는 하드웨어로부터 Atomic Instruction을 지원받아야 하는 것이다!

✅ Test And Set (Atomic Exchange)

Lock의 구현에 하드웨어의 지원이 필요하다는 점을 상기하며, Test And Set 방식을 알아보자.

int TestAndSet(int *ptr, int new) {
    int old = *ptr; // fetch old value at ptr
    *ptr = new; // store ‘new’ into ptr
    return old; // return the old value
}

우선 혼동하지 말자! 위의 코드는 명령어의 동작을 설명하기 위한 수도 코드일 뿐, 실제로는 해당 작업을 Atomic하게 수행하는 TestAndSet 명령어이다.

TestAndSet 명령어의 동작은 단순히 아래와 같다.

  • old_ptr가 가리키는 주소에서 값을 읽어 old에 저장한다.
  • old_ptr가 가리키는 위치에 새로운 값(new)을 저장한다.
  • 이전에 읽은 값(old)을 반환한다.

이를 통해 어떻게 Lock을 구현할까?

typedef struct __lock_t {
    int flag;
} lock_t;

void init(lock_t *lock) {
    // 0 indicates that lock is available,
    // 1 that it is held
    lock->flag = 0;
}

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ; // spin-wait
}

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

Atomic하게 수행되는 TestAndSet 명령어가 추가된 것 외에는 기존 flag 방식과 차이가 없다.

TestAndSet(&lock->flag, 1) == 1를 풀어서 이해해보면, flag 값을 확인하여 0인 경우, flag 값을 1로 설정한 후, 0을 리턴하여 while문에서 빠져나온다. 반대로, flag 값이 1인 경우, flag 값을 (무의미하게) 1로 설정한 후, 1을 리턴하여 while문을 돌게 된다.

✅ Compare-And-Swap

또다른 Atomic Instruction인 Compare-And-Swap을 사용한 예시이다.

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}
  • ptr 주소의 값을 읽어 actual에 저장한다.
  • actual과 expected의 값이 일치하면, ptr에 new 값을 저장한다.
  • actual을 리턴한다.

이를 통해 Lock을 구현해보자.

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

flag 값을 확인하여 0과 비교한다. 일치할 경우, flag의 주소에 1을 저장하고, 0을 리턴한다. 반대로, 일치하지 않을 경우, 1을 리턴하여 while문을 돌게 된다.

✅ Load-Linked and Store-Conditional

이번에는 Load-Linked, Store-Conditional 두 개의 명령어을 통해 Lock을 구현하는 예시이다.

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

int StoreConditional(int *ptr, int value) {
    if (no one has updated *ptr since the LoadLinked to this address) {
        *ptr = value;
        return 1; // success!
    } else {
        return 0; // failed to update
    }
}
  • LoadLinked는 단순히 ptr 주소의 값을 레지스터로 읽는 용도이다.
  • StoreConditional은 LoadLinked 레지스터로 값을 읽은 후, 해당 주소에 아무도 값을 갱신하지 않았을 경우에만 ptr 위치에 value를 저장하고 1을 리턴한다.
  • 그렇지 않을 경우 0을 리턴한다.

아래는 실제 Lock을 구현하는 코드이다.

void lock(lock_t *lock) {
    while (1) {
        while (LoadLinked(&lock->flag) == 1)
            ; // spin until it’s zero
        if (StoreConditional(&lock->flag, 1) == 1)
            return; // if set-it-to-1 was a success: all done
        // otherwise: try it all over again
    }
}

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

LoadLinked를 통해 flag 값을 확인했을 때 1이면 공회전을 반복한다. flag 값이 0으로 바뀌어 while문을 탈출하면 StoreConditional을 통해 flag에 접근하는데, 그 잠깐 사이에 flag 값이 다른 스레드로 인해 1로 바뀌어버린 경우! LoadLinked 단계부터 다시 수행된다.

✅ Fetch-And-Add

마지막으로, Fetch-And-Add 명령어를 살펴보자.

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

단순히 주소의 값을 old로 읽은 후, 1을 더한 값을 해당 주소에 저장하고, old 값을 리턴하는 명령어이다.

이를 통해 어떻게 Lock을 구현하는지는 아래의 Ticket Lock을 통해 알아보자!

✅ Ticket Lock

Fetch-And-Add 명령어를 통해 구현한 Ticket Lock이다.

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

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

해당 방식은 번호표를 뽑는 방식과 유사하고, 그렇기에 이름도 Ticket Lock이다.

  • lock->ticket = 0;, lock->turn = 0; 부분에서 티켓과 순서를 각각 0으로 초기화해준다.

  • Lock을 얻으려고 할 경우, int myturn = FetchAndAdd(&lock->ticket);을 통해 티켓을 뽑음과 동시에 티켓의 숫자를 1 올려준다.

  • 현재 순서(lock->turn)가 본인 순서(myturn)가 될 때까지, 공회전을 반복한다.

  • Lock을 해제할 경우, FetchAndAdd(&lock->turn); 부분을 통해 순서의 값을 1 올려 뒷 순번인 스레드가 Lock을 얻을 수 있도록 한다.

지금까지 소개된 Atomic Instruction을 바탕으로 구현된 Lock을 Correctness, Fairness, Performance 관점에서 평가해보자.

우선 모든 방법은 Correctness 관점에서는 옳게 동작한다. 하지만 Ticket Lock을 제외한 다른 방법들은 Fairness를 따로 보장해주지는 않는다. 마지막으로, 모든 방법은 공회전을 한다는 점에서 Performance 관점에서 좋지 않다.

3. So Much Spinning

위에서 소개된 하드웨어 기반 Spin Lock은 구현이 간단하고, 올바르게 동작한다. 하지만 모든 방식이 공회전을 하며 CPU 자원을 낭비한다는 문제점이 있다.

이를 해결하기 위해, 우리는 하드웨어 외에 OS의 지원 또한 필요하다!

1) A Simple Approach: Just Yield

이번에도 가장 단순한 방법부터 살펴보자. 공회전을 할 바에는, 단순히 다른 스레드에게 CPU 사용을 양보하는 방법이다.

즉, OS의 시스템 콜을 통해 현재 실행 중인 스레드를 Running 상태에서 Ready 상태로 바꾸는 것이다.

void init() {
    flag = 0;
}

void lock() {
    while (TestAndSet(&flag, 1) == 1)
        yield(); // give up the CPU
}

void unlock() {
    flag = 0;
}

문제점은 무엇일까?

  • yield는 즉시 컨텍스트 스위칭을 진행하기 때문에, 그로 인한 비용이 낭비될 수 있다. (Lock이 금방 풀리는 상황이었다면?)

  • 공정성을 보장하지 않는 스케줄링 방식일 경우, Lock을 얻지 못한 스레드가 계속 Ready 상태로 머무는 Starvation 문제가 발생할 수 있다.

2) Using Queues: Sleeping Instead of Spinning

다음 방법은, 공회전 대신 해당 스레드를 재우는 것이다.

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) {
  while (TestAndSet(&m->guard, 1) == 1)
  	; //acquire guard lock by spinning
    
  if (m->flag == 0) {
    m->flag = 1; // lock is acquired
    m->guard = 0;
  } else {
    queue_add(m->q, gettid());
    m->guard = 0;
    park();
  }
}

void unlock(lock_t *m) {
  while (TestAndSet(&m->guard, 1) == 1)
  	; //acquire guard lock by spinning
    
  if (queue_empty(m->q))
  	m->flag = 0; // let go of lock; no one wants it
  else
  	unpark(queue_remove(m->q)); // hold lock
    
  // (for next thread!)
  m->guard = 0;
}

  • park()
    해당 System Call을 호출한 스레드를 재우는 함수이다.

  • unpark(threadID)
    threadID로 지정된 스레드를 깨우는 함수이다.

  • guard
    Lock과 Unlock 과정의 원자성을 보장해주는 flag이다.

위와 같은 방법이 어떻게 spinning 방식과 yield 방식의 문제점을 해결하는 것인지 코드를 봤을 때는 감이 잘 오지 않는다. 하나씩 이해해보자!

  • 우선 guard와 flag의 용도를 명확히 이해해야 한다. 먼저,flag는 lock의 상태를 표현한다. flag == 0는 Lock이 열려있는 상태를 의미하고, flag == 1은 Lock이 현재 누군가에 의해 점유되었다는 것을 의미한다.

  • guard는 Lock의 상태를 변경하는 코드의 원자성을 보장하기 위해 사용된다. 즉, guard를 확보한 스레드만 Lock의 상태(flag)를 변경할 수 있다.

  • 이제 Lock을 거는 과정을 살펴보자. 왜 while (TestAndSet(&m->guard, 1) == 1) 부분에서 guard를 얻기 위해 공회전을 하는 것일까? (우리는 현재 공회전을 없애기 위한 방법을 찾고 있는데!)

  • 여기서 guard를 얻기 위한 공회전은 위에서 살펴본 하드웨어 레벨의 공회전과 달리, OS 레벨의 공회전이다! 따라서 해당 Critical Section을 짧게 보장하도록 커널 레벨에서 구현하는 것이 가능하기 때문에, 해당 공회전은 비용이 크지 않다고 보는 것이다.

위의 설명을 조금 더 쉽게 표현하면, while (TestAndSet(&m->guard, 1) == 1)의 공회전 시간이 길지 않도록 보장된다는 것이다. 왜? guard는 단순히 flag의 상태를 확인하는 작업이기 때문이다. 특정 프로세스가 작업을 끝내고 Lock을 반환할 때까지 기다리는 공회전이 아니라, 단순히 flag의 값을 확인하는 대기열이라는 점이라는 것을 명심해야 한다!

  • 짧은 공회전을 통해 guard를 획득하면, flag의 값을 확인할 수 있다. 만약 flag 확인 결과 현재 Lock이 열려있는 상태라면, m->flag = 1;를 통해 Lock을 잠그고, m->guard = 0;를 통해 guard를 반환한 후(다른 스레드도 flag의 값을 확인할 수 있도록) 실행될 것이다.

  • 만약 flag 확인 결과 현재 Lock이 잠긴 상태라면, queue_add(m->q, gettid());를 통해 큐에 현재 스레드를 추가한 후 m->guard = 0;를 통해 guard를 반환한 후, park();를 통해 잠든다.

  • 마지막으로 Unlock 과정을 살펴보자. 실행된 스레드가 작업을 마치고 Lock을 해제할 때 역시 먼저 guard를 획득해야 한다. guard를 획득한 이후, 만약 큐가 비어 있다면 현재 Lock을 얻기 위해 큐에 잠들어 있는 스레드가 한 개도 없다는 뜻이므로 단순히 m->flag = 0;를 통해 Lock을 반환한다.

  • 만약 큐에 현재 대기하고 있는 스레드가 있다면? unpark(queue_remove(m->q));을 통해, 가장 먼저부터 대기하고 있던 스레드를 깨워준다.

  • 위의 전부 작업을 마치면, 역시 guard를 반환해줘야 한다.

📌 Using Queues 방식은 어떻게 문제를 해결하는가?

위의 방식이 어떻게 동작하는지는 알겠는데, 그래서 뭐가 좋은건지 와닿지 않을 수 있다. 큐와 Sleep 방식이 기존 문제를 어떻게 해결하는지 정리해보자.

  • Busy Waiting 문제
    설명했듯이, guard를 얻기 위한 OS 레벨의 공회전은 비용이 크지 않기 때문에, 하드웨어 레벨의 Spinning 방식보다 성능 문제가 확실히 나아졌다는 점을 알 수 있다.
  • 컨텍스트 스위칭 & 공정성 문제
    yield 방식의 두 가지 문제는 어떻게 해결한 것일까? 기존 yield 방식에서는 Lock을 획득하지 못할 때마다 yield()를 통해 즉시 컨텍스트 스위칭이 발생하고, 해당 스레드는 Ready 상태로 전환되는데, 해당 스레드가 다시 스케줄링되어 또다시 Lock을 획득하지 못할 경우, 다시 yield()를 통해 컨텍스트 스위칭이 발생하는 과정이 반복된다. 하지만 큐 방식의 경우, Lock을 획득하지 못한 스레드를 재운 후, Lock이 풀렸을 시점에만 unpark()를 통해 해당 스레드를 깨우므로, 불필요한 컨텍스트 스위칭이 발생하지 않는다. 공정성 차원에서 또한 큐를 사용한다는 점에서 순서를 보장한다는 것을 쉽게 이해할 수 있다.

3) Wakeup/Waiting Race

괜찮은 방법이다! 하지만 큐 방식은 Wakeup/Waiting Race 문제를 동반한다. 아래의 상황을 가정해볼까?

  1. Thread A가 Lock을 쥐고 있는 상황에서, Thread B는 Lock을 얻기 위한 큐에 자신을 등록하는 과정까지만 수행했다.

  2. 이 때! 컨텍스트 스위칭이 발생하여 Thread A가 Unlock을 수행해버리면? 현재 큐에는 Thread B가 등록되어 있기 때문에 unpark()로 Thread B를 깨우는 (무의미한) 동작을 수행한다. (아직 Thread B는 잠들지 않았는데도!)

  3. 다시 Thread B로 컨텍스트 스위칭되어, Thread B는 park()로 잠들게 된다. 문제는, 2번 과정을 통해 Thread B는 대기열에서 사라진 상태라는 것! 누구도 Thread B를 깨울 수 없기에 영원히 잠들어버린다.

Solaris에서는 setpark()라는 시스템 콜을 추가하여 이 문제를 해결하였다.

queue_add(m->q, gettid());
setpark();
m->guard = 0;
park();

setpark()는, 현재 스레드가 운영체제에게 park 상태에 진입하기 직전임을 알리는 시스템 콜이다. 이를 통해, "unpark가 park보다 먼저 호출되면 sleep하지 않는다." 라는 작업을 수행할 수 있다.

이전 상황처럼, Thread B에서 queue_add가 수행된 후, Thread A에서 unpark()이 수행되었다고 해보자. 그러면 Thread B의 setpark()를 통해, 해당 스레드는 잠들지 않게 된다.

4) Futex (Linux)

Solaris의 park()와 unpark와 유사하게, 리눅스에서는 Lock이 futex(fast user-space mutex)라는 매커니즘으로 구현되어 있다. 즉, OS에 따라 다른 방식으로 Lock이 구현되어 있다.

아래의 코드를 통해 futex의 동작을 간단하게 알아보자.

void mutex_lock (int *mutex) {
  int v;
  
  /* Bit 31 was clear, we got the mutex (the fastpath) */
  if (atomic_bit_test_set (mutex, 31) == 0)
  	return;
    
  atomic_increment (mutex);
  while (1) {
    if (atomic_bit_test_set (mutex, 31) == 0) {
      atomic_decrement (mutex);
      return;
    }
    
    /* We have to waitFirst make sure the futex value
    we are monitoring is truly negative (locked). */
    v = *mutex;
    if (v >= 0)
    	continue;
    futex_wait (mutex, v);
  }
}

void mutex_unlock (int *mutex) {
  /* Adding 0x80000000 to counter results in 0 if and
  only if there are not other interested threads */
  if (atomic_add_zero (mutex, 0x80000000))
  	return;

  /* There are other threads waiting for this mutex,
  wake one of them up. */
  futex_wake (mutex);
}

  • futex_wait(address, expected)
    futex의 주소(address)가 expected 값과 동일한지 확인한 후, 동일하다면 해당 스레드를 재우고, 동일하지 않으면 즉시 반환한다.

  • futex_awake(address)
    주어진 address에 대해 대기 중인 스레드들을 확인하고, 대기 큐에서 한 스레드를 깨운다.

위의 두 가지가 futex 구현의 핵심이 되는 함수들이다. 이제 코드의 각 부분을 이해해보자.

if (atomic_bit_test_set (mutex, 31) == 0)
  	return;

atomic_bit_test_set는 앞서 살펴본 TestAndSet과 유사한데, mutex의 최상위 비트(31번째 비트)를 기준으로 Lock 여부를 판단한다. (여기서 mutex는 단순히 정수 포인터로 구현되어 있다.) 최상위 비트가 0이면(idle) 1로 변경 후 즉시 리턴하는데, 이 때 리턴은 Critical Section으로 진입하는 것을 의미한다.

현재 최상위 비트가 1이라서 Lock을 획득하지 못했다면? 현재 스레드를 대기열에 추가해야 하므로, 먼저 아래와 같이 원자적으로 mutex의 값에 1을 더한다. 현재 Lock을 기다리고 있는 스레드가 하나 더 추가되었다는 것을 mutex에 반영하는 것이다.

atomic_increment (mutex);

이후, 아래의 과정을 통해 현재 스레드를 재울지 말지 판단하게 된다.

while (1) {
    if (atomic_bit_test_set (mutex, 31) == 0) {
      atomic_decrement (mutex);
      return;
    }
    
    /* We have to waitFirst make sure the futex value
    we are monitoring is truly negative (locked). */
    v = *mutex;
    if (v >= 0)
    	continue;
    futex_wait (mutex, v);
  }

구현이 오묘하니 하나씩 자세히 살펴보자!

if (atomic_bit_test_set (mutex, 31) == 0) {
      atomic_decrement (mutex);
      return;
    }

while문 내부로 들어가자마자 해당 부분에서 Lock 여부를 다시 한번 확인해주는데, while문에 진입하자마자 Lock이 풀린 상황이라면 (찰나의 순간에) 즉시 Lock을 획득할 수 있게 된다. 성공한다면, 직전에 atomic_increment을 통해 대기 중인 스레드의 숫자를 하나 늘렸으므로, atomic_decrement을 통해 다시 하나 내려줘야겠지?

 v = *mutex;
    if (v >= 0)
    	continue;
    futex_wait (mutex, v);

만약 그러한 상황이 아니라면, v = *mutex;를 통해 현재 mutex의 값을 읽는다. 만약 현재 mutex의 값 v가 0보다 크거나 같다면? 최상위 비트가 0인 상태라는 뜻이므로(Lock이 idle한 상태), continue를 통해 while 문의 처음으로 되돌아가, 다시 Lock을 얻기 위해 시도한다.

v가 0보다 작다면, 최상위 비트가 1인 상태이므로(Lock이 점유 중인 상태), 드디어 얄짤 없이 futex_wait을 통해 현재 스레드를 재우게 된다.

while문 내부에서, 스레드를 재우기 전 지속적으로 Lock을 얻을 기회를 주는 것에 주목하여 이해해보면 좋을 것 같다!

이번에는 Unlock을 하는 과정을 살펴보자.

void mutex_unlock (int *mutex) {
  /* Adding 0x80000000 to counter results in 0 if and
  only if there are not other interested threads */
  if (atomic_add_zero (mutex, 0x80000000))
  	return;

  /* There are other threads waiting for this mutex,
  wake one of them up. */
  futex_wake (mutex);
}

Unlock을 하는 경우, 먼저 (atomic_add_zero (mutex, 0x80000000))를 통해 현재 대기하는 스레드가 있는지 없는지 확인한다. 어떻게?

0x80000000는 이진수로 1000 0000 ... 0000(32bit) 이므로, 현재 mutex의 값에 0x80000000를 더할 경우, mutex의 비트에 한 칸씩 자리 올림이 발생하여 최상위 비트가 0이 된다. 이 때, 대기중인 스레드가 없다면 하위 31비트가 전부 0일 것이고, 대기 중인 스레드가 존재하면 0이 아닐 것이다.

연산 결과가 0일 경우 atomic_add_zero가 참이 되고, 0이 아닌 경우 거짓이 된다. 따라서 대기 중인 스레드가 없을 경우 즉시 리턴(별도 작업 없이 Unlock 종료)하고, 만약 대기 중인 스레드가 있을 경우에는 futex_wake (mutex); 부분으로 이동하여 큐에서 잠들어있는 스레드를 하나 깨우게 되는 것이다!

4. Two-Phase Locks

마지막으로 Two-Phase Locks에 대해 간단하게 살펴보고 마무리하자.

Two-Phase Lock은 스레드가 바로 대기 상태로 들어가지 않고, 상황에 따라 공회전(Spin)과 대기(Sleep)를 조합하여 락 획득을 시도하는 방법이다. 왜? 락이 곧 해제될 가능성이 높을 때는 대기 상태로 진입하는 것보다 잠깐 공회전을 하는 것이 이득일 수 있기 때문! (컨텍스트 스위칭 비용을 생각하자.)

Two-Phase Lock의 동작 과정은 아래와 같다.

  • First phase (Spin)
    락이 곧 해제될 가능성이 높을 것이라고 기대하며, 일정 시간동안 공회전을 하며 기다린다. First phase 동안 Lock을 획득하지 못하면, Second Phase로 넘어간다.

  • Second phase (Sleep)
    First phase에서 Lock을 획득하지 못했기 때문에, Second phase에서는 해당 스레드를 재운다.

단순히 공회전을 잠깐 하며 Lock을 얻을 기회를 주는 정도의 차이로 이해하면 될 것 같다!

마치며

Lock에 대한 개념을 이해하는 것은 어렵지 않지만, 세부 구현으로 들어갈수록 점점 헷갈리는 것 같다. 그래도 이번 글에서 Lock에 대한 꽤 많은 내용을 다룰 수 있었다!

다음 글에서는 Lock 기반의 Concurrent Data Structures에 대해 알아보도록 하겠다.

profile
전윤혁
전공/개발 지식 정리
이전 포스트

[운영체제] Concurrency & Thread API

다음 포스트

[운영체제] Lock-based Concurrent Data Structures

0개의 댓글