[OS] 25-1. Semaphores (1)

Park Yeongseo·2024년 1월 29일

OS

목록 보기

30/54

Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

다양하고 흥미로운 병행성 문제들을 해결하기 위해서는 락과 조건 변수를 모두 사용해야 했다. 이를 가장 먼저 알아챈 사람은 그래프 이론의 최단 거리 알고리즘으로 잘 알려진 Edsger Dijkstra인데, 그는 이번 장에서 배울 동기화 기법인 세마포어(semaphore)를 도입한 사람이기도 하다. Dijkstra와 그 동료들은 세마포어를 동기화와 관련한 모든 것들을 위한 기법으로 만들었는데, 실제로 세마포어는 락이나 조건 변수로도 사용 가능하다.

어떻게 락이나 조건 변수 대신 세마포어를 쓸 수 있을까? 세마포어의 정의는 무엇인가? 이진 세마포어는 무엇일까? 락이나 조건 변수로 세마포어를 만들 수 있을까? 혹은, 세마포어로 락이나 조건 변수를 만들 수 있을까?

1. Semaphores: A Definition

세마포어는 두 루틴으로 조작할 수 있는, 정수 값을 담은 오브젝트다. POSIX 표준에서 이 두 루틴은 sem_wait()과 sem_post()다.

역사적으로 sem_wait()은 P()함수, sem_post()는 V() 함수라 불렸다.

세마포어의 초기값이 그 행동을 결정하므로, 세마포어는 그것과 상호 작용하기 위한 루틴을 호출하기 전에 반드시 어떤 값으로 초기화되어야 한다.

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

위 코드에서는 세마포어 s 를 선언하고 이를 sem_init()의 세 번째 인자로 들어있는 값 1로 초기화했다. sem_init()의 두 번째 인자는 앞으로 보게 될 모든 예제에서 0으로 설정되어있을 텐데, 이는 세마포어가 한 프로세스 내의 여러 스레드 사이에서 공유되고 있음을 가리킨다 (0이 아닌 경우에는 여러 프로세스들 사이에서 공유되어, 공유 메모리 영역에 위치해야함을 가리킨다) 세마포어에 대한 자세한 내용이나 다른 사용법들을 보려면 man 페이지를 보도록 하자.

세마포어가 초기화 되고 나서는 이와 상호 작용하기 위한 두 함수, sem_wait()와 sem_post()를 호출할 수 있다. 이 두 함수의 동작은 다음과 같다

int sem_wait (sem_t *s) {
	//세마포어 s의 값을 1 감소
	//세마포어 s의 값이 음수면 대기함
}

int sem_post(sem_t *s){
	//세마포어 s의 값을 1 증가
	//하나 이상의 스레드가 대기 중인 경우, 그 중 하나를 깨움
}

이제는 이 루틴들이 어떻게 구현되어있는지를 보자. 여러 스레드들이 sem_wait()와 sem_post()를 호출할 때에는 이 루틴들의 임계 영역을 관리해줘야 할 필요가 있다. 우선은 어떻게 이 두 루틴들을 사용하는지 보고, 다음으로 어떻게 이것들을 만들지에 대해 논의하도록 한다.

이 함수들이 가져야 하는 기능들의 몇 가지 두드러지는 특징들에 대해 논의해보자. 첫 번째로, sem_wait()는 바로 리턴하거나, 호출자의 실행을 이어지는 sem_post()을 대기하면서 멈추게 한다. 물론 여러 개의 스레드가 sem_wait()을 호출할 수도 있고, 그 스레드들 모두가 깨워지기를 기다리며 큐에 들어갈 수도 있다.

두 번째로, set_post()는 sem_wait()와는 달리 특정 조건이 참이되기를 기다리며 대기하지는 않는다. 대신 sem_post()는 세마포어의 값을 하나 올리고 대기 중인 스레드가 있다면 그 중 하나를 깨운다.

