출처 : http://pages.cs.wisc.edu/~remzi/OSTEP/

Concurrency

왜 락(lock)이 필요할까요?

먼저 들어가기에 앞서서 공유 자원이란 무엇인지 알아보도록 하겠습니다.

• 지역 변수는 공유 자원일 수 없습니다. 쓰레드 사이에서 공유될 수 없기 때문입니다.
• 전역 변수는 쓰레드 사이 공유되므로 공유 자원입니다.
• 동적인 객체는 쓰레드 사이 공유되므로 공유 자원입니다.
• 프로세스들도 메모리를 공유할 수 있습니다.

공유 자원의 여러 쓰레드가 사용 하게되면 동기화 문제가 발생하게 됩니다. 왜냐하면 동시성은 비결정적인 결과(non-deterministic)를 이끌어 내기 때문입니다. 이는 앞에서 이야기 하였듯이 2개 도는 그 이상의 동시에 동작하는 쓰레드들이 공유 자원에 접근을 하면 경쟁 상태(race condition)에 도달하기 때문입니다.

따라서 우리는 동기화(synchronization)를 하여 공유 자원에 대해서 관리를 할 필요가 있습니다.

우리는 일전에 저런 공유 자원에 접근하는 구간을 보고 임계 구역(Critical Section)이라고 명명한 바가 있습니다. 이런 임계 구역은 상호 배제(mutual exclusion)해야 한다는 것을 우리는 익히 압니다. 이런 상호배제를 구현하기 위해서는 아래를 만족을 해야합니다.

• 임계 구역에서의 실행은 원자적(Atomic)이여야 합니다. (전체 거나 아무것도 없거나)
• 오직 하나의 쓰레드를 임계 구역에서는 하나만 실행할 수 있습니다.
• 모든 다른 쓰레드는 기다리는 상태에 들어가게 됩니다.
• 쓰레드가 임계 구역을 빠져나오면 다른 것이 들어가게 됩니다.

락의 제작

이전의 내용을 바탕으로 임계 구역을 balance = balance + 1이라고 가정한 후 구현을 하면 아래와 같이 만들 수 있습니다.

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

여기서 lock_t mutex는 현재 락 상태를 보관하는 변수로 두 가지의 상태가 있을 수 있습니다.

• available(또는 unlocked, free) : 어떠한 쓰레드도 락을 가지고 있는 상태를 의미합니다.
• acquired(또는 locked, held) : 유일한 쓰레드 하나가 임계 구역으로 추정되는 공간에서 락을 가지고 있는 상태입니다.

다음으로 lock(&mutex) ... unlock(&mutex)는 무엇인지 각각을 알아보면 아래와 같습니다.

• lock()
  • 락을 acquired를 시도해봅니다.
  • 만약 락을 어떠한 쓰레드도 가지고 있지 않는다면, 쓰레드는 락을 acquired할 수 있습니다.
  • 이 acquired가 수행된 이후에 임계 구역에 들어가게 되고 이 쓰레드가 락의 소유자(owner)가 됩니다.
  • 이와 다르게, 이미 락이 다른 쓰레드로 acquired가 된 상태라면 임계 구역에 들어가는 것을 막습니다.
• unlock()
  • 락의 소유자가 unlock()을 부르는 경우, 락은 다시 availabe(free)상태가 됩니다.
  • lock()을 기다리는 다른 쓰레드를 깨우도록 합니다.

이러한 락은 아래의 방법을 통해서 사용할 수 있습니다.

• 락을 처음 생성 시에는 free상태로 만들어 주도록 합니다.
• lock()을 임계 구역에 들어가기 전에 불러주고, unlock()을 임계 구역을 빠져나가면 불러주도록 합니다.
• lock()은 호출자(caller)가 락을 가지고 있는 동안은 반환이 이루어지지 않습니다.
• unlock() 상태에 도달하기 전까지, 쓰레드는 스핀(spinlock) 또는 블락(mutex) 상태입니다.
• 최대 하나의 쓰레드가 어느 일정 시간에 락을 가질 수 있습니다.

