3-8장. 병행성 관련 오류

수년 동안 병행성 관련 오류 해결을 위해 연구자들이 엄청난 시간과 노력을 들였다. 대부분의 초기 연구는 교착 상태(deadlock)에 초점이 맞추어져 있었다. 최근 연구들은 다른 종류의 병행성 버그들을 다루고 있다. 실제 프로그램에서 발견된 사례를 중심으로 어떤 오류가 있는지를 살펴보고자 한다.

 

오류의 종류

첫 번째 질문은 이것이다 : 복잡한 병행 프로그램에서 발생하는 병행성 오류들은 어떤 것들이 있는가? 이 질문에 대한 답을 구하는 것은 어렵지만, 다행히 다른 사람들이 이미 비슷한 작업을 해놓았다. 실제 상황에서 어떤 종류의 오류들이 발생하는지 이해하기 위해 그들은 많이 사용되는 병행 프로그램들을 자세히 분석하였다. 

 

이 연구는 대표적인 오픈소스 프로그램 4개에 집중하였다. 유명한 DBMS(데이터 베이스 관리 시스템)인 MySQL, 웹 서버로 잘 알려진 Apache, 유명한 웹 브라우저인 Mozilla, 그리고 실제 사람들이 사용하고 있는 MS 오피스 모음인 OpenOffice를 분석하였다. 다음 그림은 위 4개의 프로그램에 대한 오류 통계이다.

 

총 105개의 오류가 있고 대부분의 오류는 교착 상태와 무관한 오류였다. 나머지 31개의 오류들은 교착 상태 관련 오류였다. 이제 이런 종류의 오류(비 교착 상태와 교착 상태)들에 대해서 좀 더 자세히 알아보도록 하겠다. 

 

비 교착 상태 오류

위 표에서도 볼 수 있었듯이 비 교착 상태 오류가 병행성 관련 오류의 과반수를 차지한다. 그것들은 어떤 종류이며, 어떻게 발생하는 것이고, 어떻게 해결할 수 있는 것일까? 비 교착 상태 오류의 분류 중 대표적인 두 종류의 오류인 원자성 위반(atomicity violation) 오류와 순서 위반(order violation) 오류를 살펴보겠다.

 

원자성 위반 오류

원자성 위반 오류는 다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성(serializability)이 지켜지지 않아 생기는 것이다.  다음 MySQL의 예제 코드를 살펴보자.

Thread1::
if(thd->proc_info)
{
   ...
   fputs(thd->proc_info, ...);
   ...
}

Thread2::
thd->proc_info = NULL;

이 예제에서 thd 자료 구조의 proc_info 필드를 두 개의 쓰레드가 접근한다. 첫 번째 쓰레드는 그 값이 NULL인지 검사하고 값을 출력한다. 두 번째 쓰레드는 값을 NULL로 설정한다. 첫 번째 쓰레드가 검사를 완료한 후 fputs를 호출하기 전에 인터럽트로 인해 두 번째 쓰레드가 그 사이에 실행될 수 있다. 두 번째 쓰레드가 실행되면 필드의 값을 NULL로 설정하기 때문에 fputs 함수는 NULL 포인터 역참조를 하게 되어 프로그램이 크래시 날것이다. 코드의 일부에 원자성이 요구되었으나, 실행 시에 그 원자성이 위반되었다. 

 

해결법은 의외로 간단하다. 공유 변수는 락을 걸면 된다. 다음은 오류를 수정한 코드이다.

Thread1::
thd_lock.lock();
if(thd->proc_info)
{
   ...
   fputs(thd->proc_info, ...);
   ...
}
thd_lock.unlock();

Thread2::
thd_lock.lock();
thd->proc_info = NULL;
thd_lock.unlock();

 

순서 위반 오류

순서 위반 오류는 메모리 참조 간의 순서가 바뀌어서 생기는 것이다. 다음 코드를 살펴보자.

Thread1::
void init()
{
    mThread = PR_CreateThread(mMain, ...);
}

Thread2::
void mMain(...) 
{
    mState = mThread->State;
}

