死锁和饥饿-哲学家就餐问题

哲学家就餐问题

  • 背景:
  1. 假设5位哲学家住在一起(可以推广到n),每天生活就是思考和吃饭,每位哲学家需要2把叉子来吃意大利面.
  2. 就餐安排: 一张圆桌,5个板凳,5个盘子,5把叉子,每个想吃饭的哲学家做到椅子上,使用盘子2侧的叉子来吃面条,
  3. 问题: 设计算法 保证互斥(2位哲学家不能使用相邻的叉子),同时还要避免死锁(每个哲学家都在等待叉子,且占用了叉子)和饥饿

问题图片

信号量解决方案

  • 规定: 每位哲学家首先拿起左边的叉子,然后拿起右边的叉子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
semaphore fork[5] = {1};
int i;
void philosopher (int i) {
    while (true) {
        think();
        wait(fork[i]); //等待左边的叉子
        wait(fork[(i+1) % 5]; // 等待右边的叉子
        eat();
        signal(fork[(i+1) % 5]); // 放回右边的叉子
        signal(fork[i]; //放回左边的叉子 (增加信号量)
    }
}
void mian() {
	parbegin(philosopher(0),philosopher(1).....philosopher(4));   
}
  • 此方案会导致死锁: 所有哲学家同时坐下来,都拿起左边的叉子,都去伸手拿右边的叉子,却都没有拿到
对上面死锁危险的解决方案:
  1. 再增加5把叉子,
  2. 哲学家学会只使用一把叉子吃面
  3. 增加服务员： 限制每次最多只能4个哲学家坐下来,那么至少有一个哲学家能够拿到2把叉子

增加服务员方案

  • 一个信号量room表示 : 限制每次哲学家同时坐下的数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semaphore fork[5] = {1};
semaphore room = 4;
int i;
void philosopher (int i) {
	while (true) {
        think();
        wait(room);
        wait(fork[i]);
        wait(fork[(i+1) % 5]);
        eat();
        signal(fork[(i+1) % 5]);
        signal(fork[i]);
        signal(room);
    }
}
void main() {
    parbegin(philosopher(0),philosopher(1).....philosopher(4));
}

基于管程的解决方案

  1. 定义 5个管程的条件变量, 每把叉子对应一个条件变量,用来标识哲学家 等待 的叉子可用情况,

  2. 开一个bool数组记录每把叉子是否可用(true/false)

  3. 管程包含2个过程：

    1. get_forks : 表示取哲学家左右的叉子, 如果至少有1把不可以用,那么在条件变量队列中等待,使得其他哲学家进程进入管程
    2. release_forks : 标识2把叉子可用

  4. 与信号量方案类似,都是首先拿起左边的叉子,然后拿起右边的叉子

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
monitor dining_controller; // 声明管程
cron ForkReady[5];  //  管程的条件变量
bool fork[5] = {true}; // 标记叉子是否可用

void get_forks(int pid) { // pid既代表哲学家又代表叉子
    int left = pid;
    int right = (pid + 1) % 5;
    if (!fork[left]) // 左边叉子被使用,则等待条件变量
        cwait(ForkReady[left]);
    fork[left] = false;//左边叉子现在可以归我们用了,再次标记为不能用
    if (!fork[right])
        cwait(ForkReady[right]);
    fork[right] = false;
}

void release_forks(int pid) {
    int left = pid;
    int right= (pid + 1) % 5;
    if (empty(ForkReady[left])) // 没有哲学家在该队列上等待,则该叉子可以使用
        fork[left] = true;
    else //如果还有等待,增加信号量
        csignal(ForkReady[left]);
    /* 释放右边的叉子 */
    if (empty(ForkReady[right]))
        fork[right] = true;
    else
        csignal(ForkReady[right]);
}

void philosopher(int i) {
    while (true) {
        think();
        get_forks(i);
        eat();
        release_forks(i);
    }
}
void main() {
	parbegin(philosopher(0),philosopher(1).....philosopher(4));
}