Chaos and Order

💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

はじめに — よく混ざる2つの言葉
カフェのたとえで理解する
スレッド vs イベントループ — 2つの実行モデル
競合状態とデータ競合
ロックとミューテックス — 順序を強制する
デッドロックと食事する哲学者
アトミック操作 — ロックなしで安全に
いつasyncが勝ち、いつスレッドが勝つのか
よくある誤解と落とし穴
おわりに
参考資料

はじめに — よく混ざる2つの言葉

「並行性(concurrency)」と「並列性(parallelism)」は、開発者がもっともよく混同する言葉のペアです。どちらも「複数のことが一度に起きている」という印象を与えるからです。しかしこの2つは異なる概念であり、その違いをあいまいにしておくと、性能問題もバグも見当違いの方向で探すことになります。

Go言語の設計者Rob Pikeが残した定義がもっとも明快です。

並行性は多くのことを**さばく(dealing with)ことであり、並列性は多くのことを同時にやる(doing)**ことである。

この一文に核心がすべて入っています。並行性は構造に関することです。複数の作業をどう分割し調整するかの問題です。並列性は実行に関することです。実際に同じ瞬間に複数の計算が進むかどうかの問題です。並行性は並列性なしでも存在でき(コアが1つのコンピュータでも複数の作業を交互にさばけますから)、並列性は並行的な設計を実現する1つの方法にすぎません。

この記事はこの区別から出発し、スレッドとイベントループ、競合状態とロック、デッドロックとアトミック操作まで、並行プログラミングの核心的な地形を整理します。イベントループが実際にどう作業を交互に処理するかを目で見たいならメッセージキュー・プレイグラウンドのasyncioタブを、複数の演算が並列に流れる計算グラフを見たいならニューラルネット・ラボを一緒に開いてみてください。

カフェのたとえで理解する

Rob Pikeの定義を日常の場面に移すとこうなります。

カフェにバリスタが1人います。注文が3つ入りました。このバリスタは1つ目の注文のエスプレッソを淹れているあいだに2つ目の注文のミルクを温め、その合間に3つ目の注文のカップを準備します。1人ですが3つの注文をさばいています。これが並行性です。実際に同じ瞬間に両手で2つのことをするのではなく、待ち時間を活用して作業のあいだを行き来するのです。

さてバリスタを3人雇います。それぞれが1つずつ注文を担当し、本当に同時に作ります。これが並列性です。3杯が同じ瞬間に実際に作られます。

核心となる洞察はこうです。並行性は問題を独立に実行可能な断片へ構造化する方法であり、並列性はその断片を実際に複数の働き手に分けて同時に実行することです。 よく設計された並行的な構造は、働き手が1人なら交互に処理し、働き手が複数なら自然に並列へ拡張します。

スレッド vs イベントループ — 2つの実行モデル

並行性をコードで実装する代表的な方法が2つあります。スレッドベースのモデルとイベントループ(async)モデルです。

スレッドモデルはOSが複数の実行フロー(スレッド)を作り、スケジューラがそれらをコアに割り当てます。コアが複数あればスレッドが本当に並列に実行されます。各スレッドは自分のスタックを持って独立に進み、OSはいつでも1つのスレッドを止めて別のスレッドへ切り替えられます(プリエンプティブなスケジューリング)。

イベントループモデルはただ1つのスレッドがあり、その中で複数の作業(コルーチン、タスク)を交互に処理します。先のカフェのバリスタと同じです。作業がI/Oを待つ瞬間(await)にその作業をいったん脇に置き、別の作業を進めます。切り替え地点をプログラマが明示的に印すという点で、協調的なスケジューリングです。

スレッドモデル (プリエンプティブ)
  スレッドA ████░░░░████░░░░       OSが任意の時点で切り替え
  スレッドB ░░░░████░░░░████       複数コアなら本当に並列

イベントループモデル (協調的)
  単一スレッド  A─await─B─await─A─await─C ...
                作業が自ら譲る地点でのみ切り替え

