死锁_gc376i6289ffbvt6

原因：资源竞争、同步互斥不当
条件：互斥、不剥夺、请求并保持、循环等待

死锁预防#

互斥条件：不可破坏
不剥夺条件：抢占资源（如 CPU，内存），但是不适用于打印机这类资源
请求并保持条件：运行前一次申请所有资源，不满足就不运行，导致饥饿，资源浪费
循环等待条件：顺序资源分配，给资源编号，必须按顺序请求资源，同类资源一次申请完。这种情况编号必须稳定，在资源新增时会被限制，资源浪费

死锁避免#

动态申请，单分配前计算安全性，防止进入不安全状态。如果不会进入不安全状态就分配。
银行家算法：系统按照某种进程推进顺序，分配所需资源，直到满足每个进程最大需求，每个进程都可完成。此时称为一个安全序列，如果无法找到一个安全序列，则是不安全状态。

检测与解除#

资源分配图

死锁定理：在分配图中，找出既不阻塞，又不孤点的进程 P，消除分配边和请求边。视为释放了资源，依次做，如果能够消除所有边就称为可完全简化。否则则是出现死锁。
解除：资源剥夺，进程撤销，进程回退（需要还原点）。

银行家算法#

输入：可用资源向量 Avaliable，进程已分配资源向量 Allocation，进程最大需求资源向量 Max
当进程发起请求 Request 时，如果 Request < Avaliable，继续，否则等待
尝试分配
Avaliable = Avaliable - Request
Allocation = Allocation + Request
用安全性算法检查此次分配之后，是否处于安全状态。

kotlin

class PRes(
    val MaxNeed: List<Int>
    val Allocation: List<Int>
    val Need: List<Int>
){
    fun allocable(avaliable List<Int>):Boolean {
        for i in avaliable {
            if (avaliable[i] - Need[i] < 0){
                return false
            }
        }
        return true
    }
    fun release(avaliable List<Int>):List<Int>{
        for i in avaliable {
            avaliable[i] += allocation[i]
        }
        return avaliable
    }
}
fun safe(pSet: List<PRes>){    
    safeSeq = emptyList()    
    while (true) {
        // 从 Need 中找出不在安全序列中
        // 且该行小于 Available 的进程加入安全序列
        val p = pSet.find { it.allocable(Available) }
	    if (p != null) {
            safeSeq.add(p)
            // 假设进入安全序列的进程顺利完成
            // 返回已分配的资源
            Available = p.release(Available)
	        needSet.remove(p)
        }else {
            break
        }
    }
    return needSet.isEmpty()
}

class PRes(
    val MaxNeed: List<Int>
    val Allocation: List<Int>
    val Need: List<Int>
){
    fun allocable(avaliable List<Int>):Boolean {
        for i in avaliable {
            if (avaliable[i] - Need[i] < 0){
                return false
            }
        }
        return true
    }
    fun release(avaliable List<Int>):List<Int>{
        for i in avaliable {
            avaliable[i] += allocation[i]
        }
        return avaliable
    }
}
fun safe(pSet: List<PRes>){    
    safeSeq = emptyList()    
    while (true) {
        // 从 Need 中找出不在安全序列中
        // 且该行小于 Available 的进程加入安全序列
        val p = pSet.find { it.allocable(Available) }
	    if (p != null) {
            safeSeq.add(p)
            // 假设进入安全序列的进程顺利完成
            // 返回已分配的资源
            Available = p.release(Available)
	        needSet.remove(p)
        }else {
            break
        }
    }
    return needSet.isEmpty()
}