(22.04.11 ~ 04.13) Concurrency Bugs

이제 이것만 공부하면 시험 범위는 끝이다. 기말 때는 중간 것도 전부 포함한단다..... 기아아아아악 살려주세요 교수님...

1. Deadlock 도입부

분명 시험 보고 나서 계획되어 있었던 걸로 아는데 왜 지금 다루는지는 모르겠지만 일단 시작하자. 동기화는 안 하는 것도 재앙적인 결과를 초래하지만 잘못 다루는 것 또한 상당히 골치 아픈 문제를 초래한다. 

 

만약 두 프로세스가 있을 때, 한 프로세스가 다른 프로세스가 잡고 있는 자원을 잡으려고 하고, 동시에 그 프로세스 또한 상대 프로세스가 들고 있는 자원을 잡으려고 하는 상황을 생각해보자. 이 때, 모든 프로세스는 서로의 자원을 잡으려고 무한정 대기하는 상태에 빠지게 된다. 이러한 상태를 교착 상태, 일명 deadlock 데드락이라고 한다. 참고로, deadlock과는 대비되는 livelock이라는 것 또한 존재한다. 데드락과는 달리 뭔가 진척은 일어나는 것처럼 보이지만, 실제로는 쓰레드들이 동시에 실행되면서 락의 해제와 획득을 반복적으로 하면서 실질적으로는 아무것도 하지 못하는 상태이다.

 

우리는 이제 이 교착 상태에 대한 것을 좀 더 자세히 살펴볼 것이다.

2. Deadlock 관련 용어 정리와 예시

교착 상태를 설명함에 있어, 자원이라고 두는 것은 주로 Lock이다. 일반적으로는 쓰레드가 필요한 작업을 수행하기 위해 필요한 모든 것 (CPU, 디스크 공간, 메모리) 를 포함한다. 자원은 Preemptable과 Non-preemptable로 구분할 수 있는데, 자원이 Preemptable하다는 것은 OS가 할당된 자원을 회수할 수 있다는 것이며, Non-preemptable하다는 것은 쓰레드가 반환 또는 종료하기 전에는 OS가 자원을 회수할 방법이 없다는 것을 의미한다. 여기서도 기아 상태가 나온다. 여기서의 기아는 쓰레드가 무한정 기다리는 상태를 의미한다.

 

이제 Deadlock이 발생하는 예시를 보자. 다음과 같이 굉장히 간단한 방법으로도 교착 상태를 만들 수 있다.

// thread A
lock1.acquire();
lock2.acquire();
lock2.release();
lock1.release();

// thread B
lock2.acquire();
lock1.acquire();
lock1.release();
lock2.release();

A가 Lock 1을 얻고, B로 넘어가서 B가 Lock 2를 얻는다. 다시 A로 넘어가서 A가 Lock 2를 얻으려고 할 때, A는 B가 Lock 2를 놓기까지 기다린다. 다시 B로 넘어가서 B가 Lock 1을 얻으려고 하면 Lock 1은 A가 들고 있기 때문에 B도 A가 Lock 1을 놓기까지 기다린다. 결국 두 쓰레드 모두 상대방이 놓을 리 없는 락을 무한정 기다리면서 진행이 되지 않는다. 이를 그림으로 만들면 이런 원형 대기 형태가 보인다.  

 

정말 단순하게 표현해놨지만 실제로도 이런 원형 대기 형태는 빈번하게 일어난다. 다만 저 락을 구하는 과정과 놓는 사이에 긴 코드가 위치해 있어 쉽게 알아채기 힘들 뿐이다.

3. Deadlock이 발생하기 위한 조건

Deadlock은 그럼 구체적으로 어떤 상황에 발생할까? 어떤 상황에 발생하는지 알아야 대처를 할테니 말이다. 교착 상태가 발생하기 위해서는 다음의 3가지 필수 조건이 모두 충족되어야 한다.

 

• 원형 대기 (Circular Waiting) : 주어진 쓰레드의 집합 내의 각 쓰레드는 다른 쓰레드가 가진 자원을 기다린다.
• 자원 든 상태로 대기 (Wait while holding) : 한 프로세스는 하나의 자원을 든 상태로 다른 자원을 기다린다.
• 비선점 자원 (No preemption) :  쓰레드가 자원을 가져가면, 쓰레드가 자발적으로 반환할 때까지 회수할 수 없다.

이 중 하나라도 미충족되면 교착 상태는 발생하지 않는다. 이 점에서 착안해 해당 조건이 절대로 충족되지 않도록 사전에 방지하는 pro-active 방법과, 해당 조건이 충족되어 교착 상태가 발생하면 이를 해소하기 위해 교정하는 reactive 방법으로 교착 상태를 해결할 수 있다. 물론 reactive 방법에서 취할 수 있는 행동은 굉장히 제한적이다. (restricted)

4. Deadlock 방지 (Avoid)

먼저 pro-active 방법으로, 교착 상태의 조건이 충족되지 않도록 만드는 법을 살펴보자.

4-1. Circular waiting 방지

Circular waiting이 일어나는 것을 막기 위해서는 항상 같은 순서대로 Lock을 acquire하는 것이 유효한 해법이다. 이러한 해법을 same order locking, 또는 lock ordering이라고 부른다. 이 해법을 위의 코드에 적용하면 이렇게 될 것이다.

// thread A
lock1.acquire();
lock2.acquire();
lock2.release();
lock1.release();