2つのモデルの根本的な違いは「切り替えがいつ起きるか」です。スレッドはOSがいつでも割り込んで切り替えます。だから本当の並列実行が可能ですが、まさにそのために共有データを扱うとき危険です。イベントループはawaitのような明示的な地点でのみ切り替えるので予測可能ですが、1つの作業が譲らずに計算を抱えると残りすべてが止まります。

競合状態とデータ競合

並行プログラミングが難しい理由の核心に**競合状態(race condition)**があります。複数の実行フローが共有資源にアクセスし、その結果が実行順序(タイミング)によって変わる状況です。

もっとも古典的な例がカウンタの増加です。counter += 1という1行は、実は3段階からなります。

1. counterの値を読む       (例: 10)
2. その値に1を足す          (11)
3. 結果をcounterに書く      (11)

2つのスレッドが同時にこの3段階を実行すると、次のようなことが起こりえます。

スレッドA: 読み(10) ....... 足す(11) 書く(11)
スレッドB: ......... 読み(10) ....... 足す(11) 書く(11)
結果: counter = 11  (2回増やしたのに11!)

2回足したのに結果は11です。1つの増加が消えました。このように複数のスレッドが同期なしに同じメモリにアクセスし、そのうち1つ以上が書き込みをする状況を特に**データ競合(data race)**と呼びます。データ競合は競合状態の一種であり、多くの言語で未定義動作(undefined behavior)として扱われます。

Pythonでこの問題を再現するとこうです。

import threading

counter = 0

def increment():
    global counter
    for _ in range(100_000):
        counter += 1   # アトミックでない — 競合が起こりうる

threads = [threading.Thread(target=increment) for _ in range(4)]
for t in threads:
    t.start()
for t in threads:
    t.join()

print(counter)  # 400000ではなく、それより小さい値が出ることがある

競合状態の恐ろしい点は再現性の低さです。ほとんどの場合たまたま順序が合って正常に動き、負荷が高いときやタイミングが特定の条件のときだけ狂います。だからテストでは現れず、本番環境でだけ爆発する悪名高いバグになります。

ロックとミューテックス — 順序を強制する

競合状態を防ぐ基本ツールがロック(lock)、なかでも相互排他を意味する**ミューテックス(mutex, mutual exclusion)**です。考え方は単純です。共有資源に触れるコード区間(クリティカルセクション)には一度に1つの実行フローだけ入れるようにします。

import threading

counter = 0
lock = threading.Lock()

def increment():
    global counter
    for _ in range(100_000):
        with lock:          # 一度に1スレッドだけこのブロック内へ
            counter += 1

# これで結果は常に400000

with lockブロックに入るにはロックを取得する必要があり、1つのスレッドがロックを握っているあいだ、他のスレッドはそれが解放されるまで待ちます。おかげで読み・足す・書くの3段階が分割されず、アトミックに実行されます。

ロックは強力ですがタダではありません。3つの代償が伴います。

性能: ロックの取得と解放にコストがかかり、複数のスレッドが同じロックを取り合う(競合、contention)と、並んで待つあいだ並列性が消えます。
粒度(granularity)の選択: ロックを広く取る(coarse-grained)と安全ですが並列性が減り、狭く取る(fine-grained)と並列性はよいが複雑でバグが生じやすくなります。
デッドロックの危険: ロックを複数使うと、互いに相手のロックを待って永遠に止まる膠着状態が生じえます。

デッドロックと食事する哲学者

**デッドロック(deadlock, 膠着状態)は、2つ以上の実行フローが互いに相手の握る資源を待ち、誰も進めない状態です。これをもっともよく示す古典問題が、Edsger Dijkstraが提示した食事する哲学者(dining philosophers)**です。

円卓に哲学者が5人座っています。各自の前にはスパゲッティの皿があり、哲学者たちのあいだにはフォークが1本ずつ、計5本置かれています。スパゲッティを食べるには左と右のフォーク2本が両方必要です。

        哲学者0
     フォーク4    フォーク0
  哲学者4            哲学者1
     フォーク3    フォーク1
        哲学者3  フォーク2  哲学者2

  各哲学者は両隣のフォーク2本があって初めて食事できる

