36

(注: これの多くは、 std::lock (c++11) を使用した Massive CPU loadに関する解説と重複していますが、このトピックは独自の質問と回答に値すると思います。)

最近、次のようなサンプル C++11 コードに遭遇しました。

std::unique_lock<std::mutex> lock1(from_acct.mutex, std::defer_lock);
std::unique_lock<std::mutex> lock2(to_acct.mutex, std::defer_lock);
std::lock(lock1, lock2); // avoid deadlock
transfer_money(from_acct, to_acct, amount);

std::lockうわー、面白いと思いました。標準はそれが何をしていると言っているのだろうか?

C++11 セクション 30.4.3 [thread.lock.algorithm]、段落 (4) および (5):

template void lock(L1&, L2&, L3&...);

4必須:各テンプレート パラメータ タイプは Lockable 要件を満たすものとする [ 注:unique_lockクラス テンプレートは、適切にインスタンス化された場合にこれらの要件を満たす。— エンドノート]

5効果:すべての引数は、各引数に対するlock()try_lock()、またはへの一連の呼び出しによってロックされます。unlock()一連の呼び出しでデッドロックが発生することはありませんが、それ以外は指定されていません。[ 注: try-and-back-off などのデッドロック回避アルゴリズムを使用する必要がありますが、実装の過度の制約を回避するための特定のアルゴリズムは指定されていません。— 終了注 ] または の呼び出しが例外をスローする場合、lock()またはの呼び出しによってロックされていた引数に対して、 が呼び出されます。try_lock()unlock()lock()try_lock()

次の例を考えてみましょう。それを「例 1」と呼びます。

Thread 1                    Thread 2
std::lock(lock1, lock2);    std::lock(lock2, lock1);

このデッドロックはできますか?

標準を単純に読むと、「いいえ」と言われます。すごい!たぶん、コンパイラが私のロックを注文してくれるかもしれません。

次に、例 2 を試してください。

Thread 1                                  Thread 2
std::lock(lock1, lock2, lock3, lock4);    std::lock(lock3, lock4);
                                          std::lock(lock1, lock2);

このデッドロックはできますか?

ここでも、標準を単純に読むと「いいえ」と言われます。ええとああ。これを行う唯一の方法は、ある種のバックオフと再試行のループを使用することです。詳細については、以下をご覧ください。

最後に、例 3:

Thread 1                          Thread 2
std::lock(lock1,lock2);           std::lock(lock3,lock4);
std::lock(lock3,lock4);           std::lock(lock1,lock2);

このデッドロックはできますか?

繰り返しますが、標準を単純に読むと「いいえ」と言われます。(これらの呼び出しのいずれかで「 への呼び出しのシーケンスがlock()「デッドロックを引き起こす」ものではない場合、正確には何ですか?)しかし、これは実装できないと確信しているので、彼らが意味したものではないと思います。

これは、私がこれまで C++ 標準で見た中で最悪のものの 1 つです。私はそれが興味深いアイデアとして始まったと推測しています: コンパイラにロック順序を割り当てさせます。しかし、委員会がそれを噛み砕くと、その結果は実装不可能になるか、再試行ループが必要になります。はい、それは悪い考えです。

「バックオフして再試行」が役立つ場合があると主張できます。それは本当ですが、どのロックを前もってつかもうとしているのかわからない場合に限られます。たとえば、2 番目のロックの ID が 1 番目のロックによって保護されているデータに依存する場合 (たとえば、階層をトラバースしているため)、グラブ - リリース - グラブ スピンを実行する必要がある場合があります。しかし、その場合、事前にすべてのロックを知っているわけではないため、このガジェットを使用することはできません. 一方、事前に必要なロックがわかっている場合、(ほとんどの場合) ループではなく、単純に順序付けを行う必要があります。

また、実装が単純にロックを順番に取得し、バックオフして再試行する場合、例 1 はライブロックになる可能性があることに注意してください。

要するに、このガジェットはせいぜい役に立たないと思います。悪い考えばかりです。

わかりました、質問です。(1) 私の主張や解釈は間違っていますか? (2) そうでなければ、彼らは一体何を考えていたのですか? (3) 「ベスト プラクティス」とはstd::lock完全に回避することであることに全員が同意する必要がありますか?

[アップデート]

一部の回答は、私が標準を誤解していると言い、それから私と同じように解釈し続け、仕様と実装を混同しています。

したがって、明確にするために:

私の標準の読みでは、例 1 と例 2 はデッドロックできません。例 3 は可能ですが、その場合のデッドロックを回避することは実装できないためです。

私の質問の要点は、例 2 のデッドロックを回避するには、バックオフと再試行のループが必要であり、そのようなループは非常に貧弱な方法であるということです。(はい、この些細な例である種の静的分析を行うことで回避できる可能性がありますが、一般的なケースではそうではありません。) また、GCC はこれをビジー ループとして実装していることにも注意してください。

【アップデート2】

ここでの断絶の多くは、哲学の基本的な違いだと思います。

ソフトウェア、特にマルチスレッド ソフトウェアを作成するには、2 つのアプローチがあります。

