第7讲死锁与银行家算法ppt课件

1、第七讲死锁与银行家算法华软软件工程系内容回想操作系统概述进程及进程间的通讯软中断、管道通讯IPC机制、音讯缓冲通讯、共享内存通讯、信号量集(PV操作)本次课内容资源分配、死锁银行家算法主要内容第一部分内容回想OS概述用户界面进程进程间通讯主要内容内容回想操作系统概述从概念上讲述了操作系统的内涵从类型上引见了操作系统的分类从技术上了解了操作系统的根底用户界面引见了各种操作界面(interface)程序界面：系统提供应编程人员的接口，也称系统调用界面。内容回想(2)进程重点了解进程的概念：程序的一次运转过程了解进程控制块PCB的构造Unix、Linux以及作用掌握进程的三种根本形状及其转换，以及进

2、程的创建、撤销、睡眠、唤醒掌握进程的同步与互斥，包括临界资源的概念进程间通讯软中断信号机制、管道通讯分类IPC机制音讯缓冲、共享内存、信号量集掌握这些对象的创建、运用、撤销等操作针对信号量集，需掌握信号量的PV操作第二部分死锁与银行家算法资源分配死锁处置机的多级调度作业调度进程调度主要内容资源分配资源分配的根本概念系统中一切进程共享并竞争系统中的一切资源操作系统对其一切的资源进展一致管理和分配用户进程提出资源需求恳求，系统采用某种合理的规那么分配资源目的：满足一切进程对资源的需求，并使系统资源的利用率到达最高资源竞争的结果提高资源的利用率导致系统死锁资源分配(2)资源管理和分配的目的保证资源有

3、高的利用率在合理的时间内,使各进程有获取所需资源的时机对“不可共享的资源实行互斥运用防止因资源的不合理分配引起系统死锁资源分配的根本方法静态资源分配：指作业级的资源分配。作业开场分配资源，作业终了释放资源。利用率低。动态资源分配：指进程级的资源分配。恳求时分配，运用完释放。利用率高。死锁死锁的根本概念一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源,因此永远无法得到的资源,这种景象称为进程死锁,这一组进程称为死锁进程产生死锁的缘由系统资源缺乏进程推进的顺序不合理进程死锁举例打印机摄像头进程A进程B占有占有等待等待死锁(2)产生死锁的必要条件：互斥:临界资源为互斥运用不可剥夺(非抢

4、占)：一旦占有就直到运用终了,由进程释放部分分配：允许部分恳求，系统可部分分配环路循环等待：各进程对资源的占有和恳求构成环路处理死锁：破坏4个必要条件中的任何一个“互斥条件普通是资源本身的特性，很难破坏普通从破坏其他三个条件思索处理方案死锁的处置方法1预防死锁：经过某些限制条件的设置，去破坏产生死锁的四个必要条件；2防止死锁：在资源的动态分配过程中，用某种方法去防止系统进入不平安形状；3检测死锁：及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施去除死锁；4解除死锁：吊销或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。预防死锁破坏环路条件静态资源分配有序资源分配法：要求将

5、资源编号，资源恳求只能按编号递增进展。举例：有资源R1、R2、R3，比如有A、B两进程都恳求R1、R2资源，必需先恳求R1，胜利后才可恳求R2缺陷：不方便运用、资源利用率低因此采用静态预防的方式来处理死锁问题牺牲了资源的利用率，而资源利用率的降低直接导致并发度的降低。为了保证资源的利用率，操作系统往往采用动态分配方式来防止死锁。死锁防止是指操作系统在动态分配过程中对每一次的分配都要采取某种战略去判别一下当前的分配有没有导致死锁的能够性，没有那么实施分配，有那么回绝分配，从而动态地防止死锁的产生。防止死锁银行家算法设银行家有10万周转资金，P, Q, R分别需求8,3,9万元搞工程，假设P已恳求

