Semaphores

동시성 문제를 해결하기 위해 lock과 condition vaariable(조건변수)가 필요하다는 것을 알았다. Dijkstra(다익스트라)는 이를 구현할 수 있는 semaphore(세마포어)를 발명했다. 세마포어는 lock과 condition variable 모두로 사용될 수 있다 세마포어에 대해 알아보자

정의

세마포어는 정수 값을 가진 객체로, POSIX 표준에서는 sem_wait()와 sem_post()라는 두 루틴을 사용하여 조작할 수 있다. 세마포어의 초기 값은 그 동작을 결정하기 때문에 다른 루틴을 호출하기 전에 먼저 초기화 해야한다.

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

세마포어 s를 선언한 뒤 sem_init()의 인수로 전달하여 초기화 한다.

• 첫 번째 인수는 세마포어

• 두 번째 인수는 세마포어가 같은 프로세스 내의 스레드 간에 공유되는 것을 나타내고 우리가 살펴볼 예제들에서는 0으로 초기화 될 것이다.

• 세 번째 인수는 세마포어의 값이다. 우리는 이 값을 조정해가며 세마포어의 역할을 나타내고 정보를 얻을 것이다.
  이렇게 초기화를 하면 다음 루틴을 사용할 수 있다.

1 int sem_wait(sem_t *s) {
2 세마포어 s의 값을 1 감소시킨다. 
3 음수인 경우 기다린다.
4 }
5
6 int sem_post(sem_t *s) {
7 세마포어 s의 값을 1 증가시킨다. 
8 대기중인 하나 이상의 스레드가 있는 경우,하나를 깨운다.
9 }

이 루틴의 몇 가지 중요한 면을 논해보자

• 첫 번째, sem_wait()는 세마포어의 값이 1이상이면 즉시 반환하거나 sem_post에 의해 호출될 때 까지 기다릴 것이다.(queue에서 잠듦)

• 두 번째, sem_post()는 기다리는 것이 없다. 세마포어의 값을 증가시킨 후, 대기중인 스레드가 있는 경우 하나를 깨운다.

• 세 번째, 세마포어의 값이 음수인 경우, 그 절댓값은 대기중인 스레드의 수와 같다.

Binary Semaphores (Locks)

이제 세마포어를 lock으로 사용해보자

1 sem_t m;
2 sem_init(&m, 0, X); // init to X; what should X be?
3
4 sem_wait(&m);
5 // critical section here
6 sem_post(&m);

단순히 critical section을 감쌌다. 여기서 중요한 것은 세마포어의 초기값 X이다. X는 무엇이어야 할까?
위의 루틴들의 정의를 다시 살펴보면 초기값은 1이어야한다. 두 개의 스레드가 있는 상황을 상상해보자
첫 번째 스레드(Tread 0)는 sem_wait()를 호출한다. 세마포어의 값이 0이 되었으므로 반환하고 계속 진행한다. Tread 0은 critical section에 들어가고, 이 때 다른 스레드가 락을 획득하려고 하지않는다면, sem_post()를 호출하며 세마포어의 값을 1로 복원할 것이다. 아래 사진은 이 상황의 추적이다.
만약 Tread 0이 sem_post()를 호출하기 전에 다른 스레드(Tread 1)가 sem_wait()를 호출하여 critical section으로 들어가려고 한다면, Tread 1은 세마포어의 값을 -1로 설정하고 대기할 것이다. 그런다면, Tread 0은 sem_post()를 호출하며 세마포어의 값을 0으로 설정 후, Tread 1을 깨울것이다. 아래 사진은 이 상황에서의 추적이다.

이렇게 함으로써 우리는 세마포어를 락으로 사용할 수 있다. 락은 보유되거나 아니거나의 두 가지 상태만 가지고 있으므로 락으로 사용되는 세마포어를 이진 세마포어(Binary Semaphore)라고 한다.

Semaphores For Ordering

세마포어는 동시 프로그램에서 이벤트를 순서대로 정렬하는 데도 유용하다. 예를 들어 스레드는 리스트가 비어있지 않을 때 까지 기다렸다가, 요소를 삭제하기를 원할 수 있다. 이런 상황에서는 종종 하나의 스레드가 뭔가가 일어날 때까지 기다리고, 다른 스레드가 그 상황이 일어났음을 신호로 보내어 대기중인 스레드를 깨운다. 따라서 세마포어를 ordering primitive(순서지정 프리미티브)로 사용할 수 있다. conditional variable(조건변수)를 사용한 것과 유사하다.

다음 예제를 살펴보자

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: begin
child
parent: end

