競合状態

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

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

電子工学[編集]

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

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

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

情報処理[編集]

情報処理における競合状態は「イベントタイミングへの予期せぬ依存が引き起こす異常な振る舞い」である[1]。特に複数のプロセススレッドが通信しながら動作する場合(並行計算)に発生する。

以下は「read-modify-write」(「状態読み込み、変更、状態書き込み」を意味する典型的な処理)で発生する競合状態の例である。

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

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

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

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

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

以下は「check-then-act」(「条件の確認(check)、それに続く(then)条件に応じた動作(act)」を意味する典型的な処理[2])で発生する競合状態(Time of check to time of use[3])の例である。二つのタスクを示す擬似コードである。

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

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

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

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

競合状態の実例[編集]

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

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

ネットワーク[編集]

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

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

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

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

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

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

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

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

種別[編集]

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

脚注[編集]

[脚注の使い方]
  1. ^ Anomalous behavior due to unexpected critical dependence on the relative timing of events. FOLDOC. (2002) race condition.
  2. ^ In this idiom, the code first checks a condition, and then acts based on the result of the condition. Yu Lin, et al.. (2013) CHECK-THEN-ACT Misuse of Java Concurrent Collections. 10.1109/ICST.2013.41
  3. ^ Secure programs must determine if a request should be granted, and if so, act on that request. There must be no way for an untrusted user to change anything used in this determination before the program acts on it. This kind of race condition is sometimes termed a time of check - time of use (TOCTOU) race condition. Secure Programming HOWTO

関連項目[編集]

外部リンク[編集]

参考文献[編集]