예제 코드로 구현을 하면 아래와 같이 됩니다.

int withdraw(account, ammount){
	lock(lock);
	// ----- CRITICAL SECTION ----- //
	balance = get_balance(account);
	balance = balance - amount;
	put_balance(account, balance);
	// ----- CRITICAL SECTION ----- //
	unlock(lock);
	return balance;
}

그리고 락은 필히 아래와 같은 요구 사항을 충족할 수 있을 때 좋은 락이라고 할 수 있습니다.

• Correctness
  • Mutual Exclusion : 어느 일정 시간에는 오직 하나의 쓰레드만이 임계 구역에 있을 수 있습니다.
  • Progress(deadlock-free) : 만약 여러 개의 쓰레드가 임계 구역을 들어가고자 하는 경우, 반드시 하나는 들어갈 수 있어야 합니다.
  • Bound Waiting(starvation-free) : 대기 중인 쓰레드가 반드시 임계 구역에 들어갈 수 있어야만 합니다.
• Fairness
  • 각각의 쓰레드는 락을 획득을 하는 데 있어서 공정해야 합니다.
• Performance
  • lock과 unlock을 하는 데 드는 데 시간 비용(time iverhead)는 어느 정도인가?
  • 다중 CPU를 지원을 하는가?

그렇다면 이러한 락이 어떻게 만들어지는 지 이번에는 확인해보도록 하겠습니다. 이러한 락은 크게 인터럽트 제어 방법(controlling interrupts)과 소프트웨어적 방법론으로만 제작하는 방법(software-only algorithm)과 하드웨어를 활용하여 제작하는 방법(Hardware atomic Instructions) 세 가지가 있습니다. 이를 정리하면 아래와 같은 표가 나타남을 알 수 있습니다.

다음으로 각각을 구현하는 방법에 관해서 알아보도록 하겠습니다.

Controlling Interrupts

이 방법은 임계 구역에서 인터럽트를 불능 사태로 만들어 제어하는 방법입니다. 상호 배제라는 개념이 등장할 때쯔음에 나온 오래된 개념입니다. 그래서 고려되는 프로세서도 단일 프로세서(single-processor)를 기준으로 합니다. 이는 일정 블럭(blocks)에 대해 문맥 교환(context switch)을 하는 외부 이벤트의 인터럽트를 불가능하게 만들어버립니다. 이를 통해 코드의 임계 구역에서는 인터럽트가 일어나지 않게 되면서 락을 구현할 수 있습니다. 그리고 이 방법은 락과 관련된 상태 저장과 관련된 것이 없습니다. 이런 방식은 아래와 같은 방법으로 구현이 가능합니다.

void lock(){
	DisableInterrupts();
}

void unlock(){
	EnableInterrupts();
}

이것의 장단점은 아래와 같이 정리 가능합니다.

그래서 이런 문제를 풀기 위해 플래그(flag)를 통해 락을 거는 방법을 생각을 해내었습니다.

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex){
	// 0 : 락을 사용 가능, 1 : 락을 사용 불가능
	mutex->flag = 0;
}

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

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

하지만 이 방법은 2가지 문제가 발생할 수 있습니다. 먼저 아래와 같은 경우를 생각해보도록 하겠습니다.

우리가 예상하던 결과는 쓰레드 1이 1 → 2 → 6의 작업이 발생한 후에 쓰레드 2가 4번 작업에서 대기 상태(spin-wait)에 들어가는 것이 목적이었습니다. 하지만 의도치 않은 곳에서 문맥 교환이 발생을 하게 되었고, 결과 쓰레드 2가 정상적으로 동작을 하는 문제가 발생하게 됩니다. 따라서 이런 기존의 방법은 상호 배재를 보장하지 못합니다.