1 つのアプローチでは、たくさんのものをまとめて実行し、どれだけうまく機能するかを確認します。今日、実際のシステムで誰かがその問題を実証できない限り、コードに問題があると確信することはできません。

もう 1 つのアプローチでは、データ競合がないこと、すべてのループが確率 1 で終了することなどを証明するために厳密に分析できるコードを記述します。この分析は、特定の実装ではなく、言語仕様で保証されているマシン モデル内で厳密に実行します。

後者のアプローチの支持者は、特定の CPU、コンパイラ、コンパイラのマイナー バージョン、オペレーティング システム、ランタイムなどに関するデモに感銘を受けません。アルゴリズムにデータ競合がある場合、実行時に何が起こっても、アルゴリズムは壊れています。アルゴリズムにライブロックがある場合、実行時に何が起こっても、アルゴリズムは壊れています。などなど。

私の世界では、2番目のアプローチは「エンジニアリング」と呼ばれています。最初のアプローチが何と呼ばれているのかわかりません。

私が知る限り、std::lockインターフェースはエンジニアリングには役に立ちません。私は間違っていることが証明されたいです。

4

4 に答える 4

45

デッドロック回避の範囲を誤解していると思います。テキストは、「マルチロ​​ック」とその「マルチロ​​ック」によって実行される個々lockのロックという 2 つの異なるコンテキストで言及されているように見えるため、これは理解できます(ただし、ロック可能なものはそれを実装します)。std::lock状態のテキストstd::lock:

すべての引数は、各引数の lock()、try_lock()、または unlock() への一連の呼び出しによってロックされます。一連の呼び出しでデッドロックが発生してはならない

std::lock10 個の異なる lockable を渡して呼び出した場合、標準ではその呼び出しでデッドロックが発生しないことが保証されています。の制御外でロック可能オブジェクトをロックした場合、デッドロックが回避される保証はありませんstd::lock。つまり、スレッド 1 が A をロックしてから B をロックすると、スレッド 2 が B をロックしてから A をロックすると、スレッド 2 に対してデッドロックが発生する可能性があります。

Thread 1     Thread 2
lock A       lock B
lock B       lock A

それはあり得なかったのでstd::lock(1 つのリソースしかロックしていなかった)、次のようなものだったに違いありませんunique_lock

最初の例のように、両方のスレッドが への1 回の呼び出しで A/B と B/A をロックしようとすると、デッドロックの回避発生します。2 番目の例は、スレッド 2 が既に最初のロックを持っている場合に 2 番目のロックが必要な場合、スレッド 1 がバックオフするため、デッドロックしません。更新された 3 番目の例:std::lock

Thread 1                  Thread 2
std::lock(lock1,lock2);   std::lock(lock3,lock4);
std::lock(lock3,lock4);   std::lock(lock1,lock2);

ロックの原子性は への1 回の呼び出しであるため、デッドロックの可能性はまだありますstd::lock。たとえば、スレッド 1 が と を正常にロックlock1lock2、次にスレッド 2 が と を正常にロックlock3した場合lock4、両方のスレッドが他方が保持するリソースをロックしようとするため、デッドロックが発生します。

だから、あなたの特定の質問に答えて:

1/ はい、標準が言っていることを誤解していると思います。それが話しているシーケンスは明らかに、単一 std::lockの に渡された個々のロック可能オブジェクトに対して実行されるロックのシーケンスです。

2/ 彼らが何を考えていたのかは、わかりにくい場合もあります :-) しかし、そうでなければ自分たちで作成しなければならない機能を、彼らが私たちに提供したいと考えていたと思います。はい、バックオフと再試行は理想的な戦略ではないかもしれませんが、デッドロック回避機能が必要な場合は、代償を払わなければならない場合があります。開発者が何度も何度も書く必要があるよりも、実装がそれを提供する方が良い.

3/ いいえ、避ける必要はありません。ロックの単純な手動注文が不可能な状況に陥ったことはないと思いますが、その可能性を軽視するつもりはありません。そのような状況に陥った場合は、これが役立ちます (したがって、独自のデッドロック回避機能をコーディングする必要はありません)。


バックオフと再試行は問題のある戦略であるというコメントに関しては、はい、それは正しいです。しかし、たとえばロックの順序付けを事前に強制できない場合などに必要になる可能性があるという点を見落としている可能性があります。

そして、それはあなたが思うほど悪いものである必要はありませんロックは によって任意の順序で実行できるため、std::lockバックオフごとに実装が再順序付けされて、「失敗した」ロック可能オブジェクトがリストの先頭に来るのを止めるものは何もありません。つまり、ロックされたものは最前線に集まる傾向があるため、std::lock不必要にリソースを要求する可能性が低くなります。

すでにロックされている唯一のロック可能な呼び出しstd::lock (a, b, c, d, e, f)を考えてみましょう。f最初のロックの試行では、その呼び出しはロックaされてeから で「失敗」しfます。

バックオフ (aによるロック解除e) に続いて、ロックするリストが変更されf, a, b, c, d, e、後続の反復で不必要にロックされる可能性が低くなります。繰り返しの間に他のリソースがロックまたはロック解除される可能性があるため、これは絶対確実ではありませんが、成功する傾向があります。