세 번째로, 세마포어의 값은 음수일 때 대기 중인 스레드의 수와 같다. 이 값이 일반적으로는 세마포어 사용자들에게 보이지는 것은 아니지만, 이점을 알아두는 것은 어떻게 세마포어가 기능하는지를 기억하는 데에 도움을 줄 것이다.

지금은 세마포어 내에서 일어날 수 있을 것 같은 경쟁 조건들에 신경쓰지 말고, 이 함수들의 작동이 원자적으로 수행된다고 가정하자.

2. Binary Semaphores (Locks)

이제 세마포어를 써보자. 우선은 세마포어를 이미 익숙한 락과 같이 사용해본다. 아래의 코드를 보면, 단순히 임계영역을 sem_wait()/sem_post() 쌍으로 둘러싸고 있음을 볼 수 있다. 아래 코드가 잘 작동하려면 세마포어 m의 초깃값 X를 지정해줘야 한다. 어떤 값이어야 할까?

sem_t m;
sem_init(&m, 0, X); // init to X; what should X be?

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

sem_wait()과 sem_post()의 정의를 다시 살펴보면, 이 초깃값은 1이어야 함을 알 수 있다. 이를 분명히 하기 위해, 두 스레드를 사용하는 시나리오를 생각해보자. 첫 번째 스레드 $T_0$ 은 sem_wait()을 호출한다. 이는 세마포어의 값을 하나 줄여 0으로 만들 것이다. 만약 값이 0보다 크거나 같지 않다면 이 스레드는 대기하게 되겠지만, 값이 0이기 때문에 sem_wait()는 그냥 리턴하고 호출 스레드의 작업이 계속될 것이다. $T_0$ 은 이제 임계 영역에 진입할 수 있다. 만약 $T_0$ 이 임계 영역에 있는 동안 다른 어떤 스레드도 락을 획득하려 하지 않는다면, 이 스레드는 sem_post()를 호출해 세마포어의 값을 0에서 1로 복원하게 될 것이다.

$T_0$ 이 락을 가지고 있는 상태에서 다른 스레드 $T_1$ 이 sem_wait()를 호출해 임계 영역에 들어가려고 한다면 어떨까? 이 경우, $T_1$ 은 세마포어의 값을 -1로 줄이고 대기할 것이다. $T_0$ 이 재실행되면 이는 결국 sem_post()를 호출해 세마포어의 값을 다시 0으로 바꿀 것이고, 잠들어 있는 $T_1$ 을 깨워 락을 획득할 수 있게 할 것이다. $T_1$ 의 작업이 끝나면, 이 스레드는 다시 세마포어의 값을 1로 증가시킬 것이다.

아래 표에는 스레드의 동작과 더불어 각 스레드의 스케줄러 상태를 보여준다. $T_1$ 이 이미 사용 중인 락을 획득하려고 할 때 Sleep 상태로 간다는 것에 주의하자. 오직 $T_0$ 이 다시 실행되는 경우에만 $T_1$ 은 깨어나 다시 실행될 수 있다. 다수의 스레드가 락을 기다리며 큐에 들어가있는 시나리오를 생각해보자. 이 경우에 세마포어의 값은 어떻게 변할까? 생각해보자.

이제 세마포어를 락처럼 사용할 수 있게 됐다. 락은 딱 두 가지의 상태만을 가지고 있기 때문에, 이렇게 락으로 쓰이는 세마포어를 가리켜 이진 세마포어(binary semaphore)라고 부르기도 한다. 세마포어를 이렇게 이진 방식으로만 사용한다면 일반화된 세마포어보다 쉬운 방식으로 구현할 수 있다는 것에 주의하자.

3. Semaphores For Ordering

