《第7讲死锁与银行家算法(57页PPT).pptx》由会员分享，可在线阅读，更多相关《第7讲死锁与银行家算法(57页PPT).pptx（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、操作系统华软软件学院软件工程系P1第七讲死锁与银行家算法华软软件工程系华软软件工程系操作系统华软软件学院软件工程系P2内容回顾操作系统概述进程及进程间的通信软中断、管道通信IPC机制、消息缓冲通信、共享内存通信、信机制、消息缓冲通信、共享内存通信、信号量集号量集(PV操作操作)本次课内容资源分配、死锁（银行家算法）主要内容操作系统华软软件学院软件工程系P3第一部分内容回顾OSOS概述概述用户界面用户界面进程进程进程间通信进程间通信主要内容主要内容操作系统华软软件学院软件工程系P4内容回顾操作系统概述从概念上讲述了操作系统的内涵从类型上介绍了操作系统的分类从技术上了解了操作系统的基础从技术上了解
2、了操作系统的基础用户界面介绍了各种操作界面(interface)程序界面：系统提供给编程人员的接口，也称系统调用界面。操作系统华软软件学院软件工程系P5内容回顾(2)进程进程 重点理解进程的概念：重点理解进程的概念：程序的一次运行过程程序的一次运行过程 理解进程控制块理解进程控制块PCBPCB的结构（的结构（UnixUnix、LinuxLinux）以及作用）以及作用 掌握进程的三种基本状态及其转换，以及进程的创建、撤销、睡掌握进程的三种基本状态及其转换，以及进程的创建、撤销、睡眠、唤醒眠、唤醒 掌握进程的同步与互斥，包括临界资源的概念掌握进程的同步与互斥，包括临界资源的概念进程间通信进程间通信
3、 软中断信号机制、管道通信（软中断信号机制、管道通信（分类分类）IPCIPC机制（机制（消息缓冲、共享内存、信号量集消息缓冲、共享内存、信号量集）掌握这些对象的创建、使用、撤销等操作掌握这些对象的创建、使用、撤销等操作针对信号量集，需掌握信号量的针对信号量集，需掌握信号量的PVPV操作操作操作系统华软软件学院软件工程系P6第二部分死锁与银行家算法资源分配资源分配死锁死锁处理机的多级调度处理机的多级调度作业调度作业调度进程调度进程调度主要内容主要内容操作系统华软软件学院软件工程系P7资源分配资源分配的基本概念系统中所有进程系统中所有进程共享共享并并竞争竞争系统中的所有资源系统中的所有资源操作系统
4、对其所有的资源进行统一操作系统对其所有的资源进行统一管理管理和和分配分配用户进程提出资源需求用户进程提出资源需求申请申请，系统采用某种合理，系统采用某种合理的规则的规则分配分配资源资源目的：满足所有进程对资源的需求，并使系统资目的：满足所有进程对资源的需求，并使系统资源的利用率达到最高源的利用率达到最高资源竞争的结果提高资源的利用率提高资源的利用率导致系统死锁导致系统死锁操作系统华软软件学院软件工程系P8资源分配(2)资源管理和分配的目标保证资源有高的利用率保证资源有高的利用率在合理的时间内在合理的时间内,使各进程有获取所需资源的机会使各进程有获取所需资源的机会对对“不可共享不可共享”的资源实
5、行的资源实行互斥互斥使用使用防止因资源的不合理分配引起系统死锁防止因资源的不合理分配引起系统死锁资源分配的基本方法静态资源分配：指静态资源分配：指作业作业级的资源分配。作业开始级的资源分配。作业开始分配资源，作业结束释放资源。利用率低。分配资源，作业结束释放资源。利用率低。动态资源分配：指动态资源分配：指进程进程级的资源分配。请求时分级的资源分配。请求时分配，使用完释放。利用率高。配，使用完释放。利用率高。操作系统华软软件学院软件工程系P9死锁死锁的基本概念一组进程中，每个进程都每个进程都无限等待被该组进程中另无限等待被该组进程中另一进程所占有的资源一进程所占有的资源,因而永远无法得到的资源,
6、这种现象称为进程死锁进程死锁,这一组进程称为死锁进程产生死锁的原因产生死锁的原因系统资源不足系统资源不足进程推进的顺序不合理进程推进的顺序不合理进程死锁举例进程死锁举例打印机打印机摄像头摄像头进程进程A进程进程B占有占有占有占有等待等待等待等待操作系统华软软件学院软件工程系P10死锁(2)产生死锁的必要条件：互斥互斥:临界资源为互斥使用临界资源为互斥使用不可剥夺不可剥夺(非抢占非抢占)：一旦占有就直到使用完毕：一旦占有就直到使用完毕,由由进程释放进程释放部分分配部分分配：允许部分申请，系统可部分分配：允许部分申请，系统可部分分配环路（循环等待）环路（循环等待）：各进程对资源的占有和请求：各进程
7、对资源的占有和请求形成环路形成环路解决死锁：破坏4个必要条件中的任何一个“互斥互斥”条件一般是资源本身的特性，很难破坏条件一般是资源本身的特性，很难破坏一般从破坏其他三个条件考虑解决方案一般从破坏其他三个条件考虑解决方案操作系统华软软件学院软件工程系P11死锁的处理方法（1）预防死锁：通过某些限制条件的设置，去破坏产生死锁的四个必要条件；（2）避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态；（3）检测死锁：及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施清除死锁；（4）解除死锁：撤消或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。操作系统华软软件学
8、院软件工程系P12预防死锁破坏环路条件（静态资源分配）有序资源分配法：要求将资源编号，资源请求只能按编号递增进行。举例：有资源R1、R2、R3，比如有A、B两进程都请求R1、R2资源，必须先申请R1，成功后才可申请R2缺点：不方便使用、资源利用率低操作系统华软软件学院软件工程系P13因此采用静态预防的方式来解决死锁问题牺牲的方式来解决死锁问题牺牲了资源的利用率，而资源利用率的降低直接了资源的利用率，而资源利用率的降低直接导致并发度的降低。为了保证资源的利用率，操作系统往往采用动态分配方式来避免死锁。死锁避免是指操作系统在动态分配过程中对每是指操作系统在动态分配过程中对每一次的分配都要采取某种策
9、略去判断一下当前的一次的分配都要采取某种策略去判断一下当前的分配有没有导致死锁的可能性，没有则实施分配，分配有没有导致死锁的可能性，没有则实施分配，有则拒绝分配，从而动态地避免死锁的产生。有则拒绝分配，从而动态地避免死锁的产生。操作系统华软软件学院软件工程系P14避免死锁银行家算法设银行家有10万周转资金，P,Q,R分别需要8,3,9万元搞项目，如果P已申请到了4万，Q要申请2万，R要申请4万.Q1：客户要求分期贷款，一旦得到每期贷款，就能够归还贷款Q2：银行家应谨慎的贷款，防止出现坏帐什么是银行家问题？什么是银行家问题？银行家-操作系统 周转资金-系统资源 贷款客户-进程当某进程请求分配资源
10、时，系统假定先分配给它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待。银行家算法的实现思想银行家算法的实现思想操作系统华软软件学院软件工程系P15算法原理我们可以把我们可以把操作系统操作系统看作是银行家，操作系统管理的看作是银行家，操作系统管理的资源相当于资源相当于银银行家管理的行家管理的资金资金，进程向操作系统请求分配资源相当于用户向银行家，进程向操作系统请求分配资源相当于用户向银行家贷款。贷款。为保证资金的安全，银行家规定：为保证资金的安全，银行家规定：(1)(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可当一个顾客对资金的最
11、大需求量不超过银行家现有的资金时就可接纳该顾客；接纳该顾客；(2)(2)顾客可以分期贷款，但贷款的总数不能超过最大需求量；顾客可以分期贷款，但贷款的总数不能超过最大需求量；(3)(3)当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；(4)(4)当顾客得到所需的全部资金后，一定能在有限的时间里归还所有当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金的资金.操作系统华软软件学院软件工程系P16表表 示示 形形 式式含含
12、 义义AvailableAvailable（可用资源数组）可用资源数组）Available j Available j k k现有资源现有资源 j j 的数目为的数目为 k k Max（最大需求矩阵）最大需求矩阵）Max i,j Max i,j k k进程进程 i i 对资源对资源 j j 的最大需的最大需求数目为求数目为 k k Allocation（分配矩阵）分配矩阵）Allocation i,j Allocation i,j k k进程进程 i i 当前已分得的资源当前已分得的资源 j j 的数目为的数目为 k kNeed（需求矩阵）需求矩阵）Need i,j Need i,j k k进
13、程进程 i i 尚需分配的资源尚需分配的资源 j j 的数目为的数目为 k k银行家算法中的数据结构操作系统华软软件学院软件工程系P17银行家算法银行家算法当当PiPi发出资源请求，发出资源请求，分配一个分配一个RequestRequest向量向量然后系统按下述流程进行执行：然后系统按下述流程进行执行：Requesti：是进程Pi的请求向量如果Requestij=K，表示进程i需要K个Rj类型的资源。银行家算法实现过程操作系统华软软件学院软件工程系P18操作系统华软软件学院软件工程系P19安全性算法实现过程安全性算法安全性算法两个向量：Work和FinishWork表示系统可提供给进程继续运行
14、所需的各类资源数目（即在分配过程中，系统的可用资源数）。初始值 Work=Available;Finish表示系统是否有足够的资源分配给进程i，使之运行完成。初始值 Finishi:=false当有足够资源分配给进程时 Finishi:=true操作系统华软软件学院软件工程系P20操作系统华软软件学院软件工程系P21 假假定定系系统统中中有有五五个个进进程程P P0 0,P P1 1,P P2 2,P P3 3,P P4 4和和三三类类资资源源A,A,B,B,C C，各各种种资资源源的的数数量量分分别别为为1010、5 5、7 7，在在T T0 0时时刻刻的的资资源源分分配配情情况况如下图所示
15、。如下图所示。P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24,3,34,3,30,1,00,1,02,0,02,0,03,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,31,2,21,2,26,0,06,0,00,1,10,1,14,3,1
16、4,3,13,3,23,3,2银行家算法实例操作系统华软软件学院软件工程系P22（1 1）T T0 0时刻系统是否安全？时刻系统是否安全？时刻系统是否安全？时刻系统是否安全？执行安全性算法进行检查：执行安全性算法进行检查：执行安全性算法进行检查：执行安全性算法进行检查：向量初值向量初值向量初值向量初值 Work:Work:AvailableAvailable(3,3,2)(3,3,2)；Finish i:Finish i:falsefalse；（；（；（；（i i0,1,40,1,4）在进程集合中找到在进程集合中找到在进程集合中找到在进程集合中找到 NeedNeed1 1(1,2,2)(1,2
17、,2)WorkWork 且且且且 Finish 1 Finish 1 falsefalse；则设则设则设则设 P P1 1 顺利执行完成，从而有：顺利执行完成，从而有：顺利执行完成，从而有：顺利执行完成，从而有：Work:Work:WorkWorkAllocationAllocation1 1 (3,3,2)(3,3,2)(2,0,0)(2,0,0)(5,3,2)(5,3,2)Finish 1:Finish 1:truetrue银行家算法实例操作系统华软软件学院软件工程系P23Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishF
18、inishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue5 3 22 0 01 2 23 3 2P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1操作系统华软软件学院软件工程系P24Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAll
19、ocationAllocationNeedNeedWorkWorktrue7 4 35 3 22 1 10 1 1P3true5 3 22 0 01 2 23 3 2P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1操作系统华软软件学院软件工程系P25Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAlloc
20、ationNeedNeedWorkWorktrue7 5 37 4 30 1 07 4 3true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P3P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1操作系统华软软件学院软件工程系P26Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationA
21、llocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1操作系统华软软件学院软件工程系P27Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁Al
22、locationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1true10 5 70 0 24 3 110 5 5P4FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P1操作系
23、统华软软件学院软件工程系P28发现：目前可执行的所有资源分配工作完成之后，发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量各个进程对应的状态向量 Finish i Finish i truetrue；且对应且对应于该向量置为于该向量置为“true”true”的进程编号依次为：的进程编号依次为：1 1 33 00 2 2 4 4，故：，故：系统存在安全序列系统存在安全序列 P P1 1，P P3 3，P P0 0，P P2 2，P P4 4 所以，所以，T T0 0 时刻系统处于安全状态！时刻系统处于安全状态！银行家算法实例操作系统华软软件学院软件工程系P29Chapter 3
24、 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁 由分析知：执行完由分析知：执行完由分析知：执行完由分析知：执行完 P P1 1、P P3 3 的资源分配请求之后，系统可的资源分配请求之后，系统可的资源分配请求之后，系统可的资源分配请求之后，系统可用的资源数量可以满足其它用的资源数量可以满足其它用的资源数量可以满足其它用的资源数量可以满足其它 3 3 个进程的资源请求，则此个进程的资源请求，则此个进程的资源请求，则此个进程的资源请求，则此时的资源分配顺序已无关紧要。所以：时的资源分配顺序已无关紧要。所以：时的资源分配顺序已无关紧要。所以：时的资源分配顺序已
25、无关紧要。所以：安全序列可以不唯一安全序列可以不唯一安全序列可以不唯一安全序列可以不唯一！true10 5 70 0 24 3 110 5 5P4FinishFinishWork+AllocatioWork+Allocation nAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P1操作系统华软软件学院软件工程系P30（2 2）P P1 1 发出请求发出请求发出请求发
26、出请求Request(1,0,2)Request(1,0,2)，系统能分配资源吗？，系统能分配资源吗？，系统能分配资源吗？，系统能分配资源吗？执行银行家算法：执行银行家算法：执行银行家算法：执行银行家算法：RequestRequest1 1(1,0,2)(1,0,2)NeedNeed1 1(1,2,2)(1,2,2)；Request Request1 1(1,0,2)(1,0,2)Available(3,3,2)Available(3,3,2)；系统为系统为系统为系统为P P1 1进行进行进行进行预分配预分配预分配预分配，并修改，并修改，并修改，并修改AvailableAvailable，Al
27、locationAllocation1 1 和和和和 NeedNeed1 1向量：向量：向量：向量：银行家算法实例RequestRequest1 1(1,0,2)(1,0,2)，NeedNeed1 1，Available Available 操作系统华软软件学院软件工程系P31 Available:Available:AvailableAvailableRequestRequest1 1 (3,3,2)(3,3,2)(1,0,2)(1,0,2)(2,3,0)(2,3,0)Allocation Allocation1 1:AllocationAllocation1 1RequestRequest
28、1 1 (2,0,0)(2,0,0)(1,0,2)(1,0,2)(3,0,2)(3,0,2)Need Need1 1:NeedNeed1 1RequestRequest1 1 (1,2,2)(1,2,2)(1,0,2)(1,0,2)(0,2,0)(0,2,0)银行家算法实例操作系统华软软件学院软件工程系P32Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishAvailableAvailableAllocationAllocationNeedNeedWorkWorktrue5 3 23 0 20 2 02 3 0P1P
29、 P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24,3,34,3,30,1,00,1,03 3,0,0,2 23,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,30 0,2,2,0 06,0,06,0,00,1,10,1,14,3,14,3,12
30、 2,3,3,0操作系统华软软件学院软件工程系P33Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishAvailableAvailableAllocationAllocationNeedNeedWorkWorktrue7 4 32 1 1true5 3 23 0 20 2 02 3 0P1P35 3 20 1 1P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B
31、,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24,3,34,3,30,1,00,1,03 3,0,0,2 23,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,30 0,2,2,0 06,0,06,0,00,1,10,1,14,3,14,3,15,3,2操作系统华软软件学院软件工程系P34Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishAvailableAvailabl
32、eAllocationAllocationNeedNeedWorkWorktrue7 5 30 1 07 4 37 4 3true7 4 32 1 1true5 3 23 0 20 2 02 3 0P0P1P35 3 20 2 0P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,
33、2,24,3,34,3,30,1,00,1,03 3,0,0,2 23,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,30 0,2,2,0 06,0,06,0,00,1,10,1,14,3,14,3,17,4,3操作系统华软软件学院软件工程系P35Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishAvailableAvailableAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 2
34、6 0 0true7 4 32 1 1true5 3 23 0 20 2 02 3 0P0P2P1P35 3 20 2 0P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24,3,34,3,30,1,00,1,03 3,0,0,2 23,0,23,0,22,1,12,1,1
35、0,0,20,0,27,4,37,4,30 0,2,2,0 06,0,06,0,00,1,10,1,14,3,14,3,17,5,3操作系统华软软件学院软件工程系P36Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁true10 5 70 0 24 3 110 5 5P4FinishFinishAvailableAvailableAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 1true5 3
36、 23 0 20 2 02 3 0P0P2P1P35 3 20 2 0P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24,3,34,3,30,1,00,1,03 3,0,0,2 23,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,30 0,2,
37、2,0 06,0,06,0,00,1,10,1,14,3,14,3,110,5,5操作系统华软软件学院软件工程系P37Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24
38、,3,34,3,30,1,00,1,03 3,0,0,2 23,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,30 0,2,2,0 06,0,06,0,00,1,10,1,14,3,14,3,110,5 5,7 7 执行安全性算法检查时，仍能够得到安全序列 P1，P3，P0，P2，P4，故请求向量 Request1(1,0,2)发出时系统安全！操作系统华软软件学院软件工程系P38分配后资源P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllo
39、cationA,B,CA,B,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24,3,34,3,30,1,00,1,03 3,0,0,2 23,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,30 0,2,2,0 06,0,06,0,00,1,10,1,14,3,14,3,12,3,0操作系统华软软件学院软件工程系P39（3 3）P P4 4发出请求发出请求发出请求发出请求Request(3,2,1)Request(3,2,1)，系统能分配资源吗？，系
40、统能分配资源吗？，系统能分配资源吗？，系统能分配资源吗？执行银行家算法进行检查：执行银行家算法进行检查：执行银行家算法进行检查：执行银行家算法进行检查：Request4(3,2,0)Need4(4,3,1)；Request4(3,2,1)Available(2,3,0)故：故：P4 资源请求失败，让其等待！资源请求失败，让其等待！银行家算法实例操作系统华软软件学院软件工程系P40分配后资源P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,CA,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B
41、,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24,3,34,3,30,1,00,1,03 3,0,0,2 23,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,30 0,2,2,0 06,0,06,0,00,1,10,1,14,3,14,3,12,3,0 0操作系统华软软件学院软件工程系P41（4 4）P P0 0发出请求发出请求发出请求发出请求Request(0,2,0)Request(0,2,0)，系统能分配资源吗？，系统能分配资源吗？，系统能
42、分配资源吗？，系统能分配资源吗？执行银行家算法进行检查：执行银行家算法进行检查：执行银行家算法进行检查：执行银行家算法进行检查：Request0(0,2,0)(0,2,0)Need0(7,4,3)(7,4,3)；Request0(0,2,0)Available(2,3,0)；系统为系统为 P0 0 作预分配，并修改有关数据：作预分配，并修改有关数据：作预分配，并修改有关数据：作预分配，并修改有关数据：银行家算法实例操作系统华软软件学院软件工程系P42 Available:Available:AvailableAvailableRequest0Request0 (2,3,0)(2,3,0)(0,
43、2,0)(0,2,0)(2,1,0)(2,1,0)Allocation0:Allocation0:Allocation0Allocation0Request0 Request0 (0,1,0)(0,1,0)(0,2,0)(0,2,0)(0,3,0)(0,3,0)Need0:Need0:Need0Need0Request0Request0 (7,4,3)(7,4,3)(0,2,0)(0,2,0)(7,2,3)(7,2,3)银行家算法实例操作系统华软软件学院软件工程系P43MaxMaxAllocationAllocationNeedNeedAvailableAvailableP07 5 30 3
44、07 2 32 1 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1 显然，对于所有进程，条件显然，对于所有进程，条件NeedNeedi iAvailableAvailable，均不成立。因，均不成立。因此，此，P P0 0 此次资源请求预分配的结果，使系统进入不安全状态，此次资源请求预分配的结果，使系统进入不安全状态，故应撤消此次预分配。故应撤消此次预分配。银行家算法实例操作系统华软软件学院软件工程系P44死锁的检测和恢复死锁的检测和恢复检查方法：检查方法：类似于银行家算法，如果某时刻不是所有进程都进类
45、似于银行家算法，如果某时刻不是所有进程都进入安全序列，这些进程将发生死锁入安全序列，这些进程将发生死锁恢复方法：将产生死锁的进程全部撤销将产生死锁的进程全部撤销逐个撤销死锁的进程，直至死锁解除逐个撤销死锁的进程，直至死锁解除从发生死锁的进程中剥夺其占有的资源，破坏死锁的从发生死锁的进程中剥夺其占有的资源，破坏死锁的“不可剥夺不可剥夺”条件。条件。操作系统华软软件学院软件工程系P45饿死饿死是死锁的另一种表现形式。假设有三个进程：Pa、Pb、Pc，每个进程都周期性地访问资源R。存在这样一种情况：Pa拥有资源R，Pb、Pc等待。当Pa退出它的临界区时，Pc获得资源R。在Pc退出临界区前，Pa又请求
46、资源R。在Pc退出临界区时，Pa又夺得资源R。Pb始终得不到资源R。从而产生饿死。操作系统华软软件学院软件工程系P46实验设父进程创建1个子进程作为生产者，创建2个子进程作为消费者。这3个子进程使用一个共享内存，该共享内存定义为具有5个变量的数组，每个变量表示一个缓冲区，缓冲区号为0-4。生产者进程依次往缓冲区0-4中写10个数据0-9，两个读进程依次从缓冲区0-4中轮流取出这10个数据。使用信号量实现进程读写缓冲区的同步和互斥。操作系统华软软件学院软件工程系P47分析与思考需要创建几个子进程？说明每个子进程的角色。需要几个信号量？初值分别为多少？有何作用？需要几个共享内存？含义是什么？依据题
47、意：请说明进程互斥体现在哪里？通过信号量如何实现？进程同步又体现在哪里？P、V操作如何设置？操作系统华软软件学院软件工程系P48分析1.需要创建3个子进程生产者、消费者A、消费者B。2.需要使用3个信号量empty full mutex分别表示缓冲区是否有空、是否有数和互斥信号量，其初值分别为5 0 13.需要2个共享内存array get,分别表示多缓冲区数组变量array0-4和消费者读缓冲区号的计数get get计数由两个消费者进程共享，由于只有一个生产者，所以写缓冲区的计数变量set不需要使用共享内存。操作系统华软软件学院软件工程系P49编程解题思路创建共享内存；创建共享内存；附接到共
48、享内存；附接到共享内存；创建信号量并赋初值；创建信号量并赋初值；定义定义P P、V V操作操作if(fork()=0)/if(fork()=0)/该子进程为发送进程该子进程为发送进程/添加发送程序段添加发送程序段 elseelse if(fork()=0)/if(fork()=0)/该子进程为接收进程该子进程为接收进程/添加接收程序段添加接收程序段 elseelseif(fork()=0)/if(fork()=0)/该子进程为发送进程该子进程为发送进程/添加发送程序段添加发送程序段 else/else/父进程程序段父进程程序段 操作系统华软软件学院软件工程系P50源代码操作系统华软软件学院软件
49、工程系P51源代码操作系统华软软件学院软件工程系P52源代码操作系统华软软件学院软件工程系P53源代码操作系统华软软件学院软件工程系P54运行结果操作系统华软软件学院软件工程系P55运行结果由运行结果看出，生产者进程分别往缓冲区0-4中送了10次产品，消费者进程A和B轮流从缓冲区0-4中取走产品，并且一次只有一个进程进入缓冲区。本实验中，生产者进程结束后需要延时几秒钟来等待消费者进程取走最后的数据，否则可能出现死锁。操作系统华软软件学院软件工程系P56谢 谢！认真完成本章小课实验认真完成本章小课实验先预习再听课，否则跟不上先预习再听课，否则跟不上其他提醒其他提醒 提提 醒醒1、每一个成功者都有
50、一个开始。勇于开始，才能找到成功的路。11月-2211月-22Tuesday,November 8,20222、成功源于不懈的努力，人生最大的敌人是自己怯懦。06:14:5306:14:5306:1411/8/2022 6:14:53 AM3、每天只看目标，别老想障碍。11月-2206:14:5306:14Nov-2208-Nov-224、宁愿辛苦一阵子，不要辛苦一辈子。06:14:5306:14:5306:14Tuesday,November 8,20225、积极向上的心态，是成功者的最基本要素。11月-2211月-2206:14:5306:14:53November 8,20226、生活总