コンピューターサイエンス：アルゴリズム / OS / ネットワーク / DB
Mutex と Semaphore
区間そのものに鍵をかける
前回の引き落としは、読んでから書き戻すまでを 2 人に同時に通したせいで壊れました。ならば、その区間に入る前に鍵を取り、出るときに返す約束にします。鍵は 1 つしか無いので、2 人目は 1 人目が返すまでその場で待たされます。この鍵が ミューテックス です。
Python
import threading
lock = threading.Lock()
def withdraw(account, amount):
with lock:
if account.balance >= amount:
account.balance -= amount
account.history.append(amount)with lock: に入るところで鍵を取り、ブロックを抜けるところで返します。残高の確認から履歴の追加までが 1 人分ずつ順に実行されるので、前回の表のような割り込まれ方はしなくなります。
acquire() と release() を自分で書くこともできますが、途中で例外が飛ぶと release() を通らず、鍵を持ったまま誰も帰ってこない状態になります。言語が用意している構文を使うのが鉄則です。Python の with、Java の synchronized、Go の defer mu.Unlock()、Rust のガードは、どれも「必ず返す」ことを保証するための形です。
鍵の持ち主が決まっている
ミューテックスの特徴は、取ったスレッドだけが返せることです。これは制限ではなく安全装置で、「関係ないスレッドが勝手に鍵を返してしまい、区間に 2 人入る」という事故を仕組みとして防いでいます。
鍵が 1 つだと、全員が 1 列に並ぶ
上の例には無駄があります。鍵はプログラム全体で 1 つなので、まったく別の口座への引き落としまで順番待ちになります。口座が 1 万あっても、同時に動けるのは 1 人だけです。
そこで鍵を口座ごとに持たせます。別々の口座なら並行に進み、同じ口座に来たときだけ待ちが発生します。この「鍵をどの単位で持つか」を粒度と呼び、並行時の性能をほぼ決めてしまいます。粗くすれば安全だが遅く、細かくすれば速いが、扱う鍵の数が増えるぶん事故の余地も増えます。
1 人ではなく、N 人まで通したいとき
守るのではなく、数を絞りたい場面もあります。外部 API へ 500 件のリクエストを投げたいが、同時接続は 5 本までに抑えたい、といった要求です。
このときは、内部にカウンタを持つ セマフォ を使います。入るときにカウンタを 1 減らし、0 になったら次の人は待ち、出るときに 1 戻します。
Python
sem = threading.Semaphore(5)
def fetch(url):
with sem:
return http_get(url)ミューテックスは「同時に 1 人」、セマフォは「同時に N 人」です。上限 1 のセマフォはほぼミューテックスとして働きますが、セマフォには持ち主の概念が無く、入ったのとは別のスレッドが返せます。壊れないように守りたいのか、数を絞りたいのかで選び分けます。
