『並行プログラミング入門』で並行処理のトピックスを網羅する

本書は並行プログラミングに関する様々なトピックを紹介する本です (『並行プログラミング入門 ――Rust, C, アセンブリによる実装からのアプローチ』).
副題にもある通り, アルゴリズムを C やアセンブリで低レベルに実装して, Rust で高レベルに使うというような流れです. 実践的な何かを作るというより, 仕組みを理解することに重点が置かれた本で, タイトルの通り並行プログラミングに入門したい方におすすめです.

キーワードの一部

レースコンディション
デッドロック
async/await
マルチタスク
アクターモデル
λ計算, π計算

並行して実行されてはいけない処理

並行プログラミングを考える上で注意を払わなければならないのは, 複数のプロセスで同時に実行されてはいけない箇所の扱いです.
複数プロセスで実行されてはいけないということは, 実行中を表すフラグを管理しておけばよいのではないかと思うわけですが, 以下のコードで問題はないでしょうか.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
bool is_in_progress = false;

void f() {
  // Wait while other process is in progress.
  while (is_in_progress) {}

  is_in_progress = true;

  // Must not be executed concurrently.
  do_something();

  is_in_progress = false;
}

一見すると問題ないように思えます. しかし, 並列処理においては do_something() が複数同時に実行される可能性があります.
なぜかというと, あるプロセスでis_in_progressが false になり while を抜けて true を代入するまでの間に, 他のプロセスでもis_in_progressが false となっているからです.

1
2
3
4
5
Process A       ------------------------------>
                   ↑(false)      ↓(true)
is_in_progress  ------------------------------>
                        ↓(false)     ↑(true)
Process B       ------------------------------>

Process A が false を読み出してから true を書き込むまでの間に, Process B も false を読み出し true を書き込んでしまう例を表しています.
ではどうすればこの状況を防げるのでしょうか?結局読み込みと書き込みの間になにか別の処理が挟まる可能性があることが問題の原因ですから, コードの書き方を工夫するだけでは不可能です.

この場合, コンパイラに組み込まれている __sync_bool_compare_and_swap という関数を使います.

1
bool __sync_bool_compare_and_swap(bool* p, bool comparand, bool new_value);

*pの値がcomparandと同じならnew_valueを代入, comparandと異なるなら何もしません. 返り値は*pの元の値です. つまり以下のようなイメージです.

1
2
3
4
5
bool sync_bool_compare_and_swap(bool *p, bool comparand, bool new_value) {
  bool tmp = *p;
  if (*p == comparand) { *p = new_value; }
  return tmp;
}

ただし, __sync_bool_compare_and_swapは, これら一連の処理の間に他の命令が何も挟まらないことが保証されます. この関数を使って, 最初の例は以下のように実装できます.

1
2
3
4
5
6
7
8
bool is_in_progress = false;

void f() {
  while (__sync_bool_compare_and_swap(&is_in_progress, false, true)) {}

  do_something();
  __sync_bool_compare_and_swap(&is_in_progress, true, false);
}

__sync_bool_compare_and_swapのように, 間に他の処理が挟まらずに実行される複数の処理を「アトミック処理」といいます.
平行プログラミングでは処理が実行される順序が不定ですが, 他のプロセスとタイミングを合わせて処理を行うことを「同期処理」と言います.

アトミック処理の必要性を示す他の例も一つ挙げます. カウンタをインクリメントする関数 h ですが, この関数 h を並行に動かしたときに先ほどと同様の問題が発生します. つまり, 10 回 h を実行しても cnt の値が 10 にならない可能性があるということです.

1
2
3
4
5
int cnt = 0;

void h() {
  ++cnt;
}

これはもちろん

cnt の読み込み
cnt に 1 を足す
cnt を書き込み

という一連の処理がアトミックではないからです. 見かけ上++cntは 1 行ですがアセンブラのレベルでは複数の命令に分解されます. この場合は __sync_add_and_fetch という組み込み関数を使います.

これまで見たように, 複数のプロセスで並行してリソースにアクセスしたときに引き起こされる意図しない状態のことを「レースコンディション (競合状態)」といいます. そして, レースコンディションを引き起こす原因となる, 並行して実行されてはいけない処理のことを「クリティカルセクション」といいます.

ミューテックス

__sync_bool_compare_and_swap を少し抽象化して使い勝手を良くします.

1
2
3
4
5
6
7
void acquire_lock(volatile bool* p) {
  while (__sync_bool_compare_and_swap(p, false, true)) {}
}

void release_lock(volatile bool* p) {
  __sync_bool_compare_and_swap(p, true, false);
}

引数に付いているvolatileというキーワードは見慣れないかもしれませんが, コンパイラの最適化を抑制するものです.
メモリへのアクセスは遅いので, メモリから読み込んだ値をレジスタに保存して関数の中で使いまわすことがあります. 通常は問題ありませんが, 並列処理では関数実行中に別のプロセスから変数の値が書き換えられる可能性があるので, その場合はレジスタにキャッシュした値を見るのではなくメモリにある値を見に行く必要があります.

これらの関数は以下のように使います.

1
2
3
4
5
6
7
bool lock = 0;

void f() {
  acquire_lock(&lock);
  // Critical section.
  release_lock(&lock);
}

