競合状態

出典: フリー百科事典『ウィキペディア（Wikipedia）』

競合状態（レースコンディション; 英:Race Condition、またはレースハザード; 英:Race Hazard とも）とは、システムや処理過程の問題であり、処理過程の出力結果がイベントなどの順序やタイミングと予期しない（かつ危険な）依存関係にある場合をいう。本来の意味は、2つの電気信号が競合していずれかが出力に影響を与える状態である。

競合状態は設計の不十分な電子工学システム、特に論理回路で発生するが、コンピュータソフトウェアでもよく発生する。

[編集] 電子工学

競合状態の典型例は論理回路システムで入力が変化するときに発生するものである。ある出力が入力の状態に依存する場合、それは定常状態の信号に関して定義されるだけかもしれない。入力の状態が変化するとき、電子システムの物理特性によって出力が変化するまである程度の遅延が生じる。その間、出力は定義された状態以外の不安定な状態となる可能性がある。このような一時的な障害を許すシステムもあるが、例えばその出力信号が他のメモリなどを含むシステムのクロックとして使用される場合、システムは設計されたものとは異なった振る舞いをするかもしれない。

例えば、2入力ANDゲートで論理信号 X とその否定 NOT X を入力にしている場合を考えてみる。理論上、その出力（X AND NOT X）はONになることは無い。しかし、信号 X がそのまま入力される側と NOT ゲートを通して入力される側で遅延時間に差があった場合、短い時間ではあるが、一時的にANDゲートの出力がONになることがある。

適切な設計技法により設計者は競合状態を認識して事前にそれを排除することができる（カルノー図）。他にも不安定状態(Metastable state)が発生することもある。

[編集] 情報処理

競合状態はソフトウェアでも発生する。特に複数のプロセスやスレッドが通信しながら動作する場合に発生する。

以下に単純な例を示す。

2つのスレッド T1 と T2 がそれぞれグローバルな整数を 1 づつインクリメントしていくとする。理想的には以下のような順序で処理したい。

整数 i = 0;
T1 が i の値を読み、レジスタに格納する : 0
T1 が i の値をインクリメントする : (i の現在値) + 1 = 1
T2 が i の値を読み、レジスタに格納する : 1
T2 が i の値をインクリメントする : (i の現在値) + 1 = 2

この例では、i の最終的な値として 2 を期待している。しかし、二つのスレッドは並行に動作し、ロックや同期などの機構を使用しないため、処理結果は間違ったものとなる可能性がある。以下にそのような場合のシナリオを示す。

整数 i = 0;
T1 が i の値を読み、レジスタに格納する : 0
T2 が i の値を読み、レジスタに格納する : 0
T1 が i の値をインクリメントする : (i の現在値) + 1 = 1
T2 が i の値をインクリメントする : (i の現在値) + 1 = 1

i の最終値は期待されている 2 ではなく 1 となる。

別の例として以下の擬似コードでは、二つのタスクを示している。

global integer A = 0;

// A の値をインクリメントして "RX" を表示する
// 端末からの割り込みが発生するたびに起動されるものとする
task Received()
{
    A = A + 1;
    print "RX";
}

// A が偶数のときだけそれを表示する
// 1秒間隔で起動されるものとする
task Timeout()
{
    if (A is divisible by 2)
    {
        print A;
    }
}

出力結果は以下のようになるだろう:

0
0
0
RX
RX
2
RX
RX
4
4

ここで、以下のような順序でイベントが発生する場合を考える:

タイムアウトによってタスク Timeout が起動される。
タスク Timeout が A を調べ、偶数だったので、次の "print A" を実行しようとする。
端末から割り込みが発生し、タスク Received に切り換えられる。
タスク Received が最後まで動作し、A をインクリメントして "RX" を表示する。
制御がタスク Timeout に戻される。
そのタスクは A を表示するが、そのときに A の現在値を使用するため、5 が表示されてしまう。

ミューテックスは、コンカレントプログラミングにおけるこのような問題に対処するために使われる。

[編集] 競合状態の実例

[編集] ファイルシステム

ファイルシステムにおけるファイルロックは一般的解決法を提供する。もっと面倒だが根本的な解決策としては、あるファイルについてひとつのプロセスが排他的なアクセス権を持ち（デーモンのような動作をする）、他のプロセスがそのファイルにアクセスしたいときはプロセス間通信でそのプロセスに依頼するという方式が考えられる（もちろん、その際にプロセスレベルの同期が必要である）。

[編集] ネットワーク

ネットワークでは、IRCのような分散チャットネットワークがあり、ユーザーは新たなチャンネルを開始させるとそのオペレータ特権を得る。異なるサーバを使用中の2人のユーザーが同じ名前のチャンネルを同時に作成しようとする場合、それぞれのサーバは対応するユーザーそれぞれにオペレータ特権を与えてしまう。これは別のサーバからの信号が届く前に特権を与えてしまうことから発生した。なお、現在では多くのIRCサーバの実装でこの問題が解決されている。

この場合の競合状態では、リソース共有のコンセプトでネットワークの状態を隠して、各サーバが自由に状態を変更した後でネットワーク上のサーバにその変化を通知している。しかし、ネットワークによる遅延（レイテンシ）があるためにこのような競合状態が発生するのである。この競合状態を解決するには、何らかの中心となるシステムを用意してチャンネルの生成と特権の付与を集中管理する必要がある。ユーザーがそのような解決策を受け入れられない場合、競合状態を検出して後からそれを訂正するなどの処理が必要となる。

[編集] 人命に関わるシステム

競合状態の特に問題となる例として、放射線療法機器（Therac-25）の事故がある。他の例として、オハイオ州の FirstEnergy 社の電力管理システムの事故がある。このシステムは警報装置に競合状態を発生する問題があった。3本のたるんだ送電線が同時に外されたとき、競合状態が発生して監視要員に警報が届かなかった。このソフトウェア上の問題によって2003年北アメリカ大停電が発生した。

[編集] コンピュータセキュリティ

述語(例えば認証のための真理値を返す演算子か関数）のチェックと使用にかかわる競合状態というものがある。チェック時点と使用時点で状態を変更できるなら、競合状態が発生する。このような競合状態を発生させるバグがコンピュータセキュリティに関わるコードに存在すると、セキュリティホールになる可能性がある。例えば、ファイルのアクセス権をチェックした後で実際のファイルオープンをする場合（あくまでもオペレーティングシステム内のこと）、チェックとオープンの間にファイルをすりかえる（例えばシンボリックリンクにする）と通常アクセスできないファイルにアクセスできる（これは、オペレーティングシステムにバグがある場合の話であって、一般に可能という話ではない）。

[編集] 非同期有限状態機械

常に1ビットだけ入力が変化すると仮定している非同期有限状態機械は、同時に複数の入力ビットが変化すると障害が発生する。これに対する解決策としては、マシンを設計する際に各状態が検知する入力ビットの変化を1ビットに限定することである。

[編集] 種別

静的競合状態: ある信号とその否定信号が入力として与えられるときに発生する可能性がある。
動的競合状態: 一回の遷移が期待されているときに多重遷移が発生する。これはゲート間の相互作用で発生する。2段階より多いゲートを使わないことで防ぐことができる。
基本競合状態: 全体のフィードバック伝播時間より短い間隔で2回入力が変化すると発生する。入力信号に何らかの遅延要素を取り入れることで解決する場合がある。