(22.04.11) Synchronization

이제 그토록 강조해온 동기화를 다룰 것이다.

0. 동기화의 필요성과 critical section

Concurrency에 있어 공유 상태는 유용하다. 쓰레드를 사용하면서 변수를 공유하는 것은 프로세스 간 통신보다 저렴하기 때문이다. 허나 잘못 사용하게 되면 끔찍한 문제를 일으킬 수 있다. 실행의 단위가 되는 쓰레드가 공유 변수를 사용하는 동안에 어느 때나 Context Switching을 일으킬 수 있기 때문에 이는 공유 상태의 일관되지 않은 결과를 초래하기도 한다.

 

예시를 들어보자. 다음과 같이 공유 자원 y에 접근하는 두 쓰레드 A, B가 있다고 하자. y의 초기값이 0이라 할 때, 쓰레드 A에서 최종적인 x의 값은 무엇이 되어야 할까?

// thread A
x = 1;
x = y + 1;

// thread B
y = 2;
y = y * 2;

만약 A가 먼저 실행되고 종료된다면 x = 1일 것이다. 만약 B의 y = 2까지 진행된 뒤에 A가 실행된다면 x = 3일 것이다. 만약 B가 끝까지 진행된 이후라면 y = 4일 것이므로 x = 5가 될 것이다. 앞선 포스팅에 나온 것처럼 쓰레드는 어떤 순서대로라도 실행되고 중간에 문맥이 교체될 수 있기 때문에 공유 상태의 일관성이 보장되지 않는 것이다. 허나, 프로그램은 어떤 임의의 interleaving이 있더라도 그에 영향을 받아서는 안 된다. 때문에 이를 고치기 위해 동기화 문제를 다루는 것이다.

 

본격적으로 동기화 문제를 해결하는 방법을 다루기 전에 몇몇 용어의 정의를 알아보자. 복수의 프로세스가 공유된 자원에 동시에 접근 및 변경하면서, 실행의 결과가 접근하는 순서에 의해 달라지는 위와 같은 현상을 race condition이라고 한다. Critical Section은 공유 자원에 동시에 접근하려는 코드 영역을 의미한다. Mutual Exclusion이란 오직 한 쓰레드만이 critical section을 실행하고 있다는 것을 보장하는 것이며, 이는 한 쓰레드가 작업을 하는 동안 다른 쓰레드를 배척한다는 의미를 포함한다.

1. Too Much Milk 문제로 알아보는 Safety와 Liveness

룸메이트 A와 B가 같은 냉장고를 쓰고 있는 상황을 생각해보자. 우유가 필요해서 우유를 사러가야 한다. 우유는 한 팩만 사오면 된다. 이 때의 문제 또한 동기화 문제가 개입할 수 있는 여지가 있다. 가장 간단한 경우로, A가 우유를 사러 장을 보러 나갔을 때, B가 냉장고를 열어 보고 우유가 없어 장을 보러 간다면 최종적으로는 우유가 두 팩 생길 것이다. 제대로 된 대처 없이는 너무 많은 우유를 사오거나, 아예 우유가 없는 상황도 발생하기도 한다.

 

이러한 TMM 문제를 통해 동기화 문제를 해결할 때 충족되어야 하는 두 가지 조건을 살펴보자.

 

• Safety : 프로그램은 절대로 나쁜 상태로 들어가서는 안 된다. TMM 문제의 경우, 너무 많은 우유를 사오는 일이 있어서는 안 되는 것이다. (No Too Much Milk)
• Liveness : 프로그램은 언젠가는 의도한 동작을 수행해야 한다. TMM 문제의 경우, 누군가는 우유를 사와서 최종적으로 냉장고에 우유가 있어야 한다. (No No Milk)

2. TMM 문제 해결 시도

그럼 이제 TMM 문제를 해결하려는 시도를 살펴보자.

2-1. Try 1

우유가 없어서 장을 보러 가기 전에 노트를 남기자. 노트가 남겨져 있다면 장을 보러가지 않는 것이다.

if (!milk) {
	if (!note) {
		leave note
		buy milk
		remove note
	}
}