이것을 달성하기 위해서 세마포어를 어떻게 사용해야 할까? 코드에서 볼 수 있듯이, 부모는 sem_wait()을 호출하고 자식은 sem_post()를 호출한다. 하지만, 이 상황에서 세마포어의 초기값은 무엇이어야할까? 물론 답은 0이다.

고려해야할 두가지 경우가 있다.

첫 번째, 부모가 자식을 생성하지만 자식이 아직 실행되지 않은(queue에 존재) 경우, 부모는 세마포어의 값을 -1로 설정하며 잠에 들고, 자식이 실행될 때 세마포어의 값을 0으로 설정하며 부모를 깨울 것이다.

두 번째, 자식이 부모가 sem_wait()을 호출하기 전에 실행을 완료하는 경우, 자식은 세마포어의 값을 1로 설정하고, 부모는 세마포어의 값을 0으로 설정하며 반환되어 원하는 효과가 달성된다.

The Producer/Consumer (Bounded Buffer) Problem

조건변수를 살펴볼 때 언급했던 생산자/소비자(유한버퍼) 문제를 다시 살펴보자

첫 번째 시도

empty와 full이라는 두 개의 세마포어를 생각해보자 스레드는 이를 사용하여 버퍼 항목이 비워짐과 채워짐을 나타낸다.

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

---

//producer,consumer
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을 -1로 설정하고 잠에 들게 된다.
그 다음 생산자가 실행된다면, P1라인에서 sem_wait(&empty)를 호출한다. empty는 0으로 감소하고, P2에서 버퍼의 첫 번째 항목에 데이터를 넣는다. 그리고 P3에서 full을 -1에서 0으로 변경하고 소비자를 깨운다.

생산자가 계속 실행된다면, empty의 값이 0이므로 차단될 것이다. 그리고 소비자가 실행된다면, C1에서 반환하고 버퍼를 소비한다. 어떤 경우에도 원하는 동작을 달성한다.

더 많은 스레드가 있을때에도 작동할까? Max가 10이라고 생각해보자 여기서 생산자와 소비자는 여러개 있다. 여기서 critical section이 생긴다.두 명의 생산자 Pa,Pb가 거의 동시에 put()을 호출한다고 생각해보자 Pa가 먼저 실행되어 첫 번째 버퍼 항목을 채운다. Pa가 fill카운터를 1로 증가시키기 전에 인터럽트를 받아 Pb가 실행되고, 또, 버퍼에 데이터를 넣는다. 이렇게 되면 데이터가 덮어 씌어지게 되며 손실이 발생한다.

해결책: 상호 배제 추가

버퍼를 채우고 인덱스를 증가시키는 과정을 보호해보자

1 void *producer(void *arg) {
2 int i;
3 for (i = 0; i < loops; i++) {
4 sem_wait(&mutex); // Line P0 (NEW LINE)
5 sem_wait(&empty); // Line P1
6 put(i); // Line P2
7 sem_post(&full); // Line P3
8 sem_post(&mutex); // Line P4 (NEW LINE)
9 }
10 }
11
12 void *consumer(void *arg) {
13 int i;
14 for (i = 0; i < loops; i++) {
15 sem_wait(&mutex); // Line C0 (NEW LINE)
16 sem_wait(&full); // Line C1
17 int tmp = get(); // Line C2
18 sem_post(&empty); // Line C3
19 sem_post(&mutex); // Line C4 (NEW LINE)
20 printf("%d\n", tmp);
21 }
22 }

put,get루틴 주위에 락을 추가했다. 하지만 이렇게 해도 작동하지 않는다. deadlock이 생기기 때문이다.

deadlock 피하기

이제 deadlock을 피해보자 생산자,소비자가 하나씩 있을 때, 소비자가 먼저 실행된다. 소비자는 C0에서 mutex를 획득하고 full 세마포어에 대해 sem_wait()를 호출한다. 이 호출은 소비자를 차단하고 CPU를 양보하게 한다. 중요한 것은 소비자가 락을 가지고 있다는 것이다. 그 후 생산자가 실행된다. 생산자는 P0에서 sem_wait()을 호출하지만 락이 이미 걸려있으므로 기다리게 된다.

소비자는 락을 가지고 full을 기다리고, 생산자는 full을 신호하려하지만,락을 기다리고 있다. 전형적인 교착상태 deadlock이다.

이 문제를 해결하기 위해 락의 범위를 줄인다.

