競合状態

競合状態または競合ハザードとは、電子機器、ソフトウェア、またはその他のシステムにおいて、システムの実質的な動作が他の制御不能なイベントの順序またはタイミングに依存し、予期しない結果や一貫性のない結果につながる状態を指します。起こり得る動作の 1 つ以上が望ましくない場合、 バグになります。

競合状態という用語は、1954年にはすでに使用されていました。たとえば、David A. Huffmanの博士論文「順次スイッチング回路の合成」などです。^[1]

競合状態は、特に論理回路やマルチスレッドまたは分散ソフトウェア プログラムで発生する可能性があります。相互排他制御を使用すると、分散ソフトウェア システムでの競合状態を防ぐことができます。

競合状態の典型的な例は、論理ゲートが同じソースから異なるパスを通ってきた信号を組み合わせるときに発生します。ゲートへの入力は、ソース信号の変化に応じてわずかに異なるタイミングで変化します。出力は、設計状態に戻る前に、短時間、望ましくない状態に変化することがあります。特定のシステムではこのようなグリッチを許容できますが、この出力が、たとえばメモリを含む他のシステムのクロック信号として機能する場合、システムは設計動作から急速に逸脱する可能性があります (つまり、一時的なグリッチが永続的なグリッチになります)。

たとえば、次のロジックが入力される2 入力AND ゲートを考えてみましょう。一方の入力に論理信号があり、もう一方の入力にその否定(¬ はブール否定) が入力されると、理論上は true 値が出力されません。ただし、 がfalse から true に変化したときに の値の変化が 2 番目の入力に伝わるのに最初の入力よりも時間がかかる場合は、両方の入力が true になる短い期間が発生し、ゲートの出力も true になります。^[2]$${\displaystyle {\text{output}}=A\wedge {\overline {A}}}$$${\displaystyle A}$${\displaystyle \neg A}$${\displaystyle A\wedge {\overline {A}}\neq 1}$${\displaystyle A}$${\displaystyle A}$

競合状態の実際の例は、ロジック回路を使用してカウンターの特定の出力を検出するときに発生する可能性があります。カウンターのすべてのビットが正確に同時に変化しない場合は、誤った一致をトリガーする可能性のある中間パターンが発生します。

重大な競合状態は、内部変数が変更される順序によって、ステート マシンの最終的な状態が決まる場合に発生します。

重大ではない競合状態は、内部変数が変更される順序によって、ステート マシンの最終的な状態が決まらない場合に発生します。

静的競合状態は、信号とその補数が組み合わされたときに発生します。

動的競合状態は、 1つの遷移のみを意図しているのに複数の遷移が発生する場合に発生します。これはゲート間の相互作用が原因です。2 レベル以下のゲーティングを使用することで、これを排除できます。

基本的な競合状態は、入力に合計フィードバック伝播時間よりも短い時間で 2 回の遷移がある場合に発生します。誘導遅延線要素を使用して入力信号の持続時間を効果的に増加させることで、競合状態が解消されることがあります。

カルノー マップなどの設計手法は、問題が発生する前に競合状態を認識して排除することを設計者に推奨します。多くの場合、ロジックの冗長性を追加することで、ある種の競合を排除できます。

これらの問題に加えて、一部のロジック要素は準安定状態になる可能性があり、回路設計者にとってさらなる問題を引き起こします。

コンピュータ プログラムに複数のコード パスがあり、それらが同時に実行されている場合、ソフトウェアで競合状態が発生する可能性があります。複数のコード パスに予想とは異なる時間がかかる場合、予想とは異なる順序で終了することがあり、予期しない動作によってソフトウェア バグが発生する可能性があります。競合は 2 つのプログラム間でも発生し、セキュリティ上の問題を引き起こす可能性があります。

重大な競合状態は、無効な実行やソフトウェア バグの原因となります。重大な競合状態は、プロセスまたはスレッドが何らかの共有状態に依存している場合によく発生します。共有状態に対する操作は、相互に排他的でなければならない重要なセクションで実行されます。このルールに従わないと、共有状態が破損する可能性があります。

