3-7장. 세마포어

세마포어는 정수 값을 갖는 객체로서 두 개의 루틴으로 조작할 수 있다. 이 두 개의 루틴은 각각 sem_wait()와 sem_post()이다. 세마포어는 초기값에 의해 동작이 결정되기 때문에, 사용하기 전 "제일 먼저" 값을 초기화해야 한다. 

class semaphore
{
    int value;
    semaphore() {value = 1;}
};

세마포어 객체 정수 값을 1로 초기화 한다.

 

이제 세마포어 내에 있는 sem_wait()와 sem_post() 메서드를 살펴보도록 하겠다. 이 둘은 원자적으로 실행된다. 레이스 컨디션 (쓰레드 간의 공유하는 값을 서로 쓰려고 하는 경쟁상태)이 발생할 수 있다는 사실은 걱정하지 말자. 그것은 곧 락과 컨디션 변수를 사용하게 될 것이다.

 

* sem_wait()

int semaphore::sema_wait()
{
    value 값을 하나 감소하고, value 값이 음수이면 대기
}

sem_wait()를 호출했을 때 value 값이 1 이상이면 즉시 리턴한다. 아니면 value 값이 1이상이 될 때까지 대기한다. 만약 value 값이 음수일 경우 그 값은 현재 대기 중인 쓰레드 개수와 같다. 일반적으로 세마포어 사용자는 이 값을 알 수 없다. 하지만, 이러한 성질을 알고 있는 것이 세마포어 작동을 이해하는데 도움이 된다. 

 

* sem_post()

int semaphore::sem_post()
{
    value의 값을 하나 증가시킨다.
    기다리고 있는 쓰레드가 있으면 하나를 깨운다.
}

sem_post() 메서드는 wait()과 다르게 대기하지 않는다. 값을 하나 증가시키며 기다리고 있는 쓰레드가 있으면 하나를 깨운다. 

 

이진 세마포어 (락)

이제 세마포어를 사용할 준비가 되었다. 우리가 처음으로 세마포어를 적용할 곳은 "락"이다. 다음 코드를 살펴보자.

class b_semaphore
{
    int value;
public:
    semaphore() {value = 1;};
    void sem_wait() {...};
    void sem_post() {...};
};

b_semaphore m;
m.sem_wait();
// 임계영역
m.sem_post();

sem_wait() / sem_post() 쌍으로 임계 영역 부분을 둘러싼 것을 볼 수 있다. 이것이 동작하기 위한 핵심은 세마포어 m의 초기 값이다. 왜 초기 value 값은 1이 되어야 할까?

이 부분을 분명히 하기 위해서 쓰레드가 두 개인 경우를 생각해보자. 첫 쓰레드(0)가 sem_wait()를 호출한다. 먼저 세마포어 값을 1 감소시켜 0으로 만든다. 쓰레드는 세마포어 값이 음수인 경우에만 대기한다. 세마포어 값이 0이므로 리턴하고 진행할 수 있다. 쓰레드 0은 이제 임계영역에 진입할 수 있다. 쓰레드 0이 임계 영역 내에 있을 때 다른 쓰레드가 락을 획득하려고 하지 않는다면, 이 쓰레드가 sem_post()를 불렀을 때 세마포어 값이 다시 1로 설정된다.(대기중인 쓰레드가 없으므로, 아무도 깨우지 않는다) 다음은 싱글코어에서의  과정을 나타낸 것이다.

 

쓰레드 0이 락을 획득한 상태에서 쓰레드 1이 sem_wait()를 호출하여 임계 영역을 진입하려고 시도하는 경우는 어떨까? 이 경우에는 쓰레드 1이 세마포어 value 값을 -1로 감소키시고 대기에 들어간다. 쓰레드 0이 다시 실행되면 sem_post()를 호출하고, 세마포어 값을 0 증가시킨다. 그리고 잠자던 쓰레드 1을 깨운다. 그러면 쓰레드 1이 락을 획득할 수 있게 된다. 쓰레드 1의 작업이 끝나면 세마포어의 값을 다시 증가시켜 1이 되도록 한다. 다음은 세마포어를 사용한 두 개의 쓰레드의 처리 과정을 그림으로 나타낸 것이다. 락은 두 개의 상태(사용 중, 사용 가능)만 가능하므로 이진 세마포어(binary semaphore)라고도 불린다.

 

하지만 세마포어는 C++11에는 없다.  왜냐하면 세마포어를 사용하는 것은 마치 GOTO문을 사용하는 것과 같기 때문이다. (스파게티 코드가 될 가능성이 있기 때문에 보통 암묵적으로 GOTO문을 사용하지 않는다)

Reader_Write 락

삽입 연산은 리스트의 상태를 변경하고, 검색은 자료 구조를 단순히 읽기만 한다. 삽입 연산이 없다는 보장만 있다면 다수의 검색 작업을 동시에 수행할 수 있다 이와 같은 경우를 위해 만들어진 락이 reader_write 락이다.  

 

코드는 다음과 같다.

#include <iostream>
#include <shared_mutex>
#include <thread>

class ThreadSafeCounter
{
private:
    std::shared_mutex mutex_;
    unsigned int value_ = 0;

public:
    ThreadSafeCounter() = default;


    unsigned int get()
    {
        // reader 락 획득
        mutex_.lock_shared();
        int tmp = value_;
        mutex_.unlock_shared();
        return tmp;
    }
    