実際、現在ロックされているものすべてが最前面になるように、すべてのロック可能なものの状態をチェックすることで、最初にリストを並べ替えることさえできます。これにより、プロセスの早い段階で「成功への傾向」操作が開始されます。

これは1 つの戦略にすぎません。他にも、さらに優れた戦略があるかもしれません。そのため、標準はそれがどのように行われるかを義務付けていませんでした.偶然に、より良い方法を思いつく天才がそこにいるかもしれません.

于 2013-08-29T21:16:03.633 に答える
23

std::lock(x, y, ...)への個々の呼び出しをアトミックと考えると、おそらく役立つでしょう。すべての引数をロックできるまでブロックします。アプリオリにロックする必要があるすべてのミューテックスがわからない場合は、この関数を使用しないでください。わかっている場合は、ロックを注文することなく、この機能を安全に使用できます。

しかし、それがあなたがやりたいことなら、ぜひあなたのロックを注文してください.

Thread 1                    Thread 2
std::lock(lock1, lock2);    std::lock(lock2, lock1);

上記はデッドロックしません。スレッドの 1 つは両方のロックを取得し、もう 1 つのスレッドは、最初のスレッドがロックを解放するまでブロックします。

Thread 1                                  Thread 2
std::lock(lock1, lock2, lock3, lock4);    std::lock(lock3, lock4);
                                          std::lock(lock1, lock2);

上記はデッドロックしません。これはトリッキーですが。スレッド 2 がロック 3 とロック 4 をスレッド 1 より先に取得した場合、スレッド 1 は、スレッド 2 が 4 つすべてのロックを解放するまでブロックします。スレッド 1 が最初に 4 つのロックを取得すると、スレッド 1 が 4 つのロックをすべて解放するまで、lock3 と lock4 をロックした時点でスレッド 2 がブロックされます。

Thread 1                          Thread 2
std::lock(lock1,lock2);           std::lock(lock3,lock4);
std::lock(lock3,lock4);           std::lock(lock1,lock2);

はい、上記はデッドロックする可能性があります。上記は、次とまったく同等であると見なすことができます。

Thread 1                          Thread 2
lock12.lock();                    lock34.lock();
lock34.lock();                    lock12.lock();

アップデート

デッドロックとライブロックはどちらも正確性の問題であるという誤解があると思います。

実際には、デッドロックはプロセスをフリーズさせるため、正確性の問題です。また、ライブロックはプロセスの速度を低下させるため、パフォーマンスの問題ですが、タスクは正しく完了します。その理由は、ライブロックは (実際には) 無期限に持続しないからです。

<disclaimer> 作成できるライブロックには永続的な形式があり、したがってデッドロックと同等です。この回答はそのようなコードには対応しておらず、そのようなコードはこの問題には関係ありません。 </disclaimer>

この回答に示されている歩留まりは、ライブロックを大幅に減少させ、パフォーマンスを大幅に向上させる重要なパフォーマンスの最適化ですstd::lock(x, y, ...)

更新 2

かなりの遅れの後、私はこの主題に関する論文の最初のドラフトを書きました。この論文では、この仕事を成し遂げる 4 つの異なる方法を比較しています。これには、コピーして自分のコードに貼り付けて自分でテストできるソフトウェアが含まれています。

http://howardhinnant.github.io/dining_philosophers.html

于 2013-08-29T21:55:29.550 に答える
4

標準語との混乱は、このステートメントによるものと思われます

5効果:すべての引数は、各引数に対するlock()try_lock()、またはへの一連の呼び出しによってロックされます。unlock()

std::lockこれは、元の呼び出しの各引数で再帰的に自分自身を呼び出すことを意味するものではありません。

Lockable の概念 ( §30.2.5.4 [ thread.req.lockable.req ])を満たすオブジェクトは、これらのメンバー関数の 3 つすべてを実装する必要があります。デッドロックを回避するために実装で定義された何かを実行しながら、不特定の順序で各引数でこれらのメンバー関数を呼び出して、すべてのオブジェクトのロックを取得しようとします。std::lock

例 3 では、std::lockロックを取得するすべてのオブジェクトに対して単一の呼び出しを発行していないため、デッドロックが発生する可能性があります。

例 2ではデッドロックは発生しません。Howard の回答でその理由が説明されています。

于 2013-08-29T21:29:39.443 に答える
1

C++11 は Boost からこの機能を採用しましたか?

もしそうなら、ブーストの説明は有益です(私のものを強調してください):

効果:引数として指定された Lockable オブジェクトを、デッドロックを回避する方法で、不特定かつ不確定な順序でロックします。デッドロックのリスクなしに、同じミューテックス (または他のロック可能なオブジェクト) を持つ複数のスレッドから、異なる順序でこの関数を同時に安全に呼び出すことができます。提供された Lockable オブジェクトに対する lock() または try_lock() 操作のいずれかが例外をスローした場合、関数によって取得されたすべてのロックは、関数が終了する前に解放されます。

于 2015-04-30T12:54:55.167 に答える