哲学家就餐问题

发表于 更新于 分类于 ，

一、历史背景

哲学家就餐问题由荷兰计算机科学家艾兹格·迪科斯彻于1965年提出。他最初用来讨论计算机系统中的资源竞争问题，特别是磁带驱动器之类的设备。

后来，英国计算机科学家托尼·霍尔（他也是Quicksort算法的发明者和图灵奖得主）在1971年的一篇文章中，使用了“哲学家”这个更生动、更易于理解的比喻来重新表述了这个问题。自此，这个带着哲学思辨色彩的故事，成为了计算机科学中讲解并发控制、死锁和资源分配时最经典、最著名的案例。

它的出现和发展，正值操作系统从批处理转向多道程序设计和分时系统，如何安全高效地管理多个进程对有限资源的竞争，成为一个亟待解决的核心问题。

二、问题描述

想象一个场景：五位哲学家围坐在一张圆桌旁，他们的生活方式只有两种状态：思考和就餐。

  • 角色：五位哲学家（P1, P2, P3, P4, P5）。
  • 资源：五支筷子（F1, F2, F3, F4, F5）。筷子被摆放在哲学家之间，每两位哲学家中间放一支。因此，每位哲学家的左边和右边都各有一支筷子。
  • 规则：
    1. 当哲学家思考时，他不影响他人。
    2. 当哲学家感到饥饿时，他必须尝试拿起他左边和右边的两支筷子才能开始就餐。
    3. 一次只能拿起一支筷子，且筷子是排他性的，即一支筷子在同一时刻只能被一位哲学家使用。
    4. 就餐结束后，哲学家会同时放下两支筷子，然后继续思考。

1

三、问题的核心

这个看似简单的场景，精准地模拟了计算机中多个进程（哲学家）竞争使用有限资源（筷子）的情形。其核心在于，如果不对进程的行为进行正确的同步协调，就会导致系统性的故障。最主要的问题是死锁。

死锁是如何发生的？

让我们看一个最直接的（也是错误的）实现流程：
每位哲学家循环执行以下步骤：

  1. 拿起左边的筷子。
  2. 拿起右边的筷子。
  3. 就餐。
  4. 放下右边的筷子。
  5. 放下左边的筷子。

死锁场景：
假设在某一时刻，所有五位哲学家同时感到饥饿，并几乎同时执行了第一步：每人都成功拿起了自己左边的筷子。
现在，桌面上所有筷子都被拿走了。紧接着，每位哲学家都试图去拿自己右边的筷子，但他们右边的筷子正被其右边的哲学家紧紧握在手中。
于是，出现了这样的局面：

  • P1 拿着 F1，等待 F2（被 P2 拿着）
  • P2 拿着 F2，等待 F3（被 P3 拿着）
  • P3 拿着 F3，等待 F4（被 P4 拿着）
  • P4 拿着 F4，等待 F5（被 P5 拿着）
  • P5 拿着 F5，等待 F1（被 P1 拿着）

所有人都在等待别人释放资源，但没有人能向前推进。系统陷入了永久的停滞，这就是死锁。

无解决方案的代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>
#include <time.h>

#define NUM_PHILOSOPHERS 5

// 定义信号量数组，代表5支筷子
sem_t chopsticks[NUM_PHILOSOPHERS];
int philosopher_ids[NUM_PHILOSOPHERS];

// 思考函数
void think(int philosopher_id) {
    printf("哲学家 %d 正在思考...\n", philosopher_id);
    usleep(rand() % 300000 + 100000); // 随机思考时间
    printf("哲学家 %d 感到饥饿了\n", philosopher_id);
}

// 就餐函数
void eat(int philosopher_id) {
    printf("哲学家 %d 开始就餐\n", philosopher_id);
    usleep(rand() % 200000 + 100000); // 随机就餐时间
    printf("哲学家 %d 结束就餐\n", philosopher_id);
}

