연습: join을 사용하여 교착 상태 방지

아티클
08/09/2011

이 항목에서는 Concurrency::join 클래스를 사용하여 응용 프로그램의 교착 상태를 방지하는 방법을 보여 주기 위해 철학자들의 만찬 문제(Dining Philosophers Problem)를 활용합니다. 소프트웨어 응용 프로그램에서는 둘 이상의 프로세스에서 각각 리소스를 보유하는 경우 다른 프로세스가 일부 다른 리소스를 해제하기를 서로 기다릴 때 교착 상태가 발생합니다.

철학자들의 만찬 문제는 여러 개의 동시 프로세스 사이에서 리소스 집합이 공유되는 경우 발생할 수 있는 일반적인 문제들 중 특정한 예입니다.

사전 요구 사항

이 연습을 시작하기 전에 다음 항목의 내용을 읽어 보십시오.

단원

이 연습에는 다음 단원이 포함되어 있습니다.

철학자들의 만찬 문제
간단한 구현
join을 사용하여 교착 상태 방지

철학자들의 만찬 문제

철학자들의 만찬 문제에서는 응용 프로그램에서 교착 상태가 어떤 식으로 발생하는지를 보여 줍니다. 이 문제에서는 다섯 명의 철학자가 원형 탁자에 앉아 있습니다. 모든 철학자는 생각과 식사를 교대로 반복합니다. 또한 모든 철학자는 왼쪽에 있는 사람과 젓가락 한 쪽을 공유하고 오른쪽에 있는 사람과 나머지 젓가락 한 쪽을 공유해야 합니다. 다음 그림에서는 이 레이아웃을 보여 줍니다.

철학자들의 만찬 문제

식사를 하기 위해 철학자는 양 쪽 젓가락을 둘 다 가지고 있어야 합니다. 모든 철학자가 한 쪽 젓가락만 가지고 있고 다른 젓가락을 기다리는 상태인 경우 아무도 음식을 먹을 수 없고 모두 굶게 됩니다.

[맨 위로 이동]

간단한 구현

다음 예제에서는 철학자들의 만찬 문제에 대한 간단한 구현을 보여 줍니다. Concurrency::agent에서 파생되는 philosopher 클래스를 사용하면 각 철학자가 독립적으로 동작할 수 있습니다. 이 예제에서는 Concurrency::critical_section 개체의 공유 배열을 사용하여 각 philosopher 개체에 젓가락 쌍에 대한 단독 액세스 권한을 제공합니다.

그림과 구현의 관계를 설정하기 위해 philosopher 클래스는 한 명의 철학자를 나타냅니다. int 변수는 각 젓가락 한 쪽을 나타냅니다. critical_section 개체는 젓가락 받침 역할을 합니다. run 메서드는 철학자의 수명을 시뮬레이션합니다. think 메서드는 생각하는 행동을 시뮬레이션하고 eat 메서드는 먹는 행동을 시뮬레이션합니다.

philosopher 개체는 eat 메서드를 호출하기 전에 받침에서 젓가락을 제거하는 것을 시뮬레이션하기 위해 두 critical_section 개체를 모두 잠급니다. eat 메서드를 호출한 후 philosopher 개체는 critical_section 개체를 다시 잠금 해제 상태로 설정하여 젓가락을 받침에 돌려줍니다.

pickup_chopsticks 메서드는 교착 상태가 발생할 수 있는 경우를 보여 줍니다. 모든 philosopher 개체가 잠금 중 하나에 대한 액세스 권한을 가지고 있으면 다른 잠금은 다른 philosopher 개체에 의해 제어되므로 philosopher 개체를 계속할 수 없습니다.

예제

코드

// philosophers-deadlock.cpp
// compile with: /EHsc
#include <agents.h>
#include <string>
#include <array>
#include <iostream>
#include <algorithm>
#include <random>

using namespace Concurrency;
using namespace std;

// Defines a single chopstick.
typedef int chopstick;

// The total number of philosophers.
const int philosopher_count = 5;

// The number of times each philosopher should eat.
const int eat_count = 50;

// A shared array of critical sections. Each critical section 
// guards access to a single chopstick.
critical_section locks[philosopher_count];

// Implements the logic for a single dining philosopher.
class philosopher : public agent 
{
public:
   explicit philosopher(chopstick& left, chopstick& right, const wstring& name)
      : _left(left)
      , _right(right)
      , _name(name)
      , _random_generator(42)
   {
      send(_times_eaten, 0);
   }

