3-2장. 락(Lock) - 1

여러 개의 명령어들을 원자적(atomic)으로 실행해보고 싶지만 병행성으로 인한 여러 쓰레드의 개입으로 인해(임계영역) 그렇게 할 수가 없었다. 여기서는 앞서 다룬 락(lock)을 이용하여 이 문제를 직접적으로 다루고자 한다. 프로그래머들은 소스 코드의 임계 영역을 락으로 둘러 그 임계 영역이 하나의 원자 단위 명령어인 것처럼 실행되도록 한다.

락 : 기본 개념

예를 위해 다음의 임계 영역이 있다고 하자. 공유 변수의 갱신이다.

balance = balance + 1;

그리고 락으로 임계 영역을 다음과 같이 감쌌다.

mutex mylock; // 전역 변수로 선언된 mylock
...
mylock.lock();
balance = balance + 1;
mylock.unlock();

락은 하나의 변수이므로 락을 사용하기 위해서는 락 객체(mylock)를 먼전 선언해야 한다. 락 객체는 락의 상태를 저장한다. 사용 가능 상태인 경우는 아직 락을 획득한 쓰레드가 없다는 뜻이고, 사용 중인 상태의 경우는 어느 한 쓰레드가 락을 획득하였고, 임계 영역을 실행 중이라는 뜻이다. 이 락 자료구조에 락을 보유한 쓰레드에 대한 정보나 락을 대기하는 쓰레드들에 대한 정보를 저장할 수도 있다. 물론, 이러한 정보는 락 사용자는 알 수 없다.

 

lock()의 의미

mutex::lock()를 호출한 쓰레드는 락의 획득을 시도한다. 아무도 락을 갖고 있지 않으면, 락을 획득한다. 그리고 임계영역에 진입한다.(이 쓰레드가 락을 소유했다 라고도 한다) 이렇게 한 쓰레드가 락을 획득하고 임계 영역에 진입하고 있으면 다른 쓰레드는 임계 영역의 진입이 막히고 멈춰있게 된다.

C++11 락 - mutex

mutex는 C++11에서 사용하는 기본 락 클래스이다. 쓰레드 간에 상호 배제(mutual exclusion) 기능을 제공한다. 상호 배제는 한 쓰레드가 임계 영역 내에 있다면 이 쓰레드의 동작이 끝날 때까지 다른 쓰레드가 임계 영역에 들어 올 수 없도록 제한한다고 해서 얻은 이름이다. 위 코드에서 lock()을 하기 전에 mutex 객체를 전역 변수로 선언하는 이유도 lock()을 사용하기 위해서이다.

 

위 코드에서 balance 외의 다른 변수를 보호해야 한다면 다른 락 객체를 사용해야 한다. 이는 곧 병행성 증가로 이어진다. 서로 다른 데이터와 자료 구조를 보호하기 위해 여러 락을 사용하여 한 번에 여러 쓰레드가 서로 다른 락으로 보호된 코드 내에 각자가 진입이 가능하도록 할 수 있다. 이를 세밀한(fine-grained) 락 사용 전략이라고 한다.(반대는 거친(coarse-grained) 락 사용 전략)

 

락의 구현

락의 동작은 대략 이해가 됐을 것이다. 그러면 어떻게 락을 만들까? 락을 만들기 위해서는 하드웨어와 운영체제의 도움을 받아야 한다. 또한 효율적인 락을 위해 low cost로 구현해야 한다.

 

락의 평가

어떤 락이든 만들기 전에 목표를 이해해야 하고 구현의 효율을 어떻게 평가할지 질문해야 한다. 락이 잘 동작하는지 평가하기 위해 먼저 기준을 정해야 한다. 

 

첫째는 상호 배제를 제대로 지원하는가이다. 가장 기본 역할이다. 기본적으로 락이 동작하여 임계 영역 내로 다수의 쓰레드가 진입을 막을 수 있는지 검사해야 한다.

 