// 哲学家线程函数 - 完全按照伪代码实现
void* philosopher(void* num) {
    int id = *(int*)num;
    
    while(1) {
        think(id);
        
        // P(chopstick[i]) - 取左边筷子
        sem_wait(&chopsticks[id]);
        printf("哲学家 %d 拿起了左边筷子\n", id);
        
        // P(chopstick[(i+1)%5]) - 取右边筷子
        sem_wait(&chopsticks[(id + 1) % NUM_PHILOSOPHERS]);
        printf("哲学家 %d 拿起了右边筷子\n", id);
        
        // eat - 就餐
        eat(id);
        
        // V(chopstick[i]) - 放回左边筷子
        sem_post(&chopsticks[id]);
        
        // V(chopstick[(i+1)%5]) - 放回右边筷子
        sem_post(&chopsticks[(id + 1) % NUM_PHILOSOPHERS]);
        printf("哲学家 %d 放回了筷子\n", id);
    }
    
    return NULL;
}

int main() {
    pthread_t philosophers[NUM_PHILOSOPHERS];
    
    srand(time(NULL));
    
    printf("=== 哲学家就餐问题纯粹模拟 ===\n");
    printf("完全按照原始伪代码实现，无任何额外机制\n");
    printf("注意：程序可能会陷入死锁并永远等待\n\n");
    
    // 初始化信号量（筷子），初始值为1
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        sem_init(&chopsticks[i], 0, 1);
        philosopher_ids[i] = i;
    }
    
    // 创建哲学家线程
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_ids[i]);
    }
    
    // 等待所有哲学家线程（实际上可能会永远等待）
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_join(philosophers[i], NULL);
    }
    
    return 0;
}

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
semaphore chopstick[5] = {1,1,1,1,1}  // 5支筷子，初始都可用

process Philosopher(i) {  // i = 0 到 4
    while (true) {
        think();           // 思考
        hungry();          //饥饿
        P(chopstick[i]);   // 拿左边筷子
        P(chopstick[(i+1)%5]); // 拿右边筷子
        eat();             // 就餐
        V(chopstick[i]);   // 放左边筷子
        V(chopstick[(i+1)%5]); // 放右边筷子
    }
}

四、解决方案

先看死锁的四个必要条件：

  1. 互斥条件 (Mutual Exclusion)
  2. 占有并等待 (Hold and Wait)
  3. 不可剥夺 (No Preemption)
  4. 循环等待 (Circular Wait)

解决方案一

破坏的条件：占有并等待

只允许哲学家能够同时拿到左右两边的筷子时，他才去拿筷子,

打破了对临界资源“筷子”的“占有且等待” 条件，从而避免了死锁。

为了实现这一点，我们需要一个全局的互斥锁，来确保在检查筷子可用性并获取筷子的过程中，不会有其他哲学家同时进行干扰。

伪代码

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
semaphore chopstick[5] = {1,1,1,1,1}
semaphore mutex = 1

Pi() {
    while(1) {
        think()
        
        // 检查并获取筷子
        success = false
        while (!success) {
            P(mutex)                    // 进入临界区
            if (chopstick[i] > 0 && chopstick[(i+1)%5] > 0) {
                P(chopstick[i])         // 拿左边筷子
                P(chopstick[(i+1)%5])   // 拿右边筷子
                success = true
            }
            V(mutex)                    // 离开临界区
            
            if (!success) wait()        // 条件不满足，等待后重试
        }
        
        eat()
        
        V(chopstick[i])                 // 放回左边筷子
        V(chopstick[(i+1)%5])           // 放回右边筷子
    }
}

源码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>
#include <time.h>

#define NUM_PHILOSOPHERS 5

// 定义信号量数组，代表5支筷子
sem_t chopsticks[NUM_PHILOSOPHERS];
sem_t mutex; // 全局互斥锁，用于保护筷子状态的检查和获取
int philosopher_ids[NUM_PHILOSOPHERS];

