Java多线程之哲学家就餐问题详解

问题描述

哲学家就餐问题（Dining philosophers problem）是一类典型的同步问题，有多个哲学家围坐在一张圆桌前，每个哲学家旁边放着一碗米饭和一条筷子。哲学家思考问题需要使用双手拿起两个相邻的筷子才能进餐，问题在于如何避免产生死锁（Deadlock）。

解决方案

方案一：线程同步

最常见的解决方案是通过线程同步来确保资源的互斥访问，即安排一个管理人员来协调哲学家们的行为。

首先我们需要对每一只筷子使用一个锁，以便每次只有一个哲学家可以用餐，并确保没有死锁的情况发生。当一位哲学家想要用餐时，他必须先碰到左边的筷子，再碰到右边的筷子。当他完成用餐后，需要将两个筷子同时放回桌面，以便其他哲学家使用。

public class DiningPhilosophers {
    private ReentrantLock[] locks = new ReentrantLock[5];

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

    public void startEating(int philosopherId) {
        int leftFork = philosopherId;
        int rightFork = (philosopherId + 1) % 5;

        // 加锁筷子
        locks[leftFork].lock();
        locks[rightFork].lock();

        System.out.println("Philosopher " + philosopherId + " is starting to eat...");

        try {
            Thread.sleep(1000); // 模拟用餐时间
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // 释放锁
        locks[rightFork].unlock();
        locks[leftFork].unlock();

        System.out.println("Philosopher " + philosopherId + " has finished eating.");
    }

    public static void main(String[] args) {
        DiningPhilosophers philosophers = new DiningPhilosophers();

        for (int i = 0; i < 5; i++) {
            final int philosopherId = i;

            Thread thread = new Thread(new Runnable() {
                @Override
                public void run() {
                    philosophers.startEating(philosopherId);
                }
            });

            thread.start();
        }
    }
}

方案二：资源层次分配法

除了使用线程同步，还可以采用资源层次分配法来避免死锁。根据《操作系统概念》的定义，资源层次分配法（Hierarchical allocation）是指为每个资源分配一个全局唯一的编号，当线程需要访问多个资源时，要按照编号的大小依次申请，避免产生死锁。

例如，我们可以为每个哲学家分配一个编号，如果要用餐，必须先从编号小的哲学家开始拿筷子。通过这样的方式，我们可以保证每个哲学家都拿到了左右两只筷子。

public class DiningPhilosophers {
    private Semaphore[] forks = new Semaphore[5];
    private Semaphore maxNumber = new Semaphore(4);

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) {
            forks[i] = new Semaphore(1);
        }
    }

    public void startEating(int philosopherId) {
        int leftFork = philosopherId;
        int rightFork = (philosopherId + 1) % 5;

        try {
            // 从编号小的哲学家开始获取筷子
            maxNumber.acquire();
            forks[leftFork].acquire();
            forks[rightFork].acquire();

            System.out.println("Philosopher " + philosopherId + " is starting to eat...");

            Thread.sleep(1000); // 模拟用餐时间

            // 释放筷子
            forks[rightFork].release();
            forks[leftFork].release();
            maxNumber.release();

            System.out.println("Philosopher " + philosopherId + " has finished eating.");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        DiningPhilosophers philosophers = new DiningPhilosophers();

        for (int i = 0; i < 5; i++) {
            final int philosopherId = i;

            Thread thread = new Thread(new Runnable() {
                @Override
                public void run() {
                    philosophers.startEating(philosopherId);
                }
            });

            thread.start();
        }
    }
}

示例说明

下面是一个示例说明两种解决方案的区别和问题：

假设有6个哲学家（0-5号），围坐在一张圆桌前。

在线程同步方案中，如果所有哲学家都同时进行startEating操作，那么会导致程序卡住。因为所有哲学家都需要同时获取左右两只筷子才能开始用餐，但只有5只筷子，必然会发生死锁。

而在资源层次分配法中，由于每个哲学家必须按照编号从小到大依次获取筷子，因此不会发生死锁。但是，当某个哲学家用餐时间过长，其他哲学家被阻塞，无法进餐，这种情况称为“饥饿”（Starvation）。

因此，无论是哪种解决方案，都只是一种权衡。线程同步方案避免了饥饿，但可能会产生死锁；而资源层次分配法可以避免死锁，但可能会产生饥饿。适合哪种方案取决于实际应用场景和需求。