0x10. Problem

0x11. situation

• N명의 철학자(philosopher)가 원형 테이블에 앉아 있음
• 각 철학자 사이에는 포크(fork)가 하나씩 존재 (총 N개)

이 젓가락 대신 상태로 shared resource 추상화

• 철학자는 세 가지 상태 반복:

  • 생각(thinking)
  • 먹기(eating)
  • hungry

• 먹기 위해서는:

  • 왼쪽 포크 + 오른쪽 포크 둘 다 필요

0x12. problem aspect

deadlock PS

• 모든 철학자가:
  • 왼쪽 포크만 잡고
  • 오른쪽 포크를 기다림 → 아무도 먹지 못함 (영원히)

[(draft yet): starvation]

• 특정 철학자는 계속 포크를 못 얻을 수 있음

0x20. IDEA

0x21. IDEA1: pick up only both

DEF

• 두 포크를 한 번에 같이 얻을 수 있을 때만 집는다
• 아니면 아무 것도 안 잡고 대기

HOW

deadlock PS 발생 조건중 hold-and-wait를 없앰

0x22. IDEA2: asymmetric coding

DEF

• 짝수: 왼쪽 → 오른쪽
• 홀수: 오른쪽 → 왼쪽

HOW

deadlock PS 발생 조건중 circular waiting을 없앰

• 모두 같은 방향으로 resource 요청하지 않음
• cycle 구조 형성 불가능

0x23. IDEA3: allow at most 4 to sit together

DEF

• 동시에 식사 시도 가능한 철학자 수를 N-1로 제한

HOW

deadlock PS 발생 조건중 circular waiting을 "간접적으로" 없앰

• 모든 사람이 동시에 resource chain 만들 수 없음
• 반드시 빈 slot 존재 → cycle 끊김

0x30. IMPL

0x31. idea1 with Monitor

monitor dining_philosopher
{
	enum { thinking, eating, hungry } state[5];
	condition self[5]; 
	
	void pickup(int i) {
		state[i] = hungry;
		test(i);
		while (state[i] != eating) {
			self[i].wait();
		}
	}
	
	void putdown(int i) {
		state[i] = thinking;
		int left = (i+4) % 5;
		int right = (i+1) % 5;
		test(left);
		test(right);
	}
	
	void test(int i) {
		int left = (i+4) % 5;
		int right = (i+1) % 5;
		if (
			state[left] != eating
			&& state[right] != eating
			&& state[i] == hungry 
		) {
			state[i] = eating;
			self[i].signal();
		}
	}
	
	void init() {
		for (int i = 0; i < 5; i++) {
			state[i] = thinking;
		}
	}
}

each Philosopher:
{
	pickup(i);
	eat();
	putdown(i);
	think();
} while (1)