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

5. Reader-Writer Locks

다른 고전적인 문제는 더 유연하고, 다양한 자료 구조 접근을 위한 여러 종류의 락에 대한 필요성에 기반한다. 예를 들어 삽입과 간단한 검색을 포함한 여러 개의 병행 리스트 연산들을 생각해보자. 삽입의 경우 리스트의 상태를 변화시키지만, 검색은 간단하게 자료 구조를 읽기만한다. 따라서 만약 삽입이 일어나지 않는다는 것이 보장된다면, 많은 검색들을 병핵적으로 일어나게 할 수 있다. 이러한 종류의 연산을 지원하는 특별한 종류의 락을 가리켜 reader-writer 락이라 부른다. 코드는 아래와 같다.

typedef struct _rwlock_t {
	sem_t lock; // binary semaphore (basic lock)
	sem_t writelock; // allow ONE writer/MANY readers
	int readers; // #readers 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) // first reader gets writelock
		sem_wait(&rw->writelock);
	sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
	sem_wait(&rw->lock);
	rw->readers--;
	if (rw->readers == 0) // last reader lets it go
		sem_post(&rw->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);
}

코드는 상당히 단순한데, 만약 어떤 스레드가 자료 구조를 업데이트하고 싶다면, 이 스레드는 한 쌍의 동기화 루틴, rwlock_acquire_writelock()과 rwlock_release_writelock()을 호출해야 한다. 내부적으로 이들은 writelock 세마포어를 이용해 오직 한 라이터만이 락을 획득하고 임계 영역에 들어가 자료 구조를 업데이트 할 수 있음을 보장한다.

더 흥미로운 것은 읽기 락을 획득하고 해제하는 루틴 쌍이다. 읽기 락을 얻으면, 리더는 우선 lock을 얻고, 얼마나 많은 리더들이 현재 자료 구조에 있는지를 추적하기 위한 readers 변수를 1 증가시킨다. 첫 번째 리더가 락을 얻었을 때, rwlock_acquire_readlock()에서 중요한 단계가 있다. 이 경우 리더는 writelock 세마포어에 대한 sem_wait()을 호출해 쓰기 락도 획득하고, sem_post()를 호출해 lock을 놓아준다.

이를 통해 한 리더가 읽기 락을 얻고 나서 다른 리더 스레드들도 읽기 락을 획득할 수 있게 한다. 다만 쓰기락을 얻으려는 스레드는 모든 리더 스레드의 작업이 끝날 때까지 대기해야 한다. 임계 영역에서 빠져나오는 마지막 스레드는 writelock에 대해 sem_post()를 호출함으로써 대기 중인 라이터가 락을 얻을 수 있게 한다.

이 접근법은 작동하지만 많은 단점들을 가지는데, 공정성의 측면에서 특히 더 그렇다. 특히 읽기 스레드들이 쓰기 스레드들을 굶기는 일이 상대적으로 더 쉽다. 이 문제에 대한 많은 세련된 해결법들이 있다. 쓰기 스레드가 대기 중일 때 더 많은 읽기 스레드들이 락에 진입하는 일을 막기 위해서는 어떻게 해야할지 생각해보자.

마지막으로, reader-writer 락을 사용할 때에는 주의를 기울여야 한다는 점을 명심하자. 이 락은 더 많은 오버헤드를 추가하고, 따라서 간단하고 빠른 락 기법을 사용하는 것보다 성능을 높이지 못할 수도 있다.

6. the dining philosophers