// 思考函数
void think(int philosopher_id) {
    printf("哲学家 %d 正在思考...\n", philosopher_id);
    usleep(rand() % 300000 + 100000); // 随机思考时间
    printf("哲学家 %d 感到饥饿了\n", philosopher_id);
}

// 就餐函数
void eat(int philosopher_id) {
    printf("哲学家 %d 开始就餐\n", philosopher_id);
    usleep(rand() % 200000 + 100000); // 随机就餐时间
    printf("哲学家 %d 结束就餐\n", philosopher_id);
}

// 哲学家线程函数
void* philosopher(void* num) {
    int id = *(int*)num;
    int left_chopstick = id;
    int right_chopstick = (id + 1) % NUM_PHILOSOPHERS;
    
    while(1) {
        think(id);
        
        // 只有当左右筷子都可用时才拿起筷子
        int success = 0;
        while (!success) {
            // 进入临界区 - 保护检查和拿取筷子的原子操作
            sem_wait(&mutex);
            
            // 原子操作：检查筷子可用性并获取筷子
            int chopstick_values[2];
            sem_getvalue(&chopsticks[left_chopstick], &chopstick_values[0]);
            sem_getvalue(&chopsticks[right_chopstick], &chopstick_values[1]);
            
            // 如果左右筷子都可用，则同时拿起
            if (chopstick_values[0] > 0 && chopstick_values[1] > 0) {
                sem_wait(&chopsticks[left_chopstick]);
                sem_wait(&chopsticks[right_chopstick]);
                success = 1;
                printf("哲学家 %d 同时拿起了左右筷子\n", id);
            }
            
            // 离开临界区
            sem_post(&mutex);
            
            // 如果无法同时拿到两支筷子，等待后重试
            if (!success) {
                usleep(rand() % 100000 + 50000);
            }
        }
        
        // 就餐
        eat(id);
        
        // 放回筷子
        sem_post(&chopsticks[left_chopstick]);
        sem_post(&chopsticks[right_chopstick]);
        printf("哲学家 %d 放回了筷子\n", id);
    }
    
    return NULL;
}

int main() {
    pthread_t philosophers[NUM_PHILOSOPHERS];
    
    srand(time(NULL));
    
    printf("=== 哲学家就餐问题模拟 ===\n");
    printf("解决方案：只有当左右筷子都可用时才拿起筷子\n");
    printf("核心机制：使用互斥锁确保检查和拿取筷子的原子性\n\n");
    
    // 初始化信号量（筷子），初始值为1，表示可用
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        sem_init(&chopsticks[i], 0, 1);
        philosopher_ids[i] = i;
    }
    
    // 初始化互斥锁
    sem_init(&mutex, 0, 1);
    
    // 创建哲学家线程
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_ids[i]);
    }
    
    // 等待所有哲学家线程（实际上会永远运行）
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_join(philosophers[i], NULL);
    }
   
    
    return 0;
}

解决方案二：

破坏的条件：循环等待

基于并发进程资源分配的理论分析，通过限制同时就餐的哲学家数量来避免死锁。

核心思想
根据系统资源分配的理论断言：

系统中有N个并发进程，每个进程需要申请R个某类资源

当系统提供K = N×(R-1)+1个同类资源时，一定不会发生死锁

在哲学家就餐问题中：

N个哲学家进程，每个需要2支筷子（R=2）

系统提供5支筷子（K=5）

代入公式：N×(2-1)+1 = 5 ⇒ N = 4

结论：在任何时刻，最多只允许4个哲学家同时尝试就餐，就能保证系统不会发生死锁。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semaphore chopstick[5] = {1,1,1,1,1}  // 5支筷子
semaphore limit = 4                     // 最多允许4个哲学家同时就餐

Pi() { // i号哲学家的进程
    while(1) {
        think()
        
        P(limit)           // 申请就餐权限
        P(chopstick[i])    // 拿左边筷子
        P(chopstick[(i+1)%5]) // 拿右边筷子
        
        eat()
        
        V(chopstick[i])    // 放回左边筷子
        V(chopstick[(i+1)%5]) // 放回右边筷子
        V(limit)           // 释放就餐权限
    }
}