그리고 다음으로 저기서 while구문이 있습니다. 즉, 이러한 방식은 CPU에 큰 부담이 됩니다. 따라서 이를 해결하기 위해서는 결과적으로 하드웨어에 의해 지원되는 명령어가 필요함을 알 수 있습니다.

Software-only Algorithm

하드웨어적인 구현에 들어가기 앞서 종래의 구현 방법¹을 좀 더 알아보도록 하겠습니다. 인터럽트의 단점을 보완하기 위해서 소프트웨어로 해결하는 방법이 나오게 되었습니다. 여기서 스핀락(spinlock)² 을 사용하는 방식을 적용하였습니다. 이를 테면, 아래와 같은 코드를 작성할 수 있었습니다.

int flag[2];

void init(){
	flag[0] = flag[1] = 0; // 1 → 쓰레드는 락을 잡은 경우를 의미합니다.
}

void lock(){
	int other = 1 - self;
	flag[self] = 1;			  // self: 호출자의 쓰레드 ID
	while (flag[other] == 1); // spin-wait
}

void unlock(){
	flag[self] = 0;
}

이 방법도 위에서 살펴본 플래그를 사용하는 방식과 유사하게 flag[self] = 1에서 문맥 교환이 발생되었을 때의 문제가 발생하게 됩니다. 이를 테면, 쓰레드 A가 해당 부분에서 문맥 교환이 발생을 하고 쓰레드 B가 동작을 하면 flag[other]의 상태가 1이기 때문에 대기 상태에 들어가게 됩니다. 그리고 쓰레드 A로 다시 문맥 교환에 의해 돌아가게 되어 while(flag[other] == 1);로 들어가면 종전의 쓰레드 B에서의 flag[self] = 1의 작업으로 대기 상태에 들어가게 됩니다. 결과적으로, 교착 상태(deadlock) 상태가 되게 됩니다. 따라서 이를 해결할 필요가 있었고, 해결책이 나오게 됩니다.

잠시 초창기 구현 방식들인 스핀락을 활용한 락의 구현을 알아보기 전에 스핀락은 락의 요구 사항의 측면으로 봤을 때 어느 정도 만족을 하는 지 알아보도록 하겠습니다.

• Correctness : YES
  • 스핀락은 임계 구역에 하나의 쓰레드만 들어갈 수 있습니다.
• Fairness : NO
  • 스핀락은 공평함을 보장하지 않습니다.
  • 어떤 쓰레드는 무한히 대기할 수(spin)도 있습니다.
• Performance
  • 단일 CPU에서 성능에 영향을 끼치는 오버헤드는 꽤 큽니다.
  • 민액 여러 개의 쓰레드가 거의 그 갯수만큼의 CPU에서 돌아간다면, 스핀락은 꽤 합리적이게 돌아갈 것입니다.

이를 잘 유념하여 이제부터 나오는 방법론을 분석해보도록 하겠습니다.

Peterson’s Algorithm

이 방법은 기존의 코드와 유사하지만 현재 어느 코드가 작업 중 인지를 점검하는 추가적인 변수를 넣어서 해결하는 방법입니다.

int flag[2];
int turn;

void init(){
	flag[0] = flag[1] = 0;
	turn = 0; 					// 누구의 차례인가?
}

void lock(){
	int other = 1 - self;
	flag[self] = 1;
	turn = other;			    // 다른 쓰레드의 턴입니다.
	while ((flag[other] == 1) && (turn == other));
}

void unlock(){
	flag[self] = 0;
}

이런 식으로 작성을 하면 원하는 동작을 볼 수 있습니다. 하지만 이 방식도 완벽하지는 않습니다. 이 방식은 2개의 프로세스에 대해서만 동작을 하기 때문에 그 이상을 하고 싶을 때 이러한 방식으로는 제작하기 힘든 문제가 있습니다. 결국은 하드웨어적인 활용이 필요하게 되었습니다.

Test and Set (Atomic Exchange)

