锐客网

  1. 首页 > 睿知 > it技术 > >

理发师问题java代码 理发师在线问答

IT技术扫描线

哲学家进餐问题（在计算机操作系统方面的相关编程）操作系统并发和互斥：哲学家进餐问题和理发师问题
1． 哲学家进餐问题：
(1) 在什么情况下5 个哲学家全部吃不上饭？
考虑两种实现的方式，如下：
A.
【理发师问题java代码 理发师在线问答】算法描述：
void philosopher(int i) /*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 的原则，总会进入到餐厅就餐，因此不会
出现饿死和死锁的现象 。
伪码：
semaphore chopstick[5]={1 ， 1 ， 1，1，1};
semaphore room=4;
void philosopher(int i)
{
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 的要求 ， 
因此不会出现饥饿的情形 。
伪码：
semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int I)
{
while(true)
{
think();
Swait(chopstick[(I+1)]%5,chopstick[I]);
eat();
Ssignal(chopstick[(I+1)]%5,chopstick[I]);
}
}
方法2：利用信号量的保护机制实现 。通过信号量mutex对eat（）之前的取左侧和右侧筷
子的操作进行保护 ， 使之成为一个原子操作，这样可以防止死锁的出现 。

推荐阅读


上一篇：ios怎么修改qq位置，苹果手机位置怎么设置

下一篇：直播什么开始的，直播是什么时候出来的