🌕 🌗 1226. 哲学家进餐

难度: 🌕 🌗

问题描述

---

解法 1 - Semaphore

class DiningPhilosophers {
    // 思路：
    // 5 把叉子可以看成是 5 把锁，每把锁只能被一个线程占有
    // 可以用 ReentrantLock 数组表示
    // 要想解决这个问题，就是说，怎么打破死锁的条件
    // 由于互斥 & 不可剥夺条件已经定死，可以考虑 如何请求并占有 以及 循环等待
    // method 1 - 限制同时最多只能 4 名哲学家用餐，超出的第 5 名哲学家只能阻塞
    ReentrantLock[] list;
    Semaphore s;

    public DiningPhilosophers() {
        this.list = new ReentrantLock[5];
        for(int i = 0; i < 5; i ++) {
            this.list[i] = new ReentrantLock();
        }
        this.s = new Semaphore(4); // 只要 <= 4 的值可以保证不会出现死锁
    }

    // call the run() method of any runnable to execute its code
    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        s.acquire(); // 在拿叉子之前首先得保证并发人数 < 5
        // 拿 左右叉子
        int left = philosopher;
        int right = (philosopher + 1) % 5; // +1 比 -1 要简单些，否则左右都要再 + 5防止出现负数
        list[left].lock();
        list[right].lock();
        pickLeftFork.run();
        pickRightFork.run();
        eat.run();
        putLeftFork.run();
        putRightFork.run();
        list[left].unlock();
        list[right].unlock();
        s.release();
    }
}

---

解法 2 - ReentrantLock

class DiningPhilosophers {
    // 思路：
    // 5 把叉子可以看成是 5 把锁，每把锁只能被一个线程占有
    // 可以用 ReentrantLock 数组表示
    // 要想解决这个问题，就是说，怎么打破死锁的条件
    // 由于互斥 & 不可剥夺条件已经定死，可以考虑 如何请求并占有 以及 循环等待
    // method 1 - 拿起左右叉子之前需要先获取 doubleLock 锁
    ReentrantLock[] list;
    ReentrantLock doubleLock;

    public DiningPhilosophers() {
        this.list = new ReentrantLock[5];
        for(int i = 0; i < 5; i ++) {
            this.list[i] = new ReentrantLock();
        }
        this.doubleLock = new ReentrantLock();
    }

    // call the run() method of any runnable to execute its code
    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        doubleLock.lock(); // 在拿叉子之前首先得获得同时获得 2 把锁的资格
        // 拿 左右叉子
        int left = philosopher;
        int right = (philosopher + 1) % 5; // +1 比 -1 要简单些，否则左右都要再 + 5防止出现负数
        list[left].lock();
        list[right].lock();
        pickLeftFork.run();
        pickRightFork.run();
        doubleLock.unlock(); // 在这里提前释放，可以让其他哲学家早点拿自己想要的钥匙
        eat.run();
        putLeftFork.run();
        putRightFork.run();
        list[left].unlock();
        list[right].unlock();
    }
}

---

解法 3 - 只允许一个哲学家同时用餐

class DiningPhilosophers {
    // 思路：
    // 5 把叉子可以看成是 5 把锁，每把锁只能被一个线程占有
    // 可以用 ReentrantLock 数组表示
    // 要想解决这个问题，就是说，怎么打破死锁的条件
    // 由于互斥 & 不可剥夺条件已经定死，可以考虑 如何请求并占有 以及 循环等待
    // method 3 - 单线程肯定安全，只允许一个哲学家可以同一时间用餐
    // ReentrantLock[] list;
    ReentrantLock doubleLock;

    public DiningPhilosophers() {
        // this.list = new ReentrantLock[5];
        this.doubleLock = new ReentrantLock();
    }

    // call the run() method of any runnable to execute its code
    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        doubleLock.lock(); // 在拿叉子之前首先得获得同时获得 2 把锁的资格
        // 拿 左右叉子
        int left = philosopher;
        int right = (philosopher + 1) % 5; // +1 比 -1 要简单些，否则左右都要再 + 5防止出现负数
        pickLeftFork.run();
        pickRightFork.run();
        eat.run();
        putLeftFork.run();
        putRightFork.run();
        doubleLock.unlock(); // 此时也不需要给叉子加锁了
    }
}

---

解法 4 - 打破循环等待

class DiningPhilosophers {
    // 思路：
    // 5 把叉子可以看成是 5 把锁，每把锁只能被一个线程占有
    // 可以用 ReentrantLock 数组表示
    // 要想解决这个问题，就是说，怎么打破死锁的条件
    // 由于互斥 & 不可剥夺条件已经定死，可以考虑 如何请求并占有 以及 循环等待
    // method 4 - 打破循环等待条件，只有 5 个哲学家同时都拿左叉子 | 右叉子才会出现死锁，
    // 只要保证5个哲学家部分先拿左边，部分先拿右边就可以打破
    ReentrantLock[] list;

    public DiningPhilosophers() {
        this.list = new ReentrantLock[5];
        for(int i = 0; i < 5; i ++) {
            this.list[i] = new ReentrantLock();
        }
    }

    // call the run() method of any runnable to execute its code
    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        // 拿 左右叉子 - 奇数哲学家先拿左边叉子，偶数哲学家先拿右边叉子
        int left = philosopher;
        int right = (philosopher + 1) % 5; // +1 比 -1 要简单些，否则左右都要再 + 5防止出现负数
        if((philosopher & 1) == 1) {
            list[left].lock();
            list[right].lock();
        } else {
            list[right].lock();
            list[left].lock();
        }
        pickLeftFork.run();
        pickRightFork.run();
        eat.run();
        putLeftFork.run();
        putRightFork.run();
        if((philosopher & 1) == 1) {
            list[left].unlock();
            list[right].unlock();
        } else {
            list[right].unlock();
            list[left].unlock();
        }        
    }
}