基于mutex锁的哲学家就餐问题饥饿问题高效解决方案咨询

现有代码饥饿原因 #

你当前的实现虽然解决了死锁问题，但存在饥饿风险的核心原因是：归还筷子时仅唤醒左右邻居，没有对饥饿哲学家的等待顺序做约束，极端情况下会出现相邻哲学家交替抢占就餐资源，中间哲学家永远无法满足就餐条件的问题。

最高效解决方案：FIFO等待队列机制 #

该方案在原有代码逻辑基础上仅增加轻量的等待队列逻辑，所有操作都在原有互斥锁的临界区内完成，无额外同步开销，能100%避免饥饿，是改造成本和运行效率最优的方案。

方案原理 #

1. 新增一个先进先出的等待队列，所有申请资源失败的饥饿哲学家按顺序加入队列尾部
2. 哲学家归还筷子后，优先按队列顺序检查队首的饥饿哲学家是否满足就餐条件，满足则唤醒出队，直到队首不满足条件为止
3. 严格保证先进入饥饿状态的哲学家优先获得就餐权限，避免插队

代码修改示例 #

1. 修改dp.h，新增队列相关定义

/*Header file for dining philosophers*/
 
#include <pthread.h>
 
// 哲学家数量
#define NUMBER      5
 
// 新增：等待队列最大长度
#define WAIT_QUEUE_SIZE NUMBER

// 最长休眠时间（秒）
#define MAX_SLEEP_TIME  5
 
// 哲学家状态：思考、饥饿、就餐
enum {THINKING, HUNGRY, EATING} state[NUMBER];
 
// 哲学家线程ID（0 ~ NUMBER-1）
int thread_id[NUMBER];
 
// 条件变量与关联互斥锁
pthread_cond_t      cond_vars[NUMBER];
pthread_mutex_t     mutex_lock;

// 新增：FIFO等待队列相关变量
int wait_queue[WAIT_QUEUE_SIZE];
int q_head = 0, q_tail = 0, q_len = 0;
 
void *philosopher(void *param);

2. 修改dining.c中的pickup_forks函数

void pickup_forks(int number)
{
    pthread_mutex_lock(&mutex_lock);
 
    state[number] = HUNGRY;
    test(number);
 
    while (state[number] != EATING) {
        // 申请失败则加入等待队列尾部
        if(q_len < WAIT_QUEUE_SIZE) {
            wait_queue[q_tail] = number;
            q_tail = (q_tail + 1) % WAIT_QUEUE_SIZE;
            q_len++;
        }
        pthread_cond_wait(&cond_vars[number], &mutex_lock);
    }
 
    pthread_mutex_unlock(&mutex_lock);
}

3. 修改dining.c中的return_forks函数

void return_forks(int number)
{
    pthread_mutex_lock(&mutex_lock);
 
    state[number] = THINKING;
    
    // 按等待顺序优先唤醒队列中满足条件的哲学家
    int check_cnt = q_len;
    for(int i=0; i<check_cnt && q_len >0; i++) {
        int curr_wait = wait_queue[q_head];
        test(curr_wait);
        if(state[curr_wait] == EATING) {
            // 满足就餐条件，出队
            q_head = (q_head + 1) % WAIT_QUEUE_SIZE;
            q_len--;
        } else {
            // 队首不满足条件，后续等待者优先级更低，直接退出
            break;
        }
    }
 
    pthread_mutex_unlock(&mutex_lock);
}

方案优势 #

• 运行效率极高：所有队列操作都是O(1)复杂度，且完全复用原有互斥锁保护，无额外同步开销
• 改造成本极低：仅修改3处代码，完全兼容原有逻辑架构
• 彻底避免饥饿：严格遵循先到先得的调度规则，不存在哲学家无限等待的可能

内容的提问来源于stack exchange，提问作者seraabrj