간단해보이고, 실생활에서는 잘 통할 것 같지만 전자 세계는 냉혹하다. A가 냉장고가 빈 것을 확인하여 장을 보러간다고 노트를 남기기 직전에 B가 냉장고를 열고 우유가 없다는 사실을 확인한다면, 노트가 없기 때문에 B 또한 결국 장을 보러 갈 것이다. 이러면 룸메이트 수준이 아닌데... 결국 Safety 위반으로 다른 해결책을 생각해야 한다.

2-2. Try 2

그러면 내 노트를 먼저 남기고 상대방의 노트가 있는지를 확인해보자. 만약 있다면 장을 보지 않는 것이다.

// Thread A
leave note A
if (!note B) {
	if (!milk)
		buy milk
}
remove note A

// Thread B
leave note B
if (!noteA ) {
	if (!milk)
		buy milk
}
remove note B

이 해결책은 새로운 문제를 유발한다. A가 노트를 남긴 후, B의 노트를 확인하기 직전에 B가 냉장고를 확인하고 B의 노트를 남긴다. B의 입장에서는 A가 노트를 남겼으므로 장을 보러가지 않는다. B가 노트를 제거하기 직전에 다시 A로 돌아오면 B의 노트가 남겨져 있기 때문에 A도 장을 보지 않는다. 즉 아무도 우유를 사러 가지 않게 되어 Liveness 위반이므로 여전히 새로운 해법이 필요하다.

2-3. Try 3

Try 2에서 문제가 되었던 것은 메모가 남겨져 있는 것을 한 번만 체크하기 때문이었다. 이를 while로 바꿔서 계속 체크하게 한다면 어떨까?

// Thread A
leave note A
while (note B) // X
	do nothing;
if (!milk)
	buy milk
remove note A

// Thread B
leave note B
if (!noteA ) { // Y
	if (!milk)
		buy milk
}
remove note B

X 시점에서 생각해보자. B의 노트가 있다면 A는 B가 노트를 남기고 어디까지 진행이 됐는지 알 수 없기 때문에 계속 기다린다. 만약 B의 노트가 없어졌다면, B가 우유를 사고 끝낸 시점이거나, A가 남긴 메모를 보고 사지 않기로 결정하고 끝낸 시점이라는 뜻이다. 따라서 해당 시점에서는 B의 중간 개입이 없을 것이라는 뜻이기에 그제서야 안전하게 냉장고를 확인하고 우유가 없다면 사러가도 되는 것이다.

 

이와 대조하여 Y 시점에서 생각해보자. A의 노트가 없다면 A가 시작도 하기 전이라는 뜻이므로 우유를 사러가도 안전하다. 반면 A의 노트가 있다면 위의 동작 구조를 봤을 때 A가 결국 사올 것이기에 우유를 사러가지 않아도 무방하다. 따라서 B는 우유를 사지 않고 종료하는 것이다.

 

굉장히 복잡한 해결 방법이지만 아무튼 각 시점에서 봤을 때 동기화 문제는 생기지 않는다는 것을 알 수 있다. 단, 이 해법은 처음 문제를 직면했을 때와 비교해서 엄청나게 복잡해졌을 뿐더러, 단 2개의 쓰레드에만 적용이 될 수 있다는 것이 가장 큰 흠이다. 물론 이러한 과정을 일반화하기 위해 Peterson's Algorithm이라는 것이 사용되는데, 이 또한 만만치 않게 복잡하다고 한다. 따라서, 공학자들은 이 문제를 좀 더 간단히 해결할 수 있는 방법을 찾게 되었다. 그 결과 Lock이 탄생했다.

3. Lock

Lock은 두 가지 기능성이 제공된다.

 

• Lock::acquire : Lock을 아무도 가져가지 않은 상태가 될 때까지 기다렸다가 가져간다.
• Lock::release : Lock을 놓아주면서, 그 락을 기다리고 있는 작업 중 아무나 깨운다.

해당 Lock을 사용할 때 우리는 몇 가지 사항을 보장받을 수 있다.

 

• 한 번에 하나의 작업만 Lock을 쥐고 있게 된다. (Safety)
• 아무도 Lock을 쥐고 있지 않으면, acquire를 통해 Lock을 쥘 수 있다. (Liveness)
• Lock을 쥐고 있던 작업이 종료되어 반환할 때, 대기하는 작업보다 높은 우선도의 작업이 없다면 해당 작업이 결국 Lock을 가진다. (Liveness)

