7. Synchronization Examples

◆ Synchronization Examples

Synchronization에 관한 고전적인 문제들이 있다.

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

 

각각을 어떻게 해결하는지 알아볼 것임.

 

---

◆ Bounded-Buffer Problem (Producer/Consumer Problem)

버퍼에 (producer가 생산한) item이 있는 경우에만 consumer가 접근해서 사용할 수 있도록 하는 문제.

개수가 n개로 고정(bound)되어 있다고 버퍼가 있다고 하자.

각 버퍼는 하나의 아이템만 홀드할 수 있다. (full 또는 empty 둘 중 하나의 상태일 것이다)

 

버퍼가 여러 프로세스에 의해 공유된다고 가정하자.

버퍼에 접근하는 프로세스로는 producer과 consumer가 존재하며, 다음과 같이 작동한다.

• producer : 데이터를 만들어서 버퍼에 집어넣음
• consumer : 버퍼에서 데이터를 꺼내서 씀

 

이런 경우 발생할 수 있는 동기화 문제를 Bounded-Buffer Problem이라고 한다.

 

 

여기서는, 다음 세 개의 세마포어를 이용해서 문제를 해결해 볼 것이다.

• mutex 세마포어 : 누군가가 접근하고 있으면 다른 사람이 접근하지 못하도록 함. 초기값 1
• full 세마포어 : 아이템이 들어있는 버퍼의 개수. 초기값 0
• empty 세마포어 : 비어있는 버퍼의 개수. 초기값 n

 

이들을 사용해 producer과 consumer을 구현해보자.

 

 

producer의 경우, empty인 버퍼가 있어야만 item을 집어넣을 수 있다. 따라서 empty 세마포어가 0인 동안에는 wait를 한다.

비로소 empty인 버퍼가 생기면, mutex 세마포어를 활용해 안전하게 크리티컬 섹션에 들어간다.

item 생산이 완료되면, full 세마포어 값을 늘린다.

 

※ 세마포어에서 wait 및 signal
ㆍwait은 세마포어의 값이 0보다 작거나 같을 때 기다리고, 0보다 커지면 해당 세마포어 값을 1 줄인다.
ㆍsignal은 세마포어의 값을 1 늘린다.

(자세한 내용은 6장 포스팅에 설명되어있다.)

 

 

consumer의 경우, item이 들어있는 버퍼로부터 꺼내서 써야 하므로, full 세마포어가 0보다 작거나 같은 경우 기다린다.

full인 버퍼가 생겼다면, mutex 세마포어를 사용해 크리티컬 섹션에 들어가 item을 꺼내 쓴다.

그리고 내가 썼으니, empty 세마포어 값을 늘린다.

 

 

---

◆ Readers-Writers Problem

reader끼리는 동시에 접근 가능하되, writer은 혼자서만 접근할 수 있도록 하는 문제

데이터셋이 여러 프로세스에 의해서 공유되고 있다고 가정하자.

공유되는 데이터셋에 접근하는 프로세스는 reader와 writer가 있다. 

• reader : 데이터를 읽기만 함
• writer : 데이터를 수정함

 

reader의 경우, 읽기만 하므로 동기화 문제를 고려할 필요는 없다. 따라서 reader 여러 명이 동시에 접근해도 괜찮다.

그러나 writer의 경우, 데이터를 수정하기 때문에, 한번에 한 명씩만 접근하도록 해야 한다. 다른 writer 및 reader가 접근해서는 안된다.

 

이런 동기화 문제를 해결하는 솔루션으로,

reader 와 writer 중 누구에게 우선권을 주는지에 관련하여 두가지 경우가 존재한다.

1. reader에게 우선권을 주는 방법
   : writer가 쓰지 않고 있는 경우, 항상 reader에게 우선권을 주는 방법
2. writer에게 우선권을 주는 방법
   : writer가 준비되어 있는 경우, 항상 reader보다 먼저 접근할 수 있도록 하는 방법

 

예제에서는 1번 방식으로 문제를 해결할 것이다.

 

< 1번 솔루션 >

reader는 다음 세가지 변수 및 세마포어를 공유한다.

• int read_count
  읽고있는 reader의 수를 의미함. 크리티컬 섹션에서 ++ 및 --되어야 하며, 초기값은 0
• mutex 세마포어
  read_count 변수를 수정하는 크리티컬 섹션을 위한 세마포어. 초기값은 1
• rw_mutex 세마포어
  writer가 자원을 수정할 수 있는지를 의미함. 초기값은 1

 

이런 방식으로 구현할 수 있다.

