2019 408 真题解答

🧑‍💻 作者: 一可爱小白兔

📦 版本: 1.0.0

📄 字数(字): 0

⏳ 时长(min): 0

⏱️ 更新于: 2026-01-08

问题描述

有 n（n ≥ 3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m（m ≥ 1）个碗，每两位哲学家之间有一根筷子。
每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。
为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的 P、V 操作（wait()、signal() 操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

问题分析

• 哲学家的编号从 0 到 n-1，每道哲学家的编号对应一个筷子，哲学家的编号和筷子的编号一一对应。
• 通过限制碗的资源来满足哲学家就餐的资源需求：如果碗的数量 m 小于哲学家的数量 n,则可以直接让碗的资源量等于 m; 如果碗的数量 m 大于哲学家的数量 n，则将碗的资源量设置为 n-1。

伪代码

semaphore chopsticks[n] = {1, 1, 1, 1, 1, ...};  // 互斥信号量，表示对每根筷子的互斥访问，初值为1
semaphore plant = min{m, n-1};                   // 同步信号量，表示可用的碗的资源量，初值为m或n-1

cobegin
pi() {
    while(1) {
        P(plant);                                // 获取碗
        P(chopstick[i]);                         // 拿起左边筷子
        P(chopstick[(i + 1) % n]);               // 拿起右边筷子
        eat;
        V(chopstick[i]);                         // 放下左边筷子
        V(chopstick[(i + 1) % n]);               // 放下右边筷子
        V(plant);                                // 释放碗
        think;
    }
}
coend