表-死锁 |
死锁的定义 | 指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。 |
死锁产生的原因 | 1) 竞争资源—空间 | 竞争不可剥夺资源 | 可剥夺资源：指某进程在获得这类资源后，该资源可以被其他进程或系统剥夺。如CPU、内存等。 不可剥夺资源：当系统将这类资源分配给某个进程后，再不能强行收回，只能在进程用完后自行释放。如打印机等。 |
竞争临时性资源 | 永久性资源：可重复使用的资源。如打印机。 临时性资源：指由一个进程产生，被另一进程使用一短暂时间后便无用的资源，也称为消耗性资源。如消息。 |
2) 进程间推进顺序非法—时间 | |
死锁产生的必要条件 | 1) 互斥条件； | 进程对所分配到的资源进行排它性使用，即在一段时间内只能有一个进程占用。 |
2) 不剥夺条件； | 指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。 |
3) 环路等待条件； | 指发生死锁时必然存在一个进程—资源的环形链。 |
4) 请求和保持条件； | 占有的请求，阻塞的保持。 |
处理死锁的基本方法 | 预防死锁 | 属于事先预防的方法。通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个来预防发生死锁。（限制条件较严格） |
避免死锁 | 属于事先预防的方法。无需事先设置条件破坏产生死锁的必要条件，而是在资源的动态分配过程中，防止系统进入不安全状态，从而避免发生死锁。（限制条件较宽松） |
检测并解除死锁 | 允许系统在运行过程中发生死锁，但可以及时地检测出死锁的发生，并采取适当的措施解除死锁。 |
预防死锁 | “互斥”条件是设备的固有特性所决定的，不仅不能改变，还应加以保护。 |
摒弃“不剥夺”条件 | 进程逐个地提出对资源的要求，当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。 |
摒弃“环路等待”条件 | 系统将所有的资源按照类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出。这样总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而可一直向前推进。 |
摒弃“请求和保持”条件 | 进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。这样在运行期间不会再请求资源，在阻塞期间不会再保持资源。 |
避免死锁 | 安全序列 | 定义 | 指系统能按该序列指定的进程顺序(P1, P2,…, Pn)，来为每个进程Pi分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利地完成。 |
实质 | 安全序列中各进程的排列顺序即为各进程完成的先后顺序，先给Pi分配资源使其完成，再考虑给Pi+1分配资源使其完成。 |
安全状态 | 如果系统能够找到一个安全序列，则称系统处于安全状态。反之，则处于不安全状态。 |
避免死锁的实质 | 避免死锁的实质即为，系统在分配资源时，如何使系统不进入不安全状态。因为： 1) 不是所有的不安全状态都必然会转为死锁状态； 2) 只要系统处于安全状态，便可避免进入死锁状态。 |
银行家算法 | 数据结构 | 1) Available[m]：可利用资源向量。每个元素代表一类可利用的资源数目，其初始值为系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态改变。若Available[j]=K，则表示系统中现有Rj类资源K个。 2) Max[n,m]：最大需求矩阵。定义了系统中n个进程中的每一个进程对m类资源的最大需求，其数值保持不变。若Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。 3) Allocation[n,m]：分配矩阵。定义了系统中每个进程已分得的每一类资源的数目，其数值随该类资源的分配和回收而动态改变。若Allocation[i,j]=K，表示进程i当前已分得Rj类资源的数目为K。 4) Need[n,m]：需求矩阵。表示每一进程尚需的各类资源数，其数值随该类资源的分配和回收而动态改变。若Need[i,j]=K，表示进程i还需Rj类资源K个。 Need[i,j]= Max[i,j]- Allocation[i,j] |
银行家算法 | 设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 1) 若Requesti[j]≤Need[i,j]，便转向步骤2)，否则出错； 2) 若Requesti[j]≤Available[j]，便转向步骤3)，否则，表示尚无足够资源，Pi须等待； 3) 系统试探着把资源分配给进程Pi，并修改下列数据结构中的数值： Available[j]≔Available[j]-Requesti[j]; Allocation[i,j]≔Allocation[i,j]+Requesti[j]; Need[i,j]≔ Need[i,j]-Requesti[j]; 4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 安全性算法： 1) 初始化。设置两个向量： a) 工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work≔Alailable。 b) Finish，表示系统是否有足够的资源分配给进程，使之运行完成，含有n个元素。开始时先做Finish[i]≔false，当有足够资源分配给进程时，再令Finish[i]≔true。 2) 找安全序列。从集合中找到一个能满足下述条件的进程： a) Finish[i]=false； b) Need[i,j]≤Work[j]（j=1,2,…,m）（对比死锁检测算法2)）； 若找到，执行步骤3)，否则执行步骤4)； 3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放分配给它的资源，故应执行： a) Work[j]≔Work[j]+Allocation[i,j]（j=1,2,…,m）； b) Finish[i]≔true； 执行步骤2)； 4) 若所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则系统处于不安全状态。 （因为“所有的简化顺序都将得到相同的不可简化图”，故安全性算法中无需执行以下回溯操作a)和b)： a) 步骤2)回退一步，重新选择一个符合条件的进程，并执行3)；【只有所有可能序列（由选取进程的顺序决定）均遍历后均不能保证所有的Finish[i]=true，才说明不存在安全序列。】 b) 若步骤2)已回退至第一步，则可判断系统处于不安全状态。） |
死锁的检测与解除 | 死锁检测 | 实现手段 | 1) 保存有关资源的请求和分配信息； 2) 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态； |
资源分配图 | 由一组结点N和一组边E组成的一个对偶G=(N,E)： N=P∪R，P为进程结点集合，R为资源结点集合；E中的每一个边e都连接P中的一个结点和R中的一个结点，e={pi,ri}是资源请求边，由进程pi指向资源ri，e={ rj,pj}是资源分配边，由资源rj指向进程pj。 |
资源分配图简化 | 1) 在资源分配图中，找一个既不阻塞（请求资源可以得到响应）又非独立（有边与其相连，发出或指入）的进程结点Pi。消去其所有的请求边和分配边，使之成为孤立的结点（即Pi可以获得所请求的所有资源，运行完成并释放其占有的所有资源）。 2) 重复1)，若能消去图中的所有边，使所有的进程结点成为孤立结点，则称该图是可完全简化的；若不能通过任何的过程使改图完全简化，则称该图是不可完全简化的。（所有的简化顺序都将得到相同的不可简化图，即若用一种顺序得到不可简化图，则该图是不可完全简化的） |
死锁定理 | S为死锁状态的充要条件为当且仅当S状态的资源分配图是不可完全简化的。 |
死锁检测数据结构 | 类似银行家算法中的数据结构： Available[m]：可利用资源向量。每个元素代表一类当前可利用的资源数目。 Allocation[n,m]：分配矩阵。定义了系统中每个进程已分得的每一类资源的数目。 Request[n,m]：请求向量。表示每个进程请求的各种类型的资源的数目。 Work[m]：工作向量。表示系统可提供给进程继续运行所需的各类资源数目。 L：孤立进程表。包含已运行完且已释放所占有的所有资源的进程。 |
死锁检测算法 | 1) 初始化： a) Work≔Available； b) 将不占用资源的进程Pi（Allocation[i,j]=0(j=1,2,…,m)）记入表L；（一个进程如果没有占用任何资源（Allocation[i,j]=0 (j=1,2,…,m)），说明它要么：①还没开始运行，还没申请过任何资源；②已经执行完毕，把所有占用的资源都释放了。在这两种情况下，进程都不会再发起新的资源请求Request[i,j]=0 (j=1,2,…,m)。步骤b)的当前这种实现可以整合到2)中，并将步骤b)改为初始化L=∅） 2) 从进程集合中找一个Request[i,j]≤Work[j] (j=1,2,…,m) （对比银行家算法中的安全性算法2)b))）的进程Pi作如下处理： a) Work[j]≔ Work[j]+Allocation[i,j] (j=1,2,…,m)； b) 将进程Pi加入表L； 3) 重复步骤 2)，直到找不到满足条件的进程； 4) 若不能将所有进程都添入表L，则表明系统状态S的资源分配图是不可完全简化的，即该系统将发生死锁。（只要存在一种简化法不能将所有进程都放入L，便是不可完全简化） |
死锁解除 | 死锁解除方法 | 1) 剥夺资源。从其他进程剥夺足够数量的资源给死锁进程，以解除死锁状态。 2) 撤销进程。 a) 将所有死锁的进程均撤销；或 b) 按照某种顺序逐个撤销死锁进程，直至有足够的资源可用，使死锁状态消除为止。 |
死锁避免与死锁检测比较 | 1) 死锁避免（银行家算法）是对进程的某次请求进行判断； 2) 死锁检测是对进程今后状况的一次性判断。 3) 死锁避免（银行家算法）中的安全性算法与死锁检测中的死锁检测算法实质上是相同的算法，均是寻找安全序列：死锁避免（银行家算法）在将进程Pi请求的资源分配给Pi后进行的安全性算法实质是死锁检测，即死锁避免算法中包含死锁检测算法。 |
