[Operating System] Semaphore

Semaphore란?

이전 포스팅에서 살펴본 CV와 이번에 살펴볼 semaphore는 모두 blocking 매커니즘으로 작동한다. 다시 말해서 현재 쓰레드가 진행 될 수 없는 상황이면 스스로를 run queue에서 제외 시키고(BLOCK 상태로 만들고) 다른 쓰레드에게 컨트롤을 넘긴다.

 

CV가 컨디션 만족 여부를 판단하는 변수에 해당한다면, semaphore는 wait와 post 함수를 통해 증감하는 정수 값을 가진 변수라고 할 수 있다.

 

int sem_wait(sem_t *s) 

• Semaphore의 값을 1 감소 시키고, 감소 이후의 값이 음수(<0)이면 0 이상의 값이 될 때까지 sleep한다.
• Semaphore의 값이 $-N$이라면 총 $N$개의 쓰레드가 자신의 차례를 기다리고 있다는 의미이다.

 

int sem_post(sem_t *s)

• Semaphore의 값을 증가시키고, 깨어나길 기다리는 쓰레드(run queue에 있는 쓰레드) 중 하나를 깨운다. (어떤 것을 스케줄링할지는 스케줄러에게 달려있다.)

 

당연히 sem_wait와 sem_post는 atomic instruction이다.

 

Parent-Child Ordering (Semaphore로 Lock과 CV를 대체 가능)

아래의 pthread 예시 코드는 이전 포스팅에서 살펴 본 것으로 CV를 활용하여 parent-child 쓰레드 간에 순서를 조율한다.

 

int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void thr_exit() {
    Pthread_mutex_lock(&m);
    done = 1;
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

void thr_join() {
    Pthread_mutex_lock(&m);
    while (done == 0)
        Pthread_cond_wait(&c);
    Pthread_mutex_unlock(&m);
}

void *child(void *arg) {
    printf("I am a child.\n");
    thr_exit();
    return NULL;
}

 

위의 코드를 semaphore를 활용하여 구현하면 다음과 같다.

 

sem_t s;

void *child(void *arg) {
    printf("I am a child\n");
    sem_post(&s);
    return NULL;
}

int main(int argc, char *argv[]) {
    sem_init(&s, 0, X);		// X는 무엇이 되어야 할까?: 0
    printf("I am a parent\n");
    pthread_t c;
    pthread_create(c, NULL, child, NULL);
    sem_wait(&s);
    printf("Parent done\n");
    
    return 0;
}

 

주목할 점은 다음과 같다.

• sem_post는 혼자서 thr_exit 함수의 기능을 다 하였다. 즉, lock, state variable 변경, signal, unlock의 기능을 혼자서 다 하고 있다.
• sem_wait는 혼자서 thr_join 함수의 기능을 다혹 있다. 즉, lock, while loop을 통한 state variable 확인, wait, unlock의 기능을 혼자서 다 하고 있다.
• 위의 코드에서 sem_init을 할 때 semaphore의 초기값을 설정하는 X에는 0이 들어가야 한다고 주석이 달려있다. Semaphore는 처음에 초기화 된 값에 따라서 그 기능이 달라진다. 위의 상황에서는 parent 쓰레드가 child 쓰레드가 끝날 때까지 기다려야 하는 상황이다. 따라서 sem_wait(&s);를 하는 순간 s의 값이 -1이 되도록 하여 child에서 sem_post(&s);를 통해 s의 값을 0으로 만들 때까지 기다리게 한다.

 

Producer-Consumer Problem

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&empty);
        sem_wait(&mutex);
        put(i);
        sem_post(&mutex);
        sem_post(&full);
    }
}

void *consumer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&full);
        sem_wait(&mutex);
        get(i);
        sem_post(&mutex);
        sem_post(&empty);
    }
}

// semaphore의 초기화 값에 주목!
int main(int argc, char *argv[]) {
    sem_init(&empty, 0, MAX);
    sem_init(&full, 0, 0);
    sem_init(&mutex, 0, 1);
}