   // Retrieves the number of times the philosopher has eaten.
   int times_eaten()
   {
      return receive(_times_eaten);
   }

   // Retrieves the name of the philosopher.
   wstring name() const
   {
      return _name;
   }

protected:
   // Performs the main logic of the dining philosopher algorithm.
   void run()
   {
      // Repeat the thinks/eat cycle a set number of times.
      for (int n = 0; n < eat_count; ++n)
      {
         think();

         pickup_chopsticks(); 
         eat();
         send(_times_eaten, n+1);
         putdown_chopsticks();
      }

      done();
   }

   // Gains access to the chopsticks.
   void pickup_chopsticks()
   {
      // Deadlock occurs here if each philosopher gains access to one
      // of the chopsticks and mutually waits for another to release
      // the other chopstick.
      locks[_left].lock();
      locks[_right].lock();
   }

   // Releases the chopsticks for others.
   void putdown_chopsticks()
   {
      locks[_right].unlock();
      locks[_left].unlock();
   }

   // Simulates thinking for a brief period of time.
   void think()
   {
      random_wait(100);
   }

   // Simulates eating for a brief period of time.
   void eat()
   { 
      random_wait(100);
   }

private:
   // Yields the current context for a random period of time.
   void random_wait(unsigned int max)
   {
      Concurrency::wait(_random_generator()%max);
   }

private:
   // Index of the left chopstick in the chopstick array.
   chopstick& _left;
   // Index of the right chopstick in the chopstick array.
   chopstick& _right;

   // The name of the philosopher.
   wstring _name;
   // Stores the number of times the philosopher has eaten.
   overwrite_buffer<int> _times_eaten;

   // A random number generator.
   mt19937 _random_generator;
};

int wmain()
{
   // Create an array of index values for the chopsticks.
   array<chopstick, philosopher_count> chopsticks = {0, 1, 2, 3, 4};

   // Create an array of philosophers. Each pair of neighboring 
   // philosophers shares one of the chopsticks.
   array<philosopher, philosopher_count> philosophers = {
      philosopher(chopsticks[0], chopsticks[1], L"aristotle"),
      philosopher(chopsticks[1], chopsticks[2], L"descartes"),
      philosopher(chopsticks[2], chopsticks[3], L"hobbes"),
      philosopher(chopsticks[3], chopsticks[4], L"socrates"),
      philosopher(chopsticks[4], chopsticks[0], L"plato"),
   };

   // Begin the simulation.
   for_each (philosophers.begin(), philosophers.end(), [](philosopher& p) {
      p.start();
   });

   // Wait for each philosopher to finish and print his name and the number
   // of times he has eaten.
   for_each (philosophers.begin(), philosophers.end(), [](philosopher& p) {
      agent::wait(&p);
      wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
   });
}

코드 컴파일

예제 코드를 복사하여 Visual Studio 프로젝트 또는 philosophers-deadlock.cpp 파일에 붙여넣고 Visual Studio 2010 명령 프롬프트 창에서 다음 명령을 실행합니다.

cl.exe /EHsc philosophers-deadlock.cpp

[맨 위로 이동]

join을 사용하여 교착 상태 방지

이 단원에서는 메시지 버퍼 및 메시지 전달 함수를 사용하여 교착 상태 가능성을 제거하는 방법을 보여 줍니다.

이전 예제와의 관계를 설정하기 위해 philosopher 클래스는 Concurrency::unbounded_buffer 개체 및 join 개체를 사용하여 각 critical_section 개체를 바꿉니다. join 개체는 젓가락을 철학자에게 제공하는 중재인 역할을 합니다.

대상이 unbounded_buffer 개체에서 메시지를 받으면 해당 메시지가 메시지 큐에서 제거되므로 이 예제에서는 unbounded_buffer 클래스를 사용합니다. 이렇게 하면 메시지를 보관하는 unbounded_buffer 개체에서 젓가락을 사용할 수 있음을 나타낼 수 있습니다. 메시지를 보관하지 않는 unbounded_buffer 개체는 젓가락이 아직 사용 중임을 나타냅니다.