여기서 부터는 하드웨어적 활용입니다. 하드웨어적인 활용이 어떤 거창한 것이 아니라 메모리를 사용하겠다는 것을 의미합니다. 이 방법을 적용하기 위해서는 락들을 제작하기 위한 명령어를 만들어야 합니다.

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

이는 크게 테스트를 위한(testing) 과거 값을 반환을 하는 과정과 동시에 새로운 값을 갱신(update)을 하는 과정으로 나뉩니다. 이러한 작업은 원자적으로 수행되어야 합니다. 이를 사용하여 스핀락을 구현하면 아래와 같습니다.

typedef struct __lock_t{
	int flag;
} lock_t;

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

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

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

Compare and Swap

이 방식은 기대되는 값과 현재 가지고 있는 값이 동등한가를 비교하는 방식으로 동작하는 방법입니다. 만약 그 두 값이 동등한 경우 새로운 값으로 갱신하고, 그렇지 않으면 현재 메모리 값을 반환하도록 합니다. 이의 구현은 아래와 같이 됩니다.

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

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

Load-Linked and Store-Conditional

이 방법은 저장 상태(Store-Conditional)는 현재 저장하고자 하는 주소에 간간히 일어나는 저장 작업이 없는 경우에만 지속되도록 하는 방법입니다. 이런 저장 상태의 결과에 따라 아래와 같은 작업이 벌어질 수 있습니다.

• SUCCESS : 1을 반환하고 값을 갱신합니다.
• FAILED : 0을 반환하고 값을 갱신하지 않습니다.

int LockLinked(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
	}
}

void lock(lock_t *lock){
	while(1){
		while(LoadLinked(&lock->flag) == 1) ;
		if(StoreConditional(&lock->flag, 1) == 1)
			return;
	}
}

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

하지만 위의 lock을 좀 더 압축을 하면 아래와 같은 방식으로 만들 수 있습니다.

void lock(lock_t *lock){
	while(LoadLinked(&lock->flag) || !StoredConditional(&lock->flag, 1)) ;
}

Fetch and Add

이 방식은 특정 주소의 값을 반환을 하면서 자동적으로 값을 1씩 증가 시켜주는 것입니다.

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

Ticket Lock

이 방식은 fetch and add로 만들어진 방식으로 먼저 본인의 턴이 올 때까지 기다리다가 티켓을 받은 후, 작업을 하는 방식으로 이 방식을 사용하게 되면 모든 쓰레드가 동작을 하게 하는 것을 보장할 수 있습니다. 즉, 이는 다시 말하면 앞에서 락의 요구 사항 중 하나인 공평성(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);
}

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

스핀락

이런 여러 방법에도 불구하고 스핀락에는 치명적인 단점이 있습니다. while에 의해 스핀이 너무 도는 문제점이 있습니다. 따라서 몇몇 경우에서는 매우 비효율적인 상황이 발생할 수 있습니다. 그래서 이러한 문제점을 OS의 지원을 통해 해결하는 방법론이 나왔습니다.

Yield를 활용하는 방법

이는 스핀에 들어가는 경우에 CPU를 다른 쓰레드에게 양보하는 방식입니다. 따라서 아래와 같은 특징을 가지게 됩니다.

• OS의 시스템 호출(system call) 명령이 호출자로 하여금 동작(running) 상태에서 대기(ready) 상태로 전이하게 됩니다.
• 문맥 교환에 드는 비용이 있으며, 기아(starvation)가 여전히 발생하는 문제가 있습니다.

void init(){
    flag = 0;
}

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

void unlock(){
    flag = 0;
}

Queue를 사용하는 방법

이 방식을 큐(Queue)를 사용해서 어떤 쓰레드가 락에 들어가서 대기 중인지를 계속해서 추적하는 방식으로 아래와 같은 특별한 명령어로써 구현이 됩니다.

• park ()
  • 쓰레드를 잠자는 상태(sleep)으로 만들도록 합니다.
• unpark (threadID)
  • threadID에 해당하는 특정 쓰레드를 깨우도록 합니다.

