代码中发生的java死锁

Question

下面是我对并发问题的实现：
5个哲学家，每个哲学家延伸线程：

问题是每次程序在死锁内完成时。我尝试了不同的解决方案，但没有人解决这个问题
也许有人能帮我。

这是我的节目：

import java.util.concurrent.ThreadLocalRandom;

class Fork {
    public static final char FORK = '|';
    public static final char NO_FORK = ' ';
    int id;

    public Fork(final int id) {
        this.id = id;
    }
}

class Philosopher extends Thread {
    public static final char PHIL_THINKING = '-';
    public static final char PHIL_LEFT_FORK = '=';
    public static final char PHIL_EATING = 'o';
    private final int id;

    public Philosopher(final int id) {
        this.id = id;
    }

    @Override
    public void run() {
        final int tableOffset = 4 * id;
        final Object leftLock = S5Philosophers.listOfLocks[id];
        final Object rightLock = S5Philosophers.listOfLocks[(id + 1)
                % S5Philosophers.NUM_PHILOSOPHERS];
        final int table__farL = tableOffset + 0;
        final int table__left = tableOffset + 1;
        final int table_philo = tableOffset + 2;
        final int table_right = tableOffset + 3;
        final int table__farR = (tableOffset + 4)
                % (4 * S5Philosophers.NUM_PHILOSOPHERS);

        while (!isInterrupted()) {
            try {
                Thread.sleep(S5Philosophers.UNIT_OF_TIME
                        * (ThreadLocalRandom.current().nextLong(6)));
            } catch (final InterruptedException e) {
                break;
            }
            // Try to get the chopstick on the left
            synchronized (leftLock) {
                synchronized (S5Philosophers.class) {
                    S5Philosophers.dinerTable[table__farL] = Fork.NO_FORK;
                    S5Philosophers.dinerTable[table__left] = Fork.FORK;
                    S5Philosophers.dinerTable[table_philo] = PHIL_LEFT_FORK;
                }

                try {
                    sleep(S5Philosophers.UNIT_OF_TIME * 1);
                } catch (final InterruptedException e) {
                    break;
                }
                // Try to get the chopstick on the right
                synchronized (rightLock) {
                    synchronized (S5Philosophers.class) {
                        S5Philosophers.dinerTable[table_philo] = PHIL_EATING;
                        S5Philosophers.dinerTable[table_right] = Fork.FORK;
                        S5Philosophers.dinerTable[table__farR] = Fork.NO_FORK;
                        //notify();
                    }
                    try {
                        sleep(S5Philosophers.UNIT_OF_TIME * 1);
                    } catch (final InterruptedException e) {
                        break;
                    }
                    // Release fork
                    synchronized (S5Philosophers.class) {
                        S5Philosophers.dinerTable[table__farL] = Fork.FORK;
                        S5Philosophers.dinerTable[table__left] = Fork.NO_FORK;
                        S5Philosophers.dinerTable[table_philo] = PHIL_THINKING;
                        S5Philosophers.dinerTable[table_right] = Fork.NO_FORK;
                        S5Philosophers.dinerTable[table__farR] = Fork.FORK;
                        //notify();
                    }
                }
            }
        }
    }
}

public class S5Philosophers {
    public static final int NUM_PHILOSOPHERS = 5;
    public static final int UNIT_OF_TIME = 50;
    public static final Fork[] listOfLocks = new Fork[NUM_PHILOSOPHERS];
    public static char[] dinerTable = null;

    static {
        for (int i = 0; i < NUM_PHILOSOPHERS; i++)
            listOfLocks[i] = new Fork(i);
    }

    public static void main(final String[] a) {
        final char[] lockedDiner = new char[4 * NUM_PHILOSOPHERS];
        for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
            lockedDiner[4 * i + 0] = Fork.NO_FORK;
            lockedDiner[4 * i + 1] = Fork.FORK;
            lockedDiner[4 * i + 2] = Philosopher.PHIL_LEFT_FORK;
            lockedDiner[4 * i + 3] = Fork.NO_FORK;
        }
        final String lockedString = new String(lockedDiner);

        // safe publication of the initial representation
        synchronized (S5Philosophers.class) {
            dinerTable = new char[4 * NUM_PHILOSOPHERS];
            for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
                dinerTable[4 * i + 0] = Fork.FORK;
                dinerTable[4 * i + 1] = Fork.NO_FORK;
                dinerTable[4 * i + 2] = Philosopher.PHIL_THINKING;
                dinerTable[4 * i + 3] = Fork.NO_FORK;
            }
        }

        for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
            final Thread t = new Philosopher(i);
            // uses this solution to allow terminating the application even if
            // there is a deadlock
            t.setDaemon(true);
            t.start();
        }

        System.out.println("The diner table:");
        long step = 0;
        while (true) {
            step++;

            String curTableString = null;
            synchronized (S5Philosophers.class) {
                curTableString = new String(dinerTable);
            }
            System.out.println(curTableString + "   " + step);

            if (lockedString.equals(curTableString))
                break;
            try {
                Thread.sleep(UNIT_OF_TIME);
            } catch (final InterruptedException e) {
                System.out.println("Interrupted.");
            }
        }
        System.out.println("The diner is locked.");
    }
}

