[운영체제] 9. Semaphore

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

 

Semaphore

Semaphore는 lock과 마찬가지로 공유된 자원의 동시성 제어에 사용되는 기법이다.

semaphore에는 중요한 두 연산이 있다. sem_wait()=P()와 sem_post()=V()이다. 

wait()은 세마포어의 값을 감소시키고, post()는 세마포어의 값을 증가시킨다.

wait는 세마포어의 값이 음수면, 실행 중인 스레드를 대기(sleep) 상태로 전환하고, 양수면 실행시킨다. post는 일단 값을 증가시키고, 값이 0 이하면 sleep중인 스레드가 있다는 뜻이므로 sleep 스레드 중 하나를 깨운다.

#include <semaphore.h>
sem_t s;

sem_init(&s, 0, 1);

sem_init()의 첫번째 parameter는 세마포어 자료구조, 두번째는 프로세스 간 공유 여부(0이면 공유 X, 나머진 O), 세번째는 세마포어 값이다. OSTEP에서는 두번째 parameter를 0으로 고정하여 한 프로세스 내 스레드끼리만 세마포어를 공유할 것이다. 만약 세마포어 값이 음수라면, 그 절댓값이 sleep 중인 스레드 수라 할 수 있다.

 

Binary Semaphores (Locks)

 

set_T m;
sem_init (&m, 0, x);

sem_wait(&m);
// critical section here
sem_post(&m);

 

위처럼 binary semaphore는 critical section에 접근하기 전에 호출하는 방식으로 lock처럼 이용할 수 있다.

위에선 sem_init 시 초기값을 x라 했다. 지금은 x의 값을 1이라 가정하며, 이때의 흐름을 살펴보겠다.

 

 

먼저 single 스레드일 때 semaphore는 위와 같이 동작한다. wait/post를 호출할 때 세마포어 값의 연산이 수행되고, wait/post의 return에서 스레드를 sleep시키거나 실행시킨다는 점을 기억하자.

 

 

먼저 스레드 0에서 sem_wait()를 통해 바로 critical section에 접근하고 세마포어 값은 1 -1 = 0이 된다. 그 뒤 interrupt로 스레드 1이 sem_wait를 수행하면, (context switch)

0 -1 = -1로 값을 바꾸고 이는 음수이므로 스레드 1을 sleep시킨다. (context switch)

다시 스레드 0으로 돌아가 critical section의 작업을 끝내고 sem_post를 수행하면 세마포어 값이 -1+1 = 0이 되고 return으로 스레드 1을 깨운다. (context switch)

이제 스레드 1에서는 sem_wait의 return으로 세마포어 값이 음수가 아니기에 (=0임) 스레드 1을 그대로 실행시켜 critical section을 작업하고 post를 return하여 세마포어 값에 1을 더해 원래의 1로 반환하게 된다.

 

이러한 semaphore는 lock을 획득한 상태, lock을 해제한 상태 2가지만 존재하기에 binary semaphore라고 한다.

 

Semaphore as Condition Variables

 

Condition Variable이란 특정 조건을 만족하는 지를 체크하는 변수이자, 조건에 따른 스레드 간 실행 순서를 ordering하는 변수라 할 수 있다. semaphore의 paremeter를 조정하여 이 역할도 수행하게 할 수 있다.

sem_t s;

void *child(void *arg) {
    printf("child\n");
    sem_post(&s); // signal here: child is done
    return NULL;
}

int main(int argc, char *argv[]) {
    sem_init(&s, 0, X); // what should X be?
    printf("parent: begin\n");
    pthread_t c;
    pthread_create(&c, NULL, child, NULL);
    sem_wait(&s); // wait here for child
    printf("parent: end\n");
    return 0;
}

위 코드는 항상 parent가 시작된 후 child가 실행되고 그 뒤 parent가 끝나는 순서로 동작한다.

이는 세마포어를 활용한 스레드 간 ordering 덕분이다.

부모 thread가 자식 스레드를 만든 뒤 sem_wait()을 통해 sleep하고, 그 뒤 자식 스레드가 sem_post()로 부모 스레드를 깨우는 방식이다.