1 void *producer(void *arg) {
2 int i;
3 for (i = 0; i < loops; i++) {
4 sem_wait(&empty); // Line P1
5 sem_wait(&mutex); // Line P1.5 (lock)
6 put(i); // Line P2
7 sem_post(&mutex); // Line P2.5 (unlock)
8 sem_post(&full); // Line P3
9 }
10 }
11
12 void *consumer(void *arg) {
13 int i;
14 for (i = 0; i < loops; i++) {
15 sem_wait(&full); // Line C1
16 sem_wait(&mutex); // Line C1.5 (lock)
17 int tmp = get(); // Line C2
18 sem_post(&mutex); // Line C2.5 (unlock)
19 sem_post(&empty); // Line C3
20 printf("%d\n", tmp);
21 }
22 }

mutex 락 획득,해제를 critical section 주위로만 이동시키고, full,empty의 대기,신호 코드는 밖에 남겨두었다.

Reader-Writer Locks

동시에 여러 리스트 작업을 수행하는 상황을 생각해보자 이 작업에서는 조회,삽입을 할 수 있다. 조회는 단순히 데이터 구조를 읽고 삽입은 데이터 구조를 변경 시킨다.
조회는 읽기만 하기에 삽입이 진행중이지만 않다면 조회를 동시에 진행할 수 있다. 이런 작업을 지원하는 락을 reader-writer lock이라고 한다. 코드는 아래와 같다.

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 세마포어를 사용하여 하나의 작성자만 락을 획득하여 critical section에 들어갈 수 있게 보장한다.

읽기 락의 루틴 쌍도 있다. 읽기 락을 획득할 때, 리더(reader)는 락을 얻고, 데이터 구조 내부에 몇 명의 리더가 있는지 추적하기 위해 readers 변수를 증가시킨다. rwlock_acquire_readlock()에서 첫 번재 리더가 락을 획득할 때, writelock 세마포어에 대해 sem_wait()를 호출하여 쓰기 잠금을 획득하고 sem_post()를 호출하여 락을 해제한다.

따라서 한 번 리더가 읽기 락을 획득하면, 더 많은 리더도 읽기 락을 획득할 수 있다. 그러나 쓰기 락을 획득하려는 스레드는 모든 리더가 완료될 때 까지 기다려야 한다. critical section에서 마지막으로 나가는 쓰레드가 writelock에 sem_post()를 호출하여 대기중인 작성자가 잠금을 획득할 수 있도록 한다. 리더가 작성자를 굶주리게(starve)하기 때문에 오버헤드를 발생기키며 성능을 높이는데 도움이 되지 않을 수 있다. 이 방법은 세마포어를 흥미롭고 유용하게 사용할 수 있는 방법을 보여준다.

The Dining Philosophers

다익스트라가 제기하고 해결한 동시성 문제 중 하나는 식사하는 철학자 문제이다. 유용성은 낮지만 흥미롭고 유명하다.
문제는 다음과 같다. 테이블 주위에 앉아있는 다섯 철학자가 있고 각 철학자 사이에는 하나의 포크가 있다. 철학자들은 각자 생각하는 시간, 포크가 필요없는 시간, 식사하는 시간이 있다. 식사를 하려면 철학자는 왼쪽과 오른쪽의 두 개의 포크가 필요하다. 포크에 대한 경합과 그로인해 발생하는 동기화 문제가 병렬 프로그래밍 공부에서 생각해볼만 하다.

각 철학자의 루프는 다음과 같다. 각 철학자는 고유한 스레드 실별자 p를 가정한다.

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

get_forks(),put_forks()루틴으로 deadlock이 없고, 병렬성이 높은 솔루션을 찾을 수 있다.

Downey의 솔루션을 따라 몇가지 함수를 사용해보자

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

철학자가 왼쪽, 오른쪽의 포크를 참조하려면 left(p),right(p)를 호출한다. 모듈로 연산(%)은 마지막 철학자(p=4)가 오른쪽의 포크 0을 가져오려고 할때 처리된다.

이 문제를 해결하기 위해 각 포크마다 하나씩, 다섯개의 세마포어를 가정해보자 sem_t forks[5]

Broken Solution

각 포크 세마포어를 1로 초기화한다고 가정해보자 그리고 각 철학자가 자신의 번호(p)를 알고 있다. 따라서 get_forks()와 put_forks()루틴을 작성할 수 있다.

1 void get_forks(int p) {
2 sem_wait(&forks[left(p)]);
3 sem_wait(&forks[right(p)]);
4 }
5
6 void put_forks(int p) {
7 sem_post(&forks[left(p)]);
8 sem_post(&forks[right(p)]);
9 }

