チュートリアル: join を使用したデッドロックの防止

このトピックでは、concurrency::join クラスを使用してアプリケーションでデッドロックを防止する方法について、"食事する哲学者の問題" を使用して説明します。 ソフトウェア アプリケーションで、2 つ以上のプロセスがそれぞれリソースを確保し、別のプロセスがリソースを解放するのをお互いに待機すると、デッドロックが発生します。

"食事する哲学者の問題" は、リソース セットが複数の同時実行プロセス間で共有される場合に発生する可能性のある一般的な問題の特定の例です。

前提条件

このチュートリアルを開始する前に、次のトピックを参照してください。

• 非同期エージェント

• チュートリアル: エージェント ベースのアプリケーションの作成

• 非同期メッセージ ブロック

• メッセージ パッシング関数

• 同期データ構造

セクション

このチュートリアルは、次のセクションで構成されています。

• ダイニング哲学者の問題

• 単純な実装

• join を使用したデッドロックの防止

ダイニング哲学者の問題

"食事する哲学者の問題" は、アプリケーションでどのようにデッドロックが発生するかを示します。 この問題では、5 人の哲学者が丸いテーブルを囲んで座っています。 どの哲学者も思索と食事を交互に行っています。 どの哲学者も左隣の哲学者と 1 本の箸を共有する必要があり、また右隣の哲学者とも別の 1 本の箸を共有する必要があります。 次の図は、この配置を表しています。

食事をするには、哲学者は 2 本の箸を持つ必要があります。 すべての哲学者が 1 本の箸を持ち、もう 1 本の箸を待つと、どの哲学者も食事することができず、すべての哲学者が餓死することになります。

[トップ]

単純な実装

次の例は、"食事する哲学者の問題" を考慮していない実装を示しています。 concurrency::agent から派生させた philosopher クラスにより、各哲学者は独立して行動できます。 この例では、concurrency::critical_section オブジェクトの共有配列を使用して、各 philosopher オブジェクトに対し、2 本の箸への排他アクセス権を与えています。

この実装を図に関連付けて説明すると、philosopher クラスは 1 人の哲学者を表します。 int 変数は、それぞれの箸を表します。 critical_section オブジェクトは、箸が置かれる箸置きとして機能します。 run メソッドは、哲学者の生命をシミュレートしています。 think メソッドは、考える行為をシミュレートしており、eat メソッドは、食事する行為をシミュレートしています。

philosopher オブジェクトは、critical_section メソッドを呼び出す前に、両方の eat オブジェクトをロックして、箸置きから箸が取られたことをシミュレートします。 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

[トップ]

join を使用したデッドロックの防止

このセクションでは、メッセージ バッファーおよびメッセージ パッシング関数を使用して、デッドロックを発生させないようにする方法について説明します。

この例を前の例に関連付けて説明すると、philosopher クラスでは、各 critical_section オブジェクトの代わりに、concurrency::unbounded_buffer オブジェクトおよび join オブジェクトが使用されます。 join オブジェクトは、哲学者に箸を与える決定者として機能します。

この例では、unbounded_buffer クラスを使用しています。これは、ターゲットが unbounded_buffer オブジェクトからメッセージを受け取ったときに、そのメッセージはメッセージ キューから削除されるためです。 これにより、メッセージを保持する unbounded_buffer オブジェクトは、箸が使用できることを示すことができます。 メッセージを保持しない unbounded_buffer オブジェクトは、箸が使用されていることを示します。

この例では、最短一致の join オブジェクトを使用しています。最短一致の join は、両方の philosopher オブジェクトにメッセージが含まれる場合に限り、各 unbounded_buffer オブジェクトに対し、両方の箸へのアクセス権を与えるためです。 最長一致の join は、メッセージが使用できるようになるとすぐにメッセージを受け取るため、最長一致の join ではデッドロックは防止されません。 すべての最長一致 join オブジェクトがメッセージのいずれかを受け取り、一方で他のメッセージが使用できるようになるのを長時間待つ場合、デッドロックが発生する可能性があります。

最長一致の join および最短一致の join の詳細、およびさまざまなメッセージ バッファーの違いの詳細については、「非同期メッセージ ブロック」を参照してください。

この例でデッドロックを防止するには

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 変数の宣言を変更して、それぞれが 1 つのメッセージを保持する 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

[トップ]

関連項目

コンカレンシー ランタイムのチュートリアル
非同期エージェント ライブラリ
非同期エージェント
非同期メッセージ ブロック
メッセージ パッシング関数
同期データ構造