计算机操作系统第四版第三章死锁ppt课件.ppt

1 死锁 资源 死锁的定义 产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法 2 一 资源的概念 OS是计算机系统中资源的管理者 而进程是竞争资源的基本单位 故对系统中所有进程的资源分配工作 都由OS完成 研究资源分配时 我们必须弄清楚该资源是可以被几个进程同时使用 还是只能为一个进程使用 资源的不同使用性质正是引起系统死锁的原因 资源的分类根据资源性质 可剥夺 抢占 和不可剥夺 非抢占 资源 可抢占资源 指占用资源的进程虽然还需要使用该资源 但另一个进程却强行把资源抢走 不可抢占资源 指只有占用者进程不再需要使用该资源而主动释放资源外 其它进程不得在占有者进程使用资源过程中强行抢占 3 根据使用方式 共享资源和独享资源 即非临界资源与临界资源 根据使用期限 永久资源和临时性资源 4 根据使用方式 共享资源和独享资源 根据使用期限 永久资源和临时性资源 可重复使用的资源 如 内存 外部设备 数据文件 表格等 5 根据使用方式 共享资源和独享资源 根据使用期限 永久资源和临时性资源 由一个进程产生 被另外一个进程使用短暂时间之后便不再使用的资源 如 消息 同步信号等等 6 二 死锁的定义 计算机系统中多道程序并发执行时 两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象 僵局 如无外力作用 这些进程将永远不能再向前推进 死锁Deadlock 系统中存在一组进程 两个或多个进程 它们中的每一个进程都占用了某种资源而又都在等待其中另一进程所占用的资源 这种等待永远不能结束 则说系统出现了 死锁 或说这组进程处于死锁状态 陷入死锁状态的进程称为死锁进程 所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁 最终可能导致整个系统处于瘫痪状态 死锁和饥饿的主要差别是什么 1 死锁 是一种相互或循环等待的局面 且它们等待的事件是决不会发生的 被死锁的进程应该是两个或两个以上 一个进程不可能自己把自己锁上 除非出现程序设计错误 2 饥饿 不是循环等待的局面 而是一种单向等待 它们等待的事件不是没有发生 而是总被别的进程抢先以致一直轮不到 很难轮到 它们 饥饿的进程可能是一个或多个 仅涉及一个进程的死锁有可能存在吗 为什么 7 图简单的死锁例子 我们先来看一个申请不同类型资源的死锁例子 假定有两个进程Pl和P2 设F和T都是可重用资源 于是Pl和P2可有如下形式 8 三 产生死锁的原因 1竞争资源当系统中供多个进程所共享的资源 不足以同时满足它们的需要时 引起它们对资源的竞争而产生死锁 进程推进的顺序不当进程在运行过程中 请求和释放资源的顺序不当 导致进程的死锁 例题 一个OS有20个进程 竞争使用65个同类资源 申请方式是逐个进行的 一旦某个进程获得它所需要的全部资源 则立即归还所有资源 每个进程最多使用三个资源 若仅考虑这类资源 该系统有无可能产生死锁 为什么 答 不可能 因为死锁产生的原因有两点 系统资源不足或推进顺序不当 在本题中 进程所需的最大资源数为60 而系统共有该类资源65个 其资源数已足够系统内各进程使用 9 例1 进程推进顺序不当产生死锁问题 例2 PV操作使用不当产生死锁 例3 同类资源分配不当引起死锁 例4 对临时性资源使用不加限制引起死锁综上 产生死锁的因素不仅与系统拥有的资源数量有关 而且与资源分配策略 进程对资源的使用要求以及并发进程的推进顺序有关 但以下两种情况进程永远等待不属于要讨论的死锁问题 1 某个进程申请系统中不存在的资源或申请的资源数超过了系统拥有的最大资源数 2 硬件故障或程序性错误引起的循环等待 10 四 产生死锁的四个必要条件 互斥条件 资源在一段时间内只能被一个进程所使用 临界资源 请求和保持条件 一个进程请求资源得不到满足而等待 但不释放已占有的资源 部分分配 不剥夺条件 一个资源仅能被占有它的进程所释放 而不能被其他进程剥夺 主动释放 环路等待条件 存在一个进程资源的环路链 链中每一个进程占用着某些资源 又在等待另一个进程占有的资源 解决死锁的方法一般可分为 预防 避免 检测和解除四种 11 死锁的排除方法 1鸵鸟算法2预防死锁3避免死锁4检测和解除死锁 13 解决死锁的最简单方法就是鸵鸟算法 即像鸵鸟一样 当遇到危险时 将头埋进沙子里 假装毫无问题 当死锁在计算机中很少出现时 比如说每五年或更长时间才出现一次时 人们就不必花费更多的精力去解决它 而是采用类似鸵鸟一样的办法忽略它 以UNIX系统为例 它潜在地存在死锁 但它并不花功夫去检测和解除死锁 而是忽略不去理它 1 鸵鸟算法 置之不理 14 2预防死锁 根据产生死锁的四个必要条件 只要使其中之一不能成立 死锁就不会出现 但必要条件1是由设备的固有特性所决定的 不仅不能改变 相反还应加以保证 因此实际上只有三种方法 预防死锁是一种较易实现的方法 已被广泛使用 但由于所施加的限制条件往往太严格 可能导致系统资源利用率和系统吞吐量降低 1 破坏请求和保持条件2 破坏不剥夺条件3 破坏环路等待条件 15 系统要求任一进程必须预先申请它所需的全部资源 而且仅当该进程的全部资源要求能得到满足时 系统才能给予一次性分配 然后启动该进程运行 但是在分配时只要有一种资源不满足 系统就不会给进程分配资源 进程运行期间 不会再请求新的资源 所以 再分配就不会发生 摒弃了部分分配 缺点 资源严重浪费进程运行延迟 1 破坏 请求和保持条件 静态分配策略 16 采用的策略 一个已经占有了某些资源的进程 当它再提出新的资源要求而不能立即得到满足时 必须释放它已经占有的所有资源 待以后需要时再重新申请 缺点 1 实现比较复杂 且要付出很大代价 2 还因为反复地申请和释放资源 而使进程的执行无限地推迟 延长了周转时间 增加了系统的开销 降低了系统吞吐量 例如打印机打印的结果不连续 2 防止 不剥夺 条件的出现 17 3 防止 环路等待 条件的出现 层次分配策略 优点 资源利用率和系统吞吐量与另两种方法相比有较明显的改善缺点 1 为系统中各种类型的资源所分配的序号必须相对稳定 这就限制了新设备类型的增加 2 进程实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费 这种方法的基本思想是 资源被分成多个层次 一个进程得到某一层的一个资源后 它只能再申请较高一层的资源 当一个进程要释放某层的一个资源时 必须先释放所占用的较高层的资源 当一个进程获得了某一层的一个资源后 它想再申请该层中的另一个资源 就必须先释放该层中的已占用资源 18 3死锁避免 如果操作系统能保证所有的进程在有限的时间内得到需要的全部资源 则称系统处于安全状态 否则称系统是不安全的 避免死锁与预防死锁的区别在于 预防死锁是设法至少破坏产生死锁的必要条件之一 严格地防止死锁的出现 避免死锁 它是在进程请求分配资源时 采用银行家算法等防止系统进入不安全状态 19 在资源的动态分配的过程中 使用某种方法去防止系统进入不安全状态 从而避免死锁的发生 系统状态 安全状态 指系统能按照某种顺序如 为每个进程分配所需的资源 直至最大需求 使得每个进程都能顺利完成 称为序列为安全序列 非安全状态 即在某个时刻系统中不存在一个安全序列 则称系统处于不安全状态或非安全状态 注意 1 安全序列不一定只有一个2 系统只要处在安全状态 就肯定不会发生死锁3 系统处在不安全状态下时 未必一定会发生死锁 虽然并非所有不安全状态都是死锁状态 但当系统进入不安全状态后 便有可能进入死锁状态 反之只要系统处于安全状态 系统便可避免进入死锁状态 因此 避免死锁的实质是如何使系统不进入不安全状态 银行家算法 20 安全状态的例子 例 假定系统有三个进程P1 P2 P3 共有12台磁带机 进程P1 P2和P3分别需要10台 4台和9台 设在T0时刻 进程P1 P2和P3已经获得5台 2台和2台 还有3台空闲没有分配 进程 最大需求 已分配 可用 P1 10 5 3 P2 P3 4 2 2 9 T0时刻系统是安全的 这时存在一个安全序列 21 银行家算法 银行家算法是最有代表性的避免死锁算法 是Dijkstra提出的银行家算法 这是由于该算法能用于银行系统现金贷款的发放而得名 22 银行家可以把一定数量的资金供多个用户周转使用 为保证资金的安全 银行家规定 1 当一个用户对资金的最大需求量不超过很行家现有的资金时可接纳该用户 2 用户可以分期贷款 但贷款的总数不能超过最大需求量 3 当银行家现有的资金不能满足用户的尚需总数时 对用户的贷款可推迟支付 但总能使用户在有限的时间里得到贷款 4 当用户得到所需的全部资金后 一定能在有限的时间里归还所有资金银行家算法是通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源的 在能确保系统处于安全状态时才能把资源分配给申请者 从而避免系统发生死锁 23 要记住的一些变量的名称 1Available 可利用资源总数 某类可利用的资源数目 其初值是系统中所配置的该类全部可用资源数目 2Max 某个进程对某类资源的最大需求数3Allocation 某类资源已分配给某进程的资源数 4Need 某个进程还需要的各类资源数 Need Max Allocation系统把进程请求的资源 Request 分配给它以后要修改的变量Available Available Request Allocation Allocation Request Need Need Request 24 例题 假定系统中有五个进程 P0 P1 P2 P3 P4 和三种类型的资源 A B C 每一种资源的数量分别为10 5 7 在T0时刻的资源分配情况如图 资源情况 进程 AllocationABC MaxABC NeedABC AvailableABC P0P1P2P3P4 010 322 902 222 433 200 753 302 211 002 743 122 00 011 431 332 25 332 122 200 资源情况 进程 AllocationABC MaxABC NeedABC AvailableABC P0P1P2P3P4 010 322 902 222 433 200 302 211 002 743 122 600 011 431 332 753 资源情况 进程 NeedABC workABC Work AllocationABC AllocationABC P0 finish 532 true true true true true 011 211 532 743 743 431 002 745 745 600 302 1047 1047 743 010 1057 已分配 还需要 可用 工作向量Work 它表示系统可提供给进程继续运行所需要的各类资源的数目 10 57 P1 P3 P4 P2 26 230 020 302 资源情况 进程 NeedABC workABC Work AllocationABC AllocationABC P2 finish 532 true true true true true 011 211 532 743 743 431 002 745 745 743 010 755 755 600 302 1057 若P1发出请求向量Request 1 0 2 10 57 P1 P3 P4 P0 27 210 资源情况 进程 AllocationABC MaxABC NeedABC AvailableABC P0P1P2P3P4 010 322 902 222 433 302 302 211 002 743 020 600 011 431 230 210 753 资源情况 进程 NeedABC workABC Work AllocationABC AllocationABC finish flase 若P0发出请求向量Request 0 2 0 10 57 030 723 若P1发出请求向量Request 0 2 0 28 3 7死锁的检测与解除死锁的检测与解除技术是指定期启动一个软件检测系统的状态 若发现有死锁存在 则采取措施恢复之 1 死锁的检测 实质是确定是否存在环路等待现象 一旦发现这种环路便认定死锁存在 并识别出该环路所涉及的有关进程 以供系统采取适当的措施来解除死锁 最常用的是一种基于进程 资源分配图和死锁定理的检测死锁算法 29 进程 资源分配图 RAG图 系统死锁可用进程 资源分配图来描述 该图是由一组结点和一组边所组成的 用圆圈代表一个进程 用方框代表一类资源 由于一种类型的资源可能有多个 可用方框中的一个点代表一类资源中的一个资源 几个概念 请求边 分配边 P1 P2 r1 r2 请求边 资源分配图 分配边 30 封锁进程 是指某个进程由于请求了超过系统中现有的未分配资源数目的资源 而被系统封锁的进程 非封锁进程 即没有被系统封锁的进程 进程 资源分配图的化简方法 假设某个进程 资源分配图中存在一个进程Pi 此刻Pi是非封锁进程 那么可以进行如下化简 当Pi有请求边时 首先将其请求边变成分配边 即满足Pi的资源请求 而一旦Pi的所有资源请求都得到满足 Pi就能在有限的时间内运行结束 并释放其所占用的全部资源 此时Pi只有分配边 删去这些分配边 实际上相当于消去了Pi的所有请求边和分配边 使Pi成为孤立结点 反复进行 在经过一系列的简化后 若能消去图中的所有边 使所有的进程都成为孤立结点 则称该图是可完全简化的 反之则是不可完全简化的 31 死锁定理 系统中某个时刻S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的 32 判定死锁准则 1 如果RAG中未出现任何环 则此时系统内不存在死锁 2 如果RAG中出现了环 且处于此环中的每类资源均只有一个个体 则有环就有死锁 此时环路是存在死锁的充分必要条件 3 如果RAG中出现了环 但处于此环中的每类资源的个数不全为1 则环的存在只是产生死锁的必要条件而不是充分条件 此时是否有死锁 还要通过对RAG的化简而定 33 判定死锁准则 1 如果RAG中未出现任何环 则此时系统内不存在死锁 2 如果RAG中出现了环 且处于此环中的每类资源均只有一个个体 则有环就就有死锁 此时环路是存在死锁的必要充分条件 3 如果RAG中出现了环 但处于此环中的每类资源的个数不全为1 则环的存在只是产生死锁的必要条件而不是充分条件 此时是否有死锁 还要通过对RAG的化简而定 34 例题 化简如图所示的资源分配图 并说明有无进程处于死锁状态 35 资源分配图中存在环路并不一定发生死锁 因为循环等待资源仅是死锁发生的必要条件 而不是充分条件 如 有环有死锁 有环无死锁 36 死锁的解除 是与检测死锁相配套的一种措施 用于将进程从死锁状态下解脱出来 常用的方法有 1 立即结束所有进程的执行 并重新启动操作系统 2 撤消进程 最简单撤消进程的方法是使全部死锁的进程夭折掉 另一方法是按照某种顺序逐个地撤消进程 直至有足够的资源可用 死锁状态消除为止 3 剥夺资源 挂起进程 使用挂起 激活机构挂起一些进程 剥夺它们的资源以解除死锁 待条件满足时 再激活进程 目前挂起法比较受到重视 5解除死锁 37 采用剥夺资源的方法解决死锁问题时应考虑三个问题 1 抢夺哪些进程的哪些资源 2 被抢夺者的恢复 3 进程的饿死 38 系统中并发运行进程由于共享资源或相互通信 如果调度不当 可能导致系统死锁 解决死锁的方法有三种 1 预防死锁 它是通过破坏死锁的四个必要条件实现的 2 避免死锁 它是在进程请求分配资源时 采用银行家算法等防止系统进入不安全状态 3 检测和解除死锁 它是通过设置一个死锁检测机构进行死锁检测 一旦检测出来 通过逐一撤消进程使系统恢复 小结 39 1 3个进程共享4个同种类型的资源 每个进程最大需要2个资源 请问该系统是否因为竞争该资源而死锁 答 1 该系统不会因为竞争该资源而死锁 因为必有一个进程可获得2个资源 故能顺利完成 并释放其所占用的2个资源给其他进程使用 使它们也顺利完成 40 2 一台计算机有8台磁带机 它们由N N 1 个进程竞争使用 每个进程可能需要3台磁带机 请问N为多少时 系统没有死锁危险 并说明其原因 答 如果选择N 2 因每个进程需要3台磁带机 所以2个进程共需6台磁带机 必然不发生死锁 如果N 3时 因3个进程竞争8台磁带机 无论如何都将满足其中2个进程的需求 而第3个进程虽暂时等待 但在另两个进程执行结束并释放资源后必然会得到所要的资源 这样3个进程都可运行到结束而不出现死锁 问 3个进程竞争7台磁带机时会发生死锁吗 答 实际上也不发生死锁 因为至少有一个进程可以得到3台磁带机而运行结束 虽然另外2个进程暂时得不到足够的资源而等待 但在已运行结束的进程释放资源后必然会得到所需要的资源而都能运行结束 即也不会发生死锁 41 3 设系统仅有一类数量为M的独占型资源 系统中N个进程竞争该类资源 其中各进程对该类资源的最大需求为W 当M N W分别取下列值时 试判断下列哪些情形会发生死锁 1 M 2 N 2 W 12 M 3 N 2 W 23 M 3 N 2 W 34 M 5 N 3 W 25 M 6 N 3 W 3 42 解答 如果资源数为M 进程个数为N 则每个进程对该类资源的最大需求不超过下面公式的X值时 系统不会发生死锁 X 由此得到 1 X 1 X W 即系统不会出现死锁 2 X 2 X W 即系统不会出现死锁 3 X 2 X W 即系统可能出现死锁 4 X 2 X W 即系统不会出现死锁 5 X 2 X W 即系统可能出现死锁 1当M N时 1 M 1 N 1 M 1 N当M N时 43 3 一系统具有150个存储单元 在T0时刻系统按表所示分配给进程 对下列请求应用银行家算法分别分析判定是否安全 1 第4个进程P4到达 最大需求60个存储单元 当前请求分配25个单元 2 第4个进程P4到达 最大需