欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

哲学家就餐问题之java解决

程序员文章站 2022-06-17 18:54:33
文章目录前言如何解决这个问题呢1.线程粗化2.奇偶互反3.最少保证前言哲学家就餐问题是在计算机科学中的一个经典问题,用来演示在并行计算中多线程同步(Synchronization)时产生的问题。有五个哲学家,他们共用一张圆桌,分别坐在五张椅子上。在圆桌上有五个碗和五支筷子,平时一个哲学家进行思考,饥饿时便试图取用其左、右最靠近他的筷子,只有在他拿到两支筷子时才能进餐。进餐完毕,放下筷子又继续思考。代码描述:public class PhilosopherThread extends Thread...

前言

哲学家就餐问题是在计算机科学中的一个经典问题,用来演示在并行计算中多线程同步(Synchronization)时产生的问题。
有五个哲学家,他们共用一张圆桌,分别坐在五张椅子上。在圆桌上有五个碗和五支筷子,平时一个哲学家进行思考,饥饿时便试图取用其左、右最靠近他的筷子,只有在他拿到两支筷子时才能进餐。进餐完毕,放下筷子又继续思考。

哲学家就餐问题之java解决

代码描述:

public class PhilosopherThread extends Thread {

    private Chopsticks left;

    private Chopsticks right;

    private int index;

    public PhilosopherThread(Chopsticks left, Chopsticks right, int index) {
        this.left = left;
        this.index = index;
        this.right = right;
    }

    @Override
    public void run() {
        synchronized (left) {
            try {
                Thread.sleep(3000L);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println(index + "等待获取筷子RIGHT进行吃饭");
            synchronized (right) {
                System.out.println(index + "获取筷子RIGHT进行吃饭");
            }
        }



    }

    public static void main(String[] args) {
        Chopsticks chopsticks1 = new Chopsticks();
        Chopsticks chopsticks2 = new Chopsticks();
        Chopsticks chopsticks3 = new Chopsticks();
        Chopsticks chopsticks4 = new Chopsticks();
        Chopsticks chopsticks5 = new Chopsticks();

        PhilosopherThread philosopherThread1 = new PhilosopherThread(chopsticks1, chopsticks2, 1);
        PhilosopherThread philosopherThread2 = new PhilosopherThread(chopsticks2, chopsticks3, 2);
        PhilosopherThread philosopherThread3 = new PhilosopherThread(chopsticks3, chopsticks4, 3);
        PhilosopherThread philosopherThread4 = new PhilosopherThread(chopsticks4, chopsticks5, 4);
        PhilosopherThread philosopherThread5 = new PhilosopherThread(chopsticks5, chopsticks1, 5);
        philosopherThread1.start();
        philosopherThread2.start();
        philosopherThread3.start();
        philosopherThread4.start();
        philosopherThread5.start();
    }
}

通过运行代码,我们发现每一个哲学家都持有左边的筷子取去取右边的筷子,到第五个人的时候,他需要获取的右边筷子是第一个哲学家左手的筷子,最终形成死锁。

如何解决这个问题呢

1. 线程粗化,一个哲学家同时拥有左右筷子时才允许进餐。
2. 奇偶互反,奇数哲学家先取右边,偶数先取左边。
3. 最少保证,最多只有4名哲学家同时去获取左边筷子,最后一名先获取右边筷子,也就是说最少保证有一个哲学家和其他哲学家的取筷顺序是相反的。

1.线程粗化

看代码,我们得知每一个哲学家都是先持有左边的筷子,然后再去获取右边的筷子,如果我们让哲学家同时持有左右筷子的时候在进餐,是不是就能保证不会出现死锁的情况呢。

在java中,没办法同时获取两个对象的锁,必须先获取左边或者右边筷子,才能获取另外一只筷子的锁,这时候我们抽象一下,把左右筷子当成一整个变量,谁获取到了这个变量的锁,就当谁同时持有了左右两只筷子。

也就是说通过一个全局变量,使用互斥锁的方式,谁先获得了,谁就允许进餐。

这种方式可不可行呢,我们看看代码

   public class PhilosopherThread extends Thread {
    
        private Chopsticks left;
    
        private Chopsticks right;
    
        private int index;
    
        private String mutex;
    
        public PhilosopherThread(Chopsticks left, Chopsticks right, int index, String mutex) {
            this.left = left;
            this.index = index;
            this.right = right;
            this.mutex = mutex;
        }
    
