데이크스트라의 '철학자의 만찬 문제'(2021, 고3, 7월)

에츠허르 비버 데이크스트라(Edsger Wybe Dijkstra, 1930-2002). 네덜란드의 컴퓨터 과학자. 1972년에 프로그래밍 언어 분야에 대한 지대한 공헌을 인정받아 튜링상을 수상했다.  from 위키백과

 

 

 

 

컴퓨터 과학자 데이크스트라가 고안한 ‘철학자의 만찬 문제’는 컴퓨터 내에서 여러 프로세스*가 서로 점유하고 있는 자원을 얻기 위해 상대방의 작업이 끝나기만을 기다리며 대기하는 ‘교착 상태’와 특정 프로세스가 원하는 자원을 계속 할당받지 못하는 ‘기아 상태’에 대한 대표적인 예시로 활용된다.

 

<그림1>

<그림1>처럼 다섯 명의 철학자(P₁~P₅)가 앉아 있는 자리 왼쪽에 포크(f₁~f₅)가 각각 하나씩 놓여 있다고 하자. 가운데 놓인 스파게티를 덜어 오기 위해서 철학자는 양옆의 포크를 동시에 이용해야 하며, 다른 철학자가 사용 중인 포크는 사용할 수 없다. 또 모든 철학자 Pₙ이 왼쪽의 포크 fₙ을 먼저 든 다음 오른쪽 포크 fₙ₊₁을 들어서 스파게티를 가져오기로 약속했을 때, 스파게티를 가져오기 위해 모든 철학자가 동시에 왼쪽 포크를 들게 되면, 오른쪽에는 남는 포크가 없어 모두가 무한정 서로를 기다리는 교착 상태가 발생한다. 또한 교착 상태가 해결되더라도 여러 이유로 특정 철학자에게 포크를 들 기회가 주어지지 않을 경우 특정 철학자만 스파게티를 먹지 못하는 기아 상태가 발생한다. 컴퓨터에서도 마찬가지로 CPU나 메모리 등과 같은 공유 자원을 이용해 프로세스를 처리하는 과정에서 다양한 이유로 교착 상태와 기아 상태가 발생하게 된다.

‘철학자의 만찬 문제’에 대해 데이크스트라는 ㉠모든 철학자 Pₙ이 동시에 포크 fₙ을 집을 때 P₅만 f₁을 집도록 하면 적어도 한 명은 식사를 할 수 있어 교착 상태를 해결할 수 있음을 밝힌 바 있다. 실제 교착 상태는 예방, 회피, 발견 및 복구의 방법으로 해결 가능한데, 우선 교착 상태의 네 가지 필요조건 중 하나를 부정함으로써 교착 상태의 발생을 사전에 예방할 수 있다. 교착 상태는 자원에 대한 배타적인 통제권을 요구하는 ‘상호 배제 조건’, 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다리는 ‘점유 대기 조건’, 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 사용할 수 없는 ‘비선점 조건’, 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있는 ‘순환 대기 조건’을 모두 충족했을 때 발생한다. 이에 따라 여러 프로세스가 공유 자원을 동시에 사용할 수 있도록 상호 배제 조건을 부정하거나, 특정 프로세스의 실행 전에 필요 한 모든 자원을 미리 할당하여 점유 대기 조건을 부정하는 방법, 자원에 고유한 순서를 할당하여 순환 대기 조건을 부정하 는 방법 등으로 교착 상태를 예방한다. 하지만 어떤 자원들은 근본적으로 동시에 공유가 불가능하기 때문에 일반적으로 상호 배제 조건은 부정할 수 없다. 한편 교착 상태를 예방하는 과정에서 장치의 이용률과 속도가 저하되고 기아 상태가 발생하기도 한다.

자원을 좀 더 효율적으로 활용하기 위해 교착 상태를 회피하는 방법으로는 ‘은행원 알고리즘’을 활용한다. 예를 들어 100달러를 가지고 있는 은행이 있다고 하자. A, B, C의 고객이 각각 최대 60달러, 40달러, 50달러를 빌리려고 한다. 은행은 현재 A, B, C고객에게 각각 30달러를 빌려준 상황이다. A, B, C고객들은 각각 30달러, 10달러, 20달러의 돈이 추가적으로 더 필요하지만 은행은 고객들에게 돈을 빌려주고 남은 10달러만 빌려줄 수 있는 상황이다. 이 상황을 해결하기 위해 은행은 대출 가능한 10달러 전부를 B고객에게 빌려주고 그 고객이 돈을 갚을 때까지 기다렸다가 A고객이나 C고객에게 돈을 빌려줄 수 있다. B고객에게 남은 돈을 먼저 빌려주면 모든 고객의 요구를 해결해 줄 수 있는 두 가지 경로의 안전 순서열 (B-A-C, B-C-A)이 존재하게 되는 것이다. 이처럼 시스템 내에 안전 순서열이 존재하는 상태를 ‘안전 상태’라고 하는데, 이러한 안전 상태에서만 프로세스에 자원을 분배함으로써 교착 상태를 회피할 수 있다.

 

좌: <그림2-1>, 우: <그림2-2>

또한 교착 상태를 발견하여 복구하기도 하는데, 교착 상태를 발견하는 방법으로는 ‘자원할당그래프’를 이용한다. 자원할당그래프는 프로세스와 자원 간의 관계를 시각적으로 표시하여 순환 대기 조건을 발견함으로써 교착 상태를 판단한다. 자원 Rₙ으로부터 프로세스 Pₙ으로 향하는 화살표를 점유선, 프로세스 Pₙ에서 자원 Rₙ으로 향하는 화살표를 요구선이라고 했을 때 <그림2-1>처럼 서로 공유하는 자원 R₁, R₂를 두고 점유선과 요구선이 순환하는 형태일 때 교착 상태임을 발견할 수 있다. 또 <그림2-2>처럼 순환 구조가 존재하더라 도 R₂처럼 한 가지 종류의 자원에 동일한 단위 자원이 여러 개 있어 프로세스의 요구대로 자원 할당이 가능하거나, P₃처럼 순환 구조에서 독립적으로 단위 자원을 점유하고 있어 반납한 단위 자원을 P₁에게 할당할 수 있을 경우 교착 상태로 보지 않는다.

교착 상태가 발견되면 교착 상태 해결을 위해 시스템을 교착 상태 이전으로 복구시키는 방법을 사용한다. 교착 상태를 복구시키는 방법으로는 주로 교착 상태에 속한 프로세스들을 중지 시키는 방법을 사용하는데, 교착 상태를 해결하기 위해 투입되는 자원이나 시간으로 인해 발생하는 시스템의 성능 저하가 교착 상태로 인해 발생하는 성능 저하보다 큰 경우 발견된 교착 상태를 무시하기도 한다. 또 다양한 방법으로 교착 상태가 해결되었음에도 불구하고 시스템 내 특정 프로세스에 기아 상태가 발생할 경우 새로운 프로세스의 시작을 보류하도록 조치하여 기아 상태를 해결한다. 이와 같은 교착 상태와 기아 상태의 해결을 통해 컴퓨터의 운영 체제는 각 프로세스를 위한 공유 자원들을 보다 안정적이고 효율적으로 운영할 수 있게 된다.

* 프로세스 : 실행 중인 프로그램.

 

@ 2021학년도 7월 전국연합학력평가 9~13번.

― 출전: 김용석, <운영체제>