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

哲学家就餐问题

• 背景:

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

信号量解决方案

• 规定: 每位哲学家首先拿起左边的叉子,然后拿起右边的叉子

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表示 : 限制每次哲学家同时坐下的数量

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. 与信号量方案类似,都是首先拿起左边的叉子,然后拿起右边的叉子

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));
}