Loading article…
レースコンディション（またはレースハザード）とは、電子機器、ソフトウェア、その他のシステムにおいて、システムの実際の動作が制御不能なイベントの順序やタイミングに依存し、予期しない結果や矛盾した結果が生じる状態のことです。起こりうる動作のうち、1つ以上が望ましくない場合、それはバグとなります。
レースコンディションという用語は、例えばデイビッド・A・ハフマンの博士論文「シーケンシャルスイッチング回路の合成」[ 1 ]などで1954年には既に使われていた。
競合状態は、特に論理回路や並行処理・分散処理ソフトウェアプログラムで発生する可能性があります。相互排他を用いることで、競合状態を防ぐことができます。
競合状態の典型的な例として、論理ゲートが同じソースから異なる経路を伝わってきた信号を組み合わせる場合が挙げられます。ゲートへの入力は、ソース信号の変化に応じてわずかに異なるタイミングで変化する可能性があります。出力は、設計状態に戻る前に、短時間、望ましくない状態に変化することがあります。一部のシステムはこのような不具合を許容できますが、この出力がメモリを含む他のシステムのクロック信号として機能する場合、システムは設計動作から急速に逸脱する可能性があります（事実上、一時的な不具合が永続的な不具合になります）。
例えば、以下の論理回路で入力された2入力ANDゲートを考えてみましょう。論理信号1つの入力とそのブール否定 別の入力では、理論上、真の値を出力することは決してできません。ただし、値の変化が2番目の入力に伝播するのに最初の入力よりも時間がかかる場合が偽から真に変化すると、両方の入力が真となる短い期間が続き、ゲートの出力も真になります。[ 2 ]
競合状態の具体的な例として、論理回路を用いてカウンタの特定の出力を検出する場合が挙げられます。カウンタのすべてのビットが完全に同時に変化しない場合、中間的なパターンが生じ、誤った一致を引き起こす可能性があります。
クリティカルレースコンディションとは、内部変数を変更する順序によって、ステートマシンが最終的に到達する状態が決まる場合に発生する現象です。
非クリティカルな競合状態とは、内部変数が変更される順序が、ステートマシンが最終的に到達する状態を決定しない場合に発生する状態です。
静的競合状態は、信号とその補数が結合されるときに発生します。
動的競合状態とは、意図した遷移が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 つのメモリ操作が同じ場所にアクセスし、かつ少なくとも一方が書き込み操作である場合、2 つのメモリ操作は競合します 。逐次的に一貫性のある実行において、2 つのメモリ操作 x と y は、 x と y が競合し、かつ実行の hb1 関係によって順序付けられていない場合に限り、競合 〈x,y 〉を形成します。競合 〈x,y〉 は、x または y の少なくとも一方がデータ操作である場合に限り、データ競合です。
ここでは、同じ場所にアクセスする2つのメモリ操作があり、そのうちの1つは書き込み操作です。
hb1関係は本論文の別の箇所で定義されており、典型的なhappens-before関係の一例です。直感的に言えば、あるメモリ操作Xが別のメモリ操作Yの開始前に必ず完了することが保証されている状況であれば、「XはYより先に実行される」と言えます。もし「XはYより先に実行される」ことも「YはXより先に実行される」こともない場合、XとYは「hb1関係によって順序付けられていない」と言えます。したがって、「…そしてそれらは実行のhb1関係によって順序付けられていない」という節は、 「…そしてXとYは潜在的に同時実行される可能性がある」 と直感的に解釈できます。
この論文では、メモリ操作の少なくとも1つがデータ操作である状況のみを危険とみなしています。また、この論文の他の部分では、データ操作とは対照的に、同時使用しても安全な同期操作のクラスも定義しています。
Java言語仕様[ 8 ]では、異なる定義が示されています。
同じ変数への 2 つのアクセス (読み取りまたは書き込み) は、少なくとも 1 つのアクセスが書き込みである場合、競合していると言われます 。プログラムに、happens-before 関係で順序付けられていない 2 つの競合するアクセス (§17.4.1) が含まれている場合、データ レースが含まれていると言われます 。データ レースは、配列の間違った長さを返すなどの誤った動作を引き起こすことはありません。
C++ のアプローチと Java のアプローチの決定的な違いは、C++ ではデータ競合が未定義動作であるのに対し、Java ではデータ競合は単にスレッド間の動作に影響を与えるという点です。[ 8 ]これは、C++ では、データ競合を含むプログラムを実行しようとすると、（仕様に準拠しているにもかかわらず）クラッシュしたり、安全でない、または奇妙な動作を示す可能性があるのに対し、Java では、データ競合を含むプログラムを実行しようとすると、望ましくない並行動作が発生する可能性があるものの、（実装が仕様に準拠していると仮定すると）それ以外は安全であることを意味します。
データ競合の重要な側面は、ある状況下では、データ競合のないプログラムは逐次的に一貫性のある方法で実行されることが保証され、プログラムの並行動作についての推論が大幅に容易になることである。このような保証を提供する形式メモリモデルは、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は、ノードへのパスが同一の回路トポロジーを設計し、製造上のばらつきを利用してどのパスが最初に完了するかをランダムに決定することで作成できます。[ 17 ]製造された各回路の特定の競合状態の結果セットを測定することで、各回路のプロファイルを収集し、後で回路の身元を確認するために秘密にすることができます。
2 つ以上のプログラムがファイルシステムの変更やアクセスを試みる際に衝突し、データの破損や権限の昇格につながる可能性があります。[ 14 ]ファイルロックは、一般的に使用される解決策です。より面倒な解決策としては、1 つの固有のプロセス (デーモンなどを実行) がファイルへの排他的アクセス権を持ち、そのファイル内のデータにアクセスする必要がある他のすべてのプロセスは、その 1 つのプロセスとのプロセス間通信を介してのみアクセスするようにシステムを構成します。これには、プロセスレベルでの同期が必要です。
ファイルシステムには、無関係なプログラムがディスクスペース、メモリスペース、プロセッササイクルなどの利用可能なリソースを突然消費することで互いに影響し合う、別の形の競合状態が存在します。この競合状態を予測して処理するように慎重に設計されていないソフトウェアは、予測不能になる可能性があります。このようなリスクは、非常に信頼性が高いように見えるシステムでは長い間見過ごされる可能性があります。しかし、最終的には十分なデータが蓄積されるか、十分な数の他のソフトウェアが追加されて、システムの多くの部分が重大な不安定化を起こす可能性があります。この例として、火星探査車「スピリット」が着陸後まもなくほぼ失われそうになったケースがあります。これは、削除されたファイルエントリによってファイルシステムライブラリが利用可能なメモリスペースをすべて消費したことが原因でした。[ 18 ]解決策は、ソフトウェアがタスクを開始する前に必要なすべてのリソースを要求して予約することです。この要求が失敗した場合は、タスクが延期され、障害が発生する可能性のある多くのポイントを回避します。あるいは、これらのポイントのそれぞれにエラー処理を実装するか、タスク全体の成功を後で検証してから続行することもできます。より一般的なアプローチは、タスクを開始する前に十分なシステムリソースが利用可能であることを単純に検証することです。しかし、複雑なシステムでは他の実行中のプログラムの動作が予測不可能な場合があるため、これだけでは十分ではないかもしれない。
ネットワークにおいて、 IRCのような分散型チャットネットワークを考えてみましょう。IRCでは、チャンネルを開始したユーザーは自動的にチャンネルオペレーター権限を取得します。同じネットワークの両端にある異なるサーバー上の2人のユーザーが、同じ名前のチャンネルを同時に開始しようとした場合、どちらのサーバーも相手サーバーからそのチャンネルを割り当てたというシグナルを受け取っていないため、それぞれのサーバーは各ユーザーにチャンネルオペレーター権限を付与します。（この問題は、様々なIRCサーバーの実装によってほぼ解決されています。）
この競合状態の場合、共有リソースの概念はネットワークの状態（どのチャネルが存在し、どのユーザーがチャネルを開始し、したがってどのような権限を持っているか）を網羅しており、各サーバーは、ネットワーク上の他のサーバーに変更を通知してネットワークの状態に関する認識を更新できる限り、自由に変更できます。しかし、ネットワーク全体の遅延により、前述のような競合状態が発生する可能性があります。この場合、共有リソースへのアクセスを制御する何らかの方法（例えば、どのサーバーがどの権限を持っているかを制御するサーバーを1つ指定するなど）を課すことで競合状態を回避すると、分散ネットワークが（少なくともネットワーク運用のその部分に関しては）集中型ネットワークに変わってしまうことになります。
コンピュータプログラムがノンブロッキングソケットを使用して記述されている場合にも、競合状態が発生する可能性があり、その場合、プログラムのパフォーマンスはネットワークリンクの速度に依存する可能性があります。
生命に関わるシステムのソフトウェアの欠陥は、壊滅的な結果を招く可能性がある。Therac -25放射線治療装置の欠陥の一つに競合状態があり、少なくとも3人の患者の死亡と、さらに数人の負傷につながった。[ 19 ]
もう1つの例は、GE Energyが提供し、オハイオ州に拠点を置くFirstEnergy Corp （その他電力施設を含む）が使用しているエネルギー管理システムです。アラームサブシステムに競合状態が存在し、3本の垂れ下がった送電線が同時にトリップすると、監視技術者にアラートが発信されず、問題への認識が遅れました。このソフトウェアの欠陥が、最終的に2003年の北米大停電につながりました。[ 20 ] GE Energyは後に、以前は発見されていなかったエラーを修正するソフトウェアパッチを開発しました。
ソフトウェアにおける競合状態を検出するのに役立つソフトウェアツールは数多く存在する。それらは大きく2つのグループに分類できる。静的解析ツールと動的解析ツールである。
スレッド安全解析は、注釈ベースのプロシージャ内静的解析のための静的解析ツールであり、元々はgccのブランチとして実装され、現在はClangで再実装され、PThreadsをサポートしています。[ 21 ]
動的解析ツールには以下が含まれます。
データ競合検出ツールの有効性を評価するために設計されたベンチマークがいくつか存在する。
競合状態は、人間とコンピュータのインタラクション設計やソフトウェアのユーザビリティにおいてよく懸念される問題です。直感的に設計されたヒューマンマシンインターフェースでは、ユーザーが期待どおりのフィードバックを受け取る必要がありますが、システムによって生成されるアクションは、スマートフォンで別のタスクを実行中に意図せず着信に応答したり拒否したりするなど、ユーザーの現在のアクションやワークフローを予期せぬ形で中断する可能性があります。
英国の鉄道信号システムでは、規則55の実施において競合状態が発生することがあった。この規則によれば、列車が走行線路上で信号機によって停止した場合、機関車の火夫は信号所まで歩いて行き、信号係に列車の存在を知らせることになっていた。少なくとも1934年のウィンウィックでは、火夫が到着する前に信号係が別の列車の進入を許可したために事故が発生した。現代の信号システムでは、運転士が無線で信号所と瞬時に連絡を取ることができるため、競合状態は解消されている。
競合状態はデジタルシステムに限られません。神経科学は、競合状態が哺乳類の脳でも発生することを示しています。実証されている競合の1つは、計画された運動を実行する神経経路と、その運動をキャンセルできる別の経路との間の競合です。[ 26 ] [ 27 ]
