16. 철학자들은 왜 굶어 죽었을까?: Chapter 7. Synchronization Examples (Part 2)

HotFried·2023년 9월 18일

Operating System

운영체제(Operating System)

목록 보기

16/22

Dining-Philosophers Problem

다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에는 음식과 양옆에 포크가 하나씩 있다.

이 철학자들은 먹고 생각하는 두 가지 활동을 번갈아 한다.
철학자는 먹고 싶을 때는 양 옆의 두 개의 젓가락을 사용해야 한다.
젓가락은 인접한 철학자만 사용할 수 있으며 동시에 두 명이 사용할 수 없다.
철학자는 식사를 마치고 두 젓가락을 원래 위치에 내려놓은 뒤 생각에 잠긴다.

→ 여러 개의 Resources가 Process들 사이에 공유된다.

→ Deadlock, Starvation(기아)가 발생할 수 있다.

간단한 해결 방법

semaphore chopstick[5];

while (true) {
  wait(chopstick[i]);
  wait(chopstick[(i+1) % 5]); //두개씩 집는다.
  ...
  /* eat for a while */
  ...
  signal(chopstick[i]);
  signal(chopstick[(i+1) % 5]); //젓가락을 내려놓는다.
  ...
  /* think for awhile */
  ...
}

세마포어를 이용해 상호배제 문제를 해결했지만,

Deadlock, Starvation(기아)가 발생한다.

→ 만약 5명의 철학자가 동시에 배가 고파졌다. 5명이 왼쪽의 젓가락을 동시에 집고 오른쪽 젓가락을 집으려고 하면…?? ⇒ 젓가락이 없어서 Deadlock이 발생한다.

Deadlock에 대한 해결책

4명의 철학자만 테이블에 동시에 앉을 수 있도록 한다.
왼쪽과 오른쪽 젓가락을 모두 사용할 수 있는 경우에만 젓가락을 집을 수 있게 한다.
짝수 번째 철학자들은 자신의 왼쪽에 있는 젓가락부터, 홀수 번째 철학자들은 자신의 오른쪽에 있는 젓가락부터 집어 들도록 한다.

→ 하지만 이런 방법들은 Starvation(기아)를 해결하지는 못한다.

모니터 해결책(Monitor Solution)

왼쪽과 오른쪽 젓가락을 모두 사용할 수 있는 경우에만 젓가락을 집을 수 있게 한다.
철학자들의 상태를 Thinking, Hungry, Eating 세 가지로 구분한다.
왼쪽, 오른쪽의 철학자가 Eating상태가 아닐 때 본인의 상태를 Eating으로 바꿀 수 있다.

→ 모니터 해결책 또한 Starvation(기아)는 해결하지 못한다.

Code

monitor DiningPhilosophers
{
  enum {THINKING, HUNGRY, EATING} state[5];
  condition self[5]; //Condition Variable

  void pickup(int i) {
    state[i] = HUNGRY;
    test(i);
    if (state[i] != EATING)
	    self[i].wait();
  }

  void putdown(int i) {
    state[i] = THINKING;
    test((i + 4) % 5);
    test((i + 1) % 5);
  }

  void test(int i) {
	  if ((state[(i + 4) % 5] != EATING) &&
		  (state[i] == HUNGRY) &&
		  (state[(i + 1) % 5] != EATING)) {
			  state[i] = EATING;
			  self[i].signal();
		 }
  }

  initialization code() {
  for (int i = 0; i < 5; i++)
  state[i] = THINKING;
  }
}