실제로 Lock을 이용하면 TMM도 훨씬 간단하게 일괄적으로 해결이 가능하다.

lock.acquire();
if (!milk)
	buy milk
lock.release();

4. Bounded Buffer 문제 (Producer Consumer 문제)

그럼 이제 또다른 유명한 동기화 문제인 Bounded Buffer 문제, 또는 Producer Consumer 문제를 살펴보자. 해당 상황은 공유된 제한된 양의 버퍼를 두고 생산자 쓰레드와 소비자 쓰레드가 실행되는 상황이다. 생산자 쓰레드는 아이템을 버퍼에 넣고, 소비자 쓰레드는 버퍼에서 아이템을 꺼내 소비한다. 버퍼가 FULL 일땐 생산자가 기다려야 하며, 버퍼가 EMPTY 일땐 소비자가 기다려야 한다.

 

생각할 수 있는 가장 간단한 문제는 Safety 위반으로 두 소비자가 동시에 같은 아이템을 꺼내 소모하는 것이다. Liveness 위반의 경우는 이론상의 문제이긴 하지만, 생산자가 생산을 해도 소비자가 소비하지 못하는 경우, 소비자가 소비를 해서 버퍼가 비어도 생산자가 생산하지 못하는 경우이다. 우리는 지금까지 동기화 문제를 위해 Lock이란 것을 개발했으니 이를 이용해서 해당 문제를 간단히 해결할 수 있을 것처럼 보인다. 간단히 구현하면 아래와 같을 것이다.

 

해당 구현은 문제가 없을 것 같지만 실제로는 문제가 생긴다. tryget에서 NULL이 반환됐을 경우, 정말로 공유 버퍼가 비었다고 말할 수 있을까? 아니다. 만약 버퍼가 비었다는 것을 확인하여 락을 반환한 이후, NULL을 반환하기 직전 생산자가 실행되어 버퍼에 아이템을 채워넣었다면 어떨까. 이러면 버퍼에 아이템이 있음에도 소비자가 소비하지 못하는 문제가 생긴다. 위에서 설명한 Liveness와 일맥상통하는 부분이다. 이 문제를 해결하기 위해서는 일정 시점까지 생산자와 소비자를 기다리게 한 다음, 생산자는 소비자에게 버퍼가 비지 않게 되었다고, 소비자는 생산자에게 빈 버퍼 공간이 생겼다고 "통보"해줄 필요가 있다.

5. Condition Variable과 이를 이용한 BB 문제 해결 시도

그래서 공학자들은 Condition Variable이라는 개념을 개발해냈다. Condition Variable은 Lock에 의해 보호되는 공유된 자원의 상태가 바뀌기까지 기다리는 것을 효율적으로 하기 위한 동기화 방법이다. CV는 공유 자원을 보호하는 Lock을 쥐고 있을 때만 사용할 수 있으며, 다음의 3가지 기능성을 제공한다.

 

• Wait() : atomic하게 쥐고 있는 Lock을 release하고 wait 상태에 들어간다. 다시 깨어나게 되면 Lock을 acquire한다.
• Signal() : wait 상태에서 기다리고 있는 작업이 존재한다면 하나를 깨운다.
• Broadcast() : wait 상태에서 기다리고 있는 작업이 존재한다면 모두를 깨운다.

Condition Variable의 중요한 특징은 memoryless하다는 것이다. 이는 waiting 쓰레드의 queue말고 내부 상태가 없다는 뜻이다. 이 말인즉, 만약 기다리고 있는 쓰레드가 없을 때 signal/broadcast가 일어난다면 해당 신호는 어딘가에 저장되지 않고 버려진다는 뜻이다. 이 때문에 CV는 과거 signal이나 broadcast에 대한 어떠한 정보도 들고 있지 않는다.

 

