Python でのデッドロック形成の例とデッドロック状況の防止

デッドロックの例
マルチスレッドを使用する人は、オペレーティング システムを学習するときにデッドロックの問題に遭遇することがよくあります。Python を使用してそれを直感的に説明します。
デッドロックの原因の 1 つはミューテックス ロックです。銀行システムで、ユーザー a がユーザー b に 100 元を送金しようとし、同時にユーザー b がユーザー a に 200 元を送金しようとすると、デッドロックが発生する可能性があります。
2 つのスレッドは互いのロックを待機し、互いのリソースを占有して解放しません。

#coding=utf-8 
import time 
import threading 
class Account: 
  def __init__(self, _id, balance, lock): 
    self.id = _id 
    self.balance = balance 
    self.lock = lock 
 
  def withdraw(self, amount): 
    self.balance -= amount 
 
  def deposit(self, amount): 
    self.balance += amount 
 
 
def transfer(_from, to, amount): 
  if _from.lock.acquire():#锁住自己的账户 
    _from.withdraw(amount) 
    time.sleep(1)#让交易时间变长，2个交易线程时间上重叠，有足够时间来产生死锁 
    print 'wait for lock...' 
    if to.lock.acquire():#锁住对方的账户 
      to.deposit(amount) 
      to.lock.release() 
    _from.lock.release() 
  print 'finish...' 
 
a = Account('a',1000, threading.Lock()) 
b = Account('b',1000, threading.Lock()) 
threading.Thread(target = transfer, args = (a, b, 100)).start() 
threading.Thread(target = transfer, args = (b, a, 200)).start() 

デッドロックを防ぐロック機構
質問:
スレッドが一度に複数のロックを取得する必要があるマルチスレッド プログラムを作成している場合、デッドロックの問題を回避する方法。
解決策:
マルチスレッド プログラムでは、デッドロックの問題の大部分は、スレッドが同時に複数のロックを取得することによって発生します。たとえば、スレッドが最初のロックを取得し、2 番目のロックを取得するときにブロックした場合、このスレッドは他のスレッドの実行をブロックし、プログラム全体がフリーズする可能性があります。 デッドロックの問題に対する 1 つの解決策は、プログラム内の各ロックに一意の ID を割り当て、複数のロックを昇順でのみ使用できるようにすることです。このルールは、コンテキスト マネージャーを使用して非常に簡単に実装できます。

import threading
from contextlib import contextmanager

# Thread-local state to stored information on locks already acquired
_local = threading.local()

@contextmanager
def acquire(*locks):
  # Sort locks by object identifier
  locks = sorted(locks, key=lambda x: id(x))

  # Make sure lock order of previously acquired locks is not violated
  acquired = getattr(_local,'acquired',[])
  if acquired and max(id(lock) for lock in acquired) >= id(locks[0]):
    raise RuntimeError('Lock Order Violation')

  # Acquire all of the locks
  acquired.extend(locks)
  _local.acquired = acquired

  try:
    for lock in locks:
      lock.acquire()
    yield
  finally:
    # Release locks in reverse order of acquisition
    for lock in reversed(locks):
      lock.release()
    del acquired[-len(locks):]

このコンテキストマネージャーの使い方は?通常の方法でロック オブジェクトを作成できますが、単一ロックであっても複数ロックであっても、ロックを適用するにはacquire()関数を使用します。例は次のとおりです:

import threading
x_lock = threading.Lock()
y_lock = threading.Lock()

def thread_1():
  while True:
    with acquire(x_lock, y_lock):
      print('Thread-1')

def thread_2():
  while True:
    with acquire(y_lock, x_lock):
      print('Thread-2')

t1 = threading.Thread(target=thread_1)
t1.daemon = True
t1.start()

t2 = threading.Thread(target=thread_2)
t2.daemon = True
t2.start()

このコードを実行すると、異なる関数で異なる順序でロックを取得してもデッドロックにならないことがわかります。 重要なのは、コードの最初の部分でこれらのロックを並べ替えていることです。ソートにより、ユーザーがロックを要求した順序に関係なく、これらのロックは固定された順序で取得されます。 複数のacquire()操作が入れ子になって呼び出された場合、潜在的なデッドロックの問題がスレッド・ローカル・ストレージ(TLS)を通じて検出される可能性があります。 コードが次のように書かれているとします:

import threading
x_lock = threading.Lock()
y_lock = threading.Lock()