    void increment()
    {
        // writer 락 획득
        mutex_.lock();
        value_++;
        mutex_.unlock();
    }
    
    void reset()
    {
        mutex_.lock();
        value_ = 0;
        mutex_.unlock();
    }
};

삽입 연산을 포함하는 writer락은 오직 하나의 쓰레드만 획득이 가능하다. 하지만 읽기만 하는 쓰레드는 read락을 획득하는데, 이 read락은 다른 쓰레드들도 획득이 가능하다. 만약 쓰려고 한다면 read락을 반납할때 까지 해당 쓰레드는 대기해야 한다. read락을 사용하기 위해서는 <shared_mutex>를 포함시켜줘야 한다.

 

하지만 이 락도 문제점이 몇 가지 존재한다. 첫 번째 문제점은 공정성 문제가 심각하다는 것이다. 상대적으로 writer 쓰레드가 불리하다. 쓰기를 하기 위해 reader락을 획득할 때까지 대기해야 하는 특성상 reader 스레드들이 writer 쓰레드의 실행을 계속 방해할 수 있고(실제로는 락 획득을 막기도 한다), 이는 곧 writer 쓰레드의 기아 현상이 발생하기 쉬워진다는 문제가 있다. 

 

두번째 문제점은 성능 문제이다. Reader, Writer 락은 일반 락보다는 실행 오버헤드가 큰 편이다. 또한 reader 락의 비율이 매우 높거나 임계 영역의 크기가 크지 않을 경우 오히려 성능이 일반 락보다 더 떨어질 수 있다.

 

식사하는 철학자

Dijkstra가 제시한 식사하는 철학자라는 유명한 문제가 있다. 너무나도 유명하기 때문에 모든 OS 교과서에 실려 있다. 우선 그림을 먼저 보자.

 

다음과 같이 5명의 "철학자"가 원탁에 앉아있다. 옆의 철학자와의 사이에는 젓가락 한 개가 놓여있다. (모두 5개) 그리고 철학자는 생각하거나 식사를 한다. 다만 생각할 때는 젓가락이 필요 없다. 식사를 위해서는 두 개의 젓가락을 집어야 한다. 자신 바로 옆(왼쪽/오른쪽) 젓가락만 집을 수 있다. 젓가락을 잡기 위한 경쟁과 그에 따른 동기화 문제가 병행 프로그래밍에서 다루려는 식사 하는 철학자 문제이다.  

 

주요 쟁점은 서로 교착상태가 없어야 하고, 아무도 굶어 죽어서는 안 되며, 병행성이 높아야 한다. 

while(1)
{
    think();
    getsticks();
    eat();
    getsticks();
}

int left(int p) {return p;}            // 철학자 p의 왼쪽 젓가락 번호
int right(int p) {return (p + 1) % 5;} // 철학자 p의 오른쪽 젓가락 번호

이 문제를 해결하기 위해서는 세마포어가 필요하다. 각 젓가락마다 한 개씩 총 다섯 개가 있고 sticks[5]로 정의한다.

 

다음과 같이 세마포어를 사용하였다.

void getsticks() 
{
    sem_wait(sticks[left(p)]);
    sem_wait(sticks[right(p)]);
}

void putsticks()
{
    sem_post(sticks[left(p)]);
    sem_post(sticks[right(p)]);
}

하지만 이것은 교착상태(deadlock)가 발생한다. 만약 각 철학자가 자신의 왼쪽 젓가락을, 다른 철학자가 자신의 오른쪽 젓가락을 잡을 수 있게 되기를 평생 기다리게 된다. 구체적으로 살펴보면, 철학자 0이 젓가락 0, 철학자 1이 젓가락 1 ,..., 그리고 철학자 4가 젓가락 4를 잡는다. 모든 젓가락은 누군가가 다 잡고 있기 때문에 모든 철학자는 다른 철학자가 갖고 있는 젓가락을 기다리며 대기하게 된다. 

 

이 문제에 대한 해답은 의존성을 제거하는 것이다. 최소한 하나의 철학자가 다른 순서로 젓가락을 집도록하면된다. 가장 높은 순번의 철학자 4가 젓가락을 다른 순서로 획득한다고 가정하자. 그 순서에 대한 코드는 다음과 같다.

void getsticks() 
{
    if(p == 4)
    {
        sem_wait(sticks[right(p)]);
        sem_wait(sticks[left(p)]);
    }
    else
    {
        sem_wait(sticks[left(p)]);
        sem_wait(sticks[right(p)]);
    }
}

이렇게 하면 모든 철학자가 젓가락 한 짝을 들고 다른 한짝을 기다리는 상황은 절대 일어날 수 없게 된다. 악순환의 고리가 깨진 것이다.

 

세마포어는 C++11에 없기 때문에 Sema라는 클래스 이름으로 우리만의 세마포어를 구현해 보자.

class Sema
{
    int m_value;
    conditional_variable m_cond;
    mutex m_lock;
    
public:
    Sema(int value) { m_value = value; }
    
    void Sema_wait()
    {
        unique_lock<mutex> lk {m_lock};
        m_lock.lock():
        while(m_value <= 0)
            m_cond.wait(lk);
        m_value--;
    }

    void Sema_post()
    {
        m_lock.lock();
        m_value++;
        m_cond.notify_all();
        m_lock.unlock();
    }
};

여기서 value값은 의미가 다르게 구현되어 있다. value 값은 0보다 작아지지 않고, 컨디션 변수를 사용해서 구현을 쉽게 한다.