6、到了4万，Q要恳求2万，R要恳求4万.Q1：客户要求分期贷款，一旦得到每期贷款，就可以归还贷款Q2：银行家应谨慎的贷款，防止出现坏帐什么是银行家问题？银行家-操作系统 周转资金-系统资源 贷款客户-进程当某进程恳求分配资源时，系统假定先分配给它，之后假设能找到一个进程完成序列平安序列，阐明系统是平安的，可进展实践分配；否那么，让恳求者等待。银行家算法的实现思想算法原理我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统恳求分配资源相当于用户向银行家贷款。为保证资金的平安，银行家规定：(1) 当一个顾客对资金的最大需求量不超越银行家现有的资金时就可接纳该顾客；

7、(2) 顾客可以分期贷款，但贷款的总数不能超越最大需求量；(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还一切的资金.表 示 形 式含 义Available（可用资源数组）Available j k现有资源 j 的数目为 k Max（最大需求矩阵）Max i, j k进程 i 对资源 j 的最大需求数目为 k Allocation（分配矩阵）Allocation i, j k进程 i 当前已分得的资源 j 的数目为 kNeed（需求矩阵）Need i, j k进程 i

8、 尚需分配的资源 j 的数目为 k银行家算法中的数据构造银行家算法当Pi发出资源恳求，分配一个Request向量然后系统按下述流程进展执行：Requesti：是进程Pi的恳求向量假设Requestij=K，表示进程i需求K个Rj类型的资源。银行家算法实现过程平安性算法实现过程平安性算法两个向量：Work和FinishWork表示系统可提供应进程继续运转所需的各类资源数目即在分配过程中，系统的可用资源数。初始值 Work=Available;Finish表示系统能否有足够的资源分配给进程i，使之运转完成。初始值 Finishi:=false当有足够资源分配给进程时 Finishi:=true 假

9、定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时辰的资源分配情况如以下图所示。 P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 02, 0, 03, 0, 22, 1, 10, 0, 27, 4, 31, 2, 26, 0, 00, 1, 14, 3, 13, 3, 2银行家算法实例1T0时辰系统能否平安？执行平安性算法进展检查： 向量初值 Wo

10、rk :Available(3, 3, 2)； Finish i :false；i0, 1, , 4 在进程集合中找到 Need1(1, 2, 2) Work 且 Finish 1 false； 那么设 P1 顺利执行完成，从而有： Work :WorkAllocation1 (3, 3, 2)(2, 0, 0)(5, 3, 2) Finish 1 :true银行家算法实例Chapter 3 处置机调度与死锁FinishWork+AllocationAllocationNeedWorktrue5 3 22 0 01 2 23 3 2P1AllocationNeedP00 1 07 4 3P12

11、 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1Chapter 3 处置机调度与死锁FinishWork+AllocationAllocationNeedWorktrue7 4 35 3 22 1 10 1 1P3true5 3 22 0 01 2 23 3 2P1AllocationNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1Chapter 3 处置机调度与死锁FinishWork+AllocationAllocationNeedWorktrue7 5 37 4 30

12、 1 07 4 3true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P3P1AllocationNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1Chapter 3 处置机调度与死锁FinishWork+AllocationAllocationNeedWorktrue10 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 2P0P2P3P1A

13、llocationNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1Chapter 3 处置机调度与死锁AllocationNeedP00 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 5P4FinishWork+AllocationAllocationNeedWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 1

14、5 3 2true5 3 22 0 01 2 23 3 2P0P2P3P1发现：目前可执行的一切资源分配任务完成之后，各个进程对应的形状向量 Finish i true；且对应于该向量置为 “true 的进程编号依次为：1 3 0 2 4，故： 系统存在平安序列 P1，P3，P0，P2，P4 所以，T0 时辰系统处于平安形状！银行家算法实例Chapter 3 处置机调度与死锁 由分析知：执行完 P1、P3 的资源分配恳求之后，系统可用的资源数量可以满足其它 3 个进程的资源恳求，那么此时的资源分配顺序已无关紧要。所以：平安序列可以不独一！true10 5 70 0 24 3 110 5 5P4

15、FinishWork+AllocationAllocationNeedWorktrue10 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 2P0P2P3P12P1 发出恳求Request(1, 0, 2)，系统能分配资源吗？ 执行银行家算法： Request1 (1, 0, 2)Need1 (1, 2, 2)； Request1 (1, 0, 2)Available (3, 3, 2)； 系统为P1进展预分配，并修正Available，Allocation1 和

16、Need1向量：银行家算法实例Request1 (1, 0, 2)，Need1 ，Available Available :AvailableRequest1 (3, 3, 2)(1, 0, 2)(2, 3, 0) Allocation1 :Allocation1Request1 (2, 0, 0)(1, 0, 2)(3, 0, 2) Need1 :Need1Request1 (1, 2, 2)(1, 0, 2)(0, 2, 0)银行家算法实例Chapter 3 处置机调度与死锁FinishAvailableAllocationNeedWorktrue5 3 23 0 20 2 02 3 0P

17、1P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 12, 3, 0Chapter 3 处置机调度与死锁FinishAvailableAllocationNeedWorktrue7 4 32 1 1true5 3 23 0 20 2 02 3 0P1P35 3 20 1 1P4P3P2P1P0Av

18、ailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 15, 3, 2Chapter 3 处置机调度与死锁FinishAvailableAllocationNeedWorktrue7 5 30 1 07 4 37 4 3true7 4 32 1 1true5 3 23 0 20 2 02 3 0P0P1P35 3 20 2

19、0P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 17, 4, 3Chapter 3 处置机调度与死锁FinishAvailableAllocationNeedWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 1t

20、rue5 3 23 0 20 2 02 3 0P0P2P1P35 3 20 2 0P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 17, 5, 3Chapter 3 处置机调度与死锁true10 5 70 0 24 3 110 5 5P4FinishAvailableAllocationNeed

21、Worktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 1true5 3 23 0 20 2 02 3 0P0P2P1P35 3 20 2 0P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 110, 5, 5Chapte

22、r 3 处置机调度与死锁P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 110, 5, 7 执行平安性算法检查时，仍可以得到平安序列 P1，P3，P0，P2，P4 ，故恳求向量 Request1 (1, 0, 2) 发出时系统平安！分配后资源P4P3P2P1P0AvailableA, B, CN

23、eedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 12, 3, 03P4发出恳求Request(3, 2, 1)，系统能分配资源吗？ 执行银行家算法进展检查： Request4(3, 2, 0)Need4(4, 3, 1)； Request4(3, 2, 1) Available(2, 3, 0) 故：P4 资源恳求失败，让其等待！银行家算法实例分配

24、后资源P4P3P2P1P0AvailableA, B, CNeedA, B, CAllocationA, B, CMaxA, B, C进 程资源 情况7, 5, 33, 2, 29, 0, 22, 2, 24, 3, 30, 1, 03, 0, 23, 0, 22, 1, 10, 0, 27, 4, 30, 2, 06, 0, 00, 1, 14, 3, 12, 3, 04P0发出恳求Request(0, 2, 0)，系统能分配资源吗？ 执行银行家算法进展检查： Request0(0, 2, 0)Need0(7, 4, 3)； Request0(0, 2, 0)Available(2, 3,

25、0)； 系统为 P0 作预分配，并修正有关数据： 银行家算法实例 Available :AvailableRequest0 (2, 3, 0)(0, 2, 0)(2, 1, 0) Allocation0 :Allocation0Request0 (0, 1, 0)(0, 2, 0)(0, 3, 0) Need0 :Need0Request0 (7, 4, 3)(0, 2, 0)(7, 2, 3)银行家算法实例MaxAllocationNeedAvailableP07 5 30 3 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 显然，对于一切进程，条件NeediAvailable，均不成立。因此， P0 此次资源恳求预分配的结果，使系统进入不平安形状，故应吊销此次预分配。银行家算法实例死锁的检测和恢复死锁的检测和恢复检查方法： 类似于银行家算法，假设某时辰不是一切进程都进入平安序列，这些进程将发生死锁恢复方法：将产生死锁的进程全部撤销逐个撤销死锁的进程，直至死锁解除从发生死锁的进程中剥夺其占有的资源，破坏死锁的“不可剥夺条件。饿死饿死是死锁的另一种表现方式。假设有三个进程：Pa、Pb、Pc，每个进程都周期性地访问资源R。存在这样一种情况：Pa拥有资源R，Pb、