データ競合(data race)と競合状態(race condition)を混同しない

T/O

マルチスレッド・プログラミングの文脈では、「データ競合(data race)」と「競合状態(race condition)」は直交した異なる概念を表す¹。両者ともに回避すべき事象だが、問題を取り扱うレイヤは明確に区別されるべき。

• データ競合(data race)は、マルチスレッド・プログラム実装上の問題である。
• 競合状態(race condition)は、並行処理システム設計上の問題である。

ここではJava, C#, C++あたりのマルチスレッド対応手続き型ベースのプログラミング言語を取り上げるが、言語パラダイムによらずマルチスレッド処理（共有メモリ型の並行処理機構）ならば広範に適用可能である。また言語仕様として両者を明確に区別するRust言語も取り上げる。

データ競合(data race)

「データ競合(data race)」が何であるかは、それぞれのプログラミング言語仕様にて定義される。競合状態(race condition)と比べると、低レイヤでプリミティブな事象を指す。

何が起きるか： データ競合(data race)が生じると、そのマルチスレッド・プログラムの実行結果は、全く予想がつかない ものとなる。例えばC++では未定義動作を引き起こす。JavaやC#などでも、何が起きるかについての保証はほどんど無い。

どう防ぐか：後述定義中「(2)同時に」への対策²、つまり、変数に対する同時アクセスをスレッド間で排他制御する。このとき利用する仕組みが、ミューテックス(mutex) や モニタ(monitor) などの同期機構³、もしくは アトミック(atomic)変数 と呼ばれるデータ型である。なお、Rust言語では型システムレベルで対策が行われており、データ競合(data race)を引き起こすソースコードはコンパイル・エラーとなる⁴。

定義： データ競合(data race)とは、(1)複数スレッド間で共有する変数に対して、(2)同時に、(3)読み／書きアクセスが行われる事象を指す。

1. 狭義にはプログラミング言語が提供する基本型（intなど）を対象とする。広義の解釈として、その言語の標準ライブラリ型のクラス（辞書型やリスト型など）や、ユーザが定義するクラスも含めてもよい。これは、どんなに複雑なクラスの内部実装であっても、最終的には基本型に対する操作へと分解できるため。
2. 同時(simultaneous)を直接説明するのは困難なため、各種プログラミング言語では「同時でない」とはどんな状況かを定義する。異なるスレッド上で実行される2つの操作A, Bがあり、必ずどちらか一方が他方より先に実行されるならば、その2操作は同時ではないと定めている。この定義では、A→B／B→Aどちらかといった具体的な順番は対象とせず、どちらか片方が先に実行される保証があればよい。
3. より厳密には「少なくとも1つが書出(write)操作である複数のアクセス」となる。つまり 全スレッドが読込(read)操作 なら、データ競合(data race)は生じない。また ++iやi *= 2;のような値の更新処理は、読込-更新-書出(RMW; Read-Modify-Write)操作と呼ばれ、文字通り書出(write)操作の一種として扱う。

競合状態(race condition)

「競合状態(race condition)」はマルチスレッド・プログラムの設計、すなわち並行処理システムの設計に起因する。データ競合(data race)に比べると、高レイヤで複合的に生じる事象を指す⁵。

何が起きるか： 競合状態(race condition)が生じると、マルチスレッド・プログラムの実行結果は、各スレッド上での操作実行順序に依存する。言い換えると、プログラム実行のたびに 同一入力を与えても異なる結果を出力する という非決定的(indeterminate)な動作につながる。

どう防ぐか： そもそも非決定的動作が意図的、つまりシステム設計通り(by design)ならば対処の必要はない⁶。意図しない競合状態(race condition)は、リソースに対する複数操作が不可分(atomic)でないことが原因となるケースが多い。これは一連の操作をクリティカルセクション(critical section)とみなし、同期機構を用いた排他制御を行うことで対処できる⁷。なお、Rust言語でも言語仕様としてのサポートは無く、競合状態(race condition)の回避は他言語同様にシステム設計者の責任である。

定義： 各スレッド上で行われる操作の実行順序やタイミングに依存して、システムの出力結果が（意図せず）変化してしまう事象を指す。

コード例示

「データ競合(data race)」と「競合状態(race condition)」の違いを、C++ソースコードによる預金口座間の送金処理で例示する。

• システムの不変条件として 0 ≦ 口座残高 を満たす。借金なし。
• 送金処理では、送金元口座に十分な残高があるときに限り、送金先口座へと指定額を送金成功する。
• 2つの預金口座間で、2つの送金要求が同時に行われる状況を考える。

データ競合の例

C++

int my_account = 0;      // 私の預金口座残高
int your_account = 100;  // あなたの預金口座残高

// 送金処理: データ競合(data race)あり！
bool racy_transfer(int& src, int& dst, int m)
{
  if (m <= src) {  // 未定義動作の可能性あり！
    src -= m;      // 未定義動作の可能性あり！
    dst += m;      // 未定義動作の可能性あり！
    return true;
  } else {
    return false;
  }
}

// 下記の2操作を別スレッドから同時に呼び出し
racy_transfer(your_account, my_account, 50);  // [A]
racy_transfer(your_account, my_account, 80);  // [B]

上記コードの実行結果は、操作後の各口座残高について確かなことを言えないだけでなく、システム全域にわたって何が起こるか全く保証できなくなる。