이렇게 동작하려면 위 코드 sem_init()의 parameter X값이 0이어야 한다.

X가 0일 때 가능한 두 케이스를 살펴보자.

1. pthread를 만들고 자식스레드에서 sem_post()가 먼저 실행되면, 자식 스레드가 semaphore 값에 1을 더해 1로 만들고 context switch하고, 부모 스레드에서 남은 sem_wait를 실행하면 semaphore가 1-1 = 0이기에 그냥 실행돼서 원하는 순서로 작동한다. state는 아래와 같다.

2. 자식 스레드보다 부모 스레드의 sem_wait()이 먼저 수행돼도,  세마포어의 값이 0-1= -1이므로 부모 스레드는 sleep하고 자식 스레드가 수행된다. 자식 스레드의 작업이 끝나면 sem_post()로 세마포어 값이 0으로 돌아오고 부모 스레드에게 cpu를 넘긴다. 그 뒤 부모 스레드에서 남은 sem_wait의 return을 수행했을 때 세마포어 값은 0이므로 정상 작동한다.

위같은 방법을 통해 스레드 간 순서를 제어할 수 있다. state는 아래와 같다.

 

The Producer / Consumer Problem

 

생산자는 데이터를 만들고 buffer에 넣고, 소비자는 buffer에서 데이터를 꺼내 소비한다.

이 공유하는 buffer와 buffer size인 count 변수가 synchronized access할 수 있는 critical section이다. bounded-buffer problem이라고도 하는데, buffer에 들어가는 데이터가 한정되있어서 그렇게 부른다고 한다.

먼저 일반적인 코드를 봐보자. put()은 버퍼의 값을 변화시키고 get()은 버퍼의 값을 반환한다.  MAX는 버퍼의 size다.

int buffer[MAX];
int fill = 0;
int use = 0;

void put(int value) {
    buffer[fill] = value; // line f1
    fill = (fill + 1) % MAX; // line f2
}

int get() {
    int tmp = buffer[use]; // line g1
    use = (use + 1) % MAX; // line g2
    return tmp;
}

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        put(i);
    }
}

void *consumer(void *arg) {
    int i, tmp = 0;
    while (tmp != -1) {
        tmp = get();
        printf("%d\n", tmp);
    }
}

buffer size=MAX=5라고 하자. 코드를 위처럼 짠다면, producer가 5개 이상의 value를 buffer에 넣을 때

buffer가 가득차면 overwrite하게 된다. 이를 방지하기 위해 full / empty condition을 semaphore로 만들 수 있다.

sem_t empty;
sem_t full;

void *producer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    sem_wait(&empty); // line P1
    put(i); // line P2
    sem_post(&full); // line P3
  }
}

void *consumer(void *arg) {
  int i, tmp = 0;
  while (tmp != -1) {
    sem_wait(&full); // line C1
    tmp = get(); // line C2
    sem_post(&empty); // line C3
    printf("%d\n", tmp);
  }
}

int main(int argc, char *argv[]) {
	// ...
    sem_init(&empty, 0, MAX);
    sem_init(&full, 0, 0);
    // ...
}

이렇게 한다면, producer가 6번째 value를 buffer에 넣을 때 sem_wait(&empty)가 -1이 되어 sleep할 것이다. producer는 consumer가 sem_post(&empty)를 0으로 만들 때까지 sleep한다.

 

하지만 여러명의 producer와 consumer가 있으면 다른 문제가 발생한다.

MAX가 1보다 클 때, put(),get()의 fill과 use에서 race condition이 발생한다.

예를들면, producer1 스레드에서 위 코드의 line f1에서 버퍼에 값을 넣고 line f2가 실행되기 전 producer2 스레드로 context switch가 발생한다면 fill 변수가 업데이트되지 않아서 값이 overwrite될 것이다.

이는 mutual exclusion을 고려하지 않았기 때문에 발생하며, critical section에 접근하기 전에 binary semaphore로 lock을 추가하면 해결할 수 있다. 여기서 매우 중요한 것은 lock을 어디에 거느냐이다.

 

 