이 코드에서 쓰레드 2의 코드는 mThread 변수가 이미 초기화가 된 것을 가정하고 있다. 만약 쓰레드 1이 먼저 실행되지 않았다면 쓰레드 2는 NULL 포인터를 사용하기 때문에 크래시 될 것이다.

 

쓰레드 1이 항상 쓰레드 2보다 먼저 실행되어야 하지만, 프로그램에서 이를 강제하지 않았다. 그렇기 때문에 이 오류의 해결을 위해서는 순서를 강제해야 한다. 이러한 종류의 동기화는 컨디션 변수가 잘 맞는다. 다음은 오류를 수정한 코드이다.

mutex mtLock;
condition_variable mtCond;
int mtInit = 0;

Thread 1::
void init()
{
    ...
    mThread = PR_CreateThread(mMain, ...);
    mtLock.lock();
    mtInit = 1;
    mtCond.notify_all();
    mtLock.unlock();
    ...
}

Thread 2::
void mMain(...) 
{
    ...
    {
        unique_lock<mutex> lk {mtLock};
        while(mtInit == 0) mtCond.wait(lk);
    }
    mState = mThread->State;
    ...
}

수정된 코드에서는 mtLock이라는 락, 그에 대한 컨디션 변수 mtCond, 그리고 상태 변수 mtInit을 추가하였다. 초기화 코드가 실행되면 mtInit의 상태를 1로 설정하고 초기화를 완료했다고 시그널을 발생시킨다. 만약 쓰레드 2가 이 시점 전에 실행된다면 상태가 변경되기를 대기한다. 이후 다시 쓰레드 2가 실행되면 상태 값 초기화 여부를 검사한 후, 올바르게 계속 진행한다. 

 

교착 상태 오류

복잡한 락 프로토콜을 사용하는 다수의 병행 시스템에서는 교착 상태라는 고전적 문제가 발생한다. 예를 들어 락 L1을 갖고 있는 쓰레드 1이 또 다른 락 L2를 기다리는 상황에서 불행하게도 락 L2를 갖고 있는 쓰레드 2가 락 L1이 해제되기를 기다리고 있을 때 교착 상태가 발생한다. 교착 상태가 발생할 가능성이 있는 코드를 다음과 같이 나타내었다.

 

이 코드에서는 교착 상태가 발생할 수 있다. 쓰레드 1이 락 L1을 획득하고 난 후 문맥 교환이 발생하여 쓰레드 2가 실행한다. 그때, 쓰레드 2가 락 L2를 획득하고 락 L1을 획득하려고 시도한다. 그러면 교착 상태가 발생한다. 각 쓰레드가 상대방이 소유하고 있는 락을 대기하고 있기 때문에 누구도 실행할 수 없게 된다. 그림으로 표현하면 다음과 같다.

 

그래프에서 사이클(cycle)의 존재는 교착 상태 발생 가능성을 의미한다. 이 그림이 문제를 명확히 해줄 것이다. 교착 상태를 방지하기 위해서는 어떻게 코드를 작성해야 할까?

 

교착 상태는 왜 발생하는가?

앞서 본 간단한 교착 상태의 상황은 손쉽게 막을 수 있겠다고 생각할 수 있다. 예를 들어 쓰레드 1과 2가 락을 같은 순서로 획득한다면 교착 상태는 절대 발생하지 않는다. 그러면 교착 상태는 왜 발생하는가?

 

첫 번째 이유는 코드가 많아지면서 구성 요소 간에 복잡한 의존성(complex dependencies)이 발생하기 때문이다. 운영체제를 생각해 보자. 가상 메모리 시스템이 디스크 블록을 가져오기 위해 파일 시스템을 접근하는 경우가 있다. 파일 시스템은 디스크 블록을 메모리에 탑재하기 위해 메모리 페이지를 확보해야 하고, 이를 위해 가상 메모리 시스템에 접근한다. 코드 상에서 자연스럽게 존재하는 순환 의존성이 교착 상태를 야기시키는 것을 방지하기 위해서 대형 시스템의 락 사용 전략과 설계는 매우 신중해야 한다.

 