typedef struct __lock_t{
    int flag, 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) ;
    if(m->flag == 0){
        m->flag == 1;
        m->guard = 0;
    }
    else{
        // gettid : get thread identfication
        queue_add(m->q, gettid()); 
        m->guard = 0;
        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;
}

하지만 이렇게만 구현하면 생각하지 못한 문제가 발생할 수 있습니다. 이를 테면, 쓰레드 A, B가 있는 데 쓰레드 B가 park()를 수행하기 직전에 쓰레드 A가 unlock() 전체를 수행을 해버린다면 쓰레드 B가 다시 깨어날 수 없게 됩니다. 이를 Solaris 운영체제는 setpark()라는 명령어를 통해 해결을 하기로 하였습니다. 이는 park() 발생 직전 다른 쓰레드로 부터 unpark()가 일어나는 경우 park()를 수행하고자 하는 쓰레드는 잠자는 상태에 들어가는 것이 아니라 lock() 함수를 끝내 버립니다.

Futex

앞의 Solaris OS의 구현 방법을 확장해낸 방식으로 리눅스에서 제공하는 방식입니다. Solaris의 park(), unpark()와 동일하게 futex_wait(address, expected), futex_wake(address)로 구성됩니다. 각각의 역할은 아래와 같습니다.

• futex_wait(address,expected)
  • 쓰레드가 잠자는 상태로 들어가게 만듭니다.
  • 주소(address)의 값이 기대되는(expected) 값과 동일하지 않으면 즉시 빠져나옵니다.
• futex_wake(address)
  • 큐에서 기다리고 있는 쓰레드 하나를 깨우도록 합니다.

아래의 내용은 nptl library의 lowlevellock.h³에서 발췌하고 약간의 이해를 돕기 쉽게 수정한 내용으로 각 역할에 대한 내용은 코드의 주석을 참고하시면 됩니다.

/*
 * mutex의 비트열에 대한 의미
 * 
 * 최상위 비트 : 락 상태를 가지고 있는 비트이다.
 * 나머지      : 락이 몇 개 걸렸는 지를 가지고 있다.
 */
void mutex_lock(int *mutex){
    int v;
    // 최상위 비트가 0이면 락을 걸도록 합니다.
    if(atomic_bit_test_set(mutex, 31) == 0) return;

    // 락 대기열에 하나가 더 들어갔음을 표기하도록 합니다.
    atomic_increment(mutex);
    while(1){
        // 최상위 비트가 0이 될 때까지 동작합니다.
        if(atomic_bit_test_set(mutex, 31) == 0){
            atomic_decrement(mutex);
            return;
        }

        /*
         * v는 최상위 비트를 점검하여 락 상태를 확인합니다.
         * 만약 최상위 비트가 1인 경우, 2의 보수에 따라 v의 값은
         * 음수가 될 것이고 따라서 우리는 락이 걸렸음을
         * 알 수 있습니다.
         */
        v = *mutex; 
        if(v >= 0) continue;

        futex_wait(mutex, v); // 잠 자는 상태에 들어가도록 합니다.
    }
}

void mutex_unlock(int *mutex){
    // 최상위 비트를 0으로 만들어서 lock을 풀도록 합니다.
    if(atomic_add_zero(mutex, 0x80000000)) return; 
    futex_wake(mutex);
}

추가적으로

락을 최종적으로 개선하기 위해선 사실 OS의 지원을 받으며 스핀도 도는 것이 현명합니다. 즉, 2단계에 걸친 작업 양상이 보인다고 할 수 있습니다.

• 1 단계
  • 락이 걸려있는 상태에서 스핀을 잠시동안 돌도록 합니다.
  • 락이 잠시 도는 동안 풀려있지 않는다면 2단계로 넘어가도록 합니다.
• 2 단계
  • 호출자는 잠자는 상태로 들어가게 됩니다.
  • 호출자는 오로지 락이 풀리면 깨어나게 됩니다.