[Philosophers] 식사하는 철학자 문제 소개

hidaehyunlee·2021년 3월 21일
1

42SEOUL

목록 보기
26/27

1. Dining philosophers problem 소개

OS의 교착상태를 설명하기 위한 유명한 문제라고 한다. 무려 1965년에 고안된 문제. 위 그림에서는 5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.

  1. 일정 시간 생각을 한다.
  2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
  3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
  4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
  5. 오른쪽 포크를 내려놓는다.
  6. 왼쪽 포크를 내려놓는다.
  7. 다시 1번으로 돌아간다.

만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면, 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다. 그런데 모든 철학자들이 그러고 있다. 이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 개수가 없게 되는데, 이것이 교착(Deadlock)상태이다.

  • 더 자세한 내용은 위키 참고.

2. Dining philosophers problem 해결 방법

출처 : Kukim 님 블로그

Philosophers 과제에서는 이 문제를 3가지 방법으로 프로그램을 만들어 구현한다.

2.1. Program 1

philo_one : Mutex

  • 철학자는 쓰레드이다.
  • 원탁에 앉아있고, 양 옆에 포크가 있다.

2.2. Program 2

philo_two : Semaphore

  • 철학자는 쓰레드이다.
  • 원탁에 앉아있고, 테이블 중앙에 포크가 있다.
  • They have no states in memory but the number of available forks is represented by a semaphore.

2.3. Program 3

philo_three : shared memory

  • 철학자는 프로세스이다.
  • 원탁에 앉아있고, 테이블 중앙에 포크가 있다.
  • 단, main process는 철학자여서는 안 된다. (the main precess sholdn't be a philosopher)
profile
삽질의 기록들 👨‍💻

0개의 댓글