두 번째 이유는 캡슐화(encapsulation)의 성질 때문이다.(캡슐화 => 상세 구현은 숨기고 모듈 방식으로 쉽게 프로그램을 작성하도록 하는 것) 이러한 모듈화와 락은 잘 조화되지 않는다. 예를 들어 자바 벡터 클래스의 AddAll() 메서드를 살펴보자. 다음과 같은 형식으로 호출될 수 있다.

 

이 메소드는 멀티 쓰레드에 안전해야 하기 때문에 내부적으로는 v1에 더해지는 벡터뿐만 아니라 인자로 전달되는 v2에 대한 락도 같이 획득해야 한다. 이 루틴은 v2의 내용을 v1에 더하기 위해서 임의의 순서로 말한 락들을 획득하는데, 여기서는 v1을 먼저 획득하고 v2를 획득한다고 하자. 어떤 쓰레드가 v2.AddAll(v1)을 거의 동시에 호출하면 교착 상태 발생 가능성이 있다. 이 모든 상황은 호출한 프로그램 모르게 진행된다.

 

교착 상태 발생 조건

교착 상태가 발생하기 위해서는 네 가지 조건이 충족되어야 한다.

 

이 네가지 조건 중 하나라도 만족시키지 않는다면 교착 상태는 발생하지 않는다. 먼저 교착 상태를 예방할 수 있는 기술들을 먼저 살펴보자. 각 전략들은 위의 조건들이 발생하는 것을 막는다. 그리고 그 전략이 교착 상태를 다루는 방법 중 하나이다.

 

교착상태의 예방

 

1. 순환 대기(Circular Wait) 예방

아마도 가장 실용적인 교착 상태 예방 기법은 순환 대기가 절대 발생하지 않도록 락 코드를 작성하는 것이다. 가장 간단한 방법은 락을 획득하는 전체 순서(total ordering)를 정하는 것이다. L1과 L2라는 두개의 락만이 시스템에 존재한다면 L1을 무조건 L2 전에 획득하도록 하면 교착 상태를 피할 수 있다. 이 순서를 따르면 순환 대기는 발생하지 않고 따라서 교착 상태도 발생하지 않는다.

 

2. 점유 및 대기(Hold-and-Wait) 예방

점유 및 대기는 원자적으로 모든 락을 단번에 획득하도록 하면 예방할 수 있다. 다음 코드를 보도록 하자.

 

제일 먼저 prevention 락을 획득하여, 락을 획득하는 과정 중에 쓰레드의 문맥 교환이 일어나는 것을 방지하고, 결과적으로 교착 상태 발생 가능성을 차단한다. 쓰레드가 락을 획득하려면 전역 prevention 락을 먼저 획득해야 한다. 다른 쓰레드가 L1과 L2를 다른 순서로 획득하려고 한다 하더라도 괜찮다. 왜냐하면 그 쓰레드가 prevention 락을 이미 획득한 후에 나머지 락을 요청하기 때문이다.

 

하지만 이 해결법은 문제점이 많다. 필요한 락들을 정확히 파악해야 하고 그 락들을 미리 획득해야 하기 때문이다. 또한 미리 모든 락을 단번에 획득하기 때문에 병행성이 저하되는 문제도 있다.

 

3. 비선점(No Preemption) 예방

일반적으로 락을 해제하기 전까지는 락을 보유하고 있는 것으로 보기 때문에 여러 락을 획득하는 것에는 문제의 소지가 있다. 왜냐하면 락을 이미 보유하고 있는 채로 다른 락을 대기하기 때문이다. 많은 쓰레드 라이브러리들은 이러한 상황을 피할 수 있도록 유연한 인터페이스를 제공한다. 

 

trylock() 루틴의 경우 할 수 있으면 락을 얻은 후 true를 리턴하고, 그렇지 못하면 false를 리턴한다. trylock()을 이용하면 교착 상태 가능성이 없고 획득 순서에 영향을 받지 않는 락 획득 방법을 만들 수 있다.

 

다른 쓰레드가 같은 프로토콜을 사용하면서 락을 다른 순서로 획득하려고 해도 교착 상태는 발생하지 않는다. 그렇지만 무한반복(livelock)이라는 새로운 문제가 생긴다. 두 쓰레드가 같은 순서로 락을 요청하면서, 교착 상태에 빠지지는 않지만 실제 진척이 있는 것은 아니기 때문에 이름대로 무한반복인 상황이다. 무한반복 문제에 대한 해법도 존재한다. 예를 들면 반복문에 랜덤 딜레이(random delay)를 넣는것이다. 그러면 경쟁하는 쓰레드 간의 반복 간섭 확률을 줄일 수 있다.

 

