並列プログラミングの落とし穴④デッドロック

これまで紹介してきた並列プログラミングの落とし穴のいくつかは、ロックを使えば回避できます。①でも次のようなロックによる問題解決（および副作用）を紹介しました。

        internal static int GetNext()
        {
            return Interlocked.Increment(ref s_curr);
        }

ロックとは、ある範囲の処理やオブジェクト・メモリーへのアクセスを同時には実行できないようにするテクニックであり、「クリティカル セクション」とか「ミューテックス」とか「セマフォ」とか「モニター」などという、同じ目的の微妙に意味や使い方の異なるテクニックがあります。ここではまとめて「ロック」と呼び、個別のテクニックの紹介はしません。

しかしロックにはいくつかの副作用があります。ロックが引き起こす最も厄介な問題がデッドロックです。デッドロックは2つのタスクが2つのオブジェクトをロックしようとするときに発生します。タスクAがオブジェクトaをロックしてからオブジェクトbをロックし、同時にタスクBがオブジェクトbをロックしてからオブジェクトaをロックしようとすると、両方のタスクが他方のタスクのロック解放を待つため、デッドロックが発生します。

銀行口座の作成・入金・引き出し・振込ができる、ロックを使った次のコードを見てみましょう。BankAccountクラスにはコンストラクターと、入金メソッドDepositと、引き出しメソッドWithdrawと、振込メソッドTransferがあります。Mainプログラムでは、それぞれ100万円で2つの口座を作成し、2つのタスクで一方の口座から他方の口座へ、口座aは口座bに1,000円を、口座bは口座aに100円を、振り込み続けます。どちらかの口座の預金残高が振込額より少なくなると、例外が発生して終わります。

    class Program
    {
        static void Main(string[] args)
        {
            BankAccount a = new BankAccount(0, 1000000);
            BankAccount b = new BankAccount(1, 1000000);
            Task A = Task.Factory.StartNew(() =>
            {
                while (true)
                {
                    a.Transfer(b, 1000);
                }
            });
            Task B = Task.Factory.StartNew(() =>
            {
                while (true)
                {
                    b.Transfer(a, 100);
                }
            });
            Task.WaitAll(A, B);
        }
    }

    public class BankAccount
    {
  private decimal m_balance = 0.0M;
        private object m_balanceLock = new object();
        private int m_id;
        public BankAccount(int id, decimal delta)
        {
            m_id = id;
            this.Deposit(delta);
        }
        public void Deposit(decimal delta)
        {
            lock (m_balanceLock)
           {
                m_balance += delta;
                Console.WriteLine("{0:0}の残高は{1:0}円",m_id, m_balance);
            }
        }
        public void Withdraw(decimal delta)
        {
            lock (m_balanceLock)
            {
                if (m_balance < delta)
                    throw new Exception("預金額が不足です");
                m_balance -= delta;
                Console.WriteLine("{0:0}の残高は{1:0}円", m_id, m_balance);
            }
        }
        public void Transfer(BankAccount dest, decimal delta)
        {
            lock (this.m_balanceLock)
            {
                Console.WriteLine("振込中：{0:0}のロック完了", this.m_id);
                lock (dest.m_balanceLock)
                {
                    Console.WriteLine("振込開始");
                    this.Withdraw(delta);
                    dest.Deposit(delta);
                }
            }
        }
    }

まずMainのb.Transferをコメントアウトして実行してみてください。残高がなくなるまで1000円の振り込みを続け、下図のように問題なく（？）例外が発生します。次にコメントを外して実行してみると、「振込中：0のロック完了」と「振込中：1のロック完了」が表示されて止まってしまいます。Transferメソッドを見ると2つのロックが行われており、それぞれ最初のロックを行ってから次のロックを行おうとして、デッドロックになっているのが分かります。

この種のデッドロックはロックの順序を一定にする規則を作れば回避できることが分かっています。例えばこの例では、必ずIDの大きいほうを先にロックするようにロックの順序を決めると、このデッドロックは回避できます。