さて全員の哲学者が同時に「まず左のフォークを取り、次に右のフォークを取る」という同じ規則に従うとしましょう。全員が同時に左のフォークを取ると、5本のフォークがすべて片手ずつ握られた状態になります。今度は全員が右のフォークを取ろうとしますが、右のフォークは隣の人の左手にあります。誰も2本目のフォークを得られず、誰も1本目を離しません。永遠の膠着です。

デッドロックが成立するには4つの条件(Coffman条件)が同時に満たされねばなりません。

相互排他: 資源を一度に1つしか使えない(フォークは共有不可)。
保持しつつ待機: 資源を握ったまま別の資源を待つ(左のフォークを握って右を待つ)。
横取り不可: 他人が握る資源を強制的に奪えない。
循環待機: 待機の連鎖が円環状につながる。

このうち1つを崩すだけでデッドロックを防げます。代表的な解法が循環待機を崩すことです。たとえばフォークに番号を振り「常に番号の小さいフォークを先に取る」という規則を置くと、最後の哲学者だけ逆順で取ることになり、循環が切れてデッドロックが消えます。

アトミック操作 — ロックなしで安全に

ロックは重いです。単にカウンタを1つ安全に増やすためにロックを取って離すのは過剰です。そこでハードウェアが直接サポートする**アトミック操作(atomic operation)**があります。

アトミック操作はCPUが「分割できない1つの動作」として保証する操作です。先に見た読み・足す・書くの3段階を、途中で他のスレッドが割り込めない単一命令として実行します。代表的なのが**CAS(Compare-And-Swap)**です。

CAS(アドレス, 期待値, 新値):
    もし *アドレス == 期待値 なら
        *アドレス = 新値 に変えて成功を返す
    そうでなければ
        何もせず失敗を返す
    — この全体がアトミックに起こる

CASを使えばロックなしで安全な増加を作れます。「現在の値を読み、それがまだそのままなら+1した値に変える。そのあいだに誰かが変えたら失敗するので再試行する」というやり方です。こうしたアプローチを**ロックフリー(lock-free)**プログラミングと呼びます。

アトミック操作の利点はロックのオーバーヘッドとデッドロックの危険がないことです。しかし万能ではありません。カウンタやフラグのような単純な単一値には優れていますが、複数のデータ構造を一度に一貫して変えねばならない複雑な場合にはアトミック操作だけでは表現しにくく、誤って使うとかえって微妙なバグ(たとえばABA問題)を招きます。だから実務では単純な場合はアトミック操作、複雑な場合はロックと役割を分けます。

いつasyncが勝ち、いつスレッドが勝つのか

さてもっとも実用的な問いです。並行性が必要なときにasync(イベントループ)を使うか、スレッド(あるいはマルチプロセシング)を使うか。答えは作業の性質次第です。

作業は大きく2つに分かれます。

I/Oバウンド: 大半の時間を何かを待つことに使う作業。ネットワーク応答、ディスク読み込み、データベースクエリ。CPUはほとんど遊んでいます。
CPUバウンド: 大半の時間を実際の計算に使う作業。画像処理、暗号化、数値シミュレーション。CPUが休む間もなく回ります。

この区別が選択を決めます。

I/Oバウンドにはasyncが勝ちます。 待つ時間が多いので、1つのスレッドがその待ちの合間に別の作業を処理すればよいのです。スレッドを何千も作るより、イベントループ1つで何千もの接続をさばくほうがメモリもはるかに少なく、切り替えコストも低いです。ウェブサーバー、プロキシ、クローラーのような「たくさん待つ」作業がここにぴったり合います。

import asyncio

async def fetch(name, delay):
    await asyncio.sleep(delay)   # 待っているあいだ別のコルーチンが動く
    return name