세마포어는 병행 프로그램의 이벤트들의 순서를 지정하는 데에도 유용하게 쓰일 수 있다. 예를 들어 한 스레드가 리스트의 원소를 삭제하기 위해 리스트가 비어있지 않기를 기다린다고 해보자. 이런 사용 패턴에서는 흔히, 한 스레드는 어떤 일이 일어나기를 기다리고, 다른 스레드는 그 일이 일으키고 그 일이 일어났다는 시그널을 보내어 기다리는 스레드를 깨운다. 이전에 조건 변수를 통해 이를 구현한 것처럼, 이번에는 세마포어를 이용해서 구현해보자.

간단한 예시는 다음과 같다. 한 스레드가 다른 스레드를 만들고 그 실행이 완료되기를 기다리려 한다 해보자. 이 프로그램이 실행됐을 때 원하는 출력은 다음과 같다.

parent: begin
child
parent: end

문제는 어떻게 세마포어를 이용해 이 효과를 얻어내느냐 하는 것이다.

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;
}

코드에서 부모는 sem_wait()을 호출하고 자식은 sem_post()를 호출하는데, 이로써 부모 스레드는 자식 스레드의 실행이 완료되기를 기다린다. 그렇다면 이 경우의 세마포어의 초깃값은 무엇이 되어야 할까?

세마포어의 값은 0으로 설정되어야 한다. 생각해볼 두 가지의 경우가 있다. 첫 번째로, 부모 스레드가 자식 스레드를 만들었지만 아직 자식 스레드가 실행되지는 않았다고 생각해보자. 이 경우 부모 스레드는 자식 스레드가 sem_post()를 호출하기 전에 sem_wait()를 호출할 것이다. 우리는 부모 스레드가 자식 스레드가 실행 완료될 때까지 대기하기를 원하는데, 이것을 가능하게 하기 위해서는 세마포어의 초깃값이 0보다 크지 않아야 하므로, 따라서 0이어야 한다. 부모는 세마포어의 값을 -1로 감소시키고 대기한다. 자식 스레드는 이후 실행되고 sem_post()를 호출해 세마포어의 값을 0으로 다시 올리고 부모를 깨운다. 부모 스레드는 sem_wait()로부터 돌아와 남은 작업들을 완료한다.

두 번째는 부모가 sem_wait()를 호출하기 전에 자식 스레드가 일을 전부 마치는 경우다. 이 경우 자식 스레드는 우선 sem_post()를 호출해 세마포어의 값을 0에서 1로 바꾼다. 이후 부모 스레드가 실행될 기회를 얻으면, 이는 sem_wait()를 호출해 세마포어의 값이 1임을 확인한다. 그러면 부모 스레드는 그 값을 다시 0으로 내리고 sem_wait()로부터 리턴한다. 대기하는 일 없이 원하던 효과만 얻게 되는 것이다.

4. The Producer / Consumer (Bounded Buffer) Problem

이 장에서 마주할 다음 문제는 생산자/소비자 문제인데, 이전 장에서 조건 변수를 다룰 때 자세히 다뤘던 문제다.

First Attempt

이 문제를 해결하기 위한 첫 번째 시도는 empty와 full, 두 세마포어를 도입하는 것이다. 스레드는 이 세마포어들을 버퍼 엔트리가 비어있는지 차있는지를 가리키기 위해 사용한다. 아래에는 put()과 get() 루틴들과, 생산자/소비자 문제를 해결하기 위한 첫 번째 시도의 코드가 있다.

/*
* put & get
*/
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;
}

/*
* first attempt to solve producer/consumer problem
*/
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 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); // MAX are empty
	sem_init(&full, 0, 0); // 0 are full
	// ...
}

이 예제에서 우선 생산자는 데이터를 넣기 위해 버퍼가 비어있기를 기다리고, 소비자도 비슷하게 데이터를 사용하기 위해 버퍼가 채워지기를 기다린다. 우선은 버퍼의 최대 크기 MAX = 1이라고 가정하고, 이 예제가 동작하는지 보자.