源码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>
#include <time.h>

#define NUM_PHILOSOPHERS 5
#define MAX_EATERS 4

// 定义信号量数组，代表5支筷子
sem_t chopsticks[NUM_PHILOSOPHERS];
sem_t eater_limit; // 限制同时就餐的哲学家数量
int philosopher_ids[NUM_PHILOSOPHERS];

// 思考函数
void think(int philosopher_id) {
    printf("哲学家 %d 正在思考...\n", philosopher_id);
    usleep(rand() % 300000 + 100000); // 随机思考时间
    printf("哲学家 %d 感到饥饿了\n", philosopher_id);
}

// 就餐函数
void eat(int philosopher_id) {
    printf("哲学家 %d 开始就餐\n", philosopher_id);
    usleep(rand() % 200000 + 100000); // 随机就餐时间
    printf("哲学家 %d 结束就餐\n", philosopher_id);
}

// 哲学家线程函数
void* philosopher(void* num) {
    int id = *(int*)num;
    
    while(1) {
        think(id);
        
        // 申请就餐权限（最多允许4个哲学家同时就餐）
        sem_wait(&eater_limit);
        
        // 取左边筷子
        sem_wait(&chopsticks[id]);
        printf("哲学家 %d 拿起了左边筷子\n", id);
        
        // 取右边筷子
        sem_wait(&chopsticks[(id + 1) % NUM_PHILOSOPHERS]);
        printf("哲学家 %d 拿起了右边筷子\n", id);
        
        // 就餐
        eat(id);
        
        // 放回左边筷子
        sem_post(&chopsticks[id]);
        
        // 放回右边筷子
        sem_post(&chopsticks[(id + 1) % NUM_PHILOSOPHERS]);
        printf("哲学家 %d 放回了筷子\n", id);
        
        // 释放就餐权限
        sem_post(&eater_limit);
    }
    
    return NULL;
}

int main() {
    pthread_t philosophers[NUM_PHILOSOPHERS];
    
    srand(time(NULL));
    
    printf("=== 哲学家就餐问题 - 解决方案二 ===\n");
    printf("资源限制法：最多允许4个哲学家同时就餐\n\n");
    
    // 初始化信号量（筷子），初始值为1
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        sem_init(&chopsticks[i], 0, 1);
        philosopher_ids[i] = i;
    }
    
    // 初始化就餐限制信号量，最多允许4个哲学家同时就餐
    sem_init(&eater_limit, 0, MAX_EATERS);
    
    // 创建哲学家线程
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_ids[i]);
    }
    
    // 等待所有哲学家线程（实际上可能会永远等待）
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_join(philosophers[i], NULL);
    }
    
    return 0;
}

解决方案三：

破坏的条件：循环等待

通过为奇数和偶数编号的哲学家设定不同的拿筷子顺序来打破循环等待。

核心思想

规定奇数号哲学家和偶数号哲学家采用不同的拿筷子顺序：

  • 奇数号哲学家：先拿左边筷子，再拿右边筷子
  • 偶数号哲学家：先拿右边筷子，再拿左边筷子

这样安排使得哲学家们竞争的资源顺序不同，从而破坏了循环等待的条件。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
semaphore chopstick[5] = {1,1,1,1,1}  // 5支筷子

Pi() { // i号哲学家的进程
    while(1) {
        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])    // 放回右边筷子
    }
}

源码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>
#include <time.h>

#define NUM_PHILOSOPHERS 5

// 定义信号量数组，代表5支筷子
sem_t chopsticks[NUM_PHILOSOPHERS];
int philosopher_ids[NUM_PHILOSOPHERS];

// 思考函数
void think(int philosopher_id) {
    printf("哲学家 %d 正在思考...\n", philosopher_id);
    usleep(rand() % 300000 + 100000); // 随机思考时间
    printf("哲学家 %d 感到饥饿了\n", philosopher_id);
}

