死锁

起因：

• ①竞争不可抢占性资源引起死锁②竞争可消耗资源引起死锁③进程推进顺序不当引起死锁

定义：

• 如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的

必要条件：

• ①互斥条件：一个资源每次只能被一个进程使用。
• ②请求和保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
• ③不可抢占条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
• ④循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

处理方法：

• 预防死锁，避免死锁，检测死锁，解除死锁

• 这四种方法对死锁的防范程度逐渐降低
• 资源利用率不断提高
• 并发程度提高

预防死锁

• 破坏四个必要条件，互斥是非共享设备所必须的，所有破坏其他三个
• 破坏请求和保持

• 第一种协议

• 必须一次性运行过程中申请所需的全部资源
• 优点：简单，易行，安全
• 缺点：资源严重浪费，可能导致饥饿

• 第二种协议

• 只获得运行初期所需的资源，然后在运行过程中，释放资源，然后在请求新的资源

• 破坏不可抢占

• 当一个已经保持某种不可抢占资源后，提出新需求不能满足，必须释放已经保持的所有资源

• 缺点延迟了进程的周转时间，增加了系统开销，降低了系统吞吐量

• 破坏循环等待

• 赋予不同序号

避免死锁

• 基本思想：确保系统始终处于安全状态
• 将系统状态分为安全和不安全，资源分配前会判断是否安全
• 银行家算法

检测死锁

• 资源分配图

• 圆：进程，方框：资源
• 方法：将资源分配图简化
• 过程：先找一个既不阻塞又非独立的进程p1，顺利情况下，p1可以获取所有资源并释放，然后去掉该边，使其变为独立点，依次执行，然后如果所有都独立，那么称为可完全简化，否则成为不可完全简化的。
• 死锁定理：当且仅当S状态的资源分配图是不可完全简化的。

解除死锁

• 抢占资源
• 终止进程

各种锁

银行家算法

每一个新进程在进入系统时，他必须声明在运行的过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量

因素：

(1) 可利用资源向量Available。

(2) 最大需求矩阵Max。

(3) 已分配给该进程的资源Allocation。

(4) 需求矩阵Need。

求解：是否安全及执行顺序，新的需求是否安全

解题思路：

1、 先求need矩阵。是Max-Allocation就得到Need矩阵。

2、 系统安全性分析，Work、Need、Alloaction、Work+Allocation,

3、 第一个进程。Work的初始化等于Available，然后Need、Alloaction都是填写步骤一对应的need。Work+Allocation也就是加法。

4、 关于安全序列并不唯一，就比较work跟need，Need[i, j]≤Work[j];就可以选择执行。

5、 第二个进程的Work是第一行的Work+Allocation，第一个进程已经结束释放掉了。后面对应的都是这样

6、 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；

7、 关于请求Request，首先判断与need，Available大小。然后假设满足。将Request的值跟原Allocation相加得到新Allocation，Available也要减少对应的值。

8、 每个进程还需要多少进程才能满足，即Request的值 = Need - Allocation