non-greedy 조인은 두 unbounded_buffer 개체에 모두 메시지가 포함된 경우에만 각 philosopher 개체에 젓가락 양 쪽에 대한 액세스 권한을 제공하므로 이 예제에서는 non-greedy join 개체를 사용합니다. greedy 조인은 메시지를 사용할 수 있게 되면 즉시 해당 메시지를 수락하므로 교착 상태를 방지하지 못합니다. 모든 greedy join 개체가 메시지 중 하나를 받지만 다른 메시지를 사용할 수 있을 때까지 영원히 기다리는 경우 교착 상태가 발생할 수 있습니다.

greedy 조인과 non-greedy 조인에 대한 자세한 내용 및 다양한 메시지 버퍼 형식 간의 차이점에 대한 설명은 비동기 메시지 블록을 참조하십시오.

이 예제에서 교착 상태를 방지하려면

예제에서 다음 코드를 제거합니다.

// A shared array of critical sections. Each critical section 
// guards access to a single chopstick.
critical_section locks[philosopher_count];

philosopher 클래스의 _left 및 _right 데이터 멤버 형식을 unbounded_buffer로 변경합니다.

// Message buffer for the left chopstick.
unbounded_buffer<chopstick>& _left;
// Message buffer for the right chopstick.
unbounded_buffer<chopstick>& _right;

unbounded_buffer 개체를 매개 변수로 사용하도록 philosopher 생성자를 수정합니다.

explicit philosopher(unbounded_buffer<chopstick>& left, 
   unbounded_buffer<chopstick>& right, const wstring& name)
   : _left(left)
   , _right(right)
   , _name(name)
   , _random_generator(42)
{
   send(_times_eaten, 0);
}

non-greedy join 개체를 사용하여 젓가락 양 쪽에 대한 메시지 버퍼에서 메시지를 받도록 pickup_chopsticks 메서드를 수정합니다.

// Gains access to the chopsticks.
vector<int> pickup_chopsticks()
{
   // Create a non-greedy join object and link it to the left and right 
   // chopstick.
   join<chopstick, non_greedy> j(2);
   _left.link_target(&j);
   _right.link_target(&j);

   // Receive from the join object. This resolves the deadlock situation
   // because a non-greedy join removes the messages only when a message
   // is available from each of its sources.
   return receive(&j);
}

젓가락 양 쪽에 대한 메시지 버퍼에 메시지를 보내 젓가락에 대한 액세스를 해제하도록 putdown_chopsticks 메서드를 수정합니다.

// Releases the chopsticks for others.
void putdown_chopsticks(int left, int right)
{
   // Add the values of the messages back to the message queue.
   asend(&_left, left);
   asend(&_right, right);
}

pickup_chopsticks 메서드의 결과를 보관하고 해당 결과를 putdown_chopsticks 메서드에 전달하도록 run 메서드를 수정합니다.

// Performs the main logic of the dining philosopher algorithm.
void run()
{
   // Repeat the thinks/eat cycle a set number of times.
   for (int n = 0; n < eat_count; ++n)
   {
      think();

      vector<int> v = pickup_chopsticks(); 

      eat();

      send(_times_eaten, n+1);

      putdown_chopsticks(v[0], v[1]);
   }

   done();
}

각각 하나의 메시지를 보관하는 unbounded_buffer 개체의 배열이 되도록 wmain 함수에서 chopsticks 변수 선언을 수정합니다.

// Create an array of message buffers to hold the chopsticks.
array<unbounded_buffer<chopstick>, philosopher_count> chopsticks;

// Send a value to each message buffer in the array.
// The value of the message is not important. A buffer that contains
// any message indicates that the chopstick is available.
for_each (chopsticks.begin(), chopsticks.end(), 
   [](unbounded_buffer<chopstick>& c) {
      send(c, 1);
});

예제

설명

다음은 non-greedy join 개체를 사용하여 교착 상태 위험을 제거하는 전체 예제를 보여 줍니다.

코드

// philosophers-join.cpp
// compile with: /EHsc
#include <agents.h>
#include <string>
#include <array>
#include <iostream>
#include <algorithm>
#include <random>

using namespace Concurrency;
using namespace std;

// Defines a single chopstick.
typedef int chopstick;

// The total number of philosophers.
const int philosopher_count = 5;

// The number of times each philosopher should eat.
const int eat_count = 50;

// Implements the logic for a single dining philosopher.
class philosopher : public agent 
{
public:
   explicit philosopher(unbounded_buffer<chopstick>& left, 
      unbounded_buffer<chopstick>& right, const wstring& name)
      : _left(left)
      , _right(right)
      , _name(name)
      , _random_generator(42)
   {
      send(_times_eaten, 0);
   }

