문서 보기문서 편집수정 내역 식사하는 철학자 문제 (덤프버전으로 되돌리기) [[분류:컴퓨터 공학]][[분류:운영 체제]][[분류:알고리즘]] [include(틀:컴퓨터공학)] [[파일:The_dining_philosophers.png|align=right&width=300]] [목차] [clearfix] == 개요 == {{{+1 Dining philosophers problem}}} [[운영체제]]의 교착([[데드락]])상태를 설명하기 위한 문제. [[1965년]]에 [[에츠허르 다익스트라]]가 만든 문제이다. 식사하는 철학자 문제는 [[컴퓨터과학]]에서 동시성과 교착 상태를 설명하는 예시로, 여러 프로세스(또는 스레드)가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 직관적으로 알 수 있다. == 상세 == > 다섯 명의 철학자가 하나의 원탁에 앉아 식사를 한다. 각각의 철학자들 사이에는 포크가 하나씩 있고, 앞에는 접시가 있다. 접시 안에 든 요리는 [[스파게티]] 같은 면 요리이기 때문에 식사를 하기 위해서는 동시에 두 개의 포크가 필요하다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없으며, 번갈아가며 각자 식사하거나 생각하는 것만 가능하다. 따라서 식사를 하기 위해서는 왼쪽과 오른쪽의 인접한 철학자가 모두 식사를 하지 않고 생각하고 있어야만 한다. 또한 식사를 마치고 나면, 왼손과 오른손에 든 포크를 다른 철학자가 쓸 수 있도록 내려놓아야 한다. 이 때, 어떤 철학자도 굶지 않고 식사할 수 있도록 하는 방법은 무엇인가?[* Five philosophers dine together at the same table. Each philosopher has their own place at the table. There is a fork between each plate. The dish served is a kind of spaghetti which has to be eaten with two forks. Each philosopher can only alternately think and eat. Moreover, a philosopher can only eat their spaghetti when they have both a left and right fork. Thus two forks will only be available when their two nearest neighbors are thinking, not eating. After an individual philosopher finishes eating, they will put down both forks. The problem is how to design a regimen (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think (an issue of incomplete information). - [[https://en.wikipedia.org/wiki/Dining_philosophers_problem#Problem_statement|Wikipedia]]] === 왜 문제가 되는가? === 예를 들어, 각 철학자들이 다음의 연속된 과정을 통해 식사를 한다고 생각해보자. > 1. 일정 시간 생각을 한다. > 1. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다. > 1. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다. > 1. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다. > 1. 오른쪽 포크를 내려놓는다. > 1. 왼쪽 포크를 내려놓는다. > 1. 다시 1번으로 돌아간다. 왼쪽 포크와 오른쪽 포크를 한번에(atomic) 가져오는 것이 아니라 순서대로(sequentially) 가져오기 때문에, 모두가 왼쪽 포크부터 집어드는 이런 단순무식한 알고리즘을 가지고 있으면 문제가 생길 수밖에 없다. 5명의 철학자 전부 왼쪽 포크를 들고 있다면 오른쪽 포크를 얻으려고 할때 오른쪽 포크는 이미 상대방이 가져간 상태이고, 오른쪽 철학자의 오른쪽 역시 가져간 상태이고.. 이렇게 원탁을 한 바퀴 돌아 자기 자신까지 돌아오면 모든 철학자들이 3번 상태에 머무르며 자기 오른쪽 포크가 사용 가능해질 때까지 영원히 기다리고만 있는 교착(Deadlock) 상태에 빠지게 된다. 또한 어떤 경우에는 계속해서 양쪽 포크를 집을 수 없어 식사를 하지 못하는 기아 상태가 발생할 수도 있고, 몇몇 철학자가 다른 철학자보다 식사를 적게 하는 경우가 발생하기도 한다. === 멀티태스킹에 대한 부연설명 === "아니, 옛날 컴퓨터는 싱글코어라 동시 작업은 생각할 필요도 없는 거 아닌가?"라고 생각한다면, 운영체제가 작업을 처리하는 방식을 이해할 필요가 있다. [[운영체제]]는 사용자에게 [[멀티태스킹]]을 제공하기 위해 돌리고 있는 프로세스들을 굉장히 짧은 시간[* 최신 리눅스 커널의 경우 4[[초(단위)#s-1.4|ms]](4/1000초). 짧게 느껴질지도 모르겠지만, [[4 GHz의 벽|수 GHz의 속도로 동작하는 요즘 CPU]]는 이 시간동안 최소 수백만 번의 연산을 수행할 수 있다.] 동안 수행하고 다른 프로세스가 CPU를 사용할 수 있게 해 준다. 인간의 반응 속도는 그렇게 빠르지 않기 때문에, CPU가 동시에 여러 작업을 수행하는 것처럼 보인다. --[[잔상권|어딜 보시죠? 그건 제 잔상입니다.]]-- 문제를 단순화시켜, 두 명의 철학자와 두 개의 포크만 있다고 생각을 해 보자. 그리고 [[운영체제|중재자]]가 있어 행동을 취할 수 있는 권리를 한명에게만 할당한다. 다음의 상황을 가정해 보자.[* 철학자는 프로세스, 포크는 자원, 중재자는 OS, 한 명에게만 할당하는 상황은 싱글코어 프로세서를 상정한 것이다.] > 1. 행동권을 할당받은 철학자가 왼쪽 포크를 집는다. > 1. 그 때 --재수없게-- 중재자가 행동권을 뺏어 다른 철학자에게 넘겨준다. > 1. 행동권을 넘겨받은 철학자는 자신의 왼쪽 포크를 집고 오른쪽 포크가 돌아오길 기다린다. > 1. 중재자가 행동권을 다른 철학자에게 넘겨준다. > 1. 이 철학자도 자신의 오른쪽 포크가 돌아오기를 기다리고 있다. 위의 예시처럼 싱글코어임에도 운영체제가 선점적 멀티태스킹[* 다른 프로세스가 수행되는 중에 CPU 사용권을 뺏어서 넘길 수 있는 방식.]을 사용한다면, 충분히 교착 상태에 빠질 수 있다. == 해결법 == [include(틀:상세 내용, 문서명=인터럽트)] === OS 차원의 해결법 === 한 철학자가 한 포크를 잡는 순간, 반대쪽 포크를 잡을 때까지 포크의 사용권리를 남에게 넘길 수 없도록 하는 것이다. 현실 세계에서는 CPU의 인터럽트를 무시하는 방식[* 선점적 멀티태스킹의 Context Switching은 대개 타이머 인터럽트에 의해 발생한다.]으로 구현할 수 있다. 하지만 이는 [[커널]] 레벨에서만 가능한 방식으로, 사용자에게 인터럽트 제어권을 넘겨준다면 악의적으로 사용해 혼자 CPU를 [[처묵처묵]]하는 상황이 발생할 수 있다. 단, 멀티쓰레드 환경이라면 사용자 레벨에서 구현할 수 있는 방식이 있다. 사용자가 Semaphore나 Mutex lock등을 이용해 Critical Section(공유 자원에 Write를 수행하는 경우 등)에서 자신이 만든 다른 쓰레드가 CPU를 잡지 못하게 만들어 쓰레드간의 교착 상태를 방지할 수 있다. === 하드웨어 아키텍처 차원의 해결법 === CPU에서 관련 명령어를 제공할 경우, 이것을 이용할 수도 있다. 양쪽 포크를 동시에 잡게 하는 명령어를 사용하면 두 철학자가 동시에 하나의 포크만 잡는 상황은 벌어지지 않는다. 이런 명령어는 쪼갤 수 없는 명령어라는 의미로 Atomic Instruction이라고도 한다. === 소프트웨어 차원의 해결법 === 여러 가지 방법이 있다. 1. 타임아웃 설정. 철학자가 포크를 집고 간발의 차이로 다른 쪽 포크를 획득하는데 실패(…)한다면, 당장 식사 시도를 포기하고 잡았던 포크를 반납하게 한다. 가장 간단하고 가장 강제적이지만, 교착이 발생하였을 때 해당 타임아웃 시간이 될 때까지 일부러 기다려줘야 한다는 딜레이가 있다. 1. 철학자들 중 하나는 포크를 오른쪽부터 잡게 한다고 생각해 보자. 예를 들어 1번 철학자는 왼쪽부터, 2번 철학자는 오른쪽부터 잡는다. 1번 철학자가 왼쪽 포크만 잡은 상태에서 행동권이 2번 철학자에게 넘어간다고 하더라도, 2번 철학자는 자신의 오른쪽 포크가 현재 사용 불가능하기 때문에, 첫번째 포크를 잡으려는 상황에서 멈춰 있게 된다. 이 상황에서 1번 철학자로 다시 행동권이 넘어오게 되면 1번 철학자는 자신의 오른쪽 포크를 잡고 다시 식사를 할 수 있게 된다. 1. 포크 하나하나에 비교 가능한 고유 값을 부여하여, 고유 값이 높은(또는 낮은) 순서대로 포크를 집게 만든다. 고유 값은 보통 [[해시]]를 사용하는 게 일반적이며, 서로 겹치면 안 된다. 예를 들어, 포크 다섯 개의 고유번호가 각각 순서대로 295, 329, 683, 591, 274이고 고유번호가 높은 순서대로 포크를 집는다고 가정하자, 3번 철학자는 3번과 4번 포크를 사용할 텐데, 그 포크들의 값은 683, 591이므로 3번 철학자는 683의 값을 가진 3번 포크를 먼저 집는다. 반대로 1번 철학자는 1번과 2번 포크를 사용할 텐데, 그 포크들의 값은 295, 329이므로 1번 철학자는 329의 값을 가진 2번 포크를 먼저 집는다. 이렇게 하면 절대로 모든 철학자가 하나의 포크를 집고 대기하는 일이 없으므로(a > b > c > d > e > a, 또는 반대일 수는 없으므로) 문제를 해결할 수 있다. == 여담 == * 다익스트라가 처음 이 문제를 만들었을 때는 철학자라고만 설명했지만, 시간이 지나 여러 버전으로 각색되며 각각의 이름이 등장하기도 한다. 주로 [[소크라테스]], [[플라톤]], [[아리스토텔레스]], [[탈레스]], [[피타고라스]]가 등장한다. * 문제를 처음 보면 "그냥 포크 하나로 식사하면 되지!"라고 생각할 수 있지만, 문제 규칙에서 분명히 포크를 양손에 잡아야 식사를 할 수 있다고 되어 있다. 대학 수업에서도 이걸로 딴지거는 학생들이 제법 있었는지~~(...)~~, 한국에서는 포크를 [[젓가락]] 한 짝으로 윤색한 더 직관적인 버전도 있다. ~~하지만 젓가락은 양손으로 쓰지 않는다~~ == 관련 문서 == * [[데드락]] * [[뮤텍스]] * [[세마포어]] * [[멀티태스킹]] * [[Too much milk problem]]캡챠되돌리기