排他制御 — 知星図

概要

排他制御（mutual exclusion）は、複数の処理が同じデータや資源に同時に触れるのを防ぎ、「この区間は一度に1人だけ」という約束を守らせる仕組みです。口座の残高を書き換える、在庫数を減らす、共有のカウンタを更新する — こうした「みんなで1つのものをいじる」場面で、順番を守らせて結果が壊れないようにするのが役目です。

なぜ順番を守らせる必要があるのかは、並行と並列の世界を思い浮かべると分かります。複数のスレッドが同じ変数を「読んで・計算して・書き戻す」操作を、示し合わせずに同時に行うと、互いの更新を上書きし合って結果が壊れます。排他制御は、この危うい区間の入口に「一度に1人しか通れない扉」を置く道具立てだと考えると、全体像がつかめます。

代表的な道具がミューテックス（mutex。mutual exclusion の略）とセマフォ（semaphore。もとは鉄道の腕木信号機）です。どちらも「同時に触れる人数を制限する」点は同じですが、制限のかけ方が違います。ほかに、読む人と書く人を分けて扱う読み書きロックや、条件が整うまで眠って待つ条件変数といった仲間もいます。

なぜ生まれたか

排他制御が必要になる背景には、「読んで・計算して・書き戻す」という何気ない操作が、実は複数の段階に分かれているという事実があります。たとえば「カウンタに1を足す」という1行のコードも、機械語のレベルでは「メモリから現在値を読む」「1を足す」「メモリに書き戻す」の3段階です。スレッドが1本なら3段階は一息に終わりますが、2本が同時に走ると、片方が読んでから書き戻すまでの隙間に、もう片方が同じ古い値を読んでしまうことがあります。

その結果、両者がそれぞれ「10を読んで11を書き戻す」ため、本来12になるべき値が11で止まり、片方の加算がまるごと消えます。これがロストアップデート（更新の喪失）で、実行のタイミング次第で結果が変わるこの現象を競合状態（race condition）と呼びます。厄介なのは、たいていはうまく動き、負荷が高いときにだけまれに壊れる点です。再現もデバッグも難しい種類のバグです。

この問題は、1台のCPUで複数のプログラムを切り替えて動かす時分割の OS が登場した1960年代に、すでに正面から扱われていました。1965年、エドガー・ダイクストラ（Edsger Dijkstra）は「複数の処理のうち、ある区間には同時に1つしか入れない」ことをどう保証するかという相互排除の問題を定式化し、あわせてセマフォという道具を提案しました。「読んで・計算して・書き戻す」の一続きを、他者に割り込ませない区間として扱う — この考え方が、ミューテックスやセマフォとして今日の OS とプログラミング言語に受け継がれています。マルチコアの時代になり、複数のスレッドが本当に同時に動くようになったことで、その重要性はさらに増しました。

詳細

クリティカルセクションとロストアップデート

排他制御が守るべき「一度に1人しか入ってはいけない区間」を、クリティカルセクション（危険区間）と呼びます。共有データを読み書きする、まさにその数行です。まず、守らない場合に何が起きるかを時系列で見てみましょう。

Aが読んでから書き戻すまでの隙間にBが割り込み、同じ古い値10を読んでしまいました。問題は個々の操作ではなく、「読んでから書くまでの窓」が2つ重なったことにあります。下の部品で、2本のスレッドの「読む・+1・書く」を時間軸の上でドラッグして重ね、更新が消える瞬間を自分で起こしてみてください。そのあとロックをミューテックスに切り替えると、何が変わるかを確かめられます。

⚡ 体験: 読む・+1・書くを重ねる — 更新が消える窓とロック

ロック

スレッドBの「読む・+1・書く」をつかんで左へドラッグし、Aの区間に重ねてみてください。いまは重なっていないので、count は正しく 12 になります。

ミューテックス — 持ち主は常に1人