내가 이 데이터를 읽고싶어!

그러면 우선, wait(mutex)를 통해 read_count 변수를 수정중인 프로세스가 없을 때까지 기다린다.

없다면 크리티컬 섹션에 들어가서 read_count를 ++한다. 

이때, 내가 이 데이터에 처음으로 접근하는 reader라면, writer가 접근하지 못하도록 데이터를 잠근다. (또는 writer가 수정중인 경우 기다린다.)

 

나갈 때도 같은 방식이다.

mutex 세마포어를 사용해 안전하게 크리티컬 섹션에 진입한 후, 만약 내가 마지막 reader라면, writer에 대해 잠근 걸 풀어준다.

 

 

writer은 간단하다. 그냥 reader 또는 writer들이 rw_mutex 락을 안 해놨으면 접근할 수 있다.

즉 이 데이터를 읽고있는 reader나 쓰고있는 writer가 아무도 없는 경우에 접근할 수 있다.

접근할 때 다른 reader나 writer들이 들어오지 못하도록 wait(rw_mutex)한다.

 

 

근데 writer가 쓰고있을 때 reader가 접근하면 어떡하지?

라는 고민을 했었는데, 그럴 필요가 없었다. 

만약 writer가 쓰고 있다면 rw_mutex == 0이라, 처음 들어오는 reader가 if문 속에서 rw_mutex를 wait한다.

다음으로 들어오는 reader들의 경우, 첫 reader가 아직 mutex 세마포어를 signal 하지 않았기 때문에 mutext 를 wait하며, read_count++에도 못 들어가고 기다리게 된다. 

 

※ 두 방법 모두 starvation을 유발할 수 있다.

첫번째 방법은 writer가 starvation이 일어날 수 있고,
두번째 방법은 reader가 starvation이 일어날 수 있다.

이 문제는 reader-writer lock을 제공하는 커널 시스템에 의해 해결될 수 있다.

 

※ 시험문제예시
r/w 문제를 조금 변형한 sync 프라블럼에 대해, 이를 해결하려면 어떤식으로 세마포어 사용해야할까?
-어떤 세마포어가 필요하고, 어떤식으로 초기화할지 생각해봐야 함

 

---

◆ Dinning-Philosophers Problem

양 옆 젓가락을 들어야 음식을 먹을 수 있는 상황에 대한 문제

N명의 철학자들이 둥근 테이블에 앉아서 식사를 하고 있다고 가정하자.

테이블 중앙에는 음식이 있다.

두 명 사이에 하나의 젓가락이 놓여있으며,

자신의 양 옆 젓가락을 한개씩 가져와 총 두 개의 젓가락을 들어야만 음식을 먹을 수 있다.

 

 

철학자들이 할 수 있는 행동은 다음 두 가지이다.

• 가만히 생각을 한다.
• 음식을 먹는다.

 

이때 발생할 수 있는 세 가지 문제가 있다. 

• 상호 배제 (Mutual Exclusion)
• 교착 상태 (DeadLock)
• 기아 현상 (Starvation)

 

이 세 문제에 대, 두 가지 해결안을 살펴보자.

• 세마포어 사용
• 모니터 사용

 

---

◆ Dinning-Philosophers Problem
: 해결안 1. 세마포어 사용

모든 사람이 순차적으로 젓가락을 들 수 있도록 한다. (왼쪽 젓가락을 오른쪽 젓가락보다 먼저 들어야 하도록 함)

초기 상태: 사람 5명, 젓가락 5개

실행 과정: 5명의 사람이 순차적으로(왼쪽 젓가락 먼저 들기) 사용하지 않은 젓가락을 1개씩 집으면서 2개의 쌍을 맞춘다. 그리고 밥을 먹은 후 젓가락을 내려 놓는다. 이 과정을 무수히 빠르게 진행한다.

문제 발생 시점: 5명의 사람 모두 젓가락을 1개씩 집은 상황을 가정하자. 젓가락 5개가 모두 사용중이지만 5명 누구도 식사를 하지 못한다. 여기서 젓가락을 나눠주지도 못하므로 5명이 젓가락 1개씩 들고 하루 종일 밥만 구경하는 교착(Deadlock)상태에 걸려 무한히 대기한다. 이렇게 한번 교착상태에 빠진 철학자들은 계속 고뇌만 하다가 기아현상(Starvation)으로 굶어 죽는다.

 

 

해결안 평가 :

• 상호 배제 (Mutual Exclusion) → 해결
• 교착 상태 (DeadLock) → 미해결
  : 5명이 젓가락 1개씩만을 들고 아무것도 못하면서 대기하는 상황이 발생할 수 있다.
