9. 운영체제 Semaphore

Semaphore Variables

• semaphore variable은 lock과 condition variable의 역할을 동시에 할 수 있다.

 

Semaphore Functions 

• sem_init()
  • 세마포어를 초기화
  • 0이면, 쓰레드간 공유
  • 0이 아니면, 프로세스간 공유
• sem_wait()
  • 변수를 감소시킴
  • 감소된 변수가 음수가 되면, 호출한 쓰레드는 sleep 상태로 들어감
• sem_post()
  • 변수를 증가시킴
  • 호출한 쓰레드는 즉시 리턴되고, sleeping 쓰레드는 깨움

 

Semaphore as Locks

• sem_init()과 sem_post()를 통해서 lock을 만들 수 있음
• lock은 acquired와 released 두 가지 state를 가지므로 Semaphore as Locks는 binary semaphore라고 불림
• 예시1
  

  

• 예시2

 

Semaphore as Condition Variables

• inital value의 설정을 통해 condition variable로 동작할 수 있음
• sem_wait()은 sem_post() 호출 전까지 대기함
  

  

• 예시1
  

  

• 예시2
  

  

---

Producer-Consumer Problem

• Producer-Consumer 문제를 세마포어로 작성해보자.

 

Race Condition in Producer-Consumer Problem

1. data를 생성하는 producer1과 producer2가 있다.
2. producer1이 먼저 실행되고 이 때 back 변수는 -1이다.
3. producer1이 put()함수를 실행하기 전에 context switching이 발생하여 producer2가 실행된다.
4. producer2는 여전히 back을 -1로 읽으므로 1을 증가시켜 0으로 만들고, queue[0]에 data를 삽입한다.
5. 다시 producer1으로 context switching이  발생하고, back을 -1로 인식하는 producer1이 back을 0으로 업데이트한 후 queue[0]에 data를 삽입한다.
6. queue[0]에 data가 중복으로 작성된다.

→ 공유되는 변수(back)에는 mutual exclusion을 위한 별도의 lock 세마포어가 필요하다.

 

Deadlock in Producer-Consumer Problem

1. producer와 consumer가 있다.
2. consumer가 먼저 실행되어 lock을 획득한다. 그런데 queue가 empty이므로 data를 꺼내지 못하고 sem_wait()에서 sleep상태가 된다.
3. 다음으로 producer가 실행되지만 lock을 획득하지 못하여 실행되지 않는다.
4. producer는 lock을 기다리고, consumer는 signal을 기다리며 deadlock이 발생한다.

→ 락의 위치를 바꾸면 해결된다.

 

Dining Philosophers

• 5명의 철학자가 원형 테이블에 앉아있다. 그들이 식사를 하려면 두 개의 포크가 필요하다.

 

Skeleton Functions for Dining Philosophers

• 각각의 철학자들에 대한 반복문
  

  

• 포크 루틴
  

  

• 포크를 선택
  

  

 

Deadlock 시나리오

• 모든 철학자들이 동시에 왼쪽 포크를 잡으면, 아무도 오른쪽 포크를 잡을 수 없다. 따라서 모든 철학자들이 오른쪽 포크가 생길 때까지 멈춰버리는 deadlock이 발생한다.
• Breaking the Cycle
  가장 단순한 솔루션은 한 명의 철학자만 오른쪽 포크를 먼저 잡게 해서 싸이클을 없애는 것이다.