哲学家进餐问题

哲学家进餐问题

并发进程并发执行时处理共享资源的一个有代表性的问题

在一个圆桌上，有n个哲学家，n只筷子，每个哲学家左右两边各返一只筷子。哲学家可以进行思考和吃饭，思考时，不获取筷子。吃饭时，必须同时获得左右两只筷子才能吃饭（先获得左边，再获得右边）。

5名哲学家与左右邻居对其中间筷子的访问是互斥关系。定义互斥信号量 chopstick[5]={1,1,1,1,1} 用于对5个筷子的互斥访问，对哲学家按顺序编号，哲学家 i 左边的筷子编号为 i ,哲学家右边的筷子的编号为 （i+1）%5 。

该算法存在的问题：

若五位哲学家同时饥饿而各自拿起了左边的筷子，这使五个信号量 chopstick 均为 0，当他们试图去拿起右边的筷子时，都将因无筷子而无限期地等待下去，即可能会引起死锁。

哲学家进餐问题的改进解法：

• 方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。
• 方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。
• 方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。

如方法二：通过互斥信号量 mutex 对 eat() 之前取左侧和右侧筷子的操作进行保护，可以防止死锁的出现：

其他方法：https://blog.csdn.net/qq1004642027/article/details/50055917

---

java多线程 模拟 哲学家进餐问题

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

class Chopstick {
    private int index;
    private boolean use = false;

    public Chopstick(int index){
        super();
        this.index=index;
    }

    @Override
    public String toString() {
        return "Chopstick [index=" + index + "]";
    }

    /*
     * 获得筷子 该筷子被获得之后，当有其他哲学家线程来请求获得时，都需要等待
     */
    public synchronized void take() throws InterruptedException {
        while (use)
            wait();
        use = true;
    }

    /*
     * 归还筷子 当持有该筷子的哲学家使用完毕之后，就将其归还，并通知其他在等待该筷子资源的哲学家
     */
    public synchronized void drop() {
        use = false;
        notifyAll();
    }
}

class Philosopher implements Runnable {
    private Chopstick right;
    private Chopstick left;
    private int index;
    private int thinkTime;

    public Philosopher(Chopstick right, Chopstick left, int index, int thinkingTime) {
        super();
        this.right = right;
        this.left = left;
        this.index = index;
        this.thinkTime = thinkingTime;
    }

    @Override
    public void run() {
        try {
            while (!Thread.interrupted()) {
                System.out.println(this + " thinking .......");
                thinking();
                System.out.println(this + " start to eat and take left stick");
                left.take();
                System.out.println(this + " take right stick");
                right.take();
                System.out.println(this + " eating");
                thinking();// 吃饭
                left.drop();
                right.drop();
            }
        } catch (InterruptedException e) {
            System.out.println(this + "InterruptedException");
        }
    }

    /**
     * 哲学家思考时间，由thinkingTime因子决定
     * 
     * @throws InterruptedException
     */
    private void thinking() throws InterruptedException {
        Thread.sleep(thinkTime * 100);
    }

    @Override
    public String toString() {
        return "Philosopher [index=" + index + "]";
    }
}

public class Chopstick_Philosopher {

    public static void main(String[] args) throws InterruptedException {
        ExecutorService executor = Executors.newCachedThreadPool();
        int size=5;
        int thinkingTime=0;
        Chopstick[] chopstick = new Chopstick[size];
        for(int i=0;i<size;i++)
            chopstick[i] = new Chopstick(i);
        for(int i=0;i<size;i++)
            executor.execute(new Philosopher(chopstick[i], chopstick[(i+1)%size], i, thinkingTime));
        Thread.sleep(4*1000);
        executor.shutdownNow();
    }

}

如果设置思考时间为0，那么很快会死锁，每个线程运行以请求右边筷子结束：
Philosopher [index=0] take right stick
Philosopher [index=4] take right stick
Philosopher [index=1] take right stick
Philosopher [index=2] take right stick
Philosopher [index=3] take right stick

解决方法一：
破坏产生死锁的循环条件
使第五个哲学家不按照先获得左边筷子，再获得右边筷子的方式进行

    public static void main(String[] args) throws InterruptedException {
        ExecutorService executor = Executors.newCachedThreadPool();
        int size=5;
        int thinkingTime=0;
        Chopstick[] chopstick = new Chopstick[size];
        for(int i=0;i<size;i++)
            chopstick[i] = new Chopstick(i);
        for(int i=0;i<size-1;i++)
            executor.execute(new Philosopher(chopstick[i], chopstick[(i+1)%size], i, thinkingTime));
        executor.execute(new Philosopher(chopstick[0], chopstick[size-1], size, thinkingTime));//更改第五个哲学家获得筷子的顺序，先右后左
        Thread.sleep(100*1000);
        executor.shutdownNow();
    }

解决方法二：
破坏请求和保持条件，增加静态变量 lock ,给获得左筷子和右筷子的过程加锁，当一个哲学家要拿筷子吃饭时，其他哲学家先别动筷子，并发能力较差。

class Philosopher implements Runnable {
    private Chopstick left;
    private Chopstick right;
    private int index;
    private int thinkTime;
    static Object lock=new Object();

    public Philosopher(Chopstick left, Chopstick right, int index, int thinkingTime) {
        super();
        this.left = left;
        this.right = right;
        this.index = index;
        this.thinkTime = thinkingTime;
    }

    @Override
    public void run() {
        try {
            while (!Thread.interrupted()) {
                System.out.println(this + " thinking .......");
                thinking();
                // 吃饭
                synchronized (lock) {
                    System.out.println(this + " start to eat and take left stick");
                    left.take();
                    System.out.println(this + " take right stick");
                    right.take();
                    System.out.println(this + " eating");
                }
                left.drop();
                right.drop();
            }
        } catch (InterruptedException e) {
            System.out.println(this + "InterruptedException");
        }
    }

    /**
     * 哲学家思考时间，由thinkingTime因子决定
     * @throws InterruptedException
     */
    private void thinking() throws InterruptedException {
        Thread.sleep(thinkTime * 100);
    }

    @Override
    public String toString() {
        return "Philosopher [index=" + index + "]";
    }
}

---

死锁

定义：
多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都讲无法向前推进。

死锁产生的原因：

1. 非剥夺式资源的竞争
2. 进程推进顺序非法

死锁产生的必要条件：

1. 互斥条件：进程要求对所有分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个资源所占有。
2. 不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，只能是主动释放。
3. 请求和保持条件：进程已经保持了至少一个资源，但又提出了对新资源的请求，但该资源已经被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源不释放。
4. 循环等待条件：存在一个进程资源的请求等待链，链中每一个资源每一个资源以获得的资源同时被链中另一个进程所请求。

预防死锁：

1. 破坏互斥条件：有些资源必须互斥使用，无法破坏互斥条件
2. 破坏不剥夺条件：增加系统开销，降低吞吐量
3. 破坏请求和保存条件：严重浪费系统资源，还可能导致饥饿现象
4. 破坏循环等待条件：浪费系统资源，并造成编程不便

避免死锁：

1. 安全状态：能找到一个分配资源的序列能够让所有进程顺利执行
2. 银行家算法：采用预分配策略检查分配完成时系统能否处于安全状态

检测死锁：利用死锁定理化简资源分配图以检测死锁的存在

解除死锁：

1. 资源剥夺法：挂起某些死锁进程并抢夺它的资源，以便让其他进程继续推进
2. 撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源
3. 进程回退法：让进程回退到足以回避死锁的地步