또 한 가지 중요한 것은 signal 또는 broadcast가 호출된 직후에 깨어난 쓰레드가 곧바로 실행되지 않는다는 것이다. 이들은 단지 해당 쓰레드를 ready list에 넣을 뿐이며, lock이 release된 시점에 누구라도 해당 lock을 acquire할 수 있기 때문에 lock을 acquire할 수 있는 시점이 올 때까지 쓰레드가 실행되지 않는다. 해당 특성으로 인해 한 가지 중요한 특징이 생긴다. wait를 할 때는 반드시 loop 안에서 해야 한다는 것이다. 단순 if 만으로 조건을 검사하여 wait을 하는 경우를 생각해보자. 이후 조건이 충족되어 signal에 의해 쓰레드가 깨어나는 시점에 쓰레드가 바로 실행되지 않을 수 있다. 락을 다른 쓰레드가 가져가 공유 자원에 변화가 일어났다면 wait의 반환 시점에서 나머지 기능을 실행하는데 필요한 조건이 충족되었으리라는 보장은 없다. 따라서 wait 이후에도 추가 검사를 할 필요가 있으며, 이 때문에 loop 안에서 wait하라고 하는 것이다.

 

이제 CV를 이용해 BB 문제를 해결하는 시도를 살펴보자.

5-1. Try 1

가장 첫 번째 시도는 아래와 같다.

front = tail = 0;

put (item) {
    lock.acquire();
    if ((tail - front) == MAX) {
        cond_var.wait(lock);
    }
    buf[tail % MAX] = item;
    tail++;
    cond_var.signal();
    lock.release();
}

get () {
    lock.acquire();
    if (front == tail) {
        cond_var.wait(lock);
    }
    item = buf[front % MAX];
    front++;
    cond_var.signal();
    lock.release();
    return item;
}

해당 방식에서는 wait을 하는 조건 검사에 if 문을 사용한다. 애시당초 이것부터 잘못된 것이지만 구체적으로 어떻게 터질 수 있는지도 살펴보자. MAX = 1이며, 생산자 P, 소비자 C1, C2가 있는 상황을 고려해보자. 

 

• C1이 실행된다. 첫 번째 if 문에서 걸려 wait 상태에 들어갈 것이다.
• P가 실행된다. (tail - front == 0) != 1 이므로 wait하지 않고, 아이템을 하나 넣으면서 signal을 보낸다. 이제 C1은 Lock을 잡으면 언제든지 다시 실행될 수 있다.
• P가 다시 실행된다. 이 시점에서는 tail - front == MAX이므로 Lock을 반환하고 wait 상태에 들어간다.
• C2가 실행된다. 현재 tail - front == MAX 이므로 wait 하지 않고 아이템을 하나 소비하며 signal을 보낸다. 이제 P도 Lock을 잡으면 언제든지 실행될 수 있다.
• C2가 Lock을 반환할 때 C1이 Lock을 잡아 실행된다. 문제는 wait 이후에도 여전히 front == tail, 즉 버퍼가 비어있어 비어있는 버퍼에서 아이템을 가져오려는 시도가 발생한다.

요약하면 Safety 요건을 위반하는 상황이 생긴다. 위에서 설명했든, signal 이후 깨어나는 시점이 고정되어 있지 않기 때문에 조건 충족이 여전히 되어 있지 않을 수 있어 발생하는 문제이다. 따라서 이를 while로 바꿔본다.

5-2. Try 2

while로 바꾼 다음의 코드는 맞을까?

front = tail = 0;

put (item) {
    lock.acquire();
    while ((tail - front) == MAX) {
        cond_var.wait(lock);
    }
    buf[tail % MAX] = item;
    tail++;
    cond_var.signal();
    lock.release();
}

get () {
    lock.acquire();
    while (front == tail) {
        cond_var.wait(lock);
    }
    item = buf[front % MAX];
    front++;
    cond_var.signal();
    lock.release();
    return item;
}

유감스럽게도 늘 그랬듯 문제가 한 번에 해결된 적이 없듯, 이번에는 liveness가 조진다. 사실 이건 잘못 짜서 생기는 문제에 더 가까운 것 같다. 위와 같이 MAX = 1, 하나의 P, 두 개의 C1, C2를 생각하자.

 

• C1이 실행되고 wait에서 기다린다.
• C2가 실행되고 wait에서 기다린다.
• P가 실행되어 signal을 보낸다. C1이 일단 깨어나 ready list에 올라간다.
• P가 다시 실행되어 wait에서 기다린다.
• C1이 실행되면서 signal을 보낸다. 문제는 해당 signal로 P가 아닌 C2가 깨어난다.
• C2가 일어났으나, 여전히 front == tail인 것을 확인하고 다시 wait 상태가 된다.
• C1이 다시 실행될 때, front == tail이기 때문에 wait 상태가 된다.
• 결론적으로 모든 쓰레드가 wait 상태에 빠져서 일어나지 않는다. (liveness 위반)

