"철학자 5명이 5개의 포크를 2개씩 써서 어떻게 사이좋게 스파게티를 먹을까"
원활한 자원활용 위한 작업규칙
프로세스 효율적 구동원리 연구
'자원독점' '교착상태' 모두 피해야 동기화도구 '세마포어' 등으로 해결
오직 그들의 생애를 먹고 생각하는 것으로 보내는 5명의 철학자들이 있습니다. 이 철학자들은 원형 테이블에 앉아 있고 각자 앞에는 먹음직스러운 스파게티가 놓여있습니다. 그리고 스파게티 접시 사이에는 5개의 포크가 있습니다. 철학자는 생각할 때는 어떤 일도 하지 않고 배가 고파지면 가장 가까이에 놓인 두 개의 포크를 이용해 스파게티를 먹습니다.(반드시 두 개의 포크를 이용해야 합니다.) 옆 사람이 사용하고 있는 포크는 사용할 수 없습니다. 이 상황에서 어떻게 하면 철학자 모두 스파게티를 잘 먹을 수 있을까요? (이 문제는 젓가락 두 쪽과 밥으로 표현되기도 합니다.)
단순하고 어쩌면 기이한 이 논제는 대학에서 컴퓨터공학을 공부하는 사람이라면 한번쯤 접하는 `철학자들의 만찬 문제(The Dining-Philosophers Problem)'입니다.
네덜란드 출신으로 1972년 튜링상을 수상한 컴퓨터과학자 에츠허르 데이크스트라(Edsger W. Dijkstra, 1930~2002)가 고안한 이 문제는 컴퓨터 내에서 구현 중인 프로그램인 프로세스의 활동을 나타냅니다. 컴퓨터에서 프로그램을 실행시키면 프로세스가 생성되어 구동합니다. 이 프로세스는 컴퓨터로부터 자원을 할당받아 일하고 우리는 그 결과를 받아봅니다. 이것이 우리가 프로그램을 실행하고 구동하는 방법입니다. 쉽게 생각해서 철학자가 두 개의 포크로 스파게티를 먹는 행위는 포크라는 자원(CPU와 메모리 등)을 이용해서 스파게티라는 과제를 처리하는 것입니다.
물론 이런 방식으로 하나의 프로세스만 동작한다면 문제가 없지만 우리가 사용하는 컴퓨터는 여러 프로세스가 동시에 일을 처리하고 자원을 원하기 때문에 문제가 발생합니다. 몸은 하나인데 여러 명과 연애를 하려다보니 문제가 발생하는 것이지요. 이럴 경우 사람들을 만나는 규칙을 정하고 일정을 잘 조정해야겠지요. 컴퓨터도 마찬가지입니다. 원활한 자원의 사용을 위해서는 작업의 규칙을 정하고 수행시기를 조정하는 동기화가 필요합니다.
만약 규칙이나 동기화 없이 한 프로세스가 자원을 독점한다면 다른 프로세스는 스파게티를 먹지 못해 기아상태(Starvation)에 빠질 것입니다. 또 모든 프로세스가 하나의 포크만 들고 기다린다면 그들은 계속 다른 포크를 기다려야하는 교착상태(deadlock)에 빠지고 컴퓨터는 작동하지 않을 것입니다.
데이크스트라는 이런 상호간의 문제들을 해결하기 위해 이 논제를 고안하여 발생할 수 있는 문제들을 생각해보고 해결방법을 찾았습니다. 그렇다면 기아나 교착상태를 막기 위해서는 어떻게 해야 하는 것일까?
우선 세마포어(Semaphores)라고 하는 동기화 도구를 이용할 수 있습니다. 데이크스트라가 고안한 세마포어는 공유자원에 대한 접근을 제한하여 문제를 해결합니다. 간단히 설명하면 컴퓨터 작동을 관리하는 오퍼레이팅시스템(OS)에 세마포어 값을 두고 덧셈과 뺄셈으로 값을 변화시켜 자원 접근권한을 부여하는 것입니다. 그러나 세마포어가 모든 교착상태 문제를 해결해주지는 못합니다.
다른 여러 가지 교착상태 해결책을 열거해보면 다음과 같습니다. 최대 4명의 철학자들만 테이블에 동시에 앉도록 허용할 수 있습니다. 또 한 철학자가 포크 두 개를 모두 집을 수 있을 때만 포크를 집도록 허용하는 것도 방법입니다. 혹은 비대칭 해결안을 사용합니다. 예를 들면, 철학자들에게 번호를 매겨 짝수의 철학자는 오른쪽 젓가락을 집고 다음에 왼쪽 젓가락을 잡도록 하는 반면, 홀수의 철학자는 반대로 규칙을 정하는 것입니다.
하지만 정해진 답은 없습니다. 컴퓨터공학을 연구하는 사람이라면 효율적이고 창조적인 규칙을 찾아보는 것도 학문을 하는 하나의 즐거움일 것입니다.
어떻게 하면 철학자들이 스파게티를 효율적으로 잘 먹을 수 있을지 여러분들도 한번쯤 생각해 보는 것은 어떻겠습니까?
원활한 자원활용 위한 작업규칙
프로세스 효율적 구동원리 연구
'자원독점' '교착상태' 모두 피해야 동기화도구 '세마포어' 등으로 해결
오직 그들의 생애를 먹고 생각하는 것으로 보내는 5명의 철학자들이 있습니다. 이 철학자들은 원형 테이블에 앉아 있고 각자 앞에는 먹음직스러운 스파게티가 놓여있습니다. 그리고 스파게티 접시 사이에는 5개의 포크가 있습니다. 철학자는 생각할 때는 어떤 일도 하지 않고 배가 고파지면 가장 가까이에 놓인 두 개의 포크를 이용해 스파게티를 먹습니다.(반드시 두 개의 포크를 이용해야 합니다.) 옆 사람이 사용하고 있는 포크는 사용할 수 없습니다. 이 상황에서 어떻게 하면 철학자 모두 스파게티를 잘 먹을 수 있을까요? (이 문제는 젓가락 두 쪽과 밥으로 표현되기도 합니다.)
단순하고 어쩌면 기이한 이 논제는 대학에서 컴퓨터공학을 공부하는 사람이라면 한번쯤 접하는 `철학자들의 만찬 문제(The Dining-Philosophers Problem)'입니다.
네덜란드 출신으로 1972년 튜링상을 수상한 컴퓨터과학자 에츠허르 데이크스트라(Edsger W. Dijkstra, 1930~2002)가 고안한 이 문제는 컴퓨터 내에서 구현 중인 프로그램인 프로세스의 활동을 나타냅니다. 컴퓨터에서 프로그램을 실행시키면 프로세스가 생성되어 구동합니다. 이 프로세스는 컴퓨터로부터 자원을 할당받아 일하고 우리는 그 결과를 받아봅니다. 이것이 우리가 프로그램을 실행하고 구동하는 방법입니다. 쉽게 생각해서 철학자가 두 개의 포크로 스파게티를 먹는 행위는 포크라는 자원(CPU와 메모리 등)을 이용해서 스파게티라는 과제를 처리하는 것입니다.
물론 이런 방식으로 하나의 프로세스만 동작한다면 문제가 없지만 우리가 사용하는 컴퓨터는 여러 프로세스가 동시에 일을 처리하고 자원을 원하기 때문에 문제가 발생합니다. 몸은 하나인데 여러 명과 연애를 하려다보니 문제가 발생하는 것이지요. 이럴 경우 사람들을 만나는 규칙을 정하고 일정을 잘 조정해야겠지요. 컴퓨터도 마찬가지입니다. 원활한 자원의 사용을 위해서는 작업의 규칙을 정하고 수행시기를 조정하는 동기화가 필요합니다.
만약 규칙이나 동기화 없이 한 프로세스가 자원을 독점한다면 다른 프로세스는 스파게티를 먹지 못해 기아상태(Starvation)에 빠질 것입니다. 또 모든 프로세스가 하나의 포크만 들고 기다린다면 그들은 계속 다른 포크를 기다려야하는 교착상태(deadlock)에 빠지고 컴퓨터는 작동하지 않을 것입니다.
데이크스트라는 이런 상호간의 문제들을 해결하기 위해 이 논제를 고안하여 발생할 수 있는 문제들을 생각해보고 해결방법을 찾았습니다. 그렇다면 기아나 교착상태를 막기 위해서는 어떻게 해야 하는 것일까?
우선 세마포어(Semaphores)라고 하는 동기화 도구를 이용할 수 있습니다. 데이크스트라가 고안한 세마포어는 공유자원에 대한 접근을 제한하여 문제를 해결합니다. 간단히 설명하면 컴퓨터 작동을 관리하는 오퍼레이팅시스템(OS)에 세마포어 값을 두고 덧셈과 뺄셈으로 값을 변화시켜 자원 접근권한을 부여하는 것입니다. 그러나 세마포어가 모든 교착상태 문제를 해결해주지는 못합니다.
다른 여러 가지 교착상태 해결책을 열거해보면 다음과 같습니다. 최대 4명의 철학자들만 테이블에 동시에 앉도록 허용할 수 있습니다. 또 한 철학자가 포크 두 개를 모두 집을 수 있을 때만 포크를 집도록 허용하는 것도 방법입니다. 혹은 비대칭 해결안을 사용합니다. 예를 들면, 철학자들에게 번호를 매겨 짝수의 철학자는 오른쪽 젓가락을 집고 다음에 왼쪽 젓가락을 잡도록 하는 반면, 홀수의 철학자는 반대로 규칙을 정하는 것입니다.
하지만 정해진 답은 없습니다. 컴퓨터공학을 연구하는 사람이라면 효율적이고 창조적인 규칙을 찾아보는 것도 학문을 하는 하나의 즐거움일 것입니다.
어떻게 하면 철학자들이 스파게티를 효율적으로 잘 먹을 수 있을지 여러분들도 한번쯤 생각해 보는 것은 어떻겠습니까?