이번에도 두 스레드를 사용한다고 하자. 하나는 생산자, 하나는 소비자 스레드다. 단일 CPU를 사용한다고 가정하고, 소비자 스레드가 먼저 실행되게 되었다고 해보자. 소비자 스레드는 우선 C1에서 sem_wait(&full)을 호출한다. full의 초깃값은 0이므로 sem_wait()가 호출될 때 -1로 줄어든다. 소비자 스레드는 다른 스레드가 sem_post()를 호출해 깨워줄 때까지 대기 상태로 들어간다.

이제 생산자 스레드가 실행된다고 해보자. P1이 실행되고 sem_wait(&empty) 루틴을 호출한다.
empty가 MAX(이 경우에는 1)로 초기화되어 있으므로, 소비자 스레드와 달리 생산자 스레드는 이어 실행된다. empty는 0으로 줄어들고, 생산자는 데이터 값을 버퍼의 첫 엔트리에 집어 넣는다(P2). 이후에는 P3에서 sem_post(&full)을 호출해 full 세마포어의 값을 -1에서 0으로 바꿔 소비자 스레드를 깨운다.

이 경우에서, 둘 중 하나의 일이 일어날 수 있다. 만약 생산자 스레드가 계속 실행되면, 이는 반복문을 돌며 다시 P1을 실행하게 될 것이다. 이번에는 empty 세마포어의 값이 0이므로 잠들게 될 것이다. 만약 인터럽트가 발생해 소비자 스레드가 실행되기 시작한다면, 이는 sem_wait(&full)로부터 돌아와, 버퍼가 꽉 차있음을 발견하고 해당 버퍼의 데이터를 소비할 것이다. 어떤 경우든 바라던 동작이 이루어지고 있다.

이 예제는 더 많은 스레드들, 예를 들면 여러 생산자와 소비자 스레드에 적용하더라도 여전히 작동한다.

그렇다면 이번에는 버퍼의 최대 크기가 1보드 큰 경우, 즉 MAX가 1보다 큰 경우를 생각해보자. 이번에는 다수의 생산자와 소비자가 있다고 가정한다. 이때는 경쟁 조건이 발생한다. 어디서 경쟁 조건이 발생할 수 있을까? put()과 get() 코드를 유심히 보자.

두 생산자 스레드 $P_a, P_b$ 가 모두 put()을 거의 동시에 호출했다고 해보자. $P_a$ 가 먼저 실행되어 첫 번째 버퍼 엔트리를 채우기 시작했다고 하자. 이때 우연히 $P_a$ 가 fill 카운터를 1로 올리기 전에 인터럽트가 발생할 수 있다. 이후 $P_b$ 가 실행되면, F1 줄에서 자신의 데이터를 버퍼의 첫 번째 버퍼에 넣게 될 것이다. $P_a$ 에서 쓰려 했던 데이터가 덮어 쓰여 사라졌다.

A Solution: Adding Mutual Exclusion

여기서는 상호 배제를 잊어버렸다. 버퍼를 채우는 것과 버퍼의 인덱스를 하나 올리는 것은 임계 영역에 속하므로 조심스레 보호되어야 한다. 그러므로 이진 세마포어를 이용해 락들을 추가해보도록 하자. 코드는 다음과 같다.

void *producer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&mutex); // Line P0 (NEW LINE)
		sem_wait(&empty); // Line P1
		put(i); // Line P2
		sem_post(&full); // Line P3
		sem_post(&mutex); // Line P4 (NEW LINE)
	}
}

void *consumer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&mutex); // Line C0 (NEW LINE)
		sem_wait(&full); // Line C1
		int tmp = get(); // Line C2
		sem_post(&empty); // Line C3
		sem_post(&mutex); // Line C4 (NEW LINE)
		printf("%d\n", tmp);
	}
}

이제 코드의 모든 put() / get()에 락들을 추가했는데, 문제는 이렇게 하면 잘 작동할 것 같지만 그렇지 않는 것이다. 이유는 데드락(deadlock, 교착 상태)이 발생하기 때문이다. 왜 데드락이 발생할까? 잠시 생각해보자.