こうすると, クリティカルセクションを実行するためにはロックを獲得し, 実行が終わったらロックを解放するというように抽象化できます. この例のように, クリティカルセクションが同時に複数のプロセスで実行されることを防ぐ同期処理を「ミューテックス (排他実行)」といいます. ついでに, acquire_lockのようにロックの空きをポーリングしてロックを獲得できるまで待つ方法を「スピンロック」といいます.
ロックは獲得したら忘れずに解放する必要があります. これはバグの原因になるので, 言語によっては (C#など) 解放漏れを防ぐ構文が用意されている場合もあります.

1
2
3
4
lock (x)
{
  // Critical section.
}

ちなみに上記のrelease_lockは単に*pに false を代入するだけですが, なぜ *p = false; としないのか疑問を持つかもしれません. これは CPU の最適化を抑制するためです.
CPU は時間あたりに実行できる機械語の命令数を上げるため, 命令の順番を変えて実行することがあります (アウトオブオーダ実行). 例えばメモリからの値の読み取りは遅いので, 読み取り完了を待たずに次の命令を実行するというようなことです.
このアウトオブオーダ実行を抑制するための処理を「メモリバリア」といい, __sync_bool_compare_and_swapのような関数は必要なメモリバリアを設定してくれます.

その他の同期処理に関するキーワード

レースコンディション, クリティカルセクション, アトミック処理, ミューテックスなどを見てきましたが, 他にも同期処理の例が挙げられているので, キーワードだけ紹介しておきます.

セマフォ: 同時に複数のプロセスがロックを獲得可能な, ミューテックスの複数版
条件変数: 「ある条件が満たされるまでプロセスを待機, 満たされたら実行」を実現したいときに使う変数
バリア同期: 全てのプロセスが条件が満たすまで待機する同期処理の方法
Read-Write ロック: 以下の条件を満たすロック. 書き込みが少ない場合に使うとミューテックスより効率が良い
- 読み込みと書き込みを行うプロセスが同時にロックを獲得しない
- 書き込みを行うスレッドが同時に 2 つ以上ロックを獲得しない
- 読み込みを行うスレッドは同時に複数ロックを獲得可能

デッドロックとライブロック

並行プログラミング特有のバグとして有名なデッドロックを紹介します.

前進しかできない車があって, 狭い道路を通ろうとしている状態を考えます.
道路を通っている最中に向かいから別の車がやってくると, どうしようもなくなります. 自分は前の車がどいてくれないと通れない, 一方向かいの車も自分がどいてくれないことには道を開けることもできません.

1
2
3
----------------
 □->        <-□
----------------

より一般的には, 処理を完了するために複数のリソースのロックが必要な場合, 別のプロセスがそれぞれ別のリソースをロックしてしまい, どのプロセスも処理を進めることができなくなった状態のことをデッドロックと言います. 自分の処理を進めるためには相手がロックしているリソースが必要という状態です.
本書では「食事する哲学者問題」が紹介されています (なぜ人数分の食器を用意しないのでしょうか. デッドロックの危険もありますし, デッドロックを回避しても他人と食器を共有することになりますし…).

さて, 狭い道をすれ違えるようにします. 路肩にちょっとしたスペースを作ります.

1
2
3
4
5
  /--\
-/    \-----------
 □->        <-□
-----------\    /-
            \--/ 

対向車が来ても一方が路肩によって相手を先に通せば, 両者ともに道を通過することができます.
しかし, お互いが路肩に寄って道を譲ろうとしまうとどうなるでしょう. タイミングが最悪だった場合, 相手が譲ってくれたから自分が先に行こうと思うと, 相手も同じタイミングで路肩を出てしまい, ではこちらが譲ろうとすると相手も路肩に寄ってしまう.
このように, どうしようもないわけではないが, 結局必要なリソースを獲得できずに処理を完了できない状態のことを「ライブロック」といいます. 状態は遷移しているけど先に進めない場合です.

さらに, 左からたくさんの車が来るとして, ずっと右の車が路肩に寄っていていつまでも道を通過できないような状態のことを「飢餓」といいます. 特定のプロセスのみがリソースを獲得できない場合です.
プロセスによってロック獲得のしやすさに差がない状態を「公平」であるといいます. スピンロックだと CPU の性能によってロックの獲得に偏りが出るので不公平ですし, ロック獲得のための競争が激しくなると無駄に CPU リソースを消費してしまうので好ましくありません. リレー走のように次のプロセスに順番を回して公平性を担保する方法や, 競争を減らすチケットロックといったアルゴリズムが紹介されています.

結語

まえがきに「並行プログラミングに関するトピックを網羅的に解説する」とあるように, アセンブリから計算モデルまで幅広く様々な事柄が説明されて, さらに各アルゴリズムの実装例もちゃんとコードが載っていました. この記事で紹介できたのはごく一部です.

個人的には, 並行プログラミングの基本的な知識がない状態だったので非常に勉強になりました. 「よく分からないけど並列は怖い」から確実に一歩進めたと思います.
一方で, 意味は分かるけど何のために使うんだろうと思った手法やアルゴリズムもしばしばあったので, 次は実例に触れながら知識を深めたいと思います.

並行して実行されてはいけない処理#

ミューテックス#

その他の同期処理に関するキーワード#

デッドロックとライブロック#

結語#

並行して実行されてはいけない処理

ミューテックス

その他の同期処理に関するキーワード

デッドロックとライブロック

結語