データ競合は競合状態の一種です。データ競合はさまざまな形式メモリモデルの重要な部分です。C11およびC ++ 11標準で定義されているメモリモデルでは、データ競合を含むCまたはC++プログラムは未定義の動作をすると規定されています。^{[3] [4]}

競合状態は、最終結果が非決定的であり、干渉するスレッド間の相対的なタイミングに依存するため、再現やデバッグが困難になることがあります。したがって、この種の問題は、デバッグ モードで実行したり、追加のログを追加したり、デバッガーを接続したりすると解消されることがあります。デバッグ中にこのように解消されるバグは、しばしば「ハイゼンバグ」と呼ばれます。したがって、ソフトウェアを慎重に設計して競合状態を回避することをお勧めします。

2 つのスレッドがそれぞれグローバル整数変数の値を 1 ずつ増やすと仮定します。理想的には、次の一連の操作が実行されます。

上記のケースでは、最終値は予想どおり 2 です。ただし、2 つのスレッドがロックや同期 (セマフォ経由) なしで同時に実行されると、操作の結果が間違ってしまう可能性があります。次の操作の代替シーケンスは、このシナリオを示しています。

この場合、最終値は期待される結果の 2 ではなく 1 になります。これは、増分操作が相互に排他的ではないために発生します。相互に排他的な操作とは、メモリ位置などのリソースにアクセスしている間は中断できない操作です。

すべてがデータ競合を競合状態のサブセットとみなしているわけではありません。^[5]データ競合の正確な定義は、使用されている正式な並行性モデルに固有ですが、通常は、あるスレッドのメモリ操作が、別のスレッドのメモリ操作がそのメモリ位置に書き込んでいるのと同時に、そのメモリ位置にアクセスしようとする可能性がある状況を指します。これは、データ競合が競合状態とは異なることを意味します。データ競合のないプログラム、たとえば、すべてのメモリアクセスでアトミック操作のみを使用するプログラムでも、タイミングによる非決定性が発生する可能性があります。

これは危険な場合があります。多くのプラットフォームでは、2 つのスレッドが同時にメモリ ロケーションに書き込むと、各スレッドが書き込もうとした値を表すビットの任意で意味のない組み合わせの値がメモリ ロケーションに保持される可能性があるためです。結果の値がどちらのスレッドも書き込もうとしなかった値である場合、メモリが破損する可能性があります (これは「書き込みの中断」と呼ばれることもあります)。同様に、あるスレッドが別のスレッドが書き込みを行っているときに、あるロケーションから読み取りを行うと、読み取りによって、書き込み前にメモリ ロケーションに保持されていた値を表すビットと、書き込まれる値を表すビットの任意で意味のない組み合わせの値が返される可能性があります。

多くのプラットフォームでは、同時アクセス用に特別なメモリ操作が提供されています。このような場合、通常、これらの特別な操作を使用した同時アクセスは安全ですが、他のメモリ操作を使用した同時アクセスは危険です。このような特別な操作 (同時アクセスが安全) はアトミック操作または同期操作と呼ばれることがありますが、通常の操作 (同時アクセスが安全ではない) はデータ操作と呼ばれます。これが、データ競合という用語が使われる理由です。同期操作のみを伴う競合状態がある多くのプラットフォームでは、このような競合は非決定的かもしれませんが、それ以外は安全です。しかし、データ競合はメモリの破損や未定義の動作につながる可能性があります。

データ競合の正確な定義は、正式な並行性モデルによって異なります。並行動作は直感的でないことが多く、そのため正式な推論が適用されることがあるため、この点は重要です。

C ++標準のドラフトN4296（2014-11-19）では、セクション1.10.23（14ページ）でデータ競合を次のように定義しています^[6]

2つのアクションが同時に発生する可能性がある場合

• 異なるスレッドで実行されるか、
• これらは順序付けられておらず、少なくとも 1 つはシグナル ハンドラによって実行されます。

プログラムの実行に、潜在的に同時に発生する競合するアクションが 2 つ含まれ、そのうちの少なくとも 1 つがアトミックではなく、どちらも他方より先に発生しない場合、データ競合が発生します (ただし、以下で説明するシグナル ハンドラの特殊なケースは除きます [省略])。このようなデータ競合が発生すると、未定義の動作が発生します。

