クリスマスの時期に、アンドレ・エイドリアンといい話をしました。 .彼は、現代の C++ を使用して、さまざまな方法で古典的な食事の哲学者の問題を解決しました。私は彼に、この古典的な同期の問題に関する記事を書くよう説得し、3 回連続して投稿できることをうれしく思います。
ベンジャミン D. エシャム / ウィキメディア コモンズ、CC BY-SA 3.0、https://commons.wikimedia.org/w/index.php?curid=56559
Andre Adrian による C++ での食事の哲学者
ダイニング哲学者の問題は、エドガー・W・ダイクストラによって説明されました。 「0 から 4 までの番号が付けられた 5 人の哲学者が、テーブルが置かれた家に住んでいて、それぞれの哲学者がテーブルに自分の場所を持っています。彼らの唯一の問題は、哲学の問題以外では、提供される料理が非常に難しい種類のものであることです。 2本のフォークで食べなければならないスパゲッティ.各プレートの横に2本のフォークがあるので、問題はありません.結果として、2人の隣人が同時に食べることはありません. [ref 1971;ダイクストラ; EWD310 順次プロセスの階層的順序付け; https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD310.html]
次の問題の説明を使用します:4 人の哲学者がシンプルな生活を送っています。すべての哲学者は同じルーチンを実行します。彼はランダムな時間考え、最初のフォークを手に入れ、2 番目のフォークを手に入れ、ランダムな時間食べ、フォークを置き、再び考え始めます。問題を面白くするために、4 人の哲学者は 4 つのフォークしか持っていません。哲学者 1 番は、食べるために 1 番と 2 番のフォークを取らなければなりません。哲学者 2 はフォーク 2 と 3 を必要とし、哲学者 4 は食べるためにフォーク 4 と 1 を必要とします。食後、哲学者はフォークをテーブルに戻します。
複数のリソースの使用
問題の記述からプログラミングへと進むにつれて、哲学者をスレッドに、フォークをリソースに変換します。最初のプログラム - dp_1.cpp - 4 つの「philosopher」スレッドと 4 つの「fork」リソース整数を作成します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | // dp_1.cpp
#include <iostream>
#include <thread>
#include <chrono>
int myrand(int min, int max) {
return rand()%(max-min)+min;
}
void lock(int& m) {
m=1;
}
void unlock(int& m) {
m=0;
}
void phil(int ph, int& ma, 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_1\n";
srand(time(nullptr));
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, m4, m1);});
t1.join();
t2.join();
t3.join();
t4.join();
}
|
main() function 42 行目で乱数を確立します。乱数ジェネレータのシード値を 1970 年 1 月 1 日からの秒数に設定します。44 行目でフォーク リソースを定義します。次に、46 行目から 4 つのスレッドを開始します。スレッドの早期終了を避けるために、 51 行目から始まるスレッドに参加します。スレッド関数 phil() 永久ループがあります。 while(true) ステートメントは常に true です 、したがって、スレッドは決して終了しません。問題の説明には、「彼はランダムな期間考える」と書かれています。まず、関数 myrand( でランダムな期間を計算します )、20 行目と 6 行目を参照してください。関数 myrand() [min, max) の範囲で疑似乱数の戻り値を生成します。プログラム トレースでは、哲学者の番号、現在の「考えている」状態、および期間をコンソールに記録します。 sleep_for() ステートメントにより、スケジューラーはその期間スレッドを待機状態にします。 「実際の」プログラム アプリケーションのソース コードでは、sleep_for() の代わりにアップ タイムを使用します。 .哲学者のスレッド思考時間が終わった後、彼は「最初のフォークを手に入れる」.行 24 を参照してください。関数 lock() を使用します。 「gets fork」を実行します。現時点では、関数 lock() よくわからないので非常に単純です。 fork リソースの値を 1 に設定しました。10 行目を参照してください。哲学者スレッドが最初の fork を取得した後、彼は誇らしげに新しい状態を "got ma" で発表します。 " コンソール出力。これで、スレッドは "2 番目のフォークを取得" します。28 行目を参照してください。対応するコンソール出力は "got mb" です。 次の状態は「he eats」 ". ここでも継続時間を決定し、コンソール出力を生成し、 sleep_for() でスレッドを占有します。 .行 31 を参照してください。状態 "he eats の後 " 哲学者はフォークを下ろします。35 行目と 14 行目を参照してください。 unlock() この関数も非常に単純で、リソースを 0 に戻します。
コンパイラの最適化を行わずにプログラムをコンパイルしてください。その理由は後で見ていきます。プログラムのコンソール出力は有望に見えます:
私たちはすでに食事哲学者の問題を解決しましたか?プログラムの出力は、この質問に答えるほど詳細ではありません。
ロギングによる複数リソースの使用
ロギングをさらに追加する必要があります。現時点では、関数 lock() リソースが使用される前に fork が利用可能かどうかをチェックしません。 lock() の改良版 プログラム内 dp_2.cpp です:
void lock(int& m) {
if (m) {
std::cout<<"\t\t\t\t\t\tERROR lock\n";
}
m=1;
}
プログラム バージョン 2 では、次の出力が生成されます。
「ERROR lock」が表示されます " コンソール出力。この出力は、2 人の哲学者が同じリソースを同時に使用していることを示しています。何ができるでしょうか?
リソース階層なしの誤ったビジー待機
lock() の if ステートメントを変更できます while ステートメントに。この while ステートメントはスピンロックを生成します。スピンロックは、ビジーな待機を意味する凝った言葉です。 fork リソースが使用されている間、スレッドは使用中の状態から使用可能な状態への変更を待ってビジー状態になります。まさにこの瞬間に、fork リソースを使用中の状態に再度設定します。プログラム内 dp_3.cpp
void lock(int& m) {
while (m)
; // busy waiting
m=1;
}
この小さな変更は、食事の哲学者の問題に対する正しい解決策ではないことを信じてください.間違ったリソースの使用法はなくなりました。しかし、別の問題があります。プログラム バージョン 3 の出力を参照してください。
すべての哲学者スレッドは、最初のフォーク リソースを取得し、2 番目のフォークを取得できません。私たちは何ができる？ Andrew S. Tanenbaum は次のように書いています。 [ref 2006;タネンバウム;オペレーティングシステム。設計と実装、第 3 版。第3.3.5章]
リソース階層による誤ったビジー待機
このソリューションは、リソース階層または部分順序付けとして知られています。食事の哲学者の問題では、部分的な順序付けは簡単です。最初に取られるフォークは、番号が小さいフォークでなければなりません。哲学者 1 から 3 の場合、リソースは正しい順序で取得されます。正しい半順序付けのために変更が必要なのは、哲学者スレッド 4 だけです。最初に fork リソース 1 を取得し、次に fork リソース 4 を取得します。ファイル dp_4.cpp のメイン プログラムを参照してください。 :
int main() {
std::cout<<"dp_4\n";
srand(time(nullptr));
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();
}
プログラム バージョン 4 の出力は問題ないようです。
これで、間違ったリソースの使用やデッドロックはなくなりました。勇気を出して、コンパイラの最適化を使用します。高速に実行できる優れたプログラムが必要です。これは、コンパイラの最適化を使用したプログラム バージョン 4 の出力です:
食べるのはいつも同じ哲学者の糸です。コンパイラの最適化の設定によって、プログラムの動作が変わる可能性はありますか?はい、可能です。哲学者スレッドは、fork リソースの値をメモリから読み取ります。コンパイラの最適化により、これらのメモリの読み取りの一部が最適化されます。すべてに価格があります!
リソース階層でまだ誤ったビジー待機
プログラミング言語 C++ には、アトミック型を定義するためのアトミック テンプレートがあります。あるスレッドがアトミック オブジェクトに書き込み、別のスレッドが読み取りを行っている場合、動作は明確に定義されています。ファイル内 dp_5.cpp atomic<int> を使用します フォークリソース用。 11、17、21、および 47 行を参照してください。 <atomic> が含まれています。 5行目:
// 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();
}
プログラム バージョン 5 の出力は次のとおりです。
次は?
この食事の哲学者の問題の次の記事では、不正行為のわずかな可能性を解決します .これまでのところ、正しいプログラムはありません。