admin 管理员组文章数量: 887016
问题描述：
有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。
约束条件
(1)只有拿到两只筷子时，哲学家才能吃饭。 (2)如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。 (3)任一哲学家在自己未拿到两只筷子吃饭前，不会放下手中拿到的筷子。
哲学家进餐问题是一大类并发控制问题的典型例子，涉及信号量机制、以及死锁等操作系统中关键问题的应用。
要解决“哲学家进餐问题”，就要明白以下几个名词的含义（自己的理解）：
（1）高并发：指的是是一种系统运行过程中遇到的一种“短时间内遇到大量操作请求”的情况,例如对资源CPU，寄存器的请求。
（2）多线程：简单来说，多线程就是多个执行序列。就是让cpu执行下这个序列，又执行下那个序列，不停地切换，正所谓一心二用。多线程是为了同步完成多项任务，不是为了提高运行效率，而是为了提高资源使用效率来提高系统的效率。
（3）多线程死锁：所谓死锁是指多个线程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。
（4）信号量：多线程同步使用的；一个线程完成某个动作后通过信号告诉别的线程，别的线程才可以执行某些动作。（值可以为>=0的数）
（5）互斥量：多线程互斥使用的；一个线程占用某个资源，那么别的线程就无法访问，直到该线程离开，其他线程才可以访问该资源。(值只能为0和1)
（6）那么如何解决高并发呢?
答：如果使用单线程，那么程序就必须等待这些操作执行完成之后才能执行其他操作。可以使用多线程解决高并发，多线程在高并发问题中的作用就是充分利用计算机资源，使计算机的资源在每一时刻都能达到最大的利用率，不至于浪费计算机资源使其闲置。实际上是系统不断地在各个线程之间来回的切换（因为系统切换的速度非常的快，所以给我们在同时运行的错觉）。
最直接的解决办法（引起死锁）
最直接的解决办法是5只筷子分别设置为初始值为1的互斥信号量。这样可以保证不会有相邻的哲学家同时进餐，但是若5位哲学家同时拿起左筷子，都会因为拿不到右筷子而引起死锁。
优化解决办法
解决办法有很多种：（1）通过互斥信号量 mutex 对哲学家进餐之前取左侧和右侧筷子的操作进行保护，可以防止死锁的出现。（当第i个哲学家将左右筷子都拿到了才允许其他哲学家拿筷子）
如下面的运行截图可以说明。哲学家4在拿起左筷子与右筷子中间没有其他的哲学家拿任何一个筷子，虽然他们也饿了，虽然他们要拿的筷子可能并没有被占用，所以这个会造成资源（筷子）得不到有效的利用。
贴上代码：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define N 5
sem_t chopsticks[N];//设置5种信号量，有5种不同类型的资源，每一种有1个,这样便于理解，因为每个哲学家需要的资源不同
pthread_mutex_t mutex;//定义互斥锁
int philosophers[N] = {0, 1, 2, 3, 4};//代表5个哲学家的编号
void delay (int len) {
int i = rand() % len;
int x;
while (i > 0) {
x = rand() % len;
while (x > 0) {
x--;
}
i--;
}
}
void *philosopher (void* arg) {
int i = *(int *)arg;
int left = i;//左筷子的编号和哲学家的编号相同
int right = (i + 1) % N;//右筷子的编号为哲学家编号+1
while (1) {
printf("哲学家%d正在思考问题\n", i);
delay(60000);
printf("哲学家%d饿了\n", i);
pthread_mutex_lock(&mutex);//加锁
sem_wait(&chopsticks[left]);//此时这个哲学家左筷子的信号量-1之后>=0时，表示能继续执行。
printf("哲学家%d拿起了%d号筷子,现在只有一支筷子,不能进餐\n", i, left);
sem_wait(&chopsticks[right]);
printf("哲学家%d拿起了%d号筷子\n", i, right);
pthread_mutex_unlock(&mutex);//解锁
printf("哲学家%d现在有两支筷子,开始进餐\n", i);
delay(60000);
sem_post(&chopsticks[left]);
printf("哲学家%d放下了%d号筷子\n", i, left);
sem_post(&chopsticks[right]);
printf("哲学家%d放下了%d号筷子\n", i, right);
}
}
int main (int argc, char **argv) {
srand(time(NULL));
pthread_t philo[N];
//信号量初始化
for (int i=0; i<N; i++) {
sem_init(&chopsticks[i], 0, 1);
}
pthread_mutex_init(&mutex,NULL);//初始化互斥锁
//创建线程
for (int i=0; i<N; i++) {
pthread_create(&philo[i], NULL, philosopher, &philosophers[i]);
}
//挂起线程
for (int i=0; i<N; i++) {
pthread_join(philo[i], NULL);
}
//销毁信号量
for (int i=0; i<N; i++) {
sem_destroy(&chopsticks[i]);
}
pthread_mutex_destroy(&mutex);//销毁互斥锁
return 0;
}（2）规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。所以将是 2,3 号哲学家竞争 3 号筷子，4,5 号哲学家竞争 5 号筷子。1 号哲学家不需要竞争。最后总会有一个哲学家能获得两支筷子而进餐。
例如下面的运行结果截图可以说明。当哲学家4放下4号筷子时，4号筷子被释放，3号哲学家得到4号筷子（右筷子）进行进餐。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define N 5
sem_t chopsticks[N];//设置5种信号量，有5种不同类型的资源，每一种有1个,这样便于理解，因为每个哲学家需要的资源不同
int philosophers[N] = {0, 1, 2, 3, 4};//代表5个哲学家的编号
void delay (int len) {
int i = rand() % len;
int x;
while (i > 0) {
x = rand() % len;
while (x > 0) {
x--;
}
i--;
}
}
void *philosopher (void* arg) {
int i = *(int *)arg;
int left = i;//左筷子的编号和哲学家的编号相同
int right = (i + 1) % N;//右筷子的编号为哲学家编号+1
while (1) {
if(i % 2 == 0){
printf("哲学家%d正在思考问题\n", i);
delay(60000);
printf("哲学家%d饿了\n", i);
sem_wait(&chopsticks[right]);//此时这个哲学家左筷子的信号量-1之后>=0时，表示能继续执行。
printf("哲学家%d拿起了%d号筷子,现在只有一支筷子,不能进餐\n", i, right);
sem_wait(&chopsticks[left]);
printf("哲学家%d拿起了%d号筷子, 现在有两支筷子,开始进餐\n", i, left);
delay(60000);
sem_post(&chopsticks[left]);
printf("哲学家%d放下了%d号筷子\n", i, left);
sem_post(&chopsticks[right]);
printf("哲学家%d放下了%d号筷子\n", i, right);
}
else{
printf("哲学家%d正在思考问题\n", i);
delay(60000);
printf("哲学家%d饿了\n", i);
sem_wait(&chopsticks[left]);//此时这个哲学家左筷子的信号量-1之后>=0时，表示能继续执行。
printf("哲学家%d拿起了%d号筷子,现在只有一支筷子,不能进餐\n", i, left);
sem_wait(&chopsticks[right]);
printf("哲学家%d拿起了%d号筷子, 现在有两支筷子,开始进餐\n", i, right);
delay(60000);
sem_post(&chopsticks[left]);
printf("哲学家%d放下了%d号筷子\n", i, left);
sem_post(&chopsticks[right]);
printf("哲学家%d放下了%d号筷子\n", i, right);
}
}
}
int main (int argc, char **argv) {
srand(time(NULL));
pthread_t philo[N];
//信号量初始化
for (int i=0; i<N; i++) {
sem_init(&chopsticks[i], 0, 1);
}
//创建线程
for (int i=0; i<N; i++) {
pthread_create(&philo[i], NULL, philosopher, &philosophers[i]);
}
//挂起线程
for (int i=0; i<N; i++) {
pthread_join(philo[i], NULL);
}
//销毁信号量
for (int i=0; i<N; i++) {
sem_destroy(&chopsticks[i]);
}
return 0;
}（3）至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。此方法能使资源得到有效的利用。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define N 5
sem_t chopsticks[N];//设置5种信号量，有5种不同类型的资源，每一种有1个,这样便于理解，因为每个哲学家需要的资源不同
sem_t m;//最多允许有m(4)个哲学家同时拿起左筷子
int philosophers[N] = {0, 1, 2, 3, 4};//代表5个哲学家的编号
void delay (int len) {
int i = rand() % len;
int x;
while (i > 0) {
x = rand() % len;
while (x > 0) {
x--;
}
i--;
}
}
void *philosopher (void* arg) {
int i = *(int *)arg;
int left = i;//左筷子的编号和哲学家的编号相同
int right = (i + 1) % N;//右筷子的编号为哲学家编号+1
while (1) {
printf("哲学家%d正在思考问题\n", i);
delay(60000);
printf("哲学家%d饿了\n", i);
sem_wait(&m);//如果前4个哲学家同时拿起左筷子，第五个不能同时拿起左筷子，保证至少有一位哲学家能吃到饭，解决（死锁状态）。
sem_wait(&chopsticks[left]);//此时这个哲学家左筷子的信号量-1之后>=0时，表示能继续执行。
printf("哲学家%d拿起了%d号筷子,现在只有一支筷子,不能进餐\n", i, left);
sem_wait(&chopsticks[right]);
printf("哲学家%d拿起了%d号筷子, 现在有两支筷子,开始进餐\n", i, right);
delay(60000);
sem_post(&chopsticks[left]);
printf("哲学家%d放下了%d号筷子\n", i, left);
sem_post(&m);//当哲学家释放了左筷子时，信号量m+1
sem_post(&chopsticks[right]);
printf("哲学家%d放下了%d号筷子\n", i, right);
}
}
int main (int argc, char **argv) {
srand(time(NULL));
pthread_t philo[N];
//信号量初始化
for (int i=0; i<N; i++) {
sem_init(&chopsticks[i], 0, 1);
}
sem_init(&m, 0, 4);
//创建线程
for (int i=0; i<N; i++) {
pthread_create(&philo[i], NULL, philosopher, &philosophers[i]);
}
//挂起线程
for (int i=0; i<N; i++) {
pthread_join(philo[i], NULL);
}
//销毁信号量
for (int i=0; i<N; i++) {
sem_destroy(&chopsticks[i]);
}
sem_destroy(&m);
return 0;
}版权声明：本文标题：C语言多线程之“哲学家就餐”问题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1728417090h1240911.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论