食事の哲学者の問題 II

前回の投稿「食事の哲学者の問題 I」では、アンドレ・エイドリアン は、古典的な食事哲学者の問題の分析を開始しました。現在、彼はアトミック、ミューテックス、およびロックを使用しています。

ベンジャミン D. エシャム / ウィキメディア コモンズ、CC BY-SA 3.0、https://commons.wikimedia.org/w/index.php?curid=56559

アンドレの分析が最後に終わった場所について簡単に思い出させてください。

リソース階層でまだ誤ったビジー待機

// dp_5.cpp
#include <iostream>
#include <thread>
#include <chrono>
#include <atomic>

int myrand(int min, int max) {
 return rand()%(max-min)+min;
}

void lock(std::atomic<int>& m) {
 while (m)
 ; // busy waiting
 m=1;
}

void unlock(std::atomic<int>& m) {
 m=0;
}

void phil(int ph, std::atomic<int>& ma, std::atomic<int>& mb) {
 while(true) {
 int duration=myrand(1000, 2000);
 std::cout<<ph<<" thinks "<<duration<<"ms\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(duration));

 lock(ma);
 std::cout<<"\t\t"<<ph<<" got ma\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(1000));

 lock(mb);
 std::cout<<"\t\t"<<ph<<" got mb\n";

 duration=myrand(1000, 2000);
 std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(duration));

 unlock(mb);
 unlock(ma);
 }
}

int main() {
 std::cout<<"dp_5\n";
 srand(time(nullptr));

 std::atomic<int> m1{0}, m2{0}, m3{0}, m4{0};

 std::thread t1([&] {phil(1, m1, m2);});
 std::thread t2([&] {phil(2, m2, m3);});
 std::thread t3([&] {phil(3, m3, m4);});
 std::thread t4([&] {phil(4, m1, m4);});

 t1.join();
 t2.join();
 t3.join();
 t4.join();
}

プログラムは問題ないように見えますが、誤動作の可能性はわずかです . lock() の 2 つの操作は、「利用可能なリソースです」と「リソースを使用中としてマークする」です。 関数はアトミックですが、それでも 2 つの操作です。これら 2 つの操作の間に、スケジューラはスレッド スイッチを配置できます。そして、この最も不都合な時期にスレッドを切り替えると、プログラム内に非常に見つけにくいバグが発生する可能性があります。

リソース階層による最適化されたビジー待機

ありがたいことに、現在のすべてのコンピューターには、「リソースをテストし、テストが肯定的であればリソースを使用中としてマークする」というアトミック操作があります。プログラミング言語 C++ では、atomic_flag type は、この特別な「テストと設定」操作を利用できるようにします。ファイル dp_6.cpp 食事する哲学者の問題の最初の正解は次のとおりです:

// dp_6.cpp
#include <iostream>
#include <thread>
#include <chrono>
#include <atomic>

int myrand(int min, int max) {
 return rand()%(max-min)+min;
}

void lock(std::atomic_flag& m) {
 while (m.test_and_set())
 ; // busy waiting
}

void unlock(std::atomic_flag& m) {
 m.clear();
}

void phil(int ph, std::atomic_flag& ma, std::atomic_flag& mb) {
 while(true) {
 int duration=myrand(1000, 2000);
 std::cout<<ph<<" thinks "<<duration<<"ms\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(duration));

 lock(ma);
 std::cout<<"\t\t"<<ph<<" got ma\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(1000));

 lock(mb);
 std::cout<<"\t\t"<<ph<<" got mb\n";

 duration=myrand(1000, 2000);
 std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(duration));

 unlock(mb);
 unlock(ma);
 }
}

int main() {
 std::cout<<"dp_6\n";
 srand(time(nullptr));

 std::atomic_flag m1, m2, m3, m4;
 unlock(m1);
 unlock(m2);
 unlock(m3);
 unlock(m4);

 std::thread t1([&] {phil(1, m1, m2);});
 std::thread t2([&] {phil(2, m2, m3);});
 std::thread t3([&] {phil(3, m3, m4);});
 std::thread t4([&] {phil(4, m1, m4);});

 t1.join();
 t2.join();
 t3.join();
 t4.join();
}

プログラム バージョン 6 の出力は、最後の出力と似ています。食事の哲学者の問題は気さくです。 1 つのリソースは 2 つのスレッド間でのみ共有されます。 atomic_fla 複数のスレッドが同じリソースを取得したい場合は、スピンロックが必要です。

良好な低 CPU 負荷 リソース階層によるビジー待機

スピンロックの欠点は、ビジー待機です。 lock() の while ループ CPU リソースの浪費です。この問題を解決するには、 sleep_for() を配置します。 この while ループの本体で機能します。 sleep_for() 関数はスケジューラで待機を行います。この待機は、アプリケーションで待機するよりもはるかに優れています。いつものように、価格があります。 sleep_for() プログラムの進行が遅くなります。ファイル dp_7.cpp は 2 番目の正解です:
// dp_7.cpp
void lock(std::atomic_flag& m) { while (m.test_and_set()) std::this_thread::sleep_for(std::chrono::milliseconds(8)); }

注:std::this_thread::yield() sleep_for() の代わりに 作成者のコンピュータの CPU 負荷を軽減しません。 yield()の影響 実装依存です。

std::mutex とリソース階層

ビジーな待機を完全に回避するには、スケジューラーからのさらなる支援が必要です。すべてのスレッドがリソースの状態をスケジューラに通知する場合、スケジューラは「リソースを待機」スレッドを「待機」状態にすることができます。スケジューラーが「リソースが使用可能です」という情報を取得すると、待機中のスレッドの状態が準備完了に変わります。スレッドからスケジューラへの情報交換は高価です。このため、C++ はスピンロックとミューテックスの両方を提供します。スレッドでスピンロックが待機しており、スケジューラでミューテックスが待機しています。ファイル dp_8.cpp ミューテックス ソリューションを示します。 #include <mutex> に注意してください :
// dp_8.cpp
#include <iostream>
#include <thread>
#include <chrono>
#include <mutex>

