dtcms hash Linux软件安装 Logstash package tkinter vector process matlab向上取整 underscorejs vue最新版本 vue滑动事件 jquery通过class获取元素 打印缩放怎么设置 short几个字节 matlab复数求模 mysql增删改查语句 maven配置eclipse quartz配置 linux查看jdk安装路径 matlab不等于 python多线程编程 python正则表达式语法 python路径设置 python学习方法 java数组反转 java数据 java基本类型 java可变参数 java的框架 java开发语言 sql语句大全实例教程 h5模板 0x0000004e cg模宝 c语言表白代码 混沌世界隐藏英雄密码 html5下载 linux定时任务 iframe跨域
当前位置: 首页 > 学习教程  > 编程语言

进程同步与互斥——哲学家就餐问题源码实现(dining philosopher’s problem)

2021/2/13 16:25:44 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

哲学家就餐问题 哲学家就餐问题(dining philosopher’s problem)是一个著名的并发问题,它由Dijkstra提出来并解决。这个问题之所以出名,是因为它很有趣,引人入胜,但其实用性却不强。可是,它的名…

哲学家就餐问题

哲学家就餐问题(dining philosopher’s problem)是一个著名的并发问题,它由Dijkstra提出来并解决。这个问题之所以出名,是因为它很有趣,引人入胜,但其实用性却不强。可是,它的名气让我们在这里必须讲。实际上,你可能会在面试中遇到这一问题,假如老师没有提过,导致你们没有通过面试,你们会责怪操作系统老师的。因此,我们这里会讨论这一问题。假如你们因为这个问题得到工作,可以向操作系统老师发感谢信,或者发一些股票期权。

这个问题的基本情况是:假定有5位“哲学家”围着一个圆桌。每两位哲学家之间有一把餐叉(一共5把)。哲学家有时要思考一会,不需要餐叉;有时又要就餐。而一位哲学家只有同时拿到了左手边和右手边的两把餐叉,才能吃到东西。关于餐叉的竞争以及随之而来的同步问题,就是我们在并发编程中研究它的原因。

下面是每个哲学家的基本循环:

while(1)
{
	think();
	getforks();
	eat();
	putfork();
}

关键的挑战就是如何实现getforks()和putforks()函数,保证没有死锁,没有哲学家饿死,并且并发度更高(尽可能让更多哲学家同时吃东西)。

根据Downey的解决方案,我们会用一些辅助函数,帮助构建解决方案。它们是:

int left(int p)  { return p; }
int right(int p) { return (p + 1) % 5;}

如果哲学家p希望用左手边的叉子,他们就调用left§。类似地,右手边的叉子就用right§。模运算解决了最后一个哲学家(p = 4)右手边叉子的编号问题,就是餐叉0。

我们需要一些信号量来解决这个问题。假设需要5个,每个餐叉一个:sem_t forks[5]。

有问题的解决方案

我们开始第一次尝试。假设我们把每个信号量(在fork数组中)都用1初始化。同时假设每个哲学家知道自己的编号(p)。我们可以写出getforks()和putforks()函数。

void getforks()
{
	sem_wait(forks[left(p)]);
	sem_wait(forks[right(p)]);
}

void putforks()
{
	sem_post(forks[left(p)]);
	sem_post(forks[right(p)]);
}

这个(有问题的)解决方案背后的思路如下。为了拿到餐叉,我们依次获取每把餐叉的锁——先是左手边的,然后是右手边的。结束就餐时,释放掉锁。很简单,不是吗?但是,在这个例子中,简单是有问题的。你能看到问题吗?想一想。问题是死锁(deadlock)。假设每个哲学家都拿到了左手边的餐叉,他们每个都会阻塞住,并且一直等待另一个餐叉。具体来说,哲学家0拿到了餐叉0,哲学家1拿到了餐叉1,哲学家2拿到餐叉2,哲学家3拿到餐叉3,哲学家4拿到餐叉4。所有的餐叉都被占有了,所有的哲学家都阻塞着,并且等待另一个哲学家占有的餐叉。我们在后续章节会深入学习死锁,这里只要知道这个方案行不通就可以了。