この問題への最も基本的な答えがミューテックスです。ミューテックスは「鍵のかかる部屋」のようなもので、クリティカルセクションに入る前にロック（施錠）し、出るときにアンロック（解錠）します。ロックを取れるのは一度に1人だけで、すでに誰かが持っていれば、後から来たスレッドは解放されるまで扉の前で待たされます。ロックした本人だけがアンロックできる — この「持ち主が1人」という性質がミューテックスの核心です。

部品で見たとおり、ロックは処理を速くする道具ではありません。重なりの窓を持つ2つの区間を、前後に並べ替える（直列化する）だけです。そのぶん待ちが生まれ、全体の終わりは遅くなります。だからこそ、ロックで守る区間はできるだけ短くするのが鉄則です。

待ち方 — 回って待つか、眠って待つか

ロックが取れなかったスレッドの待ち方には2通りあります。スピンロックは、ロックが空くまでループで何度も確かめ続けます（回って待つ）。CPUを使い続ける代わりに、空いた瞬間にすぐ入れます。もう1つのブロッキング（眠って待つ）は、スレッドをスケジューラの待ち行列に移して眠らせ、解放されたらカーネルに起こしてもらいます。CPUを無駄にしませんが、眠る・起きるの切り替えに数マイクロ秒かかります。

どちらが得かは、待つ時間の長さで決まります。ロックを持つ時間がごく短く、別のコアで持ち主が動いているなら、眠るより回って待つほうが早い。長く待つなら眠るべきです。そこで Linux のミューテックスの土台である futex は、ぶつからなければシステムコールを呼ばずにユーザ空間の原子操作だけでロックを取り、ぶつかったときだけカーネルに眠らせてもらう、という作りになっています。多くの実装は「少しだけ回って、だめなら眠る」という折衷をとっています。なお、コアが1つしかない環境でのスピンは、持ち主が動けないまま時間を使い切るだけなので逆効果です。

セマフォ — N人まで通す

セマフォはミューテックスを一般化した仕組みで、内部にカウンタを持ち「同時にN人まで入ってよい」を表現します。入るたびにカウンタを1減らし（ダイクストラの記法では P 操作）、出るたびに1増やし（V 操作）、0になったら後続を待たせます。

ミューテックスは扉1つに鍵1本。セマフォは入場券がN枚あり、券がなくなると後続は並んで待つ

カウンタの上限を1にしたセマフォ（二値セマフォ）はミューテックスとほぼ同じ働きになりますが、設計思想が違います。ミューテックスは「所有権」を持ち、ロックした本人しか解除できません。セマフォは持ち主を問わないので、あるスレッドが増やしたカウンタを別のスレッドが減らす、といった使い方ができます。このためセマフォは、データベースへの同時接続を10本に絞る（コネクションプールの内部など）といった資源数の制限や、「準備ができたら相手を起こす」という合図にも使われます。1人に絞りたいならミューテックス、人数や合図を扱いたいならセマフォ、と覚えると迷いません。

読み書きロックと条件変数

読むだけなら何人が同時に読んでも壊れません。そこで読み書きロック（readers-writer lock）は、「読む人は何人でも同時に入れる。書く人が入るときだけ全員を締め出す」という2種類の鍵を用意します。読むことが圧倒的に多い設定値やキャッシュの表に向いています。ただし、読む人が途切れないと書く人がいつまでも入れない（飢餓）ことがあるため、書く人を優先する実装もあります。

もう1つの仲間が条件変数です。「キューに仕事が入るまで待つ」のように、ロックの中で条件が整うのを待ちたいとき、ロックを握ったまま眠るとほかの誰もキューに仕事を入れられません。条件変数の wait は「ロックを手放して眠り、起こされたらロックを取り直す」を不可分に行います。起こされても条件が満たされているとは限らない（別のスレッドに先を越された、理由なく起きた）ので、次のように条件を while で確かめ直すのが定石です。

lock(m)
while queue が空:
    wait(cond, m)      # m を手放して眠り、起きたら m を取り直す
job = queue.pop()
unlock(m)

原子操作とCAS — ロックを使わない道

