Chapter 07-1. Synchronization Examples

동기화 문제에는 대표적인 3가지가 있다.

1. Bounded - Buffer Problem(Producer - Consumer Problem) - 제한된 버퍼에 데이터를 채우고 가져가는 문제

2. Readers and Writers Problem - 데이터의 공유 문제

3. Dining - Phillosopers Problem - 한 자원을 가지고 다른 자원을 요청하는 문제

 

Bounded - Buffer Problem)

기본적으로 생산자 - 소비자 문제이고 n개의 버퍼로 이루어져 있다.

데이터 공유 모델의 한 종류 이다.

int n;
semaphore mutex = 1; // -> binary semaphore
semaphore empty = n;
semaphore full = 0;

mutex는 binary semaphore로 하나의 데이터에 여러 프로세스가 동시에 접근하지 못하도록 한다.

현재 empty 버퍼의 개수는 n개 full 버퍼의 개수는 0개이다.

 

 

<Producer(생산자)>

wait(empty): empty buffer가 생길 때까지 기다린다. item을 추가해서 n-1개의 empty buffer를 가짐

wait(mutex): 다른 프로세스의 critical section이 끝날 때까지 기다린다.

--write--

signal(mutex): critical section에서 탈출하고 mutex를 반납한다.

signal(full): semaphore full에 하나를 추가시킨다.

 

n+1번 실행되면 wait(empty) 조건에 의해 producer는 block 된다. 더 이상 새 버퍼를 넣을 공간이 없기 때문이다.

 

<Consumer(소비자)>

wait(full): full buffer가 생길 때까지 기다린다. 버퍼에 아이템이 한 번도 안 들어갔다면 -1이 되어 block에 걸린다.

wait(mutex): wait(mutex): 다른 프로세스의 critical section이 끝날 때까지 기다린다.

--write--

signal(mutex): critical section에서 탈출하고 mutex를 반납한다.

signal(empty): semaphore buffer에서 하나를 뺀다.

 

Readers - Writers Problem)

reader와 writer는 하나의 공유하는 DB를 가지고 있다. 여기서 writer는 수정, reader는 데이터를 읽어 들이는 역할을 한다.

따라서 writer가 critical section에 있을 때 다른 writer와 reader가 접근하는 것을 막아야 한다.

reader는 데이터를 읽기만 하기 때문에 무결성에 영향을 미치지 않는다. 따라서 다른 reader가 동시에 읽는 것은 허용되지만 writer가 수정하는 것은 막아야 한다.

 

do {
  wait(wrt);  // 읽고 있는 독자가 없을 때까지 기다림.
  ...
  // 쓰기 작업 수행
  ...
  signal(wrt);
} while (TRUE);

writer는 reader가 데이터에 없을 때까지 기다린다.

쓰기 작업 수행 후 siganl 함수 호출로 wrt가 증가하여 writer가 액세스 할 수 있다.

 

 

do {
  wait(mutex);
    readcount ++;  // 독자 수 1 증가.
    if (readcount == 1)
      wait(wrt);  // 쓰고 있는 저자가 없을 때까지 기다림.
  signal(mutex);
  ...
  // 읽기 작업 수행
  ...
  wait(mutex);
    readcount --;      // 독자 수 1 감소
    if (redcount == 0)
      signal(wrt);     // 독자가 없다면 이를 저자에게 알림.
  signal(mutex);
} while (TRUE);

reader는 readcount를 업데이트할 때마다 lock을 획득한다.

임계 구역 접근을 위해서는 readcount를 하나 증가시키고 critical section이 끝나면 readcount를 하나 감소시킨다.

readcount 가 0이라면 사용하고 있는 reader가 없는 것이니 writer에게 이를 알려준다.

 

Dining Philosopers Problem)

다익스트라 알고리즘으로 유명한 에츠허르 다익스트라 교수님이 고안한 문제라고 한다.

흔히 DeadLock(교착상태)가 발생할만한 상황을 가정하는 얘기이다.

 

5명의 철학자가 원탁에서 식사를 한다. 철학자들의 사이마다 포크가 한 개씩 놓여있고 다음 과정을 통해서만 식사가 가능하다.

 

1. 일정 시간 동안 생각을 한다.(wait)

2. 왼쪽 포크가 사용 가능할 때까지 대기하고 만약 사용 가능하다면 집어 든다.

3. 오른쪽 포크가 사용 가능할 때까지 대기하고 만약 사용 가능하다면 집어 든다.

4. 양손 다 포크를 들고 있으면 식사를 일정 시간 동안 한다.(task 실행)

5. 오른쪽 포크를 내려놓는다.

6. 왼쪽 포크를 내려놓는다.

7. 1번으로 돌아간다.

 

만약에 여기서 모든 철학자들이 동시에 왼쪽 포크를 집게 되면 3번 상태가 영원히 올 수 없다.

이를 DeadLock 즉 교착상태라고 부른다.

 

해결방법) Semaphore을 사용해서 젓가락을 나타내는 것이다.

wait() 함수는 포크를 들게 하고 signal()은 포크를 내려놓게 하는 것이다.

 

do {
  wait( chopstick[i] );            // 왼쪽 젓가락을 집어듬.
  wait( chopstick[ (i+i) % 5] );   // 오른쪽 젓가락을 집어듬.
  ...
  // eat
  ...
  signal( chopstick[i] );          // 왼쪽 젓가락을 내려놓음.
  signal( chopstick[ (i+1) % 5] ); // 오른쪽 젓가락을 내려놓음.
  ...
  // think
  ...
} while(TURE);

위 case는 두 명의 연속된 이웃 철학자가 동시에 먹을 수 없도록 한다.

하지만 여전히 문제가 있다. 모든 철학자가 동시에 왼쪽 포크를 집는다면 교착상태가 발생한다.

 

다른 해결방법) 

1. 짝수 명의 철학자(process)만 앉게 한다.

2. 왼쪽과 오른쪽 모두 사용 가능한 경우만 포크를 집도록 한다.

3. 짝수 번째 철학자들은 자신의 왼쪽, 홀수번째 철학자들은 자신의 오른쪽 포크부터 집게 한다.