当前课程知识点：操作系统 > 第十八讲 信号量与管程 > 18.4 哲学家就餐问题 > 18.4 哲学家就餐问题
下面我们来讨论如何用前面的
信号量和管程的方法
来解决几个经典的同步问题
这就是我们这里说到的
哲学家就餐问题和读者写者问题
首先我们来看哲学家就餐问题
这个问题的描述是这样的
有五位哲学家围坐在一个圆桌旁
这是这五位哲学家
他们编号分别为0到4
然后桌子上呢放了5把刀叉
每个哲学家之间呢有一个
那这地方纯粹是为了我们在这里
来讨论同步互斥而设置一种场景
在这里头呢
每个哲学家会进行思考
或者就餐两种操作
那思考呢不需要周围的资源
而就餐呢 他需要拿到两个叉子
他才可以开始就餐
所以这时候呢
两个哲学家之间
会需要共享一把叉子
那我们可以在这儿认为呢
这个叉子是我在这里头
两个哲学家之间的共享资源
在思考的时候
哲学家会把两把叉子都放回原处
在他旁边的哲学家就可以用
这个叉子来进行就餐了
好 我的问题是我如何让
这五个哲学家能够有序的进行
他们想进行的操作
也就说他思考的时候
这时候随时可以进行
不就餐的话
他就可以在这里进行思考
那关键问题是
他想就餐的时候会怎么样
如果说相邻的两个哲学家都想就餐
那这时候呢
他们就需要有一个人等待
原因在于 这时候他们俩之间
只有一个叉子
这个叉子只能保证一个人用
好 这时候我们说
用什么办法我们能解决这些问题呢
说我在这里首先想到的
是用信号量的办法
那信号量的办法我如何来解决呢
那我们在这里做法呢
第一个方案是说我每把叉子
算是一个资源对应着一个信号量
那它的初值是1
好 然后说先有一个程序的框架
五个哲学家
每个哲学家的ID呢这里的i
它可能是0到4
它可以进行两种操作 思考和就餐
我们在这里需要考虑
主要部分是他就餐这一部分
就餐的时候他需要拿到
左边的刀叉和右边的刀叉
那这时候我们说两个P操作
来获得他左边和右边的叉子
如果他能获得到他就会就餐
等他吃完之后
他释放两边的刀叉
整个又回来 他可以又进行思考
那这时候的问题是
这个算法行吗
那在多数情况下它是没问题的
你比如说在这里头
我先申请左边的刀叉
那如果申请不到
那我再去申请右边的刀叉
如果两边申请到我就就餐
如果申请到一个
旁边这个人呢已经先拿取
我的右边的刀叉
对于他来说是左边
好 那也时候呢
我就会等着他就餐完毕之后
他放下刀叉然后进行思考的时候
我再拿起右边刀叉
这时候我也可以开始就餐了
但是在一种极端的情况下
大家可以想象
如果五个哲学家
他们都在同一时间
进行相同的动作
这时候会出现什么情况
大家一起拿左边的刀叉
先假定在前面所有的刀叉
都是放在那儿的
好 大家一起拿左边刀叉
然后这时候都拿到左边之后
这时候五个哲学家
每个人拿到一个刀叉
都是左边的对于他们来说
好 这时候他开始拿去拿右边这个
那这时候会出现啥情况
每个哲学家右边都没有了
好 那按照刚才我们约定说
这时候等着下一个用完了我再来用
但实际上这时候呢
每一个人都拿到了左边的刀叉
没有拿到右边了
而这时候所有人呢都开始等待
那这时候会等出结果来吗
没有任何一个人可以开始就餐
那这样一来的话
所有的人都是无限期等待下去
好 那所以这时候出现什么问题
这个算法是不正确的
有可能进入死锁
也就是五个人同时
拿左边刀叉的时候
那它就会进入死锁状态
好 那这个不行我怎么改呢
那这就是我们想到的第二种做法
极端的做法
因为实际上在我们系统里头
我们希望把资源得到充分的利用
一旦我没有办法做充分利用的时候
我就把所有资源打成一个整包
然后说只有一个进程
可以占用这一整包的资源
不管它是不是都需要
那在这种情况下
我这个系统也能正常的运行下去
只是效率低一些就是了
好 那我们想到是这种做法
我设置一个互斥变量
我任何一个时刻
只有一个哲学家可以就餐
那这事呢也变得可以能解决出来
那在这儿也是这样的
这是思考就餐
我需要保护就餐这一段
我用这个 mutex
来作为这个互斥信号量
好 在这个地方呢
P操作和V操作 任何一个哲学家
他只要是申请到这个互斥信号量
也就是我们这里说二进制信号量
好 那这时候呢它就可以进行就餐
因为它的初值是1
所以任何一个时刻
只有一个哲学家能够
获取到这个信号量
然后他再去依次
拿起左边和右边的刀叉
那这时候它会碰到障碍吗
不会 因为这五个信号量
你只有在申请到了
二进制信号量之后
你才有可能来申请到
刀叉的信号量
而任何一个时刻呢
我只有一个进程
申请到二进制信号量
好 那这时候呢
后面这两个申请不会碰到问题
好 他会就餐
吃完之后他放下刀叉
然后释放互斥信号量
他继续上面的思考
那从这种做法里头呢
我们看到 这是能够保证
大家顺序吃饭的
但是我这时候的情况
是我有五把刀叉
按道理来说
我可以给两个人一起吃
因为总会剩一把刀叉在那儿放着
而我们现在这里头呢
我只要他一个人吃
好 那这样话它的效率就降低了
但是它是正确的
这种做法呢我们认为它可以接受
但是性能不好
我们有没有更好的办法
好 那这时候我们说
再给出第三种解决方案
我仍然是用五把刀叉
但是我不会设一个全局的锁
把整个就餐这事
变成一个临界区的操作
那我怎么办呢
针对我们刚才说到的
五个哲学家一起拿起左边的刀叉
之后所面临的死锁的情况
我让他们每个人
拿刀叉的时候有差异
不至于是所有的人
全部都一起拿起左边的
那这样一来的话就
不会出现构成环路的情况
那总会有先有后
好 最后保证大家都能拿到
那在通常情况下呢
我可以两个人一起就餐
那在这儿怎么做呢
好 我在这儿设一个分支结构
如果说根据每个人的编号不同
我采取不同的动作
偶数编号的
我先拿左边后拿右边
奇数的先拿右边后拿左边
那这样一来的话
就不会出现五个都拿到
一部分资源构成环路这种情况
好 那等他就餐完了之后
我把刀叉放回去
那这时候我有必要再在这个地方
再把它分成两种情况吗
实际上这个操作它是不会堵塞的
所以你不用把它分成两种情况
好 那么这时候说
在这种情况下我可以
两个哲学家同时就餐吗
你比如说0号和2号
假定这时候没有其他人的话
那他们俩是可以的
因为中间隔了一个哲学家
好 那这时候他们俩
都可以拿到相应的叉子
他不断是正确的
不会出现死锁
并且允许 有可能的话
两个人同时就餐
这是我们在这里呢
用信号量能给出的
一种比较理想的办法
那这时候问
这种做法是不是最优的呢
我是不是可以
还想得出更好的办法呢
这个呢留给大家
下去之后进行思考
-0.1 Piazza讨论区
--html
-0.2 在线实验平台
--实验平台使用帮助
--平台使用帮助
-0.2在线实验平台
--Raw HTML
-1.1 课程概述
--视频
-第一讲 操作系统概述--练习
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-2.1 前言和国内外现状
-2.2 OS实验目标
-2.3 8个OS实验概述
-2.4 实验环境搭建
-2.5 x86-32硬件介绍
-2.6 ucore部分编程技巧
-2.7 演示实验操作过程
--Q6
--Q7
--Q10
-3.1 BIOS
--3.1 BIOS
-3.2 系统启动流程
-3.3 中断、异常和系统调用比较
-第三讲 启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较
-3.4 系统调用
--3.4 系统调用
-第三讲 启动、中断、异常和系统调用--3.4 系统调用
-3.5 系统调用示例
-3.6 ucore+系统调用代码
-4.1 启动顺序
--4.1 启动顺序
-4.2 C函数调用的实现
-4.3 GCC内联汇编
-4.4 x86中断处理过程
-4.5 练习一
--4.5 练习一
-4.6 练习二
--4.6 练习二
-4.7 练习三
--4.7 练习三
-4.8 练习四 练习五
-4.9 练习六
--4.9 练习六
-5.1 计算机体系结构和内存层次
-5.2 地址空间和地址生成
-5.3 连续内存分配
-5.4 碎片整理
--5.4 碎片整理
-5.5 伙伴系统
--5.5 伙伴系统
-第五讲 物理内存管理: 连续内存分配--5.6 练习
-6.1 非连续内存分配的需求背景
-6.2 段式存储管理
-- 6.2 段式存储管理
-6.3 页式存储管理
-6.4 页表概述
--6.4 页表概述
-6.5 快表和多级页表
-6.6 反置页表
--6.6 反置页表
-6.7 段页式存储管理
-第六讲 物理内存管理: 非连续内存分配--6.8 练习
-7.1 了解x86保护模式中的特权级
-第七讲 实验二 物理内存管理--7.1 了解x86保护模式中的特权级
-7.2 了解特权级切换过程
-第七讲 实验二 物理内存管理--7.2 了解特权级切换过程
-7.3 了解段/页表
-第七讲 实验二 物理内存管理--7.3 了解段/页表
-7.4 了解UCORE建立段/页表
-第七讲 实验二 物理内存管理--7.4 了解UCORE建立段/页表
-7.5 演示lab2实验环节
-8.1 虚拟存储的需求背景
-8.2 覆盖和交换
-8.3 局部性原理
-8.4 虚拟存储概念
-8.5 虚拟页式存储
-8.6 缺页异常
--8.6 缺页异常
-9.1 页面置换算法的概念
-9.2 最优算法、先进先出算法和最近最久未使用算法
-第九讲 页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法
-9.3 时钟置换算法和最不常用算法
-第九讲 页面置换算法--9.3 时钟置换算法和最不常用算法
-9.4 Belady现象和局部置换算法比较
-第九讲 页面置换算法--9.4 Belady现象和局部置换算法比较
-9.5 工作集置换算法
-第九讲 页面置换算法--9.5 工作集置换算法
-9.6 缺页率置换算法
-第九讲 页面置换算法--9.6 缺页率置换算法
-9.7 抖动和负载控制
-10.1 实验目标：虚存管理
-第十讲 实验三 虚拟内存管理--10.1 实验目标：虚存管理
-10.2 回顾历史和了解当下
-第十讲 实验三 虚拟内存管理--10.2 回顾历史和了解当下
-10.3 处理流程、关键数据结构和功能
-第十讲 实验三 虚拟内存管理--10.3 处理流程、关键数据结构和功能
-10.4 页访问异常
-第十讲 实验三 虚拟内存管理--10.4 页访问异常
-10.5 页换入换出机制
-第十讲 实验三 虚拟内存管理--10.5 页换入换出机制
-11.1 进程的概念
-第十一讲 进程和线程--11.1 进程的概念
-11.2 进程控制块
-第十一讲 进程和线程--11.2 进程控制块
-11.3 进程状态
-第十一讲 进程和线程--11.3 进程状态
-11.4 三状态进程模型
-11.5 挂起进程模型
-第十一讲 进程和线程--11.5 挂起进程模型
-11.6 线程的概念
-第十一讲 进程和线程--11.6 线程的概念
-11.7 用户线程
-第十一讲 进程和线程--11.7 用户线程
-11.8 内核线程
-第十一讲 进程和线程--11.8 内核线程
-12.1 进程切换
-第十二讲 进程控制--12.1 进程切换
-12.2 进程创建
-第十二讲 进程控制--12.2 进程创建
-12.3 进程加载
-第十二讲 进程控制--12.3 进程加载
-12.4 进程等待与退出
-第十二讲 进程控制--12.4 进程等待与退出
-13.1 总体介绍
-13.2 关键数据结构
-13.3 执行流程
-13.4 实际操作
-14.1 总体介绍
-14.2 进程的内存布局
-14.3 执行ELF格式的二进制代码-do_execve的实现
--14.3 执行ELF格式的二进制代码-do_execve的实现
-14.4 执行ELF格式的二进制代码-load_icode的实现
--14.4 执行ELF格式的二进制代码-load_icode的实现
-14.5 进程复制
-14.6 内存管理的copy-on-write机制
-15.1 处理机调度概念
-第十五讲 处理机调度--15.1 处理机调度概念
-15.2 调度准则
-15.3 先来先服务、短进程优先和最高响应比优先调度算法
--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-第十五讲 处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-第十五讲 处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc
-15.5 实时调度和多处理器调度
-第十五讲 处理机调度--15.5 实时调度和多处理器调度
-15.6 优先级反置
-第十五讲 处理机调度--15.6 优先级反置
-16.1 总体介绍和调度过程
-16.2 调度算法支撑框架
-16.3 时间片轮转调度算法
-16.4 Stride调度算法
-17.1 背景
--17.1 背景
-17.2 现实生活中的同步问题
-第十七讲 同步互斥--17.2 现实生活中的同步问题
-17.3 临界区和禁用硬件中断同步方法
-第十七讲 同步互斥--17.3 临界区和禁用硬件中断同步方法
-17.4 基于软件的同步方法
-第十七讲 同步互斥--17.4 基于软件的同步方法
-17.5 高级抽象的同步方法
-第十七讲 同步互斥--17.5 高级抽象的同步方法
-18.1 信号量
--18.1 信号量
-第十八讲 信号量与管程--18.1 信号量
-18.2 信号量使用
-第十八讲 信号量与管程--18.2 信号量使用
-18.3 管程
--18.3 管程
-第十八讲 信号量与管程--18.3 管程
-18.4 哲学家就餐问题
-18.5 读者-写者问题
-19.1 总体介绍
-19.2 底层支撑
-第十九讲 实验七 同步互斥--19.2 底层支撑
-19.3 信号量设计实现
-第十九讲 实验七 同步互斥--19.3 信号量设计实现
-19.4 管程和条件变量设计实现
-第十九讲 实验七 同步互斥--19.4 管程和条件变量设计实现
-19.5 哲学家就餐问题
-20.1 死锁概念
-第二十讲 死锁和进程通信--20.1 死锁概念
-20.2 死锁处理方法
-第二十讲 死锁和进程通信--20.2 死锁处理方法
-20.3 银行家算法
-第二十讲 死锁和进程通信--20.3 银行家算法
-20.4 死锁检测
-第二十讲 死锁和进程通信--20.4 死锁检测
-20.5 进程通信概念
-第二十讲 死锁和进程通信--20.5 进程通信概念
-20.6 信号和管道
-第二十讲 死锁和进程通信--20.6 信号和管道
-20.7 消息队列和共享内存
-第二十讲 死锁和进程通信--20.7 消息队列和共享内存
-21.1 文件系统和文件
-第二十一讲 文件系统--21.1 文件系统和文件
-21.2 文件描述符
-第二十一讲 文件系统--21.2 文件描述符
-21.3 目录、文件别名和文件系统种类
-第二十一讲 文件系统--21.3 目录、文件别名和文件系统种类
-21.4 虚拟文件系统
-第二十一讲 文件系统--21.4 虚拟文件系统
-21.5 文件缓存和打开文件
-第二十一讲 文件系统--21.5 文件缓存和打开文件
-21.6 文件分配
-第二十一讲 文件系统--21.6 文件分配
-21.7 空闲空间管理和冗余磁盘阵列RAID
-第二十一讲 文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID
-22.1 总体介绍
-第二十二讲 实验八 文件系统--22.1 总体介绍
-22.2 ucore 文件系统架构
-第二十二讲 实验八 文件系统--22.2 ucore 文件系统架构
-22.3 Simple File System分析
-第二十二讲 实验八 文件系统--22.3 Simple File System分析
-22.4 Virtual File System分析
-第二十二讲 实验八 文件系统--22.4 Virtual File System分
-22.5 I/O设备接口分析
-第二十二讲 实验八 文件系统--22.5 I/O设备接口分析
-22.6 执行流程分析
-23.1 I/O特点
--视频
-第二十三讲 I/O子系统--23.1 I/O特点
-23.2 I/O结构
--816C80A0F5E3B8809C33DC5901307461
-第二十三讲 I/O子系统--23.2 I/O结构
-23.3 I/O数据传输
--C58221E14388B9DB9C33DC5901307461
-第二十三讲 I/O子系统--23.3 I/O数据传输
-23.4 磁盘调度
--567A3F1FCBFB3F4C9C33DC5901307461
-第二十三讲 I/O子系统--23.4 磁盘调度
-23.5 磁盘缓存
--C327536B80D25CE79C33DC5901307461
-第二十三讲 I/O子系统--23.5 磁盘缓存
-html
--html