ロックを取って待たせる方式のほかに、「読んで・計算して・書き戻す」そのものを分割できない1手にしてしまう方法もあります。CPUが提供する原子操作（アトミック操作）で、途中で割り込まれないことがハードウェアで保証されます。代表がCAS（Compare And Swap）で、「値がいまもXならYに書き換えよ、違えば失敗を返せ」を1手で行います。失敗したら読み直してやり直す — この「ロックを取らずに、ぶつかったらやり直す」設計をロックフリーと呼びます。カウンタを1足すだけなら、多くの言語の atomic 型でロックなしに正しく数えられます。

ロックフリーは待ちが生じない代わりに、ぶつかりが多いとやり直しが増え、複数の値をまとめて更新するような処理を正しく組むのは非常に難しくなります。ぶつかったら読み直してやり直すという発想は、データベースの楽観ロックと同じものです。

ロックの粒度というトレードオフ

排他制御の設計で常に問われるのが、ロックの粒度です。粗いロック（データ全体を1つのロックで守る）は単純で安全ですが、本来は無関係な操作まで順番待ちさせるので並列性が失われ、遅くなります。細かいロック（データの一部分ごとに別々のロック）は無関係な操作を同時に走らせられて速い反面、複数のロックを扱うことになり、取り忘れやデッドロック — 互いに相手のロックを待ち続けて全員が止まる状態 — の危険が跳ね上がります。「安全だが遅い」と「速いが危険」の間のどこに線を引くかが、排他制御の腕の見せどころです。

優先度逆転

ロックはスケジューラの優先度とも絡み合います。低い優先度のスレッドがロックを持っている間に、高い優先度のスレッドがそのロックを待ち始めたとします。そこへ中くらいの優先度のスレッドが割り込むと、ロックを持つ低優先度のスレッドがCPUをもらえず、結果として高優先度のスレッドが中優先度のスレッドに追い越され続けます。これが優先度逆転です。1997年、火星探査機マーズ・パスファインダーが着陸後にリセットを繰り返した原因として知られ、ロックを持つスレッドの優先度を、待っている最も高い優先度まで一時的に引き上げる優先度継承を有効にすることで解決されました。

実務での顔ぶれ

排他制御は低レベルの道具に見えて、実務のあちこちに顔を出します。Webのサーバがリクエストごとのスレッドで動くなら、プロセス内で共有するキャッシュや接続数のカウンタにはロックか原子操作が要ります。データベースでは、同じ行を同時に更新させないための行ロックがトランザクションの一貫性を支えています。1台のマシンを越えて複数のサーバで「一度に1人」を保証したいときは、分散ロックという分散版の排他制御が必要になります。

一方で、「そもそも共有しなければ排他制御は要らない」という発想も力を持っています。Go はメモリを共有してロックで守る代わりに、チャネルでデータを受け渡すことを推奨します。Rust は所有権という言語の仕組みで、同じデータを複数の書き手が同時に持つことをコンパイル時に禁じます。共有するデータを最初から書き換えられなくするイミュータビリティも同じ問題への別解です — 書き換えなければ、更新がぶつかることもありません。ロックを賢く使うのと同じくらい、ロックが要らない構造にすることも並行プログラミングの大事な引き出しです。

試問

共有の変数 count（はじめは10）に、2本のスレッドがそれぞれ「読む → +1 → 書く」を1回ずつ行います。各スレッドの3つのブロックの組は、時間軸の上で左右にドラッグして動かせます。上のボタンで、ロックを「なし」と「ミューテックス」から選べます。

✦ 命題挑戦中

2本のスレッドを同時に走らせたまま（Bが Aの途中で動き出すまま）、2回の +1 を1つも失わず count を 12 にせよ

スレッドBが、Aの「読む〜書く」の途中で動き出すように重ねる
そのうえで、最後の count を正しく 12 にする（いま 12）

⚡ 体験: 読む・+1・書くを重ねる — 更新が消える窓とロック

ロック