def thread_1():

  while True:
    with acquire(x_lock):
      with acquire(y_lock):
        print('Thread-1')

def thread_2():
  while True:
    with acquire(y_lock):
      with acquire(x_lock):
        print('Thread-2')

t1 = threading.Thread(target=thread_1)
t1.daemon = True
t1.start()

t2 = threading.Thread(target=thread_2)
t2.daemon = True
t2.start()

このバージョンのコードを実行すると、1 つのスレッドが確実にクラッシュし、例外メッセージは次のようになります。

Exception in thread Thread-1:
Traceback (most recent call last):
 File "/usr/local/lib/python3.3/threading.py", line 639, in _bootstrap_inner
  self.run()
 File "/usr/local/lib/python3.3/threading.py", line 596, in run
  self._target(*self._args, **self._kwargs)
 File "deadlock.py", line 49, in thread_1
  with acquire(y_lock):
 File "/usr/local/lib/python3.3/contextlib.py", line 48, in __enter__
  return next(self.gen)
 File "deadlock.py", line 15, in acquire
  raise RuntimeError("Lock Order Violation")
RuntimeError: Lock Order Violation
>>>

クラッシュの理由は、各スレッドが取得したロックを記録することです。 acquire() 関数は、以前に取得したロックのリストをチェックします。ロックは昇順に取得されるため、関数は以前に取得したロックの ID が新しく取得したロックよりも小さい必要があると判断し、例外がトリガーされます。

話し合う
デッドロックは、すべてのマルチスレッド プログラムが直面する問題です (すべてのオペレーティング システムの教科書に共通のトピックがあるのと同様です)。経験によれば、プログラムがデッドロックの問題に悩まされないように、各スレッドが同時に保持できるロックは 1 つだけであることを確認してください。スレッドが同時に複数のロックを申請すると、すべてが予測不能になります。

デッドロックの検出と回復は拡張されたトピックであり、洗練されたソリューションはほとんどありません。より一般的に使用されるデッドロックの検出および回復ソリューションは、ウォッチドッグ カウンタを導入することです。スレッドが正常に実行されている場合、カウンタは時々リセットされ、デッドロックが発生しなければすべてが正常に進行します。デッドロックが発生し、カウンタをリセットできないためにタイマーがタイムアウトすると、プログラム自体が再起動されて通常に戻ります。

デッドロックを回避することは、プロセスがロックを取得するときに、オブジェクト ID の昇順で厳密に取得されるため、プログラムがデッドロック状態にならないことが数学的に証明されています。 。証明は読者の演習として残されます。デッドロックを回避する主な考え方は、オブジェクト ID の増加順にロックするだけでは循環依存関係は生じず、循環依存関係はデッドロックの必須条件であるため、プログラムがデッドロック状態に陥るのを防ぐというものです。

次に、スレッドのデッドロックに関する古典的な問題を示します。このセクションの最後の例として「ダイニング哲学者問題」を取り上げます。テーマはこれです。5 人の哲学者がテーブルの周りに座り、それぞれの前にお茶碗と箸を持っています。ここでは、各哲学者を独立した糸とみなすことができ、各箸を錠前とみなすことができます。各哲学者は、静かに座っている、考えている、または食事をしているという 3 つの状態のいずれかになります。各哲学者が食事をするには2本の箸が必要であることに注意してください。そのため、各哲学者が左側の箸を取った場合、私が餓死するまで、5人全員がそこに1本の箸しか座ることができません。この時点で、デッドロック状態になります。 以下は、デッドロック回避メカニズムを使用して「食事の哲学者問題」を解決する簡単な実装です:

import threading

# The philosopher thread
def philosopher(left, right):
  while True:
    with acquire(left,right):
       print(threading.currentThread(), 'eating')

# The chopsticks (represented by locks)
NSTICKS = 5
chopsticks = [threading.Lock() for n in range(NSTICKS)]

# Create all of the philosophers
for n in range(NSTICKS):
  t = threading.Thread(target=philosopher,
             args=(chopsticks[n],chopsticks[(n+1) % NSTICKS]))
  t.start()

最後に、デッドロックを回避するには、すべてのロック操作で Acquire() 関数を使用する必要があることに注意することが重要です。コードの一部が取得関数をバイパスしてロックを直接適用すると、デッドロック回避メカニズム全体が機能しなくなります。