Dijkstra가 제기하고 해결한, 가장 유명한 병해성 문제들 중 하나는 식사하는 철학자 문제(dining philosopher's problem)라 불린다. 이 문제는 재미있고 지적으로 흥미롭기에 유명하지만, 실용성은 낮다.

이 문제의 기본 설정은 다음과 같다. 다섯 명의 철학자들이 테이블을 둘러앉아 있다고 가정하자. 각 철학자 쌍 사이에는 포크가 하나 씩, 그러니까 총 다섯 개가 있다. 철학자들은 생각을 할 때가 있고, 식사를 할 때가 있는데, 생각을 할 때에는 포크가 필요가 없다. 식사를 하기 위해서 철학자들은 자신의 좌우에 있는 포크들이 필요하다. 이 포크들에 대한 경쟁과 그에 따른 동기화 문제가 이 문제를 병행성 프로그래밍에서 다루게 되는 이유다.

여기 각 철학자의 기본적인 반복문이 있는데, 각각이 0에서 4까지의 고유한 스레드 식별자 p를 가진다고 가정하자.

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

핵심 쟁점은 루틴 get_forks()와 put_forks()를 데드락이 발생하지 않게, 어떠한 철학자도 굶지 않게, 병행성이 높게 작성하는 것이다.

Downey의 해법을 따라, 다음의 보조 함수들을 이용해 문제를 해결해보도록 하자.

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

철학자 p는 자신의 왼쪽에 있는 포크를 집으려고 할 때 left(p)를 호출한다. 오른쪽도 마찬가지다. right()의 나머지 연산은 마지막 철학자가 자신의 오른쪽에 있는 0번 포크를 잡으려 할 때를 처리하기 위함이다. 이 문제를 풀려면 세마포어도 사용해야 한다. 각 포크마다 하나 씩, 총 다섯 개의 세마포어(sem_t forks[5])가 있다고 가정하자.

Broken Solution

각 세마포어의 값을 1로 초기화했다고 가정하고, 또한 각 철학자들이 자신의 번호를 알고 있다고 가정하자. 그렇다면 이제 다음과 같이 get_forks()와 put_forks() 루틴을 작성할 수 있다.

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

이 해법은 다음과 같은 직관에 근거한다. 포크를 얻기 위해서는 해당 포크의 락을 잡으면 되고, 먼저 왼쪽 포크를 잡고, 그 다음으로 오른쪽 포크를 잡는 것이다. 만약 식사를 다 마치면 두 락을 모두 풀어준다. 이 해법은 간단하지만 문제가 있다.

그 문제는 데드락이 발생한다는 것이다. 만약 누구도 자신의 오른쪽 포크를 집지 못한 상태에서 각 철학자들이 자신의 왼쪽 포크를 집게 되는 경우, 이들은 모두 자신의 오른쪽 포크를 집을 수 있기를 기다리며 멈춰버리게 될 것이다. 데드락에 대한 구체적인 내용은 곧 다루게 될 것이다. 지금은 이 해법이 제대로 작동하는 것이 아니라는 점만 알아두자.

A Solution: Breaking The Dependency

이 문제를 해결하기 위한 가장 간단한 방법은 적어도 한 철학자가 포크를 획득하는 방법을 바꾸는 것으로, Dijkstra는 이를 통해 문제를 해결했다. 구체적으로 4번 철학자가 다른 이들과는 다른 순서로 포크를 획득한다고 하자. put_forks() 코드는 동일하다.

void get_forks(int p) {
	if (p == 4) {
		sem_wait(&forks[right(p)]);
		sem_wait(&forks[left(p)]);
	} else {
		sem_wait(&forks[left(p)]);
		sem_wait(&forks[right(p)]);
	}
}

마지막 철학자가 왼쪽 포크를 잡기 전에 오른쪽 포크를 잡으려하기 때문에, 모든 철학자가 각자 하나의 포크를 얻어 대기하며 멈춰버리는 경우는 발생하지 않는다. 대기의 사이클이 무너지는 것이다.

7. Thread Throttling

세마포어의 다른 특수한 용례를 소개한다. 구체적인 문제는 다음과 같다. 어떻게 프로그래머는 너무 많은 스레드가 일을 해서 시스템을 수렁에 빠트리는 일을 막을 수 있을까? 정답은 허용할 스레드 수에 대한 임계값을 정하고 세마포어를 사용해서 병행적으로 돌아가는 스레드의 수를 제한하는 것이다. 이와 같은 접근 법을 스로틀링(throttling)이라 부르며, 이는 승인 제어(admission control)의 한 형태로 생각된다.

좀 더 구체적인 예를 생각해보자. 어떤 문제에 대해 병렬적으로 동작하는 수백개의 스레드들을 만들었다고 해보자. 그런데 코드의 어떤 부분에서, 각 스레드는 이 계산 작업의 일부를 수행하기 위해 많은 양의 메모리를 얻어야 한다. 코드의 이 부분을 memory-intensive 영역이라 부르자. 만약 모든 스레드들이 이 영역에 동시에 들어가면, 전체 메모리 할당 요청의 합이 기기의 물리 메모리의 양을 초과한다. 결과적으로 기기는 스래싱을 하기 시작할 것이고, 전체 계산도 기어다니는 수준으로 느려지게 될 것이다.

간단한 세마포어가 이 문제를 해결할 수 있다. 세마포어의 값을 한번에 memory-intensive 영역에 들어갈 수 있는 스레드의 최대 수로 초기화하고 sem_wait()과 sem_post()를 해당 영역을 둘러싸게 함으로써, 세마포어는 코드의 해당 영역에서 동시에 돌아갈 수 있는 스레드의 수를 제어할 수 있게 된다.

8. How To Implement Semaphores

마지막으로 락, 조건 변수를 이용해 Zemaphore라고 불리는 세마포어를 구현해보도록 하자. 이 작업은 상당히 직관적이다.

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

// only one thread can call this
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);
}

위 코드에서는 하나의 락, 하나의 조건 변수와 더불어 세마포어의 값을 추적하기 위한 하나의 상태 변수를 사용한다.

이 Zemaphore는 Dijkstra가 정의한 순수한 세마포어와 달리, 음수인 값이 대기 중인 스레드의 수를 나타낸다는 성질을 가지지 않는다. 이 값은 사실 0보다 작아지지 않는다. 이러한 방식은 구현하기 더 쉽고 현재 리눅스의 구현과도 맞는다.

세마포어를 이용해서 조건 변수를 만드는 것은 더 까다롭다. 몇몇 경험 많은 병행 프로그래머들이 이를 윈도우 환경에서 구현해보려 시도했지만, 많은 버그들이 뒤따랐다. 직접 시도해보면 세마포어를 통해 조건 변수를 만드는 일이 왜 보기보다 어려운지를 알 수 있을 것이다.

9. Summary

세마포어는 병행 프로그램을 작성하기 위한 강력하고 유연한 기법이다. 어떤 프로그래머들은 세마포어가 가지는 단순성과 유용성을 이유로, 락이나 조건 변수를 사용하지 않고 세마포어만을 이용하기도 한다.