int myrand(int min, int max) {
 return rand()%(max-min)+min;
}

void phil(int ph, std::mutex& ma, std::mutex& mb) {
 while(true) {
 int duration=myrand(1000, 2000);
 std::cout<<ph<<" thinks "<<duration<<"ms\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(duration));

 ma.lock();
 std::cout<<"\t\t"<<ph<<" got ma\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(1000));

 mb.lock();
 std::cout<<"\t\t"<<ph<<" got mb\n";

 duration=myrand(1000, 2000);
 std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
 std::this_thread::sleep_for(std::chrono::milliseconds(duration));
 mb.unlock(); // (9)
 ma.unlock();
 }
}

int main() {
 std::cout<<"dp_8\n";
 srand(time(nullptr));

 std::mutex m1, m2, m3, m4;

 std::thread t1([&] {phil(1, m1, m2);});
 std::thread t2([&] {phil(2, m2, m3);});
 std::thread t3([&] {phil(3, m3, m4);});
 std::thread t4([&] {phil(4, m1, m4);});

 t1.join();
 t2.join();
 t3.join();
 t4.join();
}

プログラム バージョン 8 は正しく、CPU リソースをほとんど使用しません。 C++ は、ミューテックスへのラッパーを提供して、プログラマーの作業を楽にします。

std::lock_guard リソース階層付き

lock_guard の使用 テンプレートでは、ミューテックスのみをロックに入れます。ミューテックスメンバー関数 lock locks コンストラクターと unlock で自動的に呼び出されます スコープの最後のデストラクタで。 unlock 例外がスローされた場合にも呼び出されます。

便利なバージョンは dp_9.cpp :

// dp_9.cpp

void phil(int ph, std::mutex& ma, std::mutex& mb) { while(true) { int duration=myrand(1000, 2000); std::cout<<ph<<" thinks "<<duration<<"ms\n"; std::this_thread::sleep_for(std::chrono::milliseconds(duration)); std::lock_guard<std::mutex> ga(ma); std::cout<<"\t\t"<<ph<<" got ma\n"; std::this_thread::sleep_for(std::chrono::milliseconds(1000)); std::lock_guard<std::mutex> gb(mb); std::cout<<"\t\t"<<ph<<" got mb\n"; duration=myrand(1000, 2000); std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n"; std::this_thread::sleep_for(std::chrono::milliseconds(duration)); } }

私たちはますます良くなっています。プログラムのバージョン 8 と 9 は正しく、CPU 負荷が軽いです。ただし、プログラムの出力に注意してください。
プログラムの出力が少し文字化けしています。この出力の歪みを以前に見たことがあるかもしれません。スピンロック プログラム バージョン 6 および 7 またはミューテックス プログラム バージョン 8 および 9 には問題はありません。

std::lock_guard リソース階層による同期出力

コンソール出力自体がリソースです。これが、マルチスレッド プログラムで出力が文字化けする理由です。解決策は lock_guard を置くことです すべてのコンソール出力の周り。 dp_10.cpp を参照 :
// dp_10.cpp

std::mutex mo; void phil(int ph, std::mutex& ma, std::mutex& mb) { while(true) { int duration=myrand(1000, 2000); { std::lock_guard<std::mutex> g(mo); std::cout<<ph<<" thinks "<<duration<<"ms\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(duration)); std::lock_guard<std::mutex> ga(ma); { std::lock_guard<std::mutex> g(mo); std::cout<<"\t\t"<<ph<<" got ma\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(1000)); std::lock_guard<std::mutex> gb(mb); { std::lock_guard<std::mutex> g(mo); std::cout<<"\t\t"<<ph<<" got mb\n"; } duration=myrand(1000, 2000); { std::lock_guard<std::mutex> g(mo); std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(duration)); } }

グローバルミューテックス mo コンソール出力リソースを制御します。 coutごと ステートメントはそのブロック内にあり、lock_guard() テンプレートにより、コンソール出力が文字化けしなくなります。

std::lock_guard リソース階層とカウントによる同期出力

ちょっとしたおまけとして、 dp_11.cpp を追加しました .このプログラム バージョンは、同時に食べている哲学者のスレッドの数をカウントします。 4 つのフォークがあるため、2 つの Philosopher スレッドが同時に食べる場合があります。もう一度 #include <atomic>が必要です。 . dp_11.cpp を参照 :
// dp_11.cpp

std::mutex mo; std::atomic<int> cnt = 0; void phil(int ph, std::mutex& ma, std::mutex& mb) { while(true) { int duration=myrand(1000, 2000); { std::lock_guard<std::mutex> g(mo); std::cout<<ph<<" thinks "<<duration<<"ms\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(duration)); std::lock_guard<std::mutex> ga(ma); { std::lock_guard<std::mutex> g(mo); std::cout<<"\t\t"<<ph<<" got ma\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(1000)); std::lock_guard<std::mutex> gb(mb); { std::lock_guard<std::mutex> g(mo); std::cout<<"\t\t"<<ph<<" got mb\n"; } duration=myrand(1000, 2000); ++cnt; { std::lock_guard<std::mutex> g(mo); std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms "<<cnt<<"\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(duration)); --cnt; } }

プログラム バージョン 11 の出力は次のとおりです。

追加は、「eats」ロギングの最後の 1 または 2 です。

次は?

食事の哲学者問題の次の記事で、アンドレは std::unique_lock を使用します。 (C++11)、std::scoped_lock (C++17)、および std::semaphore (C++20).