4. 상호 배제(Mutual Exclusion) 예방

마지막 예방 기법은 상호 배제 자체를 없애는 방법이다. 이를 위해 대기 없는(wait-free) 자료 구조가 고안되었다. 명시적 락이 필요 없는 강력한 하드웨어 명령어(원자적 명령어)를 사용하여 자료 구조를 만들면 된다는 것이다. 이 방식을 이용하면 락이 필요 없는 멀티쓰레드 자료구조를 제작할 수 있게 된다.

 

CompareAndSwap을 이용하여 어떠한 값의 원자적인 덧셈을 구현하면 다음과 같다.

 

락을 획득하여 값을 갱신하고 락을 해제하는 대신, CompareAndSwap 명령어를 사용하여 값에 새로운 값을 갱신하도록 반복적으로 시도한다. 

 

다음은 리스트 삽입 예제 코드와 그것을 락과 CompareAndSwap 명령어를 사용하여 경쟁 조건을 완화한 코드이다.

 

 

스케줄링으로 교착 상태 회피하기

어떤 시나리오에서는 교착 상태를 예방하는 대신 회피하는 것이 더 유용할 때가 있다. 회피하기 위해서는 실행 중인 여러 쓰레드가 어떤 락을 획득하게 될 것인지에 대해 전반적으로 파악하고 있어야 하며 그것을 바탕으로 쓰레드들을 스케줄링하여 교착상태가 발생하지 않도록 그때그때 보장한다.

 

예를 들어 쓰레드 네 개가 프로세서 두 개에서 스케줄링된다고 해 보자. 그리고 추가로 쓰레드 1(T1)이 L1과 L2 락을, T2도 L1과 L2락을, T3은 L2를 필요로 하고, T4는 락을 필요로 하지 않는다고 가정하자. 쓰레드들의 락 요청에 대한 정보를 다음과 같이 표로 정리해 볼 수 있다.

 

똑똑한 스케줄러라면 T1과 T2가 동시에 실행되지만 않는다면 교착 상태가 절대로 발생하지 않도록 할 수 있다. 그와 같이 스케줄링된 예는 다음과 같다.

 

또 다른 예를 살펴보자. 이번에는 다음의 표에서 나타난 것과 같이 동일한 자원에 대해 경쟁이 심해졌다고 해 보자.

 

쓰레드 T1, T2, T3이 실행 중 어느 시점에 모두 L1과 L2 락을 획득하는 경우를 예로 들어보자. 그런 경우 교착 상태가 절대로 발생하지 않도록 하는 가능한 스케줄링은 다음과 같다.

 

하지만 그림에서 볼 수 있듯 회피하는 방법을 사용하면 T1, T2, T3가 하나의 프로세서에서 실행된다. 결국 작업을 끝내기까지 상당히 오랜 시간이 소요된다. 병행이 가능할 수도 있겠지만, 교착 상태가 발생할 수 있기 때문에 그렇게 할 수 없으면, 어쩔 수 없이 성능 하락을 수반한다.

 

발견 및 복구

마지막 전략은 교착 상태 발생을 허용하고, 교착 상태를 발견하면 복구토록 하는 방법이다. 예를 들어 운영체제가 1년에 한 번 멈춘다고 했을 때 재부팅을 하고 다시 작업을 처리하는 식이다. 교착 상태가 아주 가끔 발생한다면 이런 방법도 꽤 유용하다.

 

많은 DB 시스템들이 교착 상태를 발견하고 회복하는 기술을 사용한다. 교착 상태 발견을 주기적으로 실행되며 자원 할당 그래프를 그려서 사이클이 생겼는지를 검사한다. 사이클이 발생하는 경우 시스템은 재부팅되어야 한다. 자료 구조에 대한 복잡한 복구가 필요할 경우, 사람이 직접 복구 작업을 수행할 수도 있다.