第5章进程同步与互斥课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第5章进程同步与互斥课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 进程 同步 课件
- 资源描述:
-
1、u并发()是多道程序技术、多处理技术、分布式处并发()是多道程序技术、多处理技术、分布式处理技术的基础,也是设计的重点理技术的基础,也是设计的重点u资源的共享和争用资源的共享和争用u多个进程活动的同步多个进程活动的同步u分配给进程的处理器时间等。分配给进程的处理器时间等。u单处理器,多单处理器,多道程序:交错道程序:交错多处理器,多道程序:交错和重叠多处理器,多道程序:交错和重叠设的当前值为:设的当前值为:.若执行顺序为:若执行顺序为:先先;后后;则结果:则结果:.若执行顺序为:若执行顺序为::();:();:;:;:();:();则结果则结果 分析:产生错误的原因是不加控制地访问共享变量分析
2、:产生错误的原因是不加控制地访问共享变量 ;getcopyputfstg复制一个记录复制一个记录源记录源记录目标记录目标记录并发环境下进程间的制约关系并发环境下进程间的制约关系u不加控制地访问共享资源会出现问题不加控制地访问共享资源会出现问题,要求控制对共享资源的访问!,要求控制对共享资源的访问!进程的同步(直接制约):进程的同步(直接制约):指系统中一些进程需要相互合作,共同完成一项指系统中一些进程需要相互合作,共同完成一项任务。具体说,一个进程运行到某一点时要求任务。具体说,一个进程运行到某一点时要求另一伙伴进程为它提供消息,在未获得消息之另一伙伴进程为它提供消息,在未获得消息之前,该进程
3、处于等待状态,获得消息后被唤醒前,该进程处于等待状态,获得消息后被唤醒进入就绪态进入就绪态进程的互斥(间接制约)进程的互斥(间接制约)由于各进程要求共享资源,而有些资源需要互由于各进程要求共享资源,而有些资源需要互斥使用,因此各进程间竞争使用这些资源,进斥使用,因此各进程间竞争使用这些资源,进程的这种关系为进程的互斥程的这种关系为进程的互斥u相关概念:相关概念:u 互斥:指多个进程不能同时使用同一个资源;互斥:指多个进程不能同时使用同一个资源;u 死锁:指多个进程互不相让,都得不到足够的资源;死锁:指多个进程互不相让,都得不到足够的资源;u 饥饿:指一个进程一直得不到资源(其他进程可能轮流饥饿
4、:指一个进程一直得不到资源(其他进程可能轮流占用资源)占用资源)u 临界资源:系统中某些资源一次只允许一个进程使用,临界资源:系统中某些资源一次只允许一个进程使用,称这样的资源为临界资源或互斥资源或共享变量称这样的资源为临界资源或互斥资源或共享变量u 临界区:进程中访问临界资源的一段代码。临界区:进程中访问临界资源的一段代码。临界区问题临界区问题进入区进入区退出区退出区临界区临界区剩余区剩余区u临界区临界区():进程中访问临界资源的:进程中访问临界资源的一段代码。一段代码。u进入区进入区():在进入临界区之前,检:在进入临界区之前,检查可否进入临界区的一段代码。查可否进入临界区的一段代码。如果
5、可以进入临界区,通常设置如果可以进入临界区,通常设置相应相应正在访问临界区正在访问临界区标志标志u退出区退出区():用于将:用于将正在访问临界正在访问临界区区标志清除。标志清除。u剩余区剩余区():代码中的其余部分。:代码中的其余部分。u内核在执行某些基本操作时内核在执行某些基本操作时,往往利用原语操作实现往往利用原语操作实现u原语原语u是一种广义指令是一种广义指令,相当于扩充了机器指令集相当于扩充了机器指令集u原语是由若干条指令构成、用于完成一定功能的一原语是由若干条指令构成、用于完成一定功能的一个过程个过程.u原语是原子操作原语是原子操作()u原子操作原子操作:u一个操作中的所有动作一个操
6、作中的所有动作,要么全做要么全做,要么全不做要么全不做.u原子操作是一个不可分割的操作原子操作是一个不可分割的操作u使用临界区应遵循的准则使用临界区应遵循的准则u有空让进:当无进程在临界区时,任何有权使用临界有空让进:当无进程在临界区时,任何有权使用临界区的进程可进入区的进程可进入u无空等待:不允许两个以上的进程同时进入临界区无空等待:不允许两个以上的进程同时进入临界区u多中择一:当没有进程在临界区,而同时有多个进程多中择一:当没有进程在临界区,而同时有多个进程要求进入临界区,只能让其中之一进入临界区,其他要求进入临界区,只能让其中之一进入临界区,其他进程必须等待进程必须等待u有限等待:任何进
7、入临界区的要求应在有限的时间内有限等待:任何进入临界区的要求应在有限的时间内得到满足得到满足u让权等待:处于等待状态的进程应放弃占用让权等待:处于等待状态的进程应放弃占用u平等竞争:任何进程无权停止其它进程的运行进程之平等竞争:任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定间相对运行速度无硬性规定u实现互斥的方法实现互斥的方法u软件方法软件方法u硬件方式:利用专门机器指令硬件方式:利用专门机器指令u特点特点u无需硬件、和程序设计语言的支持无需硬件、和程序设计语言的支持u处理开销大处理开销大,容易出错容易出错u学习的意义学习的意义u更好地理解并发处理的复杂性更好地理解并发处理的复杂
8、性u适用范围适用范围u单处理器系统单处理器系统u共享主存的多处理系统共享主存的多处理系统u前提假设前提假设:存储器级的访问是互斥的存储器级的访问是互斥的u报告了(荷兰数学家)设计的算法报告了(荷兰数学家)设计的算法u尝试:单标志尝试:单标志u有两个进程有两个进程,,设立一个共享全局整型变量,设立一个共享全局整型变量:描述允许进入:描述允许进入临界区的进程标识临界区的进程标识u在进入区循环检查是否允许本进程进入:为在进入区循环检查是否允许本进程进入:为 时,进程可进入时,进程可进入;u在退出区修改允许进入进程标识:进程退出时,改为进程的在退出区修改允许进入进程标识:进程退出时,改为进程的标识;标
9、识;u 优点:保持了互斥的特性优点:保持了互斥的特性u 缺点:缺点:u严格轮流使用临界区,限制推进速度,由执行较慢的进程决严格轮流使用临界区,限制推进速度,由执行较慢的进程决定定u容易造成资源利用不充分:在出让临界区之后,使用临界区容易造成资源利用不充分:在出让临界区之后,使用临界区之前,不可能再次使用临界区;之前,不可能再次使用临界区;u如果一个进程失败了,另一个进程将被永久阻塞如果一个进程失败了,另一个进程将被永久阻塞u忙等待忙等待():为了等待一事件的发生为了等待一事件的发生,重复执行一段循环代码重复执行一段循环代码 白白消耗时间白白消耗时间u设立一个标志数组设立一个标志数组:描述进程是
10、否在临界区,初值均为,:描述进程是否在临界区,初值均为,它是进程到达临界区的钥匙它是进程到达临界区的钥匙u先检查,后修改:在进入区中,检查另一个进程是否在临界先检查,后修改:在进入区中,检查另一个进程是否在临界区,不在临界区时修改本进程在临界区的标志;区,不在临界区时修改本进程在临界区的标志;u在退出区修改本进程在临界区的标志;在退出区修改本进程在临界区的标志;u优点:不用交替进入,可连续使用;优点:不用交替进入,可连续使用;u缺点:缺点:u不能保证互斥!不能保证互斥!和和 可能同时进入临界区。在可能同时进入临界区。在 和和 都不在临界区时,假设按下面序列执行时,会同都不在临界区时,假设按下面
11、序列执行时,会同时进入:时进入:“;”。即在检查对方之后。即在检查对方之后和切换自己和切换自己 之前有一段时间,结果都检查通过。之前有一段时间,结果都检查通过。这里的问题出在检查和修改操作不能连续进行。这里的问题出在检查和修改操作不能连续进行。u一个进程在临界区内失败一个进程在临界区内失败,另一进程永远被阻塞另一进程永远被阻塞u优点:类似于算法,与算法的区别在于先修改、后优点:类似于算法,与算法的区别在于先修改、后检查。可防止两个进程同时进入临界区,实现互斥检查。可防止两个进程同时进入临界区,实现互斥。u缺点:和可能都进入不了临界区。在和都不在临界缺点:和可能都进入不了临界区。在和都不在临界区
12、时,假设按下面序列执行,则都进不了临界区:区时,假设按下面序列执行,则都进不了临界区:“”。即在切换自己的之后和检查对方。即在切换自己的之后和检查对方之前有一段时间,结果都切换,都检查不通过。之前有一段时间,结果都切换,都检查不通过。u思路:使每个进程更礼让一些:每思路:使每个进程更礼让一些:每个进程设置自己的,表明自己想进个进程设置自己的,表明自己想进入自己的临界区,但也准备重置,入自己的临界区,但也准备重置,以尊重另一个进程。以尊重另一个进程。u优点:保证互斥优点:保证互斥u缺点:缺点:u出现活锁:一组进程都想进入它们出现活锁:一组进程都想进入它们的临界区,但没有一个能成功进入的临界区,但
13、没有一个能成功进入(不是死锁,因为两个进程相对速(不是死锁,因为两个进程相对速度的任何改变都会打破这种情形)度的任何改变都会打破这种情形)u可能成功进入,也可能有使得任何可能成功进入,也可能有使得任何进程都不能进入临界区的执行顺序进程都不能进入临界区的执行顺序。将将置为置为将将置为置为检查检查检查检查将将置为置为将将置为置为将将置为置为将将置为置为.此序列无限延伸,此序列无限延伸,任何一个进程都不能进入任何一个进程都不能进入自己的临界区自己的临界区u避免避免“无原则无原则”的礼让的礼让u规定在都想进入时的进入顺序规定在都想进入时的进入顺序u表示每个进程关于互斥的位置,解决同时进入时的冲突表示每
14、个进程关于互斥的位置,解决同时进入时的冲突问题问题u:描述可进入的进程(同时修改标志时):描述可进入的进程(同时修改标志时)u在进入区先修改后检查,并检查并发修改的先后:在进入区先修改后检查,并检查并发修改的先后:u检查对方,如果不在临界区则自己进入空闲则入检查对方,如果不在临界区则自己进入空闲则入u否则再检查:保存的是较晚的一次赋值,则较晚的进程否则再检查:保存的是较晚的一次赋值,则较晚的进程等待,较早的进程进入先到先入,后到等待等待,较早的进程进入先到先入,后到等待flagi=TRUE;turn=j;while(flagj&turn=j);critical sectionflagi=FAL
15、SE;remainder sectionu算法解决了互斥问题算法解决了互斥问题,但比较复杂,证明,但比较复杂,证明起来也比较困难。起来也比较困难。u提出一种简单的方案提出一种简单的方案。u.中断禁用中断禁用(关中断关中断,)u单处理器系统单处理器系统,并发进程交替执行而不重叠并发进程交替执行而不重叠u一个进程一直运行,直到调用了一个服务或被中断一个进程一直运行,直到调用了一个服务或被中断u如果进程访问临界资源时如果进程访问临界资源时(执行临界区代码执行临界区代码)不被中不被中断断,就可以利用它来保证互斥地访问就可以利用它来保证互斥地访问u途径途径:使用关中断原语、开中断原语使用关中断原语、开中
16、断原语u过程过程:关中断原语关中断原语;u临界区临界区u开中断原语开中断原语u其余部分其余部分u存在问题存在问题u代价高:限制了处理器交替执行各进程的能力代价高:限制了处理器交替执行各进程的能力u不能用于多处理器结构:关中断不能保证互斥不能用于多处理器结构:关中断不能保证互斥u.专门的机器指令专门的机器指令u设计一些机器指令,用于保证两个动作的原设计一些机器指令,用于保证两个动作的原子性子性,如在一个指令周期中实现测试和修改,如在一个指令周期中实现测试和修改u()指令指令u指令指令u指令定义指令定义(逻辑逻辑)u()()u u ()()u u ;u ;u u u ;u u 使用实现互斥使用实现
17、互斥 ;()()()什么都不做什么都不做 临界区临界区;剩余区剩余区 ();()(),()指令定义:指令定义:(,);do key=1;while(key!=0)Swap(lock,key);/*临界区临界区*/lock=0;剩余区剩余区while(1);u优点优点u适用于单处理器或共享主存的多处理器系统适用于单处理器或共享主存的多处理器系统,进程数目进程数目任意任意u简单且易于证明简单且易于证明u可以使用多个变量支持多个临界区,只需为每个临界可以使用多个变量支持多个临界区,只需为每个临界区设立一个布尔变量区设立一个布尔变量u缺点缺点u忙等待:当一个进程正在等待进入一个临界区时,继忙等待:当一
18、个进程正在等待进入一个临界区时,继续消耗处理器时间。续消耗处理器时间。u可能饿死:任意选择等待的进程,有的可能一直选不可能饿死:任意选择等待的进程,有的可能一直选不上上u可能死锁:高优先级进程等待处于阻塞状态的低优先可能死锁:高优先级进程等待处于阻塞状态的低优先级进程的资源(如:进程执行或指令并进入临界区,级进程的资源(如:进程执行或指令并进入临界区,然后被阻塞,并把给具有更高优先级的然后被阻塞,并把给具有更高优先级的,若试图使用与若试图使用与相同的资源,由于互斥机制,它被拒绝访问,因此进相同的资源,由于互斥机制,它被拒绝访问,因此进入忙等待循环,又因优先级高于,所以总得不到调度入忙等待循环,
展开阅读全文