[운영체제] 5. Concurrency: Semaphores and Deadlock1

Condition Variables(상태 변수)

상호배제와 동기화(순서 관계)를 제공할 수 있는 API

• pthread_cond_wait: run 상태의 쓰레드를 sleep 상태로 바꾸어 sleep 큐에 넣는 API
• pthread_cond_signal: sleep 큐에 존재하는 쓰레드를 깨워 스케쥴링 될 수 있는 ready 상태로 바꾸는 API

순서 관계가 필요한 예제

 

순서관계를 제공하는 방법

1. Busy waiting(spin): 성능이 좋지 않으며 자식이 많을 경우 문제가 생길 수 있다.

2. Codition variable: 성능도 좋으며 정확성을 보장한다.

Spin 기반 접근과 상태 변수 접근

---

생산자/소비자 문제 (Producer/Consumer Problem; Bounded Buffer Problem)

유한한 개수의 생산품을 보관하는 버퍼에 여러명의 생산자와, 소비자가 접근할 경우 적절한 동기화를 제공하여야한다. 현실 세계에서 DB, streaming server, pipe, cache 등이 이에 해당한다.

 

 

Version1-기본구조: 공유자원이나 버퍼의 수를 고려하지 않은 형태

count가 0일 경우 비어있음, 1일 경우 가득 찼음을 의미한다.

 

Version2-공유를 고려: locks과 codition variables를 사용.

생산자가 count가 가득 찬 것을 의미하는 1일 경우에는 생산을 중지하여 sleep 상태로 전이하고, consumer는 count가 0인 비어있는 경우에 소비를 중지하는 sleep 상태로 전이한다.

 

Version2에서 발생하는 문제점

  소비자1이 먼저 수행되고, c3에서 버퍼에 아이템이 없는 것을 알고 sleep 상태로 들어간다. 이후 생산자가 수행되어 제품을 생산하여 소비자1을 깨우고, 계속 수행되다가 아이템이 생산되어 버퍼가 가득찼음을 알고 p3에서 sleep 상태로 들어간다. 이때 소비자2가 수행되고 해당 아이템을 찾아서 사용한다. 이후 소비자1이 수행되어 아이템을 획득하려 하는데 소비자2가 이미 가져간 상태가 발생한다.

  위는 소비자와 생산자가 한 명일 경우에만 잘 동작한다. 해결책은 if를 while로 교체하여 다시 스케쥴링이 넘어왔을때 버퍼의 상태를 다시 한번 확인하는 절차가 필요하다.

 

Version3-while을 사용

Version3에서 발생하는 문제점

  소비자1이 먼저 수행되고 버퍼가 없어 sleep 상태로 들어간다. 소비자2가 수행되고 역시 sleep 상태로 들어간다. 생산자가 수행되고 아이템을 생산하고 소비자1을 깨운 뒤 버퍼가 가득차 sleep 상태로 들어간다. 소비자1이 수행되어 해당 아이템을 사용한 뒤, signal로 생산자가 아닌 소비자가2가 깨워지게 된다. 버퍼가 비어있어 sleep 상태로 들어간다. 소비자2가 수행되고 버퍼가 비어있는걸 보고 sleep 상태로 들어간다. 이렇게 소비자1, 소비자2, 생산자 모두 sleep 상태에 들어가게 되어 데드락이 발생한다.

 

위는 소비자1이 생산자를 깨우지 않고 소비자2을 깨웠기에 발생한 문제이다. 위를 해결하기 위해서는 생산자와 소비자는 서로 다른 상태변수를 사용하여야 한다.

 

Version4 - 두개의 상태변수와 다수의 버퍼

위가 최종적으로 다수의 생산자와 소비자가 버퍼에 접근하는 상황에서 안정적인 구현 버젼이다.

---

pthread_cond_broadcast

sleep 큐에 존재하는 모든 쓰레드를 ready 상태로 바꾸는 API

활용 예시. 현재 메모리를 할당 받으려하는 쓰레드 A,B가 존재한다. 쓰레드 A는 100byte가 필요하고 쓰레드B는 10byte가 필요하다. 이 두 쓰레드는 현재 sleep 상태이다. 방금 막 50byte의 메모리 공간이 생겨, signal을 통해 쓰레드 A가 깨어날 경우 공간이 부족해서 다시 sleep 상태로 바뀌게 된다. 이때의 해결책이 pthread_cond_broadcast이다.

---

Semaphores

