컨디션 변수와 세마포어

junto·2024년 3월 14일

operating system

목록 보기

5/13

앞선 포스팅 - 락(lock)의 필요성과 구현 마지막 부분에서 컨디션 변수의 개념을 약간 이나마 다뤘다. 여기에서 조금 더 자세하게 살펴본다. 세마포어를 알아보고, 세마포어로 락과 조건 변수를 만드는 게 가능한지와 락과 커디션 변수를 사용하여 세마포어처럼 사용할 수 있는지를 알아본다.

컨디션 변수(Condition Variable)

기존의 BusyWaiting은 조건이 참이 될 때까지 회전을 하며 기다리는 매우 비효율적인 방식이다.

while (done == 0) ;

조건이 참이 될 때까지 기다리기 위해 컨디션 변수를 활용할 수 있다. 컨디션 변수는 일종의 큐 자료구조로 쓰레드가 기다릴 수 있는 공간을 제공한다. 추가로 기본적인 연산 wait()와 signal()을 제공한다.
wait()는 쓰레드가 스스로를 잠재우기 위해서 호출한다. 락을 해제하고, 호출한 쓰레드를 재우는 역할을 한다. 다른 쓰레드가 시그널을 보내어 쓰레드가 깨어나면 wait()에서 리턴하기 전에 반드시 락을 재획득해야 한다. 이는 쓰레드가 스스로를 재우려고 할 때 생길 수 있는 경쟁 조건을 예방한다.
signal()은 쓰레드가 무엇인가를 변경했기 때문에 조건이 참이 되기를 기다리며 자는 쓰레드를 깨울 때 호출한다. 컨디션 변수를 사용한 아래 코드를 확인해보자.

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 *child(void *arg) {
	printf("child\n");
    thr_exit();
    return NULL;
}

void thr_join() {
	pthread_mutex_lock(&m);
    while (done == 0)
    	pthread_cond_wait(&c, &m);
    pthread_mutex_unlock(&m);
}

int main(int agrc, char *argv[]) {
	printf("parent: begin\n");
    pthread_t p;
    pthread_create(&p, NULL, child, NULL);
    thr_join();
    printf("parent: end\n");
    return 0;
}

구현 코드

부모 쓰레드가 자식 쓰레드를 생성하고, thr_join()을 호출하여 자식 쓰레드를 기다리는 경우가 있다. 부모 쓰레드가 락을 획득하고 자식이 끝났는지 검사(done)한 후 자식이 끝나지 않았으므로 wait()를 호출하여 스스로를 잠재운다. 자식 스레드가 추후에 실행되어 "child"라는 메시지를 출력하고 thr_exit()을 호출해서 부모 쓰레드를 깨운다.
자식 쓰레드가 생성되면서 즉시 실행되고 done 변수를 1로 설정하고 자는 쓰레드를 깨우기 위해 시그널을 보낸다. 하지만 쓰레드가 없기 때문에 단순히 리턴한다. 부모 쓰레드는 done이 1이기 때문에 대기 없이 바로 리턴한다.

1. 상태 변수(done)가 꼭 필요할까?

void thr_exit() {
	pthread_mutex_lock(&m);
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
}

void thr_join() {
	pthread_mutex_lock(&m);
    pthread_mutex_unlock(&m);
}

상태 변수가 없다면 자식 쓰레드가 생성되자마자 실행되는 경우(2)를 생각해보자. 자식 쓰레드가 부모를 깨우고나서 부모 쓰레드가 잠이 든다. 부모 쓰레드를 깨울 방법이 없다.

2. 시그널을 주거나 받을 때 락이 필요할까?

void thr_exit() {
	done = 1;
    pthread_cond_signal(&c);
}

void thr_join() {
	if (done == 0)
    	pthread_cond_wait(&c);
}

