Traditional synchronization example / Producer and Consumer problem

Traditional synchronization example

 

   - producer and consumer problem

 

   - Readers and Writers problem

 

   - Dining Philosopher problem

 

Producer and Consumer problem

 

  - 생산자는 일방적으로 데이터를 생성하고, 소비자는 그것을 소비하는 상황에서 발생하는 문제이다.

 

  - 생산자와 소비자의 데이터 처리 속도 차이로, 생산된 데이터를 날리는 것이 아닌 유한 크기 버퍼(bounded buffer)에 임시 저장하고, 소비자는 이를 차례로 사용하는 상황을 생각해보자.

 

   Pro1 _ Critical section 

   

   : 우선 버퍼 크기를 알 수 있는 buffer_count 변수가 생성자에 의해선 증가하고, 동시에 소비자에 의해선 감소할 것이다. 이것이 critical section이 된다. 이는 세마포어로 해당 임계 구역에 진입 가능한 수의 제한을 1로 하는 것으로, 동시에 buffer_count를 엑세스하지 않도록 할 수 있다. (semaphore value = 1)

 

  void produce(){

sem.wait();

      buffer_count++

      buffer.add(data)

sem.signal()

}

 

  Pro 2 _ busy wait 

   

   : producer는 buffer에 자리가 남아있어야 데이터를 저장할 수 있다. 반대로 자리가 남아있지 않는다면 그때까지 대기할 것이다. consumer은 buffer에 데이터가 남아있어야 데이터를 저장할 수 있다. 반대로 데이터가 남아있지 않는다면 그때까지 대기할 것이다.

 

void produce(){

       if(buffer_count == buffer.Size)

          while(buffer_count < buffer.Size)

}

  

 - 이런 절차는 상대의 태도에 의해 무한 루프를 빠질 수 있게하여 큰 문제를 야기할 뿐더러 CPU가무한한 대기를 반복하는 것으로 자원을 소비한다. 이 역시 세마포어를 이용해서 버퍼가 꽉찰 시에는 이후 데이터 추가 프로세스를 block하고 semaphore queue(list)에 넣어두고 소비자 측에서 소비하는 것으로 wakeUp 해주는 식으로 처리할 수 있다.

 

- 마찬가지로 버퍼가 비었을 시에는 이후 데이터 사용 프로세스를 block하고 semaphore queue에 넣어두었다가, 생산자 측에서 데이터를 생성했을 때 wakeUp 해주는 식으로 처리하여 busy wait 문제를 해결한다.

(empty_sem.value = buffer.size , full_sem.value = 0)

 

void produce(){

      empty_sem.wait()

      mutex.wait()

      ////CA/////

      mutex.signal()

      full_sem.signal

 

void consume(){

      full_sem.wait()

      mutex.wait()

      ////CA/////

      mutex.signal()

      empty_sem.signal

 

Readers and Writers 

 

   - 데이터 베이스와 같은 공유 자원를 엑세스하는 Reader 와 Writer의 제한 문제이다.

 

   - 단순히 세마포어로 공유 자원에 접근하는 개체 수를 제한하는 것이 아닌, Reader 끼리는 공유 자원을 동시에 사용해도 되고, Writer가 엑세스 하는 동안에는 Writer, Reader 모두 제한된다.

 

Dining Philosopher

 

   - 공유 자원을 동기화하는 과정에서 Dead Lock이 발생하는 예시를 보여준다.

 

Dining Philosopher

   - 원탁에서 철학자들이 식사를 하고 있다. 철학자들은 식사와 고민을 반복하고, 두명이 한 젓가락을 공유하여 식사를 한다. 젓가락마다 value가 1인 Semaphore을 두고, 철학자의 식사 시간을 다음과 같이 구현하였다.

 

void mealtime(){

   left.acquire()

   right.acquire()

   eat()

   left.acquire()

   right.release()

}

 

   - 이렇게 코드를 작성하면 중복 접근 없이 안전할 것이라고 생각할 수 있으나 이는 문제가 있다. 만약 모든 철학자가 자신의 왼쪽 젓가락을 acquire하고, 오른쪽의 젓가락을 접근하고자 대기한다면 모든 철학자가 대기만 하고 자신의 젓가락을 release하지 않아, 테이블이 무한 대기에 걸려버리는 것이다.  이를 Dead Lock이라고 한다.

 

   - Dead Lock을 처리하기 위한 여러 솔루션이 존재하지만, 간단한 것은 철학자들이 한쪽 방향 (ex, 왼쪽)으로 선접근하는 것을 막으면 모두 대기하는 일이 없어질 것이다. 철학자에게 번호를 부여하여, 홀수번 철학자는 왼쪽, 짝수번 철학자는 오른쪽부터 엑세스 하도록 하는 것으로 Dining Philosopher 문제를 해결한다.