        @Override
        public void run() {
            try {
                Thread.sleep(3000L);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            synchronized (mutex) {
                System.out.println(index + " :获取筷进行吃饭:" + left + ":" + right);
    
            }
    
        }
    
        public static void main(String[] args) {
            Chopsticks chopsticks1 = new Chopsticks();
            Chopsticks chopsticks2 = new Chopsticks();
            Chopsticks chopsticks3 = new Chopsticks();
            Chopsticks chopsticks4 = new Chopsticks();
            Chopsticks chopsticks5 = new Chopsticks();
    
            String mutex="lock";
            PhilosopherThread philosopherThread1 = new PhilosopherThread(chopsticks1, chopsticks2, 1,mutex);
            PhilosopherThread philosopherThread2 = new PhilosopherThread(chopsticks2, chopsticks3, 2,mutex);
            PhilosopherThread philosopherThread3 = new PhilosopherThread(chopsticks3, chopsticks4, 3,mutex);
            PhilosopherThread philosopherThread4 = new PhilosopherThread(chopsticks4, chopsticks5, 4,mutex);
            PhilosopherThread philosopherThread5 = new PhilosopherThread(chopsticks5, chopsticks1, 5,mutex);
            philosopherThread1.start();
            philosopherThread2.start();
            philosopherThread3.start();
            philosopherThread4.start();
            philosopherThread5.start();
    
        }
    }

2.奇偶互反

奇偶互反实际上就是针对哲学家编号,奇偶数获取相反的顺序,

比如哲学家编号从1到5,奇数的先取左边筷子,偶数的取右边筷子。那么1号哲学家取左边,2号哲学家取右边,3号哲学家取左边,以此类推,通过这样编号得到的结果就是,1号获取到左右筷子,开始进餐,2号获取到右边筷子,等待1号吃完放下在获取左边筷子(1号的右边是2号的左边),3号等待获取左边筷子,4号这时候又能同时拥有左右筷子开始进餐。

  public class PhilosopherThread extends Thread {
    
        private Chopsticks left;
    
        private Chopsticks right;
    
        private int index;
    
    
        public PhilosopherThread(Chopsticks left, Chopsticks right, int index) {
            this.left = left;
            this.index = index;
            this.right = right;
        }
    
        @Override
        public void run() {
    
            if (index % 2 == 0) {
                synchronized (right) {
                    try {
                        Thread.sleep(3000L);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(index + "等待获取筷子LEFT进行吃饭");
                    synchronized (right) {
                        System.out.println(index + "获取筷子LEFT进行吃饭");
                    }
                }
            } else {
                synchronized (left) {
                    try {
                        Thread.sleep(3000L);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(index + "等待获取筷子RIGHT进行吃饭");
                    synchronized (right) {
                        System.out.println(index + "获取筷子RIGHT进行吃饭");
                    }
                }
            }
    
        }
    
        public static void main(String[] args) {
            Chopsticks chopsticks1 = new Chopsticks();
            Chopsticks chopsticks2 = new Chopsticks();
            Chopsticks chopsticks3 = new Chopsticks();
            Chopsticks chopsticks4 = new Chopsticks();
            Chopsticks chopsticks5 = new Chopsticks();
    
            PhilosopherThread philosopherThread1 = new PhilosopherThread(chopsticks1, chopsticks2, 1);
            PhilosopherThread philosopherThread2 = new PhilosopherThread(chopsticks2, chopsticks3, 2);
            PhilosopherThread philosopherThread3 = new PhilosopherThread(chopsticks3, chopsticks4, 3);
            PhilosopherThread philosopherThread4 = new PhilosopherThread(chopsticks4, chopsticks5, 4);
            PhilosopherThread philosopherThread5 = new PhilosopherThread(chopsticks5, chopsticks1, 5);
            philosopherThread1.start();
            philosopherThread2.start();
            philosopherThread3.start();
            philosopherThread4.start();
            philosopherThread5.start();
    
        }
    }

3.最少保证

最少保证,最多只有4名哲学家同时去获取左边筷子,最后一名先获取右边筷子,也就是说最少保证有一个哲学家和其他哲学家的取筷顺序是相反的。这实际上和奇偶的思路是一致的,每次保证有一个人哲学家获取筷子的顺序和其他哲学家相反,这样死锁的条件就不成立。

   public class PhilosopherThread extends Thread {
    
        private Chopsticks left;
    
        private Chopsticks right;
    
        private int index;
    
    
        public PhilosopherThread(Chopsticks left, Chopsticks right, int index) {
            this.left = left;
            this.index = index;
            this.right = right;
        }
    
        @Override
        public void run() {
    
            if (index==5) {
                synchronized (right) {
                    try {
                        Thread.sleep(3000L);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(index + "等待获取筷子LEFT进行吃饭");
                    synchronized (right) {
                        System.out.println(index + "获取筷子LEFT进行吃饭");
                    }
                }
            } else {
                synchronized (left) {
                    try {
                        Thread.sleep(3000L);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(index + "等待获取筷子RIGHT进行吃饭");
                    synchronized (right) {
                        System.out.println(index + "获取筷子RIGHT进行吃饭");
                    }
                }
            }
    
        }
    
        public static void main(String[] args) {
            Chopsticks chopsticks1 = new Chopsticks();
            Chopsticks chopsticks2 = new Chopsticks();
            Chopsticks chopsticks3 = new Chopsticks();
            Chopsticks chopsticks4 = new Chopsticks();
            Chopsticks chopsticks5 = new Chopsticks();
    
            PhilosopherThread philosopherThread1 = new PhilosopherThread(chopsticks1, chopsticks2, 1);
            PhilosopherThread philosopherThread2 = new PhilosopherThread(chopsticks2, chopsticks3, 2);
            PhilosopherThread philosopherThread3 = new PhilosopherThread(chopsticks3, chopsticks4, 3);
            PhilosopherThread philosopherThread4 = new PhilosopherThread(chopsticks4, chopsticks5, 4);
            PhilosopherThread philosopherThread5 = new PhilosopherThread(chopsticks5, chopsticks1, 5);
            philosopherThread1.start();
            philosopherThread2.start();
            philosopherThread3.start();
            philosopherThread4.start();
            philosopherThread5.start();
    
        }

本文地址:https://blog.csdn.net/kissfox220/article/details/109602882