admin管理员组文章数量:1530518
文章目录
- 预备知识
- 1、同步互斥问题
- 2、PV操作
- 1.P操作（wait）
- 2.V操作（single）
- 3.死锁产生条件
- 一、问题描述
- 二、解决思路（1）
- 1、思路分析
- 2、伪代码实现
- 三、解决思路（2）
- 1、 思路分析
- 2、伪代码实现
- 四、解决思路（3）
- 1.思路分析
- 2.伪代码实现
预备知识
1、同步互斥问题
在计算机操作系统领域有很多经典算法，在程序并发执行过程中会遇到很多问题。基于这些问题，衍生出很多经典的算法题，哲学家就餐问题就是其中一个重要的模型。
2、PV操作
1.P操作（wait）
P操作先检测临界资源，当临界资源小于0时，进程进入阻塞状态。
white(s){ //P信号量
while(s<=0);//进入死循环
s=s-1;
}
2.V操作（single）
V操作主要实现临界资源释放。
signal（s）{ //V操作
s=s+1;
}
3.死锁产生条件
1、互斥条件： 进程要求对所分配的资源进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
2、不剥夺条件： 进程所获得的资源在未使用完之前， 不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（ 只能是主动释放）。
3、请求并保持条件： 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
4、循环等待条件： 存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。
一、问题描述
一群哲学家围绕一个圆桌思考问题，圆桌上摆满了美食。在每个哲学家两边各有一个筷子，两个哲学家之间只有一个筷子，只有当哲学家拿到左右两边的筷子才可以吃饭，当哲学家吃饱了就会将筷子放下来接着进行思考。为了避免哲学家饿死，就诞生出哲学家就餐的问题。
二、解决思路（1）
1、思路分析
为了避免哲学家饿死，我们现在给哲学家定另一个规矩：最后一个哲学家比较扛饿，他的肚子最大，一时半会儿饿不死，他最后才可以吃。假设有n个哲学家，我们通过设置一个信号初始值n-1。
2、伪代码实现
semaphore count=n-1;//限制只有n-1个哲学家就餐
semaphore mutex[]={1,1,1....};
philosopher（）{//第i个哲学家
while(1){
P(count);//最后一个哲学家进不去
P(mutex[n-1]);//先拿左边筷子
p(mutex[n]);//再拿右边筷子
//吃饭
V(mutex[n-1]);//放下左边筷子
V(mutex[n]);//放下右边筷子
V(count);//就餐结束
}
}
三、解决思路（2）
1、 思路分析
为了避免哲学家饿死，我们现在给哲学家定另一个规矩：只有当哲学家两边都有筷子的时候，哲学家才可以进行就餐。者时是将两个信号进行集中判断，进而实现哲学家就餐问题。
2、伪代码实现
semaphore mutex[]={1,1,1....};
philosopher（）{//第i个哲学家
while(1){
P(mutex[n-1],mutex[n]);//左右两边筷子同时拿起
//哲学家就餐
V(mutex[n-1],mutex[n]);//左右两边筷子同时放下
}
}
四、解决思路（3）
1.思路分析
为了避免哲学家饿死，我们现在给哲学家定另一个规矩：坐在奇数位置的哲学家只能先拿左边的筷子，坐在偶数位的哲学家只能先拿右边筷子。这样在奇数位置的筷子就变成临界变量，谁获取到这个筷子谁就可以吃饭。
2.伪代码实现
semaphore mutex[]={1,1,1....};
philosopher（）{//第i个哲学家
while(1){
if(i%2==0){
P(mutex[i-1]);//偶数位的哲学家拿右边的筷子
P(mutex[i]);
//哲学家就餐
V(mutex[i]);
V(mutex[i-1]);
}
if(i%2==1){
P(mutex[i]);//奇数位的哲学家拿左边的筷子
P(mutex[i-1]);
//哲学家就餐
V(mutex[i]);
V(mutex[i-1]);
}
}
}
版权声明：本文标题：操作系统经典问题之哲学家就餐算法 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1717895077a622190.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论