둘째는 공정성(fairness)이다. 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가? 이것을 보는 다른 관점은 좀 더 극단적인 상황을 평가해 보는 것이다. 락을 전혀 얻지 못해 굶주리는 경우(기아 문제, Starvation)가 발생하는가? 

 

마지막 기준은 성능(performance)이다. 특히, 락 사용 시간적 오버헤드를 평가해야 한다. 경쟁이 전혀 없을 때의 성능, 단일 CPU상에서 경쟁할 때의 성능, 그리고 멀티 CPU상에서 경쟁할 때의 성능 이 세 가지를 고려해야 한다. 이런 서로 다른 상황 성능을 평가해야 다양한 락 기법들이 성능에 미치는 영향을 이해할 수가 있다.

 

인터럽트 제어

초창기 단일 프로세스 시스템(싱글 CPU, 코어)에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용했었다. 코드는 다음과 같다.

void lock() 
{
    DisableInterrupts();
}

void unlock()
{
    EnableInterrupts();
}

임계 영역에 진입하기 전에 특별한 하드웨어 명령어를 사용하여 인터럽트를 막는다면 임계 영역 내의 코드에서는 인터럽트가 발생할 수 없기 때문에 원자적으로 실행될 수 있다. 모든 동작이 끝난 후에 다시 명령어를 사용하여 인터럽트를 사용 가능하도록 해 프로그램이 이전처럼 진행할 수 있도록 한다.

 

이 방법의 주요 장점은 단순함이다. 인터럽트가 발생하지 않으면, 코드가 실행 중에 다른 쓰레드가 중간에 끼어들지 않는다는 것을 보장할 수 있다.

 

하지만 이 방법은 단점이 많다. 먼저 인터럽트 활성 / 비활성화하는 큰 권한(특권 연산)을 응용 프로그램에게 줘야 한다. 이는 악용의 여지가 있다. 탐욕적(Greedy) 기법을 사용한 프로그램이 시작과 동시에 lock()을 호출하여 프로세서를 독점하여 사용할 수도 있다. 더한 경우에는 악의적인 프로그램이 lock()을 호출하고 무한 반복문에 들어갈 수도 있다. 

 

두 번째 단점은 멀티프로세서(멀티 CPU, 코어)에서는 적용을 할 수가 없다는 것이다. 여러 쓰레드가 여러 CPU에서 실행 중이라면 각 쓰레드가 동일한 임계 영역을 진입하려고 시도할 수 있다. 이때 특정 프로세서에서 인터럽트 비활성화는 다른 프로세서에서 실행 중인 프로그램에는 전혀 영향을 주지 않는다. 결과적으로는 임계영역에 진입할 수 있게 된다는 말이다. 지금은 멀티 프로세서가 흔하게 사용되고 있기 때문에 해결법은 더 정교해야 한다.

 

세 번째 단점은 장시간 동안 인터럽트를 중지시키는 것은 중요한 인터럽트의 시점을 놓칠 수 있다는 것이다. 때로는 시스템에 심각한 문제를 가져올 수 있다. 예를 들어 CPU가 저장 장치에서 읽기 요청을 마친 사실을 모르고 지나갔다고 해 보자. 운영체제는 이 읽기 결과를 기다리는 프로세스를  영영 깨울 수 없게 된다. 

 

마지막으로 이 방법은 현대 CPU에서 느리게 실행된다. 그렇게 때문에 비효율적이다.

 

위의 이유로 상호 배제를 위하여 인터럽트를 비활성화하는 것은 제한된 범위에서만 사용되어야 한다. 예를 들어 운영체제 내부 자료 구조에 대한 원자적 연산을 위해 인터럽트를 비활성화 시킬 수 있다. 운영체제 내부에서는 신뢰라는 문제가 사라지기 때문에 인터럽트를 비활성화하더라도 용인할 수 있다.

 

왜 하드웨어의 도움이 필요한가?

우선 다음 예제를 통해 SW적 시도를 해보자. flag를 이용하여 락의 획득 여부를 판단해본다.

