競合状態
電子工学
編集情報処理
編集i
を1ずつインクリメントしていくとする。理想的には以下のような順序で処理したい。
(一)Integer i = 0;
(二)T1 がiの値を読み、レジスタに格納する : 0
(三)T1 がiの値をインクリメントする : (iの現在値) + 1 = 1
(四)T2 がiの値を読み、レジスタに格納する : 1
(五)T2 がiの値をインクリメントする : (iの現在値) + 1 = 2
この例では、iの最終的な値として2を期待している。しかし、二つのスレッドは並行に動作し、ロックや同期などの機構を使用しないため、処理結果は間違ったものとなる可能性がある。以下にそのような場合のシナリオを示す。
(一)Integer i = 0;
(二)T1 がiの値を読み、レジスタに格納する : 0
(三)T2 がiの値を読み、レジスタに格納する : 0
(四)T1 がiの値をインクリメントする : (iの現在値) + 1 = 1
(五)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ここで、以下のような順序でイベントが発生する場合を考える: (一)タイムアウトによってタスク Timeout が起動される。 (二)タスク Timeout が
A
を調べ、偶数だったので、次の "print A" を実行しようとする。
(三)端末から割り込みが発生し、タスク Received に切り換えられる。
(四)タスク Received が最後まで動作し、Aをインクリメントして "RX" を表示する。
(五)制御がタスク Timeout に戻される。
(六)そのタスクはAを表示するが、そのときにAの現在値を使用するため、5が表示されてしまう。
ミューテックスは、並行プログラミングにおけるこのような問題に対処するために使われる。
競合状態と似た概念として、データ競合︵英: data race︶がある。データ競合は単一のデータに対する同時読み書きが非一貫性を引き起こす現象のことを指す。データ競合はそのデータへのアクセスをプロセッサが持つアトミック命令のような粒度の小さい排他制御で保護することによって回避できるが、競合状態も回避できるとは限らない。アトミック操作でなければならない金融トランザクションのように、動作のタイミングによらず処理結果の一貫性を保つ必要がある場合は、より粒度の大きい排他制御が可能なミューテックスなどの同期・調停機構を使う必要がある。
競合状態の実例
編集ファイルシステム
編集ファイルシステムにおけるファイルロックは一般的解決法を提供する。もっと面倒だが根本的な解決策としては、あるファイルについてひとつのプロセスが排他的なアクセス権を持ち(デーモンのような動作をする)、他のプロセスがそのファイルにアクセスしたいときはプロセス間通信でそのプロセスに依頼するという方式が考えられる(もちろん、その際にプロセスレベルの同期が必要である)。
ネットワーク
編集ネットワークでは、IRCのような分散チャットネットワークがあり、ユーザーは新たなチャンネルを開始させるとそのオペレータ特権を得る。異なるサーバを使用中の2人のユーザーが同じ名前のチャンネルを同時に作成しようとする場合、それぞれのサーバは対応するユーザーそれぞれにオペレータ特権を与えてしまう。これは別のサーバからの信号が届く前に特権を与えてしまうことから発生した。なお、現在では多くのIRCサーバの実装でこの問題が解決されている。
この場合の競合状態では、リソース共有のコンセプトでネットワークの状態を隠して、各サーバが自由に状態を変更した後でネットワーク上のサーバにその変化を通知している。しかし、ネットワークによる遅延(レイテンシ)があるためにこのような競合状態が発生するのである。この競合状態を解決するには、何らかの中心となるシステムを用意してチャンネルの生成と特権の付与を集中管理する必要がある。ユーザーがそのような解決策を受け入れられない場合、競合状態を検出して後からそれを訂正するなどの処理が必要となる。
人命に関わるシステム
編集コンピュータセキュリティ
編集非同期有限状態機械
編集常に1ビットだけ入力が変化すると仮定している非同期有限状態機械は、同時に複数の入力ビットが変化すると障害が発生する。これに対する解決策としては、マシンを設計する際に各状態が検知する入力ビットの変化を1ビットに限定することである。
種別
編集脚注
編集- ^ 競合状態(レースコンディション)とは - 意味をわかりやすく - IT用語辞典 e-Words
- ^ Anomalous behavior due to unexpected critical dependence on the relative timing of events. FOLDOC. (2002) race condition.
- ^ 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
- ^ 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
- ^ 「史上最悪のソフトウェアバグ」ワースト10を紹介(上) | WIRED.jp
- ^ History's Worst Software Bugs | WIRED
- ^ ソフトウェアのバグによって6件の重大な放射線事故が引き起こされた「セラック25事故」とは? - GIGAZINE
関連項目
編集外部リンク
編集- IPA セキュア・プログラミング講座
- レースコンディションの一般的対策 C/C++言語編
- synchronized とレースコンディション セキュアJavaプログラミング
- Unix のレースコンディション セキュアUnix/Linuxプログラミング
参考文献
編集- bmurphy1976, et al.. (2008). What is a race condition? Stack Overflow
- David A. Wheeler. (2015). Avoid Race Conditions. Secure Programming HOWTO, 7:11.
- Article "Secure programmer: Prevent race conditions—Resource contention can be used against you" by David A. Wheeler