佛山市 骏域网站建设,美橙建站五合一建站套餐申请,校园微网站建设方案ppt模板下载,丽水微信网站建设公司1、概述
1.1 死锁
死锁是多个进程因竞争资源而造成的一种僵局#xff08;互相等待#xff09;#xff0c;若无外力作用#xff0c;这些进程都将无法向前推进。
1.2 死锁产生的原因和条件
原因#xff1a;#xff08;1#xff09;竞争资源#xff1b;#xff08;2互相等待若无外力作用这些进程都将无法向前推进。
1.2 死锁产生的原因和条件
原因1竞争资源2进程间推进顺序非法
条件:1互斥条件2请求和保持条件;3不剥夺条件4环路等待条件
1.3 死锁的处理策略
1死锁预防
破坏产生死锁的四个必要条件中的一个或几个以防止发生死锁。
互斥条件所有资源允许共享则系统不会进入死锁状态但是打印机等临界资源不适用请求和保持条件采用预先静态分配方法即进程运行前一次申请完所需要的资源在资源未满足前进程不执行进程一旦执行不再提出其他资源请求这样就不会死锁不剥夺条件当一个已经保持了某些不可剥夺资源的进程请求新资源得不到满足时它必须释放已经保持的所有资源待以后需要时重新申请环路等待条件循环等待为了破坏循环等待条件可釆用顺序资源分配法。
2死锁避免银行家算法
在资源的动态分配中用某种方法防止系统进入不安全状态从而避免死锁
3死锁的检测及解除
无需釆取任何限制性措施允许进程在运行过程中发生死锁。通过系统的检测机构及时 地检测出死锁的发生然后采取某种措施解除死锁通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。当且仅当S状态的资源分配图是不可完全简化的,该条件为死锁定理。
死锁解除的主要方法有 1) 资源剥夺法。挂起某些死锁进程并抢占它的资源将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。 2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
3) 进程回退法。让一多个进程回退到足以回避死锁的地步进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息设置还原点。 2、银行家算法
主要思想是避免系统进入不安全状态。在每次进行资源分配时它首先检查系统是否有足够的资源满足要求如果有则先进行分配并对分配后的新状态进行安全性检查。如果新状态安全则正式分配上述资源否则就拒绝分配上述资源。这样它保证系统始终处于安全状态从而避免死锁现象的发生。
1具体数据项
最大需求矩阵Max
需求矩阵Need
分配矩阵Allocation
可利用资源矢量Available
存在关系Need Max-Allocation
2银行家算法描述
设request是进程Pi的请求矢量当P发出资源请求后系统按照以下步骤进行检查
如果满足Request[i,j] Need[i, j],则继续以下步骤否则认为它所需资源数已超过宣布的最大值如果满足Request[i,j] Available[i, j]则继续以下步骤否则尚无足够资源Pi需等待。系统试探着把资源分配给进程Pi并修改下面数据结构中的数值Available[j] Available[j] - Requesti[j]; Allocation[i, j] Allocation[i, j] Requesti[ j]; Need[i, j] Need[i, j] - Requesti[j];
系统执行安全性算法检查此次资源分配后系统是否处于安全状态若安全才正式将资源分配给进程Pi以完成本次分配否则将本次的分配作废恢复原来的资源分配状态让进程Pi等待。
3系统安全状态安全状态算法
安全状态是指系统能按某种进程推进顺序( P1, P2, ..., Pn)为每个进程Pi分配其所需资源直至满足每个进程对资源的最大需求使每个进程都可顺序地完成。此时称 P1, P2, ..., Pn 为安全序列。如果系统无法找到一个安全序列则称系统处于不安全状态。
工作矢量Work它表示系统可提供给进程继续运行所需的各类资源数目它含有所个元素在执行安全算法开始时WorkAvailable;
Finish它表示系统是否有足够的资源分配给进程使之运行完成。开始时 Finish[i]false当有足够资源分配给进程 Pi 时再令 Finish[i]true。
3、死锁实例
3.1 银行家算法实例
case 1系统有五个进程P1、P2、P3、P4、P5三种资源R1、R2、R3在T0时刻的状态如图所示回答下列问题
已分配资源数量Allocation最大资源需求数量MaxR1R2R3R1R2R3P1001001P2200275P3003665P4115435P5033065
R1R2R3剩余资源数Available330
1T0时刻是否为安全状态为什么
2若这时P4请求资源1,2,0是否实施资源分配为什么
3在上面基础上若进程P3请求资源0,1,0是否能实施资源分配为什么
答1T0时刻是安全状态序列为P1-P4-P5-P2-P3
AllocationNeedMax-AllocationAvailableAllocation(初始3,3,0)状态R1R2R3R1R2R3R1R2R3FinishP1001000331True核对Need矩阵P4320(need)331(Available)P4115320446True核对Need矩阵,P5032(need)446(Available)P5033032479True核对Need矩阵,P2075(need)479(Available)P2200075679True核对Need矩阵,P3662(need)679(Available)P30036626712end最后资源6,7,12
2P4请求1,2,0则Request1,2,0
比较RequestNeed(1,2,03,2,0) RequestAvailable(1,2,03,3,0)
更新Need Need-Request3,2,0-1,2,02,0,0 Available Available -Request3,3,0-1,2,02,1,0 Aollcation AollcationRequest1,1,51,2,02,3,5
已分配资源数量Allocation最大资源需求数量MaxNeedR1R2R3R1R2R3R1R2R3P1001001P2200275P3003665P4235435200P5033065
R1R2R3剩余资源数Available210安全序列为P1-P4-P5-P2-P3
AllocationNeedMax-AllocationAvailableAllocation(初始3,3,0)状态R1R2R3R1R2R3R1R2R3FinishP1001000210True核对Need矩阵P4200(need)210(Available)P4235200446True核对Need矩阵,P5032(need)446(Available)P5033032479True核对Need矩阵,P2075(need)479(Available)P2200075679True核对Need矩阵,P3662(need)679(Available)P30036626712end最后资源6,7,123在上面基础上P3请求1,1,0则Request1,1,0
比较RequestNeed(1,1,06,6,2) RequestAvailable(1,1,02,1,0)
更新Need Need-Request6,6,2-1,1,05,5,2 Available Available -Request2,1,0-1,1,01,0,0 Aollcation AollcationRequest0,0,31,1,01,1,3
已分配资源数量Allocation最大资源需求数量MaxNeedR1R2R3R1R2R3R1R2R3P1001001P2200275P3113665552P4235435200P5033065
R1R2R3剩余资源数Available100不为安全序列
AllocationNeedMax-AllocationAvailableAllocation(初始3,3,0)状态R1R2R3R1R2R3R1R2R3FinishP1001000101True核对Need矩阵P4100(need)101(Available)P4235200以下均不满足P5033032P2200075P3003662
3.2 死锁检测例题
case 1设有进程P1和P2并发执行都要使用R1和R2使用资源情况如表所示试判断是否会产生死锁并说明原因
进程P1进程P2申请资源R1申请资源R2申请资源R2申请资源R1释放资源R1释放资源R2
答可能会死锁当进程P1和P2分别申请完R1和R2当P1再去申请R2时P2未将R2资源释放P1处于等待状态因此P1和P2都申请不到资源而造成死锁
case 2系统有同类资源m个供n个进程共享若每个进程对资源的最大需求量为k试问当m,n,k的值分别为下列情况时是否会发生死锁
序号 m nk是否死锁k-1*n1m说明1633(3-1)*3176 (可能死锁)2933(3-1)*3179 (不会死锁)31363(3-1)*611313(不会死锁)
case 3有三个进程P1P2P3并发工作。进程P1需要资源S3和S1进程P2需要资源S2和S1进程P3需要S3和S2问
1若对资源分配不加限制会发生什么情况为什么
2为保证进程正确运行应采用怎样的分配策略
答
1可能会发生死锁。满足发生死锁的4大条件例如P1占有S1申请S3P2占有S2申请S1P3占有S3申请S2。
2方法一静态分配由于执行前已获得所需的全部资源因此不会出现占有资源又等待别的资源的现象
方法二按序分配不会出现循环等待资源的现象
方法三银行家算法因为在分配时保证了系统处于安全状态