   // Retrieves the number of times the philosopher has eaten.
   int times_eaten()
   {
      return receive(_times_eaten);
   }

   // Retrieves the name of the philosopher.
   wstring name() const
   {
      return _name;
   }

protected:
   // Performs the main logic of the dining philosopher algorithm.
   void run()
   {
      // Repeat the thinks/eat cycle a set number of times.
      for (int n = 0; n < eat_count; ++n)
      {
         think();

         vector<int> v = pickup_chopsticks(); 

         eat();

         send(_times_eaten, n+1);

         putdown_chopsticks(v[0], v[1]);
      }

      done();
   }

   // Gains access to the chopsticks.
   vector<int> pickup_chopsticks()
   {
      // Create a non-greedy join object and link it to the left and right 
      // chopstick.
      join<chopstick, non_greedy> j(2);
      _left.link_target(&j);
      _right.link_target(&j);

      // Receive from the join object. This resolves the deadlock situation
      // because a non-greedy join removes the messages only when a message
      // is available from each of its sources.
      return receive(&j);
   }

   // Releases the chopsticks for others.
   void putdown_chopsticks(int left, int right)
   {
      // Add the values of the messages back to the message queue.
      asend(&_left, left);
      asend(&_right, right);
   }

   // Simulates thinking for a brief period of time.
   void think()
   {
      random_wait(100);
   }

   // Simulates eating for a brief period of time.
   void eat()
   {      
      random_wait(100);      
   }

private:
   // Yields the current context for a random period of time.
   void random_wait(unsigned int max)
   {
      Concurrency::wait(_random_generator()%max);
   }

private:
   // Message buffer for the left chopstick.
   unbounded_buffer<chopstick>& _left;
   // Message buffer for the right chopstick.
   unbounded_buffer<chopstick>& _right;

   // The name of the philosopher.
   wstring _name;
   // Stores the number of times the philosopher has eaten.
   overwrite_buffer<int> _times_eaten;

   // A random number generator.
   mt19937 _random_generator;
};

int wmain()
{
   // Create an array of message buffers to hold the chopsticks.
   array<unbounded_buffer<chopstick>, philosopher_count> chopsticks;

   // Send a value to each message buffer in the array.
   // The value of the message is not important. A buffer that contains
   // any message indicates that the chopstick is available.
   for_each (chopsticks.begin(), chopsticks.end(), 
      [](unbounded_buffer<chopstick>& c) {
         send(c, 1);
   });

   // Create an array of philosophers. Each pair of neighboring 
   // philosophers shares one of the chopsticks.
   array<philosopher, philosopher_count> philosophers = {
      philosopher(chopsticks[0], chopsticks[1], L"aristotle"),
      philosopher(chopsticks[1], chopsticks[2], L"descartes"),
      philosopher(chopsticks[2], chopsticks[3], L"hobbes"),
      philosopher(chopsticks[3], chopsticks[4], L"socrates"),
      philosopher(chopsticks[4], chopsticks[0], L"plato"),
   };

   // Begin the simulation.
   for_each (philosophers.begin(), philosophers.end(), [](philosopher& p) {
      p.start();
   });

   // Wait for each philosopher to finish and print his name and the number
   // of times he has eaten.
   for_each (philosophers.begin(), philosophers.end(), [](philosopher& p) {
      agent::wait(&p);
      wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
   });
}

주석

이 예제의 결과는 다음과 같습니다.

aristotle ate 50 times.
descartes ate 50 times.
hobbes ate 50 times.
socrates ate 50 times.
plato ate 50 times.

코드 컴파일

예제 코드를 복사하여 Visual Studio 프로젝트 또는 philosophers-join.cpp 파일에 붙여넣고 Visual Studio 2010 명령 프롬프트 창에서 다음 명령을 실행합니다.

cl.exe /EHsc philosophers-join.cpp

[맨 위로 이동]

참고 항목

개념

기타 리소스

비동기 에이전트 방법 및 연습 항목

다음을 통해 공유

연습: join을 사용하여 교착 상태 방지

사전 요구 사항

단원

철학자들의 만찬 문제

간단한 구현

예제

코드

코드 컴파일

join을 사용하여 교착 상태 방지

이 예제에서 교착 상태를 방지하려면

예제

설명

코드

주석

코드 컴파일

참고 항목

개념

기타 리소스

추가 리소스