위의 코드에서 주목할 점은 다음과 같다.

• put과 get 함수는 공유 버퍼에 대해서 값을 읽고 쓰기 때문에 상호배제가 필요하다. 이 때 semaphore를 이용해서 mutex lock 구현이 가능하다. (semaphore의 값을 1로 초기화 하면 됨.)
• CV를 통해 producer-consumer 문제를 푼 걸 생각해보자. CV를 사용했을 땐 put과 get 연산 뿐 아니라 그 전후로 wait와 signal 하는 부분까지도 통째로 mutex lock으로 감싸져 있었다. 반면 semaphore를 사용한 위의 코드에선 오직 put과 get 연산만이 mutex lock으로 감싸져 있다. 이러한 차이가 발생하는 이유는 cond_wait에서는 sleep 하기전에 lock을 release하는 반면에, sem_wait에서는 decrement 이후 semaphore의 값이 음수면 곧 바로 잠들기 때문이다. 만약 sem_wait(&mutex)와 sem_post(&mutex)가 sem_wait(&empty)와 sem_wait(&full) 보다 바깥에 있었다면, lock을 잡은 상태에서 잠든 것이 되므로 데드락이 발생한다.

void *producer(void *arg) {
    for (int i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == MAX)
            Pthread_cond_wait(&empty, &mutex);
        put(i);
        Pthread_cond_signal(&fill);
        Pthread_mutex_unlock(&mutex);
    }
}

void *consumer(void *arg) {
    for (int i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == 0)
            Pthread_cond_wait(&fill, &mutex);
        int tmp = get(i);
        Pthread_cond_signal(&empty);
        Pthread_mutex_unlock(&mutex);
        printf("%d\n", tmp);
    }
}

 

 

Reader-Write Problem

Reader-write problem은 producer-consumer problem과 비슷해 보이지만 큰 차이점이 존재한다. Producer-consumer에서는 Producer와 consumer 둘 다 공유 버퍼에 값을 업데이트하는 writer에 해당하는 반면에, reader-write에서는 공유 버퍼의 값을 변화시키지 않고 읽기만 하는 reader와 공유 버퍼에 값을 업데이트하는 writer가 존재한다.

 

Reader는 공유 버퍼의 상태를 결코 변화시키지 않기 때문에 reader 간에 상호배제를 할 필요가 없다. 이는 곧 여러 개의 reader가 동시에 버퍼에서 값을 읽어도 아무런 문제가 없다는 뜻이다. (Writer 쓰레드는 당연히 한 번에 하나만 write 가능하다.) 

 

typedef struct _rwlock_t {
    sem_t lock;			// mutex lock
    sem_t writelock;	// 현재 write가 진행 중인가?
    int readers;		// critical section을 읽고 있는 reader 수
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
}

// reader가 공유 변수를 읽기 위해서 writer 쓰레드의 스케줄링을 막는다.
void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1)		// 첫 번째 reader라면
        sem_wait(&rw->writelock);		// writelock을 잡아서 write가 발생하지 않도록 한다.
    sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0)			// 마지막 reader의 read가 끝났으면 
        sem_post(&rw->writelock);	// writelock을 풀어서 writer가 새로운 값을 쓸 수 있게 한다.
    sem_post(&rw->lock);
}

// 하나의 Reader라도 read 중이면 새로운 값을 쓸 수가 없다.
void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock);
}

 

Write Starvation

위의 코드는 에러 없이 제대로 동작하긴 하지만 writer starvation의 위험이 크다. 만약 reader 쓰레드 여러 개가 간헐적으로 read를 하면서 writelock을 잡는 경우에 writer는 아주 오랫동안 lock을 잡지 못하게 된다.

 

이와 같은 write starvation을 해결하기 위해 writer는 이미 진행 중인 reader는 기다리지만 자신이 들어온 시점 이후에 들어온 reader 보다는 먼저 lock을 획득할 수 있어야 한다.