Dijkstra와 그의 동료들은 모든 다양한 동기화 관련 문제를 한 번에 해결할 수 있는 그런 기법을 개발하고자 했다. 그리고 세마포어가 탄생했다. 세마포어는 락과 컨디션 변수로 모두 사용할 수 있다.
1. 세마포어: 정의
세마포어는 정수 값을 갖는 객체로서 두 개의 루틴(sem_wait(), sem_post())을 가진다. 초기값에 의해 동작이 결정되기 때문에 제일 먼저 값의 초기화가 필요하다.
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);세마포어 s 를 선언하고, 3번째 인자로 1을 전달하여 세마포어의 값을 1로 초기화한다. em_init()의 두 번째 인자는 모든 예제에서 0이다. 이 값은 같은 프로세스 내의 쓰레드 간에 세마포어를 공유한다는 뜻이다.
초기화된 후에는 sem_wait(), sem_post()라는 함수를 호출하여 세마포어를 다룰 수 있다.
int sem_wait(sem_t *s) {
decrement the value of semaphore s by one;
wait if value of semaphore s is negative;
}
int sem_post(sem_t *s) {
increment the value of semaphore s by one;
if there are one or more threads waiting, wake one;
}sem_wait()는 세마포어 값이 1 이상이라면 즉시 리턴한다. 아니라면, 세마포어 값이 1이 될 때까지 호출자를 대기시킨다. 여러 쓰레드들이 함수를 호출할 수 있기 때문에 대기 큐에 여러 쓰레드가 존재할 수 있다. 대기 방식은 spin과 sleep 두가지가 있다.sem_post()함수는 대기하지 않는다. 세마포어 값을 증가시키고 대기 중인 쓰레드를 하나 깨운다.- 세마포어가 음수라면 그 값은 현재 대기 중인 쓰레드의 개수와 같다.
위 두개의 함수는 원자적으로 실행된다고 가정한다. 아직은 race condition에 대한 걱정은 하지 말자.
2. 이진 세마포어 (락)
우선 세마포어를 “락”으로 사용해보자.
sem_t m;
sem_init(&m, 0, X); // X로 세마포어 초기화하기.
sem_wait(&m);
// 임계 영역
sem_post(&m);X의 값이 무엇이 되어야 할까? 1이 되어야할 것이다.
쓰레드가 2개일 때를 생각해보자. 쓰레드 A는 세마포어 값을 1에서 0으로 감소시키고 임계 영역에 진입한다. 세마포어의 값이 0이기 때문에 바로 리턴한다. 이때 쓰레드 B가 sem_wait()을 호출해 임계영역에 진입을 시도한다면 어떻게 될까?
쓰레드 B는 세마포어 값을 -1로 감소시키고 대기 상태가 된다. 쓰레드 A가 이후에 작업을 완료하고 sem_post()를 호출하면 세마포어 값이 0이되고, 쓰레드 B가 다시 깨어난다. 이제 락을 획득하여 작업을 완료한 후 세마포어 값이 다시 1이 된다.
락은 두 개의 상태 (사용 가능, 사용 중) 만 존재하므로 이진 세마포어 (binary semaphore) 라고도 불린다.
3. 컨디션 변수로서의 세마포어
어떤 조건이 참이 되기를 기다리기 위해 현재 쓰레드를 멈출 때에도 세마포어는 유용하게 사용될 수 있다.
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의 값은 무엇이 되어야 할까?
printf(“parent: begin\n ”);
pthread_t c;
Pthread_create(c, NULL, child, NULL);
sem_wait(&s); // 자식을 여기서 대기
printf(“parent: end\n ”);
return 0;
}다음과 같이 자식 쓰레드의 종료를 기다리게 하고 싶다.
parent: begin
child
parent: end부모 프로세스는 자식 프로세스 생성 후 sem_wait()를 호출하여 자식의 종료를 대기한다. 자식은 sem_post()를 호출하여 종료되었음을 알린다.
이를 위해 세마포어의 값을 어떻게 초기화 해야할까?
정답은 0이다. 두가지 상황이 발생할 수 있다.
-
자식 프로세스 생성 후, 아직 자식 프로세스가 실행을 시작하지 않은 경우(준비 큐에만 들어 있고 실행 중이 아니다).
이 경우 자식이
sem_post()를 호출하기 전에 부모가sem_wait()를 호출할 것이다. 부모 프로세스는 자식이 실행될 때까지 대기하기 위해서는sem_wait()호출 전에 세마포어 값이 0보다 같거나 작아야 한다. 때문에 0이 초기값이 되어야 한다. 부모가 실행되면 세마포어 값을 감소(-1로)시키고 대기한다. 자식이 실행되었을 때sem_post()를 호출하여 세마포어의 값을 0으로 증가시킨 후 부모를 깨운다. 그러면 부모는sem_wait()에서 리턴을 하여 프로그램을 종료시킨다. -
부모 프로세스가
sem_wait()를 호출하기 전에 자식 프로세스의 실행이 종료된 경우이다. 이 경우, 자식이 먼저sem_post()를 호출하여 세마포어의 값을 0에서 1로 증가시킨다. 부모가 실행할 수 있는 상황이 되면sem_wait()를 호출한다. 세마포어 값이 1인 것을 발견할 것이다. 부모는 세마포어 값을 0으로 감소시키고sem_wait()에서 대기 없이 리턴한다. 이 방법 역시 의도한 결과를 만들어낸다.
4. 생산자/소비자 (유한 버퍼) 문제
이를 해결하기 위해 empty와 full이라는 두개의 세마포어를 사용한다.
int buffer[MAX];
int fill = 0;
int use = 0;
void put(int value) {
buffer[fill] = value; // f1
fill = (fill + 1) % MAX; // f2
}
int get() {
int tmp = buffer[use]; // g1
use = (use + 1) % MAX; // g2
return tmp;
}sem_t empty;
sem_t full;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&empty); // P1
put(i); // P2
sem_post(&full); // P3
}
}
void *consumer(void *arg) {
int i, tmp = 0;
while (tmp != −1) {
sem_wait(&full); // C1
tmp = get(); // C2
sem_post(&empty); // C3
printf(“%d\n ”, tmp);
}
}
int main(int argc, char *argv[]) {
// . . .
sem_init(&empty, 0, MAX); // empty는 MAX
sem_init(&full, 0, 0); // full은 0
// . . .
}첫 번째 시도
소비자 쓰레드는 sem_wait(&full)을 호출한다. 버퍼가 차있지 않다면(full의 세마포어 값 ≤ 0)이라면 대기 상태가 된다. 생산자 쓰레드는 sem_wait(&empty)을 호출한다. 처음에 MAX(=1)로 초기화해놨기 때문에 empty의 세마포어 값이 0으로 감소하고 버퍼를 채운다. 이후 생산자는 sem_post(&full)을 호출하여 소비자 쓰레드를 깨운다.
이번에는
MAX 값이 더 크다면 생산자와 소비자 쓰레드가 여러개가 있다면 어떨까? 경쟁 조건이 발생할 것이다. put(), get()을 잘 보자.
생산자 A와 B가 put()을 거의 동시에 호출했다고 가정하자. 생산자 A가 버퍼의 첫번째 공간에 데이터를 채우고 fill의 카운터 변수를 1로 변경하기 직전에 생산자 B가 인터럽트된다면, 똑같이 버퍼의 첫번째 공간을 채우게 된다.
해답: 상호 배제의 추가
버퍼를 채우고 버퍼에 대한 인덱스를 증가하는 동작은 임계 영역이기 때문에 신중하게 처리해야된다. 지금까지 배운 이진 세마포어와 몇개의 락을 추가해 해결해보자.
sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&mutex); // P0
sem_wait(&empty); // P1
put(i); // P2
sem_post(&full); // P3
sem_post(&mutex); // P4
}
}
void *consumer(void *arg) {
int i, tmp = 0;
while (tmp != −1) {
sem_wait(&mutex); // C0
sem_wait(&full); // C1
tmp = get(); // C2
sem_post(&empty); // C3
sem_post(&mutex); // C4
printf(“%d\n ”, tmp);
}
}
int main(int argc, char *argv[]) {
// . . .
sem_init(&empty, 0, MAX); // empty는 MAX
sem_init(&full, 0, 0); // full은 0
sem_init(&mutex,0 ,1); // lock은 1로 초기화
// . . .
}
이제 put()/get() 코드에 락을 추가했다. 그런데 아직도 동작하지 않는다. 왜일까? 교착 상태 때문이다.
생산자와 소비자 쓰레드가 각 하나씩 있다고 하자. 소비자가 먼저 실행이 되었다. mutex(c0 라인)를 획득하고 sem_wait(&full)(c1 라인)을 호출한다. 아직 데이터가 없기 때문에 소비자는 대기해야한다. 여기서 중요한 것은 소비자가 아직도 락을 획득하고 있다는 것이다.
생산자가 실행된다. 실행이 가능하면 데이터를 생성하고 소비자 쓰레드를 깨울 것이다. 불행하게도 이 쓰레드는 먼저 mutex를 획득하기 위해 sem_wait(&mutex)를 실행한다(p0 라인). 이미 락은 소비자가 획득한 상태이기 때문에 생산자 역시 대기에 들어간다.
순환 고리가 생겼다. 소비자는 mutex를 갖고 있으면서 다른 full 시그널을 발생시키기를 대기하고 있다. full 시그널을 발생시켜야 하는 생산자는 mutex에서 대기중이다. 생산자와 소비자가 서로를 기다린다. 전형적인 교착 상태이다.
최종, 제대로 된 해법
락의 범위를 줄여야 한다. mutex를 획득하고 해제하는 코드를 임계영역만을 감싸도록 하자
sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&empty); // p1
sem_wait(&mutex); // p1.5
put(i); // p2
sem_post(&mutex); // p2.5
sem_post(&full); // p3
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&full); // c1
sem_wait(&mutex); // c1.5
int tmp = get(); // c2
sem_post(&mutex); // c2.5
sem_post(&empty); // c3
printf(“%d\n ”, tmp);
}
}
int main(int argc, char *argv[]) {
// . . .
sem_init(&empty, 0, MAX);
sem_init(&full, 0, 0);
sem_init(&mutex, 0,1);
// . . .
}이제 멀티 쓰레드 프로그램에서 사용 가능한 유한 버퍼를 만들었다!
5. Reader-Writer 락
삽입 연산은 리스트의 상태를 변경하고 (전통적인 임계 영역 보호 방식으로 해결 가능하다), 검색은 자료 구조를 단순히 읽기만 한다. 삽입 연산이 없다는 보장만 된다면 다수의 검색 작업을 동시에 수행할 수 있다. 이와 같은 경우를 위해 만들어진 락이 reader-writer 락이다
typedef struct _rwlock_t {
sem_t lock; // 이진 세마포어 (기본 락)
sem_t writelock; // 하나의 쓰기 또는 다수의 읽기 락을 위한 락
int readers; // 임계 영역 내에 읽기를 수행중인 reader의 수
} 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); // readers를 변경하기 위해 이진 세마포어 사용
rw−>readers++;
if (rw−>readers == 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); // 마지막으로 읽기용 락이 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 세마포어를 사용하여 하나의 쓰기 쓰레드만이 락을 획득할 수 있도록 하여, 임계 영역 진임 후에 자료 구조를 갱신한다.
읽기 락을 획득시 읽기 쓰레드(reader)가 먼저 락을 획득하고 읽기 중인 쓰레드의 수를 표현하는 reader 변수를 증가시킨다. 첫 번째 읽기 쓰레드가 읽기 락을 획득할 때 중요한 과정이 있다. 읽기 락을 획득시 writelock 세마포어에 대해 sem_wait()을 호출하여 쓰기 락을 함께 획득한다. 획득한 쓰기 락은 읽기 락을 해제할 때 sem_post()로 다시 해제한다.
이 과정을 통해서 읽기 락을 획득하고 난 후, 다른 읽기 쓰레드들이 읽기 락을 획득할 수 있도록 한다. 다만, 쓰기 락을 획득하려는 쓰기 쓰레드 (writer)들은 모든 읽기 쓰레드가 끝날 때까지 대기하여야 한다. 임계 영역을 빠져나오는 마지막 읽기 쓰레드가 “writelock”에 대한 sem_post()를 호출하여 대기 중인 쓰기 쓰레드가 락을 획득할 수 있도록 한다.
이 방식은 몇 가지 단점이 있다.
쓰기 쓰레드에게 불리하다. 쓰기 쓰레드에게 기아 현상이 발생하기 쉽다. 쓰기 쓰레드가 대기 중일 때는 읽기 쓰레드가 락을 획득하지 못하도록 하여 기아 현상의 발생을 완화할 수 있다.
6. 식사하는 철학자
다섯 명의 “철학자”가 식탁 주위를 둘러앉았다. 다섯 개의 포크가 철학자 사이사이에 놓여있다. 철학자는 생각 중에는 포크가 필요 없고, 식사하기 위해서는 양쪽의 포크를 모두 들어야한다. 이 포크를 잡기 위한 경쟁과 그에 따른 동기화가 문제가 병행 프로그래밍에서 다루려는 식사하는 철학자 문제
while (1) {
think();
getforks();
eat();
putforks();
}주요 쟁점은 getfork()와 putfork()의 루틴을 작성하되 교착 상태의 발생을 방지해야 하고, 어떤 철학자도 못 먹어서 굶주리면 되며 병행성이 높아야 한다(즉, 가능한 많은 철학자가 동시에 식사를 할 수 있어야 한다).
int left(int p) { return p; }
int right(int p) { return (p + 1) % 5; }이 문제를 해결하기 위해서 세마포어가 필요하다. 각 포크마다 한 개씩 총 다섯 개가 있고 sem_t fork[5]로 정의한다.
불완전한 해답
각 포크에 대한 세마포어를 1로 초기화했고, 각 철학자는 자신의 순번을 알고 있다고 가정하자.
void getforks() {
sem_wait(forks[left(p)]);
sem_wait(forks[right(p)]);
}
void putforks() {
sem_post(forks[left(p)]);
sem_post(forks[right(p)]);
}원리는 간단하다. 포크가 필요하면 락을 획득하고, 식사를 완료 후 포크를 내려놓는다.
모든 철학자가 자신의 왼쪽 포크를 집고 있다면, 모든 철학자는 오른쪽 포크를 얻기 위해 계속해서 대기하게 된다. 교착 상태가 발생한다.
해답: 의존성 제거
최소한 하나의 철학자가 다른 순서로 포크를 집도록 하면 된다.
void getforks() {
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. 쓰레드 쓰로틀링
너무 많은 쓰레드가 동시에 작업을 수행하지 않도록, 세마포어를 사용하여 동시에 실행되는 쓰레드 수를 제한한다.
문제 상황 예시
예를 들어, 수백 개의 쓰레드를 만들어 병렬 작업을 수행한다고 가정하자. 코드의 특정 부분에서는 각 쓰레드가 많은 양의 메모리를 점유해 계산을 수행하는데, 이 부분을 ‘메모리 집중 구역’이라고 칭하자. 만약 모든 쓰레드가 동시에 이 메모리 집중 구역에 진입하게 되면, 물리 메모리의 총량을 초과하는 메모리 할당 요청이 발생할 것이다. 이로 인해 시스템은 스래싱(thrashing) 을 시작하여, 디스크와의 페이지 교환이 빈번하게 일어나고 전체 계산 성능이 급격히 저하될 것이다.
세마포어를 이용한 해결 방안
이 문제를 해결하는 간단한 방법은 세마포어를 사용하는 것이다. 세마포어의 초기 값은 메모리 집중 구역에 동시에 진입할 수 있는 최대 쓰레드 수로 설정한다. 그 다음, 이 구역에 sem_wait()와 sem_post() 함수 호출을 감싸서 세마포어를 적용한다. 이렇게 하면, 세마포어가 자연스럽게 메모리 집중 구역에서 동시에 실행될 수 있는 쓰레드 수를 제한하게 된다.
8. 세마포어 구현
저수준 동기화 기법인 락과 컨디션 변수를 사용하여 우리만의 세마포어를 만들어보자. 제마포어(Zemaphore)다..
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 보다 작을 수가 없다. 이 방식이 구현하기도 쉽고 현재 Linux에 구현된 방식이기도 하다.
세마포어를 사용하여 락과 컨디션 변수를 만드는 것은 매우 까다로운 문제이다. 세마포어로 컨디션 변수 구현에 성공한다면, 당신은 뛰어난 개발자의 소양을 가지고 있는 것이다.
