用C语言实现哲学家进餐的问题

用 C 语言实现哲学家进餐的问题 设有 5 个哲学家 共享一张放油把椅子的桌子 每人分得一吧椅子 但 是桌子上总共执友支筷子 在每个人两边分开各放一支 哲学家只有在 肚子饥饿时才试图分两次从两边拾起筷子就餐 就餐条件是 1 哲学家想吃饭时 先提出吃饭的要求 2 提出吃饭要求 并拿到支筷子后 方可吃饭 3 如果筷子已被他人获得 则必须等待该人吃完饭之后才能获取 该筷子 4 任一哲学家在自己未拿到 2 支筷子吃饭之前 决不放下手中的 筷子 5 刚开始就餐时 只允许 2 个哲学家请求吃饭 试问 1 描述一个保证不会出现两个邻座同时要求吃饭的算法 2 描述一个既没有两邻座同时吃饭 又没有人饿死的算法 3 在什么情况下 5 个哲学家全都吃不上饭 哲学家进餐问题是典型的同步问题 它是由 Dijkstra 提出并解决 的 该问题是描述有五个哲学家 他们的生活方式是交替地进行思考和 进餐 哲学家们共用一张圆桌 分别坐在周围的五张椅子上 在圆桌上 有五个碗和五支筷子 平时一个哲学家进行思考 饥饿时便试图取用其 左右岁靠近他的筷子 只有在他拿到两支筷子时才能进餐 进餐完毕 放下筷子继续思考 利用记录型信号量解决哲学家进餐问题 经分析可知 筷子是临界资源 在一段时间只允许一个哲学家使用 因 此 可以用一个信号量表示一支筷子 由这五个信号量构成信号量数组 其 描述如下 var chopstick array 0 4 of semaphore 所有信号量被初始化为 1 第 i 个哲学家的活动可描述为 repeat wait chopstick wait chopstick i 1 mod 5 eat signal chopstick signal chopstick i 1 mod 5 think until false 在以上描述中 哲学家饥饿时 总是先去拿他左边的筷子 即执行 wait chopstick 成功后 再去拿他右边的筷子 即执行 wait chopstick i 1 mod 5 再成功后便可进餐 进餐完毕 又先放下他 左边的筷子 然后放下他右边的筷子 虽然 上述解法可保证不会有两 个相临的哲学家同时进餐 但引起死锁是可能的 假如五个哲学家同时 饥饿而各自拿起右边的筷子时 就会使五个信号量 chopstick 均为 0 当 他们试图去拿右边的筷子时 都将因无筷子可拿而无限期地等待 对于 这样的死锁问题可采用以下集中解决方法 1 至多只允许四个哲学家同时进餐 以保证至少有一个哲学家能 够进餐 最终总会释放出他所使用过的两支筷子 从而可使更多的哲学 家进餐 2 仅当哲学家的左右两支筷子都可用时 才允许他拿起筷子进餐 3 规定奇数号的哲学家先拿起他左边的筷子 然后再去拿他右边 的筷子 而偶数号的哲学家则相反 按此规定 将是 1 2 号哲学家竞争 1 号筷子 3 4 号哲学家竞争 3 号筷子 即五个哲学家都竞争奇数号筷子 获得后 再去竞争偶数号筷子 最后总会有一个哲学家能获得两支筷子 而进餐 看了整整一个上午的操作系统 看得头都大了 我们老师的算法的大意好像是用一个总的信号量 只有获得信 号量的哲学家才可以拿筷子 具体算法如下 用类 c 描述 include 所有头文件 define N 5 define left i 1 N i 的左邻号码 define right i 1 N i 的右邻号码 define think 0 define hungry 1 define eating 2 typedef int semaphore 信号量是一个特殊的整型变量 int state N 记录每个人的状态 semaphore mutex 1 设置信号量 semaphore s N 每个哲学家一个信号量 void philosopher int i while true 无限循环 think take chopstick i eat put chopstick i void take chopstick int i p 对信号量的 p 操作 state hungry test i 试图得到两支筷子 v v 操作 p 得不到筷子则阻塞 void put chopstick in