// 就餐函数
void eat(int philosopher_id) {
    printf("哲学家 %d 开始就餐\n", philosopher_id);
    usleep(rand() % 200000 + 100000); // 随机就餐时间
    printf("哲学家 %d 结束就餐\n", philosopher_id);
}

// 哲学家线程函数
void* philosopher(void* num) {
    int id = *(int*)num;
    int left = id;
    int right = (id + 1) % NUM_PHILOSOPHERS;
    
    while(1) {
        think(id);
        
        // 奇数号哲学家先左后右，偶数号哲学家先右后左
        if (id % 2 == 1) {
            // 奇数号哲学家：先拿左边筷子，再拿右边筷子
            sem_wait(&chopsticks[left]);
            printf("哲学家 %d (奇数)拿起了左边筷子\n", id);
            
            sem_wait(&chopsticks[right]);
            printf("哲学家 %d (奇数)拿起了右边筷子\n", id);
        } else {
            // 偶数号哲学家：先拿右边筷子，再拿左边筷子
            sem_wait(&chopsticks[right]);
            printf("哲学家 %d (偶数)拿起了右边筷子\n", id);
            
            sem_wait(&chopsticks[left]);
            printf("哲学家 %d (偶数)拿起了左边筷子\n", id);
        }
        
        // 就餐
        eat(id);
        
        // 放回筷子
        sem_post(&chopsticks[left]);
        sem_post(&chopsticks[right]);
        printf("哲学家 %d 放回了筷子\n", id);
    }
    
    return NULL;
}

int main() {
    pthread_t philosophers[NUM_PHILOSOPHERS];
    
    srand(time(NULL));
    
    printf("=== 哲学家就餐问题 - 解决方案三 ===\n");
    printf("奇偶顺序法：奇数先左后右，偶数先右后左\n\n");
    
    // 初始化信号量（筷子），初始值为1
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        sem_init(&chopsticks[i], 0, 1);
        philosopher_ids[i] = i;
    }
    
    // 创建哲学家线程
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_ids[i]);
    }
    
    // 等待所有哲学家线程（实际上可能会永远等待）
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_join(philosophers[i], NULL);
    }
    
    return 0;
}

解决方案四：

破坏的条件：占有并等待

采用AND型信号量机制，要求哲学家同时获得左右两边的筷子才能开始就餐。

核心思想
使用AND型信号量（同时申请多个资源）机制，哲学家必须同时申请左右两边的筷子。如果无法同时获得两支筷子，则等待，直到两支筷子都可用时才一起获取。

伪代码

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
semaphore chopstick[5] = {1,1,1,1,1}  // 5支筷子
semaphore mutex = 1                     // 保护AND操作

// AND型信号量操作
procedure AND_WAIT(i) {
    while(true) {
        P(mutex)                        // 进入临界区
        
        if (chopstick[i] > 0 && chopstick[(i+1)%5] > 0) {
            P(chopstick[i])             // 同时获取左筷子
            P(chopstick[(i+1)%5])       // 同时获取右筷子
            V(mutex)                    // 离开临界区
            return
        }
        
        V(mutex)                        // 离开临界区
        wait()                          // 等待后重试
    }
}

Pi() { // i号哲学家的进程
    while(1) {
        think()
        
        AND_WAIT(i)                     // 同时申请左右筷子
        
        eat()
        
        V(chopstick[i])                 // 放回左筷子
        V(chopstick[(i+1)%5])           // 放回右筷子
    }
}

源码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>
#include <time.h>

#define NUM_PHILOSOPHERS 5

// 定义信号量数组，代表5支筷子
sem_t chopsticks[NUM_PHILOSOPHERS];
sem_t mutex; // 用于实现AND型信号量机制
int philosopher_ids[NUM_PHILOSOPHERS];

// 思考函数
void think(int philosopher_id) {
    printf("哲学家 %d 正在思考...\n", philosopher_id);
    usleep(rand() % 300000 + 100000); // 随机思考时间
    printf("哲学家 %d 感到饥饿了\n", philosopher_id);
}

