Search

'starvation'에 해당되는 글 1건

  1. 2009.09.02 Asynchronous Agents Library로 Dining Philosophers 문제 해결하기 - 1 1
이 글은 MSDN 글, "Solving The Dining Philosophers Problem With Asynchronous Agents"를 참고하여 작성되었습니다.

오늘은 AAL(Asynchronous Agents Library)의 액터기반프로그래밍을 사용하여, 동기화 개체들로는 해법이 상당히 골치아프기로 유명한 "철학자들의 식사(Dining Philosophers) 문제"를 풀어보겠습니다. 내용이 길어질듯 하여 3회의 연재글로 구성하려 합니다.

먼저 간단히 철학자들의 식사 문제를 소개하면,


간단히 위 그림과 같은 상황입니다. 철학자 다섯명이 식사를 하는데 젓가락(그림에는 포크지만 상관없습니다;)이 보시는바와 같이 역시 다섯개뿐입니다. 그들은 철학자답게 생각하다가 한입 먹다가를 반복합니다. 한입 먹으려면 젓가락 한쌍이 필요해서 옆사람이 사이에 놓인 젓가락을 이미 선점해 먹고 있다면 기다려야 하는 것이죠. 공유 상태를 고려하지 않고 구현하면 데드락 등으로 철학자가 굶는(starvation) 상황이 발생할 수 있습니다. 이 문제는 저명한 컴퓨터과학자 다익스트라가 처음 제시하였습니다. 모니터 등의 동기화 개체를 사용하여 해결하는 방법이 기존에 많이 설명되어 있습니다만... 솔직히 이해하기가 쉽지 않고 구현도 어렵습니다.

이때 AAL이 제공하는 액터모형을 이용하면 그러한 난해함이나 복잡함 없이 이 문제를 해결할 수 있습니다. 액터모형은 독립적으로 동작하며 서로간에는 오로지 메시지만으로 소통하는(즉, 공유 상태를 가지지 않는) 액터들로 시스템을 모델링하는 방법이라 하겠습니다.

본 예제에서는 철학자를 액터(AAL 용어로는 에이전트)로 보고 메시지 전달을 위해 AAL에서 제공하는 몇몇 메시지 블록(message block)들을 사용하여 철학자들의 식사 문제를 해결합니다.

다음과 같은 다섯 클래스들을 작성하게 됩니다.

  • Chopstick 클래스
  • 식탁 위의 젓가락을 실제 소유하며 요청에 따라 철학자에게 제공하는 역할을 하는 ChopstickProvider 
  • 생각하고 먹는 에이전트 역할의 Philosopher 클래스. 이 클래스는 한쌍의 ChopstickProvider와만 소통합니다.
  • 생각하고 먹는 상태를 나타내는 PhilosopherState 열거형
  • 젓가락들과 철학자들이 배치될 Table 클래스

이 과정에서 다음과 같은 AAL의 클래스 및 함수들을 이용합니다.
  • Concurrency::agent - 에이전트 기반 클래스
  • 이하는 메시지 블록에 속하는 여러 타입들
    • Concurrency::unbounded_buffer
    • Concurrency::overwrite_buffer
    • Concurrency::join
    • Concurrency::call
  • 이상의 메시지 블록들에 메시지를 주고 받는데 사용하는 함수들
    • Concurrency::send
    • Concurrency::asend - 위의 비동기 버전으로, 받음 여부를 확인하지 않고 바로 리턴
    • Concurrency::receive

본격적인 구현 과정은 다음 회에 계속됩니다~ ^^