병행성 제어를 위한 자료구조로 정수 값을 가진 객체이다. Lock이나 Condition variable 처럼 사용된다. 0과 1의 값을 갖는 binary semaphore와 그 외의 정수 값도 가질 수 있는 counting semaphore로 분류된다.

• sem_init: 초기 세마포어의 정수값을 초기화
• sem_wait: 값을 감소시키고 값이 0 미만이 될 경우 해당 쓰레드는 sleep 상태로 전이된다.
• sem_post: 값을 증가시키고 semaphore에 대응하는 sleep 상태의 쓰레드가 있다면 깨운다.

Binary Semaphores (Locks): 초기값으로 1을 주어 lock의 형태로 사용한다.
Counting Semaphores: 초기값으로 0을 주어 condition variable의 형태로 사용한다.

 

Semaphore를 이용한 생산자/소비자 문제

상태변수를 이용한 해결책과의 차이점은 count 변수가 존재하지 않으며, 상태변수 해결책과는 반대로 동기화 후에 상호배제를 거친다(Ordering and Mutex).

(만약, mutex and ordering의 과정을 거치게 구현한다면 데드락이 발생하게 된다.)

---

독자/저자 문제 (Reader/Writer Problem)

여러 명의 독자와 저자가 하나의 저장 공간을 공유하여 생길 수 있는 문제이다. 때로는 여러명의 독자가 데이터에 접근하는 것이 가능하다. 저자는 공유공간에 데이터를 저장한다. 생산자/소비자 문제와의 차이점은 생산자/소비자 무제는 상호배제가 항상 보장되어야 한다. 독자/저자에서는 상호배제가 필요하긴 하지만 다수의 독자 상황에서는 불필요하다. 독자들은 임계영역의 변화를 주지 않기 때문이다.

 

구현방식

독자에 대한 상호배제를 위한 lock과 한명의 저자 혹은 다수의 독자들만 허용할 수 있게 하는 writelock을 통해 구현한다.

예시1. 빨간색 포인터

저자1이 먼저 writelock을 잡으려 시도한다. writelock의 세마포어 값은 0이 되고 저자1은 임계영역에 접근하게 된다. 이후 저자2가 접근하는데 writelock의 세마포어 값이 -1이 되어 sleep 상태로 전이된다.

이후 독자1이 readlock을 습득하려 한다. lock의 세마포어 값은 0이 되어 임계 영역에 접근하게 된다.  독자의 수를 카운팅 하는 값을 1 증가시키고, 첫 독자의 접근이므로 writelock을 잡으려고 시도하지만 writelock의 세마포어 값이 -2가 되어 sleep 상태로 전이하게 된다. 이후 독자2도 접근하지만 lock의 세마포어 값이 -1이 되어 sleep 상태로 전이한다.

writelock의 sleep 큐: 저자2, 독자1
lock의 sleep 큐: 독자2

 

예시2. 파란색 포인터

독자1이 먼저 readlock을 잡으려 시도한다. lock의 값이 0이 되어 임계영역에 접근하고 첫  독자의 접근이므로 writelock의 습득 시도에도 성공하게된다. 이후 sem_post를 통해 lock의 값을 다시 증가시켜 1이된다.

이후 저자1이 writelock을 잡으려 하지만 값이 -1이 되어 sleep 상태로 전이된다. 그리고 독자2, 3이 차례로 lock에 대한 임계영역에 들어올 수 있게 된다.

---

식사하는 철학자 문제(The Dining Philosophers)

5명의 철학자가 원형의 식탁에 앉아 있다. 양 철학자 사이에는 하나의 포크가 있어 식탁에 총 5개의 포크가 존재한다. 철학자들은 각자 시간들 들여 생각한 뒤 음식을 먹는 행위를 반복한다. 식사를 하기 위해서 철학자는 양 옆의 포크를 모두 사용하여야 한다.

 

단순한 해결책: 포크를 잡고 놓는 행위에 대해 semaphore를 이용하여 해결한다.

위 해결책의 문제점. 철학자 5명이 동시에 도착하여 모두 왼쪽 포크를 집게 될 경우 데드락이 발생하게 된다.

 

새로운 해결책

1. 순서관계를 깬다. (의존성의 제거)
2. 동시에 식사 가능한 철학자의 수를 제한한다.
3. Monitor를 사용하여 두개의 포크를 모두 잡거나 그렇지 않는 것을 보장한다.
4. 더 많은 포크를 둔다. (자원 수의 증대)