경쟁 조건이 발생한다. 부모 쓰레드가 0을 확인하고 나서 잠을 드려는 순간 interrupt가 걸려 자식 쓰레드가 done을 1로 바꾸고 종료되었다고 하자. 부모 쓰레드가 스스로를 재우는 순간 깨워줄 쓰레드가 없게 된다.
모든 경우에 꼭 락을 획득할 필요는 없지만 컨디션 변수를 사용할 때는 락을 획득한 후에 시그널을 보내는 것이 가장 간단하고 최선의 방법이다. wait()를 호출할 때 락을 획득하는 것은 단순히 권고사항이 아니라 wait() 정의상 반드시 해야 한다. 정리하면 항상 락을 걸자!

3. 꼭 while문을 사용해야 할까?

if (done == 0)
	pthread_cond_wait(&c, &m);

깨어난 쓰레드가 실제 실행되는 시점에도 그 상태가 유지된다는 보장은 할 수 없다. 이렇게 시그널을 정의하는 것을 Mesa semantic이라고 한다. if문으로 한다면 때로는 찾기 어려운 버그로 이어지기 때문에 항상 while문을 사용하자!

세마포어(Semaphore)

세마포어는 추상 자료형(Abstract Data Type, ADT)으로 사용할 수 있는 자원의 개수를 정수형으로 가지고, P(S)와 V(S) 연산을 가진다. POSIX 표준에서는 sem_wait()와 sem_post()를 제공한다.
세마포어는 초깃값에 그 동작이 결정되기 때문에 사용하기 전에 먼저 초기화해야 한다.

처음에 세마포어를 접할 때 헷갈릴 수 있는 점은 경쟁 조건을 예방하기 위해 공유자원에 배타적인 접근을 가능하게 하는 것인데, 세마포어의 개수만큼 공유자원에 접근하면 데이터 무결성이 해치지 않을까 생각할 수 있다. 상호 배제가 필요한 경우 mutex나 이진 세마포어를 사용하지만, 안전한 작업을 병렬로 처리하고 싶을 때(그저 데이터 접근하여 읽는 것)는 카운팅 세마포어를 사용하여 성능을 개선할 수 있는 것이다.

sem_t s;
sem_init(&s, 0, 1);

두 번째 인자로 0을 주는 이유는 같은 프로세스 내 쓰레드 간에 세마포어를 공유한다는 것을 의미한다. 세마포어의 값을 1로 초기화한다.

int sem_wait(sem_t *s) {
	세마포어의 값을 하나 감소시킨다.
    세마포어의 값이 음수라면 기다린다.
}

int sem_post(sem_t *s) {
	세마포어의 값을 하나 증가시킨다.
    하나 이상의 쓰레드가 기다리고 있다면, 하나를 깨운다.
}

sem_wait() 함수는 즉시 리턴(세마포어의 값이 1 이상)하거나 아니면 세마포어의 값이 1이상이 될 때까지 호출자를 대기시킨다.
sem_post() 함수는 대기하지 않는다. 세마포어 값을 증가시키고 대기 중인 쓰레드를 깨운다.
세마포어가 음수라면 그 값은 현재 대기 중인 쓰레드의 개수와 같다. 이 사실을 알고 있으면 세마포어의 동작을 이해하는 데 도움이 된다.

1. 이진 세마포어

sem_t m;
sem_init(&m, 0, 1);
sem_wait(&m);
// 임계영역
sem_post(&m);

이진 세마포어의 경우 초기값은 1이 되어야 한다. 두 개의 쓰레드가 있다고 해보자. 하나의 쓰레드가 진입했다면 1에서 0이 되고, 여기에서 또 다른 쓰레드가 임계 영역 진입을 시도한다면 음수가 되고, 해당 쓰레드는 잠에 든다. 처음 쓰레드가 자원을 반납한다면 세마포어 값이 0으로 되고, 잠들고 있던 쓰레드를 깨우게 된다.
위의 방식은 범용 세마포어 방식에 가깝고, 이진 세마포어는 더 단순하게 구현할 수 있다. (1이면 사용 가능, 0이면 사용 불가)

이진 세마포어와 뮤택스는 무슨 차이가 있을까?