포크를 얻기 위해서 각각의 락을 먼저 잡는데 왼쪽의 포크를 잡고 오른쪽의 포크를 잡니다. 그리고 식사가 끝나면 포크를 해제한다. 하지만 문제가 있다. 문제는 교착상태 deadlock이다. 각 철학자가 왼쪽의 포크를 잡는다면 오른쪽의 포크를 잡기위해 기다릴 것이고 교착상태가 발생할 것이다.

A Solution: Breaking The Dependency 의존성 깨기

이 문제를 해결하는 간단한 방법은 최소 하나의 철학자가 포크를 얻는 방법을 바꾸는 것이다. 이것은 다익스트라가 문제를 해결한 방법이다. 구체적으로 철학자 4가 다른 순서로 포크를 얻는 것으로 가정해보자 get_fork()만 바꾸면 된다.

1 void get_forks(int p) {
2 if (p == 4) {
3 sem_wait(&forks[right(p)]);
4 sem_wait(&forks[left(p)]);
5 } else {
6 sem_wait(&forks[left(p)]);
7 sem_wait(&forks[right(p)]);
8 }}

마지막 철학자는 오른쪽 포크를 먼저 잡으려고 하기 때문에 교착상태가 생기지 않는다.

Thread Throttling 스레드 스로틀링

너무 많은 스레드가 동시에 작업하여 시스템이 느려질 때 프로그래머는 이를 방지할 수 있을까? '너무 많은'의 기준을 정하고 세마포어를 사용하여 특정 코드를 동시에 실행하는 스레드의 수를 제한할 수 있다. 이런 접근 방식을 스로틀링(throttling)이라고 하며, 일종의 접근 제어(admission control)로 간주한다.

구체적으로, 병렬로 작업하기 위해 수백 개의 스레드를 생성한다고 가정해보자 그러나 코드의 특정 부분에서 각 스레드가 계산의 일부를 수행하기 위해 많은 메모리를 할당해야한다. 이 부분을 메모리 집중 영역(memory-intensive region)이라고 부르겠다. 만약 모든 스레드가 동시에 메모리 집중 영역에 들어간다면, 모든 메모리 할당 요청의 합이 기계의 물리적 메모리 양을 초과하게 된다. 그 결과,기계는 스레싱(페이지를 디스크와 메모리간에 교환하는 것)을 시작하게 되고, 전체 계산 속도는 급격히 느려지게된다.

이 문제는 간단한 세마포어로 해결할 수 있다. 세마포어의 값을 한 번에 메모리 집중 영역에 들어갈 수 있는 최대 스레드 수로 초기화 하고, 그 영역 주변에 sem_wait()와 sem_post()를 두면, 세마포어는 그 영역에 들어갈 수 있는 스레드 수를 제한하게 된다.

세마포어 구현법

마지막으로, 저수준 동기화 원시 기능인 락과 조건 변수를 사용하여 Zemaphores라고 부르는 자체 세마포어 버전을 만들어 보겠다.

1 typedef struct __Zem_t {
2 int value;
3 pthread_cond_t cond;
4 pthread_mutex_t lock;
5 } Zem_t;
6
7 // only one thread can call this
8 void Zem_init(Zem_t *s, int value) {
9 s->value = value;
10 Cond_init(&s->cond);
11 Mutex_init(&s->lock);
12 }
13
14 void Zem_wait(Zem_t *s) {
15 Mutex_lock(&s->lock);
16 while (s->value <= 0)
17 Cond_wait(&s->cond, &s->lock);
18 s->value--;
19 Mutex_unlock(&s->lock);
20 }
21
22 void Zem_post(Zem_t *s) {
23 Mutex_lock(&s->lock);
24 s->value++;
25 Cond_signal(&s->cond);
26 Mutex_unlock(&s->lock);
27 }

위의 코드에서는 하나의 락과 하나의 조건 변수, 그리고 세마포어 값을 추적하는 상태 변수만 사용합니다. 코드를 직접 공부해서 완전히 이해할 때까지 해보세요.

우리의 Zemaphore와 Dijkstra가 정의한 순수 세마포어의 미묘한 차이점 중 하나는 세마포어의 값이 음수일 때 대기 중인 스레드 수를 반영하는 불변 조건을 유지하지 않는다는 점입니다. 실제로 값은 0보다 낮아지지 않습니다. 이 동작은 구현하기 더 쉽고 현재 Linux 구현과 일치합니다.

흥미롭게도, 세마포어를 사용하여 조건 변수를 만드는 것은 훨씬 까다로운 문제입니다. 일부 고도로 숙련된 동시 프로그래머가 Windows 환경에서 이를 시도했으나, 다양한 버그가 발생했습니다. 직접 시도해 보고, 세마포어를 사용하여 조건 변수를 만드는 것이 왜 더 어려운 문제인지 알아보세요.