async def main():
    # 3つの作業を同時に — 待ちの合計ではなく最大値に近く
    results = await asyncio.gather(
        fetch("a", 2), fetch("b", 1), fetch("c", 3),
    )
    print(results)

asyncio.run(main())

CPUバウンドにはスレッド(より正確には複数のプロセス)が必要です。 計算は譲る隙がないので、イベントループでは1つの作業がCPUを抱えると残りが全部止まります。本当の並列実行が必要で、そのためには複数のコアに作業を分散せねばなりません。ここにPython特有の落とし穴が1つあります。CPythonにはGIL(Global Interpreter Lock)があり、複数のスレッドがあっても一度に1つのスレッドだけがPythonバイトコードを実行します。だからPythonでCPUバウンドの作業を本当に並列で回すには、スレッドではなくマルチプロセシング(複数のプロセス)を使わねばなりません。

まとめるとこうです。

状況	よい選択	理由
たくさん待つI/O (ネットワーク、ディスク)	async / イベントループ	待ちの合間を再利用、軽い
重い計算 (CPU集約)	マルチプロセシング / 複数コア	本当の並列実行が必要
I/Oだがasyncライブラリがない	スレッドプール	ブロッキング呼び出しをスレッドで隔離
PythonでのCPU並列	マルチプロセシング	GILのためスレッドでは並列にならない

よくある誤解と落とし穴

並行プログラミングでよくつまずく点を挙げます。

「asyncは常に速い」という誤解: asyncはI/Oバウンドでのみ勝ちます。CPUバウンドの作業をasyncで包むとイベントループが詰まり、かえって遅くなります。
イベントループ内のブロッキング呼び出し: 単一スレッドのイベントループで同期ブロッキング関数(通常のtime.sleep、ブロッキングDBドライバなど)を呼ぶとループ全体が止まります。async対応ライブラリを使うか、別スレッドへ渡さねばなりません。
「スレッドをたくさん作れば速くなる」という誤解: スレッドはそれぞれスタックメモリを使い、切り替えコストがあります。コア数をはるかに超えるスレッドは、かえって切り替えオーバーヘッドで遅くなります。
ロックを広く取って並列性を殺す: 安全だからとクリティカルセクションを大きく取ると事実上の逐次実行になり、マルチコアの利点が消えます。
競合状態を「たまに出るバグ」と放置: 再現が難しいからと見過ごすと、本番環境でデータ破損として返ってきます。共有状態には必ず同期を設計せねばなりません。

おわりに

並行性と並列性は似て見えますが層が違います。並行性は多くのことをさばけるよう構造化することであり、並列性はその仕事を実際に複数のコアで同時に実行することです。よく設計された並行プログラムは、コアが1つなら交互に処理し、コアが複数なら自然に並列へ拡張します。

そしてこの構造を安全にするのが同期の技術です。競合状態をロックやアトミック操作で防ぎ、デッドロックを順序規則で避け、作業の性質(I/OかCPUか)に合わせてasyncとマルチプロセシングを選びます。この地図を頭に置けば、「なぜ遅いのか」と「なぜたまに間違うのか」という2種類の問題を、はるかに正確な場所で探せます。

イベントループが作業のあいだをどう行き来するかをメッセージキュー・プレイグラウンドのasyncioタブで実際に確かめ、複数の演算が並列に流れる計算グラフをニューラルネット・ラボで見てみてください。

参考資料

Rob Pike, "Concurrency Is Not Parallelism": https://go.dev/blog/waza-talk
Dining philosophers problem (Wikipedia): https://en.wikipedia.org/wiki/Dining_philosophers_problem
Deadlock and Coffman conditions (Wikipedia): https://en.wikipedia.org/wiki/Deadlock
Compare-and-swap (Wikipedia): https://en.wikipedia.org/wiki/Compare-and-swap
Python asyncio 公式ドキュメント: https://docs.python.org/3/library/asyncio.html
Python GIL の説明: https://docs.python.org/3/glossary.html#term-global-interpreter-lock