Next: 16 スレッドのスケジューリング Up: ソフトウェア第三　講義資料 Java入門，宣言，インタフェース，パッケージ，スレッド Previous: 14.3 waitセット

15 Starvationと Deadlock

ある資源を複数のスレッドが待っている状態を飢餓状態(starvation)といい，どうにも利用できなくなってしまっている状態をデッドロック (deadlock)状態という．デッドロックの簡単な例としては，二つのスレッドA,Bが二つの資源X,Yの両方をそれぞれ必要とするような場合に簡単に起こってしまう．それは，AがXをとり，BがYをとった状態にもしなったとすると， Aが次のYを必要として待ちに入り，BもXを必要として待ちの状態に入ってしまうためである． AがXを開放するか，BがYを開放するかしなければこの状態がずっと続いてしまう．食事をする哲学者の問題(The dining philosophers problem, 1965, Dijikstra) はデッドロックが起こる問題として有名．


// Friendly.java
class Friendly {
    private Friendly partner;
    private String name;

    public Friendly(String name) {
        this.name = name;
    }

    public synchronized void hug() {
        System.out.println(
            Thread.currentThread().getName() +
            " in " + name +
            ".hug() trying to invoke " +
            partner.name + ".hugBack()");
        partner.hugBack();
    }

    private synchronized void hugBack() {
        System.out.println(
            Thread.currentThread().getName() +
            " in " + name +
            ".hugBack()");
    }

    public void becomeFriend(Friendly partner) {
        this.partner = partner;
    }

    public static void main(String[] args) {
        final Friendly jareth = new Friendly("jareth");
        final Friendly cory = new Friendly("cory");
        jareth.becomeFriend(cory);
        cory.becomeFriend(jareth);

        new Thread(new Runnable() {
                public void run() { jareth.hug(); }
            }, "Thread1").start();

        new Thread(new Runnable() {
                public void run() { cory.hug(); }
            }, "Thread2").start();
    }
}

これを実行すると，


% java Friendly
Thread1 in jareth.hug() trying to invoke cory.hugBack()
Thread1 in cory.hugBack()
Thread2 in cory.hug() trying to invoke jareth.hugBack()
Thread2 in jareth.hugBack()
% java Friendly
Thread1 in jareth.hug() trying to invoke cory.hugBack()
Thread1 in cory.hugBack()
Thread2 in cory.hug() trying to invoke jareth.hugBack()
Thread2 in jareth.hugBack()
% java Friendly
Thread1 in jareth.hug() trying to invoke cory.hugBack()
Thread1 in cory.hugBack()
Thread2 in cory.hug() trying to invoke jareth.hugBack()
Thread2 in jareth.hugBack()

デッドロックを回避する方法としては，リソース順序付け(resource ordering) という方法がある．これは，ロックを獲得しなければいけない複数のオブジェクトに対して順序を決めて，その順序で常にロックを獲得するようにする方法である．この方法であれば，二つのスレッドが互いに一つずつのロックを獲得して，さらに他方が持っているロックを獲得しようとすることができなくなる．

generated through LaTeX2HTML. M.Inaba 平成18年5月7日