이 상황에서 문제가 되는것은 C의 신호가 C로 갈 수 있다는 것이다. 따라서 cond_var의 종류를 분리해서 C는 P로만, P는 C로만 신호를 보낼 수 있도록 만들면 문제가 없다.

front = tail = 0;

put (item) {
    lock.acquire();
    while ((tail - front) == MAX) {
        full.wait(lock);
    }
    buf[tail % MAX] = item;
    tail++;
    empty.signal();
    lock.release();
}

get () {
    lock.acquire();
    while (front == tail) {
        empty.wait(lock);
    }
    item = buf[front % MAX];
    front++;
    full.signal();
    lock.release();
    return item;
}

6. Lock을 실제로 구현하는 방법

이제 개념적으로 Lock이 어떤 것인가는 알았으니, 이를 실제로 구현하는 방법에 대해서 살펴보자.

6-1. Uniprocessor에서

단일 프로세서에서는 문제가 비교적 간단하다. 어떠한 함수가 atomic하게 실행되도록 하기 위해서는 다른 프로세스가 CPU를 선점하도록 하지만 않으면 되는 것이다. 현재 잡고 있는 프로세서를 거치지 않으면 다른 프로세스는 실행될 일이 없을테니 atomic함을 위해서는 preemption만 통제하면 된다. CPU가 선점되는 방식은 크게 두 가지인데, 하나는 쓰레드가 자발적으로 CPU에 대한 통제권을 포기하는 yield 같은 경우, 나머지 하나는 외부에서 인터럽트가 들어와 통제권을 강제로 넘기게 되는 경우이다. 따라서 잠시동안만 인터럽트를 해제할 수 있다면 atomic한 연산이 가능해질 것이다.

 

정말 대충 구현하면, 인터럽트를 끄는 것을 락을 잡는 것으로, 인터럽트를 켜는 것을 락을 놓는 것으로 할 수 있다. 문제는 이 방식으로는 여러 개의 락을 만드는 것은 불가능하며, 락을 가지고 연산하는 시간이 길어질수록 커널이 통제권을 가져올 수 없어 스케줄러의 동작 및 커널이 해야 하는 작업들을 제대로 하기 어려워진다. 따라서 락을 구하는 잠깐의 순간만 인터럽트를 끄고 락을 구한 이후에는 인터럽트를 다시 켜도록 하자.

Lock::acquire() {
    disableInterrupts();
    if (lockValue == BUSY) {
        waiting.add(TCB);
        TCB->state = WAITING;
        next = readyList.remove();
        switch(TCB, next);
        TCB->state = RUNNING;
    } else {
        lockValue = BUSY;
    }
    enableInterrupts();
}

Lock::release() {
    disableInterrupts();
    if (!waiting.Empty()) {
        next = waiting.remove();
        next->state = READY;
        readyList.add(next);
    } else {
        lockValue = FREE;
    }
    enableInterrupts();
}

인터럽트를 활성화하는 것은 깨어나서 다음에 실행될 쓰레드가 맡을 책임이다. 여기서, switch(TCB, next) 직후에는 다른 프로세스로 실행이 넘어가며, 다시 복귀한 이후에 TCB->state = RUNNING 이 실행된다. release에서는 대기하고 있는 쓰레드들 중 하나의 쓰레드만 깨우기 때문에 실행권이 돌아온 프로세스는 본인이 락을 쥐게 되었다는 것을 알 수 있고, RUNNING 상태로 바로 변환 후에 마저 실행이 가능하며, safety가 보장된다.

6-2. Multiprocessor에서

그럼 멀티 프로세서에서는 어떨까? 단순히 인터럽트를 끄고 켜는 방식으로는 안전하지 못하다. 인터럽트 자체도 프로세서 단위로 일어날 뿐더러, 여러 개의 프로세서에 걸쳐서 동시에 일어나는 일을 인터럽트를 꺼서 통제하는 것은 불가능하다. 간단하게는 위의 경우에서 lockValue가 FREE라고 인식한 두 프로세스가 다른 프로세서에서 실행되며 둘 다 본인이 락을 acquire했다고 주장할 경우가 생길 수 있다.

 