// 就餐函数
void eat(int philosopher_id) {
    printf("哲学家 %d 开始就餐\n", philosopher_id);
    usleep(rand() % 200000 + 100000); // 随机就餐时间
    printf("哲学家 %d 结束就餐\n", philosopher_id);
}

// AND型信号量操作 - 同时申请左右筷子
void and_semaphore_wait(int id) {
    int left = id;
    int right = (id + 1) % NUM_PHILOSOPHERS;
    
    while(1) {
        sem_wait(&mutex); // 进入临界区
        
        // 检查左右筷子是否都可用
        int left_available, right_available;
        sem_getvalue(&chopsticks[left], &left_available);
        sem_getvalue(&chopsticks[right], &right_available);
        
        if (left_available > 0 && right_available > 0) {
            // 同时获取左右筷子
            sem_wait(&chopsticks[left]);
            sem_wait(&chopsticks[right]);
            sem_post(&mutex); // 离开临界区
            printf("哲学家 %d 同时获得左右筷子\n", id);
            return;
        }
        
        sem_post(&mutex); // 离开临界区
        usleep(50000); // 等待后重试
    }
}

// 哲学家线程函数
void* philosopher(void* num) {
    int id = *(int*)num;
    
    while(1) {
        think(id);
        
        // 使用AND型信号量机制同时申请左右筷子
        and_semaphore_wait(id);
        
        // 就餐
        eat(id);
        
        // 放回筷子
        sem_post(&chopsticks[id]);
        sem_post(&chopsticks[(id + 1) % NUM_PHILOSOPHERS]);
        printf("哲学家 %d 放回了筷子\n", id);
    }
    
    return NULL;
}

int main() {
    pthread_t philosophers[NUM_PHILOSOPHERS];
    
    srand(time(NULL));
    
    printf("=== 哲学家就餐问题 - 解决方案四 ===\n");
    printf("AND型信号量机制：同时申请左右筷子\n\n");
    
    // 初始化信号量（筷子），初始值为1
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        sem_init(&chopsticks[i], 0, 1);
        philosopher_ids[i] = i;
    }
    
    // 初始化互斥锁
    sem_init(&mutex, 0, 1);
    
    // 创建哲学家线程
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_ids[i]);
    }
    
    // 等待所有哲学家线程（实际上可能会永远等待）
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_join(philosophers[i], NULL);
    }
    
    return 0;
}

解决方案五

主要破坏的条件：循环等待

使用状态数组跟踪每个哲学家的状态，确保哲学家只有在两个邻居都不在进餐时才允许进入进餐状态。

核心思想

通过维护每个哲学家的状态（思考、饥饿、进餐），并使用信号量数组来阻塞无法进餐的哲学家。只有当左右邻居都不在进餐状态时，哲学家才能开始进餐。

伪代码

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
41
42
43
44
45
46
47
48
// 定义常量和宏
#define N 5
#define LEFT (i + N - 1) % N
#define RIGHT (i + 1) % N
#define THINKING 0
#define HUNGRY 1
#define EATING 2

// 全局变量
int state[N]
semaphore s[N] = {0}  // 每个哲学家一个信号量
semaphore mutex = 1    // 互斥访问状态数组

// 测试哲学家i是否可以开始就餐
procedure test(i) {
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING
        signal(s[i])  // 唤醒哲学家i
    }
}

// 拿起筷子
procedure take_forks(i) {
    P(mutex)           // 进入临界区
    state[i] = HUNGRY
    test(i)            // 尝试获取筷子
    V(mutex)           // 离开临界区
    P(s[i])            // 如果无法获取则阻塞
}

// 放下筷子
procedure put_forks(i) {
    P(mutex)           // 进入临界区
    state[i] = THINKING
    test(LEFT)         // 检查左邻居
    test(RIGHT)        // 检查右邻居
    V(mutex)           // 离开临界区
}

