哲学家就餐问题与死锁总结

古城微笑少年丶 2021-10-01 08:06 304阅读 0赞

死锁的四个条件：  
（1） 互斥条件：一个资源每次只能被一个进程使用。  
（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。  
（3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。  
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系

先写一个会造成死锁的哲学家问题。当所有哲学家同时决定进餐，拿起左边筷子时候，就发生了死锁。

public class test {
    
        public static void main(String[] args) {
            ExecutorService exec = Executors.newCachedThreadPool();
            int sum = 5;
            Chopstick[] chopsticks = new Chopstick[sum];
            for (int i = 0; i < sum; i++) {
                chopsticks[i] = new Chopstick();
            }
            for (int i = 0; i < sum; i++) {
                exec.execute(new Philosopher(chopsticks[i], chopsticks[(i + 1) % sum]));
            }
        }
    }
    
    // 筷子
    class Chopstick {
        public Chopstick() {
        }
    }
    class Philosopher implements Runnable {
    
        private Chopstick left;
        private Chopstick right;
    
        public Philosopher(Chopstick left, Chopstick right) {
            this.left = left;
            this.right = right;
        }
    
        @Override
        public void run() {
            try {
                while (true) {
                    Thread.sleep(1000);//思考一段时间
                    synchronized (left) {
                        synchronized (right) {
                            Thread.sleep(1000);//进餐一段时间
                        }
                    }
                } 
                }
                catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
        }
    
    }

解决方案一：破坏死锁的**循环等待条件**。  
不再按左手边右手边顺序拿起筷子。选择一个固定的全局顺序获取，此处给筷子添加id，根据id从小到大获取，(不用关心编号的具体规则，只要保证编号是全局唯一并且有序的)，不会出现死锁情况。

public class test {
    
        public static void main(String[] args) {
            ExecutorService exec = Executors.newCachedThreadPool();
            int sum = 5;
            Chopstick[] chopsticks = new Chopstick[sum];
            for (int i = 0; i < sum; i++) {
                chopsticks[i] = new Chopstick(i);
            }
            for (int i = 0; i < sum; i++) {
                exec.execute(new Philosopher(chopsticks[i], chopsticks[(i + 1) % sum]));
            }
        }
    }
    
    // 筷子
    class Chopstick {
    
        //状态
        private int id;
    
        public Chopstick(int id) {
            this.id=id;
        }
    
        public int getId() {
            return id;
        }
    
        public void setId(int id) {
            this.id = id;
        }
    
        
    }
    
    // 哲学家
    class Philosopher implements Runnable {
    
        private Chopstick left;
        private Chopstick right;
    
        public Philosopher(Chopstick left, Chopstick right) {
            if(left.getId()<right.getId()){
                this.left = left;this.right = right;
            }else{
                this.left=right;this.right=left;
            }
        }
        
        @Override
        public void run() {
            try {
                while (true) {
                    Thread.sleep(1000);//思考一段时间
                    synchronized (left) {
                        synchronized (right) {
                            Thread.sleep(1000);//进餐一段时间
                        }
                    }
                } 
                }
                catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
        }
    
    }

方法二：破坏死锁的**请求与保持条件**，使用lock的特性，为获取锁操作设置超时时间。这样不会死锁（至少不会无尽的死锁）

class Philosopher extends Thread{
        private ReentrantLock left,right;
    
        public Philosopher(ReentrantLock left, ReentrantLock right) {
            super();
            this.left = left;
            this.right = right;
        }
        public void run(){
            try {
                while(true){
                    Thread.sleep(1000);//思考一段时间
                    left.lock();
                    try{
                        if(right.tryLock(1000,TimeUnit.MILLISECONDS)){
                            try{
                                Thread.sleep(1000);//进餐一段时间
                            }finally {
                                right.unlock();
                            }
                        }else{
                            //没有获取到右手的筷子，放弃并继续思考
                        }
                    }finally {
                        left.unlock();
                    }
                }
            } catch (InterruptedException e) {
            }
        }
    }

方法三：设置一个条件遍历与一个锁关联。该方法只用一把锁，没有chopstick类，将竞争从对筷子的争夺转换成了对状态的判断。仅当左右邻座都没有进餐时才可以进餐。提升了并发度。前面的方法出现情况是：只有一个哲学家进餐，其他人持有一根筷子在等待另外一根。这个方案中，当一个哲学家理论上可以进餐（邻座没有进餐），他肯定可以进餐。

public class Philosopher extends Thread{
    
        private boolean eating;
        private Philosopher left;
        private Philosopher right;
        private ReentrantLock lock;
        private Condition condition;
        
        public Philosopher(ReentrantLock lock){
            eating =false;
            this.lock=lock;
            condition=lock.newCondition();
        }
                
        public void setLeft(Philosopher left) {
            this.left = left;
        }
    
        public void setRight(Philosopher right) {
            this.right = right;
        }
    
        public void think() throws InterruptedException{
            lock.lock();
            try {
                eating=false;
                System.out.println(Thread.currentThread().getName()+"开始思考");
                left.condition.signal();
                right.condition.signal();
            } finally{
                lock.unlock();
            }
            Thread.sleep(1000);
        }
    
        public void eat() throws InterruptedException{
            lock.lock();
            try {
                while(left.eating||right.eating)
                    condition.await();
                System.out.println(Thread.currentThread().getName()+"开始吃饭");
                eating=true;
            } finally {
                // TODO: handle finally clause
                lock.unlock();
            }
            Thread.sleep(1000);
        }
        
        public void run(){
            try{
                while(true){
                    think();
                    eat();
                }
            }catch(InterruptedException e){}
        }
        
    }