식사하는 철학자 문제

Swift로 구현한 식사하는 철학자 문제 알고리즘(동시성 알고리즘 설계로, GCD와 Semaphore를 사용해 동기화 문제와 해결 기법을 설명)

Swift Algorithm Club을 위해 Jacopo Mangiavacchi가 작성

소개

컴퓨터 과학에서 철학자들의 만찬 문제는 동시성 알고리즘 설계에서 동기화 문제와 이를 해결하기 위한 기법을 설명하는 데 자주 사용된다.

이 문제는 1965년 에츠허르 데이크스트라가 학생 시험 문제로 처음 제안했으며, 테이프 드라이브 주변 장치에 대한 접근을 놓고 경쟁하는 컴퓨터의 관점에서 제시되었다. 이후 토니 호어가 현재의 형태로 문제를 재정립했다.

이 Swift 구현은 Chandy/Misra 솔루션을 기반으로 하며, Swift 크로스 플랫폼에서 GCD Dispatch와 세마포어를 사용한다.

문제 정의

다섯 명의 침묵하는 철학자가 스파게티 그릇과 함께 둥근 테이블에 앉아 있다. 각 철학자 사이에는 포크가 하나씩 놓여 있다.

모든 철학자는 생각과 먹기를 번갈아가며 수행해야 한다. 철학자는 왼쪽과 오른쪽 포크를 모두 잡았을 때만 스파게티를 먹을 수 있다. 각 포크는 한 번에 한 철학자만 사용할 수 있기 때문에, 다른 철학자가 사용하지 않는 경우에만 포크를 사용할 수 있다. 철학자는 먹기를 마치면 두 포크를 내려놓아 다른 철학자가 사용할 수 있게 해야 한다. 철학자는 오른쪽 포크나 왼쪽 포크를 사용 가능한 상태가 되면 잡을 수 있지만, 두 포크를 모두 잡기 전에는 먹기를 시작할 수 없다.

스파게티의 양이나 배의 공간은 무한히 공급된다고 가정한다.

이 문제의 핵심은 모든 철학자가 굶주리지 않고 영원히 생각과 먹기를 번갈아가며 수행할 수 있는 동시성 알고리즘을 설계하는 것이다. 단, 각 철학자는 다른 철학자가 언제 먹거나 생각할지 알 수 없다.

다음은 철학자들의 식탁을 나타낸 그림이다:

해결 방안

이 고전적인 알고리즘에는 여러 가지 해결 방법이 존재한다. 이 Swift 구현은 Chandy/Misra 솔루션을 기반으로 한다. 이 구현은 중앙 권한 없이도 완전히 분산된 환경에서 임의의 수의 리소스를 확보하기 위해 에이전트들이 경쟁할 수 있도록 한다. 리소스의 잠금과 직렬화를 제어할 중앙 권한이 필요하지 않다.

하지만 이 해결 방법은 "철학자들이 서로 대화하지 않는다"는 요구 사항을 위반한다. 이는 요청 메시지 때문이다.

설명

리소스를 놓고 경쟁하는 철학자들 사이에서, 각 쌍마다 포크를 생성하고 더 낮은 ID를 가진 철학자에게 할당한다(Pn 에이전트의 경우 n). 각 포크는 더럽거나 깨끗한 상태일 수 있다. 처음에는 모든 포크가 더럽다.
철학자가 일련의 리소스를 사용하려고 할 때(즉, 식사를 하려고 할 때), 해당 철학자는 경쟁하는 이웃들로부터 포크를 얻어야 한다. 철학자는 필요한 모든 포크에 대해 요청 메시지를 보낸다. 포크를 가진 철학자가 요청 메시지를 받으면, 포크가 깨끗한 경우 그대로 유지하지만 더러운 경우 포크를 내준다. 포크를 보내는 경우, 철학자는 포크를 깨끗하게 만든 후 전달한다.
철학자가 식사를 마치면, 그가 가진 모든 포크는 더러워진다. 다른 철학자가 이전에 그 포크 중 하나를 요청했다면, 식사를 마친 철학자는 포크를 깨끗하게 만든 후 전달한다.
이 해결책은 높은 수준의 동시성을 허용하며, 임의로 큰 문제도 해결할 수 있다.

또한, 이 방법은 기아 문제도 해결한다. 깨끗/더러운 라벨은 가장 "기아 상태"에 있는 프로세스에 우선권을 주고, 방금 "식사"를 마친 프로세스에는 불리한 조건을 부여한다. 이 해결책은 철학자들이 연속으로 두 번 식사하지 못하게 하고, 그 사이에 다른 이들이 포크를 사용할 수 있도록 하는 방식과 비교할 수 있다. Chandy와 Misra의 해결책은 더 유연하지만, 그 방향으로의 경향성을 가지고 있다.

Chandy와 Misra의 분석에 따르면, 포크의 분포와 깨끗/더러운 상태로부터 선호도 시스템이 도출된다. 이 시스템은 비순환 그래프를 설명할 수 있으며, 그렇다면 이 프로토콜은 그 그래프를 순환 그래프로 바꿀 수 없다. 이는 데드락이 발생하지 않음을 보장한다. 그러나 시스템이 완전히 대칭적인 상태로 초기화된 경우(예: 모든 철학자가 왼쪽 포크를 가지고 있는 경우), 그래프는 처음부터 순환적이며, 이 해결책은 데드락을 방지할 수 없다. 더 낮은 ID를 가진 철학자들이 더러운 포크를 가지도록 시스템을 초기화하면, 그래프가 처음부터 비순환적임을 보장할 수 있다.

Swift 구현

이 Swift 3.0 구현은 Chandy/Misra 해결책을 GCD와 세마포어 기법을 사용하여 macOS와 Linux에서 모두 빌드할 수 있도록 작성되었다.

코드는 DispatchSemaphore 배열을 보관하는 ForkPair 구조체와 각 철학자에게 한 쌍의 포크를 연결하는 Philosopher 구조체를 기반으로 한다.

ForkPair의 DispatchSemaphore 정적 배열은 테이블에 포크 쌍이 내려놓일 때마다 이웃 철학자들을 깨우는 데 사용된다.

백그라운드 DispatchQueue는 모든 철학자가 백그라운드에서 비동기적으로 실행되도록 하며, 전역 DispatchSemaphore는 메인 스레드를 무한히 대기 상태로 유지하고 철학자들이 계속해서 생각하고 먹는 주기를 반복하도록 한다.

함께 보기

위키백과의 철학자들의 만찬 문제
https://en.wikipedia.org/wiki/Dining_philosophers_problem

Swift Algorithm Club의 Jacopo Mangiavacchi가 작성
Swift 4.2 검토: Bruno Scheele