実験・実装 · 基礎から応用へ

ロックの取得順序とデッドロックを再現する

二つのロックを逆順に取る循環待ちを作り、取得のタイムアウトで実験を終了させます。順序を統一した場合との違いを確認します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 永久に固まるプログラムを作らない
  2. 両者が一つ目を持った状態で待ち合わせる
  3. 順序を統一すると、循環の一辺を作れない
  4. タイムアウトは、更新の後始末も必要にする
  5. 順序統一が保証しない性質も残す
  6. この記事をロゲイアに質問する理解を確かめる

永久に固まるプログラムを作らない

二つの仕事がそれぞれ別のロックを持ち、相手が持つロックを待つと、待機が循環します。実験ではバリアで「最初のロックを互いに取った」段階をそろえ、二つ目の取得へ進ませます。ただし無期限には待たせず、短い取得タイムアウトで循環を断って終了します。したがって観測するのは、無期限取得ならデッドロックになる所有関係と、その回避としてのタイムアウトです。本番の処理や別プロセスのロックには触れません。Python標準ライブラリのthreadingを使い、自分の二つのスレッドと二つのロックだけで試します。

両者が一つ目を持った状態で待ち合わせる

Aはleft、Bはrightを先に取り、バリア通過後に逆のロックを取得します。最初のロックを持ったまま二つ目を待つため、両者が直ちに成功することはできません。少なくとも一方がタイムアウトして最初のロックを返せば、他方はその後成功する場合もあります。二人とも必ずタイムアウトするとは決めつけず、一方以上が取得に失敗したことを確認します。成功して二つ目を取れた場合も確実に返し、最初のロックはfinallyで解放します。途中で例外が起きた場合は記録して、正常な検証結果と混ぜません。

python
import threading
left, right = threading.Lock(), threading.Lock()
barrier = threading.Barrier(2, timeout=3)
results, errors = [], []
def reversed_order(first, second):
    try:
        with first:
            barrier.wait()
            acquired = second.acquire(timeout=0.2)
            results.append(acquired)
            if acquired:
                second.release()
    except BaseException as error:
        errors.append(repr(error))
workers = [threading.Thread(target=reversed_order, args=pair, daemon=True)
           for pair in ((left, right), (right, left))]
for t in workers: t.start()
for t in workers: t.join(3)
assert not errors and all(not t.is_alive() for t in workers)
assert len(results) == 2 and not all(results)
print('opposite order acquisition results', results)
completed = []
def ordered():
    with left:
        with right:
            completed.append(True)
workers = [threading.Thread(target=ordered, daemon=True) for _ in range(2)]
for t in workers: t.start()
for t in workers: t.join(3)
assert len(completed) == 2 and all(not t.is_alive() for t in workers)
print('consistent order completed', len(completed))

順序を統一すると、循環の一辺を作れない

後半では両者ともleft、rightの順に取得します。一方がleftを持つ間、他方はleftの前で待つため、rightを先に持ったままleftを待つ相手は現れません。この二つのロックだけの規則では、逆順の循環を作れなくなります。実装する際は、別の関数から呼ぶ経路も同じ順序へ従う必要があります。ロックを持ったまま外部へコールバックし、その中で逆順に取得するような経路があれば、局所的な確認では足りません。取得する資源全体に対して順序を定め、その順序をどの境界で守るかを説明します。

タイムアウトは、更新の後始末も必要にする

タイムアウトで待機を終えられても、途中まで行った変更が自動で元に戻るわけではありません。最初のロックを持つ間に共有状態を変更していたなら、失敗時に不変条件をどう保つかを決めます。解除して再試行する方式では、同じ相手と繰り返し競合して進まないライブロックも考慮します。単に例外を捕まえて同じ処理を即座に回すだけで解決したとはいえません。今回の例は共有状態を変更する前の取得段階に限定するため、資源を返すことだけで後始末が完了します。業務上の変更を追加する前に、その境界を見直してください。

順序統一が保証しない性質も残す

同じ順序で取得すれば、ここで示す逆順のデッドロックは防げますが、公平な実行順や短い待ち時間まで保証するわけではありません。長い処理をロック内へ入れれば、他方は長く待ちます。外部I/Oが止まる場合、別の資源との循環、キャンセル処理なども、この二つのロックだけでは評価できません。実験結果には、前半の取得成否と後半の完了件数を記録します。前半で両方のタイムアウトを求めたり、後半が一回通っただけで全プログラムのデッドロックが消えたと結論づけたりしないことが大切です。使用したPythonの実装とバージョンも残してください。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 18

サーバーの中で起きていること · STEP 15

学習コースから次を選ぶ