• 기아 현상 (Starvation) → 미해결
  : 교착 상태에 빠지고 나면 계속 고뇌만 하다가 굶어죽게 된다.

 

---

◆ Dinning-Philosophers Problem
: 해결안 2. 모니터 사용

모든 사람은 자신의 양쪽 젓가락을 모두 얻을 수 있을 때만 젓가락을 집을 수 있도록 한다.

 

1. 이 해결안을 구현하려면, 철학자가 처할 수 있는 세가지 상태를 구분해야 한다.

enum {THINKING, HUNGRY, EATING} state[5];

• EATING 상태는 식사중인 상태로, 젓가락 두 개를 모두 획득한 상태를 의미한다.
  철학자 i는 그의 양쪽 두 이웃이 식사하지 않을 때만 상태를 EATING으로 설정할 수 있다.
  (조건 (state[(i+4)%5] != EATING) 그리고 (state[(i+1)%5] != EATING)이 성립할 때만).
• HUNGRY 상태는 젓가락을 들고있지는 않으나, 젓가락을 들고싶어하는 상태이다.
• THNIKING 상태는 젓가락을 들고있지 않으며, 젓가락을 필요로 하지도 않는 상태이다.

 

2. 그리고 다음을 condition 변수 self를 선언한다.

condition self[5];

self는 철학자 i가 배고프지만, 자신이 원하는 젓가락을 집을 수 없을 때, 젓가락 집기를 미룰 수 있도록 한다. (self[i].wait)

 

 

3. 이제 모니터를 사용한 해결안 코드를 보자.

젓가락의 분배는 모니터 DiningPhilosophers에 의해 제어된다.

• 각 철학자는 식사하기 전에 pickup() 연산을 반드시 호출해야 한다.
  이는 젓가락을 요청했다는 의미이므로, 상태를 HUNGRY로 바꾸고, 젓가락을 잡을 수 있는지 확인한다. (test(i))
  - 이때 젓가락을 잡은 경우 그대로 식사하고,
  - 젓가락을 잡지 못한 경우 내 조건 변수의 wait을 사용해 모니터 안에서 기다린다. 

• test 함수에서는, 만약 내가 HUNGRY 상태이고, 양 옆 사람이 식사중이 아닌 경우에,
  내가 식사를 할 수 있도록 하고 내 조건 변수를 푼다.

• 식사를 마친 후, 철학자는 putdown() 연산을 호출한다.
  상태를 THINKING으로 바꾸고, 내가 젓가락을 내려놨다는 사실을 양 옆 사람들에게 알려준다. 
  (양 옆 사람들이 기다리고 있을 수 있으니, 내가 젓가락을 내려놓은 시점에서 양 옆 사람 입장에서 test()를 해준다)

 

※ 철학자들은 반드시 pickup() 과 putdown() 연산을 순서대로 호출해야 한다!!!

 

 

해결안 평가 :

• 상호 배제 (Mutual Exclusion) → 해결
• 교착 상태 (DeadLock) → 해결
• 기아 현상 (Starvation) → 미해결
  : 한 철학자가 배가 고파 젓가락을 집고자 해도 다른 철학자가 계속 빠르게 선점하여 젓가락을 집는다면 철학자는 굶어죽게 된다.
  
  

---

◆ Linux에서 실제로 Synchronization을 위해 제공하는 툴들

 

커널 2.6은 완전히 preemptive하다.

즉, 동기화를 위해 인터럽트를 disable하는 대신에, 다른 sync툴을 사용해 제공한다는 것

• Semaphores
• Atomic integers
• Spinlocks
• Reader-writer version of both

 

※ 싱글 코어에서는 단순히 preemption을 disable하는 방식으로 사용해도 됨.

 

---

◆ Atomic Variable

atomic variable에 관련된 operation들이 atomic하게 동작하는 것을 보장함.

atomic_t 를 통해 atomic한 정수 변수를 정의하다.

 

이 연산들을 실행하는 동안에는, 이 스레드가 다른 스레드에 의해 수정되지 않도록 함.

Race condition이 생기지 않게끔 지원해준다는 것!

 

---

◆ POSIX Synchronization

POSIX API는 다음 세 가지 툴을 제공한다.

• Mutex locks
• Semaphores
  - Named Semaphores : 세마포어의 이름을 통해 해당 세마포어에 접근 가능
  - Unnamed Semapores : 이름이 따로 없으므로, 프로세스가 해당 세마포어를 공유하려면 다른 방식(공유 메모리 등)을 사용해야 함
• Condition variable