この定義のシグナル ハンドラに関連する部分は C++ に特有であり、データ競合の定義としては一般的ではありません。

論文「弱いメモリシステムでのデータ競合の検出」^[7]では異なる定義が示されています。

「2 つのメモリ操作が同じ場所にアクセスし、そのうちの少なくとも 1 つが書き込み操作である場合、それらの操作は競合します...」順次一貫性のある実行における 2 つのメモリ操作 x と y は、xと y が競合し、実行の hb1 関係によって順序付けられていない場合に限り、競合 〈x,y〉 を形成します。競合 〈x,y〉 は、x または y の少なくとも 1 つがデータ操作である場合に限り、データ競合です。

ここでは、同じ場所にアクセスする 2 つのメモリ操作があり、そのうちの 1 つは書き込みです。

hb1 関係は、論文の他の箇所で定義されており、典型的な「事前発生」関係の例です。直感的に、あるメモリ操作 X が別のメモリ操作 Y が開始する前に完了することが保証されている状況にあることを証明できる場合、「X は Y より前に発生する」と言います。「X は Y より前に発生する」でも「Y は X より前に発生する」でもない場合は、X と Y は「hb1 関係によって順序付けられていない」と言います。したがって、「... および実行の hb1 関係によって順序付けられていない」という節は、「... および X と Y は潜在的に同時である」と直感的に翻訳できます。

この論文では、少なくとも 1 つのメモリ操作が「データ操作」である状況のみを危険と見なしています。また、この論文の他の部分では、「データ操作」とは対照的に、潜在的に同時使用しても安全な「同期操作」のクラスも定義しています。

Java言語仕様[ ^8]では異なる定義が提供されています。

同じ変数への 2 つのアクセス (読み取りまたは書き込み) は、少なくとも 1 つのアクセスが書き込みである場合に競合していると言われます...プログラムに、事前発生関係によって順序付けられていない 2 つの競合するアクセス (§17.4.1) が含まれている場合、データ競合が含まれていると言われます...データ競合は、配列の間違った長さを返すなどの不正な動作を引き起こすことはできません。

C++ アプローチと Java アプローチの決定的な違いは、C++ ではデータ競合が未定義の動作であるのに対し、Java ではデータ競合が「スレッド間アクション」にのみ影響することです。^[8]つまり、C++ では、データ競合を含むプログラムを実行しようとすると (仕様に準拠している限り) クラッシュしたり、安全でない動作や奇妙な動作を示す可能性がありますが、Java では、データ競合を含むプログラムを実行しようとすると、望ましくない並行動作が発生する可能性がありますが、それ以外は (実装が仕様に準拠していると仮定すると) 安全です。

データ競合の重要な側面は、状況によっては、データ競合のないプログラムは逐次的に一貫性のある方法で実行されることが保証され、プログラムの同時動作についての推論が大幅に容易になることです。このような保証を提供する形式メモリモデルは、「SC for DRF」（データ競合フリーのための逐次一貫性）特性を示すと言われています。このアプローチは、最近コンセンサスを得たと言われています（おそらく、すべてのケースで逐次一貫性を保証するアプローチ、またはまったく保証しないアプローチと比較して）。^[9]

例えばJavaでは、この保証は直接指定されている: ^[8]

すべての連続一貫性実行でデータ競合が発生しない場合にのみ、プログラムは正しく同期されます。

プログラムが正しく同期されている場合、プログラムのすべての実行は順次一貫しているように見えます（§17.4.3）。

これはプログラマーにとって非常に強力な保証です。プログラマーは、コードにデータ競合が含まれているかどうかを判断するために、並べ替えについて考える必要はありません。したがって、コードが正しく同期されているかどうかを判断するときに、並べ替えについて考える必要はありません。コードが正しく同期されていると判断されると、プログラマーは並べ替えが自分のコードに影響を与えることを心配する必要がありません。

コードの順序が変更されたときに見られるような直感に反する動作を回避するには、プログラムを正しく同期する必要があります。正しい同期を使用しても、プログラム全体の動作が正しいことが保証されるわけではありません。ただし、同期を使用すると、プログラマーはプログラムの可能な動作について簡単に推測できます。正しく同期されたプログラムの動作は、順序の変更の可能性にあまり依存しません。正しい同期がないと、非常に奇妙で混乱を招く直感に反する動作が発生する可能性があります。

