[운영체제] 세마포어 (Semaphore)

 제목은 세마포어로 바뀌었지만 병행성과 관련 있는 내용이다.

semaphores : mutex 의 일반화된 형태

semaphores 는 edsger dijkstra 라는 사람이 발명했고 mutex 나 condition variable 을 구현할 수 있다. 오 다익스트라 아저씨 여기도 나오네? 기존의 lock 이 하나라면 semaphore 는 락 할 수 있는 횟수를 정수로 나타낸다. 다음과 같은 연산이 있다.

p (sem_wait() ) : - 연산, wait 와 유사하다. (n < 0 -> sleep) - lock
 - n 이 음수라면 기다려야 한다. 음수 절대값은 대기 중인 스레드의 개수가 된다.
v (sem_post() ) : + 연산, signal 연산과 유사하다. (n > 0 -> wake one up) - unlock
 - n 이 음수라면 기다리고 있는 스레드 하나를 깨운다. 어떤 스레드를 깨울 지는 구현에 따라 다르다.

binary semaphores (locks) : 0과 1만 사용하기 때문에 lock 과 비슷하다.

sem_t m;
sem_init(&m, 0, X);

X 에 들어갈 값은 락을 할 수 있는 스레드의 숫자이다.

semaphre 는 mutex 나 lock 으로도 쓸 수도 있고, condition variable 로도 쓸 수 있다. Condition Variables 로 사용하면?

sem_t s;
...
sem_init(&m, 0, X);
pthread_t c;
pthread_create(c, NULL, child, NULL);
sem_wait(&s)
...

 위같은 코드를 동작시키려면, wait 가 불렸을 때 parent 는 block 이 되어야 하므로 X 의 값은 0이 되어야 한다. 어떤 조건을 기다릴 때에는 X 를 0으로 두고 기다리면 된다. 만약 wait 를 호출하기 전에 context switching 이 발생하여 child 가 먼저 실행된다면? child 에서 sem_post 를 호출하면 세마포어의 n 값이 1이 되어 다시 parent 로 돌아와 sem_wait 를 수행해도 n 값이 0이 되어 정상적으로 실행 된다. 즉, 정상적인 흐름이다.

Bounded Buffer

// sem_t empty, full;
sem_wait(&empty);
put(value);
sem_post(&full)

 세마포어에서도 bounded buffer 문제를 해결하기 위해 두 개의 세마포어를 사용한다. 버퍼의 크기가 1보다 크면 이 condition variable 은 mutex 가 아니다. 여기서는 lock 과 condition variable 을 위한 세마포어를 각각 만들어야 한다.

sem_wait(&mutex);
sem_wait(&empty);
...

 만약 이런 코드를 동작시킨다면 lock 을 잡을 상태에서 wait 로 들어가 데드락이 발생할 수 있다. 따라서 두 코드의 순서를 바꿔주어야 한다.

Read/Write Lock

 read 는 여러 스레드에서 동시에 접근해도 되지만 write 는 동시에 하나만 접근해야 한다. read 끼리는 동시에 lock 을 할 수 있고, write 에 대해서는 mutex 를 적용한다. 하지만 락 자체의 메커니즘이 복잡해서 read/write 락 사용을 권장하지 않는다. (readers > 0 일 때 read 는 접근 가능, write 는 불가)

The Dining Philosophers

 철학자들이 원형 식탁에 앉아 있고, 철학자들 사이에 포크가 하나씩 있다. 밥을 먹기 위해선 양쪽 포크 두 개를 잡아야 한다. 데드락이 발생하지 않으려면? -> 마지막 사람만 반대쪽 포크를 먼저 잡는다. (한 명을 제외한 모든 철학자들이 포크 잡는 순서가 같다.)