たまたまこれが当社のブログの3番目の投稿であり、最初の2つと同様に、マルチスレッドプログラミングと発生する問題に取り組んでいます。 特定のハードウェアプラットフォーム上のプログラムのダイナミクスによって主に決定されるため、マルチスレッドプログラムの作成時に発生する状況は非常に困難であるという独自の困難な方法で経験したため、偶然ではありませんでした。 ほとんどのプログラマーは、1台のコンピューター、別のコンピューターで正常に動作するプログラムが完全に予期せず突然クラッシュし始める状況に遭遇したと確信しています。
以前の投稿を書いているとき、私たちは許されない間違いを犯し、複雑なものからの相互ブロックを検討し始めましたが、私たちにとっては最も興味深いケースです。 残念なことに、Habrの親愛なる聴衆はそれを感謝しませんでした。 私たちは急いで、初めてではなくても自分自身を修正しますが、ロック問題の検討には最初から近づいています。 ただし、なぜそれが必要なのか、マルチスレッドプログラムを作成するときの同期の手段は何かを知っていると期待しています。
この投稿で説明するレシピは非常にシンプルですが、すべてのプロのプログラマーが意識的に使用しているわけではなく、「何らかの理由で、そのキャプチャされたミューテックスをつかむべきではない」という感覚に導かれています。 これは私たちが何年もの間生きてきた方法であり、ひどく重要な瞬間に、私たちのお気に入りのソフトウェアが、お客様に緊急に送る必要のある「鉄のかけら」の行き詰まりなしに1時間生きることができないことに気づきませんでした。 この問題の解決のために主要なプログラマーの数日間の仕事を殺して、私たちは人生を変えた決定を下しました-私たちは相互ロックの状況を厳しく形式化することを始めました。これがなぜできるのかについての厳密な数学的証明を含む 私たちの研究は従業員の一人によって候補論文に退化したと言わなければなりませんが、そこで使用されているプレゼンテーション形式がここで興味深いかどうかはわかりません...
だから、最初からロックについて...
デッドロックの性質
デッドロックの状況の数学的に検証された複雑な定義には触れず、単に言います：デッドロックは、あるスレッドが何かが起こるのを待っているシステムの状態であり、別のスレッドが何かが起こるのを待っているので、これは起こりえないその後、最初のストリームから。
ミューテックスが常にロックの原因であることが一般に受け入れられていますが、これは完全に正確ではありません。 ブロッキングの理由は、あるスレッドから別のスレッドを待機すること、たとえば、条件変数のシグナルを待機すること、またはそれほど明白ではないが別のスレッドが完了するのを待機すること（スレッドの待機/結合）を含む手段および同期メカニズムである。 理論的には、実際には、2番目のケースは同じ「信号待ち」と同じですが、この同期操作の暗黙的な性質により、デッドロックを検索するときに、潜在的な脅威ソースとしてそれを忘れてしまい、コード内で気付かないことがよくあります。
最も単純な相互ロックの特定の状況の検討に進む前に、マルチスレッドプログラムとその中で発生する状況を説明するために使用するモデルについていくつか説明します。
マルチスレッドプログラムのモデルに関するいくつかの言葉
このモデルを「遷移のモデル」と呼び、各グラフがストリーム（サブジェクト）を表す指向グラフのコレクションです。 各グラフには、同期手段がまだ使用されていないときの状態に対応する1つの開始頂点があり、同期手段がまだ使用されていないときの状態に対応する1つの終了頂点があります。 最終的なピークに達すると、フローが自動的に再開すると想定されています。 グラフの他のすべての頂点は、1つまたは別の同期ツールに関する操作を表します。たとえば、L（ロック）-ミューテックスのキャプチャ、U（ロック解除）-ミューテックスの解放などです。 申し立てを証明するには、同期ツールに関する個々の操作の実行間の時間をモデルが無視し、スピーカーの可能な範囲を無限に拡大することが重要です。 Habrオーディエンスがモデルの数学的および物理的な本質に興味がある場合は、このトピックに関する別の投稿を書く準備ができていますが、ここで...はマルチスレッドプログラミングに関する長くて興味深い話の始まりにすぎません。
単一のストリーム（サブジェクト）で構成されるモデルの例：
図1
この図に従って、被験者は2つの分岐を通過できます。0、L1、U1、0または0、L1、L2、U2、U1、0。 L1、U1、0}および{0、L1、L2、U2、U1、0}。 同期手段に関するアクション間の遷移時間は有限であると仮定します。 アルゴリズム的に正しい。 発生する可能性のないユーザーアクションを待機している間、ミューテックスをキャプチャして保持するための同期エラーは考慮しません。
相互ブロッキングの状況の潜在的な可能性についてプログラムを研究するには、プログラム内のすべての可能なアクターの実行のチェーンを作成する必要があります。
単純な相互排他ロック
プログラムには、図1に示されているストリーム（サブジェクト）に加えて、もう1つあると仮定します。
図2
私たちのプログラムには潜在的なデッドロックがあり、テスターがすべてが正常に機能していると言っても、あなたはあなたのプログラムが異なるハードウェア上でこのように振る舞う状況から免れません：
図3
2つの独立したスレッドの実行を妨げるものはありません：スレッド1はミューテックス1をキャプチャし、スケジューラは実行をスレッド2に切り替えて、ミューテックス2をキャプチャし、その後、両方のスレッドはすでにキャプチャされているミューテックス-デッドロックをキャプチャしようとします！
相互ブロックの状況が発生する、実行のチェーンを課す少なくとも1つのバリアントがある場合、互換性のないフロー（エンティティ）のシステムを呼び出します。 したがって、そのような主題のシステムは互換性があり、相互ブロッキングの状況が可能なダイナミクスはありません。
考慮される2つの主題は互換性がありません。 図3に示すオーバーレイオプションがあり、相互ブロッキングの状況が発生します。 そのようなエンティティは、必ずしもプログラムのブロック（凍結）につながるとは限らないことに注意してください。 特定の作業のダイナミクス（同期ツールの呼び出し間の遷移の時間）は、見つかったオーバーレイオプションが実際には表示されないようなものです。 いずれにせよ、そのようなモデルによって記述されたプログラムコードは潜在的に危険であり、別のソフトウェアまたはハードウェアプラットフォームに移植するとき、および単に動作条件を変更するときにブロッキングが発生する可能性があります。
図4
ストリームは相互にペアワイズ互換性がありますが、より大きな組み合わせでは互換性がないことを覚えておくことが重要です。 図5はプログラムのモデルを示しています。このモデルでは、すべてのサブジェクトが互いにペアで互換性がありますが、すべて一緒になって相互ブロッキングの状況になります。
図5
図6は、図5に示したモデルの実行チェーンを組み合わせた別のバリエーションを示しており、デッドロックが発生しています。
図6
ただ言いたい：生きるなんて怖い！
そして、プロのプログラマーが直観的に従う2つの非常に単純なルールがなければ、多くの場合、なぜそうするのか不思議に思わない限り、これは真実です。
最初のルール
キャプチャされたミューテックスは、常に逆キャプチャの順序でリリースします。 「最初のキャプチャ-最後のリリース」のロジックに従います 。
第二のルール
常に同じミューテックスキャプチャの順序に従います。
1つのスレッドでmutex 1を取得し、次にmutex 2を取得した場合、別のスレッドでそれらを異なる順序で取得することはできません。
実際、このルールは一見すると単純ではありません。 図6を詳しく見てみましょう。このルールに違反していますが、それはいくぶん明白ではありません。 最初のストリームを見て、mutex 1の後にmutex 2をキャプチャするように修正します。2番目のストリームを見て、mutex 2の後にmutex 3をキャプチャするように修正します。スレッド3で実行されます。この失敗の結果はデッドロックであり、図に示されています。
これらの規則は単純ですが、プログラムが同期の手段としてミューテックスのみを使用し、これらの規則に従っている場合、相互ブロックは問題ではありません。 もちろん、1つのスレッドで非再帰的なmutexを二重にキャプチャしようとする状況は考慮していませんが、これはデッドロックよりも愚かです。
結論として、私は質問をしたいと思います：このトピックはHabrの聴衆にとって興味深いですか？ もしそうなら、シグナル変数を使用する際に発生するわずかに興味深い状況について話し、おそらく証拠の基盤を少し深く掘り下げたいという願望と機会があります-これはすでにマルチスレッドアプリケーションの洗練されたプログラマー向けです。
この投稿がお役に立てば幸いです。
続きを読む- シグナル変数のデッドロックに対するレシピ 。