计算机操作系统基础 (七)--- 作业管理之死锁

引言

本文为第七篇，作业管理之死锁，死锁是计算机操作系统中非常重要的概念，本文主要介绍什么是死锁以及如何解决死锁



死锁

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程



举个例子：





如果这四辆汽车按照如图的方向行驶，堵在十字路口，相互之间没有退让的话，这四辆汽车就形成了死锁。



死锁的产生

• 竞争资源

• 进程调度顺序不当



竞争资源



为什么会出现竞争资源？

• 共享资源数量不满足各个进程的需求

• 各个进程之间发生资源竞争导致死锁



举例：



假设有两个进程：进程1和进程2，进程1需要使用传真机，并且已经获取到了传真机资源。进程2需要获取打印机，并且也获取到了。如果此时进程2还需要传真机的时候，或者进程1还需要打印机的时候，他们都需要等待请求的资源被释放，但他们相互之间所占用的资源又不会被释放，因此就造成了死锁的产生，这个就是由于竞争资源而产生的死锁。如果此时多一个传真机或者打印机资源，就不会出现死锁，本质还是因为资源不够



进程调度顺序不当



还是以上边的进程1和进程2为例，假设进程1申请传真机资源为步骤A，进程2申请打印机资源为步骤B，进程2申请传真机资源为步骤C，进程1申请打印机资源为步骤D。如果这两个进程按照A、B、C、D的顺序申请资源，就会产生死锁。如果程序可以把调度顺序改为A、D、B、C，这个时候就不会出现死锁的情况。因为当进程1先获得了传真机资源，然后在获取打印机资源，完成它的工作之后，进程1就会释放这两个资源。这个时候进程2就可以获得打印机和传真机资源了。这个就是因为进程调度顺序不当导致死锁的产生





死锁的四个必要条件

• 互斥条件

• 请求保持条件

• 不可剥夺条件

• 环路等待条件



如果只满足上边的一个或两个的话，不会产生死锁



互斥条件

• 进程对资源的使用是排他性的使用

• 某个资源只能由一个进程使用，其它需要使用该资源的进程只能等待，等待资源被释放



请求保持条件

• 进程至少持有一个资源，又提出新的资源请求

• 新资源被占用，请求被阻塞

• 被阻塞的进程不释放自己所持有的资源



不可剥夺条件

• 进程获得的资源在未完成使用前不能被剥夺(程序或操作系统均不可)

• 获得的资源只能由进程自身释放



环路等待条件



发生死锁时，必然存在进程-资源环形链



P为进程，R为资源





死锁的处理

预防死锁的方法



前边提到了死锁的四个必要条件，只要破坏其中的一个或多个条件，就可以避免死锁的出现



破坏请求保持条件

• 系统规定进程运行之前，一次性申请所有需要的资源

• 进程在运行期间不会提出资源请求，从而摒弃请求保持条件。也就不可能会因为在运行的时候请求资源而导致等待的情况



破坏不可剥夺条件

• 当一个进程请求新的资源得不到满足时，必须释放占有的资源

• 进程运行时占有的资源可以被释放，意味着可以被剥夺



破坏环路等待条件

• 可用资源线性排序，申请必须按照需要递增申请

• 线性申请不再形成环路，从而摒弃了环路等待条件





假设有A、B、C、D、E这五个资源，按照线性顺序将他们排起来，假设有一个进程需要A和D这两个资源的时候，它必须先申请A，才能申请D，这样就是线性申请



银行家算法



银行家算法是一个可操作的著名的避免死锁的算法，以银行借贷系统分配策略为基础的算法



• 假设客户申请的贷款是有限的，每次申请需要声明最大资金量

• 银行家在能满足贷款时，都应该给客户贷款

• 客户在使用贷款后，能够及时归还贷款



上边是银行家算法策略的一个基础，下边是具体过程：



这个算法要求有三个数据结构，分别是已分配资源表、*所需资源表*、可分配资源表





A、B、C、D为可申请的共享资源，P1、P2、P3、P4为需要申请资源的四个进程



已分配资源表



表中的数值表示的是每个进程它当前拥有的资源(如P1进程已分配了1个C资源和4个D资源)



所需资源表



表中的数值表示的是每个进程所需要各个资源的数量(如P1进程需要6个B资源、5个C资源和6个D资源)



可分配资源表



表中的数值表示的是系统里边还剩下的各种类型资源的数量



有了上边的几个数据结构的表格，就可以进行真实的演练了



(1)所需资源表减已分配资源表



这两个数据结构相减，得到还需分配资源表，然后将还需分配资源表和可分配资源表进行对比





我们会发现，可分配资源表，不满足进程P1的需求，因为P1进程需要6个B资源、4个C资源、2个D资源，而可用的A、B、C、D资源分别只有1、5、2、0个，因此不满足进程PA的需求。后边的P2、P3、P4使用同样的方法对比可发现，可分配资源表中的资源满足P2的需求，不满足P1、P3、P4的需求。因此，系统会把可分配的资源全部分发给P2，那么这个P2进程就可以继续的执行下去，等P2执行完之后，再归还所有的资源，归还之后，又可以将新的资源分配给别的进程。这个就是银行家算法。(P1、P2、P3、P4可以看做贷款的人，数字代表贷款的钱)



在快速变化的技术中寻找不变，才是一个技术人的核心竞争力。知行合一，理论结合实践