贸易公司广告网站,建设英语网站,学编程软件,企业宣传推广2.4 死锁 文章目录 2.4 死锁2.4.1 死锁的概念2.4.2 死锁预防2.4.3 死锁避免2.4.4 死锁检测和解除 2.4.1 死锁的概念 死锁的定义 在并发环境下#xff0c;各进程因竞争资源而造成的一种互相等待对方手里的资源#xff0c;导致各进程都阻塞#xff0c;都无法向前推进的现象各进程因竞争资源而造成的一种互相等待对方手里的资源导致各进程都阻塞都无法向前推进的现象就是“死锁”。发生死锁后若无外力干涉这些进程都将无法向前推进。 死锁、饥饿、死循环的区别 共同点都是进程无法顺利向前推进的现象故意设计的死循环除外) 区别 死锁各进程互相等待对方手里的资源导致各进程都阻塞无法向前推进的现象。两个以上程序 饥饿由于长期得不到想要的资源某进程无法向前推进的现象。单个程序 比如在短进程优先SPF算法中若有源源不断的短进程到来则长进程将一直得不到处理机从而发生长进程“饥饿” 死循环某进程执行过程中一直跳不出某个循环的现象。 有时是因为程序逻辑bug导致的有时是程序员故意设计的。 死锁产生原因 对系统资源的竞争 各进程对不可剥夺的资源如打印机的竞争可能引起死锁对可剥夺的资源CPU的竞争是不会引起死锁的。 进程推进顺序非法 请求和释放资源的顺序不当也同样会导致死锁。例如并发执行的进程P1、P2分别申请并占有了资源R1、R2之后进程P1又紧接着申请资源R2而进程P2又申请资源R1两者会因为申请的资源被对方占有而阻塞从而发生死锁。 信号量的使用不当也会造成死锁 如生产者-消费者问题中如果实现互斥的P操柞在实现同步的P操作之前就有可能导致死锁。可以把互斥信号量、同步信号量也看做是一种抽象的系统资源 死锁产生的必要条件 产生死锁 必须同时满足以下四个条件只要其中任一条件不成立死锁就不会发生。 ① 互斥条件只有对必须 互斥使用的资源的争抢 才会导致死锁如哲学家的筷子、打印机设备。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的因为进程不用阻塞等待这种资源。② 不剥夺条件进程所获得的资源在未使用完之前不能由其他进程强行夺走只能主动释放。③ 请求和保持条件进程已经 保持了至少一个资源但又提出了新的资源请求而该资源又被其他进程占有此时请求进程被阻塞但又对自己已有的资源保持不放。④ 循环等待条件存在一种进程资源的 循环等待链链中的每一个进程已获得的资源同时被下一个进程所请求。 注发生死锁时一定有循环等待但是发生循环等待时未必死锁即 循环等待是死锁的必要不充分条件。 如果同类资源数大于1则即使有循环等待也未必发生死锁如上图 Pn 可以同时请求 P1 或者 Pk 的资源得到 Pk 资源后不会发生死锁。 但如果系统中每类资源都只有一个那循环等待就是死锁的充分必要条件了。 死锁处理策略 死锁预防。设置某些限制条件破坏产生死锁的4个必要条件中的一个或几个。避免死锁。在资源的动态分配过程中用某种方法防止系统进入不安全状态。死锁的检测及解除。无须采取任何限制性措施允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生然后采取某种措施解除死锁。 死锁的几种处理策略的比较见下表。 资源分配策略各种可能模式主要优点主要缺点死锁预防保守宁可资源闲置一次请求所有资源资源剥夺资源按序分配适用于突发式处理的进程不必进行剥夺效率低进程初始化时间延长剥夺次数过多不便灵活申请新资源死锁避免是“预防”和“检测”的折中在运行时判断是否可能死锁寻找可能的安全允许顺序不必进行剥夺必须知道将来的资源需求进程不能被长时间阻塞死锁检测宽松只要允许就分配资源定期检查死锁是否已经发生不延长进程初始化时间允许对死锁进行现场处理通过剥夺解除死锁造成损失
2.4.2 死锁预防
死锁的产生必须满足四个必要条件只要其中一个或者几个条件不满足死锁不会发生。 破坏互斥条件 把只能互斥使用的资源改造为允许共享使用则系统不会进入死锁状态。如: SPOOLing技术。使用 SPOOLing 技术可以把 独占设备在逻辑上改造成共享设备。比如用SPOOLing技术将打印机改造为共享设备… 破坏不剥夺条件 提供两种方案 ① 申请资源得不到时主动释放所占有资源。② 申请资源被其他进程占用时由 OS 协助剥夺。 策略的缺点 实现起来比较复杂释放已获得的资源可能造成前一阶段工作的失效因此这种方法一般只适用于易保存和恢复状态的资源如CPU反复地申请和释放资源会增加系统开销降低系统吞吐量方案 ① 可能导致进程饥饿。 破坏请求和保持条件 采用 静态分配方法即进程 在运行前一次申请完它所需要的全部资源在它的资源未满足前不让它投入运行。一旦投入运行后这些资源就一直归它所有该进程就不会再请求别的任何资源了。 策略的缺点 进程在整个运行期间都一直保持着所有资源就会造成严重的资源浪费资源利用率极低。另外该策略也有 可能导致某些进程饥饿。 破坏循环等待条件 采用 顺序资源分配法。首先给系统中的资源编号要求进程只能按编号递增顺序请求 资源。 原理分析 一个进程只有已占有小编号的资源时才有资格申请更大编号的资源。按此规则已持有大编号资源的进程不可能逆向地回来申请小编号的资源从而就不会产生循环等待的现象(类比拓扑排序)。 策略的缺点 不方便增加新的设备因为可能需要重新分配所有的编号进程实际使用资源的顺序可能和编号递增顺序不一致会导致资源浪费必须按规定次序申请资源用户编程麻烦。
2.4.3 死锁避免
死锁的避免是在资源动态分配过程中防止系统进入不安全状态以避免发生死锁。 系统安全状态 安全序列是指如果系统按照这种序列分配资源则每个进程都能顺利完成。安全状态系统如果存在安全序列则处于安全状态安全状态一定不发生死锁。安全序列可能有多个。不安全状态如果分配了资源之后系统中找不出任何一个安全序列系统就进入了不安全状态。可能发生死锁处于不安全状态未必就是发生了死锁但发生死锁时一定是在不安全状态 安全序列的计算方法 已知现有三个进程的资源分配表如下(可用代表系统还剩有 3 个资源)现假设可用资源每次分配都是全部分配并且分配给进程的资源总数应满足进程最多还需求的资源数目(如可用资源有 3 个由于 P2 进程还需要 2 个资源因此只能满足 P2)分配完后回收该进程所拥有的全部资源。 计算步骤如下 因此得到安全序列是 {P2, P1, P3}。 如果计算到 P3 时可用资源无法满足 P3 的最大需求即还需要的资源数目多于可用资源数目那么就不存在安全序列。 注死锁状态一定是不安全状态不安全状态不一定是死锁状态即死锁状态 ⇒ 不安全状态。 如A 进程需 10 个资源而可用资源有 5 个。若 A 还未提出申请则不会进入死锁状态。 系统进入不安全状态后便可能进入死锁状态反之只要系统处于安全状态系统变可避免进入死锁。 银行家算法 核心思想 在分配资源前预先判断这次分配是否会导致系统进入不安全状态以此来决定是否答应资源分配请求从而使得系统避免死锁。 数据结构描述 ①可利用资源向量 A v a i l a b l e Available Available一维数据②最大需求矩阵 M a x Max Max③分配矩阵 A l l o c a t i o n Allocation Allocation④需求矩阵 N e e d Need Need 其中 N e e d M a x − A l l o c a t i o n NeedMax-Allocation NeedMax−Allocation 注 A v a i l a b l e ( A , B , C ) ( 3 , 3 , 2 ) Available(A,B,C)(3,3,2) Available(A,B,C)(3,3,2)代表可用的 A 类资源数目有 3 个B 类资源数目有3个C 类资源数目有 2 个。 银行家算法描述 设 R e q u e s t i Request_i Requesti是进程Pi的请求向量 R e q u e s t i [ j ] K Request_i[j]K Requesti[j]K表示进程 P i Pi Pi需要 j j j类资源 K K K个。 ①若 R e q u e s t i [ j ] ≤ N e e d [ i j ] Request_i[j]≤Need[ij] Requesti[j]≤Need[ij]检查此次申请是否超过最多还需求数。 ②若 R e q u e s t i [ j ] ≤ A v a i l a b l e [ j ] Request_i[j]≤Available[j] Requesti[j]≤Available[j]检查系统的可用资源是否还能满足此次需求。 ③系统试探着把资源分配给 P i Pi Pi并修改下面数据结构的数值 A v a i l a b l e A v a i l a b l e − R e q u e s t i AvailableAvailable-Request_i AvailableAvailable−Requesti修改i进程剩余可用资源数 A l l o c a t i o n [ i j ] A l l o c a t i o n [ i j ] R e q u e s t i [ j ] Allocation[ij]Allocation[ij]Request_i[j] Allocation[ij]Allocation[ij]Requesti[j]i进程已分配资源数加上本次请求资源数 N e e d [ i j ] N e e d [ i j ] − R e q u e s t i [ j ] Need[ij]Need[ij]-Request_i[j] Need[ij]Need[ij]−Requesti[j]i进程还需的资源数减去本次请求的资源数 ④执行安全性算法检查系统是否处于安全状态即检查当前系统是否存在安全序列。 若系统安全才正式将资源分配给 P i Pi Pi否则此次试探分配作废恢复原来分配状态。 注安全性算法是银行家算法的核心。 安全性算法描述 设置工作向量 W o r k Work Work表示系统中剩余可用资源数目。算法执行开始时 W o r k A v a i l a b l e WorkAvailable WorkAvailable ①初始时安全序列为空。②检查当前的剩余资源是否能满足某个进程的最大需求。如果可以就将它加入安全序列若找不到执行步骤④③把该进程持有资源全部回收返回步骤②④若此时安全序列中已有所有进程则系统处于安全状态否则处于不安全状态。 例题 假设当前系统中资源分配和剩余情况如下表所示现 P 1 P1 P1发出请求向量 R e q u e s t 1 ( 1 0 2 ) Request_1(102) Request1(102)判断此次请求是否分配成功。 ① 系统按银行家算法进行检查 R e q u e s t 1 ( 1 , 0 , 2 ) ≤ N e e d 1 ( 1 , 2 , 2 ) Request_1(1,0,2)≤Need_1(1,2,2) Request1(1,0,2)≤Need1(1,2,2) R e q u e s t 1 ( 1 , 0 , 2 ) ≤ A v a i l a b l e ( 3 , 2 , 2 ) Request_1(1,0,2)≤Available(3,2,2) Request1(1,0,2)≤Available(3,2,2) 此次申请未超过 P 1 P1 P1进程最多还需求数,并且当前可用资源数可满足此次申请,则可试探的为 P 1 P1 P1分配资源,并修改: A v a i l a b l e A v a i l a b l e − R e q u e s t 1 ( 2 , 3 , 0 ) AvailableAvailable-Request_1(2,3,0) AvailableAvailable−Request1(2,3,0) A l l o c a t i o n 1 A l l o c a t i o n 1 R e q u e s t 1 ( 3 , 0 , 2 ) Allocation_1Allocation_1Request_1(3,0,2) Allocation1Allocation1Request1(3,0,2) N e e d 1 N e e d 1 − R e q u e s t 1 ( 0 , 2 , 0 ) Need_1Need_1-Request_1(0,2,0) Need1Need1−Request1(0,2,0) ② 系统执行安全性算法检查安全状态 令 W o r k A v a i l a b l e ( 2 , 3 , 0 ) WorkAvailable(2,3,0) WorkAvailable(2,3,0)执行安全性算法如下表所示 由安全性检查而知可以找到一个安全序列 { P1, P3, P4, P0, P2 }因此系统是安全的可以将P1所申请的资源分配给他。
2.4.4 死锁检测和解除 如果系统既不采取预防死锁的措施也不采取避免死锁的措施系统就很可能发生死锁。在这种情况下系统应当提供死锁检测和解除的手段。 资源分配图 系统死锁可利用 资源分配图 来描述。圆代表一个进程框代表一类资源框中一个圆代表一类资源中的一个资源。 两种结点 进程结点对应一个进程资源结点对应一类资源一类资源可能有多个 两种边 请求边表示进程想申请几个资源每条边代表一个分配边表示已经为进程分配了几个资源每条边代表一个 死锁定理 简化资源分配图可检测系统状态是否为死锁状态。简化方法如下 ① 在资源分配图中找出 既不阻塞又不是孤点的进程 Pi。 不阻塞表示进程申请的资源可以被满足如 P1 进程。由于 R2 资源除分配给 P2 进程一个资源外还剩有一个资源因此 P1 进程申请的 R2 资源可以被满足。相反P2 进程申请 R1 资源则不会被满足由于 R1 资源全部被分配完。不是孤点表示与该进程节点至少一个边相连。 ② 消去进程所有的请求边和分配边使之成为孤点。 重复以上步骤若能消去图中所有的边则称该图是可完全简化的。 注并不是系统中所有的进程都是死锁状态用死锁检测算法 化简资源分配图后还连着边的那些进程就是死锁进程。 死锁定理如果某时刻系统的资源分配图是不可完全简化的那么此时系统死锁 死锁解除 一旦检测出死锁的发生就应该立即解除死锁。解除死锁的主要方法有 资源剥夺法 挂起暂时放到外存上某些死锁进程并抢占它的资源将这些资源分配给其他的死锁进程。但是 应防止被挂起的进程长时间得不到资源而饥饿。 撤销进程法或称终止进程法 强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。这种方式的优点是实现简单但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间已经接近结束了一旦被终止可谓功亏一篑以后还得从头再来。撤销的原则可以按进程优先级和撤销进程代价的高低进行。 进程回退法 让一个或多个死锁进程回退到足以避免死锁的地步。进程回退时自愿释放资源而非剥夺。这就要求系统要记录进程的历史信息设置还原点。 注撤销进程法中参考的优先级应考虑进程优先级、已执行多长时间、还要多久能完成、进程已经使用了多少资源、进程是交互式的还是批处理式的等因素。