class mutex
{
public:
    mutex() {flag = false;}
    void lock()
    {
        while(true == flag);
        flag = true;
    }
    void unlock()
    {
        flag = false;
    }
private:
    bool flag;
}

이 방식을 데커(Dekker) 알고리즘이라고 한다. 이 방법은 다음과 같은 문제점들이 있다.

 

쓰레드1이 unlock()했다는 것을 쓰레드2에서 알아야 하지만 이전의 flag 값을 레지스터로 가져왔고 갱신하지 않기 때문에 쓰레드2는 계속해서 대기한다. 이로 인해 상호 배제가 실패한다. 또한 while문에서 회전 대기(spin-waiting) CPU 시간을 소모해서 다른 쓰레드의 실행이 늦어지게 된다.

 

다른 SW적 시도들

- 피터슨 알고리즘

volatile int victim = 0;
volatile int flag[2] = {false, false};

Lock(int myID)
{
    int other = 1 - myID;
    flag[myID] = true;
    victim = myID;
    // 만약 내 쓰레드가 임계 영역에 들어왔고 다른 쓰레드에서 
    // Lock을 얻은 경우 스핀한다.
    while(flag[other] && victim == myID) {}
}

Unlock(int myID)
{
    flag[myID] = false;
}

피터슨 알고리즘은 공유 메모리를 사용하여 여러 개의 프로세스가 임계영역 내에서 문제가 생기지 않게 해준다. 이 알고리즘의 문제는 id가 0과 1 두 가지이기 때문에 2개의 쓰레드에서만 동작한다. 

 

- 빵집 알고리즘

int choosing[n], turn[n];
// 프로세스 i의 코드: 0 <= i < n;

lock(int i)
{
    choosing[i] = 1;
    turn[i] = max(turn[0], turn[1], ..., turn[n-1]) + 1; // 번호표 부여
    choosing[i] = 0;
    for(int j = 0; j < n; ++j)
    {
        if(j != i)
        {
            // 번호표 부여중인경우 대기
            while(0 != choosing[i]);
            // 번호표를 부여 받았고 번호표 순위 우선순위가 낮을 경우 대기
            while(turn[j] != 0 && (turn[j], j) < (turn[i], i)); 
        }
    }
}

unlock(int i)
{
    turn[i] = 0; // 번호표 취소
}

빵집 알고리즘은 위의 데커와 피터슨 알고리즘의 단점을 보완한 알고리즘이다. 각 쓰레드는 임계영역 접근시 번호를 부여받고 낮은 번호가 먼저 온 것부터 수행한다. 하지만 번호를 부여받았다고 하더라도 한계 대기 조건을 만족하지 않는다면 대기해야 한다. 이 방식은 n개의 쓰레드에서 동작한다. 

 

SW적으로 임계영역을 해결할 여러 알고리즘들을 살펴보았다. 이렇게 보완되었음에도 불구하고 왜 하드웨어의 도움이 필요한 것일까? 그것은 SW의 문제에 있다.

 

우선 첫 번째는 제한된 프로세스의 개수이다. 빵집 알고리즘은 n개의 쓰레드를 쓸 수 있지만 데커와 피터슨은 2개의 쓰레드만 사용이 가능하다. 이는 요즘 쓰이는 멀티 CPU를 활용하기에는 턱없이 부족한 알고리즘들이다.

 

두 번째는 너무 복잡한 연산으로 인한 딜레이이다. 이 딜레이는 곧 병렬 처리 속도 저하로 이어진다. 코드는 효율적으로 보일지 몰라도 하드웨어와 속도를 비교해보면 그 차이가 매우 크다.

 

세 번째는 가장 치명적인 문제인데, 현대 CPU에서는 제대로 동작하지 않는다.(완화된 일관성 모델 때문에) 그렇기 때문에 추가적인 CPU 제어가 필요하다. 

 

따라서 우리는 하드웨어의 도움이 필요하다. 하드웨어를 이용한 락 구현을 다음 장에서 자세하게 알아보도록 하겠다.