408 操作系统

Appearance

哲学家进餐问题 ​

考情分析 ​

哲学家进餐问题是死锁和同步的经典例题，408 真题中偶有考查。属于 🔥🔥 中高频考点。

前面的同步问题中，每个进程只需要一种资源。但如果每个进程需要同时持有两种资源才能工作，而资源又是共享的——就像五个人围着火锅，每人需要两根筷子才能吃菜——经典的死锁场景就出现了。

问题描述 ​

5 个哲学家围坐在圆桌旁，桌上有 5 根筷子，每两个哲学家之间放一根。哲学家交替进行思考和进餐。

进餐时需要同时拿起左右两根筷子，用完后放回。

        P0
    C4      C0
  P4          P1
    C3      C1
        P2
        C2

每根筷子是一个信号量：

semaphore chopstick[5] = {1, 1, 1, 1, 1};

朴素方案（有死锁风险） ​

philosopher(i) {
    while (true) {
        think();
        P(chopstick[i]);           // 拿左边的筷子
        P(chopstick[(i+1) % 5]);   // 拿右边的筷子
        eat();
        V(chopstick[i]);           // 放左边的筷子
        V(chopstick[(i+1) % 5]);   // 放右边的筷子
    }
}

死锁场景：5 个哲学家同时拿起左边的筷子 → 所有人都在等右边的筷子 → 没有人能吃到饭 → 死锁。

解决方案 ​

方案一：限制人数 ​

最多允许 4 个哲学家同时拿筷子：

semaphore limit = 4;    // 最多 4 人同时尝试拿筷子

philosopher(i) {
    think();
    P(limit);                      // 限制人数
    P(chopstick[i]);
    P(chopstick[(i+1) % 5]);
    eat();
    V(chopstick[i]);
    V(chopstick[(i+1) % 5]);
    V(limit);
}

方案二：奇偶策略 ​

  • 奇数号哲学家：先拿左边，再拿右边
  • 偶数号哲学家：先拿右边，再拿左边
philosopher(i) {
    think();
    if (i % 2 == 1) {              // 奇数号
        P(chopstick[i]);           // 先左后右
        P(chopstick[(i+1) % 5]);
    } else {                       // 偶数号
        P(chopstick[(i+1) % 5]);   // 先右后左
        P(chopstick[i]);
    }
    eat();
    V(chopstick[i]);
    V(chopstick[(i+1) % 5]);
}

破坏了循环等待条件，因为相邻哲学家拿筷子的顺序不同。

方案三：同时拿两根 ​

用一个互斥信号量保证「拿两根筷子」是原子操作：

semaphore mutex = 1;

philosopher(i) {
    think();
    P(mutex);
    P(chopstick[i]);
    P(chopstick[(i+1) % 5]);
    V(mutex);
    eat();
    V(chopstick[i]);
    V(chopstick[(i+1) % 5]);
}

缺点：一次只有一个哲学家能尝试拿筷子，并发度降低。

交互可视化 ​

加载可视化中...

三种方案对比 ​

方案避免死锁的原理并发度
限制人数破坏「循环等待」（最多4人）较高
奇偶策略破坏「循环等待」（拿筷子顺序不同）最高
同时拿两根破坏「请求并保持」最低

考研高频考点 ​

  • 🔥🔥🔥 朴素方案为什么会死锁
  • 🔥🔥🔥 三种解决方案的 PV 操作写法
  • 🔥🔥 各方案分别破坏了死锁的哪个必要条件
  • 🔥 哲学家问题本质是死锁问题的体现

哲学家进餐问题是死锁的经典演示。下一篇系统地讨论死锁的定义、必要条件和预防策略。

相关文章

真题练习 ​

相关真题（1题）

2019Q43综合题8分
可视化详解

综合题：带碗限制的哲学家进餐问题，需防止死锁

哲学家进餐死锁概念信号量