Avoiding Deadlock

생산자 하나, 소비자 하나가 있고, 소비자 스레드가 먼저 실행됐다고 해보자. 이 스레드는 뮤텍스를 얻고 full 세마포어의 sem_wait()를 호출한다. 이때는 아직 어떤 데이터도 없으므로 생산자 스레드는 잠에 든다. 문제는 아직 생산자 스레드가 mutex에 대한 락은 가지고 있다는 것이다.

다음으로는 생산자 스레드가 실행된다. 이 스레드는 생산할 데이터를 가지고 있고, 실행될 수 있었다면 소비자 스레드를 깨울 수도 있었을 것이다. 하지만 mutex에 대한 sem_wait()을 호출할 때(P0), 해당 락은 이미 사용되고 있다. 생산자 또한 계속 대기하게 된다.

여기서는 간단한 사이클이 발생한다. 소비자는 mutex를 잡고 full 시그널을 기다리고, 생산자는 full 시그널을 보낼 수는 있지만 mutex 를 기다린다. 생산자와 소비자가 서로를 기다리며 교착 상태에 빠진다.

At Last, A Working Solution

이 문제를 해결하기 위해서는 락의 범위를 축소시키면 된다. 아래의 코드가 제대로 된 해법을 보여주고 있다. 단순히 mutex와 관련한 것들을 임계 영역의 바로 주위에 위치시키도록 바꾸기만 했는데도, 간단하고 잘 작동하는 유한 버퍼가 되었다.

void *producer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&empty); // Line P1
		sem_wait(&mutex); // Line P1.5 (lock)
		put(i); // Line P2
		sem_post(&mutex); // Line P2.5 (unlock)
		sem_post(&full); // Line P3
	}
}

void *consumer(void *arg) {
int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&full); // Line C1
		sem_wait(&mutex); // Line C1.5 (lock)
		int tmp = get(); // Line C2
		sem_post(&mutex); // Line C2.5 (unlock)
		sem_post(&empty); // Line C3
		printf("%d\n", tmp);
	}
}

(아래는 책에는 없는 내용)

이전 시나리오와 마찬가지로 각각 하나의 생산자, 소비자 스레드가 있고, 소비자 스레드가 먼저 돌아가게 되었다고 해보자. 소비자 스레드가 먼저 full 세마포어에 대한 sem_wait()를 호출한다. 이때 모든 버퍼가 비어있으므로 소비자 스레드는 버퍼가 채워지기를 기다리며 잠에 든다.

이후 생산자 스레드가 돌아가게 된다고 해보자. 생산자는 empty에 대한 sem_wait()를 호출한다. 버퍼가 비어있으므로 다음으로 진행해 mutex에 대한 sem_wait()를 호출한다. 이때 mutex는 누구도 사용하고 있지 않은 상태이므로 생산자는 이 락을 가질 수 있다. 버퍼에 데이터를 집어 넣고 나서는 락을 해제하고, full에 대한 시그널을 보낸다. 대기 중인 소비자 스레드는 깨어난다.

다시 소비자 스레드가 돌아갔을 때, 소비자 스레드는 버퍼가 차있음을 확인하고 다음으로 진행한다. mutex 락을 얻고 데이터를 가져오고, 락을 풀고, empty에 대한 시그널을 보낸다. 이때 empty에 대해 대기 중인 스레드가 없으므로 바로 리턴한다.

만약 소비자가 empty 시그널을 보내기 직전에 인터럽트가 발생해 생산자 스레드가 돌아가게 되면 어떨까? 루프를 돌다 P1을 다시 실행하는 생산자 스레드는 empty 락을 갖지 못해 시그널을 기다리며 잠든다. 다음으로는 소비자 스레드가 실행되고, empty 시그널을 보내 생산자 스레드를 깨운다. 잘 작동한다.

Park Yeongseo

이전 포스트

[OS] 24. Condition Variables

다음 포스트