対照的に、C++ 仕様の草案では、DRF プロパティに SC を直接要求するのではなく、それを提供する定理が存在することを単に観察しているだけです。

[注: ミューテックスと memory_order_seq_cst 操作を正しく使用してすべてのデータ競合を防ぎ、他の同期操作を一切使用しないプログラムは、その構成スレッドによって実行される操作が単純にインターリーブされ、オブジェクトの各値計算がそのインターリーブ内のそのオブジェクトに対する最後の副作用から取得されるかのように動作することが示されています。これは通常、「順次一貫性」と呼ばれます。ただし、これはデータ競合のないプログラムにのみ適用され、データ競合のないプログラムは、シングルスレッド プログラムのセマンティクスを変更しないほとんどのプログラム変換を観察できません。実際、ほとんどのシングルスレッド プログラム変換は引き続き許可されています。これは、結果として異なる動作をするプログラムは、未定義の操作を実行する必要があるためです。— 注記終了

C++ のドラフト仕様では、memory_order_seq_cst 以外の memory_order で同期操作を行う有効なプログラムが存在する可能性が認められていることに注意してください。この場合、結果は正しいプログラムであっても、逐次一貫性が保証されない可能性があります。言い換えると、C++ では、正しいプログラムであっても逐次一貫性がない場合があります。このアプローチは、C++ プログラマーに、プログラムの推論の容易さを犠牲にして、より高速なプログラム実行を選択する自由を与えると考えられています。^[9]

さまざまな定理があり、多くの場合、メモリ モデルの形式で提供され、さまざまなコンテキストで DRF 保証の SC を提供します。これらの定理の前提は、通常、メモリ モデル (したがって実装) とプログラマーの両方に制約を課します。つまり、定理の前提を満たさず、連続的に一貫性のある方法で実行することが保証されないプログラムが存在するのが通常です。

DRF1メモリモデル^[10]はDRFにSCを提供し、WO（弱い順序付け）、RCsc（逐次一貫性のある特殊操作によるリリース一貫性）、VAXメモリモデル、およびデータ競合のない0メモリモデルの最適化を可能にします。PLpcメモリモデル^[11]はDRFにSCを提供し、TSO（合計ストア順序）、PSO、PC（プロセッサ一貫性）、およびRCpc（プロセッサ一貫性の特殊操作によるリリース一貫性）モデルの最適化を可能にします。DRFrlx ^[12]は、緩和されたアトミックがある場合のDRF定理のSCのスケッチを提供します。

多くのソフトウェア競合状態は、コンピュータセキュリティへの影響を伴います。競合状態により、共有リソースにアクセスできる攻撃者は、そのリソースを使用する他のアクターに誤動作を引き起こし、サービス拒否^[13]や権限昇格^[ 14]などの影響が生じます。^[15]

特定の種類の競合状態には、述語（認証など）をチェックし、その述語に基づいて動作することが含まれますが、チェック時と使用時の間で状態が変化する可能性があります。セキュリティに敏感なコードにこの種のバグが存在すると、チェック時から使用時まで（TOCTTOU ）バグと呼ばれるセキュリティの脆弱性が生じます。

競合状態は、ハードウェア乱数ジェネレータや物理的に複製不可能な関数を作成するために意図的に使用されることもあります。^{[16] [要出典]} PUFは、ノードへのパスが同一の回路トポロジを設計し、製造上のばらつきを利用してどのパスが最初に完了するかをランダムに決定することで作成できます。製造された各回路の競合状態の結果の特定のセットを測定することで、回路ごとにプロファイルを収集し、後で回路のIDを確認するために秘密にしておくことができます。

2 つ以上のプログラムがファイルシステムを変更またはアクセスしようとして衝突すると、データの破損や権限の昇格が発生する可能性があります。^[14] ファイルロックは、一般的に使用される解決策を提供します。より面倒な解決策は、1 つの固有のプロセス (デーモンなどを実行) がファイルに排他的にアクセスできるようにシステムを編成し、そのファイルのデータにアクセスする必要がある他のすべてのプロセスは、その 1 つのプロセスとのプロセス間通信を介してのみアクセスするようにすることです。これには、プロセス レベルでの同期が必要です。

ファイル システムには、別の形の競合状態が存在します。無関係なプログラムが、ディスク領域、メモリ領域、プロセッサ サイクルなどの利用可能なリソースを突然使い果たすことで、互いに影響を及ぼし合う可能性があります。この競合状態を予測して処理するように注意深く設計されていないソフトウェアは、予測不可能になる可能性があります。このようなリスクは、非常に信頼性が高いと思われるシステムでは長い間見過ごされる可能性があります。しかし、最終的には十分なデータが蓄積されたり、十分な数の他のソフトウェアが追加されたりして、システムの多くの部分が決定的に不安定になる可能性があります。この例として、火星探査機「スピリット」が着陸後間もなくほぼ失われるという事態が起こりました。これは、ファイル エントリが削除されたためにファイル システム ライブラリが利用可能なメモリ領域をすべて消費したために発生しました。 ^[17]解決策は、ソフトウェアがタスクを開始する前に必要なすべてのリソースを要求して予約することです。この要求が失敗した場合は、タスクを延期して、失敗が発生する可能性のある多くのポイントを回避します。または、それらのポイントのそれぞれにエラー処理を装備するか、タスク全体の成功を後で確認してから続行することもできます。より一般的なアプローチは、タスクを開始する前に十分なシステム リソースが利用可能であることを確認することです。ただし、複雑なシステムでは他の実行中のプログラムの動作が予測できない可能性があるため、これでは不十分な場合があります。

ネットワークでは、 IRCのような分散チャット ネットワークを考えてみましょう。IRC では、チャネルを開始したユーザーは自動的にチャネル オペレータ権限を取得します。同じネットワークの異なる端にある異なるサーバー上の 2 人のユーザーが同時に同じ名前のチャネルを開始しようとすると、どちらのサーバーも、そのチャネルを割り当てたという他のサーバーからの信号をまだ受信していないため、各ユーザーのそれぞれのサーバーは各ユーザーにチャネル オペレータ権限を付与します。(この問題は、さまざまな IRC サーバー実装によってほぼ解決されています。)

この競合状態の場合、「共有リソース」の概念はネットワークの状態 (存在するチャネル、およびそれらを開始したユーザー (したがって、どのような権限を持っているか)) をカバーします。各サーバーは、ネットワーク上の他のサーバーに変更を通知して、ネットワークの状態の概念を更新できる限り、自由に変更できます。ただし、ネットワーク全体の遅延により、説明した種類の競合状態が発生する可能性があります。この場合、共有リソースへのアクセスに何らかの制御を課すことによって競合状態を回避するには (たとえば、どの権限を誰が保持するかを制御するサーバーを 1 つ指定する)、分散ネットワークを集中型ネットワークに変えることになります (少なくともネットワーク操作のその部分については)。

競合状態は、コンピュータ プログラムが非ブロッキング ソケットを使用して記述されている場合にも発生する可能性があり、その場合、プログラムのパフォーマンスはネットワーク リンクの速度に依存する可能性があります。

生命に関わるシステムのソフトウェアの欠陥は悲惨な結果を招く可能性がある。競合状態はTherac-25 放射線治療装置の欠陥の一つであり、少なくとも3人の患者が死亡し、さらに数人が負傷した。^[18]

もう一つの例は、GE Energy社が提供し、オハイオ州に拠点を置くFirstEnergy Corp（およびその他の電力施設）が使用しているエネルギー管理システムです。警報サブシステムに競合状態が存在し、3本のたるんだ電力線が同時にトリップしたときに、この状態により監視技術者に警報が発せられず、問題に気づくのが遅れました。このソフトウェアの欠陥が最終的に2003年の北米大停電につながりました。^[19] GE Energy社は後に、これまで発見されていなかったエラーを修正するソフトウェアパッチを開発しました。

ソフトウェアの競合状態を検出するのに役立つソフトウェア ツールは数多く存在します。これらは、静的分析ツールと動的分析ツールの 2 つのグループに大きく分類できます。

スレッドセーフティ分析は、注釈ベースの手続き内静的分析のための静的分析ツールであり、もともとgccのブランチとして実装されていましたが、現在はPThreadsをサポートするClangで再実装されています。^{[20] [非一次ソースが必要]}

動的解析ツールには次のものがあります。

• Intel Inspector は、C/C++ および Fortran アプリケーションの信頼性、セキュリティ、精度を向上させるメモリおよびスレッドのチェックとデバッグを行うツールです。Intel Advisor は、C、C++、C#、Fortran ソフトウェア開発者や設計者向けのサンプリング ベースの SIMD ベクトル化最適化と共有メモリ スレッド化支援ツールです。
• ThreadSanitizerはバイナリ（Valgrindベース）またはソースのLLVMベースの計測を使用し、PThreadsをサポートしています。^{[21] [非プライマリソースが必要]} Helgrindは、POSIX pthreadsスレッドプリミティブを使用するC、C ++、およびFortranプログラムの同期エラーを検出するためのValgrindツールです。 ^{[22] [非プライマリソースが必要]}
• データ競合検出器^[23]は、Goプログラミング言語におけるデータ競合を検出するために設計されています。

データ競合検出ツールの有効性を評価するために設計されたベンチマークがいくつかあります。

• DataRaceBench ^[24]は、 OpenMPで書かれたマルチスレッドアプリケーションを解析するデータ競合検出ツールを体系的かつ定量的に評価するために設計されたベンチマークスイートです。

神経科学は、競争状態が哺乳類の脳でも起こり得ることを実証している。^{[25] [26]}

英国の鉄道信号では、規則 55の実施時に競合状態が発生します。この規則によると、列車が信号によって走行中の線路上で停止した場合、機関車の機関助手は信号所まで歩いて行き、信号手に列車の存在を思い出させます。少なくとも 1 つのケース、 1934 年のウィンウィックでは、機関助手が到着する前に信号手が別の列車を受け入れたために事故が発生しました。現代の信号慣行では、運転手が無線で信号所に瞬時に連絡できるようにすることで競合状態を解消しています。

• 通話衝突
• 同時実行制御
• デッドロック
• ハザード（ロジック）
• 線形化可能性
• レーストラックの問題
• シンボリックリンク競合
• 同期（コンピュータサイエンス）
• 確認から使用までの時間
• テストと設定

• Karam, GM; Buhr, RJA (1990年8 月)。「Ada の飢餓およびクリティカル レース アナライザ」。IEEE Transactions on Software Engineering。16 ( 8): 829–843。doi :10.1109/32.57622。
• Fuhrer, RM; Lin, B.; Nowick , SM (1995 年 3 月)。「非同期ステート マシンの最適なステート割り当てのためのアルゴリズム」。Advanced Research in VLSI、1995 年。議事録、第 16 回カンファレンス。pp. 59–75。doi :10.1109/ ARVLSI.1995.515611。ISBN 978-0-8186-7047-3. S2CID  4435912。PDFとして2021年6月10日にWayback Machineにアーカイブされました
• 論文「イベントベースの仕様における状態割り当て問題を解決するための新しいフレームワーク」、Luciano Lavagno、Cho W. Moon、Robert K. Brayton、Alberto Sangiovanni-Vincentelli著
• Wheeler, David A. (2004 年 10 月 7 日)。「セキュア プログラマー: 競合状態を防ぐ - リソース競合は不利に働く可能性があります」。IBM developerWorks。2009年 2 月 1 日のオリジナル(PDF)からアーカイブ。代替URL
• 「競合状態を回避する」の章は、Wayback Machineで 2014-03-09 にアーカイブされています(Linux および Unix 向けのセキュア プログラミング HOWTO)
• Java における競合状態、セキュリティ、不変性、サンプル ソース コードと C コードとの比較 (Chiral Software 著)
• Karpov, Andrey (2009 年 4 月 6 日)。「Relacy Race Detector (RRD) の作者、Dmitriy Vyukov 氏へのインタビュー」。
• Microsoft サポートの説明
• 競合状態とデータ競合