经典进程同步问题——哲学家进餐问题

发表于 更新于 分类于 阅读次数： 本文字数： 6k 阅读时长 ≈ 5 分钟
哲学家进餐问题是进程间竞争临界资源而导致死锁的典型例子，具有很大的代表性，本文提供java实现代码。

经典进程同步问题——哲学家进餐问题

1. 问题描述

有五个哲学家围在一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和物质筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕后，放下筷子继续思考。

我们可以从上面的题目中得出，筷子是临界资源，同一根筷子同一时刻只能有一个哲学家可以拿到。

2. 问题分析

由问题描述我们可以知道，一共有五个哲学家，也就是五个进程；五只筷子，也就是五个临界资源；因为哲学家想要进餐，必须要同时获得左边和右边的筷子，这就是要同时进入两个临界区（使用临界资源），才可以进餐。

3. 信号量设置

因为是五只筷子为临界资源，因此设置五个信号量即可。

4. 一个错误例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量

void philosopher(int i){
  do {
    //thinking			//思考
    P(mutex[i]);//判断哲学家左边的筷子是否可用
    P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
    //...
    //eat		//进餐
    //...
    V(mutex[i]);//退出临界区，允许别的进程操作缓冲池
    V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程
  }while(true);
}

我们来分析下上面的代码，首先我们从一个哲学家的角度来看问题，程序似乎是没有问题的，申请到左右两支筷子后，然后开始进餐。但是如果考虑到并发问题，五个哲学家同时拿起了左边的筷子，此时，五只筷子立刻都被占用了，没有可用的筷子了，当所有的哲学家再想拿起右边筷子的时候，因为临界资源不足，只能将自身阻塞，而所有的哲学家全部都会阻塞，并且不会释放自己手中拿着的左边的筷子，因此就会一直处于阻塞状态，无法进行进餐并思考。

因为，为了解决五个哲学家争用的资源的问题，我们可以采用以下几种解决方法：

  • 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用餐完毕后能释放他占用的筷子，从而使别的哲学家能够进餐；
  • 仅当哲学家的左、右两支筷子可用时，才允许他拿起筷子；
  • 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。

下面我们对每种方法给出哲学家进程的伪代码。

5. 解决哲学家进餐问题——方法一

对于方法一，至多只允许有四位哲学家同时去拿左边的筷子，我们可以简单的通过增加一个信号量实现，通过这个信号量限定哲学家并发去进餐的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量
semaphore count = 4;	//控制最多允许四位哲学家同时进餐

void philosopher(int i){
  do {
    //thinking		//思考
    p(count);		//判断是否超过四人准备进餐
    P(mutex[i]);	//判断缓冲池中是否仍有空闲的缓冲区
    P(mutex[(i+1)%5]);//判断是否可以进入临界区（操作缓冲池）
    //...
    //eat			//进餐
    //...
    V(mutex[i]);//退出临界区，允许别的进程操作缓冲池
    V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程
    V(count);//用餐完毕，别的哲学家可以开始进餐
  }while(true);
}

6. 解决哲学家进餐问题——方法二

第二种方法，也就是使用AND型信号量，同时对哲学家左右两边的筷子同时申请。下面是伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量

void philosopher(int i){
  do {
    //thinking		//思考
    Swait(mutex[i], mutex[(i+1)%5]);//判断哲学家左边和右边的筷子是否同时可用
    //...
    //eat		
    //...
    Ssignal(mutex[i], mutex[(i+1)%5]);//进餐完毕，释放哲学家占有的筷子
  }while(true);
}

7. 解决哲学家进餐问题——方法三

对于第三种，需要在代码中添加个判断，来决定获取左、右筷子的顺序，其伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量

void philosopher(int i){
  do {
    //thinking	
    if(i%2 == 1){
      P(mutex[i]);//判断哲学家左边的筷子是否可用
      P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
    }else{
      P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
      P(mutex[i]);//判断哲学家左边的筷子是否可用
    }
    //...
    //eat
    //...
    V(mutex[i]);//退出临界区，允许别的进程操作缓冲池
    V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程
  }while(true);
}

8. Java测试

1) 方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package philosopher;

import java.util.concurrent.Semaphore;

/**
 * Created by mzYan on 2020-01-27 16:31
 */
public class PhilosophersTest1 {
    static final Semaphore count = new Semaphore(4);
    static final Semaphore[] mutex = {new Semaphore(1),
            new Semaphore(1),new Semaphore(1),
            new Semaphore(1), new Semaphore(1)};

    static class Philosopher extends Thread {
        Philosopher(String name){
            super.setName(name);
        }

        void eat() {
            try {
                System.out.println("哲学家【" + super.getName() + "】号吃通心粉...");
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        void think() {
            try {
                System.out.println("哲学家【" + super.getName() + "】号开始思考...");
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        void getChops() {
            try {
                count.acquire();
                Integer i = Integer.parseInt(super.getName());
                mutex[i].acquire();
                mutex[(i+1)%5].acquire();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        void putChops() {
            Integer i = Integer.parseInt(super.getName());
            mutex[i].release();
            mutex[(i+1)%5].release();
            count.release();
        }

        @Override
        public void run() {
            while(true){
                getChops();
                eat();
                putChops();
                think();
            }
        }
    }

    public static void main(String[] args) {
        Philosopher p0 = new Philosopher("0");
        Philosopher p1 = new Philosopher("1");
        Philosopher p2 = new Philosopher("2");
        Philosopher p3 = new Philosopher("3");
        Philosopher p4 = new Philosopher("4");

        p0.start();
        p1.start();
        p2.start();
        p3.start();
        p4.start();
    }
}

2） 方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package philosopher;

import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * Created by mzYan on 2020-01-27 16:31
 */
public class PhilosophersTest2 {
    static final Semaphore[] mutex = {new Semaphore(1),
            new Semaphore(1),new Semaphore(1),
            new Semaphore(1), new Semaphore(1)};

    static Lock lock = new ReentrantLock();
    static Condition condition = lock.newCondition();


    static class Philosopher extends Thread {
        Philosopher(String name){
            super.setName(name);
        }

        void eat() {
            try {
                System.out.println("哲学家【" + super.getName() + "】号吃通心粉...");
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        void think() {
            try {
                System.out.println("哲学家【" + super.getName() + "】号开始思考...");
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        void getChops() {
            Integer i = Integer.parseInt(super.getName());
            try {
                lock.lock();
                while (mutex[i].availablePermits() < 1 || mutex[(i+1)%5].availablePermits() < 1) {
                    condition.await();
                }
                mutex[i].acquire();
                mutex[(i+1)%5].acquire();
            } catch (InterruptedException e){
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }

        void putChops() {
            Integer i = Integer.parseInt(super.getName());
            lock.lock();
            mutex[i].release();
            mutex[(i+1)%5].release();
            condition.signalAll();
            lock.unlock();
        }

        @Override
        public void run() {
            while(true) {
                getChops();
                eat();
                putChops();
                think();
            }
        }
    }

    public static void main(String[] args) {
        Philosopher p0 = new Philosopher("0");
        Philosopher p1 = new Philosopher("1");
        Philosopher p2 = new Philosopher("2");
        Philosopher p3 = new Philosopher("3");
        Philosopher p4 = new Philosopher("4");

        p0.start();
        p1.start();
        p2.start();
        p3.start();
        p4.start();
    }
}