뮤택스의 경우 락을 획득한 쓰레드만이 락을 해제할 수 있다. 하지만, 세마포어의 경우 자원 사용이 완료되면 해당 자원에 접근했던 쓰레드가 아니더라도 신호를 보낼 수 있다. A쓰레드가 특정 이벤트가 생기기 전까지 기다리고(sem_wait), 관리자 쓰레드가 이벤트가 발생했을 때 특정 쓰레드를 깨울 수 있기 때문이다(sem_post).

2. 컨디션 변수로서 세마포어

sem_t s;

void *child(void *arg) {
	printf("child\n");
    sem_post(&s); 		// 시그널 전달: 자식의 동작이 끝남
    return NULL;
}

int main(int argc, char *argv[]) {
	sem_init(&s, 0, X); // X의 값은?
    pthread_t c;
    pthread_create(c, NULL, child, NULL);
    sem_wait(&s);
    return 0;
}

어떻게 세마포어 변수를 이용해 컨디션 변수처럼 사용할 수 있을까? 대기 중인 쓰레드가 프로그램에서 어떤 조건이 만족될 때까지 대기해야 한다. 위의 코드는 아래와 같이 동작한다.

자식 프로세스 생성 후, 아직 자식 프로세스가 실행되지 않은 경우
부모 프로세스가 sem_wait()을 호출하기 전에 자식 프로세스의 실행이 종료된 경우

이를 위해 초기 세마포어 값을 어떻게 설정해야 할까?
0으로 설정한다.

1의 경우 자식 프로세스가 sem_post()을 실행하기 전에 부모가 sem_wait()을 호출한다. 부모 프로세스는 자식이 실행될 때까지 대기해야 한다. 따라서 wait()호출 전에 세마포어 값이 0보다 같거나 작아야 한다. 즉, 초기 세마포어 값은 0이다.

2의 경우 자식이 먼저 sem_post()를 호출하여 세마포어의 값을 0에서 1로 증가시킨다. 부모 프로세스가 sem_wait()를 호출하면 세마포어 값이 1인 것을 발견하고 이를 0으로 만들어 sem_wait()를 대기 없이 리턴한다.

3. 세마포어 구현(락과 컨디션 변수를 이용)

저수준 동기화 기법인 락과 컨디션 변수를 사용하여 세마포어를 만들 수 있다.


typedef struct __Zem_t {
	int value;
    pthread_cond_t cond;
    pthread_mutex_t lock;
} Zem_t;

void zem_init(zem_t *s, int value) {
	s->value = value;
    cond_init(&s->cond);
    mutex_init(&s->lock);
}

void zem_wait(zem_t *s) {
	mutex_lock(&s->lock);
    while (s->value <= 0)
    	cond_wait(&s->cond, &s->lock);
    s->value--;
    mutex_unlock(&s->lock);
}

void zem_post(zem_t *s) {
	mutex_lock(&s->lock);
    s->value++;
    cond_signal(&s->cond);
    mutex_unlock(&s->lock);
}

하나의 락과 하나의 컨디션 변수를 사용하고 세마포어의 값을 나타내는 상태 변수 하나를 사용한다. Dijkstra가 정의한 세마포어와 위의 코드와 가장 큰 차이점은 전자는 세마포어의 음수값이 대기 중인 쓰레드의 수를 나타냈지만, 후자는 이 값이 0보다 작을 수가 없다.
value가 0이하라면 사용할 수 있는 자원이 없으므로 해당 쓰레드는 사용할 수 있는 자원이 생길 때까지 잠이 든다.

고전적인 동기화 문제

1. 생산자 소비자 문제(Bounded-Buffer Problem)

여러 개의 생산자 쓰레드와 소비자 쓰레드가 있다. 생산자는 데이터를 만들어 버퍼에 넣고, 소비자는 버퍼에서 데이터를 꺼내서 사용한다. 그 둘 사이에는 유한 버퍼가 있고 이는 공유자원이다.

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

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

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

sem_t empty;
sem_t full;

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

void *consumer(void *arg) {
	int tmp = 0;
    while (tmp != -1) {
    	sem_wait(&full);
        tmp = get();
        sem_post(&empty);
    }
}