Answer 1

解决方案相对简单：

1. Philosopher attempts to get fork on left
   SUCCEED -> Continue to step 2
   FAIL -> wait (for a while)
2. Philosopher attempts to get fork on right
   SUCCEED -> Continue to step 3
   FAIL -> Release left fork and wait (for a while)
3. Eat and release both forks. Then wait (for a while)

这里要强调的一点是，每当一个哲学家不能同时获得两个叉子时，他就需要放下手中的叉子，等待一段时间，否则僵局最终会发生

也许更重要的是，什么样的白痴用两个叉子吃饭

编辑

下面是一个快速的叉子示例

class Fork {
    public static final char FORK = '|';
    public static final char NO_FORK = ' ';
    private int id;
    private Lock lock = new ReentrantLock();

    public Fork(final int id) {
        this.id = id;
    }

    public boolean isHeld() {
        return lock.isLocked();
    }

    // returns true if successfully grabbed!
    public synchronized boolean tryToGrab() {
        return lock.tryLock();
    }

    public void letGo() {
        lock.unlock();
    }
}

使用信号量对象的想法也同样适用。祝你好运

Answer 2

我没有答案，但我有几个建议：

（1）这是次要的，但不要覆盖线程：覆盖可运行。这是个好习惯，但我没有时间解释原因。就这么做吧

class Philosopher implements Runnable { ... }
...
Thread t = new Thread(new Philosopher());

（2）不要使用synchronized解决这类问题：使用java。util。同时发生的锁。锁将使您在如何构造代码方面具有更大的灵活性

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

Lock[] listOfLocks = new Lock[NUM_PHILOSOPHERS];
for (int i=0 ; i<listOfLocks.length ; i++) {
    listOfLocks[i] = new ReentrantLock();
}

（3）正如@Holger所指出的，您选择了一种容易陷入僵局的策略；你得试试别的。不幸的是，您的策略深深地嵌入到代码中。这意味着要为你尝试的每一个新策略重新编写大量的内容

考虑如何将策略与代码的其余部分隔离开来。如果您定义了一个“策略”界面，如果您的每个哲学家实例都使用了一个策略来抓取筷子呢

interface Strategy {
    //returns after locking both the leftLock and the rightLock
    public void grabSticks(Lock leftLock, Lock rightLock);
}

class Philosopher implements Runnable {
    private final Strategy strategy;

    public Philosopher(Strategy strategy) {
        this.strategy = strategy;
    }

    @Override
    public void run() {
        ...
        while (...) {
            think();
            strategy.grabSticks(leftLock, rightLock);
            eat();
            leftLock.unlock();
            rightLock.unlock();
        }
    }
}

现在，每次您想尝试不同的方法时，只需更改grabSticks（）方法

。。。或方法！没有理由每个哲学家都必须使用相同的策略

我的策略界面足够好吗？这是一个开始，但也许你可以改进一下。它是否可以扩展到为哲学家提供一些比无声地抓筷子更复杂的合作方式

祝你好运，玩得开心

Answer 3

您的策略是先锁定左侧叉子（或筷子？似乎您无法决定…）。但每个哲学家对“左叉子”都有不同的概念。应该很容易想象，有可能进入这样一种情况，即每一位哲学家在第一步都锁定了他/她的“左叉”，因此没有人可以继续，因为“右叉”被视为他/她的“左叉”的人锁定

但是您应该从调试输出中识别出这种情况

---

提示我如何解决这样的问题：可以在单个int值中表示整个表状态，为每个fork分配一位。因此，对于32位哲学家来说，这就足够了。现在，每个哲学家都将被初始化为一个位掩码，告诉他/她他需要哪些分叉。然后可以使用一个atomic update同时分配两个叉子/筷子。因此，没有必要处理单叉。分配可能成功，也可能失败，使状态保持不变。哲学家必须记住的唯一一件事，除了总是指定的叉位之外，就是他目前是否拥有这两个叉。在他吃完后，他会在一次更新中把两个叉子都放回去

这一策略将解决僵局问题，但从理论上讲不会让一位哲学家挨饿（尽管可能性不大）。对于我的现实生活中的应用程序，我从不创建依赖于锁公平性的多线程代码

但是如果您想完全排除饥饿的可能性，您可以将上面描述的算法扩展到^{}的子类。此类是对使用原子int表示状态的概念的扩展，并支持等待所需资源（位）可用。它的类文档描述了如何实现公平等待，从而使哲学家不必挨饿