- 1、本文档共8页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
操作系统并发和互斥:哲学家进餐问题和理发师问题
1.哲学家进餐问题:
(1)在什么情况下5个哲学家全部吃不上饭?
考虑两种实现的方式,如下:
A.
算法描述:
voidphilosopher(inti)/*i:哲学家编号,从0到4*/
{
while(TRUE){
think();/*哲学家正在思考*/
take_fork(i);/*取左侧的筷子*/
take_fork((i+1)%N);/*取左侧筷子;%为取模运算*/
eat();/*吃饭*/
put_fork(i);/*把左侧筷子放回桌子*/
put_fork((i+1)%N);/*把右侧筷子放回桌子*/
}
}
分析:假如所有的哲学家都同时拿起左侧筷子,看到右侧筷子不可用,又都放下左侧筷子,
等一会儿,又同时拿起左侧筷子,如此这般,永远重复。对于这种情况,即所有的程序都在
无限期地运行,但是都无法取得任何进展,即出现饥饿,所有哲学家都吃不上饭。
B.
算法描述:
规定在拿到左侧的筷子后,先检查右面的筷子是否可用。如果不可用,则先放下左侧筷子,
等一段时间再重复整个过程。
分析:当出现以下情形,在某一个瞬间,所有的哲学家都同时启动这个算法,拿起左侧的筷
子,而看到右侧筷子不可用,又都放下左侧筷子,等一会儿,又同时拿起左侧筷子……如此
这样永远重复下去。对于这种情况,所有的程序都在运行,但却无法取得进展,即出现饥饿,
所有的哲学家都吃不上饭。
(2)描述一种没有人饿死(永远拿不到筷子)算法。
考虑了四种实现的方式(A、B、C、D):
A.原理:至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释
放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room作为信号量,只允
许4个哲学家同时进入餐厅就餐,这样就能保证至少有一个哲学家可以就餐,而申请进入
餐厅的哲学家进入room的等待队列,根据FIFO的原则,总会进入到餐厅就餐,因此不会
出现饿死和死锁的现象。
伪码:
semaphorechopstick[5]={1,1,1,1,1};
semaphoreroom=4;
voidphilosopher(inti)
{
while(true)
{
think();
wait(room);//请求进入房间进餐
wait(chopstick[i]);//请求左手边的筷子
wait(chopstick[(i+1)%5]);//请求右手边的筷子
eat();
signal(chopstick[(i+1)%5]);//释放右手边的筷子
signal(chopstick[i]);//释放左手边的筷子
signal(room);//退出房间释放信号量room
}
}
B.原理:仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。
方法1:利用AND型信号量机制实现:根据课程讲述,在一个原语中,将一段代码同时需
要的多个临界资源,要么全部分配给它,要么一个都不分配,因此不会出现死锁的情形。当
某些资源不够时阻塞调用进程;由于等待队列的存在,使得对资源的请求满足FIFO的要求,
因此不会出现饥饿的情形。
伪码:
semaphorechopstick[5]={1,1,1,1,1};
voidphilosopher(intI)
{
while(true)
{
think();
Swait(chopstick[(I+1)]%5,chopstick[I]);
eat();
Ssignal(chopstick[(I+1)]%5,chopstick[I]);
}
}
方法2:利用信号量的保护机制实现。通过信号量mutex对eat()之前的取左侧和右侧筷
子的操作进行保护,使之成为一个原子操作,这样可以防止死锁的出现。
伪码:
semaphoremutex=1;
semaphorechopstick[5]={1,1,1,1,1};
voidphilosopher(intI)
{
while(true)
{
think();
wait(mutex);
wait(chopstick[(I+1)]%5);
wait(chopstick[I]);
signal(mutex);
eat();
signal(chopstick[(I+1)]%5);
signal(
文档评论(0)