int main(void) {
	// ...
    sem_init(&empty, 0, MAX);	// MAX 버퍼는 비어 있는 상태로 시작
    sem_init(&full, 0, 0);		// 0이 가득 차 있는 상태
}

동작 과정을 살펴보자.
1. 소비자가 먼저 실행한다면, sem_wait(&full)을 호출한다. 변수 full의 값은 0으로 초기화되었기에 full의 값은 -1이 되고, 소비자는 대기한다. 생산자 쓰레드가 sem_post()를 호출해서 full 변수가 증가하기를 기다린다.
2. 생산자 쓰레드가 실행한다. sem_wait(&empty)을 호출한다. empty 변수가 1(MAX)로 설정되었기에 empty 변수는 감소하여 0이 되고 생산자가 데이터 값을 버퍼의 첫 번째 공간에 담는다. 생산자는 sem_post(&full)을 호출하여 세마포어의 full값을 -1에서 0으로 변경하고 소비자 쓰레드를 깨운다.

MAX의 값이 1보다 크고, 또한 생산자와 소비자 쓰레드들이 있다고 하면 경쟁 조건이 발생한다.
두 생산자가 put()을 거의 동시에 호출한다면 값이 덮어씌워지게 된다. 상호 배제를 추가한다.

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

void *consumer(void *arg) {
	int tmp = 0;
    while (tmp != -1) {
    	sem_wait(&mutex);
    	sem_wait(&full);
        tmp = get();
        sem_post(&empty);
       	sem_wait(&mutex);
    }
}

상호 배제는 해결한 거 같지만, 이번에는 교착 상태가 발생한다. 어디에서 발생할까?
소비자가 먼저 실행이 되었다. full값이 0이므로 -1로 바꾸고, 소비자는 대기한다. mutex를 가진 채로 말이다. 생산자는 mutex를 얻을 수 없다.

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

void *consumer(void *arg) {
	int tmp = 0;
    while (tmp != -1) {
       	sem_wait(&full);
    	sem_wait(&mutex);
        tmp = get();
        sem_wait(&mutex);
        sem_post(&empty);
    }
}

2. 읽기 쓰기 문제(Readers and Writers Problem)

삽입 연산이 아닌 읽기만 하는 연산은 다수의 작업을 동시에 수행할 수 있다. 이를 위해 만들어진 락이 reader-writer 락이다.

typedef struct _rwlock_t {
	sem_t lock;				// 이진 세마포어(기본 락)
    sem_t writelock;		// 하나의 쓰기 또는 다수의 읽기 락을 위한 락
    int readers;			// 임계 여역 내 읽기를 수행 중인 reader 수 
} rw_lock_t;

void rwlock_init(rw_lock_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->reader++;
    if (rw->reader == 1)
    	sem_wait(&rw_writelock);	// 읽기용 락이 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);	// 마지막으로 읽기용 락이 wirtelock 해제
    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);
}

이 방식은 공정성 문제가 있다. 쓰기 쓰레드에게 기아(Starvation)문제가 발생할 수 있다. 간단한 해결책으로는 쓰기 쓰레드의 작업이 어느 정도 쌓였을 때 주기적으로 쓸 수 있게 해주거나 쓰기 쓰레드가 대기 중일 때는 읽기 쓰레드가 락을 획득하지 못하는 방법이 있다.

3. 식사하는 철학자 문제(Dining-Philosophers Problem)

다섯 명의 철학자가 식탁 주위를 둘러앉았다. 총 다섯 개의 포크가 철학자와 철학자 사이에 하나씩 놓여있다. 철학자는 식사할 수 있고, 생각할 수 있다. 자신의 왼쪽 포크와 오른쪽 포크를 들어 식사할 수 있다. 아래 코드로 기본 동작을 확인하자.

whjie (1) {
	think();
    getforks();
    eat();
    putforks();
}

int left(int p) { return p;}
int right(int p) { return (p + 1) % 5; }

void getforks() {
	sem_wait(forks[left(p)]);
   	sem_wait(forks[right(p)]);
}

void getforks() {
	sem_post(forks[left(p)]);
   	sem_post(forks[right(p)]);
}