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

이 항목에서는 식사 철학자 문제를 사용하여 동시성::join 클래스를 사용하여 애플리케이션의 교착 상태를 방지하는 방법을 설명합니다. 소프트웨어 애플리케이션에서 교착 상태는 두 개 이상의 프로세스가 각각 리소스를 보유하고 함께 다른 프로세스가 다른 리소스를 해제할 때까지 대기하는 경우 발생합니다.

식사 철학자 문제는 여러 동시 프로세스 간에 리소스 집합을 공유할 때 발생할 수 있는 일반적인 문제 집합의 특정 예입니다.

필수 조건

이 연습을 시작하기 전에 다음 항목을 읽어보세요.

• 비동기 에이전트

• 연습: 에이전트 기반 애플리케이션 만들기

• 비동기 메시지 블록

• 메시지 전달 함수

• 동기화 데이터 구조

섹션

이 연습에는 다음과 같은 섹션이 있습니다.

• 식사 철학자 문제

• 순진한 구현

• 조인을 사용하여 교착 상태 방지

식사 철학자 문제

식사 철학자 문제는 애플리케이션에서 교착 상태가 발생하는 방법을 보여 줍니다. 이 문제에서 다섯 명의 철학자가 원탁에 앉아 있습니다. 모든 철학자는 생각과 먹는 것을 번갈아 가며 합니다. 모든 철학자는 왼쪽에 있는 이웃과 젓가락을 공유하고 다른 젓가락을 오른쪽에 있는 이웃과 공유해야 합니다. 다음 그림에서는 이 레이아웃을 보여 줍니다.

먹기 위해 철학자는 두 개의 젓가락을 들고 있어야합니다. 모든 철학자가 하나의 젓가락을 들고 다른 젓가락을 기다리고 있다면, 어떤 철학자도 먹을 수 없고 모든 굶어 죽을 수 있습니다.

[맨 위로 이동]

순진한 구현

다음 예제에서는 식사 철학자 문제의 순진한 구현을 보여 줍니다. philosopher 동시성::agent에서 파생되는 클래스를 사용하면 각 철학자가 독립적으로 작업할 수 있습니다. 이 예제에서는 동시성::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 (begin(philosophers), end(philosophers), [](philosopher& p) {
      p.start();
   });

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

코드 컴파일

예제 코드를 복사하여 Visual Studio 프로젝트에 붙여넣거나 이름이 지정된 philosophers-deadlock.cpp 파일에 붙여넣은 다음 Visual Studio 명령 프롬프트 창에서 다음 명령을 실행합니다.

cl.exe /EHsc philosophers-deadlock.cpp

[맨 위로 이동]

조인을 사용하여 교착 상태 방지

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

이 예제를 이전 예제와 연결하기 위해 클래스는 philosopher 동시성::unbounded_buffer 개체 및 개체를 사용하여 각 critical_section 개체를 join 대체합니다. 이 개체는 join 철학자에게 젓가락을 제공하는 중재자 역할을 합니다.

이 예제에서는 대상 개체에서 메시지를 받을 때 메시지 큐에서 unbounded_buffer 메시지가 제거 되므로 클래스를 사용 합니다unbounded_buffer. 이렇게 하면 unbounded_buffer 메시지를 포함하는 개체가 젓가락을 사용할 수 있음을 나타낼 수 있습니다. 메시지가 없는 개체는 unbounded_buffer 젓가락이 사용되고 있음을 나타냅니다.

이 예제에서는 욕심 없는 조인이 각 philosopher 개체에 메시지를 포함하는 경우에만 두 unbounded_buffer 젓가락에 대한 액세스 권한을 부여하기 때문에 욕심 join 이 없는 개체를 사용합니다. 탐욕스러운 조인은 사용할 수 있게 되는 즉시 메시지를 수락하기 때문에 교착 상태를 방지하지 않습니다. 모든 greedy join 개체가 메시지 중 하나를 수신하지만 다른 개체가 사용할 수 있게 될 때까지 영원히 기다리는 경우 교착 상태가 발생할 수 있습니다.

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

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

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

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

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

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

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

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);
}

1. pickup_chopsticks 욕심 join 이 없는 개체를 사용하여 두 젓가락에 대한 메시지 버퍼에서 메시지를 수신하도록 메서드를 수정합니다.

// 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);
}

1. 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);
}

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

// 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();
}

1. 함수의 변수 선언을 chopsticks wmain 각각 하나의 메시지를 보유하는 개체의 unbounded_buffer 배열로 수정합니다.

// 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 (begin(chopsticks), end(chopsticks), 
   [](unbounded_buffer<chopstick>& c) {
      send(c, 1);
});

설명

다음은 비욕심 개체를 사용하여 교착 상태의 위험을 제거하는 완료된 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 (begin(chopsticks), end(chopsticks), 
      [](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 (begin(philosophers), end(philosophers), [](philosopher& p) {
      p.start();
   });

   // Wait for each philosopher to finish and print his name and the number
   // of times he has eaten.
   for_each (begin(philosophers), end(philosophers), [](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 명령 프롬프트 창에서 다음 명령을 실행합니다.

cl.exe /EHsc philosophers-join.cpp

[맨 위로 이동]

참고 항목

동시성 런타임 연습
비동기 에이전트 라이브러리
비동기 에이전트
비동기 메시지 블록
메시지 전달 함수
동기화 데이터 구조