// 哲学家进程
procedure philosopher(i) {
    while(true) {
        think()
        take_forks(i)  // 获取筷子
        eat()          // 就餐
        put_forks(i)   // 放下筷子
    }
}

源码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>
#include <time.h>

#define NUM_PHILOSOPHERS 5
#define LEFT (i + NUM_PHILOSOPHERS - 1) % NUM_PHILOSOPHERS
#define RIGHT (i + 1) % NUM_PHILOSOPHERS

#define THINKING 0
#define HUNGRY 1
#define EATING 2

// 哲学家状态数组
int state[NUM_PHILOSOPHERS];
// 信号量数组，每个哲学家一个
sem_t s[NUM_PHILOSOPHERS];
// 互斥锁，保护状态数组
sem_t mutex;
int philosopher_ids[NUM_PHILOSOPHERS];

// 思考函数
void think(int philosopher_id) {
    printf("哲学家 %d 正在思考...\n", philosopher_id);
    usleep(rand() % 300000 + 100000);
    printf("哲学家 %d 感到饥饿了\n", philosopher_id);
}

// 就餐函数
void eat(int philosopher_id) {
    printf("哲学家 %d 开始就餐\n", philosopher_id);
    usleep(rand() % 200000 + 100000);
    printf("哲学家 %d 结束就餐\n", philosopher_id);
}

// 测试哲学家是否可以开始就餐
void test(int i) {
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING;
        sem_post(&s[i]); // 唤醒哲学家i
    }
}

// 拿起筷子
void take_forks(int i) {
    sem_wait(&mutex); // 进入临界区
    state[i] = HUNGRY;
    printf("哲学家 %d 处于饥饿状态\n", i);
    test(i); // 尝试获取筷子
    sem_post(&mutex); // 离开临界区
    sem_wait(&s[i]); // 如果无法获取筷子则阻塞
}

// 放下筷子
void put_forks(int i) {
    sem_wait(&mutex); // 进入临界区
    state[i] = THINKING;
    printf("哲学家 %d 放下筷子\n", i);
    test(LEFT); // 检查左邻居是否可以就餐
    test(RIGHT); // 检查右邻居是否可以就餐
    sem_post(&mutex); // 离开临界区
}

// 哲学家线程函数
void* philosopher(void* num) {
    int i = *(int*)num;
    
    while(1) {
        think(i);
        take_forks(i); // 获取筷子
        eat(i);        // 就餐
        put_forks(i);  // 放下筷子
    }
    
    return NULL;
}

int main() {
    pthread_t philosophers[NUM_PHILOSOPHERS];
    
    srand(time(NULL));
    
    printf("=== 哲学家就餐问题 - 解决方案五 ===\n");
    printf("状态监测法：邻居不在进餐时才允许进餐\n\n");
    
    // 初始化互斥锁
    sem_init(&mutex, 0, 1);
    
    // 初始化信号量数组和状态数组
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        sem_init(&s[i], 0, 0); // 初始值为0，哲学家开始时阻塞
        state[i] = THINKING;   // 初始状态为思考
        philosopher_ids[i] = i;
    }
    
    // 创建哲学家线程
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_ids[i]);
    }
    
    // 等待所有哲学家线程
    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_join(philosophers[i], NULL);
    }
    
    return 0;
}

五、总结

哲学家就餐问题作为并发编程领域的经典案例，深刻地揭示了多进程/多线程环境中资源竞争与同步的核心挑战。通过五种不同的解决方案，我们展示了如何从不同角度破坏死锁的必要条件，从而确保系统的安全性和活性。从简单的资源限制到精巧的状态监测，每种方案都体现了独特的设计思想和权衡考量。在实际系统设计中，选择何种方案需要综合考虑性能要求、实现复杂度、资源约束等多方面因素。理解这些解决方案不仅有助于解决具体的同步问题，更能培养系统性的并发编程思维，为构建健壮、高效的并发系统奠定坚实基础。