멀티 프로세서에서의 락의 구현이 어떻게 되어야 하는지를 살펴보기 위해 spinlock을 가져와보자. spinlock은 여러 프로세서들이 해당 락을 얻기 위해 루프를 돌면서 (busy wait) 기다리는 락으로, 해당 락이 짧은 시간동안만 차지될 것을 전제로 한다. spinlock은 CPU 스케줄러와 락을 구현하기 위해 사용된다.

Spinlock::acquire() {
    while (lockValue == BUSY)
        ;
    lockValue = BUSY
}

Spinlock::release() {
    lockValue = Free;
}

spinlock이 멀티 프로세싱에서 가지는 문제는 위에서 설명한 문제와 비슷하다. spinlock의 lockValue를 두 개의 프로세서에서 동시에 접근하려고 할 때를 생각하자. 각 프로세서는 L1, L2 cache를 각자 가지고 있고, L3 단계에서는 sharing이 일어난다. 특정 프로세서에서 release가 실행되어 L3 단계까지 lockValue가 FREE로 변경되었다고 하자. 이는 서로 다른 두 프로세서에 각각 통보될 것이고 만약 이 두 프로세서가 모두 락을 잡기 위해 대기하고 있었다면 동시에 BUSY로 값을 바꾸면서 safety violation이 일어날 것이다.

 

이러한 문제는 OS 수준에서 잡을 수 있는 것이 아니다. 때문에 OS 개발자들이 막힐 때마다 사용하는 HW 개발자 괴롭히기 스킬을 사용해서 해당 문제를 잡기 위한 뭔가를 만들어달라고 부탁했다. 이 때문에 HW 개발자들은 한 번에 한 개의 프로세서만 특정 메모리에 접근할 수 있도록 하는 명령어를 만들었다. 해당 명령어는 atomic하게 값을 메모리에서 읽고 처리한 뒤, 다시 메모리에 처리된 값을 쓰도록 한다. 이에 대한 예시로는 TestAndSet, 인텔의 xchgb, lock prefix, Compare and Swap을 꼽을 수 있다. 이들 명령어를 사용해서 Lock과 CV를 구현하는 데 사용할 수 있게 된 것이다.

 

일례로 TestAndSet을 통해 Spinlock을 구현하면 아래와 같이 만들 수 있다.

// CPU does atomically
int TestAndSet (int *old_ptr) {
    int old = *old_ptr ; // fetch old value at old_ptr
    *old_ptr = BUSY; // store BUSY into old_ptr
    return old; // return the old value
}

Spinlock::acquire() {
    while (TestAndSet(&lockValue) == BUSY)
        ;
}

Spinlock::release() {
    lockValue = Free;
}

여기서, release하는 쪽은 어차피 혼자이기 때문에 atomic하지 않아도 상관은 없다. 일반적으로 atomic 명령어는 느리기 때문에 일반 명령어를 선호하게 된다. 해당 방식으로 이제 safety는 문제가 없어졌다. 그러면 완전히 해결된 것일까? 이는 아니다. 첫 번째로 spinlock은 고질적인 busy waiting 문제를 가지고 있다. 아무것도 하지 않으면서 CPU cycle을 낭비하기 때문에 일반적으로 단일 프로세서에도 적용이 될 수 있는 해결 방식이 되기 위해서는 busy wait 방식을 버려야 한다. 두 번째로는 liveness를 보장하지 않는다는 문제가 있다. 해당 방식에서는 새로운 쓰레드가 계속 락을 잡으려고 들어오는 상황에서 특정 쓰레드가 계속 락을 잡는데 실패해서 오랫동안 실행되지 못할 가능성이 있다. 모든 쓰레드가 일정 시간 이내에 락을 잡게 된다는 보장이 없는 것이다. 일종의 기아 현상 같은 것이다.

 

두 문제는 각각 해결할 수 있다. 첫 번째 busy waiting 문제의 경우, 자발적으로 CPU를 반환하는 yield를 사용해서 schedule out 시키면 낭비되는 CPU cycle을 줄일 수 있다. 기아 현상은 다음의 새로운 HW atomic 명령어를 통해 잡을 수 있다.

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