一种方案:破除依赖

解决上述问题最简单的方法,就是修改某个或者某些哲学家的取餐叉顺序。事实上,Dijkstra自己也是这样解决的。具体来说,假定哲学家4(编写最大的一个)取餐叉的顺序不同。相应的代码如下:

void getforks()
{
	if(p == 4)
	{
		sem_wait(forks[right(p)]);		
		sem_wait(forks[left(p)]);	
	}
	else
	{
		sem_wait(forks[left(p)]);
		sem_wait(forks[right(p)]);		
	}
}

因为最后一个哲学家会尝试先拿右手边的餐叉,然后拿左手边,所以不会出现每个哲学家都拿着一个餐叉,卡住等待另一个的情况,等待循环被打破了。想想这个方案的后果,让你自己相信它有效。

源码实现:

#include <semaphore.h>
#include <unistd.h>
#include <iostream>

using namespace std;

sem_t forks[5];

void think(int i)
{
    cout << "第" << i << "个哲学家正在思考" << endl;
    /* sleep(1); */
}

void eat(int i)
{
    cout << "第" << i << "个哲学家正在吃东西" << endl;
    /* sleep(2); */
}

int left(int p) {return p;}
int right(int p) {return (p + 1) % 5;}

void getforks(int i)
{
    sem_wait(&forks[left(i)]);
    cout << "第" << i << "个哲学家拿起左筷子" << endl;
    sem_wait(&forks[right(i)]);
    cout << "第" << i << "个哲学家拿起右筷子" << endl;
}

void putforks(int i)
{
    sem_post(&forks[left(i)]);
    cout << "第" << i << "个哲学家放下左筷子" << endl;
    sem_post(&forks[right(i)]);
    cout << "第" << i << "个哲学家放下右筷子" << endl;
}

void* philosopher_process_0(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

void* philosopher_process_1(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

void* philosopher_process_2(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

void* philosopher_process_3(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

void* philosopher_process_4(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

int main()
{
    for(int i = 0; i < 5; i++)
    {
        sem_init(&forks[i], 0, 1);
    }

    pthread_t philosopher[5];

    int id[5] = {0, 1, 2, 3, 4};
    
    pthread_create(&philosopher[0], nullptr, philosopher_process_0, &id[0]);
    pthread_create(&philosopher[1], nullptr, philosopher_process_1, &id[1]);
    pthread_create(&philosopher[2], nullptr, philosopher_process_2, &id[2]);
    pthread_create(&philosopher[3], nullptr, philosopher_process_3, &id[3]);
    pthread_create(&philosopher[4], nullptr, philosopher_process_4, &id[4]);

    pthread_join(philosopher[0], nullptr);
    pthread_join(philosopher[1], nullptr);
    pthread_join(philosopher[2], nullptr);
    pthread_join(philosopher[3], nullptr);
    pthread_join(philosopher[4], nullptr);

    return 0;
}

触发死锁是概率事件,实际运行结果:

4个哲学家正在思考
第4个哲学家拿起左筷子
第4个哲学家拿起右筷子
第4个哲学家正在吃东西
第4个哲学家放下左筷子
第4个哲学家放下右筷子
第3个哲学家正在思考
第3个哲学家拿起左筷子
第3个哲学家拿起右筷子
第3个哲学家正在吃东西
第3个哲学家放下左筷子
第3个哲学家放下右筷子
第2个哲学家正在思考
第2个哲学家拿起左筷子
第2个哲学家拿起右筷子
第2个哲学家正在吃东西
第2个哲学家放下左筷子
第2个哲学家放下右筷子
第1个哲学家正在思考
第1个哲学家拿起左筷子
第1个哲学家拿起右筷子
第1个哲学家正在吃东西
第1个哲学家放下左筷子
第1个哲学家放下右筷子
第0个哲学家正在思考
第0个哲学家拿起左筷子
第0个哲学家拿起右筷子
第0个哲学家正在吃东西
第0个哲学家放下左筷子
第0个哲学家放下右筷子


本文链接: http://www.dtmao.cc/news_show_700027.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?