Lock을 이렇게 걸면, (1)comsumer의 mutex가 0으로 변하고 (2)consumer는 sem_wait(&full)로 sleep하고 (3)producer의 mutex 값은 0에서 -1로 변해서 sleep한다. 즉 아무도 깨워줄 사람이 없는 deadlock 상태가 발생한다.

이를 해결하기 위해선 아래와 같이 mutex의 코드 순서를 바꿔 lock의 범위를 줄여주면 된다.

 

Reader-Writer Locks

 

Reader는 데이터를 읽고 Writer는 데이터를 수정한다.

Writer는 데이터를 수정하기 때문에 critical section이 발생하고, Writer가 수정하는 동안에는 Reader도 접근해선 안된다.

반대로 말하자면 Writer가 실행되고 있지 않다면 Reader는 여러 스레드가 있어도 된다.

 

rule을 짜보자면, 1. writer는 무조건 혼자 writer lock을 가져야 하며

2. reader가 read lock을 일단 가진다면, 많은 reader가 read lock을 가져도 된다. writer는 reader가 모두 read할동안 기다려야 한다. 코드는 아래와 같다.

typedef struct _rwlock_t {
    sem_t lock; // binary semaphore (basic lock)
    sem_t writelock; // used to allow ONE writer or MANY readers
    int readers; // count of readers reading in critical section
} rwlock_t;

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

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1)
        sem_wait(&rw->writelock); // first reader acquires writelock
    sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0)
        sem_post(&rw->writelock); // last reader releases writelock
    sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
}

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

 

처음 세마포어를 초기화하는 sem_init에서 sem_init(lock, )은 reader, sem_init(writelock, )은 writer를 위한 세마포어다,

read lock을 획득하는 rwlock_acquire_readlock()에서 reader를 1증가시킨 뒤 reader가 1명이면 writelock도 획득한다. 

read lock을 해제하는 rwlock_release_readlock()에서는 reader 스레드가 하나도 없을 때 post(writelock)으로 writer 스레드를 깨운다. 여기서 Fairness 문제가 생긴다. reader가 0이 되는 순간이여야만 writer가 lock을 획득하여 깨어날 수 있는 starvation이 발생한다.

 

The Dining Philosophers

 

둥근 식탁에 철학자들이 둘러 앉아있다고 가정하자.

철학자들 사이엔 포크가 있고, 철학자가 생각을 하다 식탁에 있는 음식을 먹을 땐 자기 양쪽의 두 포크를 사용해야 한다.

Key challenges는 아래와 같다.

- No deadlock

- No philosopher starves

- Concurrency should be high

 

철학자의 basic loop를 코드로 살펴보자.

while (1) {
    think();
    get_forks(p);
    eat();
    put_forks(p);
}

//helper function
int left(int p) {return p;}
int right(int p) {return (p+1) % 5;} // 철학자가 5명이라고 가정

포크는 공유자원이며, 한 시점에 한 명씩 포크에 접근해야 하기에 포크마다 세마포어가 존재해야 한다.

철학자가 왼쪽 포크에 접근할 땐 left(p), 오른쪽은 right(p)를 사용한다.

포크(공유자원)을 얻는 세마포어(lock)은 아래 코드처럼 구현해보자.

void get_forks(int p) {
    sem_wait(&forks[left(p)]);
    sem_wait(&forks[right(p)]);
}
void put_forks(int p) {
    sem_post(&forks[left(p)]);
    sem_post(&forks[right(p)]);
}

이때, 모든 철학자가 음식을 먹으려고 자신의 왼쪽 포크를 집으면, 모든 철학자가 오른쪽 포크를 기다리는 deadlock이 발생한다. 이러한 문제를 해결하려면, 철학자 한명에게 오른쪽을 먼저 잡도록 rule을 바꿔주면 된다.

그렇게되면 한명의 철학자는 fork를 기다리며 sleep하게 되고, 그동안 다른 철학자가 식사를 하며 lock을 소유하는 cycle이 생긴다.