이를 이용하여 일종의 번호표 발부 시스템을 만든다. 은행이나 음식점에 가면 번호표를 뽑는 것처럼 락을 잡으려는 요청을 할 때마다 번호표를 준다. 해당 번호가 되면 락을 요청했던 쓰레드는 락을 받아 원하는 작업을 하면된다. 락을 반환할 때는 번호를 하나씩 증가시키면서 다음에 락을 잡을 쓰레드를 지정한다. 

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)
        yield();
}

void unlock(lock_t *lock) {
    lock->turn = lock->turn + 1;
}

해당 구현에서 safety는 같은 번호를 받는 쓰레드는 없다는 것으로 보증된다. myturn에 티켓 번호를 받아올 때, atomic한 명령어인 FetchAndAdd를 통해서 받아오기 때문에 해당 티켓 번호는 유일하다는 것을 알 수 있기 때문이다. unlock에서 atomic한 명령어 사용이 필요 없는 이유는 앞선 구현과 마찬가지로 오직 한 프로세스만 unlock할 수 있기 때문이다. 해당 방식으로는 기아 현상도 없어지는 것을 알 수 있다. 일종의 FIFO 형태로 락을 주는 방식이 되었기 때문에 모든 쓰레드가 언젠가는 락을 받는 것이 보장되기 때문이다. 이러한 방식을 Ticket Lock이라고 하며 대부분의 락 구현 방식은 이를 따라가고 있다고 한다.

7. Semaphore

이제 마지막으로 Semaphore, 세마포어에 대해 살펴보자. 세마포어는 학부생에게는 최소 경로 알고리즘으로 유명할 다익스트라에 의해 1960년대에 정의된 것으로, lock과 condition variable을 모두 일반화할 수 있는 개념이다. 

 

세마포어 자체는 음이 아닌 정수값을 가지며, 다음의 두 가지 연산을 제공한다.

 

• P (down이라고도 함) : atomic하게 세마포어 값이 양의 정수가 될 때까지 기다렸다가 1을 차감한다.
• V (up이라고도 함) : atomic하게 세마포어의 값을 1 올리면서 P에서 기다리고 있던 것들을 깨운다.

다익스트라 씨가 네덜란드 분이라 P는 네덜란드어로 "테스트"인 "proberen"에서, V는 "증가시키다"인 "verhogen"에서 따왔다고 한다.

 

세마포어의 초기 값은 음이 아닌 임의의 정수 값이 모두 가능하다. 만약 어떤 자원에 최대 n개의 쓰레드가 접근할 수 있다면 세마포어의 초기 값을 n으로 설정해 Counting Semaphore로 활용할 수 있다. 세마포어의 초기 값을 1로 설정한 binary semaphore의 경우에는 mutual exclusion 용도로 사용할 수 있어 Lock 처럼 활용할 수 있다. 또한 세마포어 값을 0으로 초기화한 경우, 특정 조건이 만족될 때까지 대기하고, 해당 조건이 충족됐을 때 signal하는 용도로 사용할 수 있어 Condition Variable과 기능적으로 유사한 역할을 할 수 있다. (Scheduling Constraints) 단, 세마포어는 Condition Variable과는 달리 메모리가 있어, V가 먼저 진행되더라도 나중에 실행될 P의 행동에 영향을 준다.

 

세마포어를 사용해 BB 문제를 다시 풀면 다음과 같이 해결할 수 있다. 

 

이 때 수업에서는 empty나 full 중 하나의 세마포어만을 사용하거나, 사용된 세마포어의 순서를 바꿨을 때도 정상동작할지를 생각해보라고 하셨다. 시험에 나올 것 같으니 생각해보도록 하자. 이 다음으로 살펴본 것은 Lock은 세마포어를 통해 구현할 수 있었으니, Condition Variable을 세마포어를 활용해 정확히 구현하는 것이었다.

7-1. Try 1

가장 간단한 형태의 구현으로 만들어보자. 이 구현 상의 문제는 무엇일까?

wait(lock) {
	lock.release();
	semaphore.P();
	lock.acquire();
}

signal() {
	semaphore.V();
}