// thread B
lock1.acquire();
lock2.acquire();
lock2.release();
lock1.release();

락을 release에는 적용되지 않아도 크게 상관은 없으나 acquire의 순서는 중요하다. 다만 실전에서는 이를 사용하기 위해서는 시스템 내에서 사용되는 모든 락을 파악하고, 각 락이 걸리는 모든 순서를 파악해야 완벽하게 사용할 수 있다. 이를 이해하는 것이 어려울 수 있으나, 실전에서는 이를 타파하는 방법 또한 마련되어 있다. 락이라는 객체 또한 메모리 상에 위치하고 있을 것이므로, 고유한 주소를 가질 것이다. 이를 주소 순서대로 acquire하도록 만든다면, 일관적인 순서대로 락을 acquire하는 것이 가능하기에 이 방식이 널리 채택되고 있다. (order by address)

4-2. Wait while hold 방지

다음으로 wait while hold를 방지하려면 필요한 모든 락을 동시에 잡거나, 하나도 잡지 않고 모두 기다리도록 해야 한다. 즉, atomic하게 모든 락을 잡도록 해야 한다는 것인데, 이를 위해 락을 잡기 위한 락을 마련해서 해당 락을 잡은 쓰레드만 모든 락을 잡도록 한다. 이를 two phase locking이라고 한다. 개별적인 락을 잡기 위해서라고 해도 해당 마스터 락을 구해야만 잡을 수 있도록 하는 것이다.

 

물론 이 방식의 단점은 있다. 세밀한 락 조절이 어렵고, 모든 락을 잡는 시점에서야 마스터 락을 반환할 수 있기 때문에, 전체적으로 락을 걸어서 사용하는 것과 큰 차이가 없게 된다. 이 때문에 concurrency를 제한하여 성능상의 제약이 있을 수 밖에 없다. 단, 속도보다는 correctness가 더 중시되어야 하는 시스템에서는 해당 방식을 채용한다고 한다. 

4-3. No preemption 방지

마지막으로 프로세스가 놓을 때까지 자원을 회수할 수 없는 No preemption을 방지하는 방법이다. 이를 위해 다음의 trylock이란 것을 도입한다. 이는 필요한 락을 여러 번 잡으려고 하는 기법이다.

try_again:
    lock1.acquire();
    if (trylock2.acquire() != acquired)
        lock1.release();
        goto try_again;

해당 방식으로 lock1을 잡을 경우 lock1이 계속해서 release되면서 preempted될 가능성이 있기 때문에 No preemption을 방지하기 위해 사용된다. 이 방식의 문제는 livelock을 발생시켜 starvation을 유발할 수 있다는 것이다. 위의 경우, lock1을 계속 놓고 쥐는 것만 일어나면서 유의미한 진행이 일어나지 않을 수 있다. 해당 강의에서는 livelock의 해결은 자세히 살펴보지 않는다.

5. Deadlock 대응 (Recovery)

교착 상태가 발생했을 때는 크게 두 가지 방식의 대응이 가능하다. 프로세스 자체를 abort하는 것과, 자원을 회수하는 방식이다. 

5-1. Process Abort

교착상태에 들어간 모든 프로세스를 abort하거나, circular waiting이 깨지기까지 랜덤하게 프로세스를 하나씩 abort하는 방법이 있다. 앞선 방식의 경우, 모든 프로세스가 전부 다시 시작되면서 같은 상태에 빠져 이 모든 과정을 계속 반복하는 livelock에 빠질 문제가 있으며, 후자의 경우, 한 프로세스를 abort할 때마다 교착상태가 해소되었는지 검사하는 detection을 반복하여 수행할 필요가 있다.

5-2. Preempt Resource

운영체제에서 실행되고 있는 프로세스가 가진 자원을 강제로 회수하는 방법이다. 현재 교착 상태에 대한 정보를 갖고, 또는 가지지 않고 랜덤하게 자원을 회수할 수 있다. 이 방식을 채택할 경우, 어떤 프로세스가 지나치게 실행이 되지 않도록 하는 starvation 방지 대책이 필요하다. 또한 교착 상태가 해소된 이후에는 회수한 자원을 가지고 있던 프로세스에게 다시 돌려주는 과정이 필요하다.

6. Non-deadlock Concurrency bug

사실 이 마지막 부분은 동기화로 발생하는 문제라기 보다는 동기화 처리를 안해서 발생하는 실사례 분석 정도인 것 같다. 실제 구현을 하면서 가장 자주 실수하는 두 가지 유형을 분석한 것이라 보면 될 것이다. 관심이 있으면 주어진 논문을 보라고 한다.

6-1. Atomicity Violation

임의의 interleaving이 발생해 반드시 atomic하게 일어나야 하는 작업 사이에 다른 쓰레드가 실행이 되어 버그가 생기는 것이다. 예시에서는 문제가 확연히 보이지만 실제 구현된 수 천줄의 코드 사이에서는 발견하기 어려울 수 있기 때문에 가장 흔하게 유발되는 패턴이다. 이를 해결하기 위해 우리는 Lock을 배웠다.

6-2. Ordering Violation

쓰레드 간 실행 순서를 정해놨는데, 예상한 순서대로 쓰레드가 실행되지 않아 일어나야 하는 버그이다. 이를 해결하기 위해서는 Condition Variable이나 semaphore를 사용할 수 있다.