目录
1.读者—写者问题
2.哲学家进餐问题
实现
3.管程
1.为什么要引入管程?
?2.管程的定义和基本特征
3.扩展1:用管程解决生产者消费者问题
4.扩展2:Java中类似于管程的机制
1.读者—写者问题
文章图片
个人主页:个人主页
文章图片
系列专栏:操作系统
有读者和写者两组并发进程,共享一个文件,当两个或两个以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:
①允许多个读者可以同时对文件执行读操作;
②只允许一个写者往文件中写信息;
③任一写者在完成写操作之前不允许其他读者或写者工作;
④写者执行写操作前,应让已有的读者和写者全部退出。
文章图片
1.关系分析:找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
①、两类进程:写进程、读进程
②、互斥关系:写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。
2.整理思路:根据各进程的操作流程确定P、V操作的大致顺序
3.设置信号量:设置需要的信号量,并根据题目条件确定信号量初值。(互斥信号量初值一般为1,同步信号量的初始值要看对应资源的初始值是多少)
文章图片
文章图片
- 读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。
- 其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用count 的值来判断当前进入的进程是否是第一个/最后一个读进程,从而做出不同的处理。
- 另外,对 count 变量的检查和赋值不能一气呵成导致了一些错误,如果需要实现“一气呵成”,自然应该想到用互斥信号量。
- 最后,还要认真体会我们是如何解决“写进程饥饿”问题的
2.哲学家进餐问题
一张圆桌上坐着5名哲学家,每两个哲学家之间的桌上摆一根筷子,桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿时,才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上,则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续思考。
文章图片
【操作系统(王道考研)|2.7操作系统(读者—写者问题 哲学家进餐问题 管程 )】
1.关系分析。系统中有5个哲学家进程,5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2.整理思路。这个问题中只有互斥关系,但与之前遇到的问题不同的事,每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象,是哲学家问题的精髓。
3.信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}
用于实现对5个筷子的互斥访问。并对哲学家按0~4
编号,哲学家i
左边的筷子编号为i
,右边的筷子编号为(i+1)%5
。
文章图片
上边的情况是不合理的,会产生死锁问题,那么我们应该如何防止死锁的发生呢?实现 方案一
文章图片
①可以对哲学家进程施加一些限制条件,比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
方案二
②要求奇数号哲学家先拿左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭,那么只会有其中一个可以拿起第一只筷子,另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。方案三
③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。
第一种情况:第0个科学家进行进餐;在第0个科学家进餐完之前,其他科学家进程阻塞。只有当第0个科学家进餐完毕后,其他科学家才可以进餐。
文章图片
第二种情况:第0个科学家进行进餐;在第0个科学家进餐完之前,其他科学家进程阻塞。只有当第0个科学家进餐完毕后,其他科学家才可以进餐。但是如果是第0个科学家的右边的第1个科学家进餐的话会发生阻塞,并且即使第2个科学家左右两边都有筷子,也暂时无法取得。
文章图片
第三种情况:第0个科学家进行进餐;在第0个科学家进餐完之前,其他科学家进程阻塞。只有当第0个科学家进餐完毕后,其他科学家才可以进餐。但是如果是第0个科学家的左边的第4个科学家进餐的话会发生阻塞,此时第4个科学家右边的筷子不可用,但是4号仍然会先拿起左边的筷子。
文章图片
- 哲学家进餐问题的关键在于解决进程死锁。
- 这些进程之间只存在互斥关系,但是与之前接触到的互斥关系不同的是,每个进程都需要同时持有两个临界资源,因此就有“死锁”问题的隐患。
- 如果在考试中遇到了一个进程需要同时持有多个临界资源的情况,应该参考哲学家问题的思想,分析题中给出的进程之间是否会发生循环等待,是否会发生死锁。可以参考哲学家就餐问题解决死锁的三种思路。
3.管程
1.为什么要引入管程?
管程的定义和基本特征
文章图片
2.管程的定义和基本特征
3.扩展1:用管程解决生产者消费者问题
- 管程是一种特殊的软件模块,有这些部分组成:
①、局部于管程的共享数据结构说明;
②、对该数据结构进行操作的一组过程;
③、对局部于管程的共享数据设置初始值的语句;
④、管程有一个名字。- 管程的基本特征:
①、局部于管程的数据只能被局部于管程的过程所访问;
②、一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
③、每次仅允许一个进程在管程内执行某个内部过程。
文章图片
4.扩展2:Java中类似于管程的机制
- 引入管程的目的无非就是要更方便地实现进程互斥和同步。
- ①、需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
②、需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数(如生产者消费者问题中,可以定义一个函数用于将产品放入缓冲区,再定义一个函数用于从缓冲区取出产品)
③、只有通过这些特定的“入口”才能访问共享数据
④、管程中有很多“入口”,但是每次只能开放其中一个“入口”,并且只能让一个进程或线程进入(如生产者消费者问题中,各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。 注意:这种互斥特性是由编译器负责实现的,程序员不用关心 )
⑤、可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待( 此时,该进程应先释放管程的使用权,也就是让出“入口” );可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
- 程序员可以用某种特殊的语法定义一个管程(比如: monitor ProducerConsumer …… end monitor; ),之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。【“封装”思想】
Java 中,如果用关键字 synchronized 来描述一个函数,那么这个函数同一时间段内只能被一个线程调用
文章图片
文章图片
推荐阅读
- 精品推荐|编程实用工具大全(二)(前后端皆可用,不来看看())
- 模型已经写好了,怎么表白就看你的了
- 解决IDEA 2022 Translation 翻译文档失败: 未知错误的问题
- Python之创建xml文档
- Python 中有 3 个不可思议的返回功能
- linux之pkill命令
- python|python wasm_什么是 WebAssembly(wasm)()
- 我的碎碎念|真的无语,MSRA连国防七子及北邮学生都不招了
- 算法|MoCo不适用于目标检测(MSRA提出对象级对比学习的目标检测预训练方法SoCo!性能SOTA!(NeurIPS 2021)...)