JavaやC#でも状況は全く同じ（厳密にはC++よりは保証の度合いが強いが、データ競合に対する本質的な解決までは至らないため、ここではC++と同程度に"危険"とみなす）。

競合状態の例

C++

#include <atomic>
std::atomic<int> my_account = 0;      // 私の預金口座残高
std::atomic<int> your_account = 100;  // あなたの預金口座残高

// 送金処理: データ競合(data race)しないが競合状態(race condition)！
bool unsafe_transfer(std::atomic<int>& src, std::atomic<int>& dst, int m)
{
  if (m <= src) {
    // ★この時点でも(m <= src)は真？
    src -= m;
    dst += m;
    return true;
  } else {
    return false;
  }
}

// 下記の2操作を別スレッドから同時に呼び出し
unsafe_transfer(your_account, my_account, 50);  // [A]
unsafe_transfer(your_account, my_account, 80);  // [B]

上記コードの実行では、★箇所付近での競合状態(race condition)が生じる。つまりif文でチェックした事前条件m <= srcは、実際の口座操作src -= mのタイミングでは既にfalseとなっている可能性がある。この場合、下記3通りの実行結果がありえる。

• [A]完了で your_account == my_account == 50 となり、続く[B]は失敗する。
• [B]完了で your_account == 20 && my_account == 80 となり、続く[A]は失敗する。
• 2つのスレッド上で[A]/[B]が同時に★箇所を通過すると、最終結果は your_account == -30 && my_account == 130 となる。このとき[A]/[B]いずれも正常終了するが、システム不変条件に違反している！

C++のstd::atomic<int>型に相当するのは、Javaではjava.util.concurrent.atomic.AtomicIntegerクラス（とvolatile変数操作）、C#ではvolatile変数とSystem.Threading.Interlockedクラスメソッド操作が対応する。

正しい実装

C++

#include <mutex>
int my_account = 0;      // 私の預金口座残高
int your_account = 100;  // あなたの預金口座残高
std::mutex txn_guard;

// 送金処理: 安全なトランザクション処理
bool safe_transfer(int& src, int& dst, int m)
{
  // クリティカルセクション開始
  std::lock_guard<std::mutex> lk(txn_guard);
  if (m <= src) {
    src -= m;
    dst += m;
    return true;
  } else {
    return false;
  }
}  // クリティカルセクション終了

// 下記の2操作を別スレッドから同時に呼び出し
safe_transfer(your_account, my_account, 50);  // [A]
safe_transfer(your_account, my_account, 80);  // [B]

このコードを実行すると、下記2通りの実行結果がありえる。非決定的動作となっているが、システム不変条件に違反する結果は決して生じない。

• [A]完了で your_account == my_account == 50 となり、続く[B]は失敗する。
• [B]完了で your_account == 20 && my_account == 80 となり、続く[A]は失敗する。

C++のstd::mutex型＋std::lock_guard操作に相当するのは、Javaではモニタ(monitor)＋synchronized構文またはjava.lang.concurrentパッケージで提供される一部クラス、C#ではSystem.Threading.Monitorクラスメソッド操作＋lock構文または名前空間System.Threadingで提供される一部クラスが対応する。

おまけ

• https://www.reddit.com/r/ProgrammerHumor/comments/34byk0/race_conditions/
• https://www.reddit.com/r/ProgrammerHumor/comments/2skae8/perfect_demonstration_of_a_race_condition/

---

1. 言及対象や文脈によっては「データ競合(data race)」と「競合状態(race condition)」を明確に区別する必要がないケースもあるだろう。 ↩

2. 排他制御の導入以外にも、(1)そもそも複数スレッド間で共有しない、(3)全て読み込みアクセスとする といった対策もある。プログラム設計上の選択肢があるならば、(1)共有しない → (3)全て読込(read) → (2)排他制御／アトミック の順で方式検討すべき。 ↩

3. Java言語のsynchronizedキーワードやC#言語のlockキーワードは、排他制御の記述をサポートする言語仕様といえる。使用するプログラミング言語によらず、本質的には同じ排他制御が必要となる。 ↩

4. Rust言語でも、プログラマがunsafeコードを明示的に記述すれば、型システムに抜け穴を開けて強引にコンパイルを通す手段は用意されている。この場合、データ競合(data race)を回避するのはプログラマ自身の責任となる。 ↩

5. データ競合(data race)を、「スレッド（プロセッサ）と変数（メモリ）で起きる競合状態(race condition)」とする解釈も不可能ではない。ただしデータ競合(data race)の場合は、プロセッサとメモリという実行時(runtime)の世界以外にも、コンパイル時のコード生成最適化とも強い関係があるため、両者は異なる概念として扱われるべき。 ↩

6. 一般に「競合状態(race condition)」は否定的なニュアンスを含むため、設計に基づく意図的な非決定的動作は競合状態(race condition)に含めない。非決定的動作なシステムの例としては、システム全域での合意形成をとりづらい（または事実上取れない）分散処理システムや、処理スループットを最重要視する並列処理システムが挙げられる。 ↩

7. 排他制御された一連の操作を、クリティカルセクション(critical section)の他にクリティカルリージョン(critical region)と呼ぶこともある。排他制御以外の対処策として、一連の操作をメモリという共有資源に対するトランザクション(transaction)と取り扱う、トランザクショナル・メモリ(transactional memory)方式も存在する。トランザクショナル・メモリ方式は楽観的(optimistic)トランザクション、排他制御方式は悲観的(pessimistic)トランザクションとも解釈できる。 ↩