Condition Variable의 특징은 Memoryless하다는 것이다. 이는 만약 signal이 wait보다 먼저 일어날 경우에는 무시되어야 한다는 뜻이다. 헌데 이 구현 방식에서는 semaphore의 값이 하나 올라가 P 연산 진행시 기다리지 않게 되면서 영향을 주는 결과를 초래한다. 때문에 어떤 작업이 P 연산으로 semaphore를 기다리고 있을 때만 V 연산을 하도록 바꿔주자.

7-2. Try 2 (Memoryless Property Fix)

새롭게 고친 다음의 코드도 문제가 있다.

wait(lock) {
	lock.release();
	semaphore.P();
	lock.acquire();
}

signal() {
	if (semaphore is not empty)
		semaphore.V();
}

semaphore의 기능은 atomic하게 실행되지만 lock을 release하는 코드와 semaphore.P() 사이에서 Context Switching은 발생할 수 있다. 스위칭이 일어난 뒤, signal()에서는 아무런 쓰레드가 semaphore를 기다리고 있지 않기 때문에 V를 실행시키지 않는다. 그런데, 다시 원래 프로세스로 돌아가게 되면 semaphore의 P가 실행되면서 wait 상태로 들어간다. 만약 signal이 한 번만 실행된다면 이는 기존 프로세스가 영원히 기다리게 만드는 것으로, liveness property를 위반하게 하는 것이다.

 

이러한 문제는 또 어떻게 회피할 수 있을까? wait가 선언된 직후에는 semaphore.P가 실행되기 이전에 signal 측으로 전환이 되더라도 V가 호출되도록 해야 한다. 따라서 다음과 같은 해법을 제시한다.

7-3. Try 3

wait(lock) {
	semaphore = new Semaphore;
	queue.Append(semaphore); // queue of waiting threads
	lock.release();
	semaphore.P();
	lock.acquire();
}

signal() {
	if (!queue.Empty()) {
		semaphore = queue.Remove();
		semaphore.V();
	}
}

wait에 진입한 순간에는 lock이 걸려있어 preemption이 일어난다 하더라도 signal은 불릴 수 없다. 따라서 lock을 release하기 이전에 wait가 선언되었음을 알리는 것으로 global 구조인 queue에 새로운 semaphore를 하나 만들어서 넣는다. 만약 lock을 release한 이후에 위와 같은 과정이 진행된다 하더라도, 이번에는 queue에 semaphore가 들어있다는 것을 signal 측에서 알 수 있어 다른 작업에서 wait가 불렸다는 것을 알 수 있다. 따라서 signal 쪽에서는 V를 불러 미리 semaphore 값을 증가시켜 놓아, wait 쪽에서 liveness 위반 없이 정상 실행되도록 한다.

 

Context Switching이 일어나지 않고 일반적으로 signal이 늦게 불리는 경우라 할지라도 먼저 semaphore.P가 불리면서 기다리고 있을 것이기에 문제는 발생하지 않는다. 이 해법의 핵심은 wait가 불렸음을 signal 측에 알리기 위해 Lock release가 이루어지기 전에 조치를 취하는 것이다. 따라서 queue.append를 lock release 이후에 넣으면 똑같이 liveness 문제가 발생한다.

8. 기억해야 할 규칙들

마지막으로 기억해야 할 점들을 상기하면서 해당 파트를 마치자.

 

• 공유 자원에 접근하려고 할 때는 반드시 Lock과 Condition Variable을 활용할 것
• 확실하지 않을 때에는 반드시 작업에 앞서 Lock을 acquire하고 작업의 끝에 release할 것 (물론 이는 concurrency를 limit하여 속도를 저하시킨다. 때문에 처음에는 coarse한 lock에서 점차 finer-grained하게 만든다.)
• Condition Variable을 사용할 때 (wait, signal, broadcast)는 반드시 Lock을 쥐고서 사용할 것
• Condition Variable은 Memoryless한 것을 기억할 것 (아무도 wait하지 않을 때의 signal은 버려진다)
• Condition Variable에 의해 깨워진 쓰레드는 반드시 즉시 돌아가지는 않는다는 것
• 반드시 while loop 안에서 wait할 것
• 쓰레드가 끝나기를 기다릴 때 sleep 같은 함수 사용하지 말 것
• 일관된 구조를 사용할 것