[운영체제] Semaphore

 

운영체제의 병행성 기법 중 하나인 Semaphore에 대해서 알아보자

 

 

 

Semaphore는 정수 값을 가지는 객체라고 생각하면 된다.

 

Sem_wait(), Sem_post()같이 Semaphore의 값을 조절하는 함수를 가지고 있다.

 

Semaphore 초기화

 

첫 번째 인자는 Semaphore객체, 두 번째 인자는 여러 개의 쓰레드에 의해서 공유되고 있다는 것을 의미, 세 번째 인자는 Semaphore값을 1로 초기화 하겠다는 뜻이다.

 

---

 

Semaphore의 2가지 동작에 대해서 알아보자

 

sem_wait()

Semaphore값을 1 감소시킨다.

값이 0 이상이라면 즉시 return 한다.

값이 음수가 된다면 wait상태에 들어가고, sem_post()가 호출될 때까지 wait 한다.

여러 개의 쓰레드가 sem_wait()을 호출한다면 음수인 값의 절댓값이 wait 하고 있는 쓰레드의 개수이다.

 

 

 

sem_post()

Semaphore값을 1 증가시킨다.

wait중인 쓰레드 중 하나를 깨워서 Critical Section에 진입할 수 있게 한다.

 

---

Semaphore를 이용한 Lock 구현

 

중요한 점은 Semaphore를 1로 초기화시켜야 한다는 것이다.

 

 

2개의 쓰레드가 Semaphore를 사용하는 예제

 

Semaphore 중에서 Lock으로 사용되는 것을 Binary Semaphore라고 한다.

 

---

Semaphore를 이용한 Condition Variables 구현

 

Child를 생성하고 Parent가 바로 wait 해야 하기 때문에 Semaphore값을 0으로 초기화시켜야 한다.

 

Child가 생성되고 parent의 sem_wait()가 호출되기 전에 바로 Child로 Context Switching이 일어나도 정상적으로 wait이 수행된다.

child에서 sem_post()가 수행되고 return을 하는데, sem_post()를 했기 때문에 semaphore의 값이 1이 된다.

그리고 parent의 sem_wait()을 수행하면 semaphore값을 1감소 시키는데 이 때 semaphore값이 0으로 음수가 되지 않기 때문에 sem_wait()에서도 바로 return을 한다.

 

당연히 sem_wait()이 호출된 후 Context Switching이 발생해서 Child쓰레드가 실행이 되어도 정상적으로 Parent가 wait()을 하게 되고, sem_post()를 통해서 정상적으로 Parent로 돌아올 수 있다.

 

---

Producer/Consumer (Bounded-Buffer) 문제 해결

 

Producer: put()

-> buffer의 공간이 비어있으면 data를 입력한다.

 

Consumer: get()

-> buffer의 공간이 차있으면 data를 사용한다.

 

 

 

fill = (fill + 1) % MAX를 통해서 MAX만큼의 buffer만 사용한다. (circular)

 

 

 

Producer : data를 입력하기 위해서 sem_wait를 호출해 buffer에 공간이 있는지 확인하고, 1 이상 공간이 있다면 put(i)를 수행한다.

 

Consumner : data를 읽어오기 위해서 sem_wait를 호출해 buffer에 data가 있는지 확인하고, 있다면 buffer에서 data를 가져온다.

 

 

빈 공간의 크기를 가지고 있는 empty Semaphore는 MAX로 초기화해주고

사용 중인 공간의 크기를 가지고 있는 full Semaphore는 0으로 초기화해준다.

 

---

 

 

Line f1에서 context switching이 발생하면 어떻게 될까?

 

ex) buffer[1]에 value가 입력이 되고 context switching이 발생해서 다른 쓰레드의 put이 수행된다.

     fill 값은 그대로 1 이므로 buffer[1]에 새로운 value가 쓰이게 되는 문제가 발생한다.

 

 

위 문제를 해결하기 위해서 

 

put(i)를 수행할 때 mutex라는 lock(Binary Semaphore)을 한 번 더 걸어주어야 한다.

 

 

위 그림처럼 mutex lock을 걸어주면 deadlock 문제가 발생할 수 있다.

 

만약 producer보다 consumer가 먼저 수행된다면 mutex lock을 얻고, sem_wait(&full)을 호출했더니 full이 0이라서 wait상태에 들어가게 된다.

그리고 producer가 mutex lock을 얻고 sem_wait(&empty)를 호출해야 하는데

consumer에서 얻었던 mutex lock이 아직 풀리지 않았기 때문에 producer는 consumer의 mutex lock을 기다리고, consumer는 producer에서 fill이 수행되기만을 기다리게 되는 Deadlock상태가 발생한다.

 

 

위 문제는 mutex lock이 감싸고 있는 Critical Section이 너무 크기 때문에 발생하는 문제이다.

 

 

 

따라서 위와 같이 mutex lock의 위치를 옮겨주기만 해도 deadlock문제가 해결될 수 있다.

 

---

다익스트라가 고안한 The Dining Philosophers 문제와 해결 방법

 

 

 The Dining Philosophers 문제

 

철학자들은 오른쪽, 왼쪽 2개의 포크를 사용해야 식사를 끝낼 수 있다.

위 그림처럼 둥근 테이블에 철학자 5명이 있고, 포크가 사이에 5개가 있다고 하자.

 

만약 모든 철학자가 동시에 자신의 왼쪽의 포크를 집게 된다면 문제가 발생한다.

p1 철학자는 f1을 가지고 있고 f2를 가질 수 있을 때까지 기다리게 된다.

하지만 f2포크는 p2철학자가 가지고 있고, p2철학자는 f3를 기다리는 상황이다.

이러한 상황들이 얽히면서 모두가 아무것도 할 수 없는 deadlock상황이 발생한다.

 

이러한 경우 해결방법은

예를 들어 p4 철학자만 왼손이 아